* JEZYK SCHEME -- KROTKIE OMOWIENIE

** EWALUACJA WYRAZEN

Do glownych zalet Scheme'a nalezy to, ze laczy on w sobie prostote
i semantyczna sile rachunku lambda z prostota i syntaktyczna sila
lispa. Dzieki tym dwom cechom mozna z latwoscia rozszerzac jezyk
o nowe wyrazenia, w naturalny sposob komponujace sie ze starymi,
a takze zmieniac sposob interpretacji istniejacych wyrazen.

Skladnia jezyka Scheme (podobnie jak wszystkich innych lispow)
jest bardzo prosta i stanowi "w pelni onawiasowana notacje polska".
Programy w lispie sa zlozone z nawiasow (przy czym kazdy nawias
otwierajacy musi miec odpowiadajacy nawias zamykajacy), symboli
(czyli dowolnych ciagow znakow oprocz nawiasow oraz znakow "`",
",", "'", ".", "#", podwojnych cudzyslowiow i bialych znakow.
Dodatkowy warunek jest taki, ze -- aby ciag byl uznany za symbol
-- nie moze byc interpretowany jako liczba) oraz liczb. (Standard
Scheme'a definiuje rowniez inne podstawowe jednostki leksykalne, m.in.
stringi, znaki czy wektory, jednak ze wzgledu na prostote
pominiemy sobie tutaj te kwestie)

Przykladowe wyrazenie arytmetyczne w Schemie mogloby miec zatem
postac:

: (+ (* 3 4) (/ 20 5))

Regula ewaluacji jest prosta: oczekujemy, ze wartoscia pierwszego
elementu listy bedzie funkcja (np. dodawanie, mnozenie itd.),
zas aby poznac wartosc calego wyrazenia, musimy zastosowac
funkcje do wartosci argumentow. Jezeli zatem symbole +, * i /
sa zwiazane z konwencjonalnymi dzialaniami arytmetycznymi,
powyzsze wyrazenie mozemy zgodnie z ta regula najpierw przeksztalcic do

: (+ 12 4)

a nastepnie do

: 16

** FORMY SPECJALNE

*** FORMA "quote"

Ciekawa wlasnoscia lispa jest tzw. homoikonicznosc: kod zrodlowy
programow stanowi liste symboli, liczb i ewentualnie innych list,
zas listy, symbole i liczby sa typami danych, na ktorych programy
lispowe moga operowac. Aby powstrzymac ewaluator przed interpretowaniem
symbolu, trzeba uzyc operatora "quote". Wartoscia wyrazenia

: (quote x)

bedzie

: x

Operator "quote" dziala inaczej, niz uzyte powyzej operatory arytmetyczne.
Operatory arytmetyczne (domyslnie) stanowia zwykle funkcje, zas "quote"
jest forma specjalna, ktora charakteryzuje sie tym, ze nie ewaluuje swoich
argumentow. Lisp traktuje zapis 'x rownowaznie z zapisem (quote x).

Aby uzyskac liste symboli (a b c), moglibysmy uzyc funkcji "list":

