Scheme

Die Programmiersprache Scheme ist ein LISP-Dialekt. Sie unterstützt sowohl funktionale als auch 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 derzeitige Spezifikation ist R5RS, an R6RS wird gearbeitet.

Inhaltsverzeichnis
1 Sprachelemente

1.1 Kommentare
1.2 Notation
1.3 Variablen
1.4 Prozeduren
1.5 Listen
1.6 Datentypen
1.7 Bedingungen
1.8 Schleifen

2 Literatur
3 Weblinks

Sprachelemente

Kommentare

Kommentare werden durch ein Semikolon (;) eingeleitet.

Notation

Scheme verwendet die Präfixnotation. Beispielsweise schreibt man nicht (10 - 8) sondern (- 10 8).

Variablen

Variablen werden durch define, let und einigen anderen Anweisungen definiert, wobei durch eine Definition mit define globale Variablen entstehen. 

(define var wert)

Variablen, die durch let definiert werden, sind nur innerhalb dieses Befehls gültig. 

(let ((var1 wert1)
       (var2 wert2)
       ...
       (varn wertn))
   ...
   ; var1, ..., varn sind nur innerhalb von let gültig 
   ...
 )

In Prozeduren darf define nur vor dem ersten Ausdruck verwendet werden. Also zum Beispiel: 

(define x
   (lambda ()
     (define y 5)
     (display y)
     (newline)))

Auch hier ist die definierte Variable (wie bei let) nur im Körper der Prozedur gültig.

Prozeduren

Prozeduren gehören zu den wichtigsten Sprachelementen von Scheme. In der Regel erstellt man sie mit dem lambda-Befehl. Prozeduren können durch define einer Variable zugeteilt werden.

Beispiel: Eine Prozedur mit zwei Argumenten 

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

Der lambda-Befehl kann auch weggelassen werden: 

(define (test arg1 arg2)
  ...)

Aufgerufen wird diese Prozedur wie folgt: 

(test wert1 wert2)

Prozeduren müssen generell mit zwei Klammern eingeschlossen werden. Der Rückgabewert wird durch die letzte gültige Anweisung bestimmt. Beachtlich dabei ist, dass Scheme automatisch den geeignetsten Datentyp wählt.

Man unterscheidet zwei Arten von Prozeduren: Diejenigen, die durch den Programmierer erstellt werden, und jene, die bereits vordefiniert sind (set!, car, cdr, +, -, *, /). Diese vordefinierten Prozeduren können neu definiert werden, wie folgendes Beispiel zeigt: 

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

+ würde jetzt nicht addieren, sondern subtrahieren.

Listen

Listen werden in Scheme-Programmen relativ häufig gebraucht. Eine leere Liste wird mit '() gebildet. Durch cons kann eine Liste erweitert werden. Das ' gibt Scheme an, dass der nachfolgende Ausdruck nicht interpretiert werden soll, sondern dass eine Liste dargestellt wird.

Beispiel: 

(cons 5 '()) 
 
(cons 1 (cons 2 (cons 3 (cons 4 '()))))

Dies kann wie folgt abgekürzt werden : 

(list 1 2 3 4)


Listen in Scheme sind mit binären Bäumen vergleichbar. Die linke Seite wird mit car dargestellt, die rechte Seite mit cdr (sprich: „cudder“). Durch die Anwendung mit car erhält man für gewöhnlich einen Wert; cdr enthält einen Zeiger auf das nächste Element oder auf die leere Liste.

Beispiel: 

(car '(1 2 3 4))  ;ergibt  als Ausgabe: 1
 
(cdr '(1 2 3 4))  ;ergibt als Ausgabe: (2 3 4)

Die Namen car („content of address register“) und cdr („content of decrement register“) sind Operationen nachempfunden, die seinerzeit vom IBM 704 unterstützt wurden.

Datentypen

Weitere Datentypen neben Listen sind unter anderem:


Wahr und falsch werden durch #t und #f dargestellt, wobei Scheme jedoch nur #f (Synonym für leere Liste "()") als wirklich falsch interpretiert; alles andere gilt als wahr.

Bedingungen

If:

If wertet einen Befehl oder einen Wert aus, und führt je nach Ergebnis (#t oder #f) eine entsprechende Anweisung aus. 

(if (eq? wert #t)
     (display "Der Wert ist wahr")
     (display "Der Wert ist falsch"))

Cond:

Mit Cond ist es möglich mehrere Fälle abzufangen. Trifft keiner dieser Fälle ein, so wird eine else-Behandlung für alle sonstigen Möglichkeiten eingeleitet. 

(cond ((= wert 1) (display "Der Wert ist 1"))
       ((= wert 2) (display "Der Wert ist 2"))
       (else (display "Der Wert ist weder 1 noch 2)))

Darüber hinaus gibt es noch when und case als weitere Möglichkeit, um mit Bedingungen zu arbeiten.

Schleifen

Schleifen werden in Scheme für gewöhnlich durch eine Rekursion erreicht. Ein häufiges gezeigtes Beispiel, um dies zu demonstrieren, ist die Berechnung der Fakultät. 

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

Darüber hinaus unterstützt Scheme das Konzept der tail-recursion. Das Problem der "normalen" Rekursion ist, daß man das Ergebnis des rekursiven Aufrufs weiterverwendet. Dies wird bei der tail-recursion verhindert. Anschaulich passiert folgendes: 

(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 braucht man während des Ablaufs zum Speichern des Zwischenergebnisses immer mehr Platz, da die aufrufende Prozedur nicht verlassen wird. Eine tail-rekursive Variante des obigen Beispieles wäre: 

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

Obiger 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, daß das Ergebnis des Prozeduraufrufs nicht mehr benutzt wird, und kann somit für alle Prozeduraufrufe den selben Speicherplatz verwenden. Möglich wird dies durch die zusätzliche Variable in der Prozedur fak-iter, die das Zwischenergebnis speichert.

Literatur

Weblinks

See also: Scheme, Binärer Baum, Fakultät, Funktionale Programmierung, IBM 704, Imperative Programmierung, LISP, Lambda-Ausdruck, Makro, Massachusetts Institute of Technology