プログラミング言語論 第１０回 練習問題解答例 情報工学科　篠埜　功

練習問題１ （問１） ラムダ式 (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]) = z y （問２） 置換 (λ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) にβ変換を適用せよ。 （問２） ラムダ式 (λx. (λy. x y)) (λz. y z) にβ変換を適用せよ。 （注意）この問題では、β変換を一度だけ適用するものとする。

練習問題３解答例 （問１） ラムダ式 (λx. x y) (λz. z) にβ変換を適用せよ。 (λ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) にβ変換を適用せよ。 (λ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に変換できるが、その過程を示せ。 9

練習問題４解答例 (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 （注意）上記において、置換を用いた記述は省略している。 10

練習問題５ ラムダ式 (λx. λy. x y) (λx. x y) wに対して、β変換を適用する箇所のないラムダ式になるまでβ変換を適用せよ。また、この例では途中で、２通りの適用可能性のあるラムダ式が出てくる。２通りのβ変換列を示せ。 11

練習問題５解答例 (x. y. x y) (λx. x y) w  (λz. (λx. x y) z) w  (λz. z y) w  w y または、  (λx. x y) w （注意）上記において、置換を用いた記述は省略している。 12