Scheme

Scheme

Logo języka
Pojawienie się	1970
Paradygmat	wieloparadygmatowy, funkcyjny, proceduralny, meta
Typowanie	dynamiczne, silne
Aktualna wersja stabilna	R7RS-small (2013) [±]
Twórca	Guy L. Steele Jr., Gerald Jay Sussman
Platforma sprzętowa	wieloplatformowy
Platforma systemowa	wieloplatformowy
Strona internetowa

Scheme – funkcyjny język programowania, dialekt (wariant) Lispu, który został zaprojektowany na MIT przez Guy L. Steele'a i Geralda Jaya Sussmana w latach 70. Jego główną ideą jest minimalizm, co oznacza, że sam język zawiera jedynie podstawowe mechanizmy, a na ich bazie, już z użyciem Scheme, tworzone są bardziej zaawansowane rozwiązania. Scheme nie jest czysto funkcyjnym językiem programowania, co oznacza, że dopuszczalne są efekty uboczne obliczeń. Scheme umożliwia również tworzenie programów w stylu proceduralnym i obiektowym. Jest to język o dynamicznym systemie typów. Zarządzanie pamięcią jest w pełni automatyczne. Scheme był pierwszym dialektem Lispu, który używał zmiennych leksykalnych i pierwszym, który wymagał od implementacji optymalizacji wywołań z rekurencją ogonową.

Scheme jest ustandaryzowany przez organizację IEEE oraz przez specyfikacje Revisedⁿ Report on the Algorithmic Language Scheme (RⁿRS), z których najczęściej implementowane są R⁵RS z 1998 roku, R⁶RS z 2007 roku oraz najnowszy R⁷RS (small) z 2013 roku. Przy czym wersja R⁶RS ma mieszane opinie w gronie programistów używających języka Scheme. Głównym powodem negatywnych opinii na temat tej specyfikacji jest jej duża objętość. Dodatkowo istnieją oficjalne rozszerzenia języka tzw. SRFI (ang. Scheme Request For Implementation). Niektóry SRFI stały się częścią standardów RⁿRS.

Składnia

Składnia języka jest budowana z S-wyrażeń w sposób klasyczny dla Lispu. Różne elementy języka, jak np. deklaracje i definicje, warunki, podstawienia, selekcje itp. przedstawione są w postaci list. Lista taka składa się z elementów oddzielonych tzw. białymi znakami (czyli znakami odstępu, tabulacji lub nowego wiersza) i otoczona jest parą nawiasów (w niektórych implementacjach dopuszcza się też w celu poprawienia czytelności kodu nawiasy kwadratowe). Pierwszym elementem listy jest identyfikator (nazwa) funkcji, kolejnymi są argumenty.

Elementy języka

Podstawowe operacje matematyczne

Działania, tak jak wszystkie inne funkcje, zapisujemy w notacji prefiksowej, to znaczy znak działania przed argumentami:

(+ 2 (* 2 2))
(+ 1 2 3 4)

W istocie działania matematyczne to zwykłe funkcje.

Można przekazywać im więcej niż 2 argumenty. Operatory działań mogą być przesłaniane podobnie jak inne zmienne (zobacz przykład przy podstawieniu).

Identyfikatory

Identyfikatory można tworzyć z liter alfabetu łacińskiego (A-Z i a-z), cyfr (0-9) oraz znaków ! $ % & * + – . / : < = > ? @ ^ _ ~. Dodatkowo, aby uniemożliwić mylenie identyfikatorów ze stałymi liczbowymi, niedozwolone są identyfikatory rozpoczynające się od znaków, od których mogą zaczynać się liczby – czyli od cyfr lub jednego ze znaków: + – .. Od tej reguły też jednak są wyjątki: + – i ... są prawidłowymi identyfikatorami. Niektóre implementacje mogą dopuszczać też użycie innych identyfikatorów, które rozpoczynają się od tych znaków, ale nie są liczbami. Dodatkowo przyjmuje się następujące konwencje tworzenia identyfikatorów:

• predykaty kończą się znakiem zapytania ?. W szczególności zapytania o typ zmiennej tworzymy z nazwy typu i znaku zapytania (np. vector?).
• nazwy funkcji, które modyfikują swoje argumenty, oznaczamy wykrzyknikiem !, np. set!
• operatory konwertujące jeden typ na inny oznaczamy typ1 → typ2
• funkcje działające na wektorach, znakach i łańcuchach oznacza się przedrostkami vector-, char- i string-. Czasem stosowane jest to też do operacji na listach.

Komentarze

