Syntax ·^ terms orλ expressions: erms)M,N:=X|λx.M|MN pure n-calculus Add extra operations and data types X.(X+1) AZ.(x+2*y+2) (入.(x+1)3=3+1 ·(2.(X+2*y+z)5=x+2*y+5
Syntax • terms or expressions: (Terms) M, N ::= x | x. M | M N • pure -calculus • Add extra operations and data types • x. (x+1) • z. (x+2*y+z) • (x. (x+1)) 3 = 3+1 • (z. (x+2*y+z)) 5 = x+2*y+5
Conventions Body of n extends as far to the right as possible nx MN means Ax(M N, not(x M)N 入X.fx=λx.(fx) 入X.f.fx=x.(ffx) Function applications are left-associative MNP means(M N)P, not M(N P (入X.y.X-y)53=(x.y.x-y)5)3 (fx.fx)(X.X+1)2=((千.AX.fx)(^x,X+1))2
Conventions • Body of extends as far to the right as possible x. M N means x. (M N), not (x. M) N • x. f x = x. ( f x ) • x. f. f x = x. ( f. f x ) • Function applications are left-associative M N P means (M N) P, not M (N P) • (x. y. x - y) 5 3 = ( (x. y. x - y) 5 ) 3 • (f. x. f x) (x. x + 1) 2 = ( (f. x. f x) (x. x + 1) ) 2
Higher-order functions Functions can be returned as return values 入xyx-y Functions can be passed as arguments 06×.×)(xx+1)2 Think about function pointers in C/C++
Higher-order functions • Functions can be returned as return values • Functions can be passed as arguments Think about function pointers in C/C++. x. y. x - y (f. x. f x) (x. x + 1) 2
Higher-order functions Given function f return function fo f 入.X.f(fx) · How does this work? xf.2.f(fx)y+1)5 =(x、+)(x.y+1)×)5 (X.(y+1)(x+1)5 (入X.(x+1)+1)5 5+1+1=7
Higher-order functions • Given function f, return function f ∘ f f. x. f (f x) • How does this work? (f. x. f (f x)) (y. y+1) 5 = (x. (y. y+1) ((y. y+1) x)) 5 = (x. (y. y+1) (x+1)) 5 = (x. (x+1)+1) 5 = 5+1+1 = 7
Curried functⅰonS Note difference between 入X.xy.x-y and int f (int x, int yi return x-y; n abstraction is a function of 1 parameter But computationally they are the same(can be transformed into each other Curry: transform n(x,y). x-y to nx. ny x-y Uncurry: the reverse of curry
Curried functions • Note difference between • abstraction is a function of 1 parameter • But computationally they are the same (can be transformed into each other) • Curry: transform (x, y). x-y to x. y. x - y • Uncurry: the reverse of Curry x. y. x - y and int f (int x, int y) { return x - y;}