プログラミング言語論第１０回練習問題解答例情報工学科篠埜功練習問題１（問１）ラムダ式 (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) にβ変換を適用せよ。（問２）ラムダ式 (λ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に変換できるが、その過程を示せ。練習問題４解答例 (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 （注意）上記において、置換を用いた記述は省略している。