¿Se ha formalizado alguna vez la semántica de TeX (como lenguaje de programación)?

Me parece que el lenguaje macro utilizado por puede verse como algún tipo de sistema de reescritura de términos o algún tipo de lenguaje de programación con alcance de llamada por nombre.$\TeX$

Incluso las implementaciones modernas del motor (por ejemplo, ) interpretan el código de una manera bastante directa y no conozco ningún intento de optimizar la ejecución (como pueden hacer los intérpretes optimizadores modernos). Sin embargo, idear pases de optimización correctos para un lenguaje como va a ser muy difícil debido a la "acción a distancia" que pueden tener las redefiniciones de macros y la capacidad de redefinir macros llamándolos por su nombre.X e$\TeX$$\mathit{Xe}\TeX$$\TeX$

Por lo tanto, implementar un intérprete de optimización hipotético para suena un problema muy difícil en la práctica, pero también muy útil, ya que se usa en todas las matemáticas y ciencias y los tiempos de compilación lentos son un inconveniente conocido del sistema. Tenga en cuenta que la mayor parte del tiempo se dedica a interpretar el código, no a calcular la composición real, especialmente cuando se utilizan paquetes computacionalmente pesados ​​(como por ejemplo ).$\TeX$$\TeX$tikz

Tal vez una semántica formal para el lenguaje podría ser un comienzo para abordar el problema. Entonces, ¿se ha formalizado la semántica del lenguaje de programación ?$\TeX$

(Con disculpas por una respuesta larga que va en una dirección diferente al alcance del sitio: francamente me sorprendió ver la pregunta aquí en primer lugar ...)

TeX fue diseñado para la composición tipográfica, no para la programación; así que es, en el mejor de los casos, "extraño" cuando se lo considera un lenguaje de programación.

- Donald Knuth, Tipografía digital, página 235

He leído mucho en los últimos años sobre la historia temprana (circa 1977) de TeX, y mucho de lo que Knuth ha escrito. Mi conclusión es que en el momento en que hablamos de "TeX (como lenguaje de programación)" , algo ya está mal.

Si miramos los primeros "documentos de diseño" para TeX escritos antes (ver TEXDR.AFTy TEX.ONE, publicados en Digital Typography ), está claro que Knuth estaba diseñando un sistema destinado principalmente a la composición tipográfica El arte de la programación de computadoras (ha dicho (por ejemplo, aquí ) que los principales usuarios que tenía en mente eran él y su secretario), con la idea de que, adecuadamente modificado, puede ser útil de manera más general. Para guardar la escritura, para las cosas que uno tenía que hacer repetidamente (por ejemplo, cada vez que TAOCP necesitaba incluir una cita de un autor, querría moverse verticalmente en una cierta cantidad, establecer un salto de línea, seleccionar una fuente determinada, escribir la letra cite alineado a la derecha, elija otra fuente, escriba el nombre del autor ...), había macros.

Puedes adivinar el resto. Lo que tenemos en TeX es un caso de "completar accidentalmente Turing" ( más ), excepto que sucedió en medio de una comunidad (informáticos y matemáticos, y el propio DEK también tiene la "culpa") de quienes fueron (desafortunadamente) demasiado inteligente para ignorar esto. (La leyenda dice que Michael Spivak nunca había programado antes de encontrarse con TeX, pero estaba tan entusiasmado que terminó escribiendo AMS-TeX, en ese momento uno de los conjuntos de macros más complicados que existen). Porque TeX fue escrito para ser portátil en una gran cantidad de sistemas (lo cual era un gran problema en ese momento), siempre había una tentación de hacer todo en TeX. Además, debido a su experiencia en la redacción de compiladores, Knuth escribió TeX como un compilador, y ocasionalmente lo describió como uno, y si el programa que funciona en su entrada es un "compilador", entonces seguramente está programando, ¿verdad?

Puede leer un poco más sobre cómo Knuth no tenía la intención de realizar ninguna programación en TeX, y cómo "puso muchas de las funciones de programación de TeX solo después de patear y gritar", en esta respuesta . Cualesquiera que fueran sus intenciones, como dije, la gente comenzó a encontrar formas de (ab) usar el sistema macro TeX para lograr hazañas sorprendentes de programación. Knuth encontraron esta fascinante y (además de la adición de algunas características en TeX en sí) incluyó algunos de éstos en el Apéndice D “trucos sucios” de la TeXbook, pero resulta que, a pesar del nombre, que “nueve de ejemplos diez en la misma son utilizado en la implementación de LaTeX ”.

