Barbara Liskov: Abstraktion als Grundlage modularer Software

Barbara Liskov widmete ihre Laufbahn einer Schwierigkeit, die jede große Software begleitet: Wie lässt sich ein Teil eines Systems verändern, ohne alle anderen Teile verstehen oder neu schreiben zu müssen? Ihre Antwort beruht auf präzisen Schnittstellen, verborgenen Repräsentationen und Eigenschaften, die Komponenten auch bei ihrer Weiterentwicklung bewahren müssen.

Daraus entstanden mehrere dauerhafte Beiträge. In den 1970er-Jahren entwickelten Liskov und ihr Team am MIT CLU, die erste implementierte Sprache, die Datenabstraktion direkt unterstützte. Ihre Arbeiten über Typhierarchien führten später zum nach ihr benannten Substitutionsprinzip. Argus, Viewstamped Replication und ihre Forschung zur Fehlertoleranz übertrugen dieselbe Strenge schließlich auf Programme, die über mehrere Rechner verteilt sind.

Liskov fügte Programmiersprachen also nicht nur neue Funktionen hinzu. Sie half, eine Methode zu definieren: beschreiben, was eine Komponente garantiert, verbergen, wie sie es umsetzt, und diesen Vertrag bewahren, wenn das System wächst.

Vom wissenschaftlichen Rechnen zur Softwarekomplexität

Barbara Huberman wurde 1939 in Los Angeles geboren und wuchs in San Francisco auf. Sie studierte Mathematik an der University of California, Berkeley, und begann 1961 bei der MITRE Corporation als Programmiererin. Informatik als akademisches Fach war noch jung; Fortran lernte sie unter anderem im Beruf.

Anschließend studierte sie Informatik in Stanford bei John McCarthy. Ihre 1968 abgeschlossene Dissertation behandelte ein Schachprogramm. Liskov gehörte damit zu den ersten Frauen in den USA, die an einem Informatikfachbereich promovierten.

Zurück bei MITRE arbeitete sie am experimentellen Venus-System. Dabei stieß sie auf ein allgemeineres Problem: Hardware besitzt sichtbare Grenzen zwischen Komponenten, in Software kann dagegen ein Teil leicht von internen Details eines anderen abhängen. Mit wachsendem Programm machen solche Abhängigkeiten jede Änderung riskanter.

Als Liskov Anfang der 1970er-Jahre ans MIT wechselte, suchte sie deshalb nach sprachlichen und methodischen Regeln, die Software ähnlich modular machen konnten.

Datenabstraktion: Vertrag und Repräsentation trennen

Ein abstrakter Datentyp wird durch die angebotenen Operationen und deren Eigenschaften definiert, nicht durch die intern verwendete Datenstruktur. Ein Stack kann etwa push, pop und top anbieten. Client-Code soll über dieses Verhalten nachdenken können, ohne zu wissen, ob intern ein Array, eine verkettete Liste oder etwas anderes verwendet wird.

Diese Trennung bringt drei miteinander verbundene Vorteile:

• der Client arbeitet mit einer kleineren Schnittstelle als mit der vollständigen Implementierung;
• die interne Repräsentation kann geändert werden, ohne Nutzer zu brechen;
• die Eigenschaften des Moduls lassen sich unabhängig vom restlichen System erklären und prüfen.

Entscheidend ist die Abstraktionsbarriere: Werte eines Typs können nur über erlaubte Operationen erzeugt und beobachtet werden. Die Implementierung ist wirklich verborgen und nicht bloß eine Konvention, die jeder Aufrufer umgehen könnte.

Heute prägt dieses Denken Klassen, Module, Bibliotheken und APIs. Anfang der 1970er-Jahre musste jedoch erst gezeigt werden, wie eine Sprache solche Grenzen erzwingen und wie ein ganzes System daraus aufgebaut werden konnte.

CLU: Abstraktion in die Sprache einbauen

Ab 1973 verwandelte die Programming Methodology Group des MIT diese Idee in die experimentelle Sprache CLU. Der Name stammt von cluster: Ein Cluster bündelt die private Repräsentation eines Typs und die öffentlichen Operationen, mit denen er verwendet wird.

Liskov leitete das Projekt, doch CLU war Gemeinschaftsarbeit. Alan Snyder, Russell Atkinson, Craig Schaffert und weitere Studierende und Forschende wirkten an Entwurf, Compiler, Umgebung und Dokumentation mit. Ziel war, die Ideen an realen Programmen zu erproben.

