cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
win Appeal
Conditionals Loops
as
1 of 68
1/4/21, 8:40 PM
Lambda Calculus
Have youheardof 1
Your Favorite Language
Probably has lots of features:
15hr5
Assignment (x = x + 1) O
E8
Booleans, integers, characters, strings, …
return, break, continue
Functions
ROI
Recursion
References / pointers Objects and classes Inheritance
…
Which ones can we do without?
What is the smallest universal language?
YET
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
What is computable? Before 1930s
Turing Mach 105 Informal notion of an e!ectively calculable function:
t
O
can be computed by a human with pen and paper, following an algorithm
1936: Formalization
2 of 68 1/4/21, 8:40 PM
cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
What is the smallest universal language?
turns
105
Alan Turing
19301
Alonzo Chardy
3 of 68
1/4/21, 8:40 PM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Alonzo Church
The Next 700 Languages
Peter Landin
4 of 68 1/4/21, 8:40 PM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Peter Landin, 1966
The Lambda Calculus
Has one feature: Functions
Function Calls
Whatever the next 700 languages turn out to be, they will surely be variants of lambda calculus.
5 of 68 1/4/21, 8:40 PM
cse130 https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
No, really
Assignment (x = x + 1)
Booleans, integers, characters, strings, … Conditionals
Loops
return, break, continue Functions
Recursion
References / pointers Objects and classes Inheritance
Reflection
More precisely, only thing you can do is:
Define a function Call a function
6 of 68 1/4/21, 8:40 PM
cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
7 of 68
1/4/21, 8:40 PM
PW
Describing a Programming Language
Syntax: what do programs look like? Semantics: what do programs mean?
Operational semantics: how do programs execute step-by-step?
Syntax: What Programs Look Like
cse130 Express variable
e ::= x E applehorse
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
notexpr arsine ae
Programs are expressions e (also called ¦Ë-terms) of one of three kinds:
Variable
x, y, z
Abstraction (aka nameless function definition)
\x->e
x is the formal parameter, e is the body ¡°for any x compute e ¡±
Application (aka function call)
e1 e2
e1 is the function, e2 is the argument in your favorite language: e1(e2)
(Here each of e , e1 , e2 can itself be a variable, abstraction, or application)
8 of 68
1/4/21, 8:40 PM
| \x -> e funchfiniti dn
| e1 e2
return e
IX
valid Ax
Gx lx
fencer
net
y fencer
ret
y
s
y
cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
Examples
\x -> x
function y return y id — The identity function (id)
— (“for any x compute x”)
oI
\x -> (\y -> y)
\f -> (f (\x -> x)) — A function that applies its argument to id
function a x
a
ya
c
QUIZ
x
CxcyDC
g
— A function that returns (id)
return
t
funcaonly
return y 33
Which of the following terms are syntactically incorrect?
t
A. \(\x->x)->y
B. \x -> x x
C. \x -> x (y x)
D. A and C
E Alloftheabove 9 of 68
At functionCx returnseen
B funonin se funches ret x
return hisses return a
yes
1/4/21, 8:40 PM
cse130
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
10 of 68
If
5
235
ME
so
1/4/21, 8:40 PM
E. all of the above
lx Ix
Examples
\x -> x
\x -> (\y -> y)
on
\f -> f (\x -> x)
xx
x
valid
valid
x
— The identity function
— (“for any x compute x”)
— A function that returns the identity functi
— A function that applies its argument
— to the identity function
How do I define a function with two arguments?
e.g. a function that takes x and y and returns y ?
wit
21
3
5
e
v
cse130
i Cx x
asf \x -> (\y -> y)
https://ucsd-cse130.github.io/wi21/lectures/01-lambda.html
11 of 68
1/4/21, 8:40 PM
I
y
funcC4E.e3iixIxI
on
sxJdognLna.I
anonymous
Kk
functions
must be a variable e NOT an expr
— A function that returns the identity functi
— OR: a function that takes two arguments
— and returns the second one!
EDxusax
sxCd4x
9 func Arg
t
How do I apply a function to two arguments?
e.g. apply \x -> (\y -> y) to apple and banana ?
dog