Scheme - Geißel der Menschheit

Vorwort

Weil mir die ganzen "Du hast funktionale Programmierung nicht verstanden"-Leute ständig Notizen in meinem Gästebuch hinterlassen, folgendes vorab:

Ich halte ausgesprochen wenig von Scheme! Warum?

  1. Scheme ist unübersichtlich. Ich kenne keine Sprache (Brainfuck und vielleicht Assembler Opcode ausgenommen) die chaotischer ist.
  2. Scheme-Interpreter sind langsam, weil kein richtiger Programmierer seine Zeit damit verschwendet, einen Interpreter für eine nutzlose Kunstsprache zu optimieren.
  3. Scheme ist interpretiert und erleidet dadurch nochmals Performancedefizite (ich habe mich schon eines besseren belehren lassen und eingesehen, dass irgendeine arme Seele wohl mal einen Scheme Compiler produziert hat. Dennoch habe ich von der Scheme-FAQ, die Prof. Görz selbst verlinkt hat, gelesen, dass Scheme u.a. deshalb so träge, langsam und groß ist, weil es beispielsweise erlaubt, das globale "+" zu überladen, oder Funktionen wie "cons" einfach in einem engeren Skopus zu überdefinieren - compile-time-Optimierungen fallen hier dann weg)
  4. Scheme ist nicht korrekter als andere Programmiersprachen. Zwar mag die Definition mathematisch vollständig und korrekt sein (als Laie ist mir das unmöglich nachzuvollziehen, daher nehme ich es einfach mal an, weil es mir in der Vorlesung so oft gesagt wurde) - aber die Implementierung ist genauso fehleranfällig wie die anderer Programmiersprachen.
  5. Scheme hat nicht mehr Funktionen als andere Programmiersprachen. Auch wenn uns in der Vorlesungen Funktionen höherer Ordnung (functions of higher order) als tolle Neuerung verkauft wurden, das ist nichts neues! Das kann man alles in C auch. Bestes Beispiel: Zur Not kann man sich einen Scheme-Interpreter in C programmieren!
  6. Scheme ist nicht typsicher, ganz einfach, weil es keine Typen gibt. In C entspräche das genau einem Typ: "int" (implizit "void*"), mit denen man auch alles realisieren kann... wenn man nur immer weiß, was denn da jetzt nun übergeben wird. Das erhöht nicht nur die Fehleranfälligkeit von Codes beträchtlich, sondern führt auch noch zu einer viel schwereren Wartbarkeit (wenn nicht exzessiv Kommentare verwandt wurden). Strong Typing bereits zur Compilezeit macht es dem Programmierer unmöglich Typfehler zu begehen, die in Scheme womöglich erst irgendwann zur Laufzeit auftreten würden.
  7. In Scheme kann man oft syntaktisch korrekten, aber semantisch inkorrekten Code erzeugen, indem man die Klammerung etwas verändert. Diese Fehler sind ausgesprochen schwierig zu finden.
  8. Scheme läßt sich nur sehr schlecht debuggen. Einen Fehler zu finden dauert oft ewig, oft liegt es dann wirklich nur an einer verkehrten Klammerung: Katastrophal
  9. [Dieser Punkt hat nichts mit Scheme selbst zu tun, sondern eher mit den Aufgaben, die in den Klausuren von Hr. Wilke gestellt wurden]: Die Klausuraufgaben sind nutzlos. So scheint eher die Qualität geprüft zu werden, sich durch endlos verwirrende Zeilen von Code zu wühlen (siehe Klausur 26.3.2003 Aufgabe 1c!) statt ein grundlegendes Verständnis für die Sprache abzuprüfen

Das ist natürlich nur meine persönliche Meinung. Scheme-Fetischisten können gerne ihre Flames in meinem Gästebuch hinterlassen, ich werde mich darüber sicher köstlich amüsieren.

