Przewodnik po Scheme

Zbigniew Jurkiewicz, IIUW

December 20, 2005

Przedmowa

Przewodnik oprowadza szybko ,,zwiedzającego'' po składni i znaczeniu najbardziej użytecznych konstrukcji języka Scheme. Nie jest oficjalną dokumentacją języka ani żadnej jego implementacji. Formalną definicję języka Scheme podaje Revised[przewodnik-Z-G-1.gif] Report on the Algorithmic Language Scheme.

Notacja

W dalszej części używać będziemy następujących konwencji notacyjnych:

1  Szybkie wprowadzenie

Scheme jest językiem programowania opartym na wyrażeniach. Wyrażenia nazywają wartości, np. 3.14 jest nazwą przybliżenia powszechnie znanej liczby.

1.1  Wartości

Część wyrażeń to wyrażenia elementarne, nazywające wartości. Należą do nich

1.2  Identyfikatory

Wyrażeniami prostymi są również identyfikatory. W nazwach identyfikatorów mozna używać liter, cyfr i znaków

= - > < / * ? ! +
Znak ? stawia się zwykle na końcu nazwy predykatu, zaś znakiem ! kończy się nazwy funkcji powodujących efekty uboczne -- modyfikacje stanu obiektów. Znaków -> używa się wewnątrz nazw funkcji konwersji typów (np. number->string), zaś znaku : dla symboli z pakietów/modułów do oddzielenia nazwy pakietu od właściwej nazwy (np. primes:fast-prime?).

1.3  Wywołania procedur

Wywołanie procedury jest wyrażeniem złożonym -- ciągiem wyrażeń ujętym w nawiasy. Pierwsze wyrażenie powinno nazywać procedurę, zaś pozostałe nazywają argumenty dla tej procedury. Wartością wywołania jest wynik zastosowania procedury do argumentów, np.

> (+ 1 2.14) 3.14 > (+ 1 (* 2 1.07)) 3.14 Jak widać, oba wyrażenia nazywaja tę samą wartość. W powyższym przykładzie symbole + i * oznaczały procedury dodawania i mnożenia. Formalnie wywołanie procedury ma postać
(operator operand-1 ... operand-n)

1.4  Definicje

Konstrukcji define używa się do nadania związania nazwy z pewnym obiektem Scheme, na przykład

(define pi 3.14159265)

Zdefiniowanej nazwy można używać jako identyfikatora w wyrażeniach

> pi 3.14159265 > (* 4 pi) 12.5663706

Ogólnie konstrukcja define ma następującą postać

(define nazwa wyrażenie)
Nazwa nie jest obliczana i powinna być identyfikatorem. Konstrukcji define można również używać w definicji funkcji, treści wyrażenia let i podobnych kontekstach, ale tylko na początku bloku. Odpowiada ona wtedy wyrażeniu letrec.

1.5  Definiowanie funkcji

Do definiowania funkcji służy najczęściej specjalna postać konstrukcji define

(define (nazwa parameter ...) wyrażenie ...)
(nazwane funkcje można również definiować używając ogólnej postaci define i funkcji anonimowych).

Zdefiniujemy funkcję podnoszenia do kwadratu

(define (kwadrat x) (* x x)) Tak zdefiniowaną funkcję możemy wywołać tak samo jak funkcje systemowe > (kwadrat 4) 16

1.6  Funkcje anonimowe

W Scheme funkcje są normalnymi obiektami danych, dlatego można je przekazywać jako argumenty i zwracać jako wartości innych funkcji. Nie muszą być nazywane, funkcje anonimowe można tworzyć konstrukcją

(lambda (parametr ...) wyrażenie ...)
Wartością tego wyrażenia jest procedura o podanych parametrach, która po wywołaniu oblicza kolejno wyrażenia i zwraca wartość ostatniego. Na przykład wartością (lambda (x) (* x x)) jest jednoargumentowa procedura, zwracająca kwadrat argumentu. Aby użyć lambda wyrażenia w obliczeniu zwykle umieszcza się je w pozycji operatora kombinacji, na przykład podnoszenie liczby 4 do kwadratu zapisać można jako > ((lambda (x) (* x x)) 4) 16 Ogólnie konstrukcji tej można używać wszędzie tam, gdzie może wystąpić nazwa funkcji.

Składanie funkcji (na razie jednoargumentowych) można zdefiniować jako funkcję1 działającą na funkcjach (,,funkcjonał'') (define (compose f g) (lambda (x) (f (g x)))) używając jej potem następująco > ((compose kwadrat sin) 2) 0.826821810431806 > (kwadrat (sin 2)) 0.826821810431806