Permítanme decirlo de otra manera: LaTeX, el sistema macro que Leslie Lamport escribió sobre TeX, como idea , es excelente. La creación de documentos de una manera semántica, estructurada y orientada al ser humano, en lugar de la orientación de la página (Knuth) TeX, (o como Lamport lo llamó, lógico en lugar de visual ) es excelente. Pero implementar algo tan complicado como LaTeX usando macros TeX en lugar de un lenguaje de programación "adecuado" es, en mi opinión y al menos si se hiciera hoy, en algún lugar entre un error gigante y un acto de perversidad desenfrenada. Incluso Knuth está sorprendido de que las personas no solo extiendan el programa TeX en lugar de hacer todo en macros TeX.

Hoy en día hay formas mucho mejores de hacer "programación"; puede usar un programa externo en cualquiera de los muchos idiomas ampliamente disponibles en las computadoras de la mayoría de las personas, o puede usar LuaTeX y programar en Lua (y hacer un mejor trabajo que nunca con las macros TeX solo, porque puede manipular estructuras internas y algoritmos en el nivel correcto). Y si lo hace bien, podría tener programas que funcionen mejor o más rápido que los implementados en las macros TeX.

La tarea de hacer que los programas en TeX sean más rápidos es casi divertido cuando se ve desde esta perspectiva, y me recuerda las palabras finales del artículo que describen otro "lenguaje" de programación "accidentalmente completo de Turing": el encantador " Sobre la integridad de la EM de Turing" PowerPoint ( video ) del año pasado:

Si bien el PPTXTM demuestra la posibilidad teórica del desarrollo de PowerPoint, [...]. También es necesario trabajar en la optimización de aplicaciones de PowerPoint. Aquí hay mucho potencial para explotar el almacenamiento en búfer automático de PowerPoint de la próxima diapositiva, que a través de una colocación cuidadosa de la diapositiva puede usarse para aumentar en gran medida el rendimiento de la aplicación.

La anécdota que describe Lipton es ilustrativa. No solo nunca ha existido una semántica formal de TeX, también es poco probable que haya una. Es simplemente un "lenguaje" demasiado "extraño" para eso, y (como espero haber explicado anteriormente) ni siquiera pretende ser un idioma. Por ejemplo, puede pensar que está escribiendo macros como funciones, pero introduce un solo carácter perdido (incluso un espacio ) en él, y TeX lo trata inmediatamente como una instrucción de composición tipográfica.

En resumen: TeX vuelve a la composición tipográfica lo antes posible, y cuando expande las macros lo hace de mala gana (impaciente por llegar a su trabajo "real" de composición tipográfica), y estas expansiones pueden depender de cientos de tipos de "estados" dentro el programa TeX (los valores de parámetros como \hsizeo \baselineskip, el contenido de cuadros y otros registros ...), razón por la cual cualquier semántica formal de TeX debe ser necesariamente algo que tenga en cuenta todo el estado del programa y toda su memoria, hasta que terminar con algo como "el significado del código TeX es lo que hace TeX", en una forma más compleja que el programa TeX en sí.

Muy bien, (si te he convencido) TeX no fue pensado como un lenguaje de programación y no funciona como los reales, no hay una semántica formal, y hay mejores formas de programar hoy, pero todo esto no ayuda con tu pregunta real / problema, y es que en la práctica, muchos documentos destinados para el procesamiento por TeX hacen uso complicado macros (como el látex y TikZ), impresionantes edificios de complejidad monstruosa construido encima de la otra. ¿Cómo podemos hacerlo más rápido e idear "pases de optimización"?

No llegarás allí con la semántica formal IMO. He pensado recientemente sobre esto, y los siguientes son algunos pensamientos preliminares.

Mi impresión es que Knuth fue uno de los escritores de compiladores experimentados en la década de 1960 (es por eso que le pidieron que escribiera el libro de compiladores que se convirtió en El arte de la programación de computadoras ), y TeX está (en muchos sentidos) escrito de la misma manera que los compiladores. escrito en la década de 1970, por ejemplo. Las técnicas y el diseño del compilador han mejorado desde entonces, y también lo puede ser el programa TeX. Aquí hay algunas cosas que se pueden hacer para acelerar las cosas:

• En el fondo, TeX se escribe como una "rutina interpretativa", donde los "ojos" y "boca" (sus rutinas de entrada) de TeX entregan instrucciones a su "estómago" (sus rutinas semánticas), para que se ejecuten uno por uno. (Puede ver una lista en la parte 15 del programa TeX .) Por ejemplo, cuando los ojos / boca de TeX se encuentran \hfillo \hskipen su entrada, el estómago recibe un comando "hskip", en el que actúa. Esto es similar a lo que hoy se llaman intérpretes de bytecode, y puede ser valioso refactorizar el programa TeX para emitir estos bytecodes / opcodes explícitamente, de modo que podamos usar las técnicas de compilación existentes (más convencionales hoy en día). O al menos almacenarlos en caché para evitar rehacer el trabajo. Por supuesto, hay muchos desafíos:

  • La ejecución de un comando en el "estómago" generalmente implica leer la entrada, es decir, el trabajo de las rutinas de entrada y las rutinas semánticas no ocurren en fases separadas. Por ejemplo, el comando "hskip", si se proporciona \hskip(en lugar de decir \hfill), invocará scan_gluepara leer una especificación de cola de la entrada, que a su vez puede implicar la expansión de macros y así sucesivamente hasta que se encuentren suficientes tokens para la cola, dejando la pila de entrada en Estado sustancialmente diferente.

  • Los motores como eTeX y pdfTeX y XeTeX y LuaTeX introducen nuevos comandos y primitivas (las primitivas eTeX / pdfTex son prácticamente utilizadas por todos en la práctica); también deberá apoyarlos, no solo los del programa original de Knuth's TeX.

• Podríamos hacer algo como "ejecución especulativa", procesar párrafos futuros (tal vez comenzando en puntos de control naturales como nuevas secciones o capítulos) en paralelo (usando múltiples núcleos), haciendo un seguimiento de todo el estado interno de TeX que usan (depende) y lanzando lejos de ese trabajo (y rehaciéndolo) si más tarde descubrimos que un párrafo anterior termina cambiando algo de ese estado. Por el momento, TeX se ejecuta completamente secuencialmente en 1 procesador; El hardware típico se ha movido en una dirección diferente y hay múltiples núcleos disponibles.

• Aún más simple, podríamos simplemente almacenar en caché el trabajo (a qué estado de TeX se accedió y se modificó) en una determinada sección del archivo de entrada. (Podríamos hacer este almacenamiento en caché al nivel de la entrada, el resultado neto de expandir todas las macros, o al nivel de qué conjunto de cajas se ensamblaron, o hasta el estado total del programa). Por ejemplo, el contenido dentro una \begin{tikzpicture} … \end{tikzpicture}es poco probable que dependerá mucho de estado TeX como la página número del contador, así que cuando volvamos a compilar el documento TeX podemos simplemente volver a utilizar todo el trabajo - si hemos seguido la pista de la información suficiente para saber que es seguro hacerlo. (Por supuesto, TikZ en particular tiene formas de externalizar esto e incluir los resultados, pero la idea es más general).

• Podemos usar técnicas (p. Ej., Las que se usan en la programación funcional) para hacer un procesamiento de TeX con "agujeros"; por ejemplo, ahora, cuando escribe \ref{foo}en LaTeX para referirse a un número de sección (digamos futuro), solo funciona en dos pasos de compilación: primero se procesa todo el documento (todos los párrafos tipográficos, flotantes colocados en páginas, etc.) con los números de sección escritos en un archivo auxiliar, luego en una segunda pasada todosel trabajo se realiza nuevamente, con el número de sección realmente disponible esta vez. (Este tipo de pirateo puede haber sido inevitable en ese momento, y sé que el impacto en el tiempo de ejecución es "solo un factor constante", pero ...) En cambio, ¿qué pasaría si pudiéramos simplemente procesar el documento con un "agujero" ( queda un cuadro con contenido indeterminado pero con un ancho estimado) para el número de sección, luego, al final del procesamiento del documento, complete el cuadro. (Sí, nuestro ancho estimado puede resultar incorrecto y el párrafo puede necesitar reprocesamiento y, en consecuencia, incluso la página, pero podríamos hacer el trabajo si es necesario, o aceptar, para la velocidad, un modo en el que permitiremos un ancho incorrecto para el número de sección)

