Warum schreibt Donald Knuth TAOCP in Assemblersprache?

20

Ich hasse es nicht, Assemblersprache zu verwenden, da ich einige in meinem OS-Kurs geschrieben habe. In der Assemblersprache fehlt es jedoch offensichtlich an Abstraktion. Sie müssen den Details mehr Aufmerksamkeit schenken.

Ist die Assemblersprache wirklich wichtig, um TAOCP zu schreiben?

Lucas Li
quelle
6
Die Details sind, wo der Teufel ist.
Blrfl
5
@Blrfl Ich glaube nicht an den Teufel. (Ich glaube an die Details, obwohl ... zittern )
Jimmy Hoffa
3
Der erste Band von TAOCP wurde 1968 veröffentlicht. Obwohl es zweifellos höhere Sprachen gab, war der handgeschriebene Assembler viel wichtiger, und die Rechenressourcen auf Großrechnern konnten damals in der Größenordnung einiger 8-Bit-Mikros aus den 1980er Jahren liegen. Knuth hat sich auch einmal ernsthaft für die Beibehaltung von goto ausgesprochen, da einige Algorithmen nicht ohne Ineffizienz mit verschachtelten Kontrollflussstrukturen geschrieben werden konnten. Er plädierte eigentlich nicht für eine vorzeitige Optimierung, auch nicht für IIRC. Er wollte nur die Option, die verfügbar war, wenn die Optimierung benötigt wurde.
Steve314
3
@ JimmyHoffa: Oh, na ja, in deinem Fall sind die Details, wo die de Ville ist.
Blrfl
1
Jerry Coffin ist es gelungen, das zu tun, was ich wollte, er hat es in der Quelle nachgeschlagen ;-). Ich habe in den Kapiteln nachgesehen, in denen MIX und MIXAL vorgestellt werden, wo ich solche Aussagen nicht gefunden habe ... Vielleicht sollte ich eines Tages eine elektronische Kopie bekommen. Jedenfalls denke ich, dass das Antwort-Tag in diesem Fall besser für Jerrys Antwort geeignet wäre.
Thomas

Antworten:

22

Er verwendet nicht nur MIXAL, seine Assemblersprache für MIX, sondern auch MIX, ein Modell für einen einfachen Computer (wie es in den sechziger Jahren verwendet wurde). Dies ist ein Modell für den Unterricht, mit dem er in gewissem Maße unabhängig von der Entwicklung auf dem Gebiet ist.

Wenn er eine andere Programmiersprache verwendet hätte (welche wäre Ihrer Meinung nach übrigens geeignet gewesen?), Sagen wir NPL (raffinierte Programmiersprache), hätte er entweder die Idee der Verwendung von MIX aufgeben oder eine neue einführen müssen Compiler einer beliebigen Computersprache (was weitaus komplexer ist als das, was er in Band 1 behandelt). Auf diese Weise wäre es nicht TAOCP, sondern TAONPLP geworden. Der erste ist unabhängig von einer solchen Wahl und aus diesem Grund in gewisser Weise zeitlos, wie es nur wenige Bücher über Programmierung jemals sein werden. Der zweite wäre wohl mittlerweile vergessen ...

Solange Computer im Prinzip so arbeiten wie sein MIX, ist es eine gute Sache, dies zu berücksichtigen, wenn Sie wirklich daran interessiert sind, zu lernen, wie man mit ihnen arbeitet.

Thomas
quelle
Beachten Sie, dass "Compilertechniken" offiziell das Thema des geplanten Bandes 7 ist. Es kann immer noch vorkommen, aber ich denke, jeder ist froh, dass Knuth nicht gewartet hat, bis er einen Compiler für die Veröffentlichung hatte.
Kilian Foth
@KilianFoth ja ich weiß. Aber ich würde erwarten, dass künstliche Programmiersprachen in einem solchen Buch verwendet werden. Vermutlich auf ein MMIX ausgerichtet (das zweite M ist kein Tippfehler :-) basierter Computer. Und ETA von vol. 5 ist 2020 ....
Thomas
56

Sie jungen Whippersnapper überraschen mich manchmal. Sie haben allzu oft keine Ahnung, dass etwas passiert ist, bevor Sie in die Schule gegangen sind. (Ich habe das gleiche Problem. Ich habe lange gebraucht, um zu begreifen, dass 15 Jahre aus Sicht der Erwachsenen eigentlich eine sehr kurze Zeit waren. Das ist ungefähr die Zeitspanne von Hiroshima bis zur Kubakrise. Für mich ist der Zweite Weltkrieg gerecht Geschichte, aber mein Vater hat gekämpft, und meine Mutter war in der Mittelstufe.)

