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 R7RS.Seite des Standards R7RS
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 let bindet mehrere Werte an die angegebenen Bezeichner. Diese Bindungen sind nur innerhalb des Rumpfes von let sichtbar. let hat die folgende Syntax: (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 ... )
Die Ausdrücke ausdruck-1 bis ausdruck-n werden in einer nicht spezifizierten Reihenfolge ausgewertet, bevor die resultierenden Werte an die jeweiligen Namen gebunden werden. Danach wird der Rumpf des let-Ausdrucks ausgewertet. Erst im Rumpf gelten die Bindungen name-1 bis name-n. Es ist insbesondere mit let nicht möglich, im Ausdruck ausdruck-i auf einen anderen Namen zuzugreifen, der im selben let-Ausdruck gebunden wird (vgl. let*).
Der Wert des letzten Ausdrucks im Rumpf ergibt den Wert des gesamten let-Ausdrucks. Da die Auswertungsreihenfolge der Ausdrücke ausdruck-i nicht festgelegt ist und theoretisch sogar alle Ausdrücke zeitgleich ausgewertet werden dürfen, spricht man auch von einem parallelen let.
Beispiele: (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 ist eine vereinfachte Syntax, die in einen Funktionsaufruf übersetzt wird. Beispiel: (let ((a (+ 1 1)) (b (+ 2 2))) (+ a b))
expandiert zu: ((lambda (a b) (+ a b)) (+ 1 1) (+ 2 2))
let* let* hat dieselbe Syntax wie let und eine ähnliche Semantik. Im Unterschied zu let ist bei let* die Reihenfolge, in der die Ausdrücke in den Name-Ausdruck-Paaren ausgewertet werden, festgelegt: Die Auswertung erfolgt von links nach rechts. Man spricht daher auch von einem sequentiellen let*. Im Unterschied zu let kann in den Ausdrücken (rechte Seiten der Name-Ausdruck-Paare) auf die Namen der weiter links stehenden Bindungspaare zugegriffen werden.
Beispiel: (let ((a 1)) (let* ((a 0) (b a)) b)) => 0
Wie let ist auch let* eine vereinfachte Syntax und wird in verschachtelte Funktionsaufrufe übersetzt: (let* ((a (+ 1 1)) (b (+ a 1))) (* a b))
expandiert zu: ((lambda (a) ((lambda (b) (* a b)) (+ a 1))) (+ 1 1))
letrec und named let letrec-Ausdrücke haben dieselbe Syntax wie let-Ausdrücke. Hinsichtlich der Sichtbarkeit der zu bindenden Namen gibt es jedoch einige Unterschiede. Die Namen (also die linken Seiten der Bindungspaare) können in jedem Ausdruck der Bindungspaare verwendet werden. Die vom let* her bekannte Einschränkung, dass sich die Namen in einem Ausdruck nur auf vorhergehende (also weiter links stehende) Namen beziehen können, fällt also weg. Insbesondere kann letrec zur Definition von lokalen rekursiven Funktionen verwendet werden. Beispiel: (letrec ((sum (lambda (lst s) (if (null? lst) s (sum (cdr lst) (+ s (car lst))))))) (sum (list 1 2 3) 0)) => 6
Es können auch wechselseitig rekursive Funktionen definiert werden: (letrec ((even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))) (odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))) (even? 42)) => #t
Eine Variante von letrec ist das sogenannte named let, das besonders zur Programmierung von Schleifen verwendet wird. Die Syntax ist (let ''name'' (''bindungen'') ''rumpf'')
, wobei bindungen die vom let her bekannten Paare aus Name und Ausdruck sind. Der Rumpf des named let wird als Rumpf einer Prozedur mit dem Namen name verwendet, die genau so viele Argumente hat wie Bindungspaare angegeben wurden. Das named let ist ein Makro, welches in den Aufruf dieser Prozedur name expandiert. Als Argumente werden die rechten Seiten der Bindungspaare verwendet. Das Beispiel für letrec kann mit einem named let folgendermaßen geschrieben werden: (let sum ((lst (list 1 2 3)) (s 0)) (if (null? lst) s (sum (cdr lst) (+ s (car lst)))))
define define wird meist benutzt, um auf globaler Ebene Funktionen und Konstanten zu deklarieren, aber es ist auch innerhalb des Rumpfes von Prozeduren verwendbar. Die Sichtbarkeit der so gebundenen Variablen beschränkt sich auf den Rumpf, in dem die Definition steht. define, die nicht auf globaler Ebene stehen, werden interne Definitionen genannt und gelegentlich der besseren Lesbarkeit wegen anstatt eines letrec verwendet.
Die Syntax ist: (define bezeichner ausdruck)
Der Ausdruck darf sich auch rekursiv auf bezeichner beziehen.
In diesem Beispiel werden foo und bar intern definiert. Beide Variablen sind nur innerhalb des Rumpfes des let-Ausdrucks sichtbar. (let ((x 5))
(define (foo y) (bar x y))
(define (bar a b) (+ (* a b) a))
(foo (+ x 3)))
Obiger Code entspricht dieser Version mit letrec: (let ((x 5)) (letrec ((foo (lambda (y) (bar x y))) (bar (lambda (a b) (+ (* a b) a)))) (foo (+ x 3))))
Datentypen Prozeduren Prozeduren gehören zu den wichtigsten Sprachelementen von Scheme. Sie können mit einem Lambda-Ausdruck (lambda) beschrieben werden. Da sie in Scheme wie jeder andere Datentyp behandelt werden, ist es möglich, sie mit let oder define an einen Bezeichner zu binden.
Beispiel: Eine Prozedur mit zwei Argumenten: (define test (lambda (arg1 arg2) ... ))
Es gibt eine vereinfachte Notation, mit der der define- und der lambda-Ausdruck zusammengefasst werden können: (define (test arg1 arg2) ...)
Aufgerufen wird diese Prozedur wie folgt: (test wert1 wert2)
Prozeduraufrufe müssen generell mit zwei Klammern eingeschlossen werden. Scheme betont die Rolle von Ausdrücken, die einen Wert haben, gegenüber Befehlen, die etwas tun. Deswegen ist es – im Gegensatz zu vielen anderen Sprachen – nicht nötig, den Ausdruck im Körper der Prozedurbeschreibung als Rückgabewert zu markieren. Im Gegenteil: Es sind besondere Konstrukte wie begin nötig, um Anweisungen ohne Rückgabe ihres Wertes auszuführen.
Natürlich gibt es eine Reihe von vordefinierten Prozeduren wie cons, car, cdr, +, -, *, <. Diese vordefinierten Prozeduren können neu definiert werden, wie folgendes Beispiel zeigt: (define (+ x y) (- x y))
+ würde jetzt nicht addieren, sondern subtrahieren.
Dadurch, dass die mathematischen Operatoren ebenfalls durch Prozeduren realisiert sind, ergibt sich für Berechnungen eine Präfixnotation. Scheme kennt keine Operatorhierarchie, alle Formeln sind eindeutig.
Paare und Listen