Metody realizacji języków programowania/MRJP Wykład 12

Wprowadzenie

Specyficzne cechy języków funkcyjnych

Języki funkcyjne posiadają pewne specyficzne cechy, które sprawiają, że metody ich implementacji różnią się znacząco od języków imperatywnych.

Funkcje są pełnoprawnymi obywatelami (ang. first-class citizens):

1. Mogą być argumentami funkcji

2. Mogą być wynikami funkcji

3. Mogą być częściowo aplikowane

4. Mogą być tworzone anonimowo

Spójrzmy na prosty przykład ilustrujący te cechy:

 map :: (a->b) -> [a] -> [b]
 map f [] = []
 map f (x:xs) = (f x):(map f xs)
 
 increaseAll :: [Int] -> [Int]
 increaseAll = map (\x->x+1)

Ponadto: 5. Obliczenia mogą być leniwe, tzn. wartość argumentu jest wyliczana nie w momencie wywołania funkcji, ale w momencie jego użycia.

6. Nie ma przypisania (tylko obliczanie wartości wyrażeń); w tzw. czystych językach funkcyjnych zasadniczo nie ma w ogóle efektów ubocznych;

Funkcja map bierze jako argumenty funkcję typu (a->b) i listę elementów typu a, dając w wyniku listę elementów typu b. Zauważmy jednak, że typ funkcji map można odczytać inaczej: argumentem jest funkcja typu (a->b), zaś wynikiem...funkcja typu [a]->[b].

Funkcja increaseAll korzysta z tego drugiego odczytania, stosując funkcję map z jednym tylko argumentem, którym jest stworzona ad hoc, anonimowa funkcja dodająca jeden do swego argumentu.

Zastanówmy się jaki powyższe cechy mogą mieć wpływ na implementację języka.

1. Funkcje jako argumenty funkcji występują już w językach imperatywnych. Możemy jednak musieć tworzyć i przekazywać domknięcia funkcji dla dostępu do zmiennych nielokalnych.

2. Jeśli funkcja może dawać w wyniku funkcję, dostęp do zmiennych nielokalnych jest problematyczny. Nie możemy skorzystać z klasycznego stosu rekordów aktywacji jak w językach imperatywnych. Domknięcie funkcji musi przechowywać wartości wszystkich zmiennych nielokalnych, z których ta funkcja korzysta.

Możemy jednak przekształcić program do takiej (równoważnej) postaci, aby żadna funkcja nie korzystała ze zmiennych nielokalnych. Transformację tę przedyskutujemy nieco później.

3-5. W trakcie wykonania programu musimy przechowywać struktury (grafy) reprezentujące nieobliczone (lub częściowo tylko obliczone) wyrażenia. Wykonanie programu będzie zatem polegało na konstruowaniu i redukowaniu takich grafów. Jak zobaczymy za chwilę podejście takie jest wygodne także z innych powodów.

6. Brak efektów ubocznych umożliwia stosowanie na szeroką skalę transformację programów do równoważnej, zle wygodniejszej lub efektywniejszej postaci.

Domknięcia i superkombinatory

Problem zmiennych nielokalnych nie jest nowy; występuje w każdym języku z blokową strukturą widoczności. Standardowym rozwiazaniem jest reprezentowanie wartości funkcyjnej przez tzw. domknięcie. Jest to wartość, z której można poprawnie utworzyć wcielenie danej funkcji wszędzie, gdzie może to być potrzebne. Co powinno zawierać takie domknięcie --- zależy od konkretnego języka a nawet implementacji.

W Pascalu wystarczy gdy domknięciem jest para (adres funkcji, SL), gdzie SL jest wskaźnikiem do ramki stosu procedury nadrzêdnej. Mamy bowiem pewność, że nie zniknie ona przedwcześnie ze stosu, gdyż gwarantuje to konstrukcja i reguły widoczności języka Pascal.

Kiedy jednak wartości funkcyjne mogą być nie tylko argumentami, ale i wynikami funkcji, własność ta nie może być zagwarantowana. Za domknięcie przyjmuje się wtedy zwykle informację o wartościach wszystkich zmiennych wolnych. Ich ilość (a zatem rozmiar domknięcia) można wyznaczyc statycznie (tj. w czasie kompilacji).