Komentarz do kodu źródłowego (tekst pomijany przez interpreter/kompilator) rozpoczyna się od średnika i rozciąga się aż do znaku nowej linii. W specyfikacji R⁷RS istnieją także komentarze S-Wyrażeń dzięki składni hash średnik, które poprzedza dane wyrażenie.

Podstawienia

W języku tym istnieje wiele sposobów przypisania zmiennym wartości.

(define zm wyr)

Deklaruje zmienną zm i nadaje jej wartość wyrażenia wyr. Zmienna jest dostępna do końca bloku, w którym została zdefiniowana. Próba ponownego zdefiniowania tej samej zmiennej skończy się błędem (nie we wszystkich implementacjach).

(let ((zm_1 wyr_1) ... (zm_n wyr_n))
  wyrazenie)

ustawia wartość zmiennych (zm_1, ... zm_n) na wyniki odpowiadających im wyrażeń (wyr_1, ... wyr_n) i wylicza na ich podstawie wartość wyrażenia wyrazenie. Zmienne nie są dostępne poza obrębem let. Jeśli zmienne te istnieją, to zostaną przesłonięte.

(let* ((zm_1 wyr_1) ... (zm_n wyr_n))
  wyrazenie)

Znaczenie podobne do let, jednak przy wyliczaniu wartości wyrażeń wyr_2, ...wyr_n brane są pod uwagę wartości wcześniej ustawione let-em.

(set! zmienna wartosc)

Podstawienie podobne do znanych ze „zwykłych” języków programowania. Zmienia wartość zmiennej na nową, najczęściej policzoną w jakimś wyrażeniu. Zmienna musi być zadeklarowana (np. przez define lub let albo być parametrem funkcji tworzonej przez lambda).

Przykłady:

(let ((x (+ 3 5))
      (y (- 4 7)))
  (* x y))

Wartość wyrażenia

(let ((+ *)) (+ 3 8))

będzie równa 24 (= 3 * 8), ponieważ wewnątrz let + oznacza *.

Pytania o typ

Zmienne są typowane dynamicznie, czyli zmienna nie ma ustalonego typu – jest takiego typu jak wartość, którą przechowuje. Czasem musimy więc sprawdzić czy rzeczywiście przechowuje ona wartość odpowiedniego typu (np. przed użyciem w funkcji, które przyjmują wartości tylko określonego typu lub chcąc wybrać sposób potraktowania danych zależnie od typu)

(number? 5)
(number? "foo")
(string? "foo")

Pytania o typ składają się z nazwy typu i znaku zapytania (?).

Równość

Równość dwóch zmiennych sprawdzamy predykatem eq?. Dwie zmienne są równe jeśli są tą samą liczbą, tym samym symbolem lub wskazują na tę samą parę (w szczególności listę). Dwie listy o takich samych elementach zostaną wzięte za różne jeśli powstały niezależnie od siebie (czyli jedna z nich nie przyjęła wartości przez podstawienie drugiej).

(eq? "foo" "bar")
(eq? 5 (+ 2 3))
(eq? (eq? 2 3) (eq? 3 4))

Wartości i operatory logiczne

Wartości logiczne prawda i fałsz reprezentowane są odpowiednio symbolami #t i #f. Możemy na nich wykonywać np. operacje or (alternatywa lub), and (koniunkcja i) oraz not (negacja nie). Mają one jednak odrobinę szersze zastosowanie.

Funkcje i rekurencja

Funkcje definiuje się za pomocą konstrukcji:(lambda (lista argumentów) (ciało funkcji)), przy czym może ona zostać wartością zmiennej (np. przez define lub let) albo zostać użyta bez nadawania jej nazwy.

(define fact
  (lambda (x)
    (if (= x 0)
        1
        (* x (fact (- x 1))))))

(define fib
  (lambda (n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib (- n 1)) (fib (- n 2)))))))

(define sum
  (lambda (x)
    (cond ((null? x) 0)
          (else (+ (car x) (sum (cdr x)))))))

(fact 14)

(fib 10)

