cse130
QUIZ ajb i a
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
((\x -> (x (\x -> x))) apple)
ix s.ec =b> ???
er
e Ex ez
A. (apple (\x -> x)) t
fix funcGE
B. (apple (\apple -> apple)) C. (apple (\x -> apple))
D. apple
E. (\x -> x)
x Ix
def
123
33 6
EXERCISE
What is a ¦Ë-term fill_this_in such that
ez
fill_this_in apple
=b> banana
apple
24 of 69 D banana
1/7/21, 8:59 AM
xE1 3
return
x
binder useloccurrences
cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
25 of 69
Targ HE’D apply
body D appleapple 1/7/21, 8:59 AM
ELSA: https://goto.ucsd.edu/elsa/index.html
Click here to try this exercise (https://goto.ucsd.edu /elsa/index.html#?demo=permalink%2F1585434473_24432.lc)
Ix s apple banana
A Tricky One
banga
((\x -> (\y -> x)) y) I =b>\y->y
Make sure yourIPATH is set Gsblw
rm rf n 1stack
Is this right?
z Xy t formal
eez arg function
REDEX
SYNTAX
e
Xx e Imai
a
apple
b
banana x
i
l x ET body
to make
downloading GHC
cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
26 of 69
1/7/21, 8:59 AM
=b> (\y -> y)
to
I
dy pp e a ed
Something is Fishy
cy
5 formal bodes igars
(\x -> (\y -> x)) y
body
Is this right?
Problem: The free y in the argument has been captured by \y in body!
Solution: Ensure that formals in the body are di!erent from free-variables of argument!
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Capture-Avoiding Substitution
We have to fix our definition of ¦Â-reduction: (\x -> e1) e2 =b> e1[x := e2]
where e1[x := e2] means ¡° e1 with all free occurrences of x replaced with e2 ¡± e1 with all free occurrences of x replaced with e2
as long as no free variables of e2 get captured SIT
Formally:
x[x:=e] =e
y[x := e]
(e1 e2)[x := e]
(\x -> e1)[x := e]
anged?
= y — as x /= y
= (e1[x := e]) (e2[x := e])
= (\x -> e1) — Q: Why leave `e1` unch
(\y -> e1)[x := e] |not(yinFV(e))=\y->e1[x:=e]
Oops, but what to do if y is in the free-variables of e ? i.e. if \y -> … may capture those free variables?
27 of 69 1/7/21, 8:59 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Rewrite Rules of Lambda Calculus
1. ¦Â-step (aka function call)
2. ¦Á-step (aka renaming formals)
functional
Nti
henchonly
function E return Etl’s
5
return
5
return
ytl
Semantics: ¦Á-Renaming
28 of 69 7x y Ya XyA y a
1/7/21, 8:59 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
f
\x->e =a> \y->e[x:=y] where not (y in FV(e))
x Tyy Atz We rename a formal parameter x to y
By replace all occurrences of x in the body with y We say that \x -> e ¦Á-steps to \y -> e[x := y]
Example:
(\x->x) =a> (\y->y) =a> (\z->z)
All these expressions are ¦Á-equivalent
Xx
What¡¯s wrong with these?
— (A)
(\f -> (f x)) =a>
— (B)
((\x -> (\fy -> y)) y) 29 of 69
(\x -> (x x))
outsidescopeofbinder
=a> ((\x -> (\z -> z)) z)
1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Tricky Example Revisited
((\x -> (\y -> x)) y)
ure
— rename ‘y’ to ‘z’ to avoid capt
— now do b-step without capture!
=a> ((\x -> (\z -> x)) y)
=b> (\z -> y)
To avoid getting confused,
you can always rename formals,
so di”erent variables have di”erent names!
30 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Normal Forms
Recall redex is a ¦Ë-term of the form ((\x -> e1) e2)
A ¦Ë-term is in normal form if it contains no redexes.
Xx
QUIZ
Which of the following term are not in normal form ?
y
A. x
no redex
ie containfurther b steps
b redexes
31 of 69 1/7/21, 8:59 AM
cse130
Y’t https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
32 of 69
1/7/21, 8:59 AM
B. (x y) noredexjb
XX ee If
Canning
Chetty
C. ((\x -> x) y) se e e
D. (x (\y -> y)) E. C and D
yesredex no redex
ez
Semantics: Evaluation
A ¦Ë-term e evaluates to e’ if
1. There is a sequence of steps
223 11
3
normal
e=?>e_1=?>…=?>e_N=?>e’
where each =?> is either =a> or =b> and N >= 0
2. e’ is in normal form
4
1
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Examples of Evaluation
((\xE-> x) apple) =b> apple
(\f -> f (\x -> x)) (\x -> x)
=?> ???
(\x -> x x) (\x -> x)
=?> ???
Elsa shortcuts
Named ¦Ë-terms:
let ID = (\x -> x) — abbreviation for (\x -> x)
33 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
To substitute name with its definition, use a =d> step:
(ID apple)
=d> ((\x -> x) apple) — expand definition =b> apple — beta-reduce
Evaluation:
e1 =*> e2: e1 reduces to e2 in 0 or more steps where each step is =a> , =b> , or =d>
e1 =~> e2 : e1 evaluates to e2 and e2 is in normal form
X
b
EXERCISE
xxx yy
y
ay ay
yy yy
Fill in the definitions of FIRST , SECOND and THIRD such that you get the
34 of 69 1/7/21, 8:59 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
35 of 69
1/7/21, 8:59 AM
following behavior in elsa let FIRST = fill_this_in
let SECOND = fill_this_in let THIRD = fill_this_in
eval ex1 : 1 3
Ix
sx
Kr 2
n apple orange lxz lxz x
FIRST apple banana orange
=*> apple
eval ex2 :
SECOND apple banana orange
=*> banana
eval ex3 :
THIRD apple banana orange
=*> orange
x
s
apple
ban
orange
Click here to try this exercise (https://goto.ucsd.edu /elsa/index.html#?demo=permalink%2F1585434130_24421.lc)
Non-Terminating Evaluation
((\x -> (x x)) (\x -> (x x)))
=b> ((\x -> (x x)) (\x -> (x x)))
Some programs loop back to themselves … never reduce to a normal form! This combinator is called ¦¸
ELSA: https://goto.ucsd.edu/elsa/index.html
Xx
ban
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
What if we pass ¦¸ as an argument to another function? let OMEGA = ((\x -> (x x)) (\x -> (x x)))
((\x -> (\y -> y)) OMEGA)
Does this reduce to a normal form? Try it at home!
Programming in ¦Ë-calculus Real languages have lots of features
Il
Il
Booleans t E if thenelse
Records (structs, tuples) Numbers 2 5 liststrees
fest snd
se y Z
3
Functions [we got those]
Recursion
Tf
36 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Lets see how to encode all of these features with the ¦Ë-calculus.
Syntactic Sugar
instead of
we write
\x->(\y->(\z->e))
\x->\y->\z->e
\x->\y->\z->e
\x y z -> e
(((e1 e2) e3) e4)
e1 e2 e3 e4
\x y -> y — A function that that takes two arguments — and returns the second one…
(\x y -> y) apple banana — … applied to two arguments
37 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
boollcond
TRUE
res true
How can we encode Boolean values ( TRUE and FALSE ) as functions?
Well, what do we do with a Boolean b ? decisionsIcondition choice
## ¦Ë-calculus: Booleans
FALSE
res
false
38 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Make a binary choice ifbthene1elsee2
St
b et ez
Booleans: API
We need to define three functions
let TRUE = ??? let FALSE = ???
let ITE such that
lx ly x
ly y
— if b then x else y
x
ix
= \b x y -> ???
00 b
y
ITE TRUE apple banana =~> apple
ITE FALSE apple banana =~> banana
(Here, let NAME = e means NAME is an abbreviation for e )
39 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Booleans: Implementation
let TRUE = \x y -> x — Returns its first argument let FALSE = \x y -> y — Returns its second argument let ITE = \b x y -> b x y — Applies condition to branches
— (redundant, but improves readabili
ty)
Example: Branches step-by-step
eval ite_true:
ITE TRUE e1 e2
=d> (\b x y -> b x y) TRUE e1 e2
— expand def ITE
— beta-step
— beta-step
— expand def TRUE
— beta-step
— beta-step
=b>
=b>
=b>
=d>
=b>
=b> e1
(\x y -> TRUE x y)
(\y -> TRUE e1 y)
TRUE e1 e2
(\x y -> x) e1 e2
(\y -> e1) e2
e1 e2 e2
40 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Example: Branches step-by-step
Now you try it!
Can you fill in the blanks to make it happen? (http://goto.ucsd.edu:8095 /index.html#?demo=ite.lc)
eval ite_false:
ITE FALSE e1 e2
— fill the steps in!
=b> e2
41 of 69 1/7/21, 8:59 AM
cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
EXERCISE: Boolean Operators
ELSA: https://goto.ucsd.edu/elsa/index.html Click here to try this exercise (https://goto.ucsd.edu /elsa/index.html#?demo=permalink%2F1585435168_24442.lc)
Now that we have ITE it¡¯s easy to define other Boolean operators:
Clet NOT = \b -> ??? let OR = \b1 b2 -> ??? let AND = \b1 b2 -> ???
When you are done, you should get the following behavior:
42 of 69
1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
eval ex_not_t:
NOT TRUE =*> FALSE
eval ex_not_f:
NOT FALSE =*> TRUE
eval ex_or_ff:
OR FALSE FALSE =*> FALSE
eval ex_or_ft:
OR FALSE TRUE =*> TRUE
eval ex_or_ft:
OR TRUE FALSE =*> TRUE
eval ex_or_tt:
OR TRUE TRUE =*> TRUE
eval ex_and_ff:
AND FALSE FALSE =*> FALSE
eval ex_and_ft:
AND FALSE TRUE =*> FALSE
eval ex_and_ft:
AND TRUE FALSE =*> FALSE
eval ex_and_tt:
AND TRUE TRUE =*> TRUE
AND TT AND FF
FF ns FF FF ng FF
AND
AND
FF TT ng TT TT
FF
TT
43 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Programming in ¦Ë-calculus Booleans [done]
r
Records (structs, tuples) Numbers
Functions [we got those] Recursion
¦Ë-calculus: Records
44 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Let¡¯s start with records with two fields (aka pairs) What do we do with a pair?
1. Pack two items into a pair, then 2. Get first item, or
3. Get second item.
Pairs : API
We need to define three functions
let PAIR = \x y -> ??? let FST = \p -> ??? let SND = \p -> ???
— Make a pair with elements x and y
— { fst : x, snd : y }
— Return first element
— p.fst
— Return second element
— p.snd
45 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
such that
eval ex_fst:
FST (PAIR apple banana) =*> apple
eval ex_snd:
SND (PAIR apple banana) =*> banana
Pairs: Implementation
A pair of x and y is just something that lets you pick between x and y ! (i.e. a function that takes a boolean and returns either x or y )
let PAIR = \x y -> (\b -> ITE b x y)
let FST = \p -> p TRUE — call w/ TRUE, get first value let SND = \p -> p FALSE — call w/ FALSE, get second value
46 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
EXERCISE: Triples
How can we implement a record that contains three values? ELSA: https://goto.ucsd.edu/elsa/index.html
Click here to try this exercise (https://goto.ucsd.edu /elsa/index.html#?demo=permalink%2F1585434814_24436.lc)
47 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
let TRIPLE = \x y z -> ??? letFST3 =\t->??? letSND3 =\t->??? letTHD3 =\t->???
eval ex1:
FST3 (TRIPLE apple banana orange)
=*> apple
eval ex2:
SND3 (TRIPLE apple banana orange)
=*> banana
eval ex3:
THD3 (TRIPLE apple banana orange)
=*> orange
Programming in ¦Ë-calculus
48 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Booleans [done]
Records (structs, tuples) [done] Numbers
Functions [we got those] Recursion
¦Ë-calculus: Numbers
Let¡¯s start with natural numbers (0, 1, 2, …) What do we do with natural numbers?
Count: 0, inc Arithmetic: dec, +, -, * Comparisons: == , <= , etc
49 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Natural Numbers: API
We need to define:
A family of numerals: ZERO , ONE , TWO , THREE , ... Arithmetic functions: INC , DEC , ADD , SUB , MULT Comparisons: IS_ZERO, EQ
Such that they respect all regular laws of arithmetic, e.g.
IS_ZERO ZERO =~> TRUE
IS_ZERO (INC ZERO) =~> FALSE
INC ONE =~> TWO
…
50 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Natural Numbers: Implementation
Church numerals: a number N is encoded as a combinator that calls a function on an argument N times
let ONE = \f x -> f x
let TWO = \f x -> f (f x) let THREE = \f x -> f (f (f x))
let FOUR let FIVE let SIX …
= \f x -> f (f (f (f x)))
= \f x -> f (f (f (f (f x))))
= \f x -> f (f (f (f (f (f x)))))
QUIZ: Church Numerals
Which of these is a valid encoding of ZERO ?
51 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
A: let ZERO = \f x -> x B: let ZERO = \f x -> f C: let ZERO = \f x -> f x D: letZERO=\x->x
E: None of the above
Does this function look familiar?
¦Ë-calculus: Increment
— Call `f` on `x` one more time than `n` does
let INC = \n -> (\f x -> ???)
52 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Example:
eval inc_zero :
INC ZERO
=d> (\n f x -> f (n f x)) ZERO
=b> \f x -> f (ZERO f x)
=*> \f x -> f x
=d> ONE
53 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
EXERCISE
Fill in the implementation of ADD so that you get the following behavior Click here to try this exercise (https://goto.ucsd.edu
/elsa/index.html#?demo=permalink%2F1585436042_24449.lc)
let ZERO = \f x -> x
let ONE let TWO let INC
= \f x -> f x
= \f x -> f (f x)
= \n f x -> f (n f x)
let ADD = fill_this_in eval add_zero_zero:
ADD ZERO ZERO =~> ZERO
eval add_zero_one:
ADD ZERO ONE =~> ONE
eval add_zero_two:
ADD ZERO TWO =~> TWO
eval add_one_zero:
ADD ONE ZERO =~> ONE
eval add_one_zero:
ADD ONE ONE =~> TWO
eval add_two_zero:
ADD TWO ZERO =~> TWO
54 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
QUIZ
How shall we implement ADD ?
A. let ADD = \n m -> n INC m
B. let ADD = \n m -> INC n m
C. let ADD = \n m -> n m INC
D. let ADD = \n m -> n (m INC)
E. let ADD = \n m -> n (INC m)
¦Ë-calculus: Addition
— Call `f` on `x` exactly `n + m` times
let ADD = \n m -> n INC m
55 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Example:
eval add_one_zero :
ADD ONE ZERO
=~> ONE
QUIZ
How shall we implement MULT ?
A. let MULT = \n m -> n ADD m
B. let MULT = \n m -> n (ADD m) ZERO
C. let MULT = \n m -> m (ADD n) ZERO
D. let MULT = \n m -> n (ADD m ZERO)
E. let MULT = \n m -> (n ADD m) ZERO
56 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
¦Ë-calculus: Multiplication
— Call `f` on `x` exactly `n * m` times
let MULT = \n m -> n (ADD m) ZERO
Example:
eval two_times_three :
MULT TWO ONE
=~> TWO
57 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Programming in ¦Ë-calculus
Booleans [done]
Records (structs, tuples) [done] Numbers [done]
Lists
Functions [we got those] Recursion
¦Ë-calculus: Lists
Lets define an API to build lists in the ¦Ë-calculus.
An Empty List
58 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
NIL
Constructing a list
A list with 4 elements
CONS apple (CONS banana (CONS cantaloupe (CONS dragon NIL))) intuitively CONS h t creates a new list with
head h tail t
Destructing a list
HEAD l returns the first element of the list TAIL l returns the rest of the list
HEAD (CONS apple (CONS banana (CONS cantaloupe (CONS dragon NI
L))))
=~> apple
TAIL (CONS apple (CONS banana (CONS cantaloupe (CONS dragon NI
L))))
=~> CONS banana (CONS cantaloupe (CONS dragon NIL)))
59 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
¦Ë-calculus: Lists
let NIL = ??? let CONS = ??? let HEAD = ??? let TAIL = ???
eval exHd:
HEAD (CONS apple (CONS banana (CONS cantaloupe (CONS dragon NI
L))))
=~> apple
eval exTl
TAIL (CONS apple (CONS banana (CONS cantaloupe (CONS dragon NI
L))))
=~> CONS banana (CONS cantaloupe (CONS dragon NIL)))
60 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
EXERCISE: Nth
Write an implementation of GetNth such that
GetNth n l returns the n-th element of the list l
Assume that l has n or more elements let GetNth = ???
eval nth1 :
GetNth ZERO (CONS apple (CONS banana (CONS cantaloupe NIL)))
=~> apple
eval nth1 :
GetNth ONE (CONS apple (CONS banana (CONS cantaloupe NIL)))
=~> banana
eval nth2 :
GetNth TWO (CONS apple (CONS banana (CONS cantaloupe NIL)))
=~> cantaloupe
Click here to try this in elsa (https://goto.ucsd.edu /elsa/index.html#?demo=permalink%2F1586466816_52273.lc)
61 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
¦Ë-calculus: Recursion
I want to write a function that sums up natural numbers up to n : let SUM = \n -> … — 0 + 1 + 2 + … + n
such that we get the following behavior
eval exSum0: SUM ZERO =~> ZERO
eval exSum1: SUM ONE =~> ONE
eval exSum2: SUM TWO =~> THREE
eval exSum3: SUM THREE =~> SIX
Can we write sum using Church Numerals?
Click here to try this in Elsa (https://goto.ucsd.edu
/elsa/index.html#?demo=permalink%2F1586465192_52175.lc)
QUIZ
62 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
You can write SUM using numerals but its tedious. Is this a correct implementation of SUM ?
letSUM=\n->ITE(ISZn) ZERO
(ADD n (SUM (DEC n)))
A. Yes B. No
No!
Named terms in Elsa are just syntactic sugar
To translate an Elsa term to ¦Ë-calculus: replace each name with its definition
\n -> ITE (ISZ n)
ZERO
(ADD n (SUM (DEC n))) — But SUM is not yet defined!
Recursion:
63 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Inside this function
Want to call the same function on DEC n
Looks like we can¡¯t do recursion!
Requires being able to refer to functions by name,
But ¦Ë-calculus functions are anonymous. Right?
¦Ë-calculus: Recursion Think again!
Recursion:
Instead of
64 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Inside this function I want to call the same function on DEC n Lets try
Inside this function I want to call some function rec on DEC n And BTW, I want rec to be the same function
Step 1: Pass in the function to call ¡°recursively¡±
let STEP =
\rec -> \n -> ITE (ISZ n)
ZERO
(ADD n (rec (DEC n))) — Call some rec
Step 2: Do some magic to STEP , so rec is itself
\n -> ITE (ISZ n) ZERO (ADD n (rec (DEC n)))
That is, obtain a term MAGIC such that MAGIC =*> STEP MAGIC
65 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
¦Ë-calculus: Fixpoint Combinator Wanted: a ¦Ë-term FIX such that
FIX STEP calls STEP with FIX STEP as the first argument: (FIX STEP) =*> STEP (FIX STEP)
(In math: a fixpoint of a function f(x) is a point x, such that f(x) = x)
Once we have it, we can define:
let SUM = FIX STEP
Then by property of FIX we have:
SUM =*> FIX STEP =*> STEP (FIX STEP) =*> STEP SUM
and so now we compute:
66 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
eval sum_two:
SUM TWO
=*> STEP SUM TWO
=*> ITE (ISZ TWO) ZERO (ADD TWO (SUM (DEC TWO)))
=*> ADD TWO (SUM (DEC TWO))
=*> ADD TWO (SUM ONE)
=*> ADD TWO (STEP SUM ONE)
=*> ADD TWO (ITE (ISZ ONE) ZERO (ADD ONE (SUM (DEC ONE))))
=*> ADD TWO (ADD ONE (SUM (DEC ONE)))
=*> ADD TWO (ADD ONE (SUM ZERO))
=*> ADD TWO (ADD ONE (ITE (ISZ ZERO) ZERO (ADD ZERO (SUM DEC ZER
O)))
=*> ADD TWO (ADD ONE (ZERO))
=*> THREE
How should we define FIX ???
The Y combinator
Remember ¦¸?
67 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
(\x -> x x) (\x -> x x)
=b> (\x -> x x) (\x -> x x)
This is self-replcating code! We need something like this but a bit more involved…
The Y combinator discovered by Haskell Curry:
let FIX = \stp -> (\x -> stp (x x)) (\x -> stp (x x))
How does it work?
eval fix_step:
FIX STEP
=d> (\stp -> (\x -> stp (x x)) (\x -> stp (x x))) STEP =b> (\x -> STEP (x x)) (\x -> STEP (x x))
=b> STEP ((\x -> STEP (x x)) (\x -> STEP (x x)))
— ^^^^^^^^^^ this is FIX STEP ^^^^^^^^^^^
That¡¯s all folks, Haskell Curry was very clever.
Next week: We¡¯ll look at the language named after him ( Haskell )
68 of 69 1/7/21, 8:59 AM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
(https://ucsd-cse130.github.io/wi21/feed.xml) (https://twitter.com/ranjitjhala) (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/).
69 of 69 1/7/21, 8:59 AM