プログラミング言語意味論 (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