プログラミング言語意味論 （2015 年度） テスト解答例（一部）
Ⅰ
(1)
→ (λm n f. m (n f)) (λf x. f x) (λf x. f (f x))
→ (λn f. (λf x. f x) (n f)) (λf x. f (f x))
→ λf. (λf x. f x) ((λf x. f (f x)) f)
→ λf x. (λf x. f (f x)) f x
→ λf x. (λx. f (f x)) x
→ λf x. f (f x)
(2)
→ (λp. p (λx y. x)) ((λx y f. f x y) (λf x. f x) (λf x. x))
→ (λx y f. f x y) (λf x. f x) (λf x. x) (λx y. x)
→ (λy f. f (λf x. f x) y) (λf x. x) (λx y. x)
→ (λf. f (λf x. f x) (λf x. x)) (λx y. x)
→ (λx y. x) (λf x. f x) (λf x. x)
→ (λy f x. f x) (λf x. x) … 解答はここで止めてよい
→ λf x. f x