Struktur und Interpretation von Computerprogrammen: Eine Informatik-Einführung

ISBN-13: 9783540423423 / Niemiecki / Miękka / 2001 / 682 str.

Harold Abelson;Gerald Jay Sussman;Joseph S. Sussman

Opis

Die Ubersetzung der bewahrten Einfuhrung in die Informatik, entstanden am Massachusetts Institute of Technology (MIT), wird seit Jahren erfolgreich in der Lehre eingesetzt. Schritt fur Schritt werden Konstruktion und Abstraktion von Daten und Prozeduren dargestellt. Von der Modularisierung bis zum Problemlosen mit Registermaschinen werden verschiedene Programmierparadigmen entwikckelt und die effektive Handhabung von Komplexitat gezeigt. Als Programmiersprache wird SCHEME verwendet, ein Dialekt von LISP. Alle Programme laufen in jeder dem IEEE-Standard entsprechenden SCHEME-Implementierung."

Spis treści

1 Konstruktion von Abstraktionen mit Prozeduren.- 1.1 Die Programmelemente.- 1.1.1 Ausdrücke.- 1.1.2 Namen und Umgebungen.- 1.1.3 Auswertung von Kombinationen.- 1.1.4 Zusammengesetzte Prozeduren.- 1.1.5 Das Substitutionsmodell für Prozeduranwendungen.- 1.1.6 Bedingte Ausdrücke und Prädikate.- 1.1.7 Beispiel: Berechnung der Quadratwurzel nach dem Newtonschen Iterationsverfahren.- 1.1.8 Prozeduren als „Black-box“-Abstraktionen.- 1.2 Prozeduren und Prozesse.- 1.2.1 Lineare Rekursion und Iteration.- 1.2.2 Baumrekursion.- 1.2.3 Größenordnungen.- 1.2.4 Potenzrechnung.- 1.2.5 Der größte gemeinsame Teiler.- 1.2.6 Beispiel: Primzahlen.- 1.3 Abstraktionen mit Prozeduren höherer Ordnung.- 1.3.1 Prozeduren als Argumente.- 1.3.2 Konstruktion von Prozeduren mit lambda.- 1.3.3 Prozeduren als allgemeine Methode.- 1.3.4 Prozeduren als Ergebnis.- 2 Konstruktion von Abstraktionen mit Daten.- 2.1 Einführung in die Datenabstraktion.- 2.1.1 Beispiel: Arithmetische Operationen für rationale Zahlen.- 2.1.2 Abstraktionsbarrieren.- 2.1.3 Was sind eigentlich Daten?.- 2.1.4 Erweiterte Übung: Arithmetik mit Intervallen.- 2.2. Datenhierarchien und Abgeschlossenheit.- 2.2.1 Darstellung von Sequenzen.- 2.2.2 Hierarchische Strukturen.- 2.2.3 Sequenzen als konventionelle Schnittstellen.- 2.2.4 Beispiel: Eine Bildersprache.- 2.3 Symbole.- 2.3.1 Quotierung.- 2.3.2 Beispiel: Symbolisches Differenzieren ..- 2.3.3 Beispiel: Darstellung von Mengen.- 2.3.4 Beispiel: Huffman-Bäume.- 2.4. Mehrfachdarstellungen abstrakter Daten.- 2.4.1 Darstellungen komplexer Zahlen.- 2.4.2 Etikettierte Daten.- 2.4.3 Datengesteuerte Programmierung und Additivität.- 2.5 Systeme mit generischen Operationen.- 2.5.1 Generische Arithmetikoperationen.- 2.5.2 Kombination von Daten verschiedenen Typs.- 2.5.3 Beispiel: Symbolische Algebra.- 3 Modularität, Objekte und Zustände.- 3 Zuweisungen und lokale Zustände.- 3.1.1 Lokale Zustandsvariablen.- 3.1.2 Die Vorzüge der Zuweisung.- 3.1.3 Der Preis der Zuweisung.- 3.2 Das Umgebungsmodell der Auswertung.- 3.2.1 Die Auswertungsregeln.- 3.2.2 Anwendung einfacher Prozeduren.- 3.2.3 Rahmen als Ort, an dem sich der lokale Zustand befindet.- 3.2.4 Interne Definitionen.- 3.3 Modelle mit veränderbaren Daten.- 3.3.1 Veränderbare Listenstrukturen.- 3.3.2 Darstellung von Warteschlangen.- 3.3.3 Darstellung von Tabellen.- 3.3.4 Ein Simulator für digitale Schaltkreise.- 3.3.5 Propagierung von Beschränkungen.- 3.4 Gleichzeitigkeit: Zeit ist das Wesentliche.- 3.4.1 Die Natur der Zeit in gleichzeitigen Systemen.- 3.4.2 Mechanismen zur Steuerung der Gleichzeitigkeit.- 3.5 Datenströme.- 3.5.1 Ströme als verzögerte Listen.- 3.5.2 Unendliche Datenströme.- 3.5.3 Wir nutzen das Datenstrom-Paradigma.- 3.5.4 Datenströme und verzögerte Auswertung.- 3.5.5 Modularität funktionaler Programme und Modularität von Objekten.- 4 Metalinguistische Abstraktion.- 4 Der metazirkuläre Evaluator.- 4.1.1 Das Kernstück des Evaluators.- 4.1.2 Darstellung von Ausdrücken.- 4.1.3 Die Datenstrukturen des Evaluators.- 4.1.4 Der Evaluator als Programm.- 4.1.5 Behandlung von Daten als Programm.- 4.1.6 Interne Definitionen.- 4.1.7 Die Syntaxanalyse von der Ausführung trennen.- 4.2 Variationen zu einem Schema — Auswertung nach Vorschrift.- 4.2.1 Auswertung in normaler und in applikativer Reihenfolge.- 4.2.2 Ein Interpretierer mit Auswertung nach Vorschrift.- 4.2.3 Datenströme als Listen nach Vorschrift.- 4.3 Variationen zu einem Schema — nondeterministische Berechnung.- 4.3.1 Amb und die Suche.- 4.3.2 Beispiele Nondeterministischer Programme.- 4.3.3 Implementierung des amb-Evaluators.- 4.4 Logikprogrammierung.- 4.4.1 Deduktiver Informationsabruf.- 4.4.2 Wie das Abfragesystem funktioniert.- 4.4.3 Ist Logikprogrammierung Mathematische Logik?.- 4.4.4 Implementierung des Abfragesystems.- 5 Rechnen mit Registermaschinen.- 5.1 Entwurf von Registermaschinen.- 5.1.1 Eine Sprache zur Beschreibung von Registermaschinen.- 5.1.2 Abstraktion beim Entwurf von Maschinen.- 5.1.3 Unterprogramme.- 5.1.4 Implementierung der Rekursion mit einem Keller.- 5.1.5 Befehlsübersicht.- 5.2 Ein Simulator für Registermaschinen.- 5.2.1 Das Maschinenmodell.- 5.2.2 Der Assembler.- 5.2.3 Erzeugen von Ausführungsprozeduren für Befehle.- 5.2.4 Überwachen der Maschinenleistung.- 5.3 Speicherzuteilung und Speicherbereinigung.- 5.3.1 Speicher als Vektoren.- 5.3.2 Als ob der Speicher unendlich wäre.- 5.4 Der Evaluator mit expliziter Steuerung.- 5.4.1 Der Kern des Evaluators mit expliziter Steuerung.- 5.4.2 Auswerten von Sequenzen und Endrekursion.- 5.4.3 Bedingte Ausdrücke, Zuweisungen und Definitionen.- 5.4.4 Laufenlassen des Evaluators.- 5.5 Übersetzen.- 5.5.1 Die Struktur des Übersetzers.- 5.5.2 Übersetzen von Ausdrücken.- 5.5.3 Übersetzen von zusammengesetzten Ausdrücken.- 5.5.4 Kombination von Anweisungsfolgen.- 5.5.5 Ein Beispiel für übersetzten Code.- 5.5.6 Lexikalische Adressierung.- 5.5.7 Die Schnittstelle zwischen übersetztem Code und dem Evaluator.- Appendix zur deutschen Auflage.- Verzeichnis der Übungen.- Stichwortverzeichnis.

O autorze

Harold (Hal) Abelson is Class of 1922 Professor of Electrical Engineering and Computer Science at MIT and a Fellow of the IEEE. He holds an A.B. degree from Princeton University and a Ph.D. degree in mathematics from MIT. In 1992, Abelson was designated as one of MIT's six inaugural MacVicar Faculty Fellows, in recognition of his significant and sustained contributions to teaching and undergraduate education. Abelson was recipient in 1992 of the Bose Award (MIT's School of Engineering teaching award). Abelson is also the winner of the 1995 Taylor L. Booth Education Award given by IEEE Computer Society, cited for his continued contributions to the pedagogy and teaching of introductory computer science. Abelson has a broad interest in information technology and policy, and developed and teaches the MIT course Ethics and Law on the Electronic Frontier. He is a founding director of Creative Commons and Public Knowledge, and he was a founding director of the Free Software Foundation.

Blurb

Die Übersetzung der bewährten Einführung in die Informatik, entstanden am Massachusetts Institute of Technology (MIT), wird seit Jahren erfolgreich in der Lehre eingesetzt. Schritt für Schritt werden Konstruktion und Abstraktion von Daten und Prozeduren dargestellt. Von der Modularisierung bis zum Problemlösen mit Registermaschinen werden verschiedene Programmierparadigmen entwickelt und die effektive Handhabung von Komplexität gezeigt.
Als Programmiersprache wird SCHEME verwendet, ein Dialekt von LISP. Alle Programme laufen in jeder dem IEEE-Standard entsprechenden SCHEME-Implementierung.