“Lambda-Calculus and Combinators: An Introduction”メモ
J. Roger Hindley, Homepage — http://www.users.waitrose.com/~hindley/ 著者の一人が ICL2 と略しておられるのでそれを使わせて頂きます。ICL2 1章の気付きポイントのメモと練習問題の写経など。
By the way, the expression ‘$λ$’ by itself is not a term, though it may occur in terms; similarly the expression ‘$λx$’ is not a term.
Exercise 1.4
省略表記された λ-term の括孤とλを補う問題。
$\begin{array} &
\mbox{(a) } xyz(yx) \\
≡ \Big(((xy)z)(yx)\Big) \\
\\
\mbox{(b) } λx.uxy \\
≡ \Big(λx.((ux)y)\Big) \\
\\
\mbox{(c) } λu.u(λx.y) \\
≡ \Big(λu.(u(λx.y))\Big) \\
\\
\mbox{(d) } (λu.vuu)zy \\
≡ \Big(\Big((λu.((vu)u))z\Big)y\Big) \\
\\
\mbox{(e) } ux(yz)(λv.vy) \\
≡ \Big(((ux)(yz))(λv.(vy))\Big) \\
\\
\mbox{(f) } (λxyz.xz(yz))uvw \\
≡ \Big(\Big(\Big(\Big(λx.(λy.(λz.((xz)(yz))))\Big)u\Big)v\Big)w\Big) \\
\\
\end{array}$
Exercise 1.8
省略表記された λ-term の括孤とλを補うことがヒント。
$\begin{array} &
\mbox{(a) 以下の λ-termの xy に下線を付ける} \\
λxy.xy \\
≡ (λx.(λy.(\underline{xy}))) \\
\\
\mbox{(b) uv に下線を付ける} \\
x(uv)(λu.v(uv))uv \\
≡ ((((x(\underline{uv}))(λu.(v(\underline{uv}))))u)v) \\
\\
\mbox{(c) 以下の λ-term に λu.u が存在するかどうか} \\
λu.u \\
≡ (λu.u), \\
λu.uv \\
≡ (λu.(uv)) \mbox{これには λu.u は存在しない}
\end{array}$
Exercise 1.14
$(c)$ は Definition 1.12 (Substitution) から Remark 13 で特に解説されたもの。
$\begin{array} &
\mbox{(a) } [(uv)/x](λy.x(λw.vwx)) \\
≡ λy.(uv)(λw.vw(uv)) \\
\\
\mbox{(b) } [(λy.xy)/x](λy.x(λx.x)) \\
≡ λy.(λy.xy)(λx.x) \\
\\
\mbox{(c) } [(λy.vy)/x](y(λv.xv)) \\
≡ y[(λy.vy)/x](λv.xv) \\
≡ y(λz.[(λy.vy)/x][z/v]xv) \\
≡ y(λz.(λy.vy)z) \\
;; \mbox{解答では、 z ≠ x,y,v。ただ、Definition 1.12 から} \\
;; z \notin FV((λy.vy)(xv)) \mbox{ を満たすもので良いので } z \notin \{x, v\}\\
\\
\mbox{(c)別解 } [(λy.vy)/x](y(λv.xv)) \\
≡ y[(λy.vy)/x](λv.xv) \\
≡ y(λy.[(λy.vy)/x][y/v]xv) \\
≡ y(λy.(λy.vy)y) \\
;; \mbox{z の替わりに y と置いた場合でも満たしているのがわかる} \\
\\
\mbox{(d) } [(uv)/x](λx.zy) \\
≡ λx.zy \\
\end{array}$