Einführung
Mit Scheme zu programmieren ist für Anfänger sehr einfach! Wenn man das berühmte Hello-World-Eingangsbeispiel machen will, so muss man Dr. Scheme starten und in den Quellcodebereich (display "Hello World") eingeben, das war's! Es gibt keine Rahmenanweisungen wie in Java oder C++, die man erst eingeben müsste, bevor man die eigentlichen Anweisungen eingeben kann.

Aufbau
Schon an der Anweisung (display "Hello World") kann man den grundlegenden Aufbau eines jeden Scheme-Befehls sehen. Alle Anweisungen stehen in Klammern. Die Anweisung steht immer am Anfang, die Attribute dahinter. Die Anweisung ist hier display, damit wir im unteren Fensterbereich ein Text ausgegeben, der Text wird in Anführungszeichen eingeschlossen danach der Prozedur display übergeben. Ein Attribut ist also eine Information, die die Anweisung benötigt, um das zu tun, was sie tun soll. Der Fachbegriff für eine solche Anweisung ist Prozedur. In Scheme werden folgerichtig alle Anweisungen durch Prozeduren repräsentiert.

Variablen
display kann nicht nur Text ausgeben, sondern auch den Inhalt von Variablen, Variablen sind Objekte die Daten (Zahlen, Buchstaben) speichern. Es sind also Umschreibungen, die kürzer sind und sich besser merken lassen als die eigentlichen Zahlen oder Operationen. Will man den Inhalt einer Variable ausgeben, so muss die display-Anweisung folgendermaßen aussehen: (display erg)
Die Variable wird also ohne Anführungszeichen eingeschlossen; wollten Sie dies in Dr. Scheme ausprobieren, so käme es zu einem Fehler. Warum? Na, was ist denn eigentlich erg? Sie wissen es nicht, so weiß es auch Scheme nicht! Wir müssen also erst einmal definieren, was erg eigentlich sein soll.

define
Mit define wird Scheme gesagt, was erg sein soll. Man spricht vom deklarieren oder definieren der Variable erg. In Scheme sieht das so aus: (define erg 123)
Die Anweisungen stehen also wie gehabt in Klammern, dann define, dann den Variablennamen und den Wert, den erg haben soll. In unserem Beispiel hat erg den Wert 123, wenn wir also die Anweisung von vorhin, also (display erg) darunter schreiben, dann schreibt uns Scheme 123.

Prozeduren
Wenn Sie schon einmal programmiert haben, dann werden Sie sich fragen, warum ich schon jetzt mit Prozeduren beginne. Aber in Scheme läuft eigentlich nichts ohne Prozeduren, so dass ich sie schon jetzt einführen werde.
Meistens besteht ein Programm nicht nur aus einer oder zwei Zeilen, sondern aus sehr vielen. In der Praxis wird dann so verfahren, dass die Anweisungen zusammen gefasst werden: zu Prozeduren.
Neben einer besseren Lesbarkeit, bieten Prozeduren auch noch den Vorteil, dass man Sie nur in bestimmten Fällen aufrufen kann, mehrmals aufrufen kann oder mit verschiedenen Werten aufrufen kann. Erst durch Prozeduren kann man richtige Programme schreiben.
Prozeduren haben auch Namen, wie bei Variablen muss man sie deshalb erst definieren, bevor man Sie benutzen kann. Also wird wie bei Variablen die Anweisung define benötigt. Diesmal ist die Syntax, also die Art und Weise wie man das Programm zu schreiben hat, damit Scheme es versteht, jedoch anders:
(define (sum x1 x2)
(+ x1 x2))
Damit hätten wir unsere erste Prozedur geschrieben, erraten Sie mal was Sie macht? Na, Sie addiert x1 und x2, erkennen Sie es jetzt? Wir beginnen mit define, nun schreiben wir aber den Prozedurnamen und die Attribute in eine Klammer, jede Anweisungszeile, die Scheme ausführen soll muss ganz selbstverständlich in Klammern stehen. Zum Schluss muss noch die Klammer von define geschlossen werden. Allgemein sieht die Syntax also so aus:
(define (prozedurname attribut1 attribut2)
(Anweisung1)
(Anweisung2))
Natürlich können Sie auch nur ein Attribut oder beliebig viele Attribute einsetzen, das gleiche gilt natürlich auch für die Anweisungen.
Noch würde aber nichts passieren, man muss erst die Prozedur aufrufen, und zwar indem man (sum 2 3) eingibt. Für x1 wir 2 eingesetzt und für x2 3, somit ist das Ergebnis 5 (2+3=5).