Zauważmy, że jednak pewne funkcje możemy bezpiecznie przekazywaæ bez dodatkowych informacji, a mianowicie te, które ... nie mają zmiennych wolnych! Na tej obserwacji bazuje nastêpująca metoda implementacji języków funkcyjnych: transformujemy program do postaci, w której żadna funkcja nie ma zmiennych wolnych. Funkcje takie nazywa się superkombinatorami, a proces transformacji lambda-liftingiem.

Na razie będziemy zakładać, że program dany jest w postaci ciągu definicji superkombinatorów. Domknięciami i lambda-liftingiem zajmiemy się w dalszej części wykładu.

Grafy wyrażeń

Graf wyrażenia jest uogólnieniem dobrze znanego pojęcia drzewa wyrażenia. Rozważmy na przykład funkcję:

 kwadrat x = x * x

Możemy ją przedstawić w postaci drzewa

   *
  / \
 x   x

Albo w postaci grafu:

   *
  / \
  \ /
   x

Ponieważ jednak w języku funkcyjnym wyrażenie $x*x$ oznacza zastosowanie funkcji * do argumentów x oraz x, dokładniejszą będzie reprezentacja:

      @   
     / \
    @   \
   / \___x
  *

gdzie symbol @ oznacza aplikację funkcji.

Uwaga: jako, że reprezentowane wyrażenia mogą być rekurencyjne, graf wyrażenia nie musi być acykliczny.

Wykonanie programu funkcyjnego polega na obliczeniu wartości wyrażenia poprzez kolejne redukcje. Przye reprezentacji grafowej redukcje te dokonywane są na grafach wyrażeń. Jako przykład rozważmy poniższy program funkcyjny:

 kwadrat x = x * x ;
 main = kwadrat (kwadrat 3)

Składa się on z dwóch superkombinatorów: square oraz main. Jego wykonanie polega na obliczeniu wartości superkombinatora main. Redukcje będą przebiegać następująco (znak ! oznacza wierzchołek grafu, w którym wykonujemy redukcję)

   main      ->     @
                   / \
            kwadrat   @
                     / \
              kwadrat   3

        @!        ->          @!
       / \                   / \
kwadrat   @                 @   \
         / \               / \___@
  kwadrat   3             *     / \
                          kwadrat  3

    @        ->          @
   / \                  / \
  @   \                @   \
 / \___@!             / \___@
*     / \            *     / \
kwadrat  3                 @  \
                          / \__3
                         *

     @          ->          @
    / \                    / \
   @   \                  @   \
  / \___@!               / \___9
 *     / \              *
      @   \
     / \___3
    *

    @   -> 81
   / \
  @   \
 / \___9
*

Maszyny wirtualne

Metoda szablonów

Metoda szablonów, cho rzadko stosowana bezpośrednio (z uwagi na swą niską efektywność) leży u podstaw wielu metod implementacji języków funkcyjnych. Spróbujmy nakreślić jej podstawowe założenia:

• dla każdej funkcji tworzymy jej szablon (graf ciała funkcji, z wolnymi "gniazdkami" dla argumentów)
• w momencie wywołania funkcji (tj. redukcji aplikacji) tworzymy wcielenie danego szablonu z parametrami faktycznymi "włączonymi" w odpowiednie gniazdka argumentów szablonu.

Na przykład dla funkcji main szablon będzie wyglądał następująco:

        @
       / \     
 kwadrat  @      
         / \       
   kwadrat  3

(funkcja main nie ma argumentów)

Zaś dla funkcji kwadrat

     @
    / \
 ARG1 ARG1

gdzie ARG1 oznacza gniazdko dla pierwszego argumentu; tym przykładzie występuje dwukrotnie - przypomnijmy, że

 kwadrat x = x * x

Zauważmy, że zastosowanie tej metody prowadzi do stworzenia raczje interpretera niż kompilatora: nie generujemy kodu w sansie ciągu instrukcji, a jedynie grafy funkcji. Cały proces redukcji jest realizowany przez system wykonawczy. Stąd bierrze się wspomniana nieefektywność metody szablonów.

