Wurde die Semantik von TeX (als Programmiersprache) jemals formalisiert?

Es scheint mir, dass die von verwendete Makrosprache möglicherweise als eine Art System zur Umschreibung von Begriffen oder eine Art Programmiersprache mit Call-by-Name-Scoping angesehen werden kann.$\TeX$

Sogar moderne Implementierungen der Engine (z. B. ) interpretieren Code ganz direkt, und mir ist kein Versuch bekannt, die Ausführung zu optimieren (wie es moderne Optimierungsinterpreter tun können). Es wird jedoch sehr schwierig sein , die richtigen Optimierungspässe für eine Sprache wie zu entwickeln, da die Makro-Neudefinitionen eine "Fernwirkung" haben können und Makros neu definiert werden können, indem sie beim Namen aufgerufen werden.X e$\TeX$$\mathit{Xe}\TeX$$\TeX$

Die Implementierung eines hypothetischen Optimierungsinterpreters für in der Praxis ein sehr schwieriges, aber auch ein sehr nützliches Problem, da in der gesamten Mathematik und Wissenschaft verwendet wird und langsame Kompilierungszeiten ein bekannter Nachteil des Systems sind. Beachten Sie, dass der Großteil der Zeit für die Interpretation von Code aufgewendet wird, nicht für die Berechnung des tatsächlichen Schriftsatzes, insbesondere wenn rechenintensive Pakete verwendet werden (z. B. ).$\TeX$$\TeX$tikz

Vielleicht könnte eine formale Semantik für die Sprache ein Anfang sein, um das Problem anzugehen. Wurde die Semantik der Programmiersprache jemals formalisiert?$\TeX$

(Mit Entschuldigung für eine lange Antwort, die in eine Richtung geht, die sich vom Umfang der Website unterscheidet: Ehrlich gesagt war ich überrascht, die Frage hier überhaupt zu sehen….)

TeX wurde zum Setzen und nicht zum Programmieren entwickelt. es ist also bestenfalls "seltsam", wenn man es als Programmiersprache betrachtet.

- Donald Knuth, Digitale Typografie, Seite 235

Ich habe in den letzten Jahren viel über die frühe Geschichte von TeX (um 1977) gelesen und viel darüber, was Knuth geschrieben hat. Mein Fazit ist, dass in dem Moment, in dem wir über „TeX (als Programmiersprache)“ sprechen , bereits etwas nicht stimmt.