TAOCP. Vol. 1, "Fundamental Algorithms", 1. Auflage, wurde erstmals 1968 gedruckt. Das ist 45 Jahre her. Knuth hat die Serie schon lange vorher geplant.

Als Referenz: Der Intel 8086 erschien 1978, zehn Jahre später. Die PASCAL-Sprache erschien erstmals 1971; Das Jensen & Wirth-Buch, über die zweite Version der Sprache, erschien 1974. Die anfängliche Entwicklung von C war 1969-1973: K & R wurde 1978 veröffentlicht.

Knuth wollte mit der Serie das Feld abdecken. Er legte den Stil fest, DANN, um den Praktizierenden von Nutzen zu sein. Er hatte nie erwartet, dass diese Serie buchstäblich zu seinem Lebenswerk werden würde, oder dass das Schreiben weit über ein halbes Jahrhundert reichen würde, wenn er endlich fertig ist.

Die Assemblersprache ist heute wohl nicht mehr so ​​kritisch wie damals, aber sie ist immer noch weitaus wichtiger, als die Java / C ++ / Javascript / Python / Perl-Mavens es von Ihnen allen erwarten würden.

Jetzt geh weg von meinem Gesetz!

John R. Strohm
quelle
Knuth hat 1960 einen ALGOL-Compiler implementiert, und ALGOL sollte für das Veröffentlichen von Algorithmen geeignet sein. Ich denke, dies beantwortet die Frage nicht wirklich.
Peter Taylor
10
Ich bin wirklich nicht überzeugt, dass die Begründung die Verfügbarkeit der Zeit war. LISP war verfügbar, wenn er wollte, dass es ein hohes Maß an Abstraktion aufweist, wie es die Mathematik tut. Ich glaube, er hat sich wegen des ersten Wortes des Titels der Versammlung angeschlossen. Grundlegend. Nichts ist für Algorithmen grundlegender als die schrittweisen Anweisungen für eine einfache dumme Maschine. es zwingt Sie, den Algorithmus vollständig zu zerlegen, anstatt auf hoher Ebene darüber nachzudenken, was in dem Buch nicht seine Absicht war.
Jimmy Hoffa
1
Aus diesem Grund bot meine Schule einen Kurs für historische Computer an, in dem Sie einen Altair und einige PDPs programmieren können.
Rig
@Rig - im Ernst? Jetzt fühle ich mich alt. Obwohl nicht so alt, wie HPGL einem neuen Mitarbeiter zu erklären und zu entdecken, dass sie noch nie von einem Stiftplotter gehört oder gesehen haben!
Martin Beckett
6
+1 wegen des amüsanten Geschwätzes sowie relevanter Infos.
Luser Droog
43

Knuth bespricht seine Argumentation im Vorwort. Ich zitiere nur ein paar Kleinigkeiten:

... Ich musste mich entscheiden, ob ich eine algebraische Sprache wie ALGOL oder FORTRAN oder eine maschinenorientierte Sprache für diesen Zweck verwenden wollte. Vielleicht stimmen viele der heutigen Computerfachleute meiner Entscheidung, eine maschinenorientierte Sprache zu verwenden, nicht zu, aber ich bin aus den folgenden Gründen überzeugt, dass dies definitiv die richtige Wahl war:

  1. Algebraische Sprachen eignen sich eher für numerische Probleme als für die hier betrachteten nicht-numerischen Probleme. [...]
  2. ... Durch das Schreiben in einer maschinenorientierten Sprache tendiert der Programmierer dazu, eine viel effizientere Methode zu verwenden. es ist viel näher an der Realität.
  3. Die Programme, die wir benötigen, sind bis auf wenige Ausnahmen alle eher kurz ...
  4. Eine Person, die sich mehr als beiläufig für Computer interessiert, sollte gut in Maschinensprache geschult sein ...
  5. Eine gewisse Maschinensprache wäre sowieso nötig ...

Obwohl er nicht direkt darauf hinweist, denke ich, dass seine Erwähnung von ALGOL und FORTRAN auf ein anderes Problem hinweist, das er vermieden hat und das möglicherweise noch wichtiger ist. Nehmen wir an, er hat Algol gewählt (eindeutig besser für nicht numerische Programme geeignet als Fortran). Ich würde postulieren , dass Algol wahrscheinlich sogar wäre mehr fremd die meisten der heutigen Programmierer als die Assemblersprache wählte er.