CLU führte mehrere Mechanismen ein oder kombinierte sie auf neue Weise:

• abstrakte Typen mit verborgener Repräsentation;
• parametrisierte Typen für generische Sammlungen;
• Iteratoren, die Strukturen durchlaufen, ohne deren Aufbau offenzulegen;
• strukturierte Ausnahmebehandlung;
• automatische Speicherverwaltung und Referenzobjekte.

CLU wurde kein großes Industrieprodukt. Dennoch beeinflussten seine Konzepte Ada, C++, Java, C# und viele moderne Sprachen.

Vom abstrakten Typ zum Substitutionsprinzip

Eine verborgene Repräsentation reicht bei Typhierarchien nicht aus. Wenn ein Programm ein Objekt eines Basistyps erwartet und ein Objekt eines Untertyps erhält, muss dieser Ersatz sicher bleiben. Gleiche Methodennamen allein garantieren kein kompatibles Verhalten.

Liskov formulierte 1987 eine Eigenschaft des verhaltensbasierten Subtypings, die sie später mit Jeannette Wing vertiefte. Praktisch besagt das Liskovsche Substitutionsprinzip, dass ein Objekt eines Untertyps ein Objekt des Basistyps ersetzen können muss, ohne Annahmen zu verletzen, auf die sich der Client berechtigterweise verlässt.

Angenommen, ein Typ Konto garantiert, dass ein zulässiger Auszahlungsbetrag vom Guthaben abgezogen wird. Ein Untertyp, der solche Auszahlungen willkürlich verweigert, ist kein korrekter Ersatz, auch wenn er eine gleichnamige Methode besitzt. Er verschärft eine Vorbedingung, mit der der Client nicht rechnen musste.

Das Prinzip verlangt daher mehr als eine identische Schnittstelle: Ein Untertyp darf vom Aufrufer nicht mehr verlangen, weniger versprechen oder angekündigte Invarianten brechen.

Diese Idee zeigt eine Grenze der objektorientierten Programmierung. Vererbung ist nur dann robust, wenn die Hierarchie eine kohärente Verhaltensbeziehung ausdrückt. Andernfalls sind Komposition oder getrennte Abstraktionen oft besser.

Argus: Abstraktionen trotz Ausfällen bewahren

Nach CLU wandte Liskov ihre Methoden auf verteilte Systeme an. In einem Programm auf mehreren Rechnern können Operationen durch Ausfälle oder Netzwerkunterbrechungen gestoppt werden. Manche Teile laufen weiter, während andere unerreichbar werden. Daten und Konsistenz müssen trotzdem erhalten bleiben.

Die ab Ende der 1970er-Jahre am MIT entwickelte Sprache Argus organisiert ein System um Guardians. Jeder Guardian kapselt Zustand und die darauf zugreifenden Operationen. Atomare Aktionen gruppieren Änderungen so, dass sie gemeinsam erfolgreich sein oder zurückgenommen werden müssen.

Argus beseitigt Ausfälle nicht, gibt Programmierenden aber Abstraktionen dafür, wo Zustand liegt, welche Operationen geschützt sind und wie sich Berechnungen erholen. Das nimmt moderne Systeme vorweg, in denen Transaktionen, Dienste und Replikation zusammenarbeiten.

Replikation, Objektdatenbanken und Fehlertoleranz

Mit Brian Oki veröffentlichte Liskov 1988 Viewstamped Replication, ein Protokoll, das mehrere konsistente Kopien eines Dienstes verwaltet. Eine primäre Replik ordnet Operationen; fällt sie aus, müssen die übrigen eine neue Sicht wählen und fortfahren, ohne bereits bestätigte Entscheidungen zu verlieren.

Das Protokoll gehört zur Familie der State-Machine-Replikation, auf der heute hochverfügbare verteilte Dienste beruhen. Später untersuchte das Projekt Thor transaktionalen Zugriff auf persistente Objekte. Mit Miguel Castro arbeitete Liskov außerdem an byzantinischer Fehlertoleranz, bei der Knoten sich beliebig fehlerhaft verhalten können.

Diese Themen wirken weit von CLU entfernt, verfolgen aber dieselbe Frage: Eine Komponente muss verständliche Garantien bieten, selbst wenn ihre Implementierung komplex, verteilt und ausfallgefährdet ist.

Eine kollektive Leistung als intellektuelle Infrastruktur

