Читать книгу Die UNIX-Story - Brian W. Kernighan - Страница 14

Die räumliche Anordnung kann manchmal schicksalhaft sein.

Das Büro, das ich 1967 als Praktikant bezog, lag im vierten Stock von Gebäude Nr. 2 an einem Flur, der von Treppenhaus 8 abzweigte. An meinem ersten Tag saß ich in diesem Büro (das waren noch die guten alten Zeiten, in denen man selbst als Praktikant mit Glück ein Büro für sich allein ergattern konnte) und fragte mich, was ich hier eigentlich tun sollte, als ein älterer Herr um 11 Uhr seinen Kopf zur Tür hereinstreckte und sagte: »Hallo, ich bin Dick [unverständlich]. Sollen wir Mittagessen gehen?«

Also gut, dachte ich, warum nicht? Von der Mittagspause selbst weiß ich nichts mehr, aber ich kann mich noch gut daran erinnern, dass Dick [unverständlich] nachher noch anderswo hinging und ich den Flur entlangschlich, um das Namensschild an seiner Bürotür zu lesen. Richard Hamming! Mein freundlicher Zimmernachbar war der berühmte Erfinder von Fehlerkorrekturcodes und der Autor des Lehrbuchs für einen Kurs in numerischer Analyse, den ich gerade erst belegt hatte.

Dick (Abbildung 1.5) und ich wurden gute Freunde. Er hatte feste Überzeugungen und scheute sich auch nicht, sie auszudrücken, auch wenn er damit einige Leute vor den Kopf stieß. Ich dagegen genoss seine Gesellschaft, und sein Rat war für mich äußerst nutzbringend.

Zwar war er Abteilungsleiter, allerdings gab es in seiner Abteilung keinen einzigen Mitarbeiter, was ein bisschen merkwürdig erschien. Er erzählte mir, dass er hart gearbeitet hatte, um diese Kombination aus angemessenem Titel und fehlender Verantwortung zu erreichen. Nachvollziehen konnte ich das erst, als ich selbst Leiter einer Abteilung mit einem Dutzend Mitarbeitern wurde.

Abbildung 1.5

Dick Hamming, ca. 1975, mit seinem typischen Plaidjacket (Wikipedia)

Ich war dabei, als er im Sommer 1968 erfuhr, dass er den ACM Turing Award gewonnen hatte, der heute als das Gegenstück zum Nobelpreis in der Informatik angesehen wird. Damals war der Nobelpreis mit 100.000 Dollar dotiert, der Turing Award dagegen mit nur 2.000 Dollar, was Dick zu der sarkastischen Bemerkung veranlasste, er hätte 2 % des Nobelpreises gewonnen. (Dies war übrigens erst die dritte Verleihung des Turing Award. Die beiden vorhergehenden Preise gingen an Alan Perlis und Maurice Wilkes, ebenfalls Pioniere der Informatik.) Dick wurde für seine Arbeiten über numerische Methoden, automatische Codiersysteme sowie Codes zur Fehlererkennung und -behebung ausgezeichnet.

Es war auch Dick, der mich dazu anregte, Bücher zu schreiben, was sich als eine gute Sache herausstellte. Er hielt nicht viel von den meisten Programmierern, da sie seiner Meinung nach wenn überhaupt, dann nur eine schlechte Ausbildung erhalten hatten. Ich kann ihn immer noch sagen hören:

»Wir geben ihnen ein Wörterbuch und die Grammatikregeln an die Hand und sagen ihnen: ›Junge, jetzt bist du ein großartiger Programmier.‹«

Seiner Ansicht nach sollte Programmieren ebenso gelehrt werden wie Schreiben. Was guter und was schlechter Code war, sollte auch anhand des Stils unterschieden werden. Programmierer sollten lernen, gut zu schreiben und guten Stil zu würdigen.

Unsere Meinungen gingen zwar darüber auseinander, wie das zu erreichen war, aber sein Grundgedanke war sinnvoll und führte unmittelbar zu meinem ersten Buch, The Elements of Programming Style, das ich 1974 zusammen mit P. J. »Bill« Plauger veröffentlichte, der zu diesem Zeitpunkt im Büro nebenan saß. Dabei folgten Bill und ich dem Vorbild des englischen Stilhandbuchs The Elements of Style von Strunk und White, indem wir ebenfalls Beispiele von schlecht geschriebenem Code vorstellten und zeigten, wie sie sich jeweils verbessern ließen.

