練習問題の解答例

プログラミング言語論
第９回
練習問題解答例
情報工学科篠埜功
練習問題１
（問１）ラムダ式 (z. z) w 中の自由変数を求めよ。
（問２）ラムダ式 (λz. z y) ((λz. z) w) 中の自由変数を
求めよ。
練習問題１解答例
（問１）ラムダ式 (z. z) w 中の自由変数を求めよ。
FV((z. z) w) = FV((z. z))  FV (w)
= (FV (z) \ {z})  {w}
= ({z} \ {z})  {w}
= { }  {w}
= {w}
（問２）ラムダ式 (λz. z y) ((λz. z) w) 中の自由変数を求めよ。
FV((λz. z y) ((λz. z) w)) = FV(λz. z y)  FV((λz. z) w)
= (FV (z y) \ {z})  (FV(λz. z)  FV(w))
= ((FV (z)  FV(y)) \ {z})  ((FV(z) \ {z})  {w})
= (({z}  {y}) \ {z})  (({z} \ {z})  {w})
= ({z,y} \ {z})  ({ }  {w})
= {y}  {w}
= {y, w}
練習問題２
（問１）置換 (x y) [z/x] を求めよ。
（問２）置換 (λy. x y) [z/x] を求めよ。
（問３）置換 (λy. x y) [y/x] を求めよ。
（問４）置換 (λy. x y) [λz. z y/x] を求めよ。
練習問題２解答例
（問１）置換 (x y) [z/x] を求めよ。
(x y) [z/x] = (x [z/x]) (y [z/x])
=zy
（問２）置換 (λy. x y) [z/x] を求めよ。
(λy. x y) [z/x] = λy. ((x y) [z/x])
= λy. ((x [z/x]) (y [z/x]))
= λy. (z y) （括弧は省略可）
（問３）置換 (λy. x y) [y/x] を求めよ。
(λy. x y) [y/x] = λz. (((x y) [z/y]) [y/x])
= λz. (((x [z/y]) (y [z/y])) [y/x])
= λz. ((x z) [y/x])
= λz. ((x [y/x]) (z [y/x]))
= λz. (y z) （括弧は省略可）
練習問題２解答例（続き）
（問４）置換 (λy. x y) [λz. z y/x] を求めよ。
(λy. x y) [λz. z y/x] = λw. (((x y) [w/y]) [λz. z y/x])
= λw. (((x [w/y]) (y [w/y])) [λz. z y/x])
= λw. ((x w) [λz. z y/x])
= λw. ((x [λz. z y/x]) (w [λz. z y/x]))
= λw. ((λz. z y) w) （外側の括弧は省略可）
練習問題３
（問１）ラムダ式 (λx. x y) (λz. z) にβ変換を1回適用せよ。
（問２）ラムダ式 (λx. (λy. x y)) (λz. y z) にβ変換を1回適
用せよ。
練習問題３解答例
（問１）ラムダ式 (λx. x y) (λz. z) にβ変換を1回適用せよ。
(λx. x y) (λz. z)  (x y) [λz. z/x]
= (x [λz. z/x]) (y [λz. z/x])
= (λz. z) y
（さらにもう一度β変換は適用可能）
（問２）ラムダ式 (λx. (λy. x y)) (λz. y z) にβ変換を1回適用せよ。
(λx. (λy. x y)) (λz. y z)  (λy. x y) [λz. y z/x]
= λz. (((x y) [z/y]) [λz. y z/x])
= λz. (((x [z/y]) (y [z/y])) [λz. y z/x])
= λz. ((x z) [λz. y z/x])
= λz. ((x [λz. y z/x]) (z [λz. y z/x]))
= λz. ((λz. y z) z) （外側の括弧は省略可）
（さらにもう一度β変換は適用可能）
練習問題４
ラムダ式 (λx. λy. x y) (λz. z) w は、何度かβ
変換を行うことによってwに変換できるが、
その過程を示せ。
練習問題４解答例
(x. y. x y) (z. z) w
 (λy. (λz. z) y) w
 (λy. y) w
w
または
(x. y. x y) (z. z) w
 (λy. (λz. z) y) w
 (λz. z) w
w
（注意）上記において、置換を用いた記述は省略している。
練習問題５
ラムダ式 (λx. λy. x y) (λx. x y) wに対して、β変換を
適用する箇所のないラムダ式になるまでβ変換を
適用せよ。また、この例では途中で、２通りの適用
可能性のあるラムダ式が出てくる。２通りのβ変換
列を示せ。
練習問題５解答例
(x. y. x y) (λx. x y) w
 (λz. (λx. x y) z) w
 (λz. z y) w
wy
または、
(x. y. x y) (λx. x y) w
 (λz. (λx. x y) z) w
 (λx. x y) w
wy
（注意）上記において、置換を用いた記述は省略している。

Download Report