(map (lambda (x) (* x (+ 1 x))) ;;; obliczy listę wartości wyrażenia x*(x+1)
     '(1 3 6 9))                ;;; kolejno dla 1, 3, 6 i 9

(sum '(6 6 6 100))

(sum (map fib '(1 2 3 4)))

;; zamiast tworzyć procedurę sum, możemy również użyć apply:
(apply + '(6 6 6 100))

Zamiast pętli wykorzystuje się możliwości stwarzane przez rekurencję, szczególnie przez rekurencję ogonową w której wywołanie rekurencyjne występuje jako ostatnie wyrażenie, funkcje z rekurencją ogonową zamieniane są na pętle przez kompilator.

Przykład funkcji z rekurencją ogonową do obliczania silni.

(define (! n)
  (let iter ((n n) (product 1))
    (if (zero? n)
        product
        (iter (- n 1) (* product n)))))

Tak zdefiniowana rekurencja może być wykonywana bez odkładania parametrów na stos, czyli tak jak zwykła iteracja.

Makra

Za pomocą makr można przetwarzać kod scheme jak dane. Makra są przetwarzane najczęściej w czasie kompilacji. Makro musi zwracać kod jako dane (tzn. listę symboli), które zostaną obliczone (według specyfikacji języka scheme makra tworzy się za pomocą define-syntax, let-syntax, syntax-rule ale większość implementacji udostępnia makro define-macro lub defmacro, za pomocą którego definiuje się makra w stylu Common Lispa).

Znak ` (tylny apostrof) działa tak jak ' (cytat) z tym że wewnątrz można użyć przecinka, który oblicza dane wyrażenie lub ,@ (przecinek małpa) który oblicza wyrażenie i usuwa zewnętrzne nawiasy.

"`" jest to skrót do funkcji quasiquote, "," – to skrót do unquote a ",@" to skrót do unquote-splicing

(define-macro (for params . body)
  (let ((iter (gensym)) (step (if (= (length params) 4)
                                  (cadddr params)
                                  1)))
    `(let ,iter ((,(car params) ,(cadr params)))
          (if (<= ,(car params) ,(caddr params))
              (begin
                ,@body
                (,iter (+ ,(car params) ,step)))))))

                                        ; przykład użycia
(for (i 1 10) (display i) (newline))

(define-macro (when test . body)
  `(if ,test (begin ,@body)))

(define-macro (for-list params . body)
  (let ((iter (gensym)) (list (gensym)))
    `(let ,iter ((,(car params) (car ,(cadr params)))
                 (,list (cdr ,(cadr params))))
          (when (not (null? ,(car params)))
            ,@body)
          (when (not (null? ,list))
            (,iter (car ,list) (cdr ,list))))))

;; przykład użycia
(for-list (i (list 10 20 30))
          (display i)
          (newline))

Makra Higieniczne

Problem z makrami lispowymi jest taki, że rozwinięcie makra jest wstawiane w kod użytkownika. Nawet gdy używamy funkcji gensym do generowania symboli, w kodzie pozostają nazwy funkcji i form specjalnych (lub makr), które mogą być nadpisane przez użytkownika, co wcale nie musi być takie rzadkie. Użytkownik może użyć zmiennej, która wcześniej może być nazwą makra lub funkcji użytej w rozwinięciu.

Przykład:

(define-macro (unless test . body)
  `(if (not ,test) (begin ,@body)))

(let ((not (lambda (x) x)))
   (unless #t
      (display "x")
      (newline)))

Mimo że makro unless dostaje wartość #t, zostanie wyświetlona wartość "x". Inny bardziej realny przypadek to użycie funkcji list wewnątrz makra, która często jest używana jako nazwa zmiennej, która przechowuje przetwarzaną listę. Aby móc korzystać z makr lispowych, które używają funkcji list trzeba by zapisywać każdą listę jako lst aby przypadkiem nie zepsuć makra. W języku Common lisp problem kolizji rozwiązano dzięki użyciu systemu pakietów oraz dwóch przestrzeni nazw (dla zmiennych i funkcji). W języku Scheme inaczej rozwiązano ten problem, specyfikacja języka Scheme wprowadziła makra higieniczne, które używają języka wzorców (ang. pattern language):

(define-syntax unless
   (syntax-rules ()
      ((_ test rest ...)
       (if (not test) (begin rest ...)))))

(let ((not (lambda (x) x)))
   (unless #f
      (display "x")
      (newline)))

Higieniczność makr, oznacza że nie jest możliwa zmiana zachowania makra, za pomocą kodu użytkownika. Zmiana definicji funkcji not, nie ma wpływu na makro higieniczne. Implementacja makr higienicznych, może polegać na automatycznej zmianie nazw wszystkich wolnych zmiennych (np. na wartości zwracane przez funkcje gensym). Jest to jednak pewne uproszczenie, mechanizm jest o wiele bardziej skomplikowany. Zamiana nazw musi brać pod uwagę konstrukcje, które tworzą nowe zmienne jak let czy lambda.

Makra higieniczne, ze specyfikacji R5RS, nie dawały wszystkich możliwości jakie miały marka lispowe, np. makra anaforyczne:

(define-macro (aif test if else)
  `(let ((it ,test)) (if it ,if ,else)))

(let ((alist '((foo . 10) (bar . 20))))
  (aif (assoc 'foo alist)
     (cdr it)))
;; => 10

W powyższym kodzie makro aif udostępnia zmienną it, która zawiera testowaną wartość, dlatego nie trzeba dwa razy wywoływać tego samego wyrażenia. Niektóre implementacje języka Scheme umożliwiają pisanie mark anaforycznych, za pomocą makra syntax-case. Makra te jednak nie są częścią specyfikacji języka. Innym sposobem użycia makr anaforycznych, w języku Scheme, jest użycie Biblioteki SRFI-139.

Kontynuacje

Dość unikalną cechą Scheme jest wbudowane w język wsparcie dla kontynuacji. Za pomocą standardowej funkcji call-with-current-continuation lub call/cc możliwy jest dostęp do następnego wyrażenia podlegającego ewaluacji. W przykładowym wyrażeniu (foo (bar (baz) (xenu))) kontynuacją (bar (baz) (xenu)) będzie (foo x) gdzie x jest wartością zwracaną przez (bar ...).

Szczególną cechą kontynuacji jest możliwość wywołania ich wielokrotnie czy zapisania w zmiennej do użycia na później, po odwinięciu stosu. W przeciwieństwie do funkcji biblioteki standardowej C setcontext, wzorcowa implementacja Scheme nie powoduje żadnego narzutu wydajności przy pobraniu czy wywołaniu kontynuacji. Stosowany jest tutaj styl przekazywania kontynuacji, gdzie stos nie istnieje i pobranie/wywołanie kontynuacji niczym nie różni się od wywołania funkcji.

Przykładowe zastosowanie kontynuacji to implementacja natychmiastowego wyjścia z funkcji.

(define (find item lst)
  (call-with-current-continuation
   (lambda (return)
     (for-each (lambda (x)
                 (if (equal? x item)
                     (return x))
                 (display x)
                 (newline))
               lst))))

(let ((result (find 'x '(a b d x y z f))))
  (display "wynik: ")
  (display result)
  (newline))

W powyższym przykładzie mamy funkcje for-each, która iteruje po wszystkich elementach listy. Ale dzięki dostępowi do kontynuacji jest możliwe natychmiastowe zakończenie funkcji po znalezieniu szukanego elementu.

Inny przykład to implementacja współprogramów czy generatorów takich jak te w Pythonie czy C#. Przykładowa implementacja generatora:

(define (make-coroutine-generator proc)
  (define return #f)
  (define resume #f)
  (define yield (lambda (v)
                  (call/cc (lambda (r)
                             (set! resume r)
                             (return v)))))
  (lambda ()
    (call/cc (lambda (cc)
               (set! return cc)
               (if resume
                   (resume (if #f #f))  ; void? or yield again?
                   (begin (proc yield)
                          (set! resume (lambda (v)
                                         (return (eof-object))))
                          (return (eof-object))))))))

Powyższy przykład pochodzi z implementacji SRFI-158.

Przykładowy generator liczb 0, 1 oraz 2 z dokumentu SRFI-190.

(define counter (make-coroutine-generator
                 (lambda (yield)
                   (do ((i 0 (+ i 1)))
                     ((<= 3 i))
                     (yield i)))))

Użycie takiego generatora może wyglądać tak:

(define (print-numbers)
  (let ((i (counter)))
    (if (not (eof-object? i))
        (begin
          (display i)
          (newline)
          (print-numbers)))))

(print-numbers)

Ten sam kod może służyć do tworzenia nieskończonych generatorów.

Kontynuacje wykorzystywane są także by nadać wrażenie synchroniczności typowo asynchronicznym operacjom takim jak np. zapytania HTTP. Niestety, przez obecność kontynuacji jako typ danych pierwszej klasy w Scheme nie jest możliwe orzeknięcie czy dany blok kodu będzie jeszcze wywoływany, komplikując zamykanie zasobów takich jak deskryptory plików i inne uchwyty.

Jeszcze innym przykładem użycia kontynuacji jest implementacja wyrażenia try..catch.

I/O

Wejście i wyjście w języku Scheme reprezentowane jest przez porty. Są to obiekty, które (odpowiednio) są źródłem znaków (obiektów typu char) lub które mogą przyjmować znaki. Podstawowe procedury odczytu i zapisu to read i write. Przykład zastosowania:

(write (+ (read) (read)))

Standard języka opisuje również funkcje otwierające pliki i otwierające i zamykające porty. Funkcja czytająca linie z pliku i zwracająca listę (działająca w interpreterze Guile).

(define (read-lines filename)
  (call-with-input-file filename
    (lambda (file)
      (let ((line ""))
        (let loop ((result '()))
          (set! line (read-line file))
          (if (eof-object? line)
              result
              (loop (append result (list line)))))))))

Funkcja zapisująca listę stringów do pliku

(define (write-line string port)
  (display string port)
  (newline port))

(define (write-lines filename list)
  (call-with-output-file filename
    (lambda (file)
      (let loop ((list list))
        (unless (null? list)
        (write-line (car list) file)
        (loop (cdr list)))))))

;; unless to jest macro
(define-macro (unless test . body)
  `(if (not ,test)
       (begin
         ,@body)))
;; lub
(define (write-lines list port)
  (for-each (lambda (line)
              (write-line line port))
            list))

Definicja języka

Język Scheme ciągle się rozwija, dwa główne elementy tego rozwoju to dokument opisujący rdzeń języka (RⁿRS) oraz proces zgłaszania dokumentów SRFI (Scheme Requests for Implementation) czyli propozycji rozszerzeń i ulepszeń języka opracowywanych przez użytkowników.

Standard IEEE i raport RⁿRS

Język Scheme opisany jest w dwóch dokumentach:

• standard organizacji IEEE (The IEEE standard, 1178-1990 (R1995)).
• raport RⁿRS (Revisedⁿ Report on the Algorithmic Language Scheme), gdzie n to wersja dokumentu, najnowsza to R⁷RS small.

Raport RⁿRS jest powszechnie uważany za oficjalną i podstawową definicję języka: programiści piszą programy zgodne z RⁿRS, o implementacjach języka Scheme mówi się, że są w całości lub częściowo zgodne z raportem RⁿRS.

Pierwszy dokument opisujący język Scheme powstał w roku 1975: „Scheme: an interpreter for extended lambda calculus”, autorami byli Gerald Jay Sussman i Guy Lewis Steele Jr., twórcy języka. Raport R⁵RS został opublikowany 20 lutego 1998 roku, Do sierpnia 2007 roku trwały prace nad nową definicją języka – raportem R⁶RS. Wstępna wersja nowego raportu o numerze 5.97 została poddana pod głosowanie osób, które zgłosiły zainteresowanie procesem tworzenia dokumentu. Głosowanie zakończyło się 12 sierpnia, 29 sierpnia ogłoszono wyniki głosowania i ratyfikację nowego raportu – R⁶RS. Wersja R⁷RS w wersji mniejszej (ang. small) została zatwierdzona w 2013 aktualnie trwają prace nad wersją większą (ang. large).

Dokumenty SRFI

Dokumenty zgłoszone i przyjęte w procesie SRFI (ang. Scheme Requests for Implementation) są sposobem na w miarę szybkie wprowadzanie, przenośnych między implementacjami języka, rozwiązań ułatwiających tworzenie programów. Istnieje ponad 100 dokumentów SRFI. Opisują one sposób zaimplementowania takich funkcji czy rozwiązań jak np. sposób notacji tablic, strumienie, obsługa wyjątków, rozszerzenia makr higienicznych, wykonywanie skryptów języka Scheme w systemach operacyjnych UNIX czy obsługa wielowątkowości. Rozwiązania te nie wchodzą w skład oficjalnej definicji języka, jednak mogą być brane pod uwagę przy tworzeniu kolejnych wersji raportu RⁿRS.

Implementacje

• Guile – implementacja napisana w C, stworzona przez FSF.
• Kawa – implementacja w języku Java.
• BiwaScheme – implementacja w JavaScript.
• Gauche – implementacja działająca na platformie N*IX.
• Bigloo – kompilator na platformę .NET Framework, JVM oraz do kodu natywnego.
• MIT/GNU Scheme – implementacja stworzona przez FSF.
• Gambit – kompilator i interpreter, zapoczątkowany jako praca doktorska na Uniwersytecie Brandeisa, prace nad nim były kontynuowane na Uniwersytecie Montrealskim.
• Racket – implementacja udostępniona na licencji LGPL.

Linki zewnętrzne

• scheme.org – oficjalna strona języka (ang.)
• lips.js.org – strona zawiera bookmarklet z wierszem poleceń (REPL) (ang.)
• www.gnu.org/software/guile – strona implementacji Guile (ang.)
• www.biwascheme.org – strona implementacji BiwaScheme (ang.)
• practical-scheme.net/gauche – strona implementacji Gauche (ang.)
• www-sop.inria.fr/mimosa/fp/Bigloo – strona implementacji Bigloo (ang.)