cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
1 of 41
2/16/21, 8:50 AM
Environments Past three weeks
Nypd
How to use essential language constructs? Python
Data Types
Recursion Higher-Order eFunctions
Next two weeks
Interpreter
map filter fold
Passin op as param
How to implement language constructs?
Local variables and scope Environments and Closures (skip) Type Inference
PARSING TEXT PROG
How do we represent and evaluate a program? w
datatype recfuncover date
One
5
cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
Roadmap: The Nano Language
Features of Nano:
1. Arithmetic 2. Variables
3. Let-bindings 4. Functions
5. Recursion
00
static
Compile Time
TypeChecking
1. Nano: Arithmetic
A ¡°grammar¡± of arithmetic expressions:
leetwhere
meaning
Compile
2 of 41 ContextFreeGrammar 2/16/21, 8:50 AM
G
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
3 of 41 2/16/21, 8:50 AM
have heard of B huh
e::=n |e1+e2
|e1-e2 |e1*e2
A
Expressions
Values
4
==>
4
4+12
==>
16
(4+12) – 5
==>
11
Representing Arithmetic Expressions and Values
Lets represent arithmetic expressions as type
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
data Expr
= ENum Int
| EAdd Expr Expr | ESub Expr Expr | EMul Expr Expr
— ^ n
— ^ e1 + e2
— ^ e1 – e2
— ^ e1 * e2
Lets represent arithmetic values as a type type Value = Int
value Vint Int Evaluating Arithmetic Expressions
data
We can now write a Haskell function to evaluate an expression:
eval :: Expr -> Value
eval (ENum n) =n
eval (EAdd e1 e2) = eval e1 + eval e2 eval (ESub e1 e2) = eval e1 – eval e2 eval (EMul e1 e2) = eval e1 * eval e2
4 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
Alternative representation
Lets pull the operators into a separate type
data Binop = Add | Sub | Mul
I
data Expr = ENum Int
| EBin Binop Expr Expr — ^ e1 `op` e2
— ^ `+`
— ^ `-`
— ^ `*`
— ^ n
QUIZ
Evaluator for alternative representation
5 of 41 2/16/21, 8:50 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
6 of 41
2/16/21, 8:50 AM
eval :: Expr -> Value
eval (ENum n) = n
eval (EBin op e1 e2) = evalOp op (eval e1) (eval e2)
To
{- 1 -} evalOp :: BinOp -> Value
{- 2 -} evalOp :: BinOp -> Value -> Value -> Value {- 3 -} evalOp :: BinOp -> Expr -> Expr -> Value {- 4 -} evalOp :: BinOp -> Expr -> Expr -> Expr {- 5 -} evalOp :: BinOp -> Expr -> Value
Of
out
What is a suitable type for evalOp ?
8D
The Nano Language
Features of Nano:
1. Arithmetic [done]
Var X Vary
2. Variables O
3. Let-bindings 4. Functions
5. Recursion
x
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
2. Nano: Variables
Let¡¯s add variables and let bindings!
104 5
Lb
e ::= n |e1+e2
|e1-e2 |e1*e2
| x
Lets extend our datatype
— OLD
— NEW
— variables
old
co
a
c
7 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
type Id = String
data Expr
= ENum Int
| EBin Binop Expr Expr
| EVar Id
QUIZ
— OLD
— NEW
— variables
What should the following expression evaluate to?
x+1 EAdd CEVar x (A) 0
(B) 1
(C) Error
Ent 1
Eval
Haskell
b
Nano
Environment
8 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
An expression is evaluated in an environment
A phone book which maps variables to values
[“x”:=0,”y”:=12,…]
A type for environments
type Env = [(Id, Value)]
Evaluation in an Environment
We write
(eval env expr) ==> value
to mean
When expr is evaluated in environment env the result is value
That is, when we have variables, we modify our eval uator to take an input environment env in which expr must be evaluated.
eval :: Env -> Expr -> Value
eval env expr = … value-of-expr-in-env…
First, lets update the evaluator for the arithmetic cases ENum and EBin
9 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 (ENum n) = ???
eval env (EBin op e1 e2) = ???
QUIZ
What is a suitable ?value such that
eval [ “x” := 0, “y” := 12, …] (x + 1)
(A) 0 (B) 1 (C) Error
==> ?value
QUIZ
10 of 41 2/16/21, 8:50 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
What is a suitable env such that eval env (x + 1) ==> 10
X (A) [] x (B) [x I(C) [x (D) [x (E) [y
Vundef
:= 0, y := 9]
:= 9, y := 0]
I
:= 9, y := 10, z := 666]
:= 10, z := 666, x := 9]
Evaluating Variables
Using the above intuition, lets update our evaluator to handle variables i.e. the EVar case:
eval env (EVar x) = ???
Lets confirm that our eval is ok!
11 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
envA = []
envB=[“x”:=0,”y”:=9] envC=[“x”:=9,”y”:=0] envD=[“x”:=9,”y”:=10,”z”:=666] envE=[“y”:=10,”z”:=666,”x”:=9 ]
— >>> eval envA (EBin Add (EVar “x”) (ENum 1))
— >>> eval envB (EBin Add (EVar “x”) (ENum 1))
— >>> eval envC (EBin Add (EVar “x”) (ENum 1))
— >>> eval envD (EBin Add (EVar “x”) (ENum 1))
— >>> eval envE (EBin Add (EVar “x”) (ENum 1))
The Nano Language
Features of Nano:
1. Arithmetic expressions [done] 2. Variables [done]
3. Let-bindings
4. Functions
5. Recursion
12 of 41 2/16/21, 8:50 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
2. Nano: Variables
Let¡¯s add variables and let bindings!
e ::= n |e1+e2
|e1-e2 |e1*e2 |x
|letx=e1ine2 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
QUIZ
What should the following expression evaluate to?
letx=0 in
x+1
j(A) Error (B) 1 (C) 0
Elasto
QUIZ
Vundef Whitt Vliet 0
What should the following expression evaluate to?
letx=0 in
lety=100 in
letu ee
ez
2/16/21, 8:50 AM
(A) Error 14 of 41
x+y in
ELet x
EAdd CEVar x
EInt H
y E3
cse130 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?
letx=0 in
letx=100 in
x+1
(A) Error (B) 0 (C) 1 (D) 100
15 of 41 2/16/21, 8:50 AM