Paradygmaty programowania/Wykład 6: Programowanie funkcyjne — przegląd

From Studia Informatyczne

Spis treści

Wstęp

Zacznijmy od uzasadnienia, dlaczego zajmujemy się językami funkcyjnymi. Otóż języki imperatywne, a w dużym stopniu także obiektowe, są bardzo silnie związane z architekturą von Neumanna. Należy tu przede wszystkim wymienić pojęcie stanu maszyny, któremu w językach tych odpowiadają zmienne i dane w obiektach. Niektórzy sądzą, że związek z architekturą von Neumanna narzuca niepotrzebne ograniczenia na proces tworzenia oprogramowania. W zamian za to można przyjąć paradygmat oparty na pojęciu funkcji w znaczeniu takim, jakie od lat przyjmuje się w matematyce.

Czy języki funkcyjne istnieją...? Tak, jak najbardziej, choć w środowisku komercyjnych twórców oprogramowania nie są zbytnio rozpowszechnione. Istnieje przykładowo Lisp. Jest to jeden z języków funkcyjnych, który doczekał się sporej popularności. Uproszczonym i uporządkowanym dialektem Lispu jest Scheme. W środowiskach akademickich znane i cenione są także np. języki ML wraz z pochodnymi i Haskell. Słyną m.in. ze swojego silnego typowania. Oprócz tego dość silną pozycję mają pewne języki „niszowe”, np. Erlang (w telekomunikacji) i K (w obliczeniach finansowych).

Funkcje matematyczne i funkcje-podprogramy

Alonso Church (1903-1995)Zobacz biografię
Enlarge
Alonso Church (1903-1995)
Zobacz biografię

Czym różnią się funkcje matematyczne od funkcji-podprogramów? Nie ma pamięci, a zatem nie ma zmiennych modelujących komórki pamięci. Nie ma też więc „stanu” funkcji. A więc — nie ma efektów ubocznych... Nie ma ciągów instrukcji i iteracji, a jedynie rekurencja i wyrażenia warunkowe. Innymi słowy, funkcja (w sensie matematycznym) definiuje wartość, ale nie określa ciągu działań na wartościach w pamięci, które mogłyby ją wytworzyć. Parametr funkcji reprezentuje dowolny element z dziedziny, lecz w trakcie obliczania jest ustalony (nota bene, co to znaczy „podczas obliczania”?).

Ważnym elementem podstaw matematycznych dla programowania funkcyjnego jest rachunek lambda. Rachunek ów, wymyślony przez Alonsa Churcha w roku 1941, pozwala m.in. zdefiniować funkcję bez nadawania jej nazwy. W klasycznym zapisie matematycznym definiując funkcję, nadajemy jej — z konieczności — nazwę, np. piszemy f(n) = n f(n - 1). Natomiast wyrażenie lambda (mówimy też „\lambda-wyrażenie”) utożsamiamy z samą funkcją, np. \lambda x.x^2 to funkcja obliczająca kwadrat danego parametru. Ogólnie, \lambda-wyrażenie zawiera symbol \lambda, parametry funkcji, kropkę i wyrażenie opisujące wartość funkcji; niekiedy zamiast kropki widuje się nawiasy obejmujące parametry, np. \lambda(x)x^2. Wyrażenie takie można zastosować („zaaplikować”) do parametru, pisząc parametr za owym wyrażeniem, np. (\lambda x.x^2)(3) = 3^2 = 9.

Funkcjonał to funkcja, dla której parametrami lub której wynikiem są inne funkcje. Funkcjonały zwane są także funkcjami wyższego rzędu. Przykłady:

  • Składanie funkcji (◦).
  • Operator aplikacji zbiorowej (zwany też apply-to-all lub mapcar), który bierze funkcję oraz listę „zwykłych” parametrów i stosuje podaną funkcję do poszczególnych parametrów, zwracając listę wyników.

Podstawy języków funkcyjnych

Nakreślmy cel konstruowania języków funkcyjnych:

  • Chcemy naśladować funkcje matematyczne.
  • (Czysty) język funkcyjny nie ma zmiennych — programista nie musi się więc martwić o pamięć.
  • Konstrukcje iteracyjne (np. pętla while) nie są możliwe bez zmiennych, przeto w zamian używać trzeba rekurencji (w zamian?!).
  • Wykonanie programu funkcyjnego nie ma stanu w sensie semantyki operacyjnej lub denotacyjnej.
  • Dla tych samych parametrów wykonanie funkcji zawsze daje ten samy wynik. Nazywamy to przeźroczystością odniesień.
  • To nam upraszcza semantykę.

