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ą 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 i na jak jest zrealizowane wykonywanie procedur. Łatwo sobie wyobrazić, że procedury mogą mieć postać kodu źródłowego lub częściowo skompilowanego, który jest interpretowany.Tak więc procedury mogą być zrealizowane w postaci danych (interpretowanych przez procedurę ewaluatora). Podobnie, dane mogą być procedurami. Nie widzimy sposobu implementacji podstawowych struktur danych wbudowanych w język programowania. Poznamy teraz jedną z możliwych ich implementacji - całkowicie proceduralną.

Uwaga

Niniejszy wykład ma charakter ćwiczenia umysłowego. Struktury danych wcale nie są implementowane w opisany sposób, ani nie jest to najlepszy sposób ich implementacji. Jest to jednak możliwe. Celem tego ćwiczenia jest zilustrowanie w pełni zamiennego traktowania danych jak procedur i procedur jak danych. 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.

Niektóre programy, ze względu na system typów Ocamla działają "jednorazowo", tzn. każda konstrukcja jest poprawna izostała przetestowana, jednak użycie jednej konstrukcji może uniemożliwić użycie innej.

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.

Uleniwianie

Model obliczeniowy Ocamla charakteryzuje się zachłannym obliczaniem wartości --- argumenty funkcji są obliczane bez względu na to, czy są potrzebne. Uleniwianie polega na zabezpieczeniu wartości przed obliczeniem, jeżeli nie jest to potrzebne. Zamiast wartości mamy "obietnicę jej obliczenia", czyli procedurę bezargumentową, której wartością jest dana wartość. W momencie gdy wartość jest nam potrzebna, obliczamy ją. Żeby nie obliczać tej wartości wielokrotnie, stosujemy spamiętywanie. W Ocamlu dostępna jest forma specjalna lazy i procedura force. Lazy powoduje odroczenie (ze spamiętywaniem) obliczenia wyrażenia. Chcąc obliczyć wartość wykonujemy na wyniku lazy operację force. Na potrzeby tego wykładu zaimplementujemy uproszczoną wersję uleniwiania, bez spamiętywania. Do zaimplementowania spamiętywania potrzebowalibyśmy operacji imperatywnych, o których nie było jeszcze mowy.

type 'a delayed = unit -> 'a;;
lazy w ≡ function () -> w
let force x = x ();;
let a = delay 4;;
force a;;

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