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.

Scheme jest językiem z gorliwym obliczaniem wartości argumentów. Obliczenie wartości kombinacji polega na:

• obliczeniu wartości wszystkich elementów kombinacji (zarówno procedury, jak i jej argumentów),
• zastosowaniu procedury do obliczonych wartości argumentów.

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)

Wyrażenia warunkowe

Mamy dwa rodzaje wyrażeń warunkowych: if i cond. Wyrażenie warunkowe cond ma postać kombinacji składającej się ze słowa kluczowego cond oraz pewnej liczby klauzul. Każda z klauzul to para wyrażeń ujętych w nawiasy. Pierwsze z wyrażeń musi być warunkiem logicznym -- jest ono nazywane dozorem. Drugie wyrażenia w klauzulach nazywamy następnikami.

Obliczenie wyrażenia warunkowego cond polega na:

• obliczaniu dozorów kolejnych klauzul, aż do napotkania prawdziwego dozoru,
• obliczeniu następnika klauzuli, której dozór jest prawdziwy.

Wyrażenia warunkowe if mają postać kombinacji czterech elementów, z których pierwszy to słowo kluczowe if. Drugi element kombinacji to warunek. Trzeci element to wyrażenie, które jest obliczane gdy warunek jest prawdziwy, a czwarty to wyrażenie, które jest obliczane gdy warunek jest fałszywy. Zwróćmy uwagę, że if nie jest procedurą. Jest to forma specjalna, gdyż jedno z wyrażeń nie jest obliczane.

<wyrażenie> ::= (cond { ( <wyrażenie> <wyrażenie> ) }+ )

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 parametry formalne definiowanej procedury. 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)))))