Die Programmiersprache Scheme ist eine Lisp-Variante. Sie ist funktional, unterstützt jedoch auch andere Programmierparadigmen (z. B. imperative Programmierung).

Scheme zeichnet sich dadurch aus, dass nur wenige Programmierkonzepte durch die Syntax vorgegeben sind. In Scheme gibt es daher mehr Möglichkeiten ein Programm zu beschreiben als in vielen anderen Programmiersprachen.

Beispielsweise gibt es im Scheme-Standard keine Hilfsmittel zur objektorientierten Programmierung; solche können aber mittels Makros und λ-Ausdrücken in Scheme programmiert und zur objektorientierten Programmierung in Scheme verwendet werden: Scheme ist eine programmierbare Programmiersprache.

Entwickelt wurde Scheme von Gerald Jay Sussman und Guy Lewis Steele Jr. am Massachusetts Institute of Technology, wo auch die formale Spezifikation zur Verfügung steht, der sogenannte Revised Report. Die derzeit aktuelle Spezifikation ist R⁷RS.

Syntax und Semantik

Die Syntax von Scheme ist sehr regelmäßig und einfach. Grundlage ist eine vollständig geklammerte Präfix-Notation (siehe auch Polnische Notation). Ein Programm besteht aus Ausdrücken und Definitionen. Ausdrücke sind entweder Literale oder zusammengesetzte Ausdrücke, die einen Funktionsaufruf darstellen:

  (operator operand-1 operand-2 ... operand-n)

Jedes Element eines zusammengesetzten Ausdrucks ist wieder ein Ausdruck.

Die Bedeutung (oder Semantik) von Ausdrücken ist über ihre Auswertung definiert. Die Bedeutung (Semantik) eines literalen Ausdrucks ist der konstante Wert des Ausdrucks. Zum Beispiel hat die Zeichenfolge 2 den Wert der Zahl 2 und die Zeichenfolge #t hat den booleschen Wahrheitswert für „wahr“. Bei der Auswertung zusammengesetzter Ausdrücke muss der Ausdruck operator (in Anlehnung an mathematische Operatoren) zu einer Funktion auswerten. Rechts des Operators stehen beliebig viele Operanden, die wiederum einfache oder zusammengesetzte Formen sind.

Die Klammern sind damit von besonderer Bedeutung und können im Gegensatz zu den meisten anderen Programmiersprachen nicht beliebig gesetzt werden. Die zusammengesetzte Form

(foo 42)

etwa ist ein Ausdruck, der auf semantischer Ebene den Aufruf der an die Variable foo gebundenen Funktion mit dem Argument 42 bedeutet. Die Auswertung des Ausdrucks

(foo (42))

dagegen führt zu einem Fehler zur Laufzeit: Bei (42) handelt es sich um eine zusammengesetzte Form und die Semantik sieht die Anwendung des Operators vor. Da 42 allerdings eine Zahl und keine Funktion ist, kommt es zu einem Fehler.

Ein Vorteil der vollständig geklammerten Präfix-Notation besteht darin, dass diese Notation nur mit einer einzigen Präzedenz für alle Operatoren auskommt. Eine gängige Kritik an der Syntax von Scheme bezieht sich auf die hohe Zahl der Klammern, die die Erstellung und Bearbeitung des Quelltextes erschweren. Scheme-Programmierer begegnen dieser Schwierigkeit, indem sie Editoren verwenden, die die Bearbeitung von Scheme-Quelltexten in besonderer Weise unterstützen (zum Beispiel Emacs). Zu diesen Hilfen zählen die automatische Einrückung des Codes und die Markierung zusammengehöriger Klammerpaare während des Editierens.

Einige Scheme-Implementierungen, wie zum Beispiel Racket, erlauben abweichend vom Sprachstandard zusätzlich die Verwendung von eckigen Klammern. Dadurch soll die Übersichtlichkeit erhöht werden. Beispiel:

  (let ([x 42]
        [y 23])
     (+ x y))

