output: 2011,11,10 2.1 λ λ β λ λ - abstraction λ λ - binding 1 add1 + add1(x = x + 1 add1 λx.x + 1 x + 1 add1 function application 2 add1 add1(2 g.yamadatakahiro@gmail.com 1
add1 2 β β - conversion (λx.x + 1(2 β x + 1 x 2 2 + 1 2 λ f(x, y = 2 x + y 2 λ(x, y.2 x + y 1 λy.2 x + y λx.(λy.2 x + y x λy.2 x + y EXAMPLE (λ(x, y.2 x + y(3, 4 = (λx.(λy.2 x + y(3(4 2
( = 2 3 + 4 ( = (λy.2 3 + y(4 = 2 3 + 4 (λ(x, y.2 x + y(3, 4 = (λx.(λy.2 x + y(3(4 2 1 Currying 2.7 EXERCISE 2.1 f, g f = λ(x, y, z.x + y + z g = λx.(λy.(λz.x + y + z f(1, 2, 3 = g(1(2(3 f(1, 2, 3 = (λ(x, y, z.x + y + z(1, 2, 3 = 1 + 2 + 3 3
g(1(2(3 = (λx.(λy.(λz.x + y + z(1(2(3 = (λy.(λz.1 + y + z(2(3 = (λz.1 + 2 + z(3 = 1 + 2 + 3 f(1, 2, 3 = g(1(2(3 4
2.2 λ β DEF. λ λ - term λ 1. v, v,... λ 2. M, N λ (MN λ 3. M λ x (λx.m λ (2 (3 λ NOTATION 2 λ M, N M N EXERCISE 2.2.1 λ subterm λ M M (λv.(v(λv.v v, (λv.v, v, (v(λv.v, (λv.(v(λv.v λ DEF. λ λ M 1. M M 2. M 1, M 2 (M M 1 M 2 M 1, M 2 M 3. M 1, x(m λx.m 1 M 1 M 5
NOTATION M, M 1,..., M n λ x 1,..., x n 1. ((...((M 1 M 2 M 3...M n M 1...M n 2. (λx 1.(...(λx n.m... λx 1...x n.m EXAMPLE λxyz.xz(yz (λx.(λy.(λz.((xz(yz DEF. x λ M def x M λx. x x λ M def x M λx. x DEF. λ M F V (M M 1, M 2 λ x 1. x(m x F V (M = {x} 2. M 1, M 2 (M M 1 M 2 F V (M = F V (M 1 F V (M 2 3. M 1, x(m λx.m 1 F V (M = F V (M 1 {x} 6
EXAMPLE λx.y(λy.xy y x y DEF. λ closed λ - term combinator λ M λ def M ( F V (M = β DEF. λ M x λ N λ M[x := N] M 1, M 2 λ z 1. z(m z M[x := N] { N if z x z otherwise 2. M 1, M 2 (M M 1 M 2 M[x := N] M 1 [x := N]M 2 [x := N] 3. z, M 1 (M λz.m 1 λz.m 1 if { z x M[x := N] λz.m 1 [x := N] if z / F V (N or x / F V (M 1 otherwise, λz.m 1 [z := z ][x := N] otherwise z / F V (N F V (M 1 7
DEF. α α - conversion x M λ λx.m x x α λx.m λy.m[x := x ] AX. x, x, λ M λx.m λx.m[x := x ] β (λx.mn = M[x := N] β DEF. β λ λ M, N M = N λ M, N, L λ x (β (ξ (λx.mn = M[x := N] M = N λx.m = λx.n M = N ML = NL M = N LM = LN M = M L = M M = N L = N M = N N = M M = N λ λ M = N M = N 8
DEF. β β - convertibility λ M, N β β- convertible def M = N EXAMPLE (λxy.xy(λz.z = λy.(λz.zy (λxy.xy(λz.zy = λv.(λz.zyv (λxy.xy(λz.z = (λx.(λy.xy(λz.z = (λy.xy[x := λz.z] = λy.xy[x := λz.z] = λy.x[x := λz.z]y[x := λz.z] = λy.(λz.zy (λxy.xy(λz.zy = (λx.(λy.xy(λz.zy = (λy.xy[x := λz.zy] = λv.xy[y := v][x := λz.zy] = λv.(x[y := v]y[y := v][x := λz.zy] = λv.xv[x := λz.zy] = λv.x[x := λz.zy]v[x := λz.zy] = λv.(λz.zyv EXAMPLE (λxy.x(λx.x(λx.x = λx.x (λxy.(λz.zyx(λx.x = λy.y 9
( (λxy.x(λx.x(λx.x = (λxy.x(λx.x (λx.x ( = (λx.(λy.x(λx.x (λx.x ( = λy.x[x := λx.x] (λx.x = (λx.x(λx.x = x[x := λx.x] = λx.x ( (λxy.(λz.zyx(λx.x = λx.(λy.(λz.zyx (λx.x ( = λy.(λz.zyx [x := λx.x] ( = λy. (λz.zy(λx.x = λy.(zy[z := λx.x] = λy.(λx.xy = λy.x[x := y] = λy.y EXERCISE 2.2.2 λ M x 1,..., x n λ N 1,..., N n λ M[x 1,..., x n := N 1,..., N n ] M[x 1,..., x n := N 1,..., N n ] 10
DEF. λ M x 1,..., x n λ N 1,..., N n λ M[x 1,..., x n := N 1,..., N n ] M 1, M 2 λ z [x 1,..., x n := N 1,..., N n ] [x 1,..., x i 1, x i+1,..., x n := N 1,..., N i 1, N i+1,..., N n ] i 1. z(m z { M N i if 1 i n & z x i z otherwise 2. M 1, M 2 (M M 1 M 2 M M 1 M 2 3. z, M 1 (M λz.m 1 λz.m i 1 { if 1 i n & z x i M λz.m1 if z / 1 i n otherwise, F V (N or x 1,..., x n / F V (M 1 λz.m 1 [z := z ] otherwise z / 1 i n F V (N F V (M 1 DEF. [x 1,..., x n := N 1,..., N n ] n 1. n = 1 M n M[x 1 := N 1 ] 2. n k n n M (n+1 M[x 1,..., x n := N 1 [x n+1 := x n+1],..., N n [x n+1 := x n+1]] [x n+1 := N n+1 ] [x n+1 := x n+1 ] 11