: (list 'a 'b 'c)
: ===>
: (a b c)

Operator "quote" dziala jednak nie tylko na symbole, ale rowniez na cale
wyrazenia, wiec powyzszy wynik moglibysmy uzyskac rowniez piszac po prostu
: '(a b c)
: ===>
: (a b c)

*** FORMA "lambda"

Oprocz operatora "quote", w jezyku Scheme wystepuje 5 innych podstawowych
form specjalnych. Jedna z nich jest forma "lambda", ktora ma nastepujaca
postac:

: (lambda (argumenty ...) cialo + ...)

Forma "lambda" jest bardzo potezna i w zasadzie wzieta sama w sobie
stanowi kompletny jezyk programowania, pozwalajacy na wyrazenie instrukcji
warunkowych "if-then-else" oraz liczb naturalnych. Osobom zainteresowanym
tym zagadnieniem polecam kurs programowania funkcyjnego autorstwa Johna
Harrisona:
http://www.cl.cam.ac.uk/teaching/Lectures/funprog-jr
h-1996/index.html

Mowiac najkrocej, wyrazenie lambda tworzy nowa funkcje. Najprostszy
przyklad moglby wygladac nastepujaco:

: (lambda (x y)(+ x (* x y)))

W wyniku dostajemy funkcje dwuargumentowa, ktora dodaje swoj pierwszy
argument do iloczynu obu argumentow. Gdybysmy chcieli uzyc tej funkcji,
moglibysmy napisac:

: ((lambda (x y)(+ x (* x y))) 3 4)

Aplikacje wyrazenia lambda mozna pojmowac w taki sposob, ze zastepujemy
cale wyrazenie lambda jego cialem, w ktorym symbole uzyte jako argumenty
zastepujemy wartosciami tych argumentow. W powyzszym przypadku byloby to:

: (+ 3 (* 3 4))

Choc moze to wygladac niepozornie, majac do dyspozycji te regule, mozemy
wyrazic dowolna funkcje rekurencyjna (za sprawa tzw. kombinatorow punktu
stalego, w szczegolnosci -- kombinatora Y).

Dodatkowo Scheme pozwala nam zdefiniowac funkcje mogaca przyjmowac dowolnie
wiele argumentow, jezeli zamiast listy argumentow podamy pojedynczy symbol.
Wowczas z owym symbolem zostaje w ciele funkcji zwiazana lista wszystkich
przekazanych argumentow:

: ((lambda args args) 1 2 3)
: ===>
: (1 2 3)

*** FORMA "define"

Kolejna forma specjalna jest forma "define", ktora pozwala nam nazywac
rozne obiekty. Na przyklad moglibysmy zdefiniowac podnoszenie do kwadratu:

: (define square (lambda (x) (* x x)))

Operacja ta wiaze funkcje, ktora mnozy swoj jedyny argument przez siebie,
z symbolem "square". Zapis

: (square 5)

jest rownowazny zapisowi

: ((lambda (x) (* x x)) 5)

co na mocy wczesniejszej reguly mozna przeksztalcic do

: (* 5 5)

Formy "define" mozna rowniez uzyc do wprowadzenia definicji w zasiegu
wyrazenia "lambda", np.

: (define x 5) ; zasieg zewnetrzny
: x
: ===> 5

: ((lambda () (define x 20) x))
: ====> 20

: x
: ===> 5 ; wartosc w zasiegu zewnetrznym nie ulegla zmianie

Warto wiedziec, ze formalnie nie uznaje sie definicji za wyrazenia,
i na przyklad zapis

: (lambda () (define x 20))

jest bledny, poniewaz cialo wyrazenia lambda musi zawierac przynajmniej
jedno wyrazenie.

*** FORMA "if"

Kolejna forma specjalna, ktora zasluguje na uwage, jest forma
warunkowa "if", o nastepujacej skladni:

: (if warunek wyrazenie-gdy-warunek-spelniony)

lub

: (if warunek
: wyrazenie-gdy-warunek-spelniony
: wyrazenie-w-przeciwnym-razie)

Forma "if" dziala w taki sposob, ze najpierw dokonuje ewaluacji warunku,
i jezeli wartosc warunku jest rozna od wartosci falszu (zapisywanej w Schemie
jako "#f" albo -- wg. najnowszego standardu -- jako "#false"), to
wartoscia calego wyrazenia staje sie wartosc *wyrazenia-gdy-warunek-spelniony*,
zas w przeciwnym razie wartosc wyrazenia albo jest nieokreslona (dla wariantu
pierwszego), albo jest wartoscia *wyrazenia-w-przeciwnym-razie*.

Forma "if" pozwala na definiowanie zlozonych funkcji. Klasycznym przykladem
jest funkcja "silnia":

: (define ! (lambda (n) (if (= n 0) 1 (* n (! (- n 1))))))

Zgodnie z regulami ewaluacji, wyrazenie
: (! 5)
mozna zinterpretowac nastepujaco:
: ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 5)
: ===>
: (if (= 5 0) 1 (* 5 (! (- 5 1))))
: ===>
: (* 5 (! 4))
: ===>
: (* 5 ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 4))
: ===>
: (* 5 (if (= 4 0) 1 (* 4 (! (- 4 1)))))
: ===>
: (* 5 (* 4 (! 3)))
: ===>
: (* 5 (* 4 ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 3)))
: ===>
: (* 5 (* 4 (if (= 3 0) 1 (* 3 (! (- 3 1))))))
: ===>
: (* 5 (* 4 (* 3 (! 2))))
: ===>
: (* 5 (* 4 (* 3 ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 2))))
: ===>
: (* 5 (* 4 (* 3 (if (= 2 0) 1 (* 2 (! (- 2 1)))))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (! 1)))))
: ===>
: (* 5 (* 4 (* 3 (* 2 ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 1)))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (if (= 1 0) 1 (* 1 (! (- 1 1))))))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (* 1 (! 0))))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (* 1 ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 0))))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (* 1 (if (= 0 0) 1 (* 0 (! (- 0 1)))))))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (* 1 1)))))
: ===> ... ===>
: 120

