Programowanie funkcyjne/Procedury jeszcze wyższych rzędów

Wstęp

Jaka jest różnica między danymi i procedurami? W programowaniu funkcyjnym to rozróżnienie rozmywa się. Dane mogą być traktowane jak procedury --- każdy interpreter czy kompilator zamienia dane (kod źródłowy programu) na procedurę (wykonywalny program). Procedury wyższych rzędów operują na innych procedurach jak na danych. Tak więc procedury mogą być również danymi. Można by powiedzieć, że dane tym różnią się od procedur, że zawsze są podmiotem obliczeń, a nigdy nie są same wykonywane. Niniejszy wykład powinien Państwa przekonać, że wcale tak nie musi być.

Używając języka programowania nie widzimy w jaki sposób zrealizowane są struktury danych, ani jak jest zrealizowane stosowanie procedur do argumentów. Łatwo sobie wyobrazić, że procedury mogą mieć postać kodu źródłowego lub częściowo skompilowanego, który jest interpretowany. Jak zobaczymy w tym wykładzie, również dane nie muszą być biernym przedmiotem obliczeń. Poznamy jedną z możliwych implementacji danych --- całkowicie proceduralną.

Uwaga

Niniejszy wykład ma całkowicie charakter ćwiczenia umysłowego. Struktury danych wcale nie są implementowane w opisany sposób, ani nie jest to najlepszy sposób ich implementacji. Jednak opisany sposób ich realizacji jest możliwy. Celem tego ćwiczenia jest zilustrowanie w pełni zamiennego traktowania danych i procedur. Zdobywszy tę umiejętność będziemy mogli wznieść się na wyższy poziom abstrakcji i tworzyć struktury, w których dane są przemieszane z procedurami. Jest to również dobre ćwiczenie rozwijające umiejętność posługiwania się procedurami wyższych rzędów.

Definiowanie form specjalnych

W Ocamlu argumenty procedur są obliczane gorliwie,tzn. najpierw są obliczane ich wartości, a dopiero potem przystępujemy do obliczania wartości procedury. Wyjątkiem są formy specjalne, np. if ---w zależności od wartości warunku, tylko jeden z pozostałych członów jest obliczany. Czy można takie formy zaimplementować samemu? Tak. Potrzeba do tego dwóch rzeczy. Musimy umieć zabezpieczać wartości przed zbyt wczesnym obliczaniem i definiować makrodefinicje.

Makrodefinicje

W Ocamlu możemy zmieniać składnię języka wprowadzając własne makrodefinicje. Służy do tego preprocesor P4. Nie będziemy tu mówić o nim, lecz sporadycznie użyjemy definicji wprowadzających potrzebne nam formy specjalne.

Wartości logiczne

Aby mówić o wartościach logicznych potrzebujemy:

• prawdę i fałsz,
• (if ...),
• koniunkcję, alternatywę i negację.

Wartość logiczną reprezentuję jako procedurę dwuargumentową, która w przypadku prawdy wybiera pierwszy, a w przypadku fałszu drugi argument.

let prawda x y = x;;
let falsz  x y = y;;
let jesli w k a = force (w k a);;
jesli prawda (lazy 1) (lazy 2);;
= 1
let i x y  = x y falsz;;
let lub x y = x prawda y;;
let nie x a b = x b a;;
jesli (lub falsz prawda) (lazy 1) (lazy 2);;
= 1

Produkty kartezjańskie

Aby mówić o produkcie musimy mieć:

• konstruktor pary pr: $\alpha \to \beta \to$ produkt,
• rzuty: p1: produkt $\to \alpha$ i p2: produkt $\to \beta$.

Produkt, to para argumentów czekających na funkcję.

let pr x y = function f -> f x y;;
let p1 p = p prawda;;
let p2 p = p falsz;;
let p x = pr 1 "ala" x;;
p1 p;;
= 1
p2 p;;
= "ala"

Listy nieskończone

Listy nieskończone można reprezentować jako funkcje z int. Potrzebujemy:

• listę stałą,
• dołączenie elementu na początek listy,
• pierwszy element listy,
• ogon listy.

let stala x n =  x;;
let sklej h t n = if n = 0 then h else t (n-1);; 
let glowa l = l 0;;
let ogon l n = l (n + 1);;

Liczby naturalne Churcha

Pozostały nam jeszcze liczby naturalne. (Rozszerzenie liczb naturalnych do całkowitych pozostawiamy jako ćwiczenie dla ambitnych. :-) Utożsamiamy liczbę naturalną z liczbą iteracji zadanej funkcji.

$n\equiv f\to f^n$

let id x = x;;
let compose f g = function x -> f (g x);;
let zero f = id;;
let jeden f = f;;
     

Dodawanie i mnożenie:

let inc n f = compose (n f) f;;	$f^{n+1}=f^n\circ f$
let plus m n f = compose (m f) (n f);;	$f^{m+n}=f^m\circ f^n$
let razy = compose;;	$(\text{<mrow data-mjx-texclass="ORD">razy</mrow>}mn)f=(\text{<mrow data-mjx-texclass="ORD">compose</mrow>}mn)f=$ $m(nf)=m(f^n)=(f^n{)}^m=f^{m\cdot n}$