Hier eine kleine Zusammenstellung der grundlegendsten Befehle und kurze Beispiele:
Befehl,
Datei
Beispiel und Wirkung
if
01_if.scm
Das "if" ist wohl die einfachste Konditionsanweisung in Scheme. Allerdings muss man die Klammerung beachten (was sonst...):
(if Bedingung IfTeil)
oder
(if Bedingung IfTeil ThenTeil)
Wichtig also: Der "IfTeil" oder "ThenTeil" wird nicht geklammert, wenn nur z.B. Zahlen übergeben werden sollen!
cond
02_cond.scm
Ein "cond" wäre in C ein "case". Syntaktisch recht einfach:
(cond
    (Bedingung1 Code1)
    (Bedingung2 Code2)
    ...
    (BedingungN CodeN)
    (else CodeElse)
)
Das "else" hierbei ist wirklich das "Wort" else. Ein Beispiel:
(cond
    ((= a 30) (display "A ist 30"))
    ((= a 40) (display "A ist 40"))
    ((= a 100) (display "A ist 100"))
    (else (display "A ist irgendwas anderes"))
)
unbenanntes let
03_let.scm
Ein unbenanntes "let" definiert eine neue Bindungsumgebung (Scope) und kann quasi als "Umbenennung" von Variablen innerhalb des Let-Body betrachtet werden. Mittlerweile habe ich eingesehen, dass let ganz nützlich sein kann, auch wenn man es ganz fies für Verwirraufgaben benutzen kann.
(let
    ((Alt1 Neu1) (Alt2 Neu2) (Alt3 Neu3))
    Body
)
Ein Verwirrbeispiel (wie es u.a. in Klausuren gerne drankommt):
(let
    ((a 'Scheme))
    ((let
        ((a 'Ist))
        (let
            ((a 'Dreck))
            (let
                ((b 'Stimmt))
                (BodyAnweisung)
            )
        )
    )
)
In diesem Konstrukt ist in der Zeile in der die "BodyAnweisung" ausgeführt wird a = 'Dreck und b = 'Stimmt, egal als was diese vorher definiert wurden. Der engste Skopus bindet!
benanntes let Ein benanntes "let" hat zusätzlich zu dem unbenannten let einen - ratet mal - einen Namen. Dieser Name ist aber nur im "Body" gültig und kann also nur für rekursive Funktionsaufrufe benutzt werden. Obwohl es so scheint, als ob das wirklich nutzlos ist kann man es sehr gut gebrauchen! Die Syntax:
(let
    Name
    ((Alt1 Neu1) (Alt2 Neu2) (Alt3 Neu3))
    Body
)
Und ein Beispiel Angenommen wir hätten eine Definition für den Sinus (siehe Klausuraufgabe März 2002 3b) gegeben, aber diese (nach außen sichtbare) definition reicht uns für die Rekursion nicht!
(define (sinus x)

)
Dann können wir ein benanntes "let" einführen:
; Hier mein zweiter Versuch (nach Achims Hilfe):
(define (sinus x)
    (let sinus2 ((sum 0) (pm 1) (nr 1))
        (let ((next (* pm (/ (expt x nr) (fak nr))) ))
            (display (list nr " " next " " sum))
            (newline)
            (
                if (< (abs next) epsilon)
                    (+ sum next)
                    (sinus2 (+ sum next) (* -1 pm) (+ 2 nr))
            )
        )
    )
)
let* Der Unterschied zwischen "let" und "let*" besteht darin, dass sich alle Definitionen im "Definitionsteil" eines let auf globale Variablen beziehen. Alle Definitionen im "Definitionsteil" eines let* beziehen sich zuerst auf andere, in der Definition etwaig redefinierte Variablen und erst dann auf die globale Definition. Ich weiß, beschissen zu erklären. Ein Beispiel:
(define x 123)

(let ((x 4)
      (y x))
      (+ x y)
)
=> 127
Weil x = 4 (die globale Bindung wird verdeckt) und y = "globales x" = 123.
(define x 123)

(let* ((x 4)
       (y x))
       (+ x y)
)
=> 8
Weil x = 4 (die globale Bindung wird auch hier verdeckt), aber y = 4 (durch das let* wurde hier die Definition von x bereits geändert).

Am einfachsten ist es wohl, wenn man sich let* als eine Verschachtelung von lets vorstellt (und das ist auch sytaktisch Äquivalent):
(define x 123)

(let* ((x 4)
       (y x))
       (+ x y)
)
=> 8

(let ((x 4))
    ((let ((y x))
        (+ x y)
    ))
)
=> 8
cons
04_cons.scm
Ein "cons" konstruiert ein geordnetes Paar. Da Scheme Listen als Verschachtelung geordneter Paare interpretiert, kann man damit also auch Listen erzeugen.
(cons 'Teil1 'Teil2) =
= (Teil1 . Teil2)
Der Punkt bedeuted hier also "geordnetes Paar mit erstem Element 'Teil1 und zweitem Element 'Teil2". Wenn man also lustig ist (und alle Scheme-Programmierer müssen sehr lustig sein, sonst hält man die Sprache ja nicht aus) kann man das auch verschachteln:
(cons 'Teil1 (cons 'Teil2 (cons 'Teil3 (cons 'Teil4 'Teil5)))) =
= ('Teil1 . ('Teil2 . ('Teil3 . ('Teil4 . 'Teil5)))) =
= ('Teil1 'Teil2 'Teil3 'Teil4 . 'Teil5)
Schaut einer Liste doch verdammt ähnlich, oder? Probieren wir mal
(cons 'Teil1 (cons 'Teil2 (cons 'Teil3 (cons 'Teil4 '())))) =
= ('Teil1 . ('Teil2 . ('Teil3 . ('Teil4 . '())))) =
= ('Teil1 'Teil2 'Teil3 'Teil4)
Das ist jetzt eine Liste! Eine Liste ist also nur eine verschachtelung geordneter Paare, bei denen das letzte Element einfach die leere Liste ("'()") ist.
car, cdr
05_carcdr.scm
car: Liefert das erste Element der übergebenen Liste (oder das erste Element eines Paars)
cdr: Liefert die restliche Liste (oder das zweite Element eines Paars)

Wenn wir also eine Liste haben '('Hand 'Fuß 'Kopf 'Bein) und machen darauf ein "car" dann kommt "'Hand" heraus. Ein "cdr" liefert "'('Fuß 'Kopf 'Bein)".

Verschachtelungen: car und cdr sind beliebig verschachtelbar. Diese verschachtelungen kann man abkürzen:
(car(cdr x)) = (cadr x)
(cdr(car x)) = (cdar x)
(car(cdr(cdr(cdr x)))) = (cadddr x)
(cdr(car(car(car x)))) = (cdaaar x)

(define x '('Muh 'Macht '('Die 'Tolle) 'Kuh))

(cadaddr x) = (car (cdr (car (cdr (cdr x))))) =

(car (cdr (car (cdr (cdr
    '('Muh 'Macht '('Die 'Tolle) 'Kuh)
))))) =

(car (cdr (car (cdr
    '('Macht '('Die 'Tolle) 'Kuh)
)))) =

(car (cdr (car
    '('('Die 'Tolle) 'Kuh)
))) =

(car (cdr
    '('Die 'Tolle)
)) =

(car
    '('Tolle)
) =

'Tolle
lambda Ein "lambda" fürt eine unbenannte Funktion ein.
(lambda
    (FormalerParameter1 FormalerParameter2 ... FormalerParameterN)
    (Body)
)
Wenn man "lambda" einfach so aufruft, passiert wenig. Eine unbenannte Funktion wird erzeugt, aber der Zeiger auf diese Funktion wird nirgendwo gespeichert.
(lambda
    (x y z)
    (+ x (* y z))
)

=> #[closure 81b6f00]
Jetzt kann man da natürlich etwas einsetzen...
((lambda
    (x y z)
    (+ x (* y z))
) 10 20 30)

=> 610
Oder sich den Zeiger in einem "define" Speichern
(define funktion (lambda
    (x y z)
    (+ x (* y z))
))

(funktion 10 20 30)

=> 610
null? list? pair? Man kann in Scheme ein Paar Sachen abfragen. Ob ein Objekt "null" ist, ob es eine Liste ist, oder ein geordnetes Paar. Beipsiele:
(define Liste '('Scheme 'Ist 'Scheisse))
(define Paar (cons 'Sehr 'Richtig!))
(define LeereListe '())
Es gilt also:
Liste      = ('Scheme 'Ist 'Scheisse)
Paar       = ('Sehr . 'Richtig)
LeereListe = ()
Nun zu den Abfragen:
(list? Liste)      = #t
(list? Paar)       = #f
(list? LeereListe) = #t

(pair? Liste)      = #t
(pair? Paar)       = #t
(pair? LeereListe) = #f

(null? Liste)      = #f
(null? Paar)       = #f
(null? LeereListe) = #t
Das ist nützlich sich zu merken...

Und hier meine Codebeispiele (und die, die in ner Klausur mal gefragt waren, abgetippt) zum herunterladen:
Version Geändert Download
0.06
  • Achim hat in seiner Lösung der Klausuraufgabe 3b noch etwas geändert, die neue Version ist hier drin
  • Mein Stack funktioniert immer noch nicht, aber jetzt enthält die Datei wenigstens eine Erklärung, warum!
  • Ein Beispiel angefügt, wie beliebig verschachtelte Listen zu traversieren sind
scheme-0.06.tar.bz2
0.05
  • Primzahlensuche enthalten (Verzeichnis Beispiele/)
  • Ein Versuch von mir, einen Stack zu implementieren (funktioniert nicht, push() tut nicht was es soll) und die Musterlösung von Hr. Klarner (Übungsblatt 7). Es gibt auch einen Testcase, den man gegen beide Lösungen linken kann. Wenn man meine (defekte) Implementierung testen will, gibt man im "Beispiele/" Verzeichnis "make joestack.scm" ein. Wenn man die (funktionierende) Klarner-Implementierung sehen will, "make klarnerstack.scm". Hoffentlich sieht jemand worans liegt (Achim? ;-))
scheme-0.05.tar.bz2
0.04
  • Aufgabe 2a und 3b der Klausur von 4.9.2001 nun enthalten
scheme-0.04.tar.bz2
0.03
  • Der Aufgabe 1 der Klausur vom September 2001 (4.9.2001) ist nun enthalten
scheme-0.03.tar.bz2
0.02
  • Die Klausuraufgabe 3b (März 2002) funktioniert endlich. Danke an Achim (Ayk2k3), der seine Lösung im Forum gepostet hat! Beide Lösungen sind enthalten. Die unterschiedlichen Lösungswege sind sicher interessant.
scheme-0.02.tar.bz2
0.01
  • Erstes Release
  • Ich bekomme meine Lösung für Klausuraufgabe 3b (März 2002) nicht zum Laufen! Kann mit bitte jemand helfen?
scheme-0.01.tar.bz2