La sémantique de TeX (en tant que langage de programmation) a-t-elle déjà été formalisée?

Il me semble que le macro langage employé par peut être considéré comme une sorte de système de réécriture de termes ou une sorte de langage de programmation avec une portée d'appel par nom.$\TeX$

Même les implémentations modernes du moteur (par exemple ) interprètent le code de manière assez directe et je ne suis au courant d'aucune tentative d'optimisation de l'exécution (comme les interprètes d'optimisation modernes peuvent le faire). Cependant, concevoir des passes d'optimisation correctes pour un langage comme va être très difficile en raison de "l'action à distance" que peuvent avoir les redéfinitions de macros et de la capacité de redéfinir les macros en les appelant par leur nom.$\TeX$$\mathit{Xe}\TeX$$\TeX$

Donc, implémenter un interpréteur d'optimisation hypothétique pour semble un problème très difficile en pratique mais aussi très utile, car est utilisé partout en mathématiques et en sciences et les temps de compilation lents sont un inconvénient connu du système. Notez que la majorité du temps est consacrée à l'interprétation du code, et non au calcul de la composition réelle, en particulier lorsque des packages de calcul lourds sont utilisés (tels que ).$\TeX$$\TeX$tikz

Peut-être qu'une sémantique formelle pour la langue pourrait être un début pour résoudre le problème. La sémantique du langage de programmation déjà été formalisée?$\TeX$

(Je m'excuse pour une longue réponse qui va dans une direction différente de la portée du site: franchement, j'ai été surpris de voir la question ici en premier lieu….)

TeX a été conçu pour la composition, pas pour la programmation; il est donc au mieux «bizarre» lorsqu'il est considéré comme un langage de programmation.

- Donald Knuth, Typographie numérique, page 235

J'ai lu beaucoup de choses au cours des deux dernières années sur l'histoire ancienne (vers 1977) de TeX, et beaucoup de ce que Knuth a écrit. Ma conclusion est qu'au moment où nous parlons de «TeX (en tant que langage de programmation)» , quelque chose ne va pas déjà.

Si nous regardons les premiers «documents de conception» pour TeX écrits auparavant (voir TEXDR.AFTet TEX.ONE, publiés dans Digital Typography ), il est clair que Knuth concevait un système principalement destiné à composer The Art of Computer Programming (a-t-il dit (par exemple ici ) que les principaux utilisateurs qu'il avait en tête étaient lui-même et son secrétaire), avec l'idée que, convenablement modifié, il pourrait être utile de manière plus générale. Pour économiser la frappe, pour des choses que l'on devait faire à plusieurs reprises (par exemple, chaque fois que TAOCP devait inclure une citation d'un auteur, vous voudriez vous déplacer verticalement d'un certain montant, définir un certain saut de ligne, choisir une certaine police, composer le citer à droite, prendre une autre police, composer le nom de l'auteur…), il y avait des macros.

