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
|
|
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 = declared
second 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 = referenced
first y = referenced |
|
|
Term
|
Definition
the use of the variable
bound by the declaration with which it is associated |
|
|
Term
|
Definition
| introduction of the variable as a name for some value |
|
|
Term
|
Definition
| the rules every programming language has to determine the declaration to which each variable refers |
|
|
Term
|
Definition
| the portion of the program in which a delaration is valid |
|
|
Term
|
Definition
| variables declared in this fashion are sometimes called private variables |
|
|
Term
|
Definition
| also known as static scoping |
|
|
Term
|
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
|
Definition
| can be determined statically |
|
|
Term
|
Definition
| allows variables names to be shadowed and resued |
|
|
Term
|
Definition
|
|
Term
|
Definition
the number of contours crossed when searching from the variable reference to its declaration
0 based indexing |
|
|
Term
|
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
|
Definition
| association between a variable and its value |
|
|
Term
| anything that occurs at runtime is said to be ...? |
|
Definition
|
|
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
|
Definition
| converts program text into an abstract syntax tree, does the parsing and scanning |
|
|
Term
|
Definition
| examine the abstract syntax tree and performs some associated actions which depend on the strucuture of the tree |
|
|
Term
|
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
|
Definition
| also known as the define language, is the language in which we write programs that should be evaluated by an interpreter |
|
|
Term
|
Definition
| also known as the defining language, it is the language in which we specify the interpreter |
|
|
Term
|
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
|
Definition
| divides input sequence of characters into tokens |
|
|
Term
|
Definition
| organizes sequence of tokens into a syntactic structure (e.g. an abstract syntax tree) |
|
|
Term
|
Definition
| this parser generator takes as input a lexical specification and a grammer, and produces as output a scanner and a parser |
|
|
Term
|
Definition
| assign some meaning to every element of an abstract syntax tree |
|
|
Term
|
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
|
Definition
| values that are bound to variables in an environment |
|
|
Term
|
Definition
| environment passing interpreter |
|
|
Term
|
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
|
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 = 5
in -(x,5) |
|
Definition
| x and y are local bindings. all variable bindings are local whereas assignments can be global |
|
|
Term
| what are assignments made for? |
|
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
|
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
|
Definition
| allocates a new location in memory and returns a reference to that location |
|
|
Term
|
Definition
| returns that data stored in the location to which the reference points |
|
|
Term
|
Definition
| changes the contents of the location to which the reference points |
|
|
Term
| what does the line let x = newref(0) to? |
|
Definition
|
|
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
|
|
Term
ExpVal = Int + Bool + Proc
DenVal = Ref(ExpVal) |
|
Definition
|
|
Term
Expval = Int + Bool + Proc
DenVal = Int + Bool + Proc |
|
Definition
|
|
Term
ExpVal = Int + Bool
DenVal = Int + Bool |
|
Definition
|
|
Term
|
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 points
2. 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 = 5
in -(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 store
the two new references are assigned to the variables x and y
the variables x and y are added to the environment |
|
|
Term
|
Definition
lambda forms bind members of the parameter list to a value
(lambda (x) (- x 3))
x is bound |
|
|
Term
|
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
|
|
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 expressions
procedure calls
letrec expressions |
|
|
Term
|
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
|
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
|
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
|
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
|
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 it
call by name
call by need |
|
|
Term
|
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
|
|
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
|
|
Term
|
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
|
|
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
|
|
Term
|
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 refs
second 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 environment
if 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 |
|
|
