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

Kompilacja języków programowania funkcyjnego

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ę, jakie 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 być zmuszeni do tworzenia i przekazywania 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ę transformacji 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 rozwiązaniem 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 od 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 przekazywane bez dodatkowych informacji. Są to 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: ponieważ 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. Przy 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; w tym przykładzie występuje dwukrotnie - przypomnijmy, że

 kwadrat x = x * x

Zauważmy, że zastosowanie tej metody prowadzi do stworzenia raczej 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 bierze 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ę, że jeś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 w 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ą 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 charakterystyczne dla kompilowanego języka.

Leniwe obliczenia

Zauważmy, że opisana powyżej maszyna nie realizuje w pełni paradygmatu leniwych obliczeń: co prawda argumenty są obliczane dopiero kiedy potrzeba, mogą jednak być obliczne wielokrotnie. Aby temu zaradzić (i zwiększyć sprawność maszyny) musimy wprowadzić jeszcze dwie operacje (zamiast SLIDE):

• UPDATE n --- zastąp wierzchołek grafu wskazywany przez n+1-szy element stosu przez wierzchołek na szczycie stosu
• POP n --- zdejmij n elementów ze stosu

W tej wersji epilog funkcji n-argumentowej wygląda następująco

 UPDATE n
 POP n
 UNWIND

Inne maszyny

Zauważmy, że G-maszyna poswięca dużo czasu na operację rozwijania grzbietu. Pojedyncza instrukcja UNWIND reprezentuje w istocie dość złożoną operację. Stąd niektóre nowsze maszyny wirtualne (takie jak Three Instruction Machine (TIM) [Fairbairn] czy Spineless Tagless G-machine (STG) [Peyton Jones] zastępują operację rozwijania grzbietu przez efektywniejsze (choć bardziej skomplikowane) mechanizmy.

Transformacje programów

Lambda-lifting

Lambda-lifting jest transformacją programu do postaci superkombinatorów czyli funkcji, które nie korzystają za zmiennych nielokalnych, a jedynie ze swoich argumentów. Możemy to osiągnąć używając dwóch operacji:

• przydawanie funkcji dodatkowych argumentów przekazujących wartości zmiennych nielokalnych;
• podnoszenie (lifting) funkcji lokalnych na poziom globalny.

Na przykład funkcja

 f xs y = map (\z -> h y z) xs

Zostanie przetransformowana do zbioru superkombinatorów:

 f xs y = map g xs
 g z y = h y z

gdzie g jest nową nazwą.

Transformacja ta realizowana jest następująco:

• dla każdej funkcji lokalnej obliczamy jej zbiór zmiennych wolnych (nielokalnych);
• tworzymy dla niej nowy superkombinator mający jako argumenty pierwotne argumenty funkcji oraz jej zmienne nielokalne;
• wystąpienie tej funkcji lokalnej zastępujemy odpowiednim zastosowaniem utworzonego superkombinatora.

Autor

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