Co powinno być w języku funkcyjnym?

  • Zbiór funkcji pierwotnych.
  • Zbiór funkcjonałów pozwalających konstruować złożone funkcje z funkcji pierwotnych.
  • Operacja aplikowania funkcji do argumentu.
  • Pewne struktury do reprezentowania parametrów i obliczonych wyników.

Dlaczego języki imperatywne i obiektowe nie nadają się do programowania funkcyjnego?

  • Zwykle funkcje nie mogą zwracać funkcji.
  • Możliwe są efekty uboczne.
  • Niektóre języki ewoluują jednak w stronę cech funkcyjnych. C# w wersji 3.0 (z roku 2006) pozwala np. na używanie \lambda-wyrażeń i stosuje dość zaawansowane nadawanie typów wyrażeniom.

Przegląd języków funkcyjnych

Lisp

Lisp to najstarszy język funkcyjny. Prace projektowe rozpoczęły się pod koniec lat 50-tych XX wieku. Pierwotnie jego nazwę pisano dużymi literami: LISP. Ewoluował, choć obecne koncepcje języków funkcyjnych są nieco inne.

Obiekty danych

  • W oryginalnym Lispie są tylko dwa możliwe obiekty: atomy i listy.
  • Nie są to typy w sensie języka imperatywnego.
  • Atomy to symbole (w postaci identyfikatorów) lub stałe liczbowe.
  • Listy określa się przez wyszczególnienie elementów w nawiasach.
  • Listy mogą być zagnieżdżane.
  • Listę pustą zapisuje się jako ( ).

S-wyrażenia

  • Wywołania funkcji zapisywane są w Odwrotnej Notacji Polskiej, w postaci
     (nazwaFunkcji arg_{1} \ldots arg_{n}).
  • Definicje funkcji zapisuje się w notacji lambda, w postaci
     (nazwaFunkcji (LAMBDA (arg_{1} \ldots arg_{n}) wyrażenie)).
  • Pierwotnie S-wyrażeniami nazywano określone w powyższy sposób funkcje. Później nazwą tą objęto wszystkie struktury w Lispie — i dane, i kod.
  • Podkreślmy ważną cechę Lispu: dane (listy) i kod (wywołania funkcji) mają taką samą postać.
  • Daje to m.in. możliwość dynamicznego tworzenia kodu.

Funkcja EVAL

  • Istotnym elementem Lispu jest funkcja uniwersalna, tzn. funkcja, która może policzyć każdą inną funkcję.
  • Ma ona również postać wyrażenia.
  • Implementacja funkcji EVAL może służyć (i służyła) za interpreter Lispu.

Dynamiczne ustalanie zakresu

  • Lisp wyznacza zakres widoczności dynamicznie, tzn. funkcje są obliczane w środowisku funkcji wywołujących.
  • Niektórzy podejrzewają, że mogło to być dzieło przypadku...
  • Współczesne odmiany Lispu stosują zakresy statyczne lub pozwalają na wybór.

Scheme

Scheme jest odmianą Lispu. Pojawił się w połowie lat 70-tych XX wieku. Jest niewielki w porównaniu z oryginalnym Lispem. Stosuje zakresy statyczne. Funkcje mogą być wartościami wyrażeń i elementami list; mogą być przekazywane jako parametry.

Interpreter Scheme’u

  • Ma postać nieskończonej pętli, która czyta wyrażenie, interpretuje je i wyświetla wynik.
  • Wyrażenia są interpretowane przez funkcję EVAL.

Pierwotne funkcje liczbowe

  • Są wśród nich podstawowe działania arytmetyczne.
  • Biorą dowolną liczbę argumentów, np. „+” dodaje wszystkie argumenty do siebie, a „–” od pierwszego argumentu odejmuje pozostałe.
  • Przy wywołaniu bez argumentów zwracają odpowiedni element neutralny (0 dla dodawania, 1 dla mnożenia itp.).
  • Oprócz tego są: ABS (wartość bezwzględna), SQRT (pierwiastkowanie), REMAINDER (reszta z dzielenia), MIN, MAX.

