Benutzer:Rbb/Scheme-Entwurf

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.

Philosophie

Sprachumfang

Scheme beinhaltet nur elementare Operationen, was ihren den Ruf einer akademischen Sprache eingebracht hat. Für die Entwicklung größerer Projekte fehlt einiges, so z.B. ein einheitliches Modulkonzept, weitere Bibliotheksfunktionen, etc. Die komplette Spezifikation umfasst nur 50 Seiten.

Notation

Die Notation von Scheme Programmen erscheint vielen Programmierern ungewöhnlich oder gar befremdlich. Sie basiert auf dem Prinzip der S Ausdrücke.

Der Hintergrund dieser Notation ist, dass die meisten implementationen von Programmiersprachen die Sprache in eine Datenstruktur einlesen und diese verarbeiten (in einen Baum), der Aufbau dieses Baumes hängt bei diesen Compilern oder Interpretern von der Implementierung ab.

Scheme geht einen anderen Weg, das der Quelltext enthält bereits die Baumstruktur, welche nur eingelesen werden muss. Dies, so die Scheme und [[Lisp] Anhänger hat mehrere Vorteile:

• Einfacher Parser
• Quelltext
  • strukturiert
  • leicht lesbar
  • keine redundanten Sprachelemente
• Manipulation der Baumstruktur ist möglich.

In Scheme wird der Baum über Listen repräsentiert, die wieder Listen beinhalten, Listen werden von runden Klammern eingeschlossen, die einzelnen Elemente werden durch Leerzeichen getrennt.

Der Term 3*(2+3)+10+10/1 wird durch folgenden Baum dargestellt:

(+ (* 3 (+ 2 3)) 10 (/ 10 1))

Listen/Bäume die nicht ausführbar sind müssen im Quelltext "zitiert" werden. Dies geschieht meist mit dem Apostroph ':

'(1 2 3 4).

Konventionen

Es gibt einige Konventionen wie Scheme Code geschrieben werden sollte.

Bezeichner

Scheme ist case insensitive, d.h. es unterscheidet nicht zwischen groß und Kleinschreibung. Einige Implementationen treffen diese Unterscheidung jedoch. Es hat sich daher eingebürgert immer klein zu schreiben.

die Zeichen "-",">" und "?" sind in Bezeichnern erlaubt. Bezeichner die mehrere Worte enthalten trennen diese meist mit -, Konvertierende Prozeduren enthalten meist -> und Prädikate enden meist in einem Fragezeichen, z.B.:

write-char
string->list
positive?

Einrückung Folgende Regeln haben sich zur Einrückung von Scheme-Code bewährt:

1. Auf aufeinanderfolgende schließende Klammern folgt eine neue Zeile
2. Werden Argumente demnach auf mehrere Zeilen aufgetrennt, so bekommt jedes Argument seine eigenen Zeilen. Die Argumente werden an der Position des ersten Arguments ausgerichtet.
3. Mehrere aufeinanderfolgende schließende Klammern werden nicht getrennt.

Aus (+ (* 3 (+ 2 3)) 10 (/ 10 1)) wird also

(+ (* 3 (+ 2 3))
   10 
   (/ 10 1))

Sprachelemente

Operatoren

Anstelle Operatoren als eigene Sprachelemente zu definieren sind diese in Scheme wie jede andere Prozedur definiert. Daraus ergibt sich eine (ungewohnte) Präfixnotation.

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 case als weitere Möglichkeit, um mit Bedingungen zu arbeiten.

Prozeduren

Prozeduren sind das wichtigste Sprachelementen Schemes. Eine Prozedur wird auch als Funktion bezeichnet. Im Gegensatz zu vielen herkömmlichen Programmiersprachen müssen Prozeduren keinen Namen haben, sie verhalten sich wie normale Datentypen, und können aber müssen nicht zugewiesen werden. In Anlehnung an das Lambda-Kalkül definiert man Prozeduren mit lambda.

Beispiel: Eine Prozedur mit zwei Argumenten

(lambda (arg1 arg2)
        befehl1
        befehl2
        ...
        befehln
)

Diese Funktion kann z.B. mit define einen Namen zugewiesen bekommen.

Der Aufruf einer Funktion erfolgt folgendermaßen.

(Funktionsname arg1 ... argn)

Variablen

Scheme kennt mehrere Wege Variablen zu definieren.

define

Die Prozedur define definiert Variablen. Eine solche Definition sieht folgendermaßen aus:

(define var wert)

var ist ein Symbol, der Name der Variable, wert ist der zugewiesene Wert, Werte können in Scheme auch Prozeduren sein:

(define plus +)

Die Variablen sind innerhalb des Kontexts von define 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)))

