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

(λ 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

(λ 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)))

bar source =
  let strs = lines source
    in unlines (map unwords (map reverse (map words strs)))

main = do source <- getContents
          putStr (bar source)

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)