Scheme
aus Wikipedia, der freien Enzyklopädie
Die Programmiersprache Scheme ist ein LISP-Dialekt. Sie unterstützt neben der funktionalen Programmierung auch eine Reihe von anderen Paradigmen – wie z. B. die imperative Programmierung. Scheme liegt das Prinzip zugrunde, dass eine Programmiersprache nicht dadurch beschreibungsmächtig wird, dass man Feature über Feature häuft, sondern dadurch, dass man unnötige Einschränkungen entfernt. Beispielsweise gibt es im Scheme-Standard keine Hilfsmittel zur objektorientierten Programmierung, es ist aber dank Makros und λ-Ausdrücken sehr einfach, sich solche in der Sprache zu programmieren: Scheme ist eine programmierbare Programmiersprache, die von den Programmierern bei Bedarf sehr flexibel erweitert werden kann.
Entwickelt wurde Scheme am Massachusetts Institute of Technology, wo auch die formale Spezifikation zur Verfügung steht, der so genannte Revised Report. Die derzeit aktuelle Spezifikation ist R5RS; ein erster Entwurf des Nachfolgers R6RS liegt aber bereits vor.
Drei wesentliche Merkmale unterscheiden Scheme von LISP. Zum einen gibt es in Scheme die Funktion call-with-current-continuation, die es erlaubt, die gegenwärtige Fortsetzung des Programms anzusprechen oder an eine Variable zu binden. Damit ist es möglich, durch Aufrufen der in jener Variablen gespeicherten Fortsetzung, später im Programm an die Stelle dieser Fortsetzung zurück zu springen. Zum anderen schreibt der Scheme-Standard proper tail recursion vor; das bedeutet, dass Prozeduraufrufe, die in einer endrekursiven Position stattfinden, keinen Speicherplatz auf dem Stack verbrauchen dürfen. Drittens sind Makros in Scheme im Gegensatz zu LISP hygienisch.
Inhaltsverzeichnis |
[Bearbeiten] Syntax
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, die alle als zusammengesetzte Formen dargestellt werden:
(operator operand-1 operand-2 ... operand-n)
Der Operator kann wieder eine zusammengesetzte Form, ein Schlüsselwort oder eine einfache Form, also z. B. ein Literal oder ein Variablenname sein. Rechts des Operators stehen beliebig viele Operanden, die wiederum einfache oder zusammengesetzte Formen sind. Zusammengesetzte Formen werden in runde Klammern eingeschlossen.
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. In anderen Programmiersprachen, wie etwa C dagegen hätte das zusätzliche Klammerpaar keine Bedeutung. Der Ausdruck
foo(42);
führt zur selben Berechnung wie der folgende Ausdruck:
foo((42));
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. Die Operatoren der Programmiersprache C sind dagegen in mehr als zwölf Präzedenzstufen eingeteilt.
Eine gängige Kritik an der Syntax von Scheme bezieht sich auf die verwirrend hohe Zahl der Klammern, die die Erstellung und Bearbeitung des Quelltextes erschwere. Scheme-Programmierer begegnen dieser Schwierigkeit in dem sie Editoren verwenden, 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 PLT Scheme, erlauben, abweichend vom Sprach-Standard, zusätzlich die Verwendung von eckigen Klammern. Dadurch soll die Übersichtlichkeit erhöht werden. Beispiel:
(let ([x 42]
[y 23])
(+ x y))
[Bearbeiten] Globale Definitionen
Eine Definition mit 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. Der folgende Code bindet den Namen a-number an die Zahl 42 und bindet den Namen square an eine Funktion, die eine Zahl quadriert:
(define a-number 42)
(define square
(lambda (x)
(* x x)))
Für die Definition von globalen Prozeduren gibt es noch spezielle Formen von define, die Definition von globalen Prozeduren erlauben, ohne lambda hinzuschreiben. Diese Formen sind jedoch nur Vereinfachungen um der Bequemlichkeit willen. Obige Definition von square kann in abgekürzter Form so geschrieben werden:
(define (square x) (* x x))
[Bearbeiten] 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.
[Bearbeiten] 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 resultierende Werte an die entsprechenden Namen gebunden werden. Dann wird der Rumpf des Let-Ausdrucks ausgewertet. Erst im Rumpf des let 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 daher 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))
[Bearbeiten] let*
let* hat die selbe 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 können in den Ausdrücken (rechte Seiten der Name-Ausdruck-Paare) die Namen aus den weiter links stehenden Bindungspaaren 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 Funktionsaufruf übersetzt:
(let* ((a (+ 1 1))
(b (+ a 1)))
(* a b))
expandiert zu
((lambda (a)
((lambda (b) (* a b)) (+ a 1)))
(+ 1 1))
[Bearbeiten] letrec und named let
letrec-Ausdrücke haben die selbe 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 kann fällt also weg. Insbesonder 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 (bindings) rumpf)
wobei bindings 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)))))
[Bearbeiten] define
define wird meist benutzt um auf globaler Ebene Funktionen und Konstanten zu deklarieren, aber es ist auch innerhalb des Rumpfes von Prozeduren verwendbar. Der 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))))
[Bearbeiten] Datentypen
[Bearbeiten] 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)
... ))
Der define und der lambda-Ausdruck können auch zusammengefasst werden:
(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 nicht - wie in vielen anderen Sprachen üblich - 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.
[Bearbeiten] Paare und Listen
Listen werden in Scheme-Programmen relativ häufig gebraucht. Wichtigster Baustein für Listen in Scheme sind Paare. Ein Paar ist eine Datenstruktur, die zwei beliebige Scheme-Werte enthält. Mit cons wird ein neues Paar erzeugt. Beispiel:
(cons 'sinn 42)
Dieser Aufruf von cons erzeugt ein neues Paar dessen erstes Feld das Symbol 'sinn enthält und dessen zweites Feld die Zahl 42. Auf das erste Feld eines Paares kann mit der eingebauten Funktion car (sprich: „carr“) zugegriffen auf das zweite Feld mit cdr (sprich: „kudder“). Die Namen car („content of address register“) und cdr („content of decrement register“) sind ein historischer Zufall, haben sich aber so erhalten. Sie beziehen sich auf Operationen, die seinerzeit bei der ersten Lisp-Implementation auf der IBM 704 benutzt wurden. Die eingebauten Funktionen set-car! und set-cdr! setzen die Werte der entsprechenden Felder eines Paares auf einen neuen Wert. Das Typ-Prädikat pair? gibt genau dann #t (für wahr) zurück, wenn es auf ein Paar, also einen mit cons erzeugten Wert angewendet wurde.
Die Definition von Listen ist induktiv: Die leere Liste, geschrieben '(), ist eine Liste. Außerdem ist ein Paar, dessen cdr eine Liste ist eine Liste. Durch die Definition ergibt sich, dass eine Liste aus Paaren besteht: Im car-Feld eines Paares steht ein beliebiger Wert, im cdr-Feld das Paar, das das nächste Listenelement enthält. Das Ende der Liste ist erreicht, wenn cdr-Feld die leere Liste zu finden ist, was sich mit der eingebauten Funktion null? überprüfen lässt. Beispiele für Listen:
'() (cons 1 '()) (cons 1 (cons 2 '()))
Für die Erzeugung von Listen gibt es außerdem noch die komfortable Funktion list, die eine beliebige Anzahl von Argumenten nimmt und diese als Liste zurückgibt. (list 1 2 3) erzeugt eine Liste, die diesen Aufrufen von cons entspricht:
(cons 1 (cons 2 (cons 3 '())))
Funktionen, die auf Listen verarbeiten sind meist rekusive Funktionen. Mit dieser Funktion lässt sich zum Beispiel die Länge einer Liste bestimmen:
(define (length lst)
(if (null? lst)
0
(+ 1 (length (cdr lst)))))
Scheme-Programmierer machen von der Möglichkeit die Felder eines Paares mit set-car! oder set-cdr! zu ändern fast nie Gebrauch. Die Verarbeitung von Listen erfolgt fast immer rein funktional, d. h. aus Listen werden neue Listen erzeugt. Ein Beispiel ist diese Funktion map, die eine Funktion f auf alle Elemente einer Liste anwendet:
(define (map f lst)
(if (null? lst)
'()
(cons (f (car lst)) (map f (cdr lst)))))
[Bearbeiten] Weitere Datentypen
Weitere Datentypen sind unter anderem:
- integer (ganze Zahlen, beliebige Stellenzahl)
- rational (Brüche, beliebige Genauigkeit)
- real (Dezimalzahlen)
- komplexe Zahlen
- Symbole
- Zeichen
- Strings (Zeichenkette)
- Paare
- Vektoren
- Port (Repräsentation für Eingabe/Ausgabe-Geräte, Dateien, etc)
- Boolean
Wahr und falsch werden durch #t und #f dargestellt, wobei Scheme jedoch nur #f (in veralteten Implementierungen nur ein Synonym für leere Liste '()) als logisch falsch interpretiert; alle anderen Werte gelten als wahr.
[Bearbeiten] 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))
[Bearbeiten] Schleifen
Scheme besitzt keinerlei Programmiersprachen-Konstrukte für Schleifen. Schleifen werden in der Regel durch rekursive Funktionsaufrufe implemeniert. 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
Wie man sieht 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 den selben Speicherplatz verwenden. Die zusätzliche Variable a in der Prozedur fak-iter akkumuliert die Zwischenergebnisse.
[Bearbeiten] Kommentare
Kommentare werden durch ein Semikolon (;) eingeleitet und reichen bis zum Zeilenende.
[Bearbeiten] Implementierungen und Entwicklungswerkzeuge
Es steht eine große Zahl von Implementierungen der Programmiersprache zur Verfügung (Liste bekannter Implementierungen). Im folgenden werden nur einige populäre Implementierungen erwähnt:
- PLT Scheme ist eine verbreitete Implementierung, die neben einer großen Menge von Bibliotheken eine eigene Entwicklungsumgebung mit den Namen DrScheme beinhaltet. DrScheme ist speziell auf den Einsatz in der Programmieranfängerausbildung zugeschnitten und leicht zu bedienen. PLT Scheme enthält mehrere Compiler, die Scheme-Code nachBytecode, Nativecode oder C-Code übersetzen.
- Scheme48 ist eine komplett in Scheme geschriebene Scheme-Implementierung. Zum Bootstraping wird ein statisch getypter Scheme-Dialekt names 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 Scheme-Code zu debuggen aus.
- Gambit C verfügt neben einem Scheme-Interpreter auch über einen der effizientesten Scheme-zu-C-Compiler.
[Bearbeiten] Literatur
- Abelson, Sussman: Structure and Interpretation of Computer Programs, McGraw-Hill, ISBN 0070004226
- Abelson, Sussman: Struktur und Interpretation von Computerprogrammen, Springer-Verlag, ISBN 3540423427
- Dybvig: The Scheme Programming Language, The MIT Press, ISBN 0-262-54148-3
- Ferguson, Iain: The Schemer's Guide, Schemers Inc., ISBN 0-9628745-2-3
- Friedman, Felleisen: The Little Schemer, The MIT Press, ISBN 0-262-56099-2
- Friedman, Felleisen: The Seasoned Schemer, The MIT Press, ISBN 0-262-56100-X
- Springer, Friedman: Scheme and the Art of Programming, The MIT Press, ISBN 0-262-19288-8
- Klaeren, Sperber: Vom Problem zum Programm, Teubner, ISBN 3-519-22242-6
- Chazarain, Jacques: Programmer avec Scheme, International Thomson Publishing France, ISBN 2841801314
[Bearbeiten] Weblinks
- schemers.org Materialsammlung zu Scheme
- The Original 'Lambda Papers' by Guy Steele and Gerald Sussman
[Bearbeiten] Einführungen
- HowTo Design Programs (HTDP) - Einsteiger-Scheme-Buch
- Structure and Interpretation of Computer Programs (SICP) - Dieses Scheme-Buch wird in Einsteiger-Programmierkursen am MIT und anderen Universitäten verwendet.
- Teach Yourself Scheme in Fixnum Days - Online-Kurs für Einsteiger.
