cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
2. Nano: Variables e Lets 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
Dont 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 enve1
v2= eval enve2
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 doesnt 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
Lets 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 =Ix -> 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 Functions 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 Calls Value
How to evaluate the call incr 10 ?
1. Lookup the i.e.
29 of 41 2/16/21, 8:50 AM
Reviews
There are no reviews yet.