Unser erstes Beispiel stammte aus einem Buch über numerische Analyse, das Dick mir gezeigt hatte. Eines Tages kam er damit in mein Büro und ließ sich völlig aufgebracht darüber aus, wie schlecht die numerischen Programmteile waren. Mir sprang gleich ein Abschnitt mit furchtbarem Fortran-Code ins Auge:

DO 14 I=1,N

DO 14 J=1,N

14 V(I,J)=(I/J)*(J/I)

Lassen Sie mich das für Nicht-Fortran-Programmierer erklären. Dieser Code besteht aus zwei verschachtelten DO-Schleifen, die beide in der Zeile mit der Nummer 14 enden. Jede der Schleifen durchläuft ihre Indexvariable von der unteren zur oberen Schranke. In der äußeren Schleife durchläuft also I die Werte von 1 bis N, in der inneren Schleife J. Die Variable V ist ein Array aus N Zeilen und N Spalten. I durchläuft alle Zeilen und J jeweils alle Spalten einer Zeile.

Dieses Schleifenpaar erstellt also eine NxN-Matrix mit dem Wert 1 in der Diagonalen und 0 an allen anderen Positionen. Für N = 5 ergibt sich beispielsweise:

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

Dieser Code nutzt die Tatsache aus, dass die Integerdivision in Fortran jegliche Nachkommastellen abschneidet. Wenn I ungleich J ist, ergibt die Division daher 0; wenn I gleich J ist (also auf der Diagonalen), dagegen 1.

Das sah für mich viel zu clever aus, denn Cleverness an der falschen Stelle ist in der Programmierung eine Untugend.

Der Code lässt sich auch einfacher und offensichtlicher schreiben, sodass er eine viel klarere Vorstellung vermittelt. Bei jedem Durchlauf durch die äußere Schleife setzt die innere Schleife jedes Element der Zeile I auf 0, und die äußere Schleife setzt dann das Diagonalenelement V(I,I) auf 1:

C MAKE V AN IDENTITY MATRIX

DO 14 I = 1,N

DO 12 J = 1,N

12 V(I,J) = 0.0

14 V(I,I) = 1.0

Das führte auch zu unserer ersten Regel für guten Programmierstil:

Schreiben Sie deutlich – versuchen Sie nicht, zu clever zu sein.

Dick ging 1976 in Pension, unterrichtete aber noch an der Naval Postgraduate School im kalifornischen Monterey, bis er Anfang 1998 im Alter von 82 Jahren starb. Es wurde gemunkelt, dass sein Kurs unter den Studenten als »Hamming über Hamming« bezeichnet wurde, worin man schon fast eine peinliche Parallele zu diesem Abschnitt meines Buches sehen kann.

Dick dachte immer sorgfältig darüber nach, was er tat und warum er es tat. Er pflegte zu sagen: »Einsichten, nicht Zahlen, sind der Zweck der EDV.« Dieser Satz stand sogar (in Chinesisch) auf einer seiner Krawatten. Eine seine ersten Einsichten bestand darin, dass die Informatik schließlich etwa die Hälfte der Arbeit bei Bell Labs ausmachen würde. Keiner seiner Kollegen stimmte ihm darin zu, allerdings sollte sich seine Schätzung schon sehr bald als zu vorsichtig erweisen. Er pflegte auch zu sagen, dass der Freitagnachmittag hervorragend geeignet war, um große Gedanken zu wälzen, weshalb er sich um diese Zeit zurücklehnte und nachdachte. Allerdings war er für Besucher wie mich jederzeit zu sprechen.

Einige Jahre nach seiner Pensionierung hielt Dick einen erhellenden Vortrag mit dem Titel »You and Your Research«, in der er seine Ratschläge über eine erfolgreiche Karriere auf den Punkt brachte. Eine erste Version dieses Vortrags hielt er im März 1986 bei Bellcore. Ken Thompson fuhr mich dorthin, sodass wir ihm zuhören konnten. Seit Jahrzehnten empfehle ich Studenten diesen Vortrag. Es lohnt sich wirklich, die Abschrift zu lesen oder sich eine der Videoaufzeichnungen davon anzusehen.