Liskov erhielt 2008 den Turing Award für Beiträge zu praktischen und theoretischen Grundlagen von Programmiersprachen und Systementwurf. CLU beruhte auf der Programming Methodology Group, das Substitutionsprinzip wurde mit Jeannette Wing vertieft, Viewstamped Replication mit Brian Oki entwickelt und Argus, Thor sowie Fehlertoleranzsysteme entstanden mit vielen Mitarbeitenden.

Ihr besonderer Beitrag liegt im roten Faden: Sie beginnt bei einem konkreten Softwareproblem, formuliert die notwendige Abstraktion, baut sie in eine Sprache oder ein System ein und prüft sie durch Implementierung.

Darum bleibt CLU trotz begrenzter Verbreitung wichtig. Eine Forschungssprache kann Informatik verändern, ohne dominant zu werden: Sie macht Ideen testbar, zeigt Grenzen und liefert Begriffe, die andere Ökosysteme übernehmen.

Warum Barbara Liskov weiterhin wichtig ist

Moderne Entwicklung beruht auf Grenzen: öffentlichen APIs, Modulen, Diensten, Typen, Verträgen und Protokollen. Sie erlauben Teams, unabhängig zu arbeiten und Implementierungen zu verändern, ohne alles neu zu schreiben.

Liskovs Arbeiten erinnern daran, dass eine syntaktische Grenze nicht genügt. Ein Modul muss die richtigen Details verbergen. Ein Untertyp muss versprochenes Verhalten erhalten. Ein replizierter Dienst muss seine Garantien bewahren, wenn ein Rechner ausfällt. Abstraktion ignoriert die Realität nicht; sie kapselt sie hinter einem expliziten Vertrag.

Ob Sammlung im Speicher oder Dienst über mehrere Rechenzentren: Die zentrale Frage bleibt dieselbe - auf welche Eigenschaften darf sich der Rest des Programms verlassen?

Chronologie

• 1939: Geburt von Barbara Huberman in Los Angeles.
• 1961: Mathematikabschluss in Berkeley und Beginn als Programmiererin bei MITRE.
• 1968: Promotion in Informatik in Stanford bei John McCarthy.
• 1972: Wechsel ans MIT.
• 1973: Start des CLU-Projekts.
• 1976: wichtige Veröffentlichung über CLUs Abstraktionsmechanismen.
• 1980er-Jahre: Entwicklung von Argus für verteilte Programmierung und atomare Aktionen.
• 1987: Formulierung des später so genannten Liskovschen Substitutionsprinzips.
• 1988: Viewstamped Replication mit Brian Oki.
• 1994: vertiefte Formulierung des verhaltensbasierten Subtypings mit Jeannette Wing.
• 2008: Turing Award.
• 2018: IEEE Computer Pioneer Award.

Häufig gestellte Fragen

Was hat Barbara Liskov erfunden?

Sie spielte eine zentrale Rolle bei der Formulierung der Datenabstraktion, leitete die Entwicklung von CLU und formulierte die Eigenschaft, die als Liskovsches Substitutionsprinzip bekannt wurde. Außerdem trug sie zu Argus, Viewstamped Replication und verteilten Speichersystemen bei.

Was ist ein abstrakter Datentyp?

Ein Typ, der durch seine Operationen und garantierten Eigenschaften definiert wird, während seine interne Repräsentation verborgen bleibt. Client-Code kann dadurch etwa einen Stack oder eine Menge verwenden, ohne von deren konkreter Implementierung abzuhängen.

Warum ist CLU wichtig, obwohl es wenig verbreitet war?

CLU erprobte abstrakte Typen, Iteratoren, Ausnahmen und parametrisierte Typen in einer vollständigen Sprache. Diese Mechanismen beeinflussten spätere Sprachen und Programmierpraktiken.

Was besagt das Liskovsche Substitutionsprinzip genau?

Ein Objekt eines Untertyps muss ein Objekt des Basistyps ersetzen können, ohne Eigenschaften zu verletzen, auf die sich der Client verlässt. Kompatibilität betrifft also versprochenes Verhalten und nicht nur Methodennamen und Signaturen.

Wie hängen CLU und Liskovs verteilte Systeme zusammen?

Beide kapseln Komplexität hinter expliziten Abstraktionen. CLU schützt die Repräsentation eines Typs; Argus und Replikationsprotokolle schützen die Garantien eines Dienstes trotz Parallelität, Verteilung und Ausfällen.