Paradygmaty programowania/Ćwiczenia 8: U podstaw programowania funkcyjnego — rachunek lambda

Zadanie 1

Napisz termy reprezentujące następujące funkcje:

• ${𝒪}(n_1,...,n_m)=0$

• ${𝒮}(x)=x+1$

• ${{ℐ}}_i^n(n_1,...,n_m)=n_i$.

Wskazówka:

Funkcje ${𝒪}$, ${𝒮}$ i ${{ℐ}}_i^n$ są reprezentowane odpowiednio przez termy

$O$, $S$ i $I_i^n$:

• $O=\lambda n_1...n_{m}sx.x$

• $S=\lambda nsx.s(nsx)$

• $I_i^n=\lambda n_1...n_{m}sx.n_{i}sx$.

Zadanie 2

Napisz termy definiujące funkcję kodującą parę liczb oraz funkcje rozkodowujące.

Wskazówka:

Poniższe termy reprezentują funkcję kodującą (term $I$) oraz funkcje rozkodowujące (termy $L$ i $R$):

$\begin{array}{rlr}I& =& \lambda mnstx.(ms)(ntx)\\ R& =& \lambda zsx.z(\lambda y.y)sx\\ L& =& \lambda zsx.zs(\lambda y.y)x.\end{array}$

Kodem pary liczb $(m,n)$ jest funkcja, która czeka na podanie dwóch argumentów: jeżeli pierwszy z nich jest identycznością, to funkcja zwraca $n$, jeżeli drugi, to $m$. Sprawdźmy jak działają termy $I$, $L$ i $R$ na przykładzie. Kodem pary $(2,1)$ jest:

$I\underset{\_}{2}\underset{\_}{1}=\lambda stx.s(s(tx))$.

Prawą współrzędną liczymy, używając termu $R$:

$\begin{array}{rlr}R(I\underset{\_}{2}\underset{\_}{1})& {=}_{\beta }& \lambda sx.(I\underset{\_}{2}\underset{\_}{1})(\lambda y.y)sx\\ & {=}_{\beta }& \lambda sx.(\lambda y.y)((\lambda y.y)(sx))\\ & {=}_{\beta }& \lambda sx.sx\\ & =& \underset{\_}{1}\end{array}$

a lewą — termu $L$:

$\begin{array}{rlr}L(I\underset{\_}{2}\underset{\_}{1})& {=}_{\beta }& \lambda sx.(I\underset{\_}{2}\underset{\_}{1})s(\lambda y.y)x\\ & {=}_{\beta }& \lambda sx.s(s((\lambda y.y)x))\\ & {=}_{\beta }& \lambda sx.s(sx)\\ & =& \underset{\_}{2}\end{array}$

Zadanie 3

Niech funkcje $h$ oraz $g_1,...,g_m$ będą lambda definiowalne odpowiednio przez termy $H$, $G_1$, ..., $G_m$, a jednoargumentowa funkcja $t$ przez term $T$. Napisz termy reprezentujące funkcje:

• $f_1(n_1,...,n_k)=h(g_1(n_1,...,n_k),...,g_m(n_1,...,n_k))$

• $f_2(x,n)=t^{(n)}(x)$.

Wskazówka:

• $F_1=\lambda n_1...n_{k}sx.H(G_1{n}_1...n_k)...(G_m{n}_1...n_k)sx$

• $F_2=\lambda xn.nTx$
  

Niech $t$ będzie funkcją następnika. Wówczas $f(1,2)=3$. Sprawdźmy, jak działa term $F_2$:

$\begin{array}{rlr}{F}_2\underset{\_}{1}\underset{\_}{2}& =& \underset{\_}{2}T\underset{\_}{1}\\ & {=}_{\beta }& (\lambda sx.s(sx))T\underset{\_}{1}\\ & {=}_{\beta }& T(T\underset{\_}{1})\\ & ...& \\ & {=}_{\beta }& \lambda sx.s(s(sx))\\ & =& \underset{\_}{3}\end{array}$

Zadanie 4

Napisz term reprezentujący funkcję $f(n)=n!$.

Wskazówka:

Funkcja $f$ daje się zapisać jako:

$f(n)=[ifn=0then1elsef(n-1)\cdot n]$.

Punkt stały termu

$F=\lambda fn.ifn=0then1elsef(n-1)\cdot n$,

czyli ${𝒴}F$, reprezentuje funkcję $f$. Sprawdźmy na kilku przykładach, czy tak jest rzeczywiście:

$\begin{array}{rlr}({𝒴}F)\underset{\_}{0}& =& F({𝒴}F)\underset{\_}{0}\\ & {=}_{\beta }& \underset{\_}{1}\\ \\ ({𝒴}F)\underset{\_}{1}& =& F({𝒴}F)\underset{\_}{1}\\ & {=}_{\beta }& (({𝒴}F)\underset{\_}{0})\cdot \underset{\_}{1}\\ & {=}_{\beta }& \underset{\_}{1}\\ \\ ({𝒴}F)\underset{\_}{2}& =& F({𝒴}F)\underset{\_}{2}\\ & {=}_{\beta }& (({𝒴}F)\underset{\_}{1})\cdot \underset{\_}{2}\\ & {=}_{\beta }& \underset{\_}{1}\cdot \underset{\_}{2}\\ ...\end{array}$

Zadanie 5

Napisz term reprezentujący funkcję Fibonacciego:

$\begin{array}{rl}f(0)& =1\\ f(1)& =1\\ f(n+1)& =f(n)+f(n-1)\end{array}$

Wskazówka:

Punkt stały termu

$\begin{array}{rl}F& =\lambda fn.ifn=0then1else\\ & ifn-1=0then1\\ & elsef(n-1)+f(n-2),\end{array}$

czyli ${𝒴}F$, reprezentuje funkcję $f$.

Sprawdźmy na przykładzie, czy tak jest rzeczywiście:

$\begin{array}{rl}({𝒴}F)\underset{\_}{2}& =F({𝒴}F)\underset{\_}{2}\\ & {=}_{\beta }(({𝒴}F)\underset{\_}{1})+(({𝒴}F)\underset{\_}{0})\\ & {=}_{\beta }\underset{\_}{1}+\underset{\_}{1}\end{array}$

Zadanie 6

Jakiego typu są poniższe termy:

• $\lambda x:\alpha \to \beta .\lambda y:\alpha .xy$

• $\lambda x:(\alpha \to \alpha )\to \beta .x(\lambda y:\alpha .y)$

• $\lambda x:\alpha \to (\beta \to beta).\lambda y:\alpha .xy$

Zadanie 7

Podaj przykładowe termy (jeśli takowe istnieją) dla poniższych typów.

• $\alpha \to \beta$

• $(\alpha \to (\alpha \to \alpha ))\to \alpha$

• $(\alpha \to \beta )\to (\alpha \to \alpha )$

• $\alpha \to (\alpha \to \beta )$

• $((\alpha \to \beta )\to \beta )\to \alpha$