Scheme Prelude: A Puzzle
• This puzzle should reveal something about Scheme syntactic expansion and variable binding.
• What does execution of the following code do? Try to figure it out yourself, rather than simply entering it into Scheme. Hint: It does NOT produce an error.
(define mystery
(lambda ‘x ‘x))
• •
•
•
Talk with someone near you and try to figure it out.
Can you write some code that applies this mystery procedure in such a way that it returns a value (not an error)?
(mystery )
; you fill in the argument(s)
CSSE 304 Days 16-17 Environments and Closures
1
Syntax Semantics
• define-datatype and parse-exp give us a way to get from a concrete representation of program syntax to a more abstract one.
• Now we want to get the meaning (interpretation).
• How do we implement lexical scoping with first- class procedures?
• First question: How to represent the bindings of data to variables?
• We will spend a couple of class days taking an abstract look at this, then we will look at concrete implementations of environments
Some data structures behind Scheme’s execution mechanism
Many students have found this to be a difficult topic.
We will spend today, the next class meeting, and perhaps part of the one after that on it.
Don’t allow yourself to get lost during either class!
Ask instead!
ENVIRONMENTS AND CLOSURES
2
Variable bindings and environments
• Anenvironmentisatableofvariablenames(symbols) and their associated values
a
#t
xyz
“xyz”
i
4
j
7
Variable bindings and environments • The global (top-level) environment is dynamic;
symbols are added to the environment via define • the values of symbols are changed via set!
However car proc is represented
However + proc is represented
car
+
3
Variable bindings and environments • TSPL section 2.9 says:
Variables must be defined before they can be assigned
• But in many Scheme versions (including Chez) ,
– a set! of a previously undefined variable actually defines it.
• Thus at the top level, define and set! seem to be equivalent, although really they should be used for different things.
• Your interpreter will only be required to implement set! for defined variables.
local environments
• When a lambda-defined procedure is applied to arguments (also when a let, let*, or letrec is executed), a new local environment is created to hold the bindings of the variables that are defined at that level.
• When Scheme evaluates an expression, there is always a current local environment. If the expression is outside of all lambdas, lets, let*s, and letrecs, letrecs, that current local env. is null.
.. .
4
Evaluate a let expression
a. Evaluate (in the current local environment) the expression
to get the values to be assigned to the let variables
b. Create a new local environment with bindings for the let variables. Its “enclosing environment” pointer points to the current environment.
c. Evaluate the body of the let in this new environment. > (define a 5)
> (let ([z (+ a 3)]
[t 7])
(let ([y (+ z a)])
(list a t z y)))
“Evaluate exp in env” means “evaluate exp, with env as the current environment.”
s
Interlude
Tom Swifties (most are from Wikipedia):
“Who left the toilet seat down?” Tom asked peevishly.
“I’ll never again put my arm in a lion’s mouth,” Tom said off-handedly.
“Can I go looking for the Holy Grail again?” Tom requested.
“I unclogged the drain with a vacuum cleaner,” Tom said succinctly.
“We just struck oil!” Tom gushed.
“They had to amputate them both at the ankles,” Tom said defeatedly.
“Who discovered radium?” asked Marie curiously.
“Hurry up and get to the back of the ship,” Tom said sternly.
“Who put the moss in the bog again?” asked Tom repeatedly.
“A word that contains all five English vowels plus y? And I suppose you want them to appear in alphabetical order!” said Tom facetiously.
“The robber is coming down the stairs”, Tom said condescendingly. “Nnnn”, Tom murmured forensically.
5
Procedures (closures)
• When a lambda-expression is evaluated, what is returned?
• When does the body of a lambda- expression get evaluated?
• What kind of info needs to be stored in a procedure?
• What happens when a procedure is applied?
(Answers on the next few slides)
Procedures (closures)
• Wheneveralambdaexpressionisevaluated,a
procedure (also known as a closure) is created
• Aclosureconsistsofthreeparts.
• Note that a lambda expression is not a procedure. What is it?
• Is the body of a lambda expression ever evaluated during the evaluation of the lambda?
6
1. 2.
Procedure application
The expressions for the procedure and arguments are evaluated. A new local environment is created:
Each variable from the procedure’s formal parameter list is bound to the corresponding value from the actual argument list.
The new local environment’s “pointer to an enclosing local environment” is set to be a copy of the local environment pointer that is the third part of the closure.
– –
The body of the procedure is evaluated in this new local environment. If a variable is not found in local environment, look in the global environment.
3.
Simple Example:
> (define add2 (lambda (car)
(+ car 2))) > (add2 17)
I will draw pictures on the board and verbally describe what is going on. Much of that verbal explanation appears on the next two slides. You should read them later.
Simple Example
(define add2 (lambda (car) (+ car 2)))
•
The evaluation of the lambda-expression produces a closure like this:
• Because the lambda-expression has no lexically- enclosing bindings, the environment pointer in this closure is null.
• The define adds an entry for add2 to the global environment, whose value is this procedure.
• Draw picture on the board …
7
Simple Example (continued) (add2 17) What happens when the procedure is applied?
1. First, the value of add2 is looked up in the (global) environment. The value of 17 is itself.
2. Now we create a new local environment, binding the local variable car to the value 17.
The enclosing environment pointer for this local environment is a copy of the closure’s null environment pointer.
3.
Now we evaluate the body.
– There is no + in the local environment, and there is no enclosing environment, so we find + in the global environment.
– the value of car ( which is 17) is found in the local environment.
– 17 is added to 2 (primitive procedures such as + are applied without making any new environments).
• A – –
• A – – –
Diagram notation (use it!)
local environment has two parts:
a table of bindings of variables to values
A pointer to the enclosing local environment
closure has three parts
List of parameter names Code (the procedure’s body)
A pointer to the environment that was current when the closure was created.
Begin Day 17 (Fall, 2019)
8
Summary/Review questions
1. What happens when a lambda-expression is executed?
2. When is a new local environment created?
3. What is the initial value of the current local environment?
4. When we evaluate a let expression, to what does the “env pointer” in the new local environment point?
5. When we evaluate a lambda expression, to what does the “env pointer” in the resulting closure point?
6. When we apply a closure, where does the new local environment get its “enclosing env” pointer?
1. 2. 3. 4.
5. 6.
Summary/Review questions
What happens when a lambda expression is executed?
– A closure is created and returned
When is a new local environment created?
– When Scheme (a) executes a let (or letrec) or (b) applies a closure
What is the initial value of the current local environment?
– Empty environment
When we evaluate a let, to what does the
“env pointer” in the new local environment point?
– The current local environment
When we evaluate a lambda expression, to what does the “env pointer” in the resulting closure point?
– The current local environment.
When we apply a closure, where does the new local environment get its “enclosing env” pointer?
– A copy of the closure’s environment pointer
9
Recap: Procedures (closures)
• Wheneveralambdaexpressionisevaluated,a
procedure (also known as a closure) is created
• Aclosureconsistsofthreeparts.
• Note that a lambda expression is not a procedure. What is it?
• Is the body of a lambda expression ever evaluated during the evaluation of the lambda?
1. 2.
Recap: Procedure application
The expressions for the procedure and arguments are evaluated. A new local environment is created:
Each variable from the procedure’s formal parameter list is bound to the corresponding value from the actual argument list.
The new environment’s “pointer to an enclosing environment” is set to be a copy of the local environment pointer that is the third part of the closure.
– –
The body of the procedure is evaluated, using this new local environment. If a variable is not found in local environment, look in the global environment.
3.
Simple Example:
> (define add2 (lambda (car)
(+ car 2))) > (add2 17)
I will draw pictures on the board and verbally describe what is going on. Much of that verbal explanation appears on the next two slides. You should read them later.
10
A More Complex Example
((lambda (x)
((lambda (y)
(+ x y)) 15))
20)
First, the outer lambda-expression is evaluated to produce this closure:
What happens next? (Draw it on the board)
Another Environments and
Closures Example
The following three Scheme expressions are evaluated (in the order shown here):
>(define fact
(lambda (n)
(fact2 n 1))
>(define fact2
(lambda (n acc)
(if (zero? n)
acc
(fact2 (- n 1) (* n acc)))))
>(fact 2)
Draw a diagram showing all closures and local environments that are created during this execution
(with arrows indicating when one of these objects contains a reference to another one). Use words to describe the process.
11
Evaluate letrec expressions
a. Create a new local environment, similar to a let environment, except that:
i. The “enclosing environment” pointers of all closures that are bound to the letrec variables point to the new environment, not the enclosing environment.
b. Evaluate the body of the letrec in this new environment.
Yet Another E&C Example
>(define odd?
(letrec ([odd? (lambda (n)
(if (zero? n)
#f
(even? (- n 1))))]
[even? (lambda (m)
(lambda (x)
(odd? x))))
>(odd? 2)
(if (zero? m)
#t
(odd? (- m 1))))])
12
Interlude
• Quote from Richard Feynman(1918-1988), Caltech physicist and Nobel Prize winner:
– There are 1011 stars in the galaxy. That used to be a huge number. But it’s only a hundred billion. It’s less than the national deficit! We used to call them astronomical numbers. Now we should call them economical numbers.
• What does a trillion dollars look like?
– http://articles.mercola.com/sites/articles/archive /2009/04/07/What-Does-a-Trillion-Dollars- Look-Like.aspx
Final E&C Example
The following two Scheme expressions are evaluated (in the order shown here):
>(define f
(lambda (x)
(let ([a (lambda (y z)
(+ x y z))])
(lambda (b)
(a (+ 5 b) x))))
>((f 3) 4)
13