Programowanie funkcyjne/Wyliczanie procesów

Środowisko i ramki.

Podział środowiska na ciąg ramek połączonych wskaźnikami w listę jednokierunkową. Poszukując w środowisku wartości stałej przeglądamy kolejne ramki. Definiowanie nowych wartości powoduje dodanie nowej ramki zawierającej wprowadzane definicje. Można przesłaniać wartości już istniejące w słowniku. Nie powoduje to jednak ich usunięcia ze słownika.

Każda ramka reprezentuje pewne środowisko. Aktualne środowisko jest reprezentowane przez ostatnio dodaną ramkę. Środowisko, do którego prowadzi wskaźnik od danej ramki nazywamy środowiskiem otaczającym.

Model obliczeń

let (globalny) tworzy nową ramkę zawierającą definiowaną wartość(-ci). Dotychczasowe środowisko staje się środowiskiem otaczającym tej ramki. Utworzona ramka staje się aktualnym środowiskiem (globalnym).

TU GRAFIKA 1

Ramka może zawierać więcej niż jedną definicję --- and.

TU GRAFIKA 2

Procedura jako wartość

Na wartość procedury składają sie trzy elementy: nazwy argumentów% \footnote{% 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. }% , 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ę.

Wartości różnych typów danych

Wartości elementarnych typów wbudowanych (takie jak int, czy bool) są pamiętane wprost. Wartości typów złożonych są pamiętane jako wskaźniki do odpowiednich wartości. Dzięki temu wynikiem obliczenia wartości jest zawsze albo wskaźnik, albo wartość, która zajmuje porównywalnie dużo miejsca w pamięci do wskaźnika. W rezultacie definiując stałe o złożonych wartościach nie kopiujemy tych wartości, a jedynie wskaźniki do nich.

Wartości różnych złożonych typów danych są generalnie tworzone 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 wartości tworzących go.
• Rekord --- podobnie do produktu kartezjańskiego.
• Lista to albo pusta lista, albo para: głowa i ogon.
• Warianty są pamiętane jako stała wyznaczająca operator i wskaźnik(i) do argumentu(-ów).

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;;

TU GRAFIKA 3

Obliczenie wyrażenia:

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

będzie przebiegać następująco:

TU GRAFIKA 4

Przykład:

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

TU GRAFIKA 5

Przykład: Wyliczanie procedur rekurencyjnych:

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

TU GRAFIKA 6

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;;
         

TU GRAFIKA 6

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;;
         

TU GRAFIKA 8

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;;
         

TU GRAFIKA 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ę.

TU GRAFIKA 10

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}

TU GRAFIKA 11

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;;

TU GRAFIKA 12

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;;
         

TU GRAFIKA 13