Programowanie funkcyjne/Scheme

Wstęp

W dotychczasowych wykładach poznawaliśmy i używaliśmy języka Ocaml. Ocaml (Objective Caml) to dialekt języka ML. Wśród dialektów ML-a jest to język bogaty, ze względu na to, że zawiera:

• bogaty zestaw bibliotek,
• programowanie obiektowe,
• system modułów i funktorów, wraz z funktorami wyższych rzędów.

Tak jak inne dialekty ML-a, Ocaml charakteryzuje się:

• ścisłą statyczną kontrolą typów,
• polimorfizmem, oraz
• tym, że zawiera konstrukcje imperatywne.

W tym i kolejnym wykładzie zobaczymy przedstawicieli innych rodzin funkcyjnych języków programowania. W tym wykładzie poznamy język Scheme -- dialekt Lispu. Jest to język o bardzo prostej, wręcz minimalistycznej składni. Tak jak Ocaml, zawiera konstrukcje imperatywne. Natomiast charakteryzuje się dynamiczną kontrolą typów.

Kombinacje i wyrażenia

Podstawową konstrukcją składniową w Scheme'ie jest kombinacja. Jest to sekwencja wartości ujętych w nawiasy. Pierwsza z tych wartości musi być procedurą. Kolejne wartości stanowią argumenty. Obliczenie wartości kombinacji polega na wywołaniu procedury będącej pierwszym elementem kombinacji i zastosowaniu jej do pozostałych elementów kombinacji.

Wyrażenia, nazywane również S-wyrażeniami, budujemy używając kombinacji, nazwanych wartości i stałych.

<wyrażenie>     ::= <stała> | <kombinacja> 
<kombinacja>    ::= ( { <wyrażenie> }+ )
<stała>         ::= <identyfikator> | <liczba> | ...

Do pewnego stopnia, wyrażenia zapisujemy jak w notacji polskiej, tzn. najpierw operacja, a potem argumenty. Jednak inaczej niż w notacji polskiej, nawiasy otaczające kombinacje są konieczne. Niektóre procedury potrafią przyjmować różne liczby argumentów. Jest tak np. z operacjami arytmetycznymi. Nawiasy wyznaczają dokładnie listę argumentów w wyołaniu procedury.

Przykład [Wyrażenia]

Poniższe wyrażenia są wszystkie równe 42 (lub 42.0).

42
(+ 36 6)
(* 3 14)
(- 100 58)
(- (* 1 2 3 4 5) (/ (* (+ 6 7) 8 9) 12)) 
(/ (silnia 7) (silnia 5))
(/ 596.4 14.2)

Definicje

Nowe nazwane wartości możemy definiować za pomocą formy specjalnej define. Ma ona postać kombinacji trzech elementów, z których pierwszy to słowo kluczowe define. Jeżeli drugi element jest identyfikatorem, to jest to definicja stałej, a jej wartość określa trzeci element. Drugi element może też być kombinacją złożoną z kilku identyfikatorów. Wówczas jest to definicja procedury -- pierwszy z identyfikatorów to nazwa definiowanej procedury, a kolejne to nazwy argumentów. Trzeci element definicji to treść procedury. Definicje procedur mogą być rekurencyjne (i nie wymaga to dodatkowego zaznaczenia, jak w Ocamlu).

<definicja>  ::=  (define <identyfikator> <wyrażenie> )  |
                  (define ( { <identyfikator> }+ ) <wyrażenie> )

Przykład [Definicje stałych]

Oto przykładowe definicje stałych

(define a 6)
(define b (+ a 1))
(* a b)
42

Podobnie jak w Ocamlu, kolejne definicje przysłaniają już zdefiniowane stałe:

(define a 2)
(define b (* 2 a))  
(define a (* a b)) 
a
8

Przykład [Definicje procedur]

(define (silnia n) (if (<= n 1) 1 (* n (silnia (- n 1)))))