[SOLVED] CS Haskell cse130

cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
25 of 41
2/16/21, 8:50 AM
Nano: Functions
Lets add
lambda abstraction (aka function definitions) application (aka function calls)
se
e ::= n |e1`op`e2
|x |letx=e1ine2
formal body | x -> e
| e1 e2
funerary
Example
letincr=x->x+1 in
incr 10
Representation
OLD
formal
FunDef
Ix
a
body
Fun Call
1 Ez
In a
func arg
Elam X LEBinLeVar x
NEW
abstraction
application
ELet incr
EApp Eva
incr Elut 10
9

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
letincr=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
27 of 41
2/16/21, 8:50 AM
ELet incr (ELam x (EBin Add (EVar x) (ENum 1)))
(
EApp (EVar incr) (ENum 10)
)
Functions are Values
Recall the trinity
let.fi
in f
to
But what is the value of a function? Lets build some intuition with examples.
g
QUIZ
xti
gI
Env
in
let
inc
ENI

cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
What does the following expression evaluate to?
env
(A) Error/Undefined (B) 10
(C) 11
(D) 0
(E) 1
let incr = x -> x + 1
abstraction (definition)
in
t
nor
env
incr 10
application (call)
What is the Value of incr?
Is it an Int ? Is it a Bool ? Is it a ???
What information do we need to store (in the Env ) about incr ? D
if
toutput
X t I
28 of 41 VA Var Expr 2/16/21, 8:50 AM

cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
29 of 41
2/16/21, 8:50 AM
A Functions Value is its Code
eval
eval
x
A Calls Value
Fram
env
pyar.anf.tb.am
letincr=x->x+1
in (incr := ) : env
incr 10 -- evaluate with parameter := 10 What information do we store about ?
Ei
Tody
body
iienvbodyJ
How to evaluate the call incr 10 ?
1. Lookup the i.e. for incr (stored in the environment),
7

cse130 l https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
2. Evaluate body with param set to 10 !
Two kinds of Values
We now have two kinds of Values
v ::= n — OLD
| — 1. Plain Int (as before)
2. A functions code: a pair of parameter and body-expression
data Value
= VInt Int — OLD
| VCode Id Expr —
Evaluating Lambdas and Applications
30 of 41 2/16/21, 8:50 AM

cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
eval :: Env -> Expr -> Value
— OLD
— NEW
Lets make sure our tests work properly!
exLam1 = ELet “incr” (ELam “x” (EBin Add (EVar “x”) (ENum 1)))
(
EApp (EVar “incr”) (ENum 10)
)
— >>> eval [] exLam1
— 11
QUIZ
What should the following evaluate to?
J
eval env (ENum n)= ???
eval env (EVar x)= ???
eval env (EBin op e1 e2) = ???
eval env (ELet xe1 e2) = ???
eval env (ELam x e)= ???
eval env (EApp e1 e2)= ???
letc=1 i in
iaf
letinc=x->x+c in
inc 10
(A) Error/Undefined (B) 10
31 of 41
C
i
At C
11
1
2/16/21, 8:50 AM

cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
(C) 11 (D) 0 (E) 1
exLam2 = ELet “c” (ENum 1)
(ELet “incr” (ELam “x” (EBin Add (EVar “x”) (EVar “
c”)))
(
EApp (EVar “incr”) (ENum 10)
) )
— >>> eval [] exLam2
— ???
QUIZ
And what should this expression evaluate to?
32 of 41 2/16/21, 8:50 AM
WE

cse130 Quit
letc=1 in
letinc=x->x+c
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
33 of 41
2/16/21, 8:50 AM
in
i0nc 10 (A) Error/Undefined
(B) 110 a
(C) 11
localscope eustatic
formal hay letc=100
in
oral produce
33
The Immutability Principle
A functions behavior should never change
A function must always return the same output for a given input
Why?
How to charge to

cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
> myFunc 10 0
> myFunc 10 10
Oh no! How to find the bug? Is it
In myFunc or
In a global variable or
In a library somewhere else or …
My worst debugging nightmare
Colbert Immutability Principle (https://youtu.be/CWqzLgDc030?t=628)
The Immutability Principle ?
How does our eval work?
exLam3 = ELet “c” (ENum 1)
(
ELet “incr” (ELam “x” (EBin Add (EVar “x”) (EVar “c”)))
(
ELet “c” (ENum 100)
(
EApp (EVar “incr”) (ENum 10)
) )
)
— >>> eval [] exLam3
— ???
34 of 41 2/16/21, 8:50 AM

cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
Oops?
letc=1 in
letinc=x->x+c in
letc=100
in
= 1] <<< envinc 10And so we geteval env (inc 10)– []– [“c” := 1]– [“inc” := , c := 1]
— [“c” := 100, “inc” := eval (“x” := 10 : env) (x + c)
==>10+100
==> 110
Ouch.
Enforcing Immutability with Closures
How to enforce immutability principle inc 10 always returns 11 ?
Key Idea: Closures
35 of 41 2/16/21, 8:50 AM

cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
At definition: Freeze the environment the functions value At call: Use the frozen environment to evaluate the body Ensures that inc 10 always evaluates to the same result!
letc=1 in
letinc=x->x+c
in
<<< frozenv = [“c” := 1]letc=100inc>, “c” := 1]
inc 10
Now we evaluate
eval env (inc 10)
— []
— [“c” := 1]
— [“inc” := , c := 1]
— [“c” := 100, “inc” := eval (“x” := 10 : frozenv) (x + c) where frozenv = [“c” := 1]
==>10+1 ==> 1
tada!
Representing Closures
Lets change the Value datatype to also store an Env
36 of 41 2/16/21, 8:50 AM

cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
data Value
= VInt Int — OLD
| VClos Env Id Expr —
Evaluating Function Definitions
How should we fix the definition of eval for ELam ? eval :: Env -> Expr -> Value
eval env (ELam x e) = ???
Hint: What value should we bind incr to in our example above?
(Recall At definition freeze the environment the functions value)
Evaluating Function Calls
How should we fix the definition of eval for EApp ? eval :: Env -> Expr -> Value
eval env (EApp e1 e2) = ???
(Recall At call: Use the frozen environment to evaluate the body)
Hint: What value should we evaluate incr 10 to?
37 of 41 2/16/21, 8:50 AM

cse130
Pei funEnv https://ucsd-cse130.github.io/wi21/lectures/05-environments.html funparam
KfenBody
38 of 41
2/16/21, 8:50 AM
aL
1. Evaluate incr to get
2. Evaluate 10 to get 10
O
Cte x + c in x:=10 : frozenv IT
3. Evalua
Lets generalize that recipe!
1. Evaluate e1 to get 2. Evaluate e2 to get v2
3. Evaluate body in param := v2 : frozenv
Immutability Achieved
Lets put our code to the test!
exLam3 = ELet “c” (ENum 1)
(
ELet “incr” (ELam “x” (EBin Add (EVar “x”) (EVar “c”)))
(
ELet “c” (ENum 100)
(
EApp (EVar “incr”) (ENum 10)
) )
)
— >>> eval [] exLam3
— ???
QUIZ
What should the following evaluate to?
Jez argvaluetextenvefenparan
argual

cse130
https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
39 of 41
2/16/21, 8:50 AM
letadd=x->(y->x+y) in
let add10 = add 10 in
let add20 = add 20
30
Functions Returning Functions Achieved!
exLam4 = …
— >>> eval [] exLam4
TODO
Practice
What should the following evaluate to?
letadd=x->(y->x+y) in
let add10 = add 10 in
let doTwice = f -> (x -> f (f x)) in
doTwice add10 100
TODO
11
Add 10 100
in
di85io
C
azzo9
(add10 100) + (add20 1000)
Functions Accepting Functions Achieved!
eval CT 120
extwice

cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
exLam5 = …
— >>> eval [] exLam4
The Nano Language
Features of Nano:
1. Arithmetic expressions [done]
A defface Ins
. Variables [done] 2I
FainD
3
. Let-bindings [done] 4. Functions [done]
5. Recursion
… You figure it out Hw4 … 🙂
(https://ucsd-cse130.github.io/wi21/feed.xml) (https://twitter.com/ranjitjhala)
40 of 41 2/16/21, 8:50 AM

cse130 https://ucsd-cse130.github.io/wi21/lectures/05-environments.html
(https://plus.google.com/u/0/104385825850161331469) (https://github.com/ranjitjhala)
Generated by Hakyll (http://jaspervdj.be/hakyll), template by Armin Ronacher (http://lucumr.pocoo.org), suggest improvements here (https://github.com /ucsd-progsys/liquidhaskell-blog/).
41 of 41 2/16/21, 8:50 AM