1.7  Struktura programu

Program w Scheme jest ciągiem definicji i obliczanych wyrażeń. Definicje i wyrażenia mogą występować w dowolnej kolejności, byleby żadna zmienna nie była używana przed jej zdefiniowaniem. Programy mogą być zapisywane na plikach i uruchamiane wsadowo. W trybie wsadowym definicje zwykle poprzedzają obliczane wyrażenia.

Inna możliwość to praca interakcyjna pod nadzorem interpretera. W tym trybie programista podaje kolejno definicje i wyrażenia do wyliczenia, używając debuggera do poprawiania wykrytych błędów.

W programach mogą (i powinny ;-) być umieszczane komentarze. Komentarz jest to dowlny ciąg znaków rozpoczynający się co najmniej jednym średnikiem i ciągnący do końca wiersza. Komentarzy rozpoczynających się kilkoma średnikami używa się konwencjonalnie do wskazywania komentarzy nagłówkowych, odnoszących się do większych fragmentów kodu, np. poprzedzając definicję funkcji opisującym ją komentarze.

1.8  Wartości Booleowskie

Wartośc prawdy jest oznaczana jako #t, zaś fałsz jako #f. Ponadto w wielu kontekstach, np. w wyrażeniach warunkowych dowolny obiekt różny od #f również oznacza prawdę. Nie należy tego nadużywać bez potrzeby.

1.9  Predykaty

W Scheme są zdefiniowane predykaty dla wszystkich typów danych. Ich nazwy zakończone są znakiem ?. Predykaty te zwracają #t lub #f.

Dla żadnego obiektu nie jest równocześnie prawdziwy więcej niż jeden spośród następujących predykatów: boolean?, pair?, symbol?, number?, char?, string?, vector?, procedure?.

1.10  Wyrażenia warunkowe

Najprostszym wyrażeniem warunkowym jest

(if warunek konsekwencja [alternatywa])

Jego wykonanie polega na obliczeniu wartości warunku i zależnie od tego, czy jest on spełniony, obliczenie konsekwencj lub alternatywy. Należy pamiętać, że dowolna wartość różna od #f desygnuje prawdę, a więc wartością (if 0 1 2) jest 1.

Jeśli alternatywa została pominięta, a warunek nie jest spełniony, to wartość wyrażenia if nie jest określona. Takiej postaci wyrażenia if używa się dla warunkowych efektów ubocznych, dla czytelności lepiej jednak skorzystać wtedy z (nieco mocniejszych) wyrażeń when lub unless.

Wyrażenie when ma postać

(when warunek wyrażenie wyrażenie ...)

Jeśli warunek jest spełniony, to oblicza się kolejno wyrażenia i zwraca wartość ostatniego z nich, w przeciwnym razie wartość wyrażenia nie jest określona.

Wyrażenie

(unless warunek wyrażenie wyrażenie ...)

jest przeciwieństwem when. Wyrażenia są obliczane tylko wtedy, gdy warunek nie jest spełniony.

Najogólniejszym (i najstarszym) wyrażeniem warunkowym jest

(cond (warunek wyrażenie ...)
      (warunek wyrażenie ...)
      ...
      [(else wyrażenie ...)])

Oblicza się kolejno warunki tak długo, aż któryś z nich będzie spełniony. Jeśli któryś warunek będzie spełniony, to oblicza się kolejno odpowiadające mu wyrażenia i zwraca ostatnio obliczoną wartość (czyli jeśli po warunku nie następują żadne wyrażenia, to zwraca się po prostu wartość warunku).

