Programowanie funkcyjne/Model obliczeń

Wstęp

W tym wykładzie przedstawimy uproszczoną semantykę operacyjną poznanego fragmentu Ocamla. Z jednej strony będzie to model wykonywania obliczeń na tyle dokładny, że pozwoli nam określić wyniki oraz złożoność czasową i pamięciową obliczeń. Z drugiej strony będzie on uproszczony, gdyż pewne kwestie pominiemy, np. kontrolę typów, rozmaite optymalizacje wykonywane przez kompilator, czy sposób realizacji tych elementów języka, których jeszcze nie poznaliśmy. Wyjaśnimy też pewne szczegóły wykonywania obliczeń, które pominęliśmy wcześniej.

Środowisko i ramki

Przedstawiając podstawy Ocamla mówiliśmy o środowisku przypisującym nazwom stałych ich wartości. Dodatkowo takich środowisk może być wiele: środowisko zawierające wszystkie aktualnie globalnie zdefiniowane stałe, środowiska powstające na potrzeby definicji lokalnych i wywołań procedur.

Środowisko jest zrealizowane jako lista jednokierunkowa tzw. ramek. Każda ramka zawiera identyfikator (lub identyfikatory) i ich wartości (lub wskaźniki do takich wartości), oraz wskaźnik do kolejnej ramki tworzącej środowisko. Poszukując w środowisku wartości stałej, przeglądamy kolejne ramki środowiska. Pierwsza ramka, która zawiera nazwę stałej określa jej wartość.

Dalej będziemy utożsamiać środowisko ze wskaźnikiem do pierwszej ramki tworzącej środowisko. Środowisko reprezentowane przez listę ramek bez pierwszej ramki będziemy nazywać środowiskiem otaczającym, a wskaźnik prowadzący z jednej ramki do kolejnej będziemy nazywać wskaźnikiem do środowiska otaczającego.

Przykład [Środowisko]

Definicje globalne

Prowadząc interakcję z kompilatorem pracujemy w kontekście tzw. aktualnego środowiska (globalnego). Każda dodana definicja zmienia to środowisko. Zdefiniowanie nowych wartości powoduje dodanie nowej ramki zawierającej zdefiniowane wartości. Dotychczasowe środowisko staje się środowiskiem otaczającym tej ramki. Utworzona ramka staje się nowym aktualnym środowiskiem (globalnym).

Mechanizm ten pozwala na przesłanianie istniejących w środowisku stałych. Jeśli zdefiniujemy nową stałą o takiej samej nazwie, to będzie ona znajdowała się we wcześniejszej ramce i to właśnie ona będzie znajdowana w aktualnym środowisku. Jednak poprzednio zdefiniowana stała nie jest usuwana ze środowiska. Jak zobaczymy, będzie to miało znaczenie przy obliczaniu procedur odwołujących się do wcześniej zdefiniowanych stałych.

Ramka może zawierać więcej niż jedną stałą, jeżeli w definicji użyjemy spójnika and.

Wartości typów danych

Wartości prostych typów wbudowanych (takie jak int, bool, czy float) są pamiętane w ramkach wprost. Wartości typów złożonych są pamiętane jako wskaźniki do odpowiednich struktur wskaźnikowych reprezentujących te wartości. Dzięki przyjęciu takiej konwencji, reprezentacja dowolnej wartości zajmuje zawsze stałą pamięć. (Dotyczy to zarówno wartości przechowywanych w ramkach, jak i przekazywanych obliczanych wartości wyrażeń.) W rezultacie definiując stałe o złożonych wartościach nie kopiujemy tych wartości, a jedynie wskaźniki do nich. Dodatkowo, ponieważ raz powstałe wartości nie ulegają zmianie, struktury danych reprezentujące różne wartości mogą współdzielić pewne fragmenty.

Wartości różnych złożonych typów danych są generalnie reprezentowane jako rekordy złożone ze wskaźników do wartości składowych:

• Element produktu kartezjańskiego jest reprezentowany jako n-tka wskaźników do tworzących go wartości współrzędnych.
• Rekord -- podobnie jak produkt kartezjański jest reprezentowany jako rekordy złożony z wskaźników do wartości pól.
• Lista to albo pusta lista, albo para: głowa i ogon.
• Warianty są pamiętane jako stała wyznaczająca operator i wskaźnik do argumentu.

Przykład [Wartości złożonych typów danych]

Wartości proceduralne

Na wartość procedury składają sie trzy elementy: nazwy argumentów¹, treść procedury i wskaźnik do ramki reprezentującej środowisko, w którym zdefiniowano procedurę. Pierwsze dwa elementy przekładają się, w trakcie kompilacji, na kod procedury. Natomiast wskaźnik do środowiska, w którym zdefiniowano procedurę może być ustalany w trakcie obliczeń --- dotyczy to np. procedur lokalnych. Reasumując, wartość procedury jest reprezentowana jako para wskaźników: do kodu skompilowanej procedury i do środowiska, w którym procedura została zdefiniowana. W przypadku procedur rekurencyjnych "środowisko, w którym zdefiniowano procedurę" zawiera jej własną definicję.

---