Vous pouvez deviner le reste. Ce que nous avons dans TeX est un cas de «accidentellement Turing-complet» ( plus ), sauf que cela s'est produit au milieu d'une communauté (informaticiens et mathématiciens, et DEK lui-même est à «blâmer» aussi) qui étaient (malheureusement) trop intelligent pour ignorer cela. (La légende raconte que Michael Spivak n'avait jamais programmé avant de rencontrer TeX, mais il était tellement séduit qu'il finit par écrire AMS-TeX, à l'époque l'un des ensembles de macros les plus compliqués qui existent.) Parce que TeX a été écrit pour être portable sur un grand nombre de systèmes (ce qui était très important à l'époque), il y avait toujours une tentation de tout faire dans TeX. En outre, en raison de son expérience en écriture de compilateur, Knuth a écrit TeX comme un compilateur, et l'a parfois décrit comme tel, et si le programme qui fonctionne sur votre entrée est un «compilateur», alors vous programmez sûrement, non?

Vous pouvez en lire un peu plus sur la façon dont Knuth n'avait pas l'intention de faire de programmation dans TeX, et comment il «n'a intégré de nombreuses fonctionnalités de programmation de TeX qu'après avoir donné des coups de pied et des cris», dans cette réponse . Quelles que soient ses intentions, comme je l'ai dit, les gens ont commencé à trouver des moyens d'utiliser (ab) le système de macro TeX pour accomplir des exploits de programmation surprenants. Knuth a trouvé cela fascinant et (en plus d'ajouter quelques fonctionnalités dans TeX lui-même) en a inclus quelques-unes dans l'annexe D «Dirty Tricks» de The TeXbook, mais il s'avère, malgré le nom, que «neuf exemples sur dix y sont utilisé dans la mise en œuvre de LaTeX ”.

Permettez-moi de dire les choses autrement: LaTeX, le système de macro que Leslie Lamport a écrit au-dessus de TeX, comme idée , est excellent. La création de documents d'une manière sémantique, structurée et orientée vers l'homme, plutôt que selon la méthode orientée page de (Knuth) TeX (ou, comme Lamport l'a appelé, logique plutôt que visuelle ) est excellente. Mais implémenter quelque chose d'aussi compliqué que LaTeX en utilisant des macros TeX plutôt que dans un langage de programmation «approprié» est, à mon avis et du moins si cela a été fait aujourd'hui, quelque part entre une erreur géante et un acte de perversité gratuite. Même Knuth est choqué que les gens ne se contentent pas d'étendre le programme TeX au lieu de tout faire dans les macros TeX.

Aujourd'hui, il existe de bien meilleures façons de faire de la «programmation»; vous pouvez utiliser un programme externe dans l'une des nombreuses langues largement disponibles sur les ordinateurs de la plupart des gens, ou vous pouvez utiliser LuaTeX et programmer dans Lua (et faire un meilleur travail que vous ne l'auriez jamais fait avec les macros TeX seules, car vous pouvez manipuler les structures internes et algorithmes au bon niveau). Et si vous le faites correctement, vous pourriez avoir des programmes qui fonctionnent mieux ou plus rapidement que ceux mis en œuvre dans les macros TeX.

La tâche de rendre les programmes dans TeX plus rapides est presque amusante vu sous cet angle, et me rappelle les derniers mots de l'article décrivant un autre «langage» de programmation «accidentellement Turing complet»: le charmant « On the Turing Completeness of MS » de Tom Wildenhain PowerPoint ( vidéo ) de l'année dernière:

Alors que le PPTXTM prouve la possibilité théorique du développement PowerPoint, […]. Il faut également travailler sur l'optimisation des applications PowerPoint. Il y a beaucoup de potentiel ici pour exploiter la mise en mémoire tampon automatique de PowerPoint de la diapositive suivante, qui, grâce à un placement soigneux des diapositives, peut être utilisée pour augmenter considérablement les performances de l'application.

L' anecdote que Lipton décrit est illustrative. Non seulement il n'y a jamais eu de sémantique formelle de TeX, mais il est également peu probable qu'il y en ait une. C'est tout simplement trop «bizarre» une «langue» pour cela, et (comme j'espère l'avoir expliqué ci-dessus), elle n'est même pas conçue comme une langue. Par exemple, vous pensez peut-être que vous écrivez des macros en tant que fonctions, mais y introduisez un seul caractère errant (même un espace ), et TeX le traite immédiatement comme une instruction de composition.

En bref: TeX revient à la composition à la première occasion, et quand il développe des macros, il le fait à contrecœur (impatient d'accéder à son "vrai" travail de composition), et ces extensions peuvent elles-mêmes dépendre de centaines de types d '"états" à l'intérieur le programme TeX (les valeurs de paramètres comme \hsizeou \baselineskip, le contenu des boîtes et autres registres…), c'est pourquoi toute sémantique formelle de TeX doit nécessairement être quelque chose qui prend en compte l'état entier du programme et toute sa mémoire, jusqu'à ce que nous se retrouver avec quelque chose comme «la signification du code TeX est ce que fait TeX», sous une forme plus complexe que le programme TeX lui-même.

Si bien, (si je vous ai convaincu) TeX n'était pas conçu comme un langage de programmation et ne fonctionne pas comme les vrais, il n'y a pas de sémantique formelle et il existe de meilleures façons de programmer aujourd'hui - mais tout cela ne vous aide pas question / problème réel, qui est que , dans la pratique, de nombreux documents destinés à traiter par TeX faire utiliser des macros compliquées (comme LaTeX et TikZ), édifices magnifiques de la complexité monstrueuse construite au - dessus de l'autre. Comment accélérer la mise en place de «passes d'optimisation»?

Vous n'y arriverez pas avec la sémantique formelle OMI. J'y ai récemment réfléchi et voici quelques réflexions préliminaires.

Mon impression est que Knuth était l'un des auteurs-compilateurs expérimentés dans les années 1960 (c'est pourquoi on lui a demandé d'écrire le livre des compilateurs qui est devenu The Art of Computer Programming ), et TeX est (à bien des égards) écrit de la même manière que les compilateurs étaient écrit dans les années 1970, disons. Les techniques et la conception du compilateur se sont améliorées depuis, tout comme le programme TeX. Voici quelques choses qui peuvent être faites, en accélérant les choses:

• Au fond, TeX est écrit comme une «routine d'interprétation», où les «yeux» et la «bouche» de TeX (ses routines d'entrée) délivrent des instructions à son «estomac» (ses routines sémantiques), à exécuter une par une. (Vous pouvez voir une liste dans la partie 15 du programme TeX .) Par exemple, lorsque les yeux / la bouche de TeX se rencontrent \hfillou \hskipdans son entrée, l'estomac reçoit une commande «hskip», sur laquelle il agit. Ceci est similaire à ce qu'on appelle aujourd'hui les interprètes de bytecode, et il peut être utile de refactoriser le programme TeX pour émettre ces bytecodes / opcodes de manière explicite, afin que nous puissions utiliser les techniques de compilation existantes (plus conventionnelles aujourd'hui). Ou du moins les mettre en cache pour éviter de refaire le travail. Il y a bien sûr de nombreux défis:

  • L'exécution d'une commande dans «l'estomac» implique généralement toujours la lecture de l'entrée, c'est-à-dire que le travail des routines d'entrée et des routines sémantiques ne se fait pas en phases distinctes. Par exemple, la commande «hskip», si elle est donnée \hskip(plutôt que de dire \hfill), invoquera scan_gluepour lire une spécification de colle à partir de l'entrée, ce qui peut impliquer l'expansion des macros et ainsi de suite jusqu'à ce que suffisamment de jetons soient trouvés pour la colle, laissant la pile d'entrée dans un état sensiblement différent.

  • Des moteurs comme eTeX et pdfTeX et XeTeX et LuaTeX introduisent de nouvelles commandes et primitives (les primitives eTeX / pdfTex sont pratiquement utilisées par tout le monde dans la pratique); vous devrez également les prendre en charge, pas seulement ceux du programme TeX original de Knuth.

• Nous pourrions faire quelque chose comme «une exécution spéculative», traiter des paragraphes futurs (peut-être en commençant à des points de contrôle naturels comme de nouvelles sections ou chapitres) en parallèle (en utilisant plusieurs cœurs), en gardant une trace de tous les états internes TeX qu'ils utilisent (en fonction de), et en lançant loin ce travail (et le refaire) si plus tard nous découvrons qu'un paragraphe précédent finit par changer une partie de cet état. Pour le moment, TeX fonctionne entièrement séquentiellement sur 1 processeur; le matériel typique a évolué dans une direction différente et plusieurs cœurs sont disponibles.

• Encore plus simple, nous pourrions simplement mettre en cache le travail (quel état TeX a été consulté et modifié) par une certaine section du fichier d'entrée. (Nous pourrions faire cette mise en cache au niveau de l'entrée - le résultat net de l'expansion de toutes les macros - ou au niveau de quel ensemble de boîtes ont été assemblées, ou jusqu'à l'état total du programme.) Par exemple, le contenu à l'intérieur a \begin{tikzpicture} … \end{tikzpicture}est peu susceptible de dépendre beaucoup de l'état de TeX comme le compteur de numéro de page, donc lorsque nous recompilons le document TeX, nous pouvons simplement réutiliser tout le travail - si nous avons suivi suffisamment d'informations pour savoir qu'il est sûr de le faire. (Bien sûr, TikZ en particulier a des moyens d'externaliser cela et d'inclure les résultats, mais l'idée est plus générale.)

• Nous pouvons utiliser des techniques (par exemple celles utilisées dans la programmation fonctionnelle) pour effectuer un traitement TeX avec des «trous» - par exemple en ce moment, lorsque vous écrivez \ref{foo}dans LaTeX pour faire référence à un numéro de section (par exemple futur), cela ne fonctionne que dans deux passes de compilation: tout d'abord le document entier est traité (tous les paragraphes sont composés, les flottants positionnés sur les pages, etc.) avec les numéros de section écrits dans un fichier auxiliaire, puis sur une deuxième passe tousle travail est à nouveau effectué, avec le numéro de section réellement disponible cette fois. (Ce type de piratage était peut-être inévitable à l'époque, et je sais que l'impact sur le temps d'exécution n'est «qu'un facteur constant», mais….) Et si nous pouvions simplement traiter le document avec un «trou» ( une boîte avec un contenu indéterminé mais une certaine largeur estimée) à gauche pour le numéro de section, puis à la fin du traitement du document remplir la boîte? (Oui, notre largeur estimée peut s'avérer incorrecte et le paragraphe peut nécessiter un retraitement et par conséquent même la page, mais nous pouvons soit faire le travail si nécessaire, soit accepter, pour la vitesse, un mode dans lequel nous autoriserons une mauvaise largeur pour le numéro de section.)

• Des techniques similaires peuvent fonctionner pour l'édition interactive d'un document TeX: lorsque vous éditez un paragraphe, il peut être traité «en direct», les futurs paragraphes étant simplement déplacés dans la cuisine (par exemple). Nous savons que c'est possible, car il existe déjà des implémentations TeX (commerciales) qui font cela, par exemple BaKoMaTeX et Texpad et les anciennes Textures . (Voir la vidéo sur la page d'accueil de BaKoMa-TeX et de même TeXpad, par exemple cette vidéo - j'ai essayé cette dernière et elle était insupportablement buggée dans la pratique cependant.)

• À ne pas sous-estimer: la valeur de montrer des choses à l'utilisateur, rendant TeX plus déboguable. À l'heure actuelle, les utilisateurs ne voient que leur entrée TeX et n'ont aucune idée exacte du travail que fait TeX, par exemple, combien de temps il consacre au saut de ligne pour les paragraphes, ou à la macro-expansion (et quelles macros), quelles boîtes il assemble et jeter, quelles promotions sont écrites par quel paquet, etc. Je pense (peut-être avec optimisme) qu'il existe des utilisateurs qui aimeraient voir ces informations et trouveraient utile, par exemple, de savoir si le paquet étrange qu'ils utilisent pour l'ombrage les équations avec un dégradé en arrière-plan sont bon marché (ce qui ajoute peu au temps de traitement) ou non. En voyant où beaucoup de travail inutile est accompli, ils pourraient en jeter une partie (au moins jusqu'à leur tirage final). (C'est un peu comme des compilateurs ou d'autres outils insérant des informations de profilage dans des programmes.) Rendre TeX plus transparent et débogable peut être une énorme amélioration de l'utilisabilité, par exemple. (TeX est déjà assez convivial et débogable pour son époque IMO si nous utilisons principalement du TeX ordinaire avec très peu de macros, mais pas avec LaTeX ou comment la plupart des utilisateurs le rencontrent aujourd'hui.)

De plus, tout travail futur devrait probablement prendre en compte (s'appuyer sur) LuaTeX qui est la meilleure modification de TeX que nous ayons actuellement.

Ce ne sont que des pensées oiseuses (je n'en ai implémenté aucune, pour savoir l'effort requis ou combien d'accélération nous gagnerions), mais j'espère que cela contribuera à répondre à votre question ou à vous donner des idées pour les directions futures .

Non, à ma connaissance, il n'y a eu aucun travail sur la formalisation de TeX du type qui vous intéresse.

(Ce qui suit est un commentaire subjectif et personnel). Je pense que c'est une idée intrigante et bien posée, et votre motivation à l'utiliser pour effectuer des optimisations semble raisonnable - une autre question connexe est de savoir si vous pouvez définir un format de bytecode pour accélérer l'accélération de l'interprétation. D'un autre côté, l'idée a deux inconvénients.

Tout d'abord, il n'est pas clair pour moi qu'il existe un grand potentiel d'optimisations (par exemple, quel type de transformations préservant le programme pourrait-on effectuer pour accélérer le calcul?), Car il se peut que la sémantique du langage soit intimement liée à l'analyse le flux de caractères, et donc peu accommodant à la conception de représentations intermédiaires optimisées.

Deuxièmement, la nécessité d'améliorer la vitesse d'interprétation de TeX n'est pas bien établie: la vitesse de construction de la vitesse par lots est restée raisonnable grâce aux améliorations matérielles. Les cas où les accélérations pourraient être les bienvenues sont des packages graphiques complexes (les présentations de beamer peuvent prendre un certain temps à construire), des packages incorporant des calculs riches (mais alors une autre langue peut être plus appropriée), et des cas d'utilisation nécessitant une reconstruction rapide pour une rétroaction instantanée des utilisateurs (mais ensuite l'incrémentalité, plutôt que l'optimisation, peut être le point; une sémantique formelle aiderait certainement à raisonner sur les implémentations incrémentielles également).

C'est-à-dire: cela ressemble à un sujet amusant et instructif, mais il n'est pas clair pour moi que les justifications pratiques pour faire le travail sont solides. Si quelqu'un était intéressé à le faire par curiosité, cela semble être une excellente aventure, mais sinon, il peut y avoir d'autres façons d'employer le même ensemble de compétences dont l'impact serait plus recherché par les utilisateurs finaux.