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. Musi istnieć metoda reprezentowania i przechowywania częściowo obliczonych wyrażeń w trakcie wykonania programu.

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

Autor

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