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)=x_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$):

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned I & = & \lambda mn stx. (ms)(ntx)\\ R & = & \lambda z sx. z(\lambda y.y)sx\\ L & = & \lambda z sx. zs(\lambda y.y)x. \endaligned}

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$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned R (I \underline{2}\ \underline{1}) & =_\beta & \lambda sx. (I \underline{2}\ \underline{1})(\lambda y.y) sx\\ & =_\beta & \lambda sx. (\lambda y.y) ((\lambda y.y)(sx))\\ & =_\beta & \lambda sx. sx\\ & = & \underline{1} \endaligned}

a lewą - termu $L$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned L (I \underline{2}\ \underline{1}) & =_\beta & \lambda sx. (I \underline{2}\ \underline{1})s (\lambda y.y) x\\ & =_\beta & \lambda sx. s(s((\lambda y.y)x))\\ & =_\beta & \lambda sx. s(sx)\\ & = & \underline{2} \endaligned}

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$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned F_2 \underline{1}\ \underline{2} & = & \underline{2}\ T \underline{1}\\ & =_\beta & (\lambda sx. s(sx))T \underline{1}\\ & =_\beta & T( T\underline{1})\\ & ... & \\ & =_\beta & \lambda sx. s(s(sx))\\ & = & \underline{3} \endaligned}

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned ({\cal Y} F)\underline{0} & = & F({\cal Y} F)\underline{0}\\ & =_\beta & \underline{1}\\ \\ ({\cal Y} F)\underline{1} & = & F({\cal Y} F)\underline{1}\\ & =_\beta & (({\cal Y} F)\underline{0})\cdot \underline{1}\\ & =_\beta & \underline{1}\\ \\ ({\cal Y} F)\underline{2} & = & F({\cal Y} F)\underline{2}\\ & =_\beta & (({\cal Y} F)\underline{1})\cdot \underline{2}\\ & =_\beta & \underline{1}\cdot \underline{2}\\ ... \endaligned}

Zadanie 5

Napisz term reprezentujący funkcję Fibonacciego:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned f(0) & = 1\\ f(1) & = 1\\ f(n+1) & = f(n) + f(n-1) \endaligned }

Wskazówka:

Punkt stały termu

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned F & = \lambda f n. \quad if \quad n=0\ then\ 1\ else\\ & if\ n-1 = 0\ then\ 1\\ & else\ f(n - 1) + f(n-2), \endaligned }

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

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned ({\cal Y} F)\underline{2} & = \quad F({\cal Y} F)\underline{2}\\ & =_\beta \quad (({\cal Y} F)\underline{1}) + (({\cal Y} F)\underline{0})\\ & =_\beta \quad \underline{1} + \underline{1} \endaligned}

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$