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> | ...

Wyrażenia arytmetyczne

Do budowy wyrażeń arytmetycznych możemy używać standardowych symboli operacji arytmetycznych oraz liczb całkowitych i zmiennopozycyjnych. Dla obu rodzajów liczb używamy tych samych operacji. Dzięki temu, że w Scheme'ie zgodność typów jest kontrolowana w trakcie wykonania, typ wyniku jest ustalany w trakcie obliczeń, na podstawie typów argumentów.

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. Operacje arytmetyczne potrafią przyjmować dowolną liczbę argumentów. Nawiasy wyznaczają dokładnie listę argumentów.

Przykład [Wyrażenia arytmetyczne]

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 logiczne

Wartości prawda i fałsz są reprezentowane przez stałe #t i #f. Do budowy wyrażeń logicznych możemy używać standardowych relacji porównywania oraz operacji logicznych:

• and (koniunkcja),
• or (alternatywa) i
• not (negacja).

Relacje porównywania przyjmują dwa lub więcej argumentów i są spełnione, jeśli każde dwa kolejne argumenty są w danej relacji. Operacje and i or przyjmują dowolną liczbę argumentów. Natomiast negacja przyjmuje tylko jeden argument.

Przykład [Wyrażenia logiczne]

(and #t (< 1 2 3) (not (= 1 2 1)))
#t

(and)
#t 

(= (* 2 2) (+ 2 2) 4) 
#t 

Wyrażenia warunkowe

Mamy dwa rodzaje wyrażeń warunkowych: cond i if. 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.

W ostatniej klauzuli, jako dozór można podać słowo kluczowe else. Jest ono równoważne dozorowi, który jest zawsze spelniony.

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

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.

<wyrażenie> ::= (if <wyrażenie> <wyrażenie> <wyrażenie> )

Wyrażenie postaci:

$\mathtt{(}\mathtt{i}\mathtt{f}w{v}_1{v}_2\mathtt{)}$

jest równoważne:

$\mathtt{(}\mathtt{c}\mathtt{o}\mathtt{n}\mathtt{d}\mathtt{(}w{v}_1\mathtt{)}\mathtt{(}\mathtt{e}\mathtt{l}\mathtt{s}\mathtt{e}{v}_2\mathtt{)}\mathtt{)}$

Oczywiście, wyrażenia warunkowe cond i if są formami specjalnymi, gdyż nie dałoby się ich zdefiniować jako procedur.

Przykład [Wyrażenia warunkowe]

(if 
  (= x 0) 
  0 
  (/ 1 x))
 
(cond 
  ((> x 0) x) 
  ((= x 0) 1) 
  (else (-x)))

Definicje

Definicje stałych

Nowe nazwane stałe możemy definiować za pomocą formy specjalnej define. Ma ona postać kombinacji trzech elementów, z których pierwszy to słowo kluczowe define. Drugi element to nazwa definiowanej stałej, a jej wartość określa trzeci element.

<definicja>  ::=  (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

Definicje procedur

Procedury definiujemy również za pomocą define i definicje takie również mają postać trójelementowych kombinacji. Natomiast w przypadku definicji procedur, drugi element to kilka identyfikatorów ujętych w nawiasy. 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> )

Przykład [Definicje procedur]

Silnia:

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

Signum (znak liczby):

(define (sig x)
  (cond
    ((< x 0) (- 1))
    ((> x 0) 1)
    (else 0)))

Liczenie NWD algorytmem Euklidesa (przez odejmowanie):

(define (nwd x y) 
  (cond
    ((= x y) x)
    ((> x y) (nwd (- x y) y))
    (else (nwd x (- y x)))
  )
)

$\lambda$-abstrakcja

$\lambda$-abstrakcję zapisujemy podobnie do definicji procedury, tylko z pominięciem nazwy procedury i używając innego słowa kluczowego. $\lambda$-abstrakcja ma postać kombinacji trzech elementów. Pierwszy z nich to słowo kluczowe lambda. Drugi, to nazwy parametrów formalnych ujęte w nawiasy. Natomiast trzeci, to wyrażenie stanowiące treść $\lambda$-abstrakcji.

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

Przykład [$\lambda$-abstrakcja]

(define abs (lambda (x) (if (> x 0) x (- x))))

Definicje lokalne

Definicje lokalne mają dokładnie taką samą treść jak globalne, ale są umieszczone w treści innych definicji, zwykle definicji procedur. Ich zakres jest ograniczony do definicji, w której się znajdują.

(define (pitagoras x y)
  (define (square x) (* x x))
  (+ (square x) (square y))
)
(pitagoras 3 4)
25

Wyrażenia let

Oprócz definicji lokalnych, istnieje odpowiednik wyrażeń let-in z Ocamla. Są to wyrażenia let. Mają one postać kombinacji złożonej z trzech elementów. Pierwszy z nich to słowo kluczowe let. Drugi z nich, to lista par definiujących lokalnie wprowadzane stałe, ujęta w nawiasy. Natomiast trzeci element, to wyrażenie, którego wartość stanowi wartość całego wyrażenia. Para definiująca lokalnie wprowadzaną stałą składa się z nazwy tej stałej oraz wyrażenia określającego jej wartość, ujętych w nawiasy.

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

Wyrażenie postaci:

(let (
  ($x_1{w}_1$)
  ... 
  ($x_n{w}_n$))
  $t$
)

jest równoważne:

((lambda ($x_1\dots x_n$) $t$) $w_1\dots w_n$)

Przykład [Wyrażenie let]

(define (pitagoras x y)
  (let
    ((square (lambda (x) (* x x))))
    (+ (square x) (square y))
  )
)

Struktury danych

Pary

Podstawową konstrukcją do budowy złożonych danych jest para. Przypomnijmy, że w Scheme'ie mamy dynamiczną kontrolę typów. Oznacza to, że dopiero w momencie wykonywania jakiejś operacji na danych, sprawdzane jest, czy dane te są odpowiednich typów. Dzięki temu, elementy par mogą być czymkolwiek, w tym również parami i nie jest to narzucone przez żaden system typów. Tak więc za pomocą par możemy budować listy oraz drzewa (zwane strukturami listowymi).

Podstawowe operacje na parach to:

• cons -- dwuargumentowy konstruktor pary,
• car -- rzutowanie pary na pierwszą współrzędną,
• cdr -- rzutowanie pary na drugą współrzedną.

Przykład [Pary]

(define p (cons 1 2))
(car p)
1

(cdr p)
2

Struktury listowe

Listy tworzymy z par w ten sposób, że pierswsza współrzędna pary to głowa listy, a druga to ogon listy. Pusta lista jest reprezentowana za pomocą specjalnej wartości (). Dostepny jest też wbudowany predykat null? który jest prawdziwy tylko dla (). Listy są wypisywane jako ciąg wartości elementów, ujęty w nawiasy.

Do budowy list, oprócz cons, dostępna jest procedura list, która przyjmuje dowolną liczbę argumentów, a jej wynikiem jest lista zbudowana z tych argumentów. Należy być ostrożnym i nie mylić wyrażenia (list 1 2 3 4) z listą (1 2 3 4), tak jak ją wypisuje kompilator.

Ponieważ operacje car i cdr</t> nie są przesadnie poręczne, Scheme udostępnia skróconą formę zapisu ich złozeń i tak zamiast (car (cdr l)) możemy napisać (cadr l). Dla innych złożeń dostępne są analogiczne skrótowce.

Przykład [Listy]

(cons 1 (cons 2 (cons 3 ())))
(1 2 3)

(caddr (list 1 2 3 4))
3