Scheme – funkcyjny język programowania, dialekt (wariant) Lispu, który stał się zaprojektowany na MIT przez Guy L. Steele-a oraz Geralda Jay Sussmana w latach 70. Jego główną ideą jest minimalizm, co oznacza, że sam język zawiera zaledwie podstawowe mechanizmy, a na ich bazie, już z użyciem Scheme, wykonywane są bardziej zaawansowane rozwiązania. Scheme nie jest czysto funkcyjnym językiem programowania, co oznacza, że dopuszczalne są efekty uboczne obliczeń. Scheme dopuszcza także wykonywanie programów w stylu proceduralnym oraz 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 oraz pierwszym który wymagał od implementacji optymalizacji wywołań z rekurencją ogonową. Scheme jest ustandaryzowany przez organizaję IEEE oraz przez dokumenty Revisedⁿ Report on the Algorithmic Language Scheme (RnRS), z których najczęściej implementowane są R5RS z 1998 roku oraz R6RS z 2007 roku.

Składnia

Składnia języka jest budowana z S-wyrażeń w sposób klasyczny dla Lispu. Zróżnicowane elementy języka, jak np. deklaracje oraz 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 albo nowego wiersza) oraz otoczona jest parą nawiasów (w poniektó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ń bywają przesłaniane analogicznie jak inne zmienne (zobacz przykład przy podstawieniu).

Identyfikatory

Identyfikatory da się tworzyć z liter alfabetu łacińskiego (A-Z oraz 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 potrafią zaczynać się liczby – czyli od cyfr albo jednego ze znaków: + – .. Od tej reguły też jednak są wyjątki: + – oraz ... są prawidłowymi identyfikatorami. Pewne implementacje potrafią 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 oraz znaku zapytania (np. vector?).
• nazwy funkcji, które modyfikują swoje argumenty, oznaczamy wykrzyknikiem !, np. set!
• operatory konwertujące jeden typ na odmienny oznaczamy typ1 → typ2
• funkcje działające na wektorach, znakach oraz łańcuchach oznacza się przedrostkami vector-, char- oraz 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 oraz rozciąga się aż do znaku nowej linii.

Podstawienia

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

(define zm wyr)

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

(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) oraz wylicza na 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 policzone.

(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 albo 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), albowiem 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 albo 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 oraz 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 albo wskazują na tę samą parę (w szczególności listę). Dwie listy o takich samych elementach zostaną wzięte za zróżnicowane jeśli powstały niezależnie od siebie (czyli jedna z nich nie przyjęła wartości przez podstawienie drugiej ani).

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

Wartości oraz operatory logiczne

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

Funkcje oraz 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 albo 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 oraz 9

(sum '(6 6 6 100))

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

Zamiast pętli wykorzystuje się możliwości stwarzane przez rekurencję, szczególnie przez rekurencję ogonową w której wywołanie rekurencyjne jest 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 bywa wykonywana bez odkładania parametrów na stos, czyli tak jak zwykła iteracja.

Makra

Za pomocą makr da się przetwarzać kod scheme jak dane. Makra są przetwarzane w czasie kompilacji. Makro musi zawracać 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 przeważajaca ilość implementacji udostępnia makro define-macro albo defmacro za pomocą definiuje się makra w stylu Common Lispa).

Znak ` (tylny apostrof) działa tak jak ' (cytat) z tym że wewnątrz da się użyć przecinka, który oblicza dane wyrażenie albo ,@ (przecinek małpa) który oblicza wyrażenie oraz 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))

Kontynuacje

Dość unikalną cechą Scheme jest wbudowane w język wsparcie dla kontynuacji. Za pomocą standardowej funkcji call-with-current-continuation albo 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 oraz pobranie/wywołanie kontynuacji niczym nie różni się od wywołania funkcji.

Przykładowe zastosowanie kontynuacji to implementacja współprogramów czy generatorów takich jak te w Pythonie czy C#. Przykładowa implementacja współprogramów:

(define (make-coroutine fn . args)
  (define (return . args) (call-with-current-continuation
                           (lambda (inner)
                             (set! k inner)
                             (apply outer args))))
  (define (k) (apply fn return args))
  (define outer #f)
  (lambda ()
    (call-with-current-continuation
     (lambda (outer-k)
       (set! outer outer-k)
       (k)
       (values)))))

Przykładowy generator atomów grafu:

 (define (tree-iterate yield datum)
  (cond ((null? datum))
        ((pair? datum)
         (tree-iterate yield (car datum))
         (tree-iterate yield (cdr datum)))
        (else (yield datum))))

Kontynuacje wykorzystywane są by nadać wrażenie synchroniczności typowo asynchronicznym operacjom takim jak np. zapytania HTTP^[1]. 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 oraz inne uchwyty^[2].

I/O

Wejście oraz 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) albo które potrafią przyjmować znaki. Podstawowe procedury odczytu oraz zapisu to read oraz write. Przykład zastosowania:

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

Standard języka opisuje także funkcje otwierające pliki oraz otwierające oraz zamykające porty. Funkcja czytająca linie z pliku oraz 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)))))))))

Fukcja zapisująca liste stringów do pliku

(define (write-lines list port)
  (let loop ((list list))
    (unless (null? list)
            (write-line (car list) port)
            (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ń oraz ulepszeń języka opracowywanych przez użytkowników.

Standard IEEE oraz raport RⁿRS

Język Scheme opisany jest w dwóch dokumentach^[3]:

• standard organizacji IEEE (The IEEE standard, 1178-1990 (R1995))
• raport R⁶RS (Revised⁶ Report on the Algorithmic Language Scheme), szósta wersja dokumentu RⁿRS

Raport RⁿRS jest powszechnie uważany za oficjalną oraz 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 albo 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 oraz Guy Lewis Steele Jr., twórcy języka. Raport R⁵RS stał się opublikowany 20 lutego 1998 roku, Do sierpnia 2007 roku trwały prace nad nową definicją języka – raportem R⁶RS^[4]. Wstępna wersja nowego raportu o numerze 5.97 był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 oraz ratyfikację nowego raportu – R⁶RS^[5].

Dokumenty SRFI

Dokumenty zgłoszone oraz przyjęte w procesie SRFI^[6]są sposobem na w miarę szybkie wprowadzanie przenośnych pomiędzy implementacjami języka rozwiązań ułatwiających wykonywanie programów. Aktualnie istnieje około 60 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, higieniczne makra, 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 bywają brane pod uwagę przy tworzeniu kolejnych wersji raportu RⁿRS.

Implementacje

• Guile implementacja napisana w języku C umożliwiająca zagnieżdzanie w języku C oraz jako języka skryptowego. Implementacja zbudowana przez FSF.
• Kawa implementacja języka scheme w języku Java.
• BiwaScheme implementacja w javascrypcie.
• Gauche implementacja działająca na platformie N*IX.
• Bigloo Kompilator na platformę .Net, JVM oraz do kodu natywnego.
• MIT Scheme implementacja zbudowana przez FSF
• Gambit kompilator oraz interpreter zbudowany przez FSF

Przypisy