Można usprawnić ten proces, generując kod, który zbuduje grtaf dla funkcji. Na tym pomyśle oparta jest G-maszyna autorstwa Augustssona i Johnsona, o której za chwilę. Najpierw jednak przedyskutujemy kwestię znajdowania następnego redeksu.

Znajdowanie następnego redeksu

Istnieje wiele różnych strategii wyboru następnego redeksu i ich omawianie wykracza poza ramy tego wykładu. Tutaj zajmiemy się jedynie strategią lewostronną, która ma tę ważną cechę, żejeśli tylko istnieje jakakolwiek kolejność redukcji, która doprowadzi do obliczenia wyrażenia, to strategia lewostronna będzie miała taki sam efekt.

Strategia lewostronna polega na znalezieniu redeksu leżącego "najbardziej na lewo" w drzewie wyrażenia (tu dla uproszczenia na chwilę zapominamy o reprezentacji grafowej i wracamy do reprezentacji drzewiastej, tym niemniej metoda przenosi się łatwo na grafy). Możemy ją zrealizować następująco:

1. Zaczynając od korzenia, podążamy lewą gałęzią drzewa aż do napotkania superkombinatora. Zwykle trakcie tego procesu zapamiętujemy odwiedzone wierzchołki na stosie. Proces ten nazywany jest rozwijaniem grzbietu, a jego ślad na stosie grzbietem.

2. Sprawdzamy ilość argumentu superkombinatora i cofamy się o taką ilość kroków w górę drzewa. Napotkany węzeł jest następnym redeksem dla strategii lewostronnej.

G-maszyna

G-maszyna (czyli maszyna grafowa) składa się ze sterty, przechowującej grafy, oraz stosu, na którym przechowywane są wskaźniki do sterty oraz stałe. W momencie wywołania funkcji na stosie leży grzbiet. Kod funkcji buduje graf dla wcielenia funkcji i dokonuje kolejnej redukcji.

Sercem G-maszyny są tedy instrukcje związane z budowaniem grafów i ich redukcją. Do tej kategorii należą m.in. instrukcje

• PUSH n --- połóż na wierzchołku stosu n-ty (względem bieżącego wierzchołka stosu) argument

• PUSHGLOBAL f --- połóż na stosie adres funkcji f

• PUSHINT n --- połóż na stosie stałą całkowitą n

• MKAP --- zbuduj węzeł aplikacji (używając dwóch pierwszych elementów stosu)

• SLIDE n --- usuń n elementów spod wierzchołka stosu. Jeśli stos przed tą operacją zawiera elementy

  A0 A1 ... An B C ...

to po tej operacji będzie zawierał

  A0 B C ...

• UNWIND --- znajdź następny redeks (rozwijając grzbiet) i zredukuj go

Kod dla naszej przykładowej funkcji main będzie zatem wyglądał następująco:

 PUSHINT 3  
 PUSHGLOBAL kwadrat
 MKAP
 PUSHGLOBAL kwadrat
 MKAP
 SLIDE 1
 UNWIND

Zaś dla funkcji kwadrat

 PUSH 1 (ARG1)
 PUSH 2 (też ARG1, ale stos wzrósł o 1)
 PUSHGLOBAL *
 MKAP
 SLIDE 2
 UNWIND

Zauważmy, że graf budowany przez powyższy kod nie jest drzewem - zawiera dwie krawędzie prowadzące do argumentu funkcji.

Dla funkcji n-argumentowej schemat generacji kodu wygląda następująco:

• instrukcje budujące graf (łatwo je wygenerować obchodząc szablon funkcji w porządku postfiksowym)
• SLIDE n+1 (usuwanie ze stosu starego grzbietu przy zachowaniu wskaźnika do nowozbudowanego grafu)
• UNWIND (rozwinięcie grzbietu i redukcja znalezionego redeksu)

Poza podstawowymi instrukcjami G-maszyna posiada instrukcje realizujące operacje pierwotne (np. arytmetyczne) oraz inne operacje charakterystycznew dla kompilowanego języka.

Autor

Marcin Benke, Instytut Informatyki UW; e-mail: ben@mimuw.edu.pl