Spezialform Lambda

Das Schlüsselwort lambda leitet die Spezialform für sogenannte Lambda-Ausdrücke ein. Ein Lambda-Ausdruck wertet zu einer Prozedur aus, die in Scheme ein Wert erster Klasse ist. Prozeduren können damit wie Werte anderer Typen im Programm verwendet werden, also etwa an Namen gebunden werden, als Argumente bei einem Prozeduraufruf übergeben werden oder von einer Prozedur zurückgegeben werden.

Definition der Spezialform lambda:

(lambda (argument) expression)

(lambda (x) (* x x)) ; Bildet das Quadrat von x

Aufruf der vom obigen Lambda-Ausdruck erzeugten Prozedur:

((lambda(x) (* x x)) 5) ; Bildet das Quadrat von 5
; (Rückgabe = 25)

Der Name dieser Spezialform geht auf den Lambda-Kalkül zurück.

Globale Definitionen

Eine Definition mit dem Schlüsselwort define bindet einen Wert an einen Namen. Der Name ist global gebunden, kann also an einer beliebigen Stelle im Programm nach der Definition verwendet werden. Da Prozeduren in Scheme ebenfalls Werte sind, können mit define auch globale Prozeduren definiert werden. Im folgenden Code-Abschnitt wird der Name a-number an die Zahl 42 gebunden und anschließend der Name square an eine Funktion, die eine Zahl quadriert:

  (define a-number 42)

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

Zur Definition globaler Prozeduren kann auch eine vereinfachte Notation verwendet werden, bei der der lambda-Ausdruck weggelassen wird. Obige Definition von square kann in abgekürzter Form wie folgt geschrieben werden:

  (define (square x)
    (* x x))

Ein Beispiel dafür, dass eine Funktion eine andere Funktion zurückgeben kann, liefert folgender Ausdruck:

(define (sum-with x)
    (lambda (y) (+ y x)))

Der Parameter x der Funktion sum-with bestimmt, wie sich die zurückgegebene Funktion verhält: Die zurückgegebene Funktion addiert ein Argument y genau um den in sum-with angegebenen Faktor x.

((sum-with 5) 1)
; Ergebnis: 6

Lokale Bindungen

Die Variablen- und Funktionsdeklaration gestaltet sich in Scheme etwas anders als in konventionellen Programmiersprachen. Zum einen müssen Variablen und Funktionen (Prozeduren) nicht an Bezeichner gebunden werden, zum anderen geschieht die Deklaration über Prozeduren, es gibt keine gesonderten Schlüsselwörter.

Zur Deklaration stehen die Formen define und let zur Verfügung, je nach Bedarf können anstelle von let auch die Variationen let* und letrec verwendet werden.

 (let ((name-1 ''ausdruck-1'')
       (name-2 ''ausdruck-2'')
       ...
       (name-n ''ausdruck-n''))
   ...
   ; Rumpf des let-Ausdrucks
   ; name-1, ..., name-n sind nur innerhalb des Rumpfes von '''let''' gebunden
   ...
 )

 (let ((a 3)
       (b (+ 10 12))
       (c (lambda (n) (* n 2))))
      (c (+ a b)))
 => 50

 (let ((a 1))
      (let ((a 0)
            (b a))
           b))
 => 1

  (let ((a (+ 1 1)) (b (+ 2 2)))
    (+ a b))

  ((lambda (a b) (+ a b)) (+ 1 1) (+ 2 2))

 (let ((a 1))
      (let* ((a 0)
             (b a))
            b))
 => 0

  (let* ((a (+ 1 1))
         (b (+ a 1)))
    (* a b))

  ((lambda (a)
     ((lambda (b) (* a b)) (+ a 1)))
   (+ 1 1))

  (letrec ((sum (lambda (lst s)
                 (if (null? lst)
                   s
                   (sum (cdr lst) (+ s (car lst)))))))
    (sum (list 1 2 3) 0))
  => 6

  (letrec ((even? (lambda (n)
                  (if (zero? n)
                    #t
                    (odd? (- n 1)))))
           (odd? (lambda (n)
                  (if (zero? n)
                    #f
                    (even? (- n 1))))))
    (even? 42))
  => #t

  (let ''name'' (''bindungen'') ''rumpf'')

  (let sum ((lst (list 1 2 3))
            (s 0))
    (if (null? lst)
        s
        (sum (cdr lst) (+ s (car lst)))))

 (define bezeichner ausdruck)

  (let ((x 5))

    (define (foo y)
      (bar x y))

    (define (bar a b)
      (+ (* a b) a))

    (foo (+ x 3)))

  (let ((x 5))
    (letrec ((foo (lambda (y) (bar x y)))
             (bar (lambda (a b) (+ (* a b) a))))
      (foo (+ x 3))))

