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

(λp. p (λx y. y) (λx y. x)) (λx y. x)
→ (λx y. x) (λx y. y) (λx y. x)
→ (λz x y. y) (λx y. x)
→ λx y. y

(λm n f x. m f (n f x)) (λf x. f (f x)) (λf x. f (f x))
→ (λn f x. (λf x. f (f x)) f (n f x)) (λf x. f (f x))
→ λf x. (λf x. f (f x)) f ((λf x. f (f x)) f x)
→ λf x. (λx. f (f x)) ((λf x. f (f x)) f x)
→ λf x. f (f ((λf x. f (f x)) f x))
→ λf x. f (f ((λx. f (f x)) x))     …  解答はここで止めてよい
→ λf x. f (f (f (f x)))