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