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

From Studia Informatyczne

Spis treści

Zadanie 1

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

  • {\cal O}(n_1, ..., n_m) = 0
  • {\cal S}(x) = x+1
  • {\cal I}^n_i(n_1, ..., n_m) = n_i.

Wskazówka:

Funkcje \cal O, \cal S{\cal I}^n_i są reprezentowane odpowiednio przez termy

O, SI^n_i:

  • O = \lambda n_1 ...n_m sx.x
  • S = \lambda n sx. s(nsx)
  • I^n_i = \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):


\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, LR na przykładzie. Kodem pary (2,1) jest:


I \underline{2}\ \underline{1} = \lambda stx. s(s(tx)).


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


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


\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_1n_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:


\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) = [if\ n = 0\ then\ 1\ else\ f(n-1)\cdot n].


Punkt stały termu


F = \lambda f n. if\ n=0\ then\ 1\ else\ f(n - 1)\cdot n,


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


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


\aligned  f(0) & =   1\\ f(1) & =   1\\ f(n+1) & =  f(n) + f(n-1) \endaligned

Wskazówka:

Punkt stały termu


\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 {\cal Y} F, reprezentuje funkcję f.

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


\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