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 wiêc 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      ->       @
                   / \
             square   @
                     / \
               square   3

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

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

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

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

Autor

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