|
|
| (Nie pokazano 3 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).
| |
| | |
| [[grafika:pf-rys-3-1.gif||center]] | |
| | |
| Ramka może zawierać więcej niż jedną definicję --- <tt>and</tt>.
| |
| | |
| [[grafika:pf-rys-3-2.gif||center]]
| |
| | |
| ===Procedura jako wartość===
| |
| | |
| 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.
| |
| | |
| ===Wartości różnych typów danych===
| |
| | |
| Wartości elementarnych typów wbudowanych (takie jak <tt>int</tt>, 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ść.
| |
| | |
| Przykład:
| |
| Następujące definicje:
| |
|
| |
| '''let''' x = 2;;
| |
| '''let''' square x = x * x;;
| |
| '''let''' pitagoras x y = square x + square y;;
| |
| | |
| [[grafika:pf-rys-3-3.gif||center]]
| |
|
| |
| Obliczenie wyrażenia:
| |
|
| |
| pitagoras x (x + 1) + pitagoras x ((square x) + 1);;
| |
|
| |
| będzie przebiegać następująco:
| |
| | |
| [[grafika:pf-rys-3-4.gif||center]]
| |
|
| |
| Przykład:
| |
| | |
| Prześledźmy obliczenie prostego wyrażenia zawierającego
| |
| <math>\lambda</math>-abstrakcję:
| |
| | |
| [[grafika:pf-rys-3-5.gif||center]]
| |
|
| |
| Przykład:
| |
| Wyliczanie procedur rekurencyjnych:
| |
|
| |
| let '''rec''' silnia n =
| |
| '''if''' n < 2 '''then''' 1 '''else''' n * silnia (n - 1);;
| |
| silnia 3;;
| |
|
| |
| [[grafika:pf-rys-3-6.gif||center]]
| |
| | |
| ===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;;
| |
|
| |
| [[grafika:pf-rys-3-7.gif||center]]
| |
| | |
| 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;;
| |
|
| |
| [[grafika:pf-rys-3-8.gif||center]]
| |
| | |
| ===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.
| |
| | |
| 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;;
| |
|
| |
| [[grafika:pf-rys-3-9.gif||center]]
| |
| | |
| 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ą <tt>g</tt>.Procedura ta jest widoczna tylko wewnątrz procedury <tt>f</tt>, a jednak jej definicja ma tylko jedną instancję.
| |
| | |
| [[grafika:pf-rys-3-10.gif||center]]
| |
| | |
| 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 <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}
| |
| | |
| [[grafika:pf-rys-3-11.gif||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;;
| |
| | |
| [[grafika:pf-rys-3-12.gif||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}
| |
|
| |
| 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;;
| |
|
| |
| [[grafika:pf-rys-3-13.gif||center]]
| |
