On this page:
1.1 Programmieren mit arithmetischen Ausdrücken
1.2 Arithmetik mit nicht-numerischen Werten
1.3 Auftreten und Umgang mit Fehlern
1.4 Bedeutung von BSL Ausdrücken

1 Programmieren mit Ausdrücken

Dieser Teil des Skripts basiert auf [HTDP/2e] Kapitel 1

1.1 Programmieren mit arithmetischen Ausdrücken

Jeder von Ihnen weiß, wie man Zahlen addiert, Kaffee kocht, oder einen Schrank eines schwedischen Möbelhauses zusammenbaut. Die Abfolge von Schritten, die sie hierzu durchführen, nennt man Algorithmus, und Sie wissen wie man einen solchen Algorithmus ausführt. In diesem Kurs werden wir die Rollen umdrehen: Sie werden den Algorithmus programmieren, und der Computer wird ihn ausführen. Eine formale Sprache, in der solche Algorithmen formuliert werden können, heißt Programmiersprache. Die Programmiersprache, die wir zunächst verwenden werden, heißt BSL. BSL steht für "Beginning Student Language". Zum Editieren und Ausführen der BSL Programme verwenden wir DrRacket. DrRacket kann man unter der URL http://racket-lang.org/ herunterladen. Bitte stellen Sie als Sprache "How To Design Programs - Anfänger" ein. Folgen Sie diesem Text am besten, indem Sie DrRacket parallel starten und immer mitprogrammieren.

Viele einfache Algorithmen sind in einer Programmiersprache bereits vorgegeben, z.B. solche zur Arithmetik mit Zahlen. Wir können "Aufgaben" stellen, indem wir DrRacket eine Frage stellen, auf die uns DrRacket dann im Ausgabefenster die Antwort gibt. So können wir zum Beispiel die Frage

(+ 1 1)

im Definitionsbereich (dem oberen Teil der DrRacket Oberfläche) stellen — als Antwort erhalten wir im Interaktionsbereich (dem Bereich unterhalb des Definitionsbereichs) bei Auswertung dieses Programms ("Start" Knopf) 2. Im Definitionsbereich schreiben und editieren Sie ihre Programme. Sobald Sie hier etwas ändern, taucht der "Speichern" Knopf auf, mit dem Sie die Definitionen in einer Datei abspeichern können. Im Interaktionsbereich wird das Ergebnis einer Programmausführung angezeigt; außerdem können hier Ausdrücke eingegeben werden, die sofort ausgewertet werden aber nicht in der Datei mit abgespeichert werden.

Die Art von Programmen bzw. Fragen wie (+ 1 1) nennen wir Ausdrücke. In Zukunft werden wir solche Frage/Antwort Interaktionen so darstellen, dass wir vor die Frage das > Zeichen setzen und in der nächsten Zeile die Antwort auf die Frage:

> (+ 1 1)

2

Operationen wie + nennen wir im Folgenden Funktionen. Die Operanden wie 1 nennen wir Argumente. Hier einige weitere Beispiele für Ausdrücke mit anderen Funktionen:

> (+ 2 2)

4

> (* 3 3)

9

> (- 4 2)

2

> (/ 6 2)

3

> (sqr 3)

9

> (expt 2 3)

8

> (sin 0)

0

Die Argumente dieser Funktionen sind jeweils Zahlen, und das Ergebnis ist auch wieder eine Zahl. Wir können auch direkt eine Zahl als Ausdruck verwenden. Zum Beispiel:

> 5

5

DrRacket zeigt als Ergebnis wieder genau dieselbe Zahl an. Eine Zahl, die direkt in einem Ausdruck verwendet wird, heißt auch Zahlenliteral.

Für manche Ausdrücke kann der Computer das mathematisch korrekte Ergebnis nicht berechnen. Stattdessen erhalten wir eine Annäherung an das mathematisch korrekte Ergebnis. Zum Beispiel:

> (sqrt 2)

#i1.4142135623730951

> (cos pi)

#i-1.0