• Técnicas similares pueden funcionar para la edición interactiva de un documento TeX: cuando edita un párrafo, puede procesarse "en vivo", con futuros párrafos simplemente movidos hacia abajo de la cocina (digamos). Sabemos que es posible, ya que ya existen implementaciones (comerciales) de TeX que hacen esto, por ejemplo, BaKoMaTeX y Texpad y las texturas anteriores . (Vea el video en la página de inicio de BaKoMa-TeX y, de manera similar, el de TeXpad, por ejemplo, este video ; probé el último y, sin embargo, era insoportablemente defectuoso en la práctica).

• No debe subestimarse: el valor de mostrarle cosas al usuario, haciendo que TeX sea más depurable. En este momento, los usuarios solo ven su entrada de TeX y no tienen idea exactamente de qué trabajo está haciendo TeX, por ejemplo, cuánto tiempo pasa en el salto de línea para párrafos, o en la macroexpansión (y de qué macros), qué cajas está ensamblando y descartando, qué ofertas especiales están siendo escritas por qué paquete, etc. Creo (tal vez con optimismo) que existen usuarios a quienes les gustaría ver esta información y les sería útil, por ejemplo, saber si el paquete extraño que están usando para sombrear Las ecuaciones con un gradiente en el fondo son baratas (agregan poco al tiempo de procesamiento) o no. Al ver dónde se está haciendo un gran trabajo derrochador, podrían tirar parte de él (al menos hasta su última impresión). (Esto es algo así como los compiladores u otras herramientas que insertan información de perfiles en los programas). Hacer que TeX sea más transparente y depurable puede ser una gran mejora de usabilidad, por ejemplo. (TeX ya es bastante fácil de usar y depurar para su tiempo IMO si usamos principalmente TeX simple con muy pocas macros, pero no con LaTeX o cómo la mayoría de los usuarios lo encuentran hoy en día).

Además, cualquier trabajo futuro probablemente debería tener en cuenta (construir) LuaTeX, que es la mejor modificación de TeX que tenemos actualmente.

Todos estos son solo pensamientos ociosos (no he implementado ninguno de ellos, para saber el esfuerzo requerido o la velocidad que ganaríamos), pero espero que esto responda de alguna manera a responder su pregunta o darle ideas para futuras direcciones. .

No, que yo sepa, no ha habido trabajo para formalizar TeX del tipo que le interesa.

(Lo que sigue es un comentario subjetivo y personal). Creo que es una idea intrigante y bien planteada, y su motivación para usarla para realizar optimizaciones parece razonable: otra pregunta relacionada es si podría definir un formato de código de bytes para acelerar la interpretación. Por otro lado, la idea tiene dos desventajas.

Primero, no está claro para mí que haya un gran potencial para las optimizaciones (por ejemplo, ¿qué tipo de transformaciones de preservación de programas se podrían realizar para acelerar la computación?), Ya que puede ser que la semántica del lenguaje esté íntimamente relacionada con el análisis el flujo de caracteres y, por lo tanto, no se adapta mucho al diseño de representaciones intermedias optimizadas para la optimización.

En segundo lugar, la necesidad de mejoras en la velocidad de interpretación de TeX no está bien establecida: la velocidad de la construcción de la velocidad por lotes se ha mantenido razonable gracias a las mejoras de hardware. Los casos en los que las aceleraciones podrían ser bienvenidas son paquetes de gráficos complejos (las presentaciones de beamer pueden tardar bastante tiempo en construirse), paquetes que incorporan cálculos enriquecidos (pero luego otro idioma puede ser más apropiado) y casos de uso que requieren una reconstrucción rápida para comentarios instantáneos del usuario (pero luego el objetivo puede ser la incrementalidad, en lugar de la optimización; una semántica formal ciertamente también ayudaría a razonar sobre implementaciones incrementales).

Es decir: esto suena como un tema divertido e instructivo, pero no me queda claro que las justificaciones prácticas para hacer el trabajo sean sólidas. Si alguien estaba interesado en hacerlo por curiosidad, eso suena como una excelente aventura, pero de lo contrario puede haber otras formas de emplear el mismo conjunto de habilidades cuyo impacto sería más buscado por los usuarios finales.