プログラミング言語意味論 (2017 年度) テスト解答例(一部)


(1)
(λ x y z. x z (y z)) (λ a b. a) (λ c d. c)
→ (λ y z. (λ a b. a) z (y z)) (λ c d. c)
→ λ z. (λ a b. a) z ((λ c d. c) z)
→ λ z. (λ b. z) ((λ c d. c) z)
→ λ z. z
(2)
(λ m. m (λ f n. n f (f (λ f x. f x))) (λ n f x. n f (f x))) (λ f x. x) (λ f x. f x)
→ (λ f x. x) (λ f n. n f (f (λ f x. f x))) (λ n f x. n f (f x)) (λ f x. f x)
→ (λ x. x) (λ n f x. n f (f x)) (λ f x. f x)
→ (λ n f x. n f (f x)) (λ f x. f x)
→ λ f x. (λ f x. f x) f (f x)
→ λ f x. (λ x. f x) (f x) (ここで止めてもよい。)
→ λ f x. f (f x)