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). \begin{przyklad} %% %% let a = 2;; %% let b = 2 * a;; %% let a = 2 * b + a;; %% let b = "{}ala";; %% \begin{center} \includegraphics{rys-3-1} \end{center} \end{przyklad} Ramka może zawierać więcej niż jedną definicję --- and.\begin{przyklad} \begin{center} \includegraphics{rys-3-2} \end{center} \end{przyklad}

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 \codeline{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ść.

\begin{przyklad} Następujące definicje:

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

będą reprezentowane w środowisku w taki oto sposób: \begin{center} \includegraphics{rys-3-3} \end{center} Obliczenie wyrażenia:

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

będzie przebiegać następująco: \begin{center} \includegraphics{rys-3-4} \end{center} \end{przyklad}

\begin{przyklad} Prześledźmy obliczenie prostego wyrażenia zawierającego $\lambda$-abstrakcję: \begin{center} \includegraphics{rys-3-5} \end{center} \end{przyklad}

\begin{przyklad} Wyliczanie procedur rekurencyjnych:

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

\begin{center} \includegraphics{rys-3-6} \end{center} \end{przyklad}

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.

\begin{przyklad} 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;;

\begin{center} \includegraphics{rys-3-7} \end{center} \end{przyklad}

\begin{przyklad} 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;;

\begin{center} \includegraphics{rys-3-8} \end{center} \end{przyklad}

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.

\begin{przyklad} 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;;

\begin{center} \includegraphics{rys-3-9} \end{center} \end{przyklad}

\begin{przyklad} 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ę. \begin{center} \includegraphics{rys-3-10} \end{center} \end{przyklad}

\begin{przyklad}

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} \includegraphics{rys-3-11} \end{center} \end{przyklad}

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ć. \newpage \begin{przyklad} 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;;

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

\begin{przyklad} 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;;

\begin{center} \includegraphics{rys-3-13} \end{center} \end{przyklad}