Term
|
Definition
•For each feature:
•Add a production to the grammar
•Specify an abstract syntax for the new production
•Add the appropriate evaluation functionality to handle the new
language feature (i.e. new cases clauses, new procedures) |
|
|
Term
|
Definition
•A closure is a self-contained package that contains everything a
procedure needs to be applied
•Procedure body
•List of all formal parameters
•Bindings for the procedure's free variables at the time the closure
was created
•It is convenient to store the entire creation environment of a
procedure rather than just the bindings for free variables |
|
|
Term
| Applying a procedure with apply-procedure |
|
Definition
•Accepts the procedure and its argument
•Retrieves the environment that was saved at the time the procedure
was created
•Extends that environment with bindings for the procedure's
parameters
•Evaluates the body of the procedure in the new extended
environment
(define apply-procedure
(lambda (proc1 arg)
(cases proc proc1
(procedure (var body saved-env)
(value-of body
(extend-env var arg saved-env)))))) % EXPLICIT-REFS
(extend-env var (newref arg) saved-env)))))) % IMPLICIT-REFS |
|
|
Term
|
Definition
| pointers to data stored in memory (the data store) |
|
|
Term
|
Definition
In EXPLICIT-REFS: allocates a new location in memory and returns a
reference to that location |
|
|
Term
|
Definition
In EXPLICIT-REFS: returns the data stored in the location to which the
reference points |
|
|
Term
|
Definition
In EXPLICIT-REFS: changes the contents of the location to which the
reference points
The setref! procedure recursively iterates through the memory until it
finds the location to update, then updates it (Very inefficient) |
|
|
Term
| Explicit vs. Implicit References |
|
Definition
•Previous interpreter utilized explicit references
•Reference allocation (newref), dereferencing (deref), and
modifications (setref) are explicit in the programmer's code
•References are not automatically created by interpreter
•Many programming languages will automatically create references as
needed
•Programmer need not explicitly specify references
•References are implicitly defined by the language |
|
|
Term
| EXPLICIT-REFS vs. IMPLICIT-REFS |
|
Definition
•Like EXPLICIT-REFS, IMPLICIT-REFS uses a "memory" to store data
•EXPLICIT-REFS allows references as expressed values as shown below
•In IMPLICIT-REFS, references are only used as denoted values
•No more pointers to pointers
•All variables (denoted values) are references
EXPLICIT-REFS
ExpVal = Int + Bool + Proc + Ref(ExpVal)
DenVal = ExpVal
IMPLICIT-REFS
ExpVal = Int + Bool + Proc
DenVal = Ref(ExpVal) |
|
|
Term
| Designing an Interface for a Recursive Data Type |
|
Definition
1. Include one constructor for each kind of data in the data type
2. Include one predicate for each kind of data in the data type
3. Include one extractor for each piece of data passed to a
constructor of the data type |
|
|
Term
|
Definition
•Specifies the constructors for building the data type
•Specifies the observers for testing (predicates) and extracting data
(extractors) |
|
|
Term
|
Definition
•An interpreter consists of two parts:
•A front end converts program text (a program in the source language)
into an abstract syntax tree
•An evaluator (the actual interpreter) examines the abstract syntax tree
and performs some associated actions which depend on the
structure of the tree |
|
|
Term
|
Definition
•A compiler translates program text into some other language (the target language)
•A compiler consists of:
•A front end converts program text into an abstract syntax tree
•A series of compiler phases, for tasks such as semantic analysis, optimization,
code emission, etc.
•An interpreter to evaluate the compiled language
•May be a processor evaluating machine code, or a virtual machine evaluating
byte code) |
|
|
Term
| Source, Host, and Target Language |
|
Definition
•The source language (or defined language) is the language in which we
write programs that should be evaluated by an interpreter.
•The host language (or defining language) is the language in which we
specify the interpreter.
•The target language is the language a source language in translated to
by a compiler. A target language may be a higher-level programming
language (e.g. C) or assembly language (or machine language). |
|
|
Term
|
Definition
•The front end does the scanning & parsing
•Scanner divides input sequence of characters into tokens
•Parser organizes sequence of tokens into a syntactic structure (e.g. an
abstract syntax tree)
•Building a parser by hand can be tedious
•Lexical analyzer generators (e.g. lex) automatically generate scanners
from some specification (e.g. lex, flex, ANTLR)
•Parser generators (compiler-compilers) automatically generate parsers
from a grammar specification (e.g. yacc, Bison, ANTLR) |
|
|
Term
| Environment-Passing Interpreter |
|
Definition
•LET interpreter is an environment-passing interpreter
•The environment is a data structure containing name-to-value bindings
• The initial environment represents the default set of name-to-value
bindings for the interpreter
•Values are added to the environment when new variables are defined
• When evaluating operands in an expression, we have to lookup
identifiers in the environment to determine their values
•The initial environment can be configured with default bindings for any
number of identifiers
•The empty-env is extended for each new binding |
|
|
Term
| Updating the Environment Datatype |
|
Definition
•Add a new variant to the environment datatype
•extend-env is used for let expressions
•extend-env-rec is used for letrec expressions
•Stores the name, bound variables, and the body of the recursive
procedure in the environment |
|
|
Term
|
Definition
| the value of expression exp in environment p should be val |
|
|
Term
| the association between a variable and its value is called |
|
Definition
a binding
the extent of a binding is the time interval during which the binding is maintained. in our language, as in scheme, this is dynamic |
|
|
Term
| the scope of the declaration |
|
Definition
| the potion of the program in which a declaration is valid |
|
|
Term
|
Definition
Lexical depth of a variable is equivalent to the number of contours
crossed when searching from the variable reference to its declaration |
|
|
Term
| what's the difference between producing a value and producing an effect? |
|
Definition
| an effect is global: it is seen by the entire computation. An effect affects the entire computation |
|
|
Term
| How does assignment differ from binding? |
|
Definition
| As we have seen, binding is local, but variable assignment is potentially global. It is about the sharing of values between otherwise unrelated portions of the computation. Two procedures can share information if they both know about the same location in memory. A single procedure can share information with a future invocation of itself by leaving the information in a known location. |
|
|
Term
|
Definition
| Build values of a given data type |
|
|
Term
|
Definition
•Extract information from a representation of the data type
•Test to see if value is a representation of a particular data type |
|
|
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 (the variable name denotes a value) |
|
|
Term
|
Definition
| a data structure containing name-to-value bindings |
|
|
Term
|
Definition
represents the default set of name-to-value
bindings for the interpreter |
|
|
Term
| Evaluating Simple Expressions |
|
Definition
• Constant expression return a typed version of themselves
• Variables are looked up in the environment and returned if they exist
(define value-of
(lambda (exp env)
(cases expression exp
...
(const-exp (num) (num-val num))
(var-exp (var) (apply-env env var))
...
))) |
|
|
Term
|
Definition
• Use Scheme's own let own procedure to bind the value of exp1 in the
current environment
• Extract the numerical values from exp1
• Evaluate the numerical value, returned a typed version of a boolean |
|
|
Term
| Evaluating Difference Expressions |
|
Definition
• Use Scheme's own let own procedure to bind the values of exp1 and
exp2 in the current environment
• Extract the numerical values from exp1 and exp2
• Evaluate the difference and return a typed version of the result |
|
|
Term
|
Definition
• Evaluates the test expression (exp1) in the current environment and
binds the result to val1
• If the boolean value of val1 evaluates to #t according to Scheme's
own if expression, then evaluate the true expression (exp3)
• Otherwise, evaluate the false expression (exp3) |
|
|
Term
|
Definition
The let expression (let-exp) creates a temporarily extended set of
environment bindings for evaluating an expressions and then evaluates
an expression relative to that temporary environment
(let-exp (var exp1 body)
(let ((val1 (value-of exp1 env)))
(value-of body
(extend-env var val1 env)))) % EXPLICIT-REFS
(extend-env var (newref val1) env)))) % IMPLICIT-REFS |
|
|
Term
|
Definition
• Extracts the var and the body from the expression
• Calls the procedure constructor and saves var, body and the current
environment (env) into a closure
• Returns a typed version of the closure
(define value-of
(lambda (exp env)
(cases expression exp
...
(proc-exp (var body)
(proc-val (procedure var body env)))
...
))) |
|
|
Term
|
Definition
• Evaluates the rator in the current environment and binds the extracted
procedure value to proc using Scheme's let procedure
• Evaluates the rand in the current environment and binds the result to
arg using Scheme's let procedure
• Passes the proc closure and its actual parameter (arg) to applyprocedure
for evaluation
(define value-of
(lambda (exp env)
(cases expression exp
...
(call-exp (rator rand)
(let ((proc (expval->proc (value-of rator env)))
(arg (value-of rand env)))
(apply-procedure proc arg)))
...
))) |
|
|
Term
| Variables appear in two different ways |
|
Definition
• As a reference - a use of a variable
(f x y)
• As a declaration - introduces a variable as a name of some value
(lambda (x) (+ x 3)) |
|
|
Term
|
Definition
| All programming languages have scoping rules for their variables |
|
|
Term
|
Definition
In lexical scoping, the scope of a variable can be determined by
searching from the variable reference outward until the variable
declaration is found |
|
|
Term
|
Definition
• The scope of lexical variables can be determined statically
• Lexical scoping allows variable names to be shadowed and reused
• Lexical scopes are nested |
|
|
Term
|
Definition
| Lexical position is a variables position within a scope |
|
|
Term
|
Definition
Lexical address identifies a variable based on lexical information
• (x:d p) where d is the lexical depth and p is the lexical position
• Lexical depth is typically 0 based indexing
• Eliminates the need for variable names
• Useful for finding variables in an environment data structure |
|
|
Term
|
Definition
• Computations may also have effects on a system
• Reading input files
• Printing output
• Modifying memory |
|
|
Term
|
Definition
Variable bindings are local whereas assignments can be global
• Assignments are made to share values between different portions of a
computation (e.g. different procedures)
• Two procedures can share info through a common memory location
• A single procedure can maintain some state between invocations |
|
|
Term
|
Definition
• References are explicitly defined by programmer
• References are pointers to data stored in memory (the data store)
• Storable values are typically the same as expressed values
• Instead of accessing actual memory, memory is modeled in our
EXPLICIT-REFS interpreter as a Scheme list |
|
|
Term
|
Definition
• A procedure can create private variables to store some hidden state
• The reference to the counter value is stored in func's closure and
is accessible in the body of func
• On each call to func the reference to counter is always the same
• The value stored in the location that counter points to changes |
|
|
Term
| Grammar Additions for EXPLICIT-REFS Language |
|
Definition
• Three new expression types are added to the grammar to handle
references
• A production to create new references
• A production to dereference references
• A production to set the value in the location to which a reference
points |
|
|
Term
|
Definition
• The begin-exp evaluates multiple expressions exp1 and exps
• Returns the result of the last expression evaluated |
|
|
Term
| Variables as References in IMPLICIT-REFS |
|
Definition
• All variables denote a reference
that points to some location in
the data store (i.e. "memory")
• A location in the data store is created for each binding operation
• (i.e. procedure calls, let, and letrec expressions)
• No longer adding (Var, ExpVal) to the environment
• Add (Var, Ref(ExpVal)) to the environment, and store ExpVal in
the data store |
|
|
Term
|
Definition
• In assign-exp :
• var represents the variable being assigned a new value
• exp1 represents the value being assigned to the variable
• The expression exp1 must be evaluated before its value can be stored
• The variable var is looked up in the environment to determine the
memory location to which the new value should be written
(define value-of
...
(assign-exp (var exp1)
(begin
(setref!
(apply-env env var)
(value-of exp1 env))
(num-val 27))) % arbitrary return value
)))
The setref! procedure recursively iterates through the memory until it
finds the location to update, then updates it (Very inefficient) |
|
|
Term
|
Definition
• New locations should be allocated at every new binding
• New bindings are created in four different cases
• Initial environment creation
• let expressions
• procedure calls
• letrec expressions |
|
|
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 procedure
• Modifications to a variable within a procedure are local to that
procedure
• The procedure does not have access to the reference of the actual
parameter that was passed into the procedure |
|
|
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
| CALL-BY-REFERENCE vs. IMPLICIT-REFS |
|
Definition
• In CALL-BY-REFERENCE, expressed and denoted values are the same
as they were in IMPLICIT-REFS
• In IMPLICIT-REFS, using call-by-value, new "memory" locations are
created in the data store for each argument passed to a procedure
• In CALL-BY-REFERENCE, new "memory" locations are only allocated
when the argument is not a variable
• Variables already refer to a location in "memory" |
|
|
Term
|
Definition
• Many programming language evaluate each operand before passing a
value/reference to a procedure
• In lazy evaluation an operand in a procedure call is not evaluated until
is it needed by the procedure body
• If the procedure body never refers to the parameter, then it is never
evaluated
• Consider the following example
• Without lazy evaluation, it never terminates
• With lazy evaluation is returns 11
leterec infinite-loop (x) = infinite-loop(-(x,-1))
in let f = proc (z) 11
in (f (infinite-loop 0)) |
|
|