Wenn wir uns die frühen „Designdokumente“ für TeX ansehen , die zuvor geschrieben wurden (siehe TEXDR.AFTund TEX.ONEin Digital Typography veröffentlicht ), ist es klar, dass Knuth ein System entwarf, das hauptsächlich für den Satz Die Kunst der Computerprogrammierung gedacht war (er hat gesagt (z. B. hier ). Die Hauptnutzer, die er im Sinn hatte, waren er selbst und seine Sekretärin, mit der Idee, dass es, entsprechend modifiziert, allgemeiner nützlich sein könnte. Um das Tippen zu sparen, musste man immer wieder etwas tun (z. B. jedes Mal, wenn TAOCP ein Zitat eines Autors einschließen musste, wollte man sich vertikal um einen bestimmten Betrag bewegen, einen bestimmten Zeilenumbruch setzen, eine bestimmte Schriftart auswählen, den Text eingeben zitiere rechtsbündig, nimm eine andere Schriftart, setze den Namen des Autors ...), es gab Makros.

Sie können den Rest erraten. Was wir in TeX haben, ist ein Fall von „versehentlichem Turing-Complete“ ( mehr ), mit der Ausnahme, dass es mitten in einer Community passiert ist (Informatiker und Mathematiker, und DEK selbst ist ebenfalls „schuld“), die (leider) zu klug, um das zu ignorieren. (Der Legende nach hatte Michael Spivak noch nie programmiert, bevor er auf TeX gestoßen war, aber er war so begeistert, dass er schließlich AMS-TeX schrieb, zu der Zeit eines der kompliziertesten Makros, die es gab.) Weil TeX geschrieben wurde Um auf eine große Anzahl von Systemen portierbar zu sein (was zu dieser Zeit ein großes Problem war), gab es immer die Versuchung, alles in TeX zu tun. Außerdem wegen seiner Erfahrung als Compiler, Knuth schrieb TeX wie einen Compiler und beschrieb es gelegentlich als einen, und wenn das Programm, das an Ihrer Eingabe arbeitet, ein „Compiler“ ist, dann programmieren Sie sicher, oder?

Lesen Sie in dieser Antwort etwas mehr darüber, wie Knuth keine Programmierung in TeX vorhatte und wie er „viele der Programmierfunktionen von TeX erst nach dem Treten und Schreien einfügte“ . Was auch immer seine Absichten waren, wie ich sagte, die Leute begannen, Wege zu finden, um das TeX-Makrosystem (ab) zu verwenden, um überraschende Programmierleistungen zu erzielen. Knuth fand dies faszinierend und (zusätzlich zum Hinzufügen einiger Funktionen in TeX selbst) nahm er einige davon in Anhang D „Schmutzige Tricks“ des TeXbook auf, aber es stellte sich heraus, dass „neun von zehn Beispielen darin sind wird bei der Implementierung von LaTeX verwendet “.

Lassen Sie es mich anders sagen: LaTeX, das Makrosystem, das Leslie Lamport als Idee über TeX geschrieben hat , ist großartig. Das Erstellen von Dokumenten auf semantische, strukturierte und menschenorientierte Art und Weise anstelle der seitenorientierten Art und Weise von (Knuth) TeX (oder wie Lamport es nannte, eher logisch als visuell ) ist großartig. Aber die Umsetzung etwas so komplizierte , wie LaTeX TeX - Makros und nicht in einer „richtigen“ Programmiersprache ist, meiner Meinung nach, und zumindest , wenn es heute getan wurde, irgendwo zwischen einem riesigen Fehler gemacht und einem Akt der mutwilligen Perversität. Sogar Knuth ist schockiert, dass die Leute nicht nur das TeX-Programm erweitern, sondern alles in TeX-Makros tun.

Heutzutage gibt es viel bessere Möglichkeiten, „zu programmieren“. Sie können ein externes Programm in einer der vielen Sprachen verwenden, die auf den meisten Computern verfügbar sind, oder Sie können LuaTeX verwenden und in Lua programmieren (und mit TeX-Makros allein bessere Arbeit leisten als jemals zuvor, da Sie interne Strukturen und Funktionen manipulieren können Algorithmen auf der richtigen Ebene). Und wenn Sie es richtig machen, könnten Sie Programme haben, die besser oder schneller funktionieren als die, die in TeX-Makros implementiert sind.

Die Aufgabe, Programme in TeX schneller zu machen, ist in diesem Licht beinahe amüsant und erinnert mich an die letzten Worte des Papiers, in dem eine andere „versehentlich vollständige“ Programmiersprache beschrieben wird: Tom Wildenhains liebenswertes „ On the Turing Completeness of MS“ PowerPoint ( Video ) vom letzten Jahr:

Während der PPTXTM die theoretische Möglichkeit der PowerPoint-Entwicklung beweist, […]. Bei der Optimierung von PowerPoint-Anwendungen muss ebenfalls gearbeitet werden. Hier gibt es ein großes Potenzial, die automatische Pufferung der nächsten Folie durch PowerPoint zu nutzen, die durch vorsichtiges Platzieren der Folie verwendet werden kann, um die Anwendungsleistung erheblich zu steigern.

Die Anekdote, die Lipton beschreibt, ist illustrativ. Es hat nicht nur nie eine formale Semantik von TeX gegeben, es ist auch unwahrscheinlich, dass es eine gibt. Es ist einfach zu "komisch" eine "Sprache" dafür, und (wie ich hoffe, dass ich es oben erklärt habe) es ist nicht einmal als Sprache gedacht. Zum Beispiel könnten Sie denken, Sie schreiben Makros als Funktionen, aber Sie fügen ein einzelnes, streuendes Zeichen (sogar ein Leerzeichen ) darin ein, und TeX behandelt es sofort als eine Satzanweisung.

Kurz gesagt: TeX kehrt zum frühestmöglichen Zeitpunkt zum Schriftsatz zurück, und wenn es Makros erweitert, tut es dies widerwillig (ungeduldig, um zu seiner „echten“ Arbeit des Schriftsatzes zu gelangen), und diese Erweiterungen können selbst von Hunderten von Arten des „Zustands“ innerhalb abhängen Das TeX-Programm (die Werte von Parametern wie \hsizeoder \baselineskip, der Inhalt von Kästchen und anderen Registern ...), weshalb jede formale Semantik von TeX notwendigerweise etwas sein muss, das den gesamten Status des Programms und seinen gesamten Speicher berücksichtigt, bis wir Am Ende steht so etwas wie "die Bedeutung von TeX-Code ist das, was auch immer TeX tut", in einer Form, die komplexer ist als das TeX-Programm selbst.

Also gut, (wenn ich Sie überzeugt habe) TeX war nicht als Programmiersprache gedacht und funktioniert nicht wie echte, es gibt keine formale Semantik und es gibt bessere Möglichkeiten, heute zu programmieren - aber all dies hilft nicht bei Ihrer Die eigentliche Frage / das eigentliche Problem ist, dass in der Praxis viele Dokumente, die für die Verarbeitung durch TeX bestimmt sind , komplizierte Makros (wie LaTeX und TikZ) verwenden, atemberaubende Gebäude von ungeheurer Komplexität, die aufeinander aufbauen. Wie können wir es schneller machen und "Optimierungspässe" entwickeln?

Mit der formalen Semantik IMO kommen Sie nicht dahin. Ich habe kürzlich darüber nachgedacht und im Folgenden einige vorläufige Gedanken.

Mein Eindruck ist, dass Knuth einer der erfahrenen Compiler-Schreiber in den 1960er Jahren war (deshalb wurde er gebeten, das Compiler-Buch zu schreiben, das sich zur Kunst der Computerprogrammierung entwickelte ), und TeX ist (in vielerlei Hinsicht) so geschrieben, wie es Compiler waren geschrieben in den 1970er Jahren, sagen wir. Compilertechniken und -design wurden seitdem verbessert, und das TeX-Programm kann es auch sein. Hier sind einige Dinge, die getan werden können, um die Dinge zu beschleunigen:

• Im Kern ist TeX wie eine "Interpretationsroutine" geschrieben, bei der die TeX "Augen" und "Mund" (ihre Eingaberoutinen) Anweisungen an ihren "Magen" (ihre semantischen Routinen) liefern, die nacheinander ausgeführt werden. (Eine Liste finden Sie in Teil 15 des TeX-Programms .) Wenn TeX beispielsweise auf Augen / Mund \hfilloder \hskipEingaben trifft , erhält der Magen den Befehl „hskip“, auf den er einwirkt. Dies ähnelt dem, was heute als Bytecode-Interpreter bezeichnet wird, und es kann sinnvoll sein, das TeX-Programm so umzugestalten, dass diese Bytecodes / Opcodes explizit ausgegeben werden, damit wir möglicherweise vorhandene (heute üblichere) Compilertechniken verwenden können. Oder sie zumindest zwischenspeichern, um Wiederholungen zu vermeiden. Es gibt natürlich viele Herausforderungen:

  • Die Ausführung eines Befehls im „Magen“ beinhaltet in der Regel noch das Lesen der Eingabe, dh die Arbeit der Eingaberoutinen und der semantischen Routinen erfolgt nicht in getrennten Phasen. Wenn beispielsweise der Befehl "hskip" gegeben wird \hskip(anstatt zu sagen \hfill), wird er aufgerufen scan_glue, um eine Klebstoffspezifikation aus der Eingabe zu lesen, was wiederum das Erweitern von Makros usw. beinhalten kann, bis genügend Token für den Klebstoff gefunden wurden, wobei der Eingabestapel in a verbleibt wesentlich anderer Zustand.

  • Engines wie eTeX und pdfTeX sowie XeTeX und LuaTeX führen neue Befehle und Grundelemente ein (die eTeX / pdfTex-Grundelemente werden praktisch von jedem in der Praxis verwendet). Sie müssen sie auch unterstützen, nicht nur die im ursprünglichen Knuth's TeX-Programm.

• Wir könnten so etwas wie „spekulative Ausführung“ tun, zukünftige Absätze (möglicherweise beginnend an natürlichen Kontrollpunkten wie neuen Abschnitten oder Kapiteln) parallel verarbeiten (unter Verwendung mehrerer Kerne), den gesamten internen TeX-Status verfolgen, den sie verwenden (von dem sie abhängen), und werfen Entfernen Sie diese Arbeit (und wiederholen Sie sie), wenn Sie später feststellen, dass ein früherer Absatz einen Teil dieses Zustands ändert. Momentan läuft TeX vollständig sequentiell auf 1 Prozessor; Die typische Hardware hat sich in eine andere Richtung bewegt, und es sind mehrere Kerne verfügbar.

• Noch einfacher wäre es, die Arbeit (auf welchen TeX-Status zugegriffen und welcher geändert wurde) einfach in einem bestimmten Abschnitt der Eingabedatei zwischenzuspeichern. (Wir könnten diese Zwischenspeicherung auf der Ebene der Eingabe durchführen - das Nettoergebnis der Erweiterung aller Makros - oder auf der Ebene der zusammengestellten Boxen oder bis zum Gesamtstatus des Programms.) Zum Beispiel den Inhalt im Inneren Es \begin{tikzpicture} … \end{tikzpicture}ist unwahrscheinlich, dass a in hohem Maße vom TeX-Status abhängt, beispielsweise vom Seitenzähler. Wenn wir das TeX-Dokument neu kompilieren, können wir die gesamte Arbeit einfach wiederverwenden - wenn wir genügend Informationen gespeichert haben, um zu wissen, dass dies sicher ist. (Natürlich hat insbesondere TikZ Möglichkeiten, dies zu externalisieren und die Ergebnisse einzubeziehen, aber die Idee ist allgemeiner.)

• Wir können Techniken (z. B. solche, die in der funktionalen Programmierung verwendet werden) verwenden, um eine TeX-Verarbeitung mit „Löchern“ durchzuführen. Wenn Sie z. B. jetzt \ref{foo}in LaTeX schreiben , um auf eine (etwa zukünftige) Abschnittsnummer zu verweisen, funktioniert dies nur in zwei Kompilierungsdurchläufen: Zuerst wird das gesamte Dokument verarbeitet (alle Absätze, Gleitkommazahlen usw.), wobei die Abschnittsnummern in eine Hilfsdatei geschrieben werden, und dann in einem zweiten Durchgang alleDie Arbeit wird erneut ausgeführt, wobei die Abschnittsnummer dieses Mal tatsächlich verfügbar ist. (Diese Art von Hack mag zu diesem Zeitpunkt unvermeidlich gewesen sein, und ich weiß, dass die Auswirkung auf die Laufzeit "nur ein konstanter Faktor" ist, aber ...) Was wäre, wenn wir das Dokument einfach mit einem "Loch" verarbeiten könnten? ( ein Feld mit unbestimmtem Inhalt, aber geschätzter Breite) für die Abschnittsnummer übrig, dann am Ende der Dokumentverarbeitung das Feld ausfüllen? (Ja, unsere geschätzte Breite kann sich als falsch herausstellen, und der Absatz muss möglicherweise erneut verarbeitet werden, und folglich auch die Seite. Wir könnten jedoch entweder die Arbeit bei Bedarf erledigen oder aus Gründen der Geschwindigkeit einen Modus akzeptieren, in dem wir eine falsche Breite für zulassen die Abschnittsnummer.)

• Ähnliche Techniken können für die interaktive Bearbeitung eines TeX-Dokuments verwendet werden: Wenn Sie einen Absatz bearbeiten, kann dieser "live" verarbeitet werden, wobei zukünftige Absätze einfach in der Galeere nach unten verschoben werden (etwa). Wir wissen, dass dies möglich ist, da es bereits (kommerzielle) TeX-Implementierungen gibt, z. B. BaKoMaTeX und Texpad und die früheren Texturen . (Siehe das Video auf der Homepage von BaKoMa-TeX und ähnlichem von TeXpad, zB dieses Video - ich habe das letztere ausprobiert und es war in der Praxis unerträglich fehlerhaft .)

• Nicht zu unterschätzen: Der Wert, dem Benutzer Dinge zu zeigen, die TeX besser debuggbar machen. Im Moment sehen Benutzer nur ihre TeX-Eingaben und wissen nicht genau, welche Arbeit TeX leistet, z. B. wie viel Zeit sie für das Zeilenumbruch von Absätzen oder für die Makroerweiterung (und von welchen Makros), welche Boxen sie zusammenstellen und verwenden wegwerfen, welche Specials von welchem ​​Paket ausgegeben werden usw. Ich glaube (vielleicht optimistisch), dass es Benutzer gibt, die diese Informationen sehen möchten und es nützlich finden, z. B. zu wissen, ob das seltsame Paket für die Schattierung verwendet wird Gleichungen mit einem Farbverlauf im Hintergrund sind billig (was die Verarbeitungszeit nur geringfügig verlängert) oder nicht. Wenn sie sehen, wo viel verschwenderische Arbeit geleistet wird, können sie etwas davon wegwerfen (zumindest bis zu ihrer endgültigen Auflage). (Dies ähnelt in etwa Compilern oder anderen Tools, die Profilinformationen in Programme einfügen.) TeX transparenter und debuggbarer zu machen, kann beispielsweise eine enorme Verbesserung der Benutzerfreundlichkeit bedeuten. (TeX ist für seine Zeit schon recht benutzerfreundlich und debuggbar, wenn wir meistens einfaches TeX mit sehr wenigen Makros verwenden, aber nicht mit LaTeX oder wie der Großteil der Benutzer es heute antreffen.)

Bei zukünftigen Arbeiten sollte wahrscheinlich auch LuaTeX berücksichtigt werden, die derzeit die beste Modifikation von TeX ist.

All dies sind nur müßige Gedanken (ich habe keine von ihnen implementiert, um zu wissen, welche Anstrengungen erforderlich sind oder wie viel Geschwindigkeit wir gewinnen würden), aber ich hoffe, dass dies dazu beiträgt, Ihre Frage zu beantworten oder Ihnen Ideen für zukünftige Richtungen zu geben .

Nein, meines Wissens wurde noch nicht an der Formalisierung von TeX gearbeitet, an der Sie interessiert sind.

(Was folgt, ist ein subjektiver und persönlicher Kommentar). Ich denke, es ist eine faszinierende und gut durchdachte Idee, und Ihre Motivation, damit Optimierungen durchzuführen, klingt vernünftig - eine weitere verwandte Frage ist, ob Sie ein Bytecode-Format definieren könnten, um die Interpretation zu beschleunigen. Andererseits hat die Idee zwei Nachteile.

Erstens ist mir nicht klar, dass es ein großes Optimierungspotenzial gibt (z. B. welche Art von programmerhaltenden Transformationen könnte man durchführen, um die Berechnung zu beschleunigen?), Da die Sprachsemantik möglicherweise in engem Zusammenhang mit dem Parsen steht der Zeichenfluss, und damit der Gestaltung optimierungsfreundlicher Zwischendarstellungen wenig entgegenkommend.

Zweitens ist die Notwendigkeit von Verbesserungen bei der Geschwindigkeit der TeX-Interpretation nicht gut begründet: Die Geschwindigkeit der Erstellung der Batch-Geschwindigkeit ist dank Hardware-Verbesserungen angemessen geblieben. Fälle, in denen eine Beschleunigung erwünscht sein könnte, sind komplexe Grafikpakete (die Erstellung von Beamer-Präsentationen kann einige Zeit in Anspruch nehmen), Pakete, in die umfangreiche Berechnungen eingebettet sind (eine andere Sprache ist möglicherweise besser geeignet), und Anwendungsfälle, bei denen eine schnelle Neuerstellung für sofortiges Benutzer-Feedback erforderlich ist (aber dann) Inkrementalität statt Optimierung mag der Punkt sein; eine formale Semantik würde sicherlich auch bei inkrementellen Implementierungen hilfreich sein).

Das heißt: Das klingt nach einem lustigen, lehrreichen Thema, aber mir ist nicht klar, dass die praktischen Gründe für die Ausführung der Arbeit stark sind. Wenn jemand aus Neugier daran interessiert war, klingt dies nach einem hervorragenden Abenteuer, aber ansonsten gibt es möglicherweise andere Möglichkeiten, die gleichen Fähigkeiten einzusetzen, deren Wirkung von Endbenutzern stärker nachgefragt wird.