Do celów testowych można używać:

let ile n = n (function x -> x + 1) 0;;
let compose f g = function x -> f (g x);;
let rec iterate n f =
  if n = 0 then id else compose (iterate (n-1) f) f;;
ile (iterate 1000);;
= 1000
  
let dwa x = plus jeden jeden x;;
ile (razy dwa dwa);;
= 4      

Jak moglibyśmy odróżniać od siebie liczby naturalne Churcha? Podstawową operacją porównania jest tzw. test zera --- sprawdzenie, czy dana liczba jest równa zero. Szukamy więc takiej funkcji $f$, że $f^0=\text{<mrow data-mjx-texclass="ORD">id</mrow>}$ jest czymś istotnie innym, niż $f^i$ dla $i>0$. Taką funkcją może być:

$f(x)=\text{<mrow data-mjx-texclass="ORD">falsz</mrow>}$

let test_zera x = x (function _ -> fałsz) prawda;;
jesli (test_zera zero) (lazy 1) (lazy 2);;
= 1      

Jak zmniejszyć $n$ o 1? Liczba $n$ to taki obiekt, który przekształca zadaną funkcję $f$ w funkcję $f^n$. Nie mamy jednak żadnego dostępu do tego jak $n$ to robi. Problem ten można przedstawić sobie tak: mając dane $n$, $f$ i $x$ należy obliczyć $f^{n-1}(x)$.

Rozważmy funkcję:

$g(a,b)=(b,fa)$

oraz ciąg:

$(g^i(x,x){)}_{i=0,\dots ,n}=((x,x),(x,fx),(fx,f^{2}x),\dots ,(f^{n-1}x,f^{n}x))$

Wystarczy więc z ostatniej pary w ciągu wydobyć pierwszą współrzędną. Co można zapisać tak:

let dec n f x = 
  let g (a, b) = (b, f b)
  in let (y, _) = n g (x, x) 
     in y;;
val dec:(('a*'b->'b*'c)->'d*'d->'e*'f)->('b->'c)->'d->'e      

lub tak, wykorzystując zaimplementowane przez nas produkty kartezjańskie:

let dec n f x = p1 (n (function p -> pr (p2 p) (f (p2 p))) (pr x x));;
val dec : 
(((('a -> 'b -> 'b) -> 'c) -> ('c -> 'd -> 'e) -> 'e) -> 
(('f -> 'f -> 'g) -> 'g) -> ('h -> 'i -> 'h) -> 'j) -> 
('c -> 'd) -> 'f -> 'j = <fun>
ile (dec dwa);;
= 1      

Odejmowanie, to wielokrotne zmniejszanie o jeden:

let minus m n = (n dec) m;;
ile (minus dwa jeden);;
= 1      

Za pomocą odejmowania i testu zera można zaimplementować porównanie:

let wieksze m n = nie (test_zera (minus m n));;
jesli (wieksze dwa jeden) (lazy 1) (lazy 2);;
= 1

Abstrakcja rekurencji

Procedura fold stanowi abstrakcję rekurencyjnego przetwarzanialist. Czy istnieje kwintesencja wszelkiej rekurencji? A co to jest rekurencja? Jak przerobić definicję rekurencyjną na nierekurencyjną --- poprzez wprowadzenie dodatkowego parametru funkcyjnego. Przykład: silnia. Z rekurencją:

let rec fac n = 
  if n <= 1 then 
    1 
  else
    n * fac (n - 1);;
     

Bez rekurencji:

let factorial fac n = 
  if n <= 1 then 
    1 
  else 
    n * fac (n - 1);;
     

To jest procedura, która przetwarza procedurę facliczącą poprawnie silnię dla liczb $\le n$ na procedurę liczącą poprawnie silnię dla liczb $\le n+1$. Teraz trzeba jakoś chytrze podstawić funkcję wynikową jako argument. Inaczej mówiąc szukamy funkcji, która jest punktem stałym factorial.Będzie ona poprawnie liczyć silnię dla wszystkich liczb.

Operator punktu stałego --- pierwsze podejście.

let rec y f = f (y f);;
  
let f = y factorial ;;
= factorial (y factorial) = factorial (factorial (y factorial)) = ...      

To się niestety zapętli, ze względu na to, że argument procedury factorial jest obliczany przed jej zastosowaniem. Aby uniknąć zapętlenia, musimy uleniwić ten argument argument i wyliczać go tylko na żądanie. Operator punktu stałego.

let factorial fac n = 
  if n <= 1 then 
    1 
  else 
    n * (force fac (n - 1));;
  
let rec y f = f (lazy (y f));;
  
let fac = y factorial ;;

Każdą procedurę rekurencyjną możemy sprowadzić do zastosowania operatora punktu stałego i uleniwiania. Oto kolejny przykład, rekurencyjna procedura obliczająca liczby Fibonacciego:

let fibonacci fib n = 
  if n <= 2 then 
    1
  else
    (force fib (n-1)) + (force fib (n-2));;
  
let fib = y fibonacci;;

Laboratoria i ćwiczenia

Laboratoria i ćwiczenia do wykładu