*** FORMA "set!"

Forma "set!" powoduje przypisanie nowej wartosci do istniejacej (tzn. zwiazanej)
zmiennej. Zmienna moze byc zwiazana albo przy pomocy formy "define", albo
jako parametr formalny w formie "lambda"

: (define x 5)
: x
: ===> 5

: ((lambda (x) (set! x (+ x 1)) x) 7) ; zmiana wartosci zmiennej lokalnej
: ===> 8

: x
: ===> 5

: ((lambda () (set! x (+ x 1)))) ; zmiana wartosci zmiennej zewnetrznej
: x
: ===> 6

*** FORMA "begin"

Formy "begin" uzywamy do grupowania wyrazen, np. wewnatrz ktorejs galezi
formy "if". Warto jednak zwrocic uwage, ze zapis

: (begin definicje/wyrazenia ...)

nie jest rownowazny zapisowi

: ((lambda () definicje/wyrazenia ...))

poniewaz forma "begin" nie wprowadza nowego zasiegu. W szczegolnosci
forma "begin" moze zawierac wylacznie definicje, i np. zapis

: (begin (define symbol-1 wartosc-1) (define symbol-2 wartosc-2))

jest rownowazny zapisowi:

: (define symbol-1 wartosc-1)
: (define symbol-2 wartosc-2)

** FUNKCJE WBUDOWANE
Lista funkcji wbudowanych nie jest szczegolnie istotna. W dotychczasowych
przykladach uzywalem funkcji +,*,-,/,= oraz list.

*** FUNKCJA "apply"

Jest jednak kilka funkcji, ktore zasluguja na szczegolna uwage. Pierwsza
z nich jest "apply". Zapis

: (funkcja argumenty ...)

jest rownowazny zapisowi

: (apply funkcja (list argumenty ...)).

Na przyklad zamiast

: (+ 1 2)

mozna napisac

