プログラミング言語意味論（2013年度）テスト解答例（一部）

(λn. n (λx. (λx y. y)) (λx y. x)) (λf x. f (f x))
→ (λf x. f (f x)) (λx. (λ x y. y)) (λx y. x)
→ (λx. (λx. (λx y. y)) ((λx. (λx y. y)) x)) (λx y. x)
→ (λx. (λx y. y)) ((λx. (λ x y. y)) (λx y. x))
→ λx y. y

(λn f x. n (λg h. h (g f)) (λu. x) (λu. u)) (λf x. f x)
→ λf x. (λf x. f x) (λg h. h (g f)) (λu. x) (λu. u)
→ λf x. (λx. (λg h. h (g f)) x) (λu. x) (λu. u)
→ λf x. (λg h. h (g f)) (λu. x) (λu. u)
→ λf x. (λh. h ((λu. x) f)) (λu. u)
→ λf x. (λu. u) ((λu. x) f)
→ λf x. (λu. x) f
→ λf x. x