Bedingungsabfrage
Erst wenn man verschiedene Zustände unterscheiden kann, kann man auf Ereignisse reagieren. Und Programme die nicht auf Ereignisse reagieren können haben nur sehr wenige Einsatzmöglichkeiten. Dafür gibt es natürlich in Scheme eine Möglichkeit, die erste ist if, die zweite cond.

if-Bedingungsabfrage
Die if-Anweisung sieht so aus: (if (= Bedingung true) (dann) (sonst))
Ist also die Begingung in der Klammer wahr, wird der Inhalt der ersten Klammer ausgeführt, ansonsten der der anderen Klammer. Natürlich kann man bei Bedarf den sonst-Fall weglassen. Als Bedingung werden meistens Vergleiche wie =,<,> gewählt, dabei gilt wie immer die Präfixnotation. Es kann immer nur eine Anweisungszeile je Fall ausgeführt werden.
Natürlich können die Bedingungen auch mit logischen Operatoren wie and, or oder not verknüpft werden. Mit and kann man Bedingungen so verknüpfen, dass beiden Bedingen wahr sein müssen, damit der dann-Fall ausgeführt wird. Bei der Verknüpfung mit or muss nur eine der Bedingungen stimmen, damit der dann-Fall ausgeführt wird. Mit not kann man schließlich das Gegenteil der Bedingung abfragen, stimmt die Bedingung also nicht, so wird der dann-Fall ausgeführt, stimmt die Bedingung dann der sonst-Fall.

