Past three weeks
How to use essential language constructs?
- Data Types
- Recursion
- Higher-Order Functions
Next two weeks
How to implement language constructs?
- Local variables and scope
- Environments and Closures
Interpreter
How do we represent and evaluate a program?
How should we evaluate this expression?
eval []
{let c = 42 in let cTimes = \x -> c * x in cTimes 2}
=> eval [c:42]
{let cTimes = \x -> c * x in cTimes 2}
=> eval [cTimes:???, c:42]
{cTimes 2}What is the value of cTimes???
Rethinking our values
Until now: a program evaluates to an integer (or fails)
What do these programs evaluate to?
Now: a program evaluates to an integer or a lambda abstraction (or fails)
- Remember: functions are first-class values
Let’s change our definition of values!
data Value = VNum Int
| VLam ??? -- What info do we need to store?
-- Other types stay the same
type Env = [(Id, Value)]
eval :: Env -> Expr -> Value
Function values
How should we represent a function value?
We need to store enough information about cTimes so that we can later evaluate any application of cTimes (like cTimes 2)!
First attempt:
Let’s try this!
eval []
{let c = 42 in let cTimes = \x -> c * x in cTimes 2}
=> eval [c:42]
{let cTimes = \x -> c * x in cTimes 2}
=> eval [cTimes:(\x -> c*x), c:42]
{cTimes 2}
-- evaluate the function:
=> eval [cTimes:(\x -> c*x), c:42]
{(\x -> c * x) 2}
-- evaluate the argument, bind to x, evaluate body:
=> eval [x:2, cTimes:(\x -> c*x), c:42]
{c * x}
=> 42 * 2
=> 84Looks good… can you spot a problem?
QUIZ
What should this evaluate to?
(A) 84
(B) 10
(C) Error: multiple definitions of c
Static vs Dynamic Scoping
What we want:
Lexical (or static) scoping:
- each occurrence of a variable refers to the most recent binding in the program text
- definition of each variable is unique and known statically
- good for readability and debugging: don’t have to figure out where a variable got “assigned”
What we don’t want:
Dynamic scoping:
- each occurrence of a variable refers to the most recent binding during program execution
- can’t tell where a variable is defined just by looking at the function body
- nightmare for readability and debugging:
let cTimes = \x -> c * x in
let c = 5 in
let res1 = cTimes 2 in -- ==> 10
let c = 10 in
let res2 = cTimes 2 in -- ==> 20!!!
res2 - res1
Function values
This representation can only implement dynamic scoping!
evaluates as:
eval []
{let c = 42 in let cTimes = \x -> c * x in let c = 5 in cTimes 2}
=> eval [c:42]
{let cTimes = \x -> c * x in let c = 5 in cTimes 2}
=> eval [cTimes:(\x -> c*x), c:42]
{let c = 5 in cTimes 2}
=> eval [c:5, cTimes:(\x -> c*x), c:42]
{cTimes 2}
=> eval [c:5, cTimes:(\x -> c*x), c:42]
{(\x -> c * x) 2}
=> eval [x:2, c:5, cTimes:(\x -> c*x), c:42]
{c * x}
-- latest binding for c is 5!
=> 5 * 2
=> 10Lesson learned: need to remember what c was bound to when cTimes was defined!
- i.e. “freeze” the environment at function definition
Closures
To implement lexical scoping, we will represent function values as closures
Closure = lambda abstraction (formal + body) + environment at function definition
Our example:
eval []
{let c = 42 in let cTimes = \x -> c * x in let c = 5 in cTimes 2}
=> eval [c:42]
{let cTimes = \x -> c * x in let c = 5 in cTimes 2}
-- remember current env:
=> eval [cTimes:<[c:42], \x -> c*x>, c:42]
{let c = 5 in cTimes 2}
=> eval [c:5, cTimes:<[c:42], \x -> c*x>, c:42]
{cTimes 2}
=> eval [c:5, cTimes:<[c:42], \x -> c*x>, c:42]
{<[c:42], \x -> c * x> 2}
-- restore env to the one inside the closure, then bind 2 to x:
=> eval [x:2, c:42]
{c * x}
=> 42 * 2
=> 84
QUIZ
Which variables should be saved in the closure environment of f?
(A) a
(B) a x
(C) y g
(D) a y g
(E) a x y g z
Free vs bound variables
- An occurrence of
xis free if it is not bound - An occurrence of
xis bound if it’s insidee2wherelet x = e1 in e2ewhere\x -> e
- A closure environment has to save all free variables of a function definition!
let a = 20 in
let f =
\x -> let y = x + 1 in
let g = \z -> y + z in
a + g x -- a is the only free variable!
in ...
Evaluator
Let’s modify our evaluator to handle functions!
data Value = VNum Int
| VClos Env Id Expr -- env + formal + body
eval :: Env -> Expr -> Value
eval env (Num n) = VNum n -- must wrap in VNum now!
eval env (Var x) = lookup x env
eval env (Bin op e1 e2) = VNum (f v1 v2)
where
(VNum v1) = eval env e1
(VNum v2) = eval env e2
f = ... -- as before
eval env (Let x e1 e2) = eval env' e2
where
v = eval env e1
env' = add x v env
eval env (Lam x body) = ??? -- construct a closure
eval env (App fun arg) = ??? -- eval fun, then arg, then apply
Evaluating functions:
- Construct a closure: save environment at function definition
- Apply a closure: restore saved environment, add formal, evaluate the body
eval :: Env -> Expr -> Value
...
eval env (Lam x body) = VClos env x body
eval env (App fun arg) = eval bodyEnv body
where
(VClos closEnv x body) = eval env fun -- eval function to closure
vArg = eval env arg -- eval argument
bodyEnv = add x vArg closEnvQUIZ
With eval as defined above, what does this evaluate to?
(A) 15
(B) 5
(C) Error: unbound variable x
(D) Error: unbound variable y
(E) Error: unbound variable f
eval []
{let f = \x -> x + y in let y = 10 in f 5}
=> eval [f:<[], \x -> x + y>]
{let y = 10 in f 5}
=> eval [y:10, f:<[], \x -> x + y>]
{f 5}
=> eval [y:10, f:<[], \x -> x + y>]
{<[], \x -> x + y> 5}
=> eval [x:5] -- env got replaced by closure env + formal!
{x + y} -- y is unbound!
QUIZ
With eval as defined above, what does this evaluate to?
(A) 120
(B) Evaluation does not terminate
(C) Error: unbound variable f
eval []
{let f = \n -> n * f (n - 1) in f 5}
=> eval [f:<[], \n -> n * f (n - 1)>]
{f 5}
=> eval [f:<[], \n -> n * f (n - 1)>]
{<[], \n -> n * f (n - 1)> 5}
=> eval [n:5] -- env got replaced by closure env + formal!
{n * f (n - 1)} -- f is unbound!Lesson learned: to support recursion, we need a different way of constructing the closure environment!
The Nano Language
Features of Nano:
- Arithmetic expressions [done]
- Variables and let-bindings [done]
- Functions [done]
- Recursion [this is part of HW4]