# Shared Flashcard Set

## Details

Programming Systems and Languages
Scheme stuff
93
Computer Science
10/27/2009

Term
 in what ways can variables appear when it comes to their scoping and binding?
Definition
 as a reference and as a declaration
Term
 in what way is the following variable bound?(f x y)
Definition
 reference
Term
 in what way is the following variable bound(lambda (x) (+ x 3))
Definition
 declaration - introduces a variable as a name of some value
Term
 in what way is the first x bound in the following?in what way is the second x bound in the following?(lambda (x) (+ x 3))
Definition
 first x = declaredsecond x = referenced
Term
 in what way is the first x bound in the following?in what way is the second x bound in the following?in what way is the y bound in the following?(let ((x (+ y 7))) (+ x 3))
Definition
 first x = declared second x = referencedfirst y = referenced
Term
 reference
Definition
 the use of the variable bound by the declaration with which it is associated
Term
 declaration
Definition
 introduction of the variable as a name for some value
Term
 scoping rules
Definition
 the rules every programming language has to determine the declaration to which each variable refers
Term
 scope
Definition
 the portion of the program in which a delaration is valid
Term
 lexical scoping
Definition
 variables declared in this fashion are sometimes called private variables
Term
 lexical scoping
Definition
 also known as static scoping
Term
 lexical scoping
Definition
 sets the scope of a variable so that it may be called from within the block of code in which it is defined
Term
 lexical variables
Definition
 can be determined statically
Term
 lexical scoping
Definition
 allows variables names to be shadowed and resued
Term
 lexical scopes
Definition
 are nested
Term
 lexical depth
Definition
 the number of contours crossed when searching from the variable reference to its declaration 0 based indexing
Term
 lexical position
Definition
 is a variable position within a scope
Term
Definition
 identifies a variable based on its lexical information (x:d p) where d is the lexical depth and p is the lexical position
Term
 binding
Definition
 association between a variable and its value
Term
 anything that occurs at runtime is said to be ...?
Definition
 dynamic
Term
Definition
 predicts where in the environment any particular variable will be found
Term
 source language or defined language
Definition
 text of the program written in the language we are implementing
Term
 what are the parts of a an interpreter ?
Definition
 front end and an evaluator
Term
 front end
Definition
 converts program text into an abstract syntax tree, does the parsing and scanning
Term
 evaluator
Definition
 examine the abstract syntax tree and performs some associated actions which depend on the strucuture of the tree
Term
 compiler
Definition
 translates program text into some other language (the target language)divided into two parts: an analyzer and a translator
Term
 what does a compiler consist of ?
Definition
 front end, series of compiler phases and an interpreter to evaluate the compiled language
Term
 source language
Definition
 also known as the define language, is the language in which we write programs that should be evaluated by an interpreter
Term
 host language
Definition
 also known as the defining language, it is the language in which we specify the interpreter
Term
 target language
Definition
 is the language a source language is translated to by a compiler. May be a higher-level programming language (C) or assembly language or machine language
Term
 scanner
Definition
 divides input sequence of characters into tokens
Term
 parser
Definition
 organizes sequence of tokens into a syntactic structure (e.g. an abstract syntax tree)
Term
 SLLGEN
Definition
 this parser generator takes as input a lexical specification and a grammer, and produces as output a scanner and a parser
Term
 interpreters
Definition
 assign some meaning to every element of an abstract syntax tree
Term
 expressed values
Definition
 values that can be specified by means of an expression in the given programming language (i.e. values that can be the result of the evaluation of an expression)numbers, pairs, characters, strings....
Term
 denoted values
Definition
 values that are bound to variables in an environment
Term
 LET interpreter
Definition
 environment passing interpreter
Term
 environment
Definition
 data strucuture containing name-to-value bindings
Term
 let expression for the LET interpreter
Definition
 creates a temporarily extended set of environment bindings for evaluating an expression and then evaluates an expression relative to that temporary environment