Im Sommer 1967 saß in dem genau gegenüberliegenden Büro auf der anderen Seite des Flures Vic Vyssotsky (Abbildung 1.6), ein weiterer außerordentlich kluger und talentierter Programmierer. Er war zusammen mit Corby für Multics verantwortlich, fand aber trotzdem Zeit, sich fast täglich mit einem kleinen Praktikanten zu unterhalten. Vic drängte mich, einen Fortran-Kurs für Physiker und Chemiker abzuhalten, die Programmieren lernen mussten. Dieser Unterricht für Nicht-Programmierer machte mir großen Spaß. Er half mir, mein Lampenfieber zu überwinden, und erleichterte es mir, später noch verschiedene weitere Lehraufträge zu erhalten.

Kurz danach zog Vic zu einem anderen Bell-Labs-Standort, wo er an dem Raketenabwehrsystem Safeguard arbeitete. Schließlich kehrte er nach Murray Hill zurück und wurde Direktor für Informatikforschung. In dieser Eigenschaft war er mein Vorgesetzter mehrere Ebenen über mir.

Im Frühjahr 1968 machte ich mich an meine Doktorarbeit zu dem von meinem Doktorvater Peter Weiner vorgeschlagenen Thema der Graphenpartitionierung. Die Aufgabe bestand darin, eine gegebene Menge durch Kanten verbundener Knoten so in zwei gleich große Gruppen aufzuteilen, dass die Anzahl der Kanten, die Knoten in einer Gruppe mit Knoten der anderen Gruppe verbinden, so gering wie möglich ist. Abbildung 1.7 zeigt ein Beispiel dafür. Bei jeder anderen Aufteilung der Knoten in zwei Fünfergruppen ergeben sich mehr als zwei Kanten zwischen den beiden Mengen.

Abbildung 1.6

Vic Vyssotsky, ca. 1982 (mit freundlicher Genehmigung der Bell Labs)

Abbildung 1.7

Ein Beispiel der Graphenpartitionierung

Diese Aufgabenstellung ging vorgeblich auf ein praktisches Problem zurück: Wie weist man Teile eines Programms den Seiten im Arbeitsspeicher zu, sodass bei der Ausführung des Programms nur eine minimale Verlagerung von Seiten aus dem und in den Speicher auftritt? Die Knoten sind hierbei die Codeblöcke und die Kanten die möglichen Übergänge von einem Block zu einem anderen, wobei jeder Kante eine Gewichtung als Maß dafür zugewiesen werden kann, wie häufig solche Übergänge auftreten und wie aufwendig sie sind, wenn sich die beiden Blöcke auf unterschiedlichen Seiten befinden.

In gewissem Sinne war es ein akademisches Problem, aber es stellte auch eine plausible Abstraktion eines realen Vorgangs dar. Außerdem gab es noch andere konkrete Probleme, die sich auf dieses abstrakte Modell zurückführen ließen. Ein Beispiel dafür ist die Frage, wie Bauelemente auf Platinen angeordnet werden konnten, um eine teure Verkabelung zwischen zwei Platinen zu minimieren. Eine weitere, wenn auch weniger augenfällige Problemstellung besteht darin, Mitarbeiter auf die Stockwerke eines Gebäudes zu verteilen, wobei diejenigen, die am meisten miteinander kommunizieren, möglichst in derselben Etage untergebracht werden sollten.

Das reichte aus, um eine Doktorarbeit zu rechtfertigen. Allerdings machte ich wenig Fortschritte. Als ich im Sommer 1968 zu einem zweiten Praktikum in die Bell Labs zurückkehrte, sprach ich darüber mit Shen Lin (Abbildung 1.8), der erst kurz zuvor den effizientesten bekannten Algorithmus für das klassische Problem des Handelsreisenden entwickelt hatte. Dabei muss zu einer gegebenen Menge von Städten die kürzeste Route gefunden werden, um jede Stadt genau einmal zu besuchen und schließlich nach Hause zurück zu fahren.

Abbildung 1.8

Shen Lin, ca. 1970 (mit freundlicher Genehmigung der Bell Labs)