: (apply + '(1 2))

Ponadto funkcja "apply" moze byc uzyta z dodatkowymi argumentami pomiedzy
argumentem funkcyjnym a lista. Wowczas elementy pomiedzy pierwszym a ostatnim
argumentem zostana dopisane na poczatku ostatniego argumentu. W zwiazku z tym
nastepujace wywolania sa rownowazne:

: (+ 1 2 3)
: (apply + '(1 2 3))
: (apply + 1 '(2 3))
: (apply + 1 2 '(3))
: (apply + 1 2 3 '())

*** FUNKCJE "values" i "call-with-values"

Pewna specyficzna cecha Scheme'a jest to, ze zdefiniowane w nim funkcje moga
zwracac wiecej niz jedna wartosc. Do zwracania wielu wartosci sluzy funkcja
"values", ktora pobiera dowolnie wiele argumentow:

: (values 1 2 3)
: ===> 1
: ===> 2
: ===> 3

Do przechwycenia tych wartosci sluzy funkcja call-with-values, ktora pobiera
dwie funkcje -- producenta (0-argumentowego) i konsumenta (n-argumentowego), np.

: (call-with-values (lambda()(values 1 2 3)) (lambda(a b c)(+ a b c)))

*** FUNKCJE "cons", "car" i "cdr"

Do tej pory w kilku przykladach uzylem dowolnie-wielo-argumentowej funkcji
"list", ktorej wartoscia jest lista podanych do niej argumentow. Warto
jednak wiedziec nieco wiecej o architektonice list. Po pierwsze, istnieje
w Schemie specjanly symbol na oznaczenie listy pustej, a jest on zapisywany tak:

: '()

Po drugie, listy skonstruowane sa z par. Do tworzenia par sluzy funkcja cons:

: (cons 'a 'b)
: ===> (a . b)

Po trzecie, funkcje car i cdr sluza do pobrania odpowiednio pierwszego
i drugiego elementu pary:

: (car (cons 'a 'b))
: ===> a

: (cdr (cons 'a 'b))
: ===> b

Elementy (car x) i (cdr x) bedziemy od tej pory nazywac odpowiednio glowa
i ogonem listy.

Po czwarte, zapis

: (a . (b . (c . ())))

jest rownowazny zapisowi

: (a b c)

zas zapis

: (a . (b . (c . d)))

zapisowi

: (a b c . d)

dla dowolnych dopuszczalnych wartosci a, b, c, d). Jezeli drugi element
ostatniej pary listy nie jest lista pusta, to taka liste nazywamy
"lista kropkowana" ("dotted list").

Stad tez (list 1 2 3) jest rownowazne (cons 1 (cons 2 (cons 3 '()))).

*** PREDYKATY POROWNUJACE: "=", "<", "<=", ">", ">=", "eq?"

Oprocz uzytej w jednym z poprzednich przykladow funkcji "=", sprawdzajacej
rownosc numeryczna, Scheme definiuje kilka innych uzytecznych predykatow
do operowania na liczbach, m.in. "<" (mniejszy od), ktory zwraca
prawde wtw jej argumenty (liczbowe) stanowia ciag rosnacy, np.

: (< 1 3 7)
: ===> #t ; gdzie #t to specjalna wartosc odpowiadajaca prawdzie logicznej

: (< 3 7 1)
: ===> #f

Pozostale funkcje porownujace ("<=", ">", ">=") dzialaja tak, jak mozna
sie po nich spodziewac. Na uwage zasluguje predykat eq?, ktory sprawdza,
czy dwa obiekty sa tym samym obiektem -- na przyklad, czy dwa symbole
sa tym samym symbolem. W przypadku list dzialanie tej funkcji moze byc
zaskakujace:

: (define a '(1 2 3))
: (define b '(1 2 3))
: (eq? a b)
: ===> #f

Wynika to stad, ze listy a i b stanowia osobne obiekty w pamieci.
(W pewnych przypadkach niektore kompilatory moglyby zoptymalizowac powyzszy
kod w taki sposob, ze a i b bylyby tym samym obiektem, i wowczas uzycie
funkcji eq? moze zwrocic #t).

Lista pusta jest zawsze tozsama ze soba, tj.

: (eq? '() '())
: ===> #t

*** UWAGI O FUNKCJI "call-with-current-continuation" ("call/cc")

Ostatnia osobliwa funkcja jest call-with-current-continuation, zazwyczaj
skracana jako call/cc. Z pewnych wzgledow omowie ja dopiero pozniej, gdy
bede mial mozliwosc zademonstrowania jej dzialania na konkretnym przykladzie.