Jeśli żaden warunek nie był spełniony, to wartość wyrażenia cond nie jest określona. Jako ostatniego warunku można opcjonalnie użyć słowa kluczowego else, oznacza ono warunek zawsze spełniony (jest to typowy lukier składniowy, ponieważ tę samą rolę doskonale spełniłby warunek #t, a także jakakolwiek inna stała różna od #f).

Wyrażenie

(case klucz
  ((wartość wartość ...) wyrażenie ...)
  ((wartość wartość ...) wyrażenie ...)
  ...
  [(else wyrażenie ...)])

stanowi uproszczoną wersję wyrażenia cond. Oblicza się wartość klucza i kolejno porównuje z każdą z wartościami z kolejnych klauzul. Gdy są równe, oblicza się kolejno wyrażenia tej klauzuli i zwraca wartość ostatniego. Jeśli nie znaleziono pasującej wartości, to wartość całego wyrażenia nie jest określona. Aby tego uniknąć zamiast listy wartości można w ostatniej klauzuli użyć stałej składniowej else, pasujacej do każdego klucza.

1.11  Inne konstrukcje syntaktyczne

Poza wyrażeniami warunkowymi inne konstrukcje syntaktyczne to:

(quote obiekt) lub 'obiekt

Oba powyższe wyrażenia zwracają po prostu obiekt (bez obliczania jego wartości). Pozwala to zapobiegać obliczeniu stałych wyglądających jak wyrażenia, np. wyrażenia '(1 2 3) zwraca listę (1 2 3).

(and wyrażenie ...)

Oblicza kolejno wyrażenia do momentu, gdy wartością któregoś będzie fałsz i wtedy zwraca #f. W przeciwnym razie zwraca wartość ostatniego wyrażenia.

(or wyrażenie ...)

Oblicza kolejno wyrażenia do momentu, gdy wartością któregoś nie będzie fałsz i wtedy zwraca tę wartość. W przeciwnym razie (tzn. gdy wszystkie obliczenia dały fałsz) zwraca wartość #f.

(not wyrażenie)

Jeśli wartością wyrażenia #f, to zwraca #t, w przeciwnym razie zwraca #f (not jest więc zwykłą funkcją, ale dobrze pasuje w tym miejscu ;-).

(let ((zmienna wyrażenie-inicjujące)
      ...)
  wyrażenie ...)

Oblicza wyrażenia-inicjujące i związuje z odpowiednimi zmiennymi. W tak utworzonym środowisku lokalnym oblicza kolejno wyrażenia i zwraca wartość ostatniego z nich.

(let* ((zmienna wyrażenie-inicjujące)
       (zmienna wyrażenie-inicjujące)
       ...)
   wyrażenie ...)

Podobne do let, ale obliczanie wyrażeń-inicjujacych odbywa się po kolei, przy czym obliczanie każdego wyrażenia-inicjującego odbywa się w środowisku, w którym poprzednie zmienne są są już zainicjowane.

(letrec ((nazwa wyrażenie-definiujące)
         ...)
   wyrażenie ...)

Oblicza wyrażenia-definiujące w środowisku, w którym widoczne są wszystkie (niezainicjowane) nazwy i wiąże je z nazwami w tym środowisku. Następnie oblicza kolejno wyrażenia i zwraca wartość ostatniego.

W wyrażeniach-definiujących mogą wystąpić odwołania do nazw. Musi być jednak możliwe ich obliczenie, przy założeniu, że nazwy te nie są związane z żadnymi wartościami. W praktyce oznacza to, że wartościami wyrażeń-definiujących powinny być procedury lub zbudowane z nich struktury danych (najczęściej są to po prostu lambda-wyrażenia).

(set! zmienna wyrażenie)

Przypisuje zmiennej wartość wyrażenia.

(begin wyrażenie wyrażenia ...)

Oblicza kolejno wyrażenia i zwraca wartość ostatniego. Przydatne do umieszczenia ciągu wyrażeń wszędzie tam, gdzie dozwolone jest tylko pojedyncze wyrażenie. Oczywiście wszystkie wyrażenia poza ostatnim powinny wywoływać efekty uboczne, w przeciwnym razie ich użycie nie ma sensu.

(delay wyrażenie)

Służy do leniwego obliczania. Tworzy i zwraca zamrożone wyrażenie. Obiekt taki może być argumentem force, co spowoduje obliczenie wyrażenia.

(force zamrożone-wyrażenie)

Jeśli zamrożone-wyrażenie nie było jeszcze obliczane, to jest ono obliczane, a otrzymana wartość zapamiętywana w nim i zwracana. W przeciwnym razie zwracana jest po prostu zapamiętana wartość.

1.12  Porównywanie

(eq? x y)

Zwraca #t jeśli wartością x i y jest ten sam obiekt.

(equal? x y)

Zwraca #t jeśli wartości x i y są tak samo zbudowane, co w zaadzie oznacza, że są tak samo wypisywane.

(= x y)

Tylko do porównywania liczb.

2  Typy danych

Pamięć dla dowolnych obiektów tworzonych w programie jest przydzielana i zwalniana automatycznie (służy do tego mechanizm odśmiecania).

Poznaliśmy już wartości logiczne #t i #f, służace do reprezentowania prawdy i fałszu. Omówimy teraz pokrótce inne typy danych występujące w Scheme.

2.1  Listy i pary

Parą nazywamy obiekt zawierający dwie składowe car i cdr, nazwane tak od funkcji dostępu do nich. Parę zawieerającą liczby 3 i 5 zapisuje się jako

(3 . 5)

Lista jest ciągiem elementów, zapisywanym jako

(1 4 9 16 25)
Wyróżnionym rodzajem listy jest lista pusta, zapisywana jako
()
Inne listy buduje się z par w taki sposób, że car każdej pary zawiera kolejny element listy, zaś cdr wskazuje na następną parę tworzącą listę (czyli na resztę listy). Jako cdr pary zawierającej ostatni element listy umieszcza się listę pustą. Tak więc listę (2 3 5 7) można również zapisać jako
(2 . (3 . (5 . (7 . ()))))
Tak więc lista jest w rzeczywistości albo parą albo listą pustą.

2.1.1  Operacje na parach i listach

(cons x y)

Tworzy i zwraca parę której pierwszym elementem jest wartość x, zaś drugim wartość y. Jeśli y jest listą, dołącza x na początek listy y.

(car l)

Zwraca pierwszy element pary lub listy l.

(cdr l)

Jeśli l jest parą, to zwraca jej drugi element. Dla listy (niepustej) zwraca resztę listy (tzn. listę bez pierwszego elementu).

(null? x)

Zwraca #t jeśli x jest listą pustą, w przeciwnym razie #f.

(list element ...)

Tworzy listę z podanych elementów.

(list-ref l k)

Zwraca k-ty element listy l.

(length l)

Zwraca długość (liczbę elementów) listy l.

(append list ...)

Tworzy nową listę powstałą ze złączenia podanych list.

(reverse l)

Zwraca nową listę zawierającą elementy listy l w odwrotnej kolejności.

(member obiekt l)

Przegląda listę l w poszukiwaniu elementu równego (equal?) obiektowi. Zwraca podlistę (,,ogon l''), rozpoczynającą się od znalezionego elementu. Jeśli takiego elementu nie ma zwraca #f.

(memq obiekt l)

Podobna do member, ale używa funkcji eq? do porównywania.

(set-car! para obiekt)

Przypisuje (destrukcyjnie) pierwszemu elementowi pary obiekt. W przypadku listy zmienia pierwszy element listy.

(set-cdr! para obiekt)

Przypisuje (destrukcyjnie) drugiemu elementowi pary obiekt. W przypadku listy zmienia resztę listy. Jeśli obiekt nie jest listą, to para przestanie być listą!

(append! lista ...)

Destrukcyjnie łączy ze sobą listy, tzn. zamienia cdr ostatniej pary tworzącej listę (gdzie poprzednio było ()) na dowiązanie do pierwszej pary następnej listy. Zwraca pierwszą listę (oczywiście trwale zmodyfikowaną).

2.1.2  Listy asocjacji

Listą asocjacji nazywamy listę składającą się z pozycji, będących parami postaci

(klucz . wartość)

(assoc klucz a-lista)

Znajduje pierwszą pozycję o podanym kluczu (używając equal? do porównywania) i zwraca ją. Jeśli takiej pozycji nie było, to zwraca #f.

(assq klucz a-lista)

Podobna do assoc, ale używa funkcji eq? do porównywania.

2.2  Symbole

Symbole są to obiekty bez żadnej struktury wewnętrznej, odróżniane na podstawie unikalnej nazwy (przypominają nieco elementy typów wyliczeniowych). W wielu implementacjach z każdym symbolem związana jest jego lista własności. Dla list własności określone są funkcje

(remprop symbol własność)     UW

Usuwa podaną własność z listy własności podanego symbolu. Własność musi być symbolem. > (putprop 'kawa 'kofeina? 'tak) > (getprop 'kawa 'kofeina?) TAK > (remprop 'kawa 'kofeina?) > (getprop 'kawa 'kofeina?) #f

2.3  Liczby i operacje arytmetyczne

(= x y)
(< x y)
(> x y)
(<= x y)
(>= x y)

Klasyczne predykaty arytmetyczne.

(max x ...)
(min x ...)

Zwracają maksimum i minimum z podanych liczb.

(gcd x ...)
(lcm x ...) 

Zwracają największy wspólny dzielnik oraz najmniejszą wspólną wielokrotność podanych liczb x's. Wynik jest zawsze nieujemny.

(+ x ...)
(* x ...)
(- x ...)

Klasyczne operacje arytmetyczne

(/ x ...)

Dzielenie, wyniki zależy od typów argumentów, np. dla liczb całkowitych będzie to liczba wymierna lub całkowita.

(- x)
(/ x)

Szczególne przypadki poprzednich: negacja i odwrotność.

(expt x y)

Potęgowanie, podnosi x do potęgi y.

(quotient n m)

Dzielenie całkowite.

(remainder dzielna dzielnik)

Reszta z dzielenia całkowitego, ma znak dzielnej.

(modulo dzielna dzielnik)

Reszta z dzielenia całkowitego, ma znak dzielnika.

(zero? x)
(positive? x)
(negative? x) 

Sprawdzają, czy x jest zerem, liczbą dodatnią, liczbą ujemną.

(even? x)
(odd? x)

Sprawdzają czy x jest liczbą parzystą lub nieparzystą.

(1+ x)
(1- x)

Skrótowy zapis dla (+ x 1) oraz (- x 1)

(abs x)

Wartośc bezwzględna liczby x.

(floor x)

Najbliższa liczbie x liczba całkowita [przewodnik-Z-G-2.gif] taka, że [przewodnik-Z-G-3.gif].

(ceiling x)

Najbliższa liczbie x liczba całkowita [przewodnik-Z-G-4.gif] taka, że [przewodnik-Z-G-5.gif].

(round x)

Najbliższa liczbie x liczba całkowita, w przypadku ,,remisu'' wybiera liczbę parzystą.

(sqrt x)

Pierwiastek kwadratowy z x.

(sin x)
(cos x)
(tan x)

Funkcje trygonometryczne.

(asin x)
(acos x)
(atan x) 

Odwrotne funkcji trygonometryczne.

(exp x)

Liczba niewymierna e podniesiona do potęgi x.

(log x)

Logarytm naturalny z x. (log 0) zwraca -inf.0.

2.4  Wektory

Wektory są to tablice jednowymiarowe, indeksowane zawsze od zera.

(make-vector n [wartość-początkowa])

Tworzy nowy wektor składający się z n elementów. Jeśli podano wartość-początkową, to wszystkie elementy są nią zainicjowane, w przeciwym razie wartości początkowe elementów nie są okreśłone.

(vector element ...)

Tworzy i zwraca wektor składający się z podanych elementów.

(vector-length wektor)

Zwraca długość vektora (liczbę jego elementów, czyli jego rozmiar).

(vector-ref wektor i)

Zwraca i-ty element vektora.

(vector-set! wektor i w)

Przypisuje i-temu elementowi wektora wartość w.

2.5  Funkcjonały (funkcje wyższych rzędów

(apply procedura lista-argumentów)

Wywołuje procedurę od podanej listy-argumentów.

(apply-if warunek procedura wyrażenie)     makro/UW

Z kolekcji zbyszek/utils.scm.

Najpierw oblicza się warunek. Jeśli wynikiem obliczenia warunku nie jest fałsz, to wywołuje się procedurę od tego wyniku i zwraca otrzymaną wartość. W przeciwnym razie oblicza się wyrażenie i zwraca jego wartość.

> (apply-if (assq 'c '((a b) (c d) (e f))) cadr 'niemożliwe) d

(map procedura lista lista ...)

Wywołuje się procedurę kolejno od pierwszych elementów list, drugich elementów list itd. Otrzymane wynki zwraca się w postaci listy. Listy muszą być tej samej długości, ma ich być tyle, ilu argumentów oczekuje procedura. Uwaga: kolejność obliczeń nie jest określona.

(for-each procedura lista lista ...)

Podobna do map, ale nie zwraca żadnego wyniku. Ponieważ jest używana dla efektów ubocznych, więc wykonuje obliczenia w ustalonej kolejności.

(filter predykat l)

Zwraca listę zawierającą tylko te elementy listy l, dla których predykat był spełniony.

(find-if pred list)

Zwraca pierwszy element listy spełniający predykat.

2.6  Wejście-wyjście

(write wyrażenie) lub (display wyrażenie)

Oblicza wyrażenie i wypisuje wynik.

(close-input-port port)

Zamyka port wejściowy port. Od tego momentu nie jest możliwe pobieranie zeń dalszych znaków.

(close-output-port port)

Zamyka port wyjściowy port. Od tego momentu nie jest możliwe wypisywanie nań żadnych znaków.

(fresh-line)     ???

Powoduje przejście do nowej linii na bieżącym porcie wejściowym o ile nie jest on aktualnie na początku nowej linii.

(flush-input [port])     UW

Pomija wszystkie znaki czekające na wskazanym porcie wejściowym (domyślnie bieżącym). Zwykle nie ma sensu dla plików, lecz jedynie dla portów ,,interakcyjnych''.


1 W realizacji MIT Scheme wprowadzono dodatkowy skrót notacyjny, pozwalający zapisać tę definicję nieco prościej

(define ((compose f g) x) (f (g x)))

Last modified: Friday, June 3rd, 2005
HTML conversion by TeX2page 2004-09-11