Buch: "Structure and Interpretation of Computer Programs. 2nd Edition" / Harold Abelson, Gerald Jay Sussman, Julie Sussman / 1996. Siehe auch SICP / (für die Übungs-Aufgaben) SolutionsSICP.
Lektüre-Notizen:
- Vorwörter:
- "1. Building Abstractions with Procedures":
- Computer-Prozesse ("computational processes") sind Vorgänge innerhalb von Computern, die Daten ("data") manipulieren. Gesteuert werden sie von Programmen ("programs") genannten Regelwerken, verfasst in Programmiersprachen ("programming languages") – wie etwa Lisp, dessen Dialekt Scheme folgend verwendet wird.
- Ein Lisp-Interpreter ist eine Maschine, die in Lisp beschriebene Computer-Prozesse ausführt. Die Lisp-Beschreibung eines Computer-Prozesses wird Prozedur ("procedure") genannt. Solche Prozeduren können selbst als von Lisp manipulierbare Daten behandelt werden.
- "1.1 The Elements of Programming":
- Mächtige Sprachen besitzen als Mechanismen primitive Ausdrücke ("primitive expressions") für einfachste Prozeduren- und Daten-Typen; Kombinations-Mittel ("means of combination"), diese zu kombinieren; und Abstraktions-Mittel ("means of abstractions"), um solche Kombinationen als Einheiten zu behandeln.
- "1.1.1 Expressions":
- In Lisp können beispielsweise Zahlen Ausdrücke sein (für numerische Daten), oder Zeichen wie "+" und "-" (für bestimmte Prozeduren). Solche primitiven Ausdrücke können zu Komposit-Ausdrücken ("compound expressions") aka Kombinationen ("combinations") zusammengefügt werden, in dieser Form:
- Ein "(" gefolgt vom Ausdruck für eine Prozedur (Operator) gefolgt von einem Leerzeichen gefolgt von einer durch weitere Leerzeichen getrennten Folge weiterer Ausdrücke (Operanden), deren Werte die Argumente der vom Operator bezeichneten Prozedur darstellen, gefolgt von einem ")".
- Die Notations-Weise, den Operator vor die Operanden zu stellen, heißt Präfix-Notation ("prefix notation").
- In der Präfix-Notation einer Kombination ist Einnisten ("nesting") anderer Kombinationen möglich – die Verwendung präfix-notierter Kombinationen als Elementen präfix-notierter Kombinationen. Dies erlaubt komplexe Klammer-Monster, die aber Einrückung und Mehrzeiligkeit übersichtlich machen kann ("pretty-printing").
- Der Interpreter liest Ausdrücke ein, evaluiert sie durch Ausrechnen ihres Ergebnis-Werts, und gibt diesen schließlich aus. Diese Abfolge heißt Lese-Evaluations-Ausgabe-Schleife ("read-eval-print loop").
- "1.1.2 Naming and the Environment":
- Berechnungs-Gegenstände sind Werte. Variablen sind mit Namen identifizierte Träger von Werten. Mit dem Operator "define" lässt sich eine Variable definieren – mit dem ersten Operanden als ihrem Namen und dem zweiten als von ihr getragenem Wert. Hierbei handelt es sich um ein Abstraktions-Mittel.
- Die Definition einer Variable wird im Gedächtnis der Umgebung ("environment") gespeichert. Es kann mehrere Umgebungen geben – etwa die globale Umgebung ("global environment").
- "1.1.3 Evaluating Combinations":
- Allgemeine Regel zum Evaluieren von Ausdrücken: 1. Ist der Ausdruck kombiniert, evaluiere erst seine UnterAusdrücke ("subexpressions"). 2. Wende dann die Prozedur, die der Wert des linkesten UnterAusdrucks bzw. Operators ist, auf die Operanden bzw. die eben ermittelten Werte der übrigen Unter-Ausdrücke an.
- Diese Evaluations-Regel ist rekursiv: Sie enthält einen Aufruf ihrer selbst, denn das Evaluieren der UnterAusdrücke ruft notwendigerweise erneut die allgemeine Evaluations-Regel auf. Rekursion ist ein mächtiges Werkzeug, um hierarchische und baumförmige (siehe nächsten Punkt) Systeme abzuarbeiten.
- Evaluation genesteter Kombinationen ist baumförmig darstellbar, mit Operanden und Operatoren eingenisteter Kombinationen als Zweigen auszurechnender Ergebnis-Werte, die selber ebenso solche Verzweigungen darstellen, mit einem einzelnen Start-Knoten als finalem (oberstem) Wert. So ein Modell heißt Baum-Akkumulation ("tree accumulation").
- Evaluation solcher Bäume EndKnoten (von Ausdrücken, die keine Kombinationen sind): Zahlen entsprechen ihren numerischen Werten; Namen den ihnen in der gegenwärtigen Umgebung zugewiesenen Werten; eingebaute Operatoren ("built-in operators") sind Namen, denen die Umgebung als Wert (änderbar) vorbestimmte Prozeduren zuweist.
- Es gibt Spezial-Formen ("special forms"), für die eigene Evaluations-Regeln gelten anstelle der obigen allgemeinen. Das schon vorgestellte "define" ist eine davon.
- Das Set ihrer Evaluations-Regeln bildet einer Programmiersprache Syntax. Lisp besitzt nur sehr wenige davon. Ist eine Evaluations-Regel funktional nicht notwendig, d.h. ließe sich in ihrer Funktion durch den Einsatz bereits gegebener anderer Evaluations-Regeln ersetzen, ist sie syntaktischer Zucker ("syntactic sugar").
- "1.1.4 Compound Procedures":
- Zahlen sind primitive Daten, arithmetische Operationen primitive Prozeduren.
- Das Nesting von Kombinationen stellt selbst ein Kombinations-Mittel dar.
- Auch Prozedur-Definitionen nutzen "define". Sie definieren Komposit-Prozeduren ("compound procedures") (hier ist SICP etwas unklar, aber http://www.cs.berkeley.edu/~bh/ssch27/glossary.html erklärt: diese sind vom Programmierer definierte Prozeduren im Gegensatz zu den vordefinierten "primitiven"). Syntax:
- "define (" gefolgt vom Namen der neuen Prozedur, gefolgt von einem Leerzeichen, gefolgt von formalen Parametern (lokalen Namen bei Aufruf anzugebender Argumente), gefolgt von ")" und einem Leerzeichen, gefolgt vom Körper ("body") der Prozedur, die formale Parameter als Platzhalter der Argumente wiederholt, gefolgt von ")".
- Dass Name und formale Parameter in einer Klammer gruppiert werden, entspricht der Schreibweise künftiger Aufrufe der Prozedur. Mir ist unklar, warum SICP in der formalen Definition der Prozeduren-Definition nicht auch den Körper in Klammern setzt, in folgenden Beispielen tritt er nicht ohne auf. Vielleicht steckt ein Geheimnis dahinter!
- SICP merkt an, der Körper könne mehrere statt nur eines einzelnen Ausdrucks enthalten, sagt aber nichts über die Syntax einer solchen Aneinanderreihung.
- "1.1.5 The Substition Model for Procedure Application":
- Das Substitions-Modell setzt Anwendung von Komposit-Prozeduren so um: Ersetze im Körper der Prozedur die als Platzhalter dienenden formalen Parameter durch die Argumente des Prozeduren-Aufrufs, evaluiere danach den Prozedur-Körper. Dies ist nur eine stark vereinfachte Darstellung dessen wie LISP-Interpreter Komposit-Prozeduren anwenden.
- LISP-Interpreter nutzen anwendungsgeordnete Evaluation ("applicative-order evaluation"): Jeder Prozeduren-Aufruf übergibt als Operanden der aufgerufenen Prozedur die fertig evaluierten Werte seiner eigenen Operanden. Ein "(square (+ 2 3) )" (definiert mit "(define (square x x) (* x x) )") würde erst "(square 5)" und dann "(* 5 5)".
- Ein alternativer Ansatz wäre normalgeordnete Evaluation ("normal-order evaluation"): Hier werden die noch nicht evaluierten Ausdrücke als Operanden übergeben. Ein "(square (+ 2 3) )" würde "(* (+ 2 3) (+ 2 3) )". Erst wenn (wie jetzt im Beispiel) als Operatoren nur primitive verbleiben, werden die Unter-Ausdrücke durch diese evaluiert.
- "1.1.6 Conditional Expressions and Predicates":
- Prädikate ("predicates") sind Ausdrücke und Prozeduren, deren Werte bzw. im Fall von Prozeduren deren Rückgabe-Werte "wahr" oder "falsch" sein können. Für "falsch" gibt Scheme einen speziellen Wert #f zurück, als "wahr" gelten dagegen alle anderen Werte.
- Primitive Prädikate zum Vergleich von ZahlenWerten: "<" (erster Operand ist kleiner als der zweite), ">" (erster Operand ist größer als der zweite), "=" (beide Operanden sind gleich).
- Logische Prädikate zur Evaluation von Wahrheit und Falschheit von Ausdrücken: "and" (alle Ausdrücke sind wahren Werts; Wert des letzten wahren wird zurückgegeben, oder #f), "or" (mindestens ein Ausdruck ist wahren Werts; Wert des ersten für den das gilt wird zurückgegeben), "not" (Ausdruck ist falschen Werts).
- Eine Fall-Analyse ("case analysis") klärt eine Frage durch deren Aufteilung in mehrere auszuführende Tests, die das mögliche Ergebnis eingrenzen. So erklärt es zumindest ungefähr http://en.wikipedia.org/wiki/Case_analysis – während SICP den Begriff einigermaßen unerklärt einführt.
- Eine Spezial-Form zur Fall-Analyse ist "cond" ("Konditional"). Sie wird eingeklammert geschrieben als "cond" gefolgt von einem Leerzeichen gefolgt von einer durch Leerzeichen getrennten Reihe eingeklammerter Klauseln ("clauses"), die je aus einem Prädikat gefolgt von einem Konsequenz-Ausdruck ("consequent expression") bestehen.
- Eine andere Spezial-Form sind Konditional-Ausdrücke mit "if", eingeklammert geschrieben als "if" gefolgt von einem Leerzeichen gefolgt von einem Prädikat-Ausdruck gefolgt von zwei Konsequenz-Ausdrücken, derer der erste ("consequent") bei Wahrheit des Prädikat-Werts und der zweite ("alternative") andernfalls zurückgegeben wird.
- Im Gegensatz zur "cond"-Form können die Konsequenz-Ausdrücke hier keine Reihen von Ausdrücken sein.
- "1.1.7 Example: Square Roots by Newton's Method":
- "1.1.8 Procedure als Black-Box Abstractions":
- Eine Prozedur ist rekursiv definiert, wenn ihre Definition einen Aufruf ihrer selbst enthält.
- Prozeduren rufen andere Prozeduren über die Namen auf, denen diese anderen Prozeduren als Wert zugewiesen sind. Aus Sicht der aufrufenden Prozeduren sind die anderen oft black boxes, Innereien unbekannt: bloße prozedurale Abstraktionen. Solche Black-Box-Prozeduren sollten einsetzbar sein ohne Kenntnis ihrer Vorgehensweise.
- Enthält eine Umgebung die Definition einer Variable, dann ist die Variable relativ zu dieser Umgebung eine gebundene Variable ("bound variable"); andernfalls ist sie eine freie Variable. Der Bereich, für den eine Variable definiert ist, ist ihr Sichtbarkeits-Bereich ("scope") – nur hier gilt ihre Wert-Zuordnung.
- Die Erklärung formaler Parameter innerhalb einer Prozeduren-Definition bindet diese Namen an diese Prozeduren-Definition. Diese Namen sind lokal zur Prozeduren-Definition: Werden dieselben Namen anderswo mit anderen Werten definiert, berührt das die Werte hinter den Namen in der definierten Prozedur nicht.
- Prozeduren-Definitionen können innere Variablen-Definitionen enthalten, die Variablen an die Prozedur binden / sie für keinen Bereich außerhalb ihrer definieren. Für diese Block-Struktur sind die Definitionen einzuschieben zwischen der Klammer, die den Prozeduren-Namen und die formalen Parameter, und der, die den Körper enthält.
- Solche inneren Definitionen können eigene lokale Variablen festlegen, unberührt von Bestimmungen in sie umklammernden Prozeduren-Definitionen. Werden Variablen indes undefiniert und so frei genutzt, beziehen sie ihren Wert von solchen übergeordneten Bestimmungen. Dies Scoping nach oben heißt lexikalische Sichtbarkeit ("lexical scoping").
- Wird ein übergeordnet definierte Variable lokal erneut definiert, also von einer freien lexikalisch sichtbaren in eine gebundene lokal sichtbare verwandelt, wird sie gefangen ("captured"): Ihre Referenz wird überschrieben.
- "1.2 Procedures and the Processes They Generate":
- "1.2.1 Linear Recursion and Iteration":
- Prozeduren können verschieden geformte Ketten von Evaluationsschritten als Prozess zeitigen. Als Beispiel werden zwei verschiedene Prozessformen besprochen, die sich aus rekursiven Prozeduren ergeben können:
- Rekursive Prozesse halten mit jedem Rekursions-Schritt später noch auszuführende Operationen der aufrufenden Prozedur vor – eine wachsende Liste an aufgeschobenen Operationen ("deferred operations"), die sich der Interpreter merken muss, oft z.B. in Daten-Strukturen namens Stapel ("stack") realisiert.
- Iterative Prozesse schieben keine Operationen auf, jeder ihrer Evaluationsschritte enthält die selbe Menge an Operatoren bzw. Status-Variablen ("state variables"), deren Werte von Schritt zu Schritt nach festen Regeln verändert werden.
- Ein Interpreter, der iterative Prozesse aus (bestimmten?) rekursiven Prozeduren erzeugen kann, ist Schwanz-rekursiv ("tail-recursive"). Scheme-Interpreter sind dies oft, Compiler von Sprachen wie C dagegen nicht – hier erfordert Zeugung iterativer Prozesse spezielle Iterations-Prozeduren-Syntax ("for", "while").
- "1.2.2 Tree Recursion":
- Baum-Rekursion ergibt sich, wenn eine Prozedur sich selbst mehrfach aufruft. Die Abfolge der Aufrufe der Prozedur lässt sich als ein Baum darstellen, worin sich aus allen Aufrufen außer jenen, deren Parameter bestimmte Rekursions-Stopp-Bedingungen triggern, jeweils mehrere weitere Aufrufe (der aufrufenden Prozedur) verzweigen.
- Etwas unklare Formulierung der Quantität von Baum-Rekursions-Prozessen: Die Zahl ihrer "Schritte" ("steps") sei proportional der Zahl der Knoten in der beschriebenen Baum-Darstellung, der von ihnen eingenommene "Raum" ("space") dagegen proportional zu dessen Tiefe.
- Bei Baum-Rekursion kann es vorkommen, dass die selbe Prozedur mehrfach mit den selben Parametern aufgerufen, also die selbe Berechnung mehrfach eingefordert wird. Daraus folgende Prozesse lassen sich optimieren, indem die Ergebnisse von Berechnungen für spätere WiederholungsNachfragen vorrätig gehalten werden ("tabulation"/"memoization").
- …
- …
- …
- …