練習問題の解答例

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