(define) wird meist auf top-level Ebene benutzt um global Variablen und Funktionen zuzuweisen.

let, let* und letrec

let, let* und letrec sind eine weitere Möglichkeit Variablen einzuführen, im Gegensatz zu define betonen sie den funktionalen Charakter von Scheme Programmen. Sie unterscheiden sich im Gültigkeitsbereich der definierten Variablen.

let

let weißt folgende Struktur auf:

(let ((var1 wert1)
      (var2 wert2)
      ...
      (varn wertn))
     körper)

Die Variablen var1, var2, ... varn, mit den zugehörigen Werten wert1, wert2, ..., wertn gelten nur im Körper, d.h. die wert1 - wertn dürfen sich nicht aufeinander beziehen.

let

let* hat den selben Aufbau wie let, allerdings schachtelt es intern jedes var-wert-Paar in ein eigenes let, aus

(let* ((var1 wert1)
      (var2 wert2)
     körper)

wird

(let ((var1 wert1)) 
     (let ((var2 wert2))
          körper))

Somit kann sich wert2 also auf wert1 beziehen

letrec

Die Schachtelung der lets mit let* ermöglicht allerdings noch keine rekursiven Definitionen. Dies übernimmt letrec. Folgendes Beispiel zeigt die Verwendung von letrec anhand der Definition der Prozeduren gerade? und ungerade?

(letrec ((ungerade? (lambda (n)
                      (if (= n 1)
                        #t
                        (gerade? (- n 1)))))
         (gerade? (lambda (n)
                    (if (= n 1)
                      #f
                      (ungerade? (- n 1))))))
  (display (gerade? 12)))

Datentypen

Paare und Listen

Ein Paar ist eine Datenstruktur, die aus zwei Werten besteht. Gebildet wird ein Paar durch den Aufruf von cons.

(cons wert1 wert2)
=> (wert1 . wert2) (Kurzschreibweise)

Auf die Elemente eines Paars kann mit den Prozeduren car und cdr zugegriffen werden. car gibt den ersten Wert zurück, cons den zweiten. Die Namen car („content of address register“) und cdr („content of decrement register“) sind Operationen nachempfunden, die seinerzeit vom IBM 704 unterstützt wurden.

(car (cons 1 2)
=> 1

(cdr (cons 1 2)
=> 2

Durch Verkettung von mehreren Paaren kann man nun eine Liste erstellen:

(cons 1 (cons 2 (cons 3 4)))
=> (1 2 3 . 4) (Kurzschreibweise)

R5RS nennt diese Art von Listen "improper lists" (ungeeignete, unsachgemäße Listen), da man schlecht das Ende dieser Listen feststellen kann. Deswegen verwendet man einen Anker, die "leere Liste" um eine richtige Liste zu erhalten: ()

(cons 1 (cons 2 (cons 3 (cons 4 '())))) beziehungsweise '(1 2 3 4 . ())
=> (1 2 3 4) (Kurzschreibweise)

Datentypen

Weitere Datentypen neben Listen sind unter anderem:

• integer (ganze Zahlen)
• rational (Brüche)
• real (Kommazahlen)
• complex (komplexe Zahlen)
• symbol
• string (Zeichenkette)
• port

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.

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.

Kommentare

Kommentare werden durch ein Semikolon (;) eingeleitet.

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
• Klaeren, Sperber: Vom Problem zum Programm, Teubner, ISBN 3-519-22242-6

Weblinks

• schemers.org
• Scheme Requests for Implementation (SRFI)
• Structure and Interpretation of Computer Programs (SICP) - Dieses Scheme-Buch wird in Einsteiger-Programmierkursen am MIT und anderen Universitäten verwendet
• HowTo Design Programms - Einsteiger-Scheme-Buch