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

Typy proste

Wśród wbudowanych typów prostych mamy szereg rodzajów liczb: całkowite, wymierne, zmiennopozycyjne i zespolone. Operacje na liczbach same rozpoznają jakiego rodzaju są argumenty, i ich wyniki są odpowiedniego rodzaju. Oprócz liczb mamy (omówione już) wartości logiczne, oraz napisy (ujmowane w cudzysłów) i symbole.

Symbole to nietypowy typ danych. Odpowiadają one pojęciu identyfikatora, trzeba jednak pamiętać, że są to wartości danych, a identyfikatory są nazwami określonych wartości. Zapisujemy je stawiając apostrof przed identyfikatorem, jaki mają reprezentować.

Dostępne są predykaty kontrolujące typy wartości: number?, boolean?, string?, symbol?, list?.

Przykład [Typy proste]

42
42

(/ 2 12)
1/6

(* 3.14 2 2)
12.56

(sqrt (- 4))
0+2i
 
(> 2 3)
#f

"ala ma kota"
"ala ma kota"

'nazwa
nazwa 

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

Operacje na listach

Dostępnych jest szereg standardowych operacji na listach, takich jak length, append, reverse, map itp.

Przykład [Operacje na listach]

Oto jak możnaby zdefiniować operacje length i append:

(define (length l)
  (if (null? l)
  0
  (+ 1 (length (cdr l)))))

(define (append l1 l2)
  (if (null? l1)
  l2
  (cons (car l1) (append (cdr l1) l2))))

Notacja kropki i ogona

Możemy definiować procedury, które mogą mieć różną liczbę argumentów. Ich definicje mają postać:

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

Procedura taka wymaga przynajmniej tylu argumentów, ile jest identyfikatorów przed kropką. Natomiast identyfikator po kropce reprezentuje listę wszystkich pozostałych argumentów. Na przykład:

(define (p x y . z) ... )

Procedura p ma przynajmniej dwa argumenty. Pierwszy argument jest równy x, drugi y, a pozostałe argumenty tworzą listę równą z.