Definiowanie funkcji

  • Program to zbiór definicji funkcji.
  • Można używać funkcji bez nazw, np. (LAMBDA (x) (* x x)).
  • Zatem poniższe wywołanie wyświetli wynik 36:
     ((LAMBDA (x) (* x x)) 6)
  • W powyższym λ-wyrażeniu „x” jest zmienną związaną.
  • ożna związać nazwę z wartością lub z λ-wyrażeniem za pomocą specjalnej funkcji DEFINE.
    • W pierwszym przypadku powstają nazwane stałe (nie zmienne!), np. (DEFINE pi 3.1415926).
    • W drugim przypadku, jako parametry potrzebne są dwie listy: prototyp funkcji i wyrażenie (lub wyrażenia), z którymi nazwa jest wiązana. W tym przypadku pomija się słowo LAMBDA, np.
     (DEFINE (square x) (* x x))
  • Parametry przekazywane są przez wartość.

Funkcje do obsługi wyjścia

  • Typowy sposób wyprowadzenia wyników programu to po prostu wyjście z interpretera, czyli wynik aplikacji funkcji EVAL do funkcji w programie.
  • Jest też jednak imperatywna funkcja wyjściowa, która wyświetla podane wyrażenie (jest to właściwie jej efekt uboczny...) — (DISPLAY wyrażenie).
  • Druga funkcja imperatywna to (NEWLINE).

Predykaty działające na liczbach

  • Dostępne są predykaty: =, <>, >, <, >=, <=.
  • EVEN? sprawdza, czy podana wartość liczbowa jest parzysta.
  • ODD? sprawdza, czy nieparzysta.
  • ZERO? sprawdza, czy wartość jest zerem.
  • NEGETIVE? sprawdza, czy podana wartość jest ujemna.
  • Wartości logiczne są zapisywane jako #F i #T.
  • Lista pusta () interpretowana jest jako #F, a dowolna lista niepusta — jako #T.

Struktury sterujące

  • Scheme ma dwie struktury służące do sterowania.
  • Wybór „jeden z dwóch” zapisuje się w postaci:
     (IF predykat  wyrażenieT  wyrażenieF)
  • Wybór „jeden z wielu” zapisuje się w postaci:
     (COND
     (predykat1  wyrażenie1)
     (predykat2  wyrażenie2)
     ...
     (predykatn  wyrażenien)
     (ELSE  wyrażenieE))

Przykład

  • Definicja funkcji obliczającej silnię
     (DEFINE (silnia n) (IF (= n 0) 1 (* n (silnia (– n 1)))))


Funkcje listowe

  • QUOTE zwraca swój parametr bez jakichkolwiek zmian (czyli bez obliczania go jako funkcji); w tej roli można też użyć jednego apostrofu, np. (QUOTE (A B C)) to to samo, co ‘(A B C), czyli lista (A B C).
  • Funkcja ta jest potrzebna, gdy chcemy np. potraktować listę jako „czyste” dane, a nie jako wywołanie funkcji z parametrami. Użycie nie zacytowanej listy (A B C) skutkowałoby próbą policzenia funkcji A na argumentach B i C.
  • CAR zwraca pierwszy element (głowę) podanej listy, np. (CAR ‘(A B C)) zwraca A.
  • Wywołanie CAR dla pustej listy lub atomu jest błędem.
  • CDR zwraca część listy pozostałą po usunięciu głowy (ogon), np. (CDR ‘(A B C)) zwraca (B C).
  • CONS tworzy listę z podanej głowy i ogona, tzn. wstawia pierwszy parametr jako nową głowę w liście będącej drugim parametrem, np.
    • (CONS ‘A ‘(B C)) zwraca (A B C).
    • (CONS ‘(A B) ‘(C D)) zwraca ((A B) C D).
  • CONS zaaplikowane do dwóch atomów zwraca tzw. parę z kropką, np. (CONS ‘A ‘B) zwraca (A . B).
  • Nie jest to właściwie element języka, lecz pewien przypadkowy efekt, wynikający ze sposobu implementacji list w pierwszych interpreterach Lispu.
  • Funkcja LIST tworzy listę z dowolnej liczby parametrów. Jest to skrótowa forma o takim samym znaczeniu jak zagnieżdżone wywołania CONS.

Inne predykaty

  • EQ? zwraca #T, jeśli obydwa parametry są atomami i są równe.
  • LIST? zwraca #T, jeśli parametr jest listą.
  • NULL? zwraca #T, jeśli parametr jest listą pustą.