Das i im letzten Ergebnis steht für "inexact", also ungenau. In BSL kann man an diesem i sehen, ob eine Zahl ein exaktes Ergebnis oder nur ein angenähertes Ergebnis ist.

Programme beinhalten Ausdrücke. Alle Programme, die wir bisher gesehen haben, sind Ausdrücke. Jeder von Ihnen kennt Ausdrücke aus der Mathematik. Zu diesem Zeitpunkt ist ein Ausdruck in unserer Programmiersprache entweder eine Zahl, oder etwas, das mit einer linken Klammer "(" startet und mit einer rechten Klammer ")" endet. Wir bezeichnen Zahlen als atomare Ausdrücke und Ausdrücke, die mit einer Klammer starten, als zusammengesetzte Ausdrücke. Später werden andere Arten von Ausdrücken hinzukommen.

Programieren Sie einen Ausdruck, der die Summe der Zahlen 3, 5, 19, und 32 berechnet.

Wie kann man mehr als zwei Zahlen addieren? Hierzu gibt es zwei Möglichkeiten:

Durch Schachtelung:

> (+ 2 (+ 3 4))

9

oder durch Addition mit mehr als zwei Argumenten:

> (+ 2 3 4)

9

Immer wenn Sie in BSL eine Funktion wie + oder sqrt benutzen möchten, schreiben Sie eine öffnende Klammer, gefolgt vom Namen der Funktion, dann einem Lehrzeichen (oder Zeilenumbruch) und dann die Argumente der Funktion, also in unserem Fall die Zahlen, auf die die Funktion angewandt werden soll.

Programmieren Sie einen Ausdruck, der den Durchschnitt der Zahlen 3, 5, 19 und 32 berechnet.

Am Beispiel der Schachtelung haben Sie gesehen, dass auch zusammengesetzte Ausdrücke als Argumente zugelassen sind. Diese Schachtelung kann beliebig tief sein:

> (+ (* 5 5) (+ (* 3 (/ 12 4)) 4))

38

Das Ergebnis für einen solchen geschachtelten Ausdruck wird so berechnet, wie sie es auch auf einem Blatt Papier machen würden: Wenn ein Argument ein zusammengesetzter Ausdruck ist, so wird zunächst das Ergebnis für diesen Ausdruck berechnet. Dieser Unterausdruck ist möglicherweise selber wieder geschachtelt; in diesem Fall wird diese Berechnungsvorschrift auch auf diese Unterausdrücke wieder angewendet (rekursive Anwendung). Falls mehrere Argumente zusammengesetzte Ausdrücke sind, so werden diese in einer nicht festgelegten Reihenfolge ausgewertet. Die Reihenfolge ist nicht festgelegt, weil das Ergebnis nicht von der Reihenfolge abhängt — mehr dazu später.

Zusammengefasst ist Programmieren zu diesem Zeitpunkt das Schreiben von arithmetischen Ausdrücken. Ein Programm auszuführen bedeutet, den Wert der darin enthaltenen Ausdrücke zu berechnen. Ein Drücken auf "Start" bewirkt die Ausführung des Programms im Definitionsbereich; die Ergebnisse der Ausführung werden im Interaktionsbereich angezeigt.

Noch ein praktischer Hinweis: Wenn Sie dieses Dokument mit einem Webbrowser lesen, sollten alle Funktionen, die in den Beispielausdrücken vorkommen, einen Hyperlink zu ihrer Dokumentation enthalten. Beispielsweise sollte der Additionsoperator im Ausdruck (+ 5 7) einen solchen Hyperlink enthalten. Unter diesen Links finden Sie auch eine Übersicht über die weiteren Operationen, die sie verwenden können.

1.2 Arithmetik mit nicht-numerischen Werten

Wenn wir nur Programme schreiben könnten, die Zahlen verarbeiten, wäre Programmieren genau so langweilig wie Mathematik ;-) Zum Glück gibt es viele andere Arten von Werten, mit denen wir ganz analog zu Zahlen rechnen können, zum Beispiel Text, Wahrheitswerte, Bilder usw.