cond-Bedingungsabfrage
Wer mehr als eine Möglichkeit überprüfen will, sollte lieber die zweite Möglichkeit der Bedingungsabfrage einsetzen, nämlich cond.
Mit cond können mehrere Zustände überprüft werden, so kann z.B. unterschieden werden, ob eine Zahl kleiner, gleich oder größer ist und dem entsprechend unterschiedlich reagiert werden. Syntaktisch müsste eine cond-Bedingungsabfrage so aussehen:
(cond ((= Bedingung true) dann)
(else Anweisung)
Im Anweisungsbereich können auch mehrere Anweisungen stehen, die ausgeführt werden sollen, wenn die Bedingung zutrifft. Möchte man eine Anweisung ausführen, wenn keine der Bedingungen zutrifft, so sollte man noch einen else-Fall einbauen, der immer dann eintritt, wenn alle vorherigen Bedingungen false sind.

Anweisungen mit begin zusammenfassen
Bei der if-Bedingungsabfrage hatte ich erwähnt, dass man immer nur eine Anweisung je Fall ausführen kann. Möchte man mehr als eine Anweisung ausführen und möchte nicht die flexiblere cond-Bedingungsabfrage einsetzen, dann bleibt einem nur die Möglichkeit die Anweisungen mit beginn zusammenzufassen. Die Syntax sieht so aus:
(begin (Anweisung1) (Anweisung2))
Damit kann man beliebig viele Anweisungen zusammenfassen.

Rekursion
Im Zusammenhang mit Prozeduren gibt es ein weiteres wichtiges Konzept: die Rekursion. Bei der Rekursion wird ein komplexes Problem in viele kleine Teilprobleme zerteilt, die sich einzeln recht einfach lösen lassen. Sind die Teilprobleme gelöst werden deren Ergebnisse wieder zu einem Ganzen zusammengesetzt und das komplexe Problem ist gelöst.
Für die Rekursion setzt man eine Kombination aus Prozeduren und der Bedingungungsabfrage ein, zuerst wird das Problem in Teilprobleme zerteilt, diese Teilprobleme werden der Reihe nach von einer Prozedur bearbeitet, in dem die Prozedur mit veränderten Werten nochmals aufgerufen wird. Da irgendwann alle Teilprobleme gelöst sind, muss es aber auch eine Möglichkeit geben, die kontinuierlichen Aufrufe der Prozedur wieder zu unterbrechen. Dies geschieht mit einer Bedingungsabfrage, die eine Abbruchbedingung überwacht, wenn Sie eintritt, wird abgebrochen und die Teilprobleme zu einem Ganzen zusammengesetzt und ausgegeben.

Beispiel für eine Rekursion
Die Berechnung der Fakultät einer Zahl bietet sich als gutes Beispiel für eine Rekursion an. Bei der Rekursion werden alle Elemente innerhalb eines Intervalls miteinander multipliziert, also für 3! (! steht für Fakultät) ist 1*2*3 zu rechnen, als Ergebnis erhalten wir also 6.
Ich schreibe mal den Scheme-Code für die rekursive Berechnung der Fakultät, wir werden den Code anschließend analysisieren:

(define (fakultaet n)
(if (= n 0)
1
(* n (fakultaet (- n 1)))))

(fakultaet 6)

Analyse
Wir nutzen zur Analyse des Codes mal die Möglichkeiten der Programmierumgebung Dr. Scheme und setzen den Stepper ein. Davor müssen wir jedoch das Sprachlevel auf Anfänger runtersetzen, da der Stepper nicht in allen Sprachleveln funktioniert. Gehen Sie also zum Menüpunkt Sprache und wählen Sie dort Sprache wählen aus. In dem nun erscheinenden Fenster müssen Sie nun die Menüpunkt How to design Programs aus, es sollte sich eine Liste ausklappen. Dort ist der erste Punkt Anfänger/in auszuwählen und anschließend auf OK zu drücken. Klicken Sie dann auf das Symbol mit dem Fuß im oberen rechten Fensterbereich ganz links. Es erscheint das Fenster des Steppers.

Analyse mit dem Stepper
Links grün hervorgehoben sehen Sie den ersten Schritt, der Stepper zeigt unseren Funktionsaufruf an, rechts sehen Sie nun, dass für n nun die Zahl 6 eingesetzt wurde. Im folgenden wandern die Schritte von rechts nach links, drücken Sie oben auf Step >, das Fenster verändert sich, rechts sehen wir, dass 6 nicht gleich null ist. Bei diesem Vergleich wird für die Zahl 0 der triviale Fall abgefangen wird, würden wir mit 0 aufgerufen haben, dann würde nun 1 zurückgegeben werden. Außerdem ist es unsere Abbruchbedingung! Wir rechnen nämlich nicht wie eingangs erklärt 1*2*3*4*5*6, sondern 6*5*4*3*2*1*1, irgendwann kommen wir auch bei 0 an, dann soll 1 zurückgegeben werden.
Da wir aber 6 zugewiesen haben, tritt der sonst Fall ein, dies sehen Sie, wenn Sie nochmals auf Step > drücken. Nun sehen Sie rechts den sonst-Fall, in den für n unsere Zahl 6 eingesetzt wurde.
Wir wollen uns nun mal ausführlich mit dieser Zeile (* 6 (fakultaet (- 6 1)) befassen, denn es "handelt sich" hier um die Rekursion. Wir multiplizieren 6 mit der Klammer. In der Klammer steht der Prozeduraufruf, bei dem n um eins verringert wird. fakultaet wird also mit 5 nochmals aufgerufen. Es werden die gleichen Schritte wie bei n = 6 durchlaufen, also Abbruchbedingung. Wenn Sie mal ein bisschen "weitersteppen", sehen Sie was passiert, die sonst-Fall-Klammer wird immer länger, Scheme ersetzt den Funktionsaufruf immer wieder durch (* n (fakultaet (- n 1)), so dass am Ende, also wenn n = 0 1 zurückgegeben hat, folgender langer Term da steht:
(*6 (*5 (*4 (*3 (* 2 (* 1 1)))))
Nun fasst Scheme die Klammern von innen nach außen (also von rechts nach links) zusammen, indem er die Produkte innerhalb der Klammern ausrechnet. Hat er also alle Klammern bis auf die erste zusammengefasst steht da noch (* 6 120), nach dieser Rechnung erhalten wir unser Ergebnis 720.

Fazit zur rekursiven Berechnung
Nun haben wir gesehen, wie man ein "großes" Problem, wie die Fakultät von 6 zu errechnen mit einer rekursiven Prozedur berechnet. Wir schreiben uns erst einmal einen Term zusammen, mit allen Zahlen innerhalb des Intervalls. Anschließend multiplizieren wir das Ganze aus.
Aber gerade diese Vorgehensweise hat auch ihre Nachteile, versuchen Sie mal die Fakultät von 99 mit dieser Prozedur auszurechnen (STOPP! Lieber nicht!) Das dauert sehr lange, weil wir immer den ganzen Term mitschleppen müssen und so unnötig Speicher und Rechenzeit vergeuden.
Da liegt also das Problem! Aber auch dafür gibt es eine Lösung, aber auch da gibt es ein Problem...

Iteration
Bei der Iteration werden die Zwischenergebnisse bei der Berechnung nur als Betrag mitgeführt, so nehmen diese nur wenig Platz ein. Außerdem kann man mit diesen Zwischenbeträgen auch mehrmalige Berechnungen der selben Rechnung vermeiden, ein Problem, dass wir bis jetzt bei der rekursiven Berechnung übersehen haben.
Das Problem, dass ich bei dem obigen Fazit zur rekursiven Berechnung angesprochen haben, liegt darin, dass die Problemlösung für den Programmierer schwerer ist. Meistens sind die iterativen Prozeduren komplexer als ihre rekursiven Pendants.

Beispiel für eine Iteration
Wir verwenden einfach das gleiche Problem wie bei der rekuriven Berechnung, also die Berechnung der Fakultät. So sähe der Quelltext für die iterative Berechnung aus:

(define (f-iter produkt zaehler max)
(if (> zaehler max)
produkt
(f-iter (* zaehler produkt) (+ zaehler 1) max)))

(f-iter 1 1 6)

Analyse
Wie schon auf den ersten Blick zu sehen ist, brauchen wir viel mehr Variablen. Wie schon bei der rekursiven Prozedur haben wir auch als erstes eine Abbruchbedingung eingebaut. Diese bricht die Iteration ab, wenn der Zähler größer als die Zahl ist, für die wir die Fakultät berechnen. Damit ist klar, dass wir diesmal "von unten" berechnen, also 1*2*3*4*5*6.
produkt ist das Produkt aller Zahlen die wir bis jetzt miteinander multipliziert haben, der Zähler zählt mit jedem Durchlauf um eins hoch und liefert so die Zahlen, die mit dem Produkt multipliziert werden. max ist die Zahl, von der die Fakultät berechnet werden soll.
Wenn Sie wollen, können Sie sich auch diese Prozedur im Stepper an sehen. Sie werden sehen, dass alle Zwischenergebnisse in Produkt fertig ausgerechnet gespeichert werden. Der letzte Aufruf sieht so aus: (f-iter 720 7 6), der Zähler ist nun also größer als max und die Abbruchbedingung trifft zu. Nun wird also gemäß dem Quellcode die Variable Produkt zurückgegeben, somit also das korrekte Ergebnis geliefert.
Haben Sie schon geschaut? Ja, es stimmt mit dem Ergebnis unserer Rekursion überein.

Related Workshops: Allgemeines \\ Dr. Scheme
Related Files: Dr. Scheme