Shen überlegte sich einen Ansatz zur Graphenpartitionierung, der durchaus vielversprechend aussah, auch wenn nicht garantiert war, dass er auch tatsächlich zur bestmöglichen Lösung führen würde. Es gelang mir, eine effiziente Implementierung dafür zu schreiben, und ich experimentierte mit sehr vielen Graphen, um zu bestimmen, wie gut der Algorithmus in der Praxis funktionierte. Er schien zwar äußerst wirkungsvoll zu sein, allerdings fanden wir nie eine Möglichkeit, um eine optimale Lösung zu garantieren. Dafür entdeckte ich einige interessante Sonderfälle von Graphen, für die ich Algorithmen entwerfen konnte, die sowohl schnell waren als auch garantiert die optimale Lösung lieferten. Insgesamt reichte das für meine Doktorarbeit. Als der Sommer zu Ende ging, hatte ich alles beisammen, was ich brauchte. Den Herbst über schrieb ich an der Arbeit, und meine letzte mündliche Prüfung legte ich im Januar 1969 ab. Die drei Jahre aus der optimistischen Schätzung von Princeton hatten sich in Wirklichkeit als viereinhalb Jahre erwiesen.

Eine Woche später begann ich im Computing Science Research Center der Bell Labs zu arbeiten. Ein Vorstellungsgespräch hatte es nicht gegeben. Im Herbst hatten mir die Labs das Angebot unter der Voraussetzung gemacht, dass ich zu dem Zeitpunkt meine Doktorarbeit abgeschlossen hatte. Sam Morgan, der Direktor des Centers und damit mein Vorgesetzter zwei Ebenen über mir, sagte zu mir: »Wir stellen keine abgebrochenen Doktoranden ein.« Meine Doktorarbeit abzuschließen, war mit Sicherheit eine gute Sache, denn im Dezember wurde mir in einem weiteren Brief bereits eine erhebliche Gehaltserhöhung mitgeteilt, noch bevor ich überhaupt die Arbeitsstelle angetreten hatte.

Nebenbei bemerkt: Es hatte seinen Grund, dass Shen und ich nicht in der Lage waren, einen effizienten Algorithmus zur Graphenpartitionierung zu finden, der stets die beste Lösung ermittelte, auch wenn wir diesen Grund damals nicht kannten. Andere hatten sich ebenfalls den Kopf über die inhärenten Schwierigkeiten bei kombinatorischen Optimierungsaufgaben wie der Graphenpartitionierung zerbrochen und dabei einige bemerkenswerte allgemeine Beziehungen aufgedeckt.

Stephen Cook, Mathematiker und Informatiker an der Universität von Toronto, zeigte 1971 in einer aufsehenerregenden Arbeit, dass viele dieser anspruchsvollen Probleme einschließlich der Graphenpartitionierung in dem Sinne äquivalent sind, dass uns die Aufstellung eines effizienten Algorithmus für eines davon (also eines Algorithmus, der besser ist, als alle möglichen Lösungen auszuprobieren) in die Lage versetzen würde, effiziente Algorithmen für alle zu finden. Die Frage, ob diese Aufgaben wirklich schwierig sind, ist in der Informatik immer noch unbeantwortet, allerdings ist die Wahrscheinlichkeit dafür sehr hoch. Für diese Arbeit erhielt Cook 1982 den Turing Award.

Als ich 1969 meine Festanstellung bei den Bell Labs erhielt, sagte mir niemand, woran ich arbeiten sollte. Das war dort so üblich: Man wurde den anderen vorgestellt, dazu angeregt, sich ein bisschen umzusehen, und dann allein gelassen, um seine eigenen Forschungsaufgaben und Mitarbeiter zu finden. Im Rückblick wirkt das ziemlich beängstigend, aber ich kann mich nicht entsinnen, dass ich deswegen Besorgnis empfunden hätte. Es war so viel los, dass sich mit Leichtigkeit etwas zu untersuchen oder Kollegen finden ließen, mit denen man zusammenarbeiten konnte. Nach meinen zwei Sommerpraktika kannte ich außerdem bereits die Leute und einige der laufenden Projekte.

Dieses Fehlen von ausdrücklichen Vorgaben von oben stellte die übliche Vorgehensweise dar. Die Projekte im Center 1127 wurden nicht durch die Geschäftsleitung zugewiesen, sondern wuchsen von innen heraus. Die Menschen, die an einem bestimmten Thema interessiert waren, fanden sich zu einer Gruppe zusammen. Das galt auch für die Arbeit in anderen Teilen der Bell Labs. Wenn ich in einer Entwicklungsgruppe mitarbeitete, konnte ich versuchen, Kollegen aus der Forschung dazu zu ermuntern, sich mir anzuschließen, aber diese Mitarbeit war stets freiwillig.

