Syntax 。入terms or入expressions: (Terms)M,N:=x入x.MMN ·pure入-calculus Add extra operations and data types ·2x.(X+1) ·入z.(x+2*y+z) ·(2×.(x+1)3=3+1 ·(2z.(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 extends as far to the right as possible Ax.M N means Ax.(M N),not (x.M)N ·入x.fx=入x.(fx) ·x.入f.fx=入x.(入f.fx) Function applications are left-associative MN P means(M N)P,not M(N P) ·(2x.y.x-yW53=((x.y.x-y)5)3 ·(2f.入x.fx)(x.x+1)2=((2f.入x.fx)(2x.×+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 x(y.×-y Functions can be passed as arguments (f.2x.fx)⑦x.x+12 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 入f.2x.f(fx) ·How does this work? (2f.x.f(fx)(y.y+1)5 =(x.(y.y+1)(y.y+1)X)5 =(2x.(2y.y+1)(+1)5 =(2x.(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 functions Note difference between x.y.×-y and int f (int x,int y)return x-y;} 。入abstraction is a function of 1 parameter But computationally they are the same (can be transformed into each other) ·Curry:transform(x,y).x-yto入x.y.×-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;}