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


(1)
(λ x y. x y (λ u v. v)) (λ x y. x) (λ x y. y)
→ (λ w. (λ x y. x) w (λ u v. v)) (λ x y. y)(λ x y. x) (λ x y. y) (λ u v. v)
→ (λ w x y. y) (λ u v. v)
λ x y. y

(2)
(λ a b. b a) (λ f x. f (f x)) (λ f x. f (f x))
→ (λ b. b (λ f x. f (f x))) (λ f x. f (f x))(λ f x. f (f x)) (λ f x. f (f x))
→ λ g. (λ f x. f (f x)) ((λ f x. f (f x)) g)
→ λ g w. (λ f x. f (f x)) g ((λ f x. f (f x)) g w)
→ λ g w. (λ x. g (g x)) ((λ f x. f (f x)) g w)
(ここで止めてもよい)
→ λ g w. g (g ((λ f x. f (f x)) g w))
→ λ g w. g (g ((λ x. g (g x)) w))
→ λ g x. g (g (g (g x)))

(オンライン問題)Ⅱ
a.
bar source =
  let strs = lines source
    in unlines (map unwords (map reverse (map words strs)))

main = do source <- getContents
          putStr (bar source)
b.(ハンドコーディングの場合)
foo n = foo' n 0
  where foo' n c = if n == 1 then c
                   else if n `mod` 2 == 0 then foo' (n `div` 2) (c + 1)
                        else foo' (3 * n + 1) (c + 1)