プログラミング言語意味論 （2016 年度） テスト解答例（一部）
Ⅰ
(1)
→ (λ a b. b a) (λ f x. f x) (λ f x. f (f x))
→ (λ b. b (λ f x. f x)) (λ f x. f (f x))
→ (λ f x. f (f x)) (λ f x. f x)
→ λ x. (λ f x. f x) ((λ f x. f x) x)
→ λ x x1. (λ f x. f x) x x1
→ λ x x1. (λ x1. x x1) x1 （ここで止めてよい。）
→ λ x x1. x x1
(2)
→ (λ t. t (λ a b. b)) ((λ x y g. g x y) (λ f x. f x) (λ f x. x))
→ (λ x y g. g x y) (λ f x. f x) (λ f x. x) (λ a b. b)
→ (λ y g. g (λ f x. f x) y) (λ f x. x) (λ a b. b)
→ (λ g. g (λ f x. f x) (λ f x. x)) (λ a b. b)
→ (λ a b. b) (λ f x. f x) (λ f x. x)
→ (λ b. b) (λ f x. x) （ここで止めてよい。）
→ λ f x. x