¹Formalnie rzecz biorąc, jest to jeden argument. Dopóki jednak nie wprowadzimy procedur wyższych rzędów, oraz w sytuacjach, gdy takie uproszczenie nie będzie prowadzić do nieporozumień, będziemy dopuszczać obiekty proceduralne z wieloma argumentami.

Aplikacja procedury do argumentów

Obliczenie wartości procedury polega na:

• wyliczeniu wszystkich elementów: procedury i jej argumentów,
• stworzeniu nowej ramki, dla której środowiskiem otaczającym jest środowisko, w którym zdefiniowano procedurę, oraz nazwom parametrów formalnych przyporządkowano wartości argumentów,
• wyliczeniu w takim środowisku wartości wyrażenia stanowiącego treść.

Przykład: Następujące definicje:

let x = 2;;
let square x = x * x;;
let pitagoras x y = square x + square y;;

Obliczenie wyrażenia:

pitagoras x (x + 1) + pitagoras x ((square x) + 1);;
         

będzie przebiegać następująco:

Przykład:

Prześledźmy obliczenie prostego wyrażenia zawierającego $\lambda$-abstrakcję:

Przykład: Wyliczanie procedur rekurencyjnych:

let rec silnia n = 
  if n < 2 then 1 else n * silnia (n - 1);;
silnia 3;;
         

Rekurencja ogonowa

Jeśli wartości zwracane przez wszystkie wywołania rekurencyjne, bez żadnego przetwarzania są przekazywane jako wynik danej procedury, to mówimy o rekurencji ogonowej. W przypadku rekurencji ogonowej, w momencie wywołania rekurencyjnego nie musimy tworzyć nowej ramki --- możemy wykorzystać istniejącą ramkę zmieniając jedynie wartości argumentów.

Przykład: Silnia z akumulatorem:

let rec s a x = 
  if x <= 1 then a else s (a * x) (x - 1);;
let silnia x = s 1 x;;
silnia 3;;
         

Przykład: Liczby Fibonacciego z akumulatorem:

let rec fibpom a b n = 
  if n = 0 then a else fibpom b (a + b) (n - 1);;
let fib n = fibpom 0 1 n;;
fib 5;;
         

Definicje lokalne

Ewaluacja let-in jest analogiczna do rozwinięcia tej formy specjalnej do zastosowania $\lambda$-abstrakcji. Wyrażenie postaci:

let $a$ = $b$ in $c$
       

jest równoważne:

(function $a$ -> $c$) $b$
       

Schemat obliczenia wyrażenia let jest następujący:

• tworzona jest ramka zawierająca definicję symboli lokalnych (otaczającym ją środowiskiem jest aktualne środowisko),
• w tak powstałym środowisku wyliczana jest wartość wyrażenia,
• po czym aktualnym środowiskiem jest to, co poprzednio.

Przykład: Następujący przykład pokazuje sposób realizacji definicji lokalnych.

let f x = 
  let y = x + 2
  in 
    let z = 2 * y
    in 
      x + y + z;;
f 9;;
         

Przykład: Niniejszy przykład ilustruje mniej typową kombinację użycia definicji lokalnych i procedur.

let f = 
  let g x = x - 8
  in
    fun x -> g (2 * x);;
let h x = f (x * x);;
h 5;;
         

Zwróćmy uwagę na procedurę pomocniczą g.Procedura ta jest widoczna tylko wewnątrz procedury f, a jednak jej definicja ma tylko jedną instancję.

Przykład:

let f x y = 
  let
    g a = a * x * y
  in 
    g x + g y;;
f 4 2 - f 2 1;;
         

W tym przykładzie, w każdym wywołaniu procedury fpowstaje osobna instancja procedury lokalnej g.Jest to naturalne zważywszy, że procedura g korzysta z argumentów wywołania procedury f.\begin{center}

Odśmiecanie

Ramka zawierająca lokalne definicje nie musi stawać się od razu zbędna, gdyż mogą na nią wskazywać wartości proceduralne. Zbędne ramki są usuwane w miarę potrzeb --- zbędne to takie, na które nic nie wskazuje lub, do których nie można dotrzeć z aktualnego środowiska poprzez wskaźniki.

Ramki nie tworzą listy, ale drzewo (biorąc pod uwagę wskaźniki na otaczające środowisko). Ramki, które trzeba trzymać w pamięci też nie muszą tworzyć listy, tylko drzewo. Występuje to np. wówczas, gdy wynikiem procedury jest procedura. Zahaczamy tu o procedury wyższych rzędów, ale nie będziemy tego tematu teraz rozwijać.

Przykład: Niniejszy przykład pokazuje sytuację, gdy ramki powstałe w czasie wywołania procedury mogą być potrzebne po jego zakończeniu.

let f x = 
  let g y = x * y
  in g;;
let h = f 6;;
h 7;;

Ramka zawierająca definicję procedury g powstaje w wyniku wywołania f 6, ale jest potrzebna później, do obliczenia h 7.\end{przyklad}

Przykład: Poniższy przykład ilustruje sposób przekazywania wielu argumentów, tak jak to jest realizowane --- po jednym na raz.

let g x =
  let
    a = x * x
  in 
    fun y -> y + a;;
let h x = (g x) x;;
h 6;;