Datentypen

 (define test
   (lambda (arg1 arg2)
         ... ))

 (define (test arg1 arg2)
  ...)

 (test wert1 wert2)

 (define (+ x y)
     (- x y))

  (cons 'sinn 42)

  '()
  (cons 1 '())
  (cons 1 (cons 2 '()))

(list 1 2 3)
(cons 1 (cons 2 (cons 3 '())))

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

  (define (map f lst)
    (if (null? lst)
       '()
       (cons (f (car lst)) (map f (cdr lst)))))

Fallunterscheidung

If

if wertet einen Test-Ausdruck aus und wertet je nach dessen Wahrheitswert den zweiten Operanden (Konsequente) oder den dritten Operanden (Alternative) aus. Der Wert des gesamten If-Ausdrucks ergibt sich aus der Auswertung der Konsequente bzw. Alternative. Nur wenn der Test-Ausdruck den Wert #f hat, wird die Alternative ausgewertet, andernfalls die Konsequente. D. h. jeder Wert außer #f gilt als logisch wahr.

Ein entsprechender Ausdruck sieht zum Beispiel so aus:

 (if (> x 0)
    'positive
    'not-positive)

Dieser Ausdruck wertet entweder zum Symbol 'positive oder zum Symbol 'not-positive aus. Da If ein Ausdruck ist, kann If innerhalb von Ausdrücken verwendet werden:

  (* 2 (if (> x max) max x))

Cond

Mit cond ist es möglich, mehrere Fälle zu unterscheiden. Ein Fall besteht aus einem Test und einer Konsequente. Die Fälle werden von links nach rechts überprüft. Liefert der Test eines Falles nicht #f zurück, wird die entsprechende Konsequente ausgewertet: Dieser Wert ergibt dann den Wert des gesamten cond-Ausdrucks. Trifft keiner der angegebenen Fälle zu, wird, falls vorhanden, der else-Fall ausgewertet. Ist kein else-Fall vorhanden, ist der Wert des cond-Ausdrucks nicht definiert. Beispiel:

 (cond ((= wert 65) 'a)
       ((= wert 66) 'b)
       (else 'unbekannt))

Schleifen

Scheme besitzt keinerlei Programmiersprachen-Konstrukte für Schleifen (allerdings wird in den automatisch inkorporierten „Scheme Standard Libraries“ beispielsweise mit dem do-Konstrukt die Möglichkeit von Schleifen angeboten). Schleifen werden in der Regel durch rekursive Funktionsaufrufe implementiert. Eine Endlosschleife sieht im einfachsten Fall so aus:

 (define (loop)
  (loop))

Ein häufig gezeigtes Beispiel, um dies zu demonstrieren, ist die Berechnung der Fakultät:

 (define (fak n)
    (if (= n 0) 1
        (* n (fak (- n 1)))))

Um dieses theoretisch ansprechende Konzept praktikabel umzusetzen, optimiert Scheme die endstämmige Rekursion (bzw. allgemeiner: alle endstämmigen Funktionsaufrufe). Bei der nicht-endstämmigen Rekursion leistet die Funktion nach dem Selbstaufruf noch Arbeit. Im Beispiel die Multiplikation:

 (fak 4)
 (* 4 (fak 3))
 (* 4 (* 3 (fak 2)))
 (* 4 (* 3 (* 2 (fak 1))))
 (* 4 (* 3 (* 2 (* 1 (fak 0)))))
 (* 4 (* 3 (* 2 (* 1 1))))
 (* 4 (* 3 (* 2 1)))
 (* 4 (* 3 2))
 (* 4 6)
 24

Hier wird während des Ablaufs zum Speichern der Zwischenergebnisse zunehmend mehr (Speicher-)Platz benötigt. Eine endstämmige (tail-recursive) Variante des obigen Beispieles wäre:

 (define (fak-iter n a)
  (if (= n 0) a
      (fak-iter (- n 1) (* n a))))

 (define (fak n)
  (fak-iter n 1))

Der Ablauf würde dann wie folgt aussehen:

 (fak 4)
 (fak-iter 4 1)
 (fak-iter 3 4)
 (fak-iter 2 12)
 (fak-iter 1 24)
 (fak-iter 0 24)
 24

Scheme erkennt, dass das Ergebnis des Prozeduraufrufs nur noch zurückgegeben wird, und kann somit für alle Prozeduraufrufe denselben Speicherplatz verwenden. Die zusätzliche Variable a in der Prozedur fak-iter akkumuliert die Zwischenergebnisse.

Kommentare

Kommentare werden durch ein Semikolon (;) eingeleitet und reichen bis zum Zeilenende.

Vergleich zwischen Scheme und LISP

Drei wesentliche Merkmale unterscheiden Scheme von Lisp:

• In Scheme gibt es die Funktion call-with-current-continuation. Sie erlaubt, die gegenwärtige Continuation (d. h. eine Art Ausführungszustand des laufenden Programms) als Variable zu verwenden. Damit ist es möglich, später im Programmablauf zur Stelle dieser Continuation zurück zu springen.
• Der Scheme-Standard schreibt proper tail recursion vor: Prozeduraufrufe in einer endrekursiven Position dürfen keinen Speicherplatz auf dem Aufrufstapel des Programms verbrauchen. Das bedeutet, dass eine unbegrenzte Anzahl an endrekursiven Aufrufen einer Prozedur möglich ist.
• Im Gegensatz zu LISP sind Makros in Scheme „hygienisch“: Innerhalb eines Makros eingeführte Bezeichner verdecken keine anderen Bezeichner der lexikalischen Umgebung außerhalb des Makros, also des aufrufenden Programms. Umgekehrt werden innerhalb eines Makros verwendete Bezeichner immer innerhalb der lexikalischen Umgebung des Makros aufgelöst, nicht außerhalb. Das bedeutet, dass die Bezeichner eines Makros nur für das Makro selbst sichtbar sind und das Makro nicht auf Bezeichner des übergeordneten Programms zugreifen kann, sowie dass das Programm nicht auf die internen Bezeichner des Makros zugreifen kann.

Implementierungen und Entwicklungswerkzeuge

Es steht eine große Zahl von Implementierungen der Programmiersprache zur Verfügung. Im Folgenden werden nur einige populäre Implementierungen erwähnt:

• Bigloo übersetzt Scheme-Code in verschiedene andere Sprachen: C, Java und .NET.
• Chicken ist eine Implementierung, die Scheme nach C übersetzt und deswegen auf praktisch allen Plattformen läuft. Sie stellt sowohl einen Interpreter als auch einen Compiler zur Verfügung und hat wegen der Anbindung zu C eine umfangreiche Bibliothek an Erweiterungen. Die Implementierung ist weitgehend R5RS-konform.
• Gambit C verfügt neben einem Scheme-Interpreter auch über einen der effizientesten Scheme-zu-C-Compiler.
• Gauche ist eine R7RS-konforme Implementierung. Sie ist als Skriptinterpreter für Entwickler und Administratoren konzipiert. Einige der Entwicklungsziele sind eine kurze Startzeit, eine eingebaute Systemschnittstelle, native Mehrsprachenunterstützung. Weiterhin können zahlreiche Erweiterungen eingebunden werden, z. B. für OpenGL und GTK+.
• GNU Guile ist ein Interpreter, der als Bibliothek eingebunden werden kann. Ziel ist in erster Linie, Programme leicht um Scripting-Fähigkeiten erweitern zu können.
• LispMe ist eine Implementierung für PalmOS-kompatible PDAs.
• Racket (früher PLT Scheme) ist eine verbreitete Implementierung, die neben einer großen Menge von Bibliotheken eine eigene Entwicklungsumgebung mit dem Namen DrRacket (früher DrScheme) beinhaltet. DrRacket ist speziell auf den Einsatz in der Programmieranfängerausbildung zugeschnitten und leicht zu bedienen. Racket enthält mehrere Compiler, die Racket-/Scheme-Code zu Byte- oder C-Code umwandeln.
• Scheme 48 ist eine komplett in Scheme geschriebene Scheme-Implementierung. Zum Bootstrapping wird ein statisch typisierter Scheme-Dialekt namens PreScheme verwendet. Scheme 48 übersetzt Scheme-Code in Bytecode, der in einem Speicherimage gesichert werden kann. Scheme 48 zeichnet sich besonders durch seine Möglichkeiten aus, Scheme-Code zu debuggen.
• SIOD. Ein kleiner, schneller Scheme-Interpreter, der unter anderem Verwendung in GIMPs ScriptFu bis Version 2.4 fand.

Literatur

• Hal Abelson, Gerald Jay Sussman: Structure and Interpretation of Computer Programs. McGraw-Hill, ISBN 0-07-000422-6
• Hal Abelson, Gerald Jay Sussman: Struktur und Interpretation von Computerprogrammen. Springer-Verlag, ISBN 3-540-42342-7
• R. Kent Dybvig: The Scheme Programming Language. The MIT Press, ISBN 0-262-54148-3 (4. Ausgabe online)
• Iain Ferguson: The Schemer’s Guide. Schemers Inc., ISBN 0-9628745-2-3
• Daniel P. Friedman, Matthias Felleisen: The Little Schemer. The MIT Press, ISBN 0-262-56099-2
• Daniel P. Friedman, Matthias Felleisen: The Seasoned Schemer. The MIT Press, ISBN 0-262-56100-X
• Daniel P. Friedman, Matthias Felleisen: The Reasoned Schemer. The MIT Press, ISBN 0-262-56214-6
• George Springer, Daniel P. Friedman: Scheme and the Art of Programming. The MIT Press, ISBN 0-262-19288-8
• Herbert Klaeren, Michael Sperber: Die Macht der Abstraktion: Einführung in die Programmierung. Teubner, ISBN 3-8351-0155-2
• Herbert Klaeren, Michael Sperber: Vom Problem zum Programm. Teubner, ISBN 3-519-22242-6
• Jacques Chazarain: Programmer avec Scheme. International Thomson Publishing, France, ISBN 2-84180-131-4
• Chris Hanson, Garald Jay Sussman: Software Design for Flexibility. The MIT Press, ISBN 978-0-262-04549-0

Weblinks

• schemers.org Materialsammlung zu Scheme
• Guy Steele, Gerald Sussman: The Original ‚Lambda Papers‘.
• SRFI (Scheme Requests for Implementation) stellt eine Sammlung von Funktionalitäten bereit, die sich praktisch als Standard-Bibliothek für Scheme-Implementierungen herausgebildet hat.

Einzelnachweise

1. ↑ Seite des Standards R7RS
2. ↑ Liste bekannter Implementierungen
3. ↑ Bigloo-Webseite
4. ↑ Gambit C-Webseite
5. ↑ Gauche-Webseite
6. ↑ LispMe-Webseite
7. ↑ Racket-Webseite
8. ↑ Scheme-48-Webseite
9. ↑ SIOD-Webseite (Memento vom 6. April 2007 im Internet Archive)