Zu jedem dieser sogenannten Datentypen gibt es Konstruktoren, mit denen man Werte dieser Datentypen konstruieren kann, sowie Funktionen, die auf Werte dieses Datentyps angewendet werden können und die weitere Werte des Datentyps konstruieren. Konstruktoren für numerische Werte sind zum Beispiel 42 oder 5.3 (also die Zahlenliterale; Funktionen sind zum Beispiel + oder *.

Die Konstruktoren für Text (im folgenden auch String genannt) erkennt man an Anführungszeihen. So ist zum Beispiel

"Konzepte der Programmiersprachen"

ein Stringliteral. Eine Funktion auf diesem Datentyp ist string-append, zum Beispiel

> (string-append "Konzepte der " "Programmiersprachen")

"Konzepte der Programmiersprachen"

Es gibt weitere Funktionen auf Strings: Um Teile aus einem String zu extrahieren, um die Reihenfolge der Buchstaben umzukehren, um in Groß- oder Kleinbuchstaben zu konvertieren usw. Zusammen bilden diese Funktionen die Arithmetik der Strings.

Die Namen aller dieser Funktionen muss man sich nicht merken; bei Bedarf können die zur Verfügung stehenden Funktionen für Zahlen, Strings und andere Datentypen in der DrRacket Hilfe nachgeschlagen werden unter: Hilfe -> How to Design Programs Languages -> Beginning Student -> Pre-defined Functions

Programmieren Sie einen Ausdruck, der den String "Der Durchschnitt ist ..." erzeugt. Statt der drei Punkte soll der Durchschnitt der Zahlen 3, 5, 19 und 32 stehen. Verwenden Sie den Ausdruck, der diesen Durchschnitt berechnet, als Unterausdruck.

Bisher haben wir nur Funktionen kennengelernt, bei denen alle Argumente und auch das Ergebnis zum selben Datentyp gehören müssen. Zum Beispiel arbeitet die Funktion + nur mit Zahlen, und die Funktion string-append arbeitet nur mit Strings. Es gibt aber auch Funktionen, die Werte eines Datentyps as Argument erwarten, aber Werte eines anderen Datentypes als Ergebnis liefern, zum Beispiel die Funktion string-length:

> (+ (string-length "Programmiersprachen") 5)

24

Das Ergebnis von (string-length "Programmiersprachen") ist die Zahl 19, die ganz normal als Argument für die Funktion + verwendet werden kann. Sie können also Funktionen, die zu unterschiedlichen Datentypen gehören, in einem Ausdruck zusammen verwenden. Dabei müssen Sie allerdings darauf achten, daß jede Funktion Argumente des richtigen Datentyps bekommt. Es gibt sogar Funktionen, die Argumente unterschiedlicher Datentypen erwarten, zum Beispiel

> (replicate 3 "hi")

"hihihi"

Schließlich gibt es auch Funktionen, die Datentypen ineinander umwandeln, zum Beispiel

> (number->string 42)

"42"

> (string->number "42")

42

Als Programmierer können Sie also viele verschiedene Datentypen benutzen, um Ihr Ziel zu erreichen.

Ein weiterer wichtiger Datentyp sind Wahrheitswerte (Boolsche Werte). Die einzigen Konstruktoren hierfür sind die Literale true und false. Funktionen auf boolschen Werten sind zum Beispiel die aussagenlogischen Funktionen:

> (and true true)

true

> (and true false)

false

> (or true false)

true

> (or false false)

false

> (not false)

true

Boolsche Werte werden auch häufig von Vergleichsfunktionen zurückgegeben:

> (> 10 9)

true

> (< -1 0)

true

> (= 42 9)

false

> (string=? "hello" "world")

false

Natürlich können Ausdrücke weiterhin beliebig verschachtelt werden, z.B. so:

Beachten Sie in diesem Beispiel wie die Einrückung des Textes hilft, zu verstehen, welcher Teilausdruck Argument welcher Funktion ist. Probieren Sie in DrRacket aus, wie die Funktionen "Einrücken" bzw. "Alles einrücken" im Menü "Racket" die Einrückung ihres Programms verändern.

> (and (or (= (string-length "hello world") (string->number "11"))
           (string=? "hello world" "good morning"))
       (>= (+ (string-length "hello world") 60) 80))

false

Der letzte Datentyp den wir heute einführen werden, sind Bilder. In BSL sind Bilder "ganz normale" Werte, mit dazugehöriger Arithmetik, also Funktionen darauf. Existierende Bilder können per copy&paste oder über das Menü "Einfügen -> Bild" direkt in das Programm eingefügt werden. Wenn Sie dieses Dokument im Browser betrachten, können Sie das Bild dieser Rakete image mit Copy&Paste in ihr Programm einfügen. Genau wie die Auswertung einer Zahl die Zahl selber ergibt, ergibt die Auswertung des Bilds das Bild selber.

> image

image

Achten Sie darauf, das Teachpack "image.ss" zu verwenden, das zu HtDP/2e gehört. Es steht im DrRacket-Teachpack-Dialog in der mittleren Spalte.

Wie auf anderen Datentypen sind auch auf Bildern eine Reihe von Funktionen verfügbar. Diese Funktionen müssen allerdings erst durch das Aktivieren eines "Teachpacks" zu BSL hinzugefügt werden. Aktivieren Sie in DrRacket das HtDP/2e Teachpack "image.ss", um selber mit den folgenden Beispielen zu experimentieren.

Beispielsweise kann die Fläche des Bildes durch diesen Ausdruck berechnet werden:

> (* (image-width image) (image-height image))

600

Statt existierende Bilder in das Programm einzufügen kann man auch neue Bilder konstruieren:

> (circle 10 "solid" "red")

image

> (rectangle 30 20 "solid" "blue")

image

Programmieren Sie einen Ausdruck, der mehrere Kreise um denselben Mittelpunkt zeichnet.
Programmieren Sie einen Ausdruck, der einen Kreis zeichnet, der durch eine schräge Linie geschnitten wird. Markieren Sie die Schnittpunkte durch kleine Kreise.

Die Arithmetik der Bilder umfasst nicht nur Funktionen um Bilder zu konstruieren, sondern auch um Bilder in verschiedener Weise zu kombinieren:

> (overlay (circle 5 "solid" "red")
           (rectangle 20 20 "solid" "blue"))

image

Benutzen Sie die Dokumentation von BSL (z.B. über die Links in der Browser-Version dieses Dokuments) wenn Sie wissen wollen welche weiteren Funktionen auf Bildern es gibt und welche Parameter diese erwarten. Zwei wichtige Funktionen die Sie noch kennen sollten sind empty-scene und place-image. Die erste erzeugt eine Szene, ein spezielles Rechteck in dem Bilder plaziert werden können. Die zweite Funktionen setzt ein Bild in eine Szene:

> (place-image (circle 5 "solid" "green")
               50 80
               (empty-scene 100 100))

image

1.3 Auftreten und Umgang mit Fehlern

Bei der Erstellung von Programmen können unterschiedliche Arten von Fehlern auftreten. Es ist wichtig, die Klassen und Ursachen dieser Fehler zu kennen.

Eine wichtige Art von Fehlern sind Syntaxfehler. Ein Beispiel für ein Programm mit einem Syntaxfehler sind die Ausdrücke (+ 2 3( oder (+ 2 3 oder (+ 2 (+ 3 4).

Syntaxfehler werden vor der Programmausführung von DrRacket geprüft und gefunden; diese Prüfung kann auch mit der Schaltfläche "Syntaxprüfung" veranlasst werden.

Ein Syntaxfehler tritt auf, wenn ein BSL Programm nicht zur BSL Grammatik passt. Später werden wir diese Grammatik genau definieren; informell ist eine Grammatik eine Menge von Vorschriften über die Struktur korrekter Programme.

Die Grammatik von dem Teil von BSL, den sie bereits kennen, ist sehr einfach:
  • Ein BSL Programm ist eine Sequenz von Ausdrücken.

  • Ein Ausdruck ist eine Zahl, ein Bild, ein Boolscher Wert, ein String, oder ein Funktionsaufruf.

  • Ein Funktionsaufruf hat die Form (f a1 a2 ...) wobei f der name einer Funktion ist und die Argumente a1,a2,... Ausdrücke sind.

Die folgenden Programme sind alle syntaktisch korrekt, allerdings lassen sich nicht alle diese Programme auswerten:

> (number->string "asdf")

number->string: expects argument of type <number>; given

"asdf"

> (string-length "asdf" "fdsa")

string-length: expects 1 argument, given 2: "asdf" "fdsa"

> (/ 1 0)

/: division by zero

> (string->number "asdf")

false

Nicht jedes syntaktische korrekte Programm hat in BSL eine Bedeutung. Bedeutung heißt in diesem Fall dass das Programm korrekt ausgeführt werden kann und einen Wert zurückliefert. Die Menge der BSL Programme, die eine Bedeutung haben, ist nur eine Teilmenge der syntaktisch korrekten BSL Programme.

Die Ausführung des Programms (number->string "asdf") ergibt einen Laufzeitfehler, ein Fehler der auftritt während das Programm läuft (im Unterschied zu Syntaxfehlern, die vor der Programmausführung erkannt werden). Wenn in BSL ein Laufzeitfehler auftritt, wird die Programmausführung abgebrochen und eine Fehlermeldung ausgegeben.

Dieser Fehler ist ein Beispiel für einen Typfehler: Die Funktion erwartet, dass ein Argument einen bestimmten Typ hat, diesem Fall ’Zahl’, aber tatsächlich hat das Argument einen anderen Typ, in diesem Fall ’String’.

Ein anderer Fehler, der auftreten kann, ist der, dass die Anzahl der angegebenen Argumente nicht zu der Funktion passt. Im Programm (string-length "asdf" "fdsa") tritt dieser Fehler.

Manchmal stimmt zwar der Datentyp des Arguments, aber trotzdem ’passt’ der Argument in irgendeiner Weise nicht. Im Beispiel (/ 1 0) ist es so, dass die Divionsfunktion als Argumente Zahlen erwartet. Das zweite Argument ist eine Zahl, trotzdem resultiert die Ausführung in einer Fehlermeldung, denn die Division durch Null ist nicht definiert.

Programmiersprachen unterscheiden sich darin, zu welchem Zeitpunkt solche Fehler gefunden werden, also zum Beispiel vor der Ausführung oder erst während der Ausführung. Im Allgemeinen gilt: Je früher desto besser! - allerdings muss diese zusätzliche Sicherheit häufig mit anderen Restriktionen erkauft werden, zum Beispiel der, dass einige korrekte Programme nicht mehr ausgeführt werden können.

Eine andere Situation liegt im Fall (string->number "asdf") vor. Die Ausführung des Programms ergibt den Wert false. Dieser Wert signalisiert, dass der übergebene String keine Zahl repräsentiert. In diesem Fall tritt also kein Laufzeitfehler auf, sondern die Ausführung wird fortgesetzt. Der Aufrufer von (string->number "asdf") hat dadurch die Möglichkeit, abzufragen, ob die Umwandlung erfolgreich war oder nicht, und je nachdem das Programm anders fortzusetzen. Das Programm ist also aus BSL-Sicht wohldefiniert. Die Funktion string->number hätte alternativ aber auch so definiert werden können, dass sie in dieser Situation einen Laufzeitfehler auslöst.

1.4 Bedeutung von BSL Ausdrücken

Fassen wir nochmal den jetzigen Stand zusammen: Programmieren ist das Aufschreiben arithmetischer Ausdrücke, wobei die Arithmetik Zahlen, Strings, Boolsche Werte und Bilder umfasst. Programme sind syntaktisch korrekt wenn Sie gemäß der Regeln aus dem vorherigen Abschnitt konstruiert wurden. Nur syntaktisch korrekte Programme (aber nicht alle) haben in BSL eine Bedeutung. Die Bedeutung eines Ausdrucks in BSL ist ein Wert, und dieser Wert wird durch folgende Auswertungsvorschriften ermittelt:

Diese Vorschriften können wir als Anleitung zur schrittweisen Reduktion von Programmen auffassen. Wir schreiben ee’ um zu sagen, dass e in einem Schritt zu e’ reduziert werden kann. Werte können nicht reduziert werden. Die Reduktion ist wie folgt definiert:

Experimentieren Sie in DrRacket mit dem "Stepper" Knopf: Geben Sie einen komplexen Ausdruck in den Definitionsbereich ein, drücken Sie auf "Stepper" und dann auf die "Schritt nach rechts" Taste und beobachten was passiert.

  • Falls der Ausdruck die Form (f v1 ... vn) hat und die Anwendung von f auf v1,...,vN den Wert v ergibt, dann (f v1 ... vn)v.

  • Falls ein Audruck e1 einen Unterausdruck e2 in einer Auswertungsposition enthält, der reduziert werden kann, also e2e2’, dann gilt e1e1’, wobei e1’ aus e1 entsteht indem e2 durch e2’ ersetzt wird.

Die letzte Regel nennen wir die Kongruenzregel. In dem Teil der Sprache, den Sie bereits kennengelernt haben, sind alle Positionen von Unterausdrücken Auswertungspositionen. Da bisher nur Funktionsaufrufe Unterausdrücke haben, daher gilt in diesem Fall folgender Spezialfall der Kongruenzregel: Fall eiei’, dann (f e1 ... en)(f e1 ... ei-1 ei ei+1 ...).

Wir benutzen folgende Konventionen:

Beispiele:

Im Allgemeinen kann ein Ausdruck mehrere reduzierbare Unterausdrücke haben, also die Kongruenzregeln an mehreren Stellen gleichzeitig einsetzbar sein. In den Beispielen oben haben wir zum Beispiel (+ (* 2 3) (* 4 5))(+ (* 2 3) 20) aber auch (+ (* 2 3) (* 4 5))(+ 6 (* 4 5)). Es ist jedoch nicht schwer zu sehen, dass immer wenn wir die Situation e1 → e2 und e1e3 haben, dann gibt es ein e4 so dass gilt e2* e4 und e3* e4 . Diese Eigenschaft nennt man Konfluenz. Reduktionen die auseinanderlaufen können also immer wieder zusammengeführt werden; der Wert den man am Ende erhält ist auf jeden Fall eindeutig.

Auf Basis dieser Reduktionsregeln können wir nun definieren, unter welchen Umständen zwei Programme die gleiche Bedeutung haben: Zwei Ausdrücke e1 und e2 haben die gleiche Bedeutung, geschrieben e1e2 , falls es einen Ausdruck e gibt so dass e1* e und e2* e .

Beispiele:

Die Rechtfertigung für diese Definition liegt in folgender wichtiger Eigenschaft begründet: Wir können innerhalb eines großen Programms Teilausdrücke beliebig durch Teilausdrücke mit der gleichen Bedeutung ersetzen, ohne die Bedeutung des Gesamtprogramms zu verändern. Etwas formaler können wir das so ausdrücken:

Sei e1 ein Unterausdruck eines größeren Ausdrucks e2 und e1e3 . Ferner sei e2’ eine Kopie von e2 in dem Vorkommen von e1 durch e3 ersetzt wurden. Dann gilt: e2e2’.

Diese Eigenschaft folgt direkt aus der Kongruenzregel und der Definition von ≡ . Dieser Gleichheitsbegriff ist identisch mit dem, den Sie aus der Schulmathematik kennen, wenn Sie Gleichungen umformen, zum Beispiel wenn wir a + a - b umformen zu 2a - b weil wir wissen dass a + a = 2a.

Die Benutzung von ≡ um zu zeigen dass Programme die gleiche Bedeutung haben nennt man auch equational reasoning.