Przykład

  • Funkcja sprawdzająca, czy atom (podany jak pierwszy parametr) jest elementem listy (podanej jako drugi parametr).
     (DEFINE (member atm lst)
       (COND
         ((NULL? lst) ‘())
         ((EQ? atm (CAR lst)) #T)
         (ELSE (member atm (CDR lst)))
       )
     )

Składanie funkcji

  • Był to jedyny pierwotny funkcjonał w pierwotnym Lispie.
  • Scheme także go zawiera.
  • Działa tak:
    • Wszelkie listy (nie cytowane za pomocą QUOTE bądź apostrofu) są traktowane jako wywołania funkcji.
    • Najpierw są wyliczane ich parametry.
    • Odnosi się to rekurencyjnie do list zagnieżdżonych w listach.
  • Jest to w istocie właśnie składanie funkcji.
  • Przykład: (CDR (CDR ‘(A B C))) zwraca (C).

Przykład

  • Operator aplikacji zbiorowej można zdefiniować następująco:
     (DEFINE (mapcar fun lst)
       (COND
       ((NULL? lst) ‘())
       (ELSE (CONS (fun (CAR lst)) (mapcar fun (CDR lst))))
       )
     )

Funkcje tworzące kod

  • Program i dane w Schemie mają taką samą strukturę.
  • To powoduje, że można z łatwością dynamicznie „budować” kod.

Przykład

  • Przypuśćmy, że mamy listę atomów liczbowych i chcemy policzyć ich sumę.
  • Zauważmy, że operatora + nie można zaaplikować bezpośrednio, gdyż wymaga on jako parametrów atomów, a nie listy.
  • Mamy dwie istotnie różne możliwości.
  • Pierwsza to napisanie funkcji, która doda po kolei wszystkie atomy:
     (DEFINE (sumator lst)
       (COND
         ((NULL? lst) 0)
         (ELSE (+ (CAR lst) (sumator (CDR lst))))
       )
     )
  • Druga to zbudowanie odpowiedniego wywołania dla operatora + za pomocą CONS i policzenie go poprzez wywołanie funkcji EVAL:
     (DEFINE (sumator lst)
       (COND
         ((NULL? lst) 0)
         (ELSE (EVAL (CONS ‘+ lst)))
       )
     )

Wiązanie nazwy z wartością

  • Służy do tego funkcja LET.
  • Składnia wywołania jest następująca:
     (LET
       (
       (nazwa1 wyrażenie1)
       (nazwa2 wyrażenie2)
       ...
       (nazwan wyrażenien)
       )
       ciało
     )
  • Wywołanie powoduje związanie podanych nazw z odpowiednimi wyrażeniami oraz obliczenie ciała.
  • Funkcja LET jest przydatna jako pewien sposób modularyzacji obliczeń.
  • Zauważmy, że ze względu na założony brak efektów ubocznych, nie ma znaczenia, czy jakieś obliczenie wykonamy raz, czy dwa razy. Zatem użycie LET i następne wielokrotne wykorzystanie związanych nazw nie wpływa na wynik obliczeń.


Silnia w językach funkcyjnych

Przykład

  • Funkcja obliczająca iloraz sum dwóch list.
  • Zwraca 0, jeśli druga suma (dzielnik) jest zerem.
     (DEFINE (iloraz x y)
       (LET
         ((licznik (sumator x))(mianownik (sumator y)))
         (IF (ZERO? mianownik) 0 (/ licznik mianownik))
       )
     )

ML

ML to język, który w swoim czasie był typowym akademickim przykładem języka funkcyjnego. Stosuje zakresy statyczne. Jest silnie typowany, bez niejawnych konwersji, za to stosuje niejawne nadawanie typów. Wyrażenia arytmetyczne zapisywane w tradycyjnej postaci infiksowej. Zawiera obsługę wyjątków.

Funkcje

  • Deklaracje mają postać fun nazwa (parametry) = ciało;
  • Przykładowo:
     fun square (x: int): int = x * x;
  • Funkcje zawierające działania arytmetyczne nie mogą być polimorficzne.
  • Funkcje zawierające tylko operacje na listach, operatory n-tek i porównania (= oraz <>) mogą być polimorficzne.
  • Można stosować konstrukcję „if-then-else”, np.
     fun fact(n: int): int = if n = 0 then 1 else n * fact(n–1);
  • Alternatywą jest często dopasowywanie do wzorca, np.
     fun fact(0)           = 1
       | fact(n: int): int = n * fact(n–1);

Listy

  • Listy zapisywane są w nawiasach kwadratowych, np. [3, 2, 7].
  • Lista pusta zapisywana jest jako [] lub nil.
  • Konstruktor listowy (odpowiednik CONS) to ::, np. 1 :: [3, 2, 7] daje [1, 3, 2, 7].
  • Elementy listy muszą być tego samego typu.
  • Funkcje wydzielające głowę i ogon (odpowiedniki CAR i CDR) to hd oraz tl.
  • Operator :: może być używany w dopasowaniach do wzorca, np.
     fun length([])     = 0
       | length(h :: t) = 1 + length(t);

Przykład

  • Funkcja łącząca dwie listy.
  • Zrealizowana jako rekurencyjna, z dopasowywaniem za pomocą operatora ::
     fun append([], lst)     = lst
       | append(h :: t, lst) = h :: append(t, lst);

Haskell

Haskell Brooks Curry (1900-1982)Zobacz biografię
Enlarge
Haskell Brooks Curry (1900-1982)
Zobacz biografię

Podobnie jak ML, stosuje zakresy statyczne. Jest silnie typowany. Stosuje obliczanie leniwe, tzn. nie oblicza podwyrażeń, dopóki nie jest to konieczne. Zawiera ciekawe operacje „listotwórcze”. Czysto funkcyjny, naprawdę bez efektów ubocznych.

Funkcje

  • Definicje funkcji są postaci np.
     fact 0 = 1
     fact n = n * fact (n–1)
  • W powyższym przykładzie stosowane jest dopasowywanie.
  • Alternatywnie można użyć dozorów, np.
     fact n
       | n == 0   = 1
       | n > 0    = n * fact (n–1)
  • Powyższa forma to wyrażenie warunkowe. Może zawierać część opatrzoną klauzulą otherwise, obliczaną wówczas, gdy wszystkie dozory są fałszywe.

Listy

  • Listy zapisywane są w nawiasach kwadratowych, np. [3, 2, 7].
  • Lista pusta zapisywana jest jako [].
  • Konstruktor listowy (odpowiednik CONS) to :, np. 1 : [3, 2, 7] daje [1, 3, 2, 7].
  • Listy można łączyć za pomocą operatora ++, np. [1, 3] ++ [2 ,7] daje [1, 3, 2, 7].
  • Operator # podaje długość listy.
  • Za pomocą operatora .. można określać ciągi arytmetyczne, np.
    • [1..5] daje [1, 2, 3, 4, 5]
    • [3, 6..15] daje [3, 6, 9, 12, 15].
  • Operator : może być używany w dopasowaniach, np.
     iloczyn []      = 1
     iloczyn (a : x) = a * iloczyn x

Operacje listotwórcze

  • Jest to metoda opisu list, które reprezentują zbiory.
  • Ogólna postać to [ wyrażenie | kwalifikator ].
  • Przykładowo, [ n * n | n ← [1..20] ] definiuje listę kwadratów liczb od 1 do 20.
  • Innymi słowy — „lista wszystkich n*n po n z zakresu od 1 do 20”.
  • Kwalifikatorem może być generator (jak w powyższym przykładzie) lub warunek, np.
     dzielniki n = [ i | i <- [1..n div 2], n mod i == 0]

Przykład

  • Implementacja sortowania szybkiego
     sort []    = []
     sort (h:t) = sort [b | b<-t, b<=h] ++ [h] ++ sort [b | b<-t, b>h]
  • Czyż nie jest imponująco zwięzła?

Obliczanie leniwe

  • Parametry funkcji obliczane są tylko wtedy, gdy jest to potrzebne do obliczenia owej funkcji.
  • Jeśli funkcja ma np. dwa parametry, a w konkretnym wywołaniu pierwszy parametr nie jest potrzebny w obliczeniach, odpowiedni parametr aktualny nie będzie obliczany.
  • Jeśli potrzebna jest tylko część parametru, tylko ta część zostanie obliczona.
  • Pozwala to definiować i stosować struktury nieskończone.
  • Struktury takie nie są faktycznie tworzone, lecz mogą być wykorzystane w leniwych obliczeniach.
  • Trzeba oczywiście uważać, by nie zmusić Haskella do nieskończonych obliczeń.

Przykład

  • lnieujemne = [0..]
  • lparzyste = [2, 4..]
  • kwadraty = [ n*n | n<-[0..] ]

Przykład

  • Zdefiniujmy dwie funkcje sprawdzające przynależność do listy.
  • Pierwsza funkcja:
     test1 [] b = False
     test1 (a : x) b = (a == b) || test1 x b
  • Druga funkcja:
     test2 (m : x) n
       | m < n     = test2 x n
       | m == n    = True
       | otherwise = False
  • Zauważmy, że funkcji test1 nie można użyć do sprawdzenia w rodzaju „test1 kwadraty 16”.
  • Takie sprawdzenie jest możliwe w przypadku funkcji test2, ale wymaga oczywiście założenia, że testowana lista jest uporządkowana rosnąco.