Eine Zeit lang arbeitete ich weiterhin mit Shen an kombinatorischer Optimierung. Shen konnte sich äußerst gut in solche Fragestellungen hineindenken und durch manuelles Herumspielen mit überschaubaren Beispielen ein Gespür für mögliche Lösungswege entwickeln. Er hatte eine neue Idee für das Problem des Handelsreisenden, eine Technik, die noch besser war als sein vorheriger Algorithmus (der damals der beste bekannte war), und ich implementierte sie in Fortran. Sie funktionierte gut und galt viele Jahre lang als Stand der Technik.

Diese Arbeit machte Spaß und war sehr befriedigend. Obwohl ich Ideen sehr gut in Code umsetzen konnte, hatte ich jedoch Schwierigkeiten, was Algorithmen anging. Daher ging ich nach und nach zu anderen Gebieten wie Software zur Dokumentenerstellung und fachspezifische Programmiersprachen über und betätigte mich auch ein wenig als Autor.

Ich arbeitete noch einige weitere Male mit Shen zusammen, unter anderem an einem komplexen Tool zur Optimierung des Designs privater Netzwerke für AT&T-Kunden. Es tat gut, immer wieder zwischen abstrakter Informatik und Systemen zu wechseln, die praktischen Wert für das Unternehmen hatten.

Abbildung 1.9

PR-Foto von ca. 1970 (mit freundlicher Genehmigung der Bell Labs)

Der PR-Abteilung der Bell Labs gefiel Shens Arbeit zum Problem des Handelsreisenden, sodass sie es in mehreren Anzeigen herausstellte. Die etwas unscharfe Abbildung 1.8 ist einer davon entnommen, wobei ich die Person in der Ecke bin. Abbildung 1.9 stammt aus einer Hochglanz-PR-Zeitschrift, die von den Bell Labs herausgegeben wurde. Darin ging es um unsere Arbeit zur Graphenpartitionierung. Erschienen ist sie wahrscheinlich, nachdem wir ein Patent für den Algorithmus erhalten hatten.

Die Krawatte, die ich auf dem Bild trage, ist übrigens ganz untypisch für mich. Einige Jahre später schrieben Dennis Ritchie und ich einen Artikel über C für eine andere Zeitschrift des Unternehmens, wahrscheinlich Western Electric Engineer. Vor der Veröffentlichung wurden wir gebeten, Bilder von uns einzusenden, die mit abgedruckt werden sollten. Einige Wochen danach erhielten wir die Mitteilung, dass die Bilder verloren gegangen seien. »Kein Problem«, sagten wir, »wir schicken sie euch einfach noch mal.« Darauf erhielten wir die Antwort: »Könnt Ihr diesmal bitte Krawatten tragen?« Das lehnten wir kategorisch ab. Kurz danach kam die Zeitschrift heraus, und zwar mit unseren ursprünglichen, krawattenlosen Bildern, die auf wundersame Weise wiedergefunden worden waren.

Als ich meine feste Stelle antrat, bekam ich ein Büro im vierten Stock von Gebäude Nr. 2 an dem Korridor, der von Treppenhaus 9 abzweigte. Dort blieb ich 30 Jahre lang. Das Büro war für mich ein Fixpunkt in einer Welt im Wandel. Meine Nachbarn auf der gegenüberliegenden Seite des Flures waren im Laufe der Jahre Ken Thompson, Dennis Ritchie, Bob Morris, Joe Ossanna und Gerard Holzmann. Dazu kamen bedeutende Gäste wie John Lions, Andy Tanenbaum und David Wheeler.

Im letzten Jahrzehnt meiner Tätigkeit in den Bell Labs lagen die Büros von Ken Thompson und Dennis Ritchie dem meinen gegenüber. Abbildung 1.10 zeigt das Büro von Dennis, aufgenommen im Oktober 2005 aus der Tür meines Büros heraus. Kens Büro lag links davon.

Die unmittelbar benachbarten Büros gehörten im Laufe der Jahre Bill Plauger, Lorinda Cherry, Peter Weinberger und Al Aho. Doug McIlroy, Rob Pike und Jon Bentley saßen nur wenige Türen weiter. Es ist viel einfacher, mit anderen Menschen zusammenzuarbeiten, wenn sie sich auch physisch ganz in der Nähe befinden. Mit meinen Nachbarn habe ich wirklich Glück gehabt.

Abbildung 1.10

Dennis Ritchies Büro im Jahr 2005