Für die dritte Ausgabe überarbeitete er den MIX, um ihn besser an moderne Prozessoren anzupassen, und musste den Code dafür neu schreiben. Ich würde jedoch davon ausgehen, dass, wenn er eine höhere Sprache verwendet hätte, das Umschreiben wesentlich umfangreicher gewesen wäre - und alle Gründe, die er genannt hat, auch weiterhin bestehen würden.

Jerry Sarg
quelle
Außerdem waren Compiler damals in der Regel teuer. Jahre nach Erscheinen von TAOCP Band 1 interviewte ich an einem Ort, an dem ich das Geld nicht für einen ausgeben wollte (und um ehrlich zu sein, war der IBM 370-Assembler nicht so schlecht), und meine Frau arbeitete in einem Assemblersprachengeschäft einige Jahre später.
David Thornley
2
Wie kann ich Punkt 4 verbessern?
Javier
5
@Javier hol eine Kopie und schreibe +1 in den Rand.
Luser Droog
29

Knuth hat seine aktualisierte Begründung auch:

Warum eine Maschinensprache?

Viele Leser denken zweifellos: `` Warum ersetzt Knuth MIX durch eine andere Maschine, anstatt sich nur an eine Programmiersprache auf hohem Niveau zu halten? Kaum jemand setzt heutzutage Assembler ein. ''

Solche Leute haben ein Recht auf ihre Meinung, und sie brauchen sich nicht darum zu kümmern, die maschinensprachlichen Teile meiner Bücher zu lesen. Die Gründe für die Maschinensprache, die ich im Vorwort zu Band 1 aus den frühen 1960er Jahren genannt habe, sind jedoch bis heute gültig:

  • Eines der Hauptziele meiner Bücher ist es, zu zeigen, wie Konstruktionen auf hohem Niveau tatsächlich in Maschinen implementiert werden, und nicht nur, wie sie angewendet werden. Ich erkläre Coroutine-Verknüpfungen, Baumstrukturen, Zufallszahlengenerierung, hochpräzise Arithmetik, Radix-Konvertierung, Packen von Daten, kombinatorische Suche, Rekursion usw. von Grund auf.
  • Die Programme, die in meinen Büchern benötigt werden, sind im Allgemeinen so kurz, dass ihre Hauptpunkte leicht verstanden werden können.
  • Leute, die sich mehr als beiläufig für Computer interessieren, sollten zumindest eine Vorstellung davon haben, wie die zugrunde liegende Hardware ist. Andernfalls sind die Programme, die sie schreiben, ziemlich seltsam.
  • Maschinensprache ist in jedem Fall erforderlich, da viele der von mir beschriebenen Softwareprogramme ausgegeben werden.
  • Das Ausdrücken grundlegender Methoden wie Algorithmen zum Sortieren und Suchen in Maschinensprache ermöglicht aussagekräftige Studien über die Auswirkungen der Cache- und RAM-Größe und anderer Hardware-Eigenschaften (Speichergeschwindigkeit, Pipelining, Mehrfachausgabe, Lookaside-Puffer, Größe von Cache-Blöcken). etc.) beim Vergleich verschiedener Schemata.

Außerdem, wenn ich eine Hochsprache verwendet habe, welche Sprache sollte es sein? In den 1960er Jahren hätte ich wahrscheinlich Algol W gewählt; in den siebziger Jahren hätte ich dann meine Bücher mit Pascal umschreiben müssen; in den achtziger Jahren hätte ich sicherlich alles auf C geändert; in den 1990er Jahren hätte ich auf C ++ und dann wahrscheinlich auf Java umsteigen müssen. In den 2000er Jahren wird zweifellos noch eine andere Sprache de rigueur sein. Ich kann es mir nicht leisten, meine Bücher umzuschreiben, wenn Sprachen in Mode kommen oder nicht. sprachen sind nicht der punkt meiner bücher, sondern der punkt, den du in deiner lieblingssprache machen kannst. Meine Bücher konzentrieren sich auf zeitlose Wahrheiten.

Daher werde ich weiterhin Englisch als die Hochsprache in TAOCP verwenden und ich werde weiterhin eine Niedrigsprache verwenden, um anzugeben, wie Maschinen tatsächlich berechnen. Leser, die nur Algorithmen sehen möchten, die bereits als Plug-in in einer modischen Sprache verpackt sind, sollten die Bücher anderer kaufen.

Die gute Nachricht ist, dass die Programmierung für RISC-Maschinen angenehm und einfach ist, wenn die RISC-Maschine ein schönes, klares Design hat. Ich muss mich also nicht mit arkanen, fummeligen kleinen Details befassen, die von den Hauptpunkten ablenken. In dieser Hinsicht wird MMIX deutlich besser sein als MIX.

Alan Shutko
quelle