RTFM #5: Structure and Interpretation of Computer Programs (SICP)

the next big thing Golo Roden  –  3 Kommentare

Die Serie RTFM stellt in unregelmäßigen Abständen zeitlose und empfehlenswerte Bücher für Entwicklerinnen und Entwickler vor. Primär handelt es sich um Fachbücher, doch gelegentlich sind auch Romane darunter. Heute geht es um "Structure and Interpretation of Computer Programs" von Hal Abelson, Gerald Jay Sussman und Julie Sussman.

In diesem Format geht es regelmäßig um Bücher, die dazu beitragen können, eine allgemein bessere Entwicklern beziehungsweise ein allgemein besserer Entwickler zu werden. Dabei liegt der Fokus auf zeitlosen Büchern, die sie sich mit Konzept- und Methodenwissen befassen. Derartiges Wissen hat nämlich eine weitaus höhere Halbwertszeit als Bücher zu aktuellen Sprachen und Versionen.

Eines der Bücher, die als zeitlos gelten, ist "Structure and Interpration of Computer Programs" (kurz "SICP") von Hal Abelson, Gerald Jay Sussman und Julie Sussman. Es stammt bereits aus dem Jahr 1979 und wird aufgrund seines Covers häufig auch ehrfurchtsvoll als "Wizard Book" bezeichnet. Worum geht es im Buch?

Eine Einführung in Scheme

Die Antwort auf diese Frage fällt erstaunlich vielschichtig aus. Auf den ersten Blick handelt es sich um eine Einführung in Scheme, einen Lisp-Dialekt. Der Schwerpunkt liegt dabei allerdings auf den zugrunde liegenden Konzepten der Programmierung, und diese Themen haben es in sich.

Das erste Kapitel beginnt mit der These, in der Programmierung habe man es grundsätzlich mit drei Ebenen zu tun: Die erste Ebene sind die einzelnen kleinen Bausteine, die zweite Ebene ist die Kombination dieser Bausteine, und die dritte schließlich die Abstraktion – was die Grundlage für eine weitere Iteration auf höherer Ebene bildet. Dieses Muster zieht sich wie ein roter Faden durch das Buch und wird aus verschiedenen Perspektiven wiederholt.

RTFM #5: SICP

Als Bausteine werden zunächst Ausdrücke eingeführt, die kombiniert und in Funktionen zusammengefasst werden können. Dabei werden Funktionen ausschließlich aus der mathematisch-funktionalen Perspektive behandelt, was über Rekursion, Iteration und Komplexität schließlich zur Abstraktion durch Funktionen höherer Ordnung führt.

Die Themen, die in diesem ersten Kapitel auf rund 100 Seiten besprochen werden, fallen durch eine extrem hohe Informationsdichte auf – andere Bücher brauchen für die gleichen Inhalte mit weniger Details weitaus mehr Seiten. SICP gelingt der Spagat, verhältnismäßig kompakt und zugleich detailliert zu sein, auf hervorragende Weise.

Code … und Daten

Während sich das erste Kapitel mit Funktionen befasst, kümmert sich das zweite um Datenstrukturen und -typen. Dazu wird zunächst ein eigener Datentyp für rationale Zahlen eingeführt, auf dem anschließend arithmetische Operationen definiert werden. Diese Funktionen sind zunächst losgelöst von den Daten und werden noch nicht gemeinsam gekapselt.

Auch hier beginnt der Aufbau wieder mit einfachen Bausteinen (nämlich Paaren von Datenwerten), die zu komplexeren Strukturen kombiniert werden, bis schließlich über Daten abstrahiert wird: Dazu führt SICP das sogenannte "Data-Directed Programming" ein, es wird der Begriff "Tagged Data" besprochen, und es wird gezeigt, wie sich Operationen generisch implementieren lassen, dass verschiedene Typen miteinander genutzt werden können, ohne jede Kombination einzeln programmieren zu müssen.

Variablen, Zuweisungen und State

Das dritte Kapitel führt schließlich Variablen und damit zusammenhängend Zuweisungen ein, spricht aber auch direkt das damit einhergehende Problem an, dass nämlich die Auswertung von Ausdrücken viel komplizierter wird, da nun zeitliche Veränderungen berücksichtigt werden müssen. Die im ersten Kapitel einfache Auswertung genügt nun nicht mehr, stattdessen wird ein neues Modell auf Basis von Frames benötigt – was eng mit dem lexikalischen Scope von Scheme zusammenhängt.

Damit wird die Grundlage für komplexere Datentypen und deren Zustände geschaffen, wie Listen, Queues und Tabellen. All diese Strukturen werden als veränderliche Daten angesehen, bei denen parallele Schreibzugriffe zu Konflikten führen können. Daher beschäftigt sich das Kapitel auch mit der Frage, wie man mit Data-Races, Deadlocks & Co. umgeht.

Streams, die als verzögerte Listen implementiert werden, runden das Kapitel ab. Sie erinnern aufgrund der Art ihrer Auswertung stark an Generatorfunktionen in JavaScript beziehungsweise an die Lazy Evaluation von Haskell.

Ein Interpreter für Scheme …

Das vierte Kapitel beschäftigt sich mit metalinguistischer Abstraktion und führt dazu den Metacircular Evaluator ein, quasi einen in Scheme geschriebenen Interpreter für Scheme. In Scheme geschriebener Code wird auf dem Weg zu Daten für die höhere Abstraktionsschicht, was letztlich sehr schön zeigt, dass Code und Daten eins sind – was etwas ist, hängt nur vom jeweiligen Blickwinkel ab.

Auf dem Weg lässt sich Scheme dann um weitere Fähigkeiten erweitern, quasi um kleine domänenspezifische Sprachen, was dann auch im Rest des Kapitels erfolgt. So wird eine Erweiterung für Lazy Evaluation entwickelt, ebenso eine für nichtdeterministisches Verhalten und zu guter Letzt auch für logisches Programmieren, ähnlich zu Prolog.

All diese Themen gehen über den Umfang einer "Einführung in Scheme" definitiv weit hinaus. Sie sind durchaus komplex und anspruchsvoll, aber ungemein interessant und lehrreich.

… und ein Compiler

Das fünfte und letzte Kapitel setzt dem ganzen schließlich noch die Krone auf: Hier wird in Scheme eine Registermaschine samt Compiler entwickelt, die einen eigenen Assembler-Dialekt versteht, um dann Code auf dieser virtuellen Maschine auszuführen. Das fünfte Kapitel erhebt quasi das vierte vom Interpreter zum Compiler.

Man erfährt dabei viel über Compilerbau, das Entwickeln von virtuellen Maschinen, Speicherverwaltung und ähnliche Themen, die zwar im Prinzip die Grundlage für praktisch jede Programmiersprache sind, mit denen man aber in kaum einer Sprache direkt in Berührung kommt.

Neben dem eigentlichen Inhalt enthält das Buch Hunderte, wenn nicht Tausende Übungsaufgaben. Wer SICP ernsthaft durcharbeiten möchte, braucht also vor allem viel Zeit, der Aufwand lohnt sich aber, da man dabei unglaublich viel lernt. Scheme als Programmiersprache wird dabei fast zur Nebensache – der eigentliche Wert des Buchs liegt tiefer.

Fazit

SICP ist sicherlich eines der besten Bücher, die jemals über Programmierung geschrieben wurden. Jede Entwicklerin und jeder Entwickler sollte es unabhängig von der persönlich präferierten Programmiersprache zumindest teilweise gelesen haben, insbesondere die ersten drei Kapitel bieten in kompakter Form einen tiefgehenden Einblick in zahlreiche wichtige Themen.

Da man das Buch ohnehin öfter als einmal lesen muss, um es wirklich zu erfassen, bietet sich an, es zunächst einmal nur zu lesen, ohne direkt die praktischen Übungen zu machen, damit man einen Eindruck und einen Überblick davon bekommt, was einen erwartet, und dann erst im zweiten Durchlauf auch die Übungen zu bearbeiten.

Insgesamt ist SICP also eine ganz eindeutige Kauf- und Leseempfehlung – alternativ zum Kauf findet man es auf der Verlagswebseite auch zum kostenfreien Lesen im HTML-Format.