cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
2. Nano: Variables e Let¡¯s add variables and let bindings!
e ::= n
| e1 + e2
| e1 – e2 | e1 * e2 |x
| let x = e1 in e2 IT
Lets extend our datatype
type Id = String
data Expr
= ENum Int
| EBin Binop Expr Expr | EVar Id
— OLD
— NEW
in
let
E
z
z
— OLD
— NEW
I | ELet Id Expr Expr How should we extend eval ?
13 of 41 2/16/21, 8:50 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
j
Vundef Whitt Whit 0
QUIZ
What should the following expression evaluate to?
let x = 0 in
x+1
(A) Error (B) 1
Elasto
(C) 0
QUIZ
What should the following expression evaluate to?
let x = 0 in
let y = 100 in
x + y
(A)Error 14 of 41
let
n
e
ez
2/16/21, 8:50 AM
5
2 Ceta o in
y
in
b zig ez
Elet x
EAdd CEVar x
EInt ID
cse130
Xty https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
(B) 0 (C) 1 (D) 100 (E) 101
QUIZ
What should the following expression evaluate to?
let x = 0 in
let x = 100
in
T
x+1
should
recent
n
most
get
(A) Error (B) 0 (C) 1 (D) 100
def
15 of 41
2/16/21, 8:50 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
(E) 101
QUIZ
What should the following expression evaluate to? let
a 0 in
let x = 0
y
+ x
in
(let x = 100 in in
x+1 )
100 in Ytl
se
101
let y
(A) Error (B) 1 (C) 101 (D) 102 (E) 2
16 of 41
2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
Principle: Static/Lexical Scoping
Every variable use gets its value from a unique definition: ¡°Nearest¡± let -binder in program text
¡°Static¡± means you can tell without running the program Great for readability and debugging
1. Define local variables
2. Be sure where each variable got its value
Don¡¯t have to scratch head to figure where a variable got ¡°assigned¡± How to impOlement static scoping?
QUIZ
17 of 41 2/16/21, 8:50 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
Lets re-evaluate the quizzes!
expr
e
x+1 (A)ienv k
env e
55 le letx
e
let x = 0 in
T
in
ee
guts
— env
— ??? what env to use for `x + 1`?
in Esty (D) (“x” := 0) : env returns
(B) [ ]
X(C) [ (“x” := 0) ]
forgetsother vars
X(E) env ++ [“x” := 0]lookup valueofX
n55
QUIZ
let x = 0 in
let y = 100 in
x+y
X(A) (“x” := 0) : env
a
X (B) (“y” := 100) : env 18 of 41
no no
y
x
wrong
notrecent
— env
— (x := 0) : env
eval
let x o end
Cano
— ??? what env to use for `x + y` ?
2/16/21, 8:50 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
(C) (“y” := 100) : (“x” := 0) : env (D) (“x” := 0) : (“y” := 100) : env
X(E) [(“y” := 100), (“x” := 0)]
QUIZ
Lets re-evaluate the quizzes!
oopsforgot
env
let x = 0 in
let x = 100 in
x+1
— env
— (“x” := 0) : env
(A) (“x” := 0) : env
(B) (“x” := 100) : env
(C) (“x” := 100) : (“x” := 0) : env (D) (“x” := 0) : (“x” := 100) : env (E) [(“x” := 100)]
— ??? what env to use for `x + 1`?
19 of 41
2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
Extending Environments
Letsfillin eval forthe let x = e1 in e2 case! eval env (ELet x e1 e2) = ???
e
1. Evaluate e1 in env to get a value v1
2. Extend environment with value for x i.e. to (x := v1) : env 3. Evaluate e2 using extended environment.
Lets make sure our tests pass!
Run-time Errors
Haskell function to evaluate an expression:
20 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
eval :: Env -> Expr -> Value
eval env (Num n) =n
eval env (Var x) = lookup x env eval env (Bin op e1 e2) = evalOp op v1 v2
where
v1 = eval env e1
v2 = eval env e2
eval env (Let x e1 e2) = eval env1 e2
where
v1 = eval env e1
env1 = (x, v1) : env
QUIZ
— (A) — (B)
— (C) — (C)
— (D)
Will eval env expr always return a value ? Or, can it crash?
(A) operation at A may fail (B) operation at B may fail (C) operation at C may fail
(D) operation at D may fail (E) nah, its all good…, always returns a Value
Free vs bound variables
21 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
Undefined Variables
How do we make sure lookup doesn¡¯t cause a run-time error? Bound Variables
Consider an expression let x = e1 in e2
An occurrence of x is bound in e2
tog
a
i.e. when occurrence of form let x = … in … x …
i.e. when x occurs ¡°under¡± a let binding for x . O
Free Variables
Anoccurrenceof x isfreein e ifitisnotboundin e Closed Expressions
An expression e is closed in environment env :
If all free variables of e are defined in env Successful Evaluation
lookup will never fail
Oo
O
co O
If eval env e is only called on e that is closed in env
22 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
QUIZ
Which variables occur free in the expression?
let y = (let x = 2 in x
O
IT
) + x
in
let x = 3
oral
better
in env containing
in
00
x+y
(A) None (B) x
(C) y
(D) x and y
x
Exercise
23 of 41 2/16/21, 8:50 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
Consider the function
no Vundet | otherwise = error “Sorry! bad expression, it will crash `eval
evaluate :: Expr -> Value evaluate e pp
guarantee
| isOk e = eval emptyEnv e
`!”
where
O
it mayreturn Vundef — has NO bindings
emptyEnv = []
What should isOk check for? (Try to implement it for nano …)
0
The Nano Language
Features of Nano:
E1. Arithmetic expressions [done] 2. Variables [done]
3. Let-bindings [done]
4. Functions
5. Recursion
EX PR
lxe Value
24 of 41
2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
Nano: Functions
Let¡¯s add
lambda abstraction (aka function definitions) application (aka function calls)
e ::= n
| e1 `op` e2
|x
| let x = e1 in e2
body
Functarg
Example
I
Representation
— OLD
— NEW
— abstraction
— application
formal
| \x -> e | e1 e2
let incr = \x -> x + 1 in
incr 10
25 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
data Expr
= ENum Int
| EBin Binop Expr Expr | EVar Id
| ELet Id Expr Expr
| ??? | ???
Representation
data Expr
= ENum Int
| EBin Binop Expr Expr | EVar Id
| ELet Id Expr Expr
| ELam Id Expr
| EApp Expr Expr
Example
let incr = \x -> x + 1 in
incr 10
— OLD
— NEW
— abstraction \x -> e
— application (e1 e2)
is represented as
— OLD
— NEW
— abstraction \x -> e
— application (e1 e2)
26 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
ELet “incr” (ELam “x” (EBin Add (EVar “x”) (ENum 1)))
(
EApp (EVar “incr”) (ENum 10)
)
Functions are Values
Recall the trinity
letf in f
to
But… what is the value of a function? Lets build some intuition with examples.
lx
xH
QUIZ
27 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
What does the following expression evaluate to?
let incr =I\x -> x + 1 in
incr 10
(A) Error/Undefined (B) 10
(C) 11
(D) 0
(E) 1
— abstraction (“definition”)
n veenv
— application (“call”)
I
What is the Value of incr?
Isitan Int ?
Isita Bool ?
Is it a ???
E
What information do we need to store (in the Env ) about incr ?
28 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
A Function¡¯s Value is its Code
— env Pyaram body let incr = \x -> x + 1
in — (“incr” := ) : env
incr 10 -- evaluate with parameter := 10
What information do we store about ?
A Call¡¯s Value
How to evaluate the ¡°call¡± incr 10 ?
1. Lookup the i.e.
29 of 41 2/16/21, 8:50 AM