|
|
| (Nie pokazano 9 wersji utworzonych przez jednego użytkownika) |
| Linia 1: |
Linia 1: |
| ==Środowisko i ramki.==
| | [[Programowanie funkcyjne/Model obliczeń]] |
| 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ń==
| |
| <tt>let</tt>(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ę --- <tt>and</tt>.\begin{przyklad}
| |
| <!--% \begin{code}
| |
| -->
| |
| <!--% let a = 2 and b = 4;;\\
| |
| -->
| |
| <!--% let a = 2 * b and b = 4 * a;;\\
| |
| -->
| |
| <!--% a;;\\
| |
| -->
| |
| <!--% b;;
| |
| -->
| |
| <!--% \end{code}
| |
| -->
| |
| \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 <tt>bool</tt>)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
| |
| <math>\lambda</math>-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 <tt>let-in</tt> jest analogiczna do rozwinięcia tej formy specjalnej do zastosowania <math>\lambda</math>-abstrakcji.
| |
| Wyrażenie postaci:
| |
|
| |
| let <math>a</math> = <math>b</math> '''in''' <math>c</math>
| |
|
| |
| jest równoważne:
| |
|
| |
| (function <math>a</math> -> <math>c</math>) <math>b</math>
| |
|
| |
| Schemat obliczenia wyrażenia <tt>let</tt> 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ą <tt>g</tt>.Procedura ta jest widoczna tylko wewnątrz procedury
| |
| <tt>f</tt>, 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 <tt>f</tt>powstaje osobna instancja procedury lokalnej <tt>g</tt>.Jest to naturalne zważywszy, że procedura <tt>g</tt> korzysta z argumentów wywołania procedury <tt>f</tt>.\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 <tt>g</tt> powstaje w wyniku wywołania <tt>f 6</tt>, ale jest potrzebna później, do obliczenia <tt>h 7</tt>.\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}
| |