Term
 procedures for the LET interpreter
Definition
 are represented as first-class (expressed) values in the PROC language
Term
 what happens when a procedure is called?
Definition
 the body of the procedure is evaluated in an environment that has bindings for the procdure's parameters
Term
 closure
Definition
 a self-contained package that contains everything a procedure needs to be applied
Term
 what is wrong with the follow code segment?let double(x) = if zero?(x) then 0 else -((double -(x,1), -2)in (double 6)
Definition
 attempts to use the double procedure (recursively) before it is bound instead of using let your must use letrec
Term
 what does apply-env do in the LET interpreter?
Definition
 searches the environment for a symbol
Term
 in the following code segment..are the variable bindings local or global?let x = 10 y = 5in -(x,5)
Definition
 x and y are local bindings. all variable bindings are local whereas assignments can be global
Term
Definition
 to share values between different portions of a computation (e.g. different procdures)
Term
 in EXPLICIT-REFS what are references?
Definition
 pointers to data stored in memory (the data store)
Term
 EXPLICIT-REFS
Definition
 adds memory references to our language. instead of accessing acutal memory, memory is modeled in the form of a scheme list. references are not automatically created by the interpreter
Term
 newref
Definition
 allocates a new location in memory and returns a reference to that location
Term
 deref
Definition
 returns that data stored in the location to which the reference points
Term
 setref
Definition
 changes the contents of the location to which the reference points
Term
 what does the line let x = newref(0) to?
Definition
 creates a reference to x
Term
 what does the line = if zero?(deref(x)) do?
Definition
 get the value that x points to and checks to see if that value is 0
Term
 what does the following line of code do?setref(x,13)
Definition
 sets the memory location that x points to, to 13
Term
 what is the visibility of the following variable ?let func = let counter = newref(0) in proc(dummy) begin .... ..... end .....
Definition
 counter is a private variable that is stored in func's closure and is accessible in the body of func
Term
 explain the following procedure let func = let counter = newref(0) in proc(dummy) begin setref(counter, -(deref(counter),-1)) deref(counter) end in let a = (func 11) in let b = (func 11) in = (a,b)
Definition
 this procedure keeps a private variable that stores the number of times func has been called. on each call to func the reference to counter is always the same. The value stored in the location that counter points to changes. Hence, on the first call to func the return value is 1, the second call to func returns 2 and the entire program returns the value -1
Term
 explain the following sequence of code from the EXPLICIT-REFS interpreter(define value-of ... (newref-exp (exp1) (let ((v1 (value-of exp1 env))) (ref-val (newref v1))))...)))(define newref (lambda (val) (let ((next-ref (length the-store))) (set! the-store (append the-store (list val))) next-ref)))
Definition
 this is the definition of the new-ref expression. exp1 represents the value to be stored in memory. exp1 must be evaluated before it can be stored. this procedure takes the value-of the exp1 in the environment and sets that value to v1. it then creates a new reference with that value in v1. it returns a refernce to the location at which it was stored.
Term
 why can the return value for setref-exp be ignored?
Definition
 becuase setref takes two arguments, 1. the memory location that is to be modified and 2. the new value to be stored in the memory location referenced by location
Term
 why is the setref procedure so inefficient ?
Definition
 because it recursively iterates through the memory until it finds the location to update, then updates it
Term
 what is the similarity between EXPLICIT-REFS and IMPLICIT-REFS?
Definition
 both use memory to store data
Term
 what is the difference between EXPLICIT-REFS and IMPLICIT-REFS?
Definition
 EXPLICIT-REFS allows references as expressed values. in IMPLICIT-REFS references are only used as denoted values
Term
 ExpVal = Int + Bool + Proc + Ref(ExpVal)DenVal = Expval
Definition
 EXPLICIT-REFS
Term
 ExpVal = Int + Bool + ProcDenVal = Ref(ExpVal)
Definition
 IMPLICIT-REFS
Term
 Expval = Int + Bool + ProcDenVal = Int + Bool + Proc
Definition
 PROC Interpreter
Term
 ExpVal = Int + BoolDenVal = Int + Bool
Definition
 LET Interpreter
Term
 IMPLICIT-REFS
Definition
 All variables denote a reference that points to some location in that data store (i.e. memory)a location in the data store is created for each binding operation (procedure calls, let, and letrec)uses "the store"new references are created for each procedure call
Term
 explain the processing of finding variables in IMPLICIT-REFS
Definition
 two step process. 1. look up the variable in the environment to determine the location in "memory" to which it points2. retrieve the value from the data store at the location pointed to by the variable(var-exp (var) (deref (apply-env env var)))
Term
 explain how IMPLICIT-REFS would handle the execution of the following...let x = 10 y = 5in -(x,y)
Definition
 two location are allocated in the data store to hold the values x =10 and y = 5 two new references are created that point to the locations in the data storethe two new references are assigned to the variables x and y the variables x and y are added to the environment
Term
 bound variable
Definition
 lambda forms bind members of the parameter list to a value (lambda (x) (- x 3))x is bound
Term
 free-variable
Definition
 a variable not bound to a region (lambda (x) (- x 3)) (+ x 7))x is bound in the first half and free in the second half
Term
 state whether the occurs free expression is true or false.(occurs-free? 'x 'x)(occurs-free? 'x 'y)(occurs-free? 'x '(lambda (x) (x y)))(occurs-free? 'x '(lambda (y) (x y)))(occurs-free? 'x '((lambda (x) x) (x y)))(occurs-free? 'x '((lambda (y) (lambda (z) (x (y z)))))
Definition
 (occurs-free? 'x 'x) => #t(occurs-free? 'x 'y) => #f(occurs-free? 'x '(lambda (x) (x y))) => #f(occurs-free? 'x '(lambda (y) (x y))) => #t(occurs-free? 'x '((lambda (x) x) (x y))) => #t(occurs-free? 'x '((lambda (y) (lambda (z) (x (y z))))) => #t
Term
 when does the initial assignment to a variable occur using IMPLICIT-REFS
Definition
 at the time of binding
Term
 what does the set expression do in IMPLICIT-REFS
Definition
 changes the value in the data store that a variable references
Term
 name the four cases in which new bindings are created
Definition
 new locations should be allocated at every new binding initial environment creation let expressionsprocedure callsletrec expressions
Term
 call-by-value
Definition
 the argument expression is evaluated, and the resulting value is bound to the corresponding variable in the function (frequently by copying the value into a new memory region). If the function or procedure is able to assign values to its parameters, only its local copy is assigned — that is, anything passed into a function call is unchanged in the caller's scope when the function returns. it is not a single evaluation strategy, but rather the family of evaluation strategies in which a function's argument is evaluated before being passed to the function. new references are created each time a variable is bound, including when a procedure is called most common form of parameter passing denoted value is a reference to a location containing the expressed value of the actual parameter
Term
 call-by-reference
Definition
 a function receives an implicit reference to the argument, rather than a copy of its value. This typically means that the function can modify the argument- something that will be seen by its caller. has the advantage of greater time- and space-efficiency (since arguments do not need to be copied), as well as the potential for greater communication between a function and its caller (since the function can return information using its reference arguments), but the disadvantage that a function must often take special steps to "protect" values it wishes to pass to other functions.a new location is created for every evaluation of an operand other than a variable
Term
 call-by-name
Definition
 the arguments to functions are not evaluated at all — rather, function arguments are substituted directly into the function body using capture-avoiding substitution. If the argument is not used in the evaluation of the function, it is never evaluated; if the argument is used several times, it is re-evaluated each time.in the var-exp we first find the location to which the variable is bound. if the location contains an expressed value, then that value is returned as the value of the var-exp. if it instead contains a thunk then the thunk is evaluated and that value is returned
Term
 call-by-need
Definition
 is a memoized version of call-by-name where, if the function argument is evaluated, that value is stored for subsequent uses. In a "pure" (effect-free) setting, this produces the same results as call-by-name; when the function argument is used two or more times, this method is almost always faster.once we find the value of the thunk, we can install that expressed value in the same location, so that the thunk will not be evaluated again
Term
 lazy-evaluation
Definition
 an operand in a procedure call is not evaluated until it is needed by the procedure body. if the body never refers to the parameter, then there is no need to evaluate itcall by namecall by need
Term
 thunk
Definition
 consists of an expression and an environment. used when a procedure needs to use the value of its bound variable.
Term
 DenVal = Ref(ExpVal + Thunk)ExpVal = Int + Bool + Proc
Definition
 lazy evaluation call by name call by need
Term
 what interpreter is this program using?let x = 0 % create a new reference to x in letrec even(dummy) = if zero?(x) % automatically dereference x then 1 else begin set x = -(x,1); % assign a new value to x (odd 888) end odd(dummy) = if zero?(x) then 0 else begin set x = -(x,1); (even 888) end in begin set x = 13; % assign a new value to x (odd 888) end
Definition
 IMPLICIT-REFS because the features of newref and deref are happening automatically.
Term
 which interpreter does the following use ?let func = let counter = newref(0) in proc(dummy) begin setref(counter, -(deref(counter), -1)) deref(counter) end in let a = (func 11) in let b = (func 11) in -(a,b)
Definition
 EXPLICIT-REFS
Term
 Which interpreter does the following use?let func = let counter = 0 in proc(dummy) begin set counter = -(counter, -1); counter end in let a = (func 11) in let b = (func 11) in -(a,b)
Definition
 IMPLICIT-REFS
Term
 call-by-value 2
Definition
 new references are created each time a variable is bound, including when a procedure is called makes a copy of arguments passed into a procedure when a procedure assigns a new value to one of its parameters, the change cannot be seen by the caller only the copy of the variable is assigned
Term
 under call-by-value what does this return let func = proc (x) set x = 4 % func creates a copy of x in let a = 3 % set a to 3 in begin (func a); % pass a to func with CBV a % a = 3 is returned here end
Definition
 3 is returned
Term
 under call by reference what is returned let func = proc (x) set x = 4 % func gets reference to x in let a = 3 % set a to 3 in begin (func a); % pass a to func with CBR a % a = 4 is returned here end
Definition
 4 is returned
Term
 call by reference 2
Definition
 instead of copying an argument, as in call-by-value, a reference to the original value is passed to a procedure when a procedure assigns a new value to one of its parameters, the change will be seen by the caller a typical use is to return multiple values from a procedure
Term
 what is returned for CBV and CBR for the following procedure let swap = proc (x) proc (y) let temp = x in begin set x = y; set y = temp end in let a = 33 in let b = 44 in begin ((swap a) b); -(a,b) end
Definition
 CBV = -11 because only a copy is made and the actual values to which x and y refer are never altered CBR = 11 because swap gets a reference to x and y and the actual values of x and y are altered
Term
 in IMPLICIT-REFS CBV what happens when to the arguments passed to a procedure?
Definition
 new "memory" locations are created in the data store
Term
 give the interpreter being used for each of the following (define apply-procedure (lambda (proc1 arg) (cases proc proc1 (procedure (var body saved-env) (value-of body (extend-env var (newref arg) saved-env)))))) (extend-env var arg saved-env))))))
Definition
 first line is implicit refssecond line is call by ref
Term
 what does the value of operand procedure do?(define value-of-operand (lambda (exp env) (cases expression exp (var-exp (var) (apply-env env var)) (else (newref (value-of exp env))))))
Definition
 checks to see if the input expression is a variable if yes, retrieve the value of the variable from the environmentif no, then evaluate the expression, store the result in memory, create a new reference to that value, return the new reference so that it can be passed to a procedure
Supporting users have an ad free experience!