A semântica do TeX (como linguagem de programação) já foi formalizada?

Parece-me que a linguagem macro empregada por Talvez o X possa ser visto como algum tipo de sistema de reescrita de termos ou algum tipo de linguagem de programação com escopo de chamada por nome.$\TeX$

Mesmo implementações modernas do Motor X (por exemplo, X e$\TeX$ ) interprete o código de maneira bastante direta e não conheço nenhuma tentativa de otimizar a execução (como os intérpretes de otimização modernos podem fazer). No entanto, planejar a otimização correta passa para um idioma como$\mathit{Xe}\TeX$ será muito difícil devido à "ação à distância" que as redefinições de macro podem ter e à capacidade de redefinir macros chamando-as pelo nome.$\TeX$

Então, implementando um intérprete de otimização hipotético para parece um problema muito difícil na prática, mas também muito útil, pois oé usado em toda matemática e ciências e os tempos de compilação lentos são uma desvantagem conhecida do sistema. Observe que a maior parte do tempo é gasta na interpretação do código, não computando a composição tipográfica real, especialmente quando são usados ​​pacotes computacionalmente pesados ​​(como).$\TeX$$\TeX$tikz

Talvez uma semântica formal para o idioma possa ser um começo para resolver o problema. Então, a semântica da linguagem de programação já foi formalizada?$\TeX$

(Pedimos desculpas por uma resposta longa que segue uma direção diferente do escopo do site: francamente, fiquei surpreso ao ver a pergunta aqui em primeiro lugar….)

O TeX foi projetado para composição tipográfica, não para programação; então é, na melhor das hipóteses, "estranho" quando considerado como uma linguagem de programação.

- Donald Knuth, Tipografia digital, página 235

Eu li muito nos últimos anos sobre o início da história (por volta de 1977) do TeX, e muito do que Knuth escreveu. Minha conclusão é que, no momento em que falamos sobre "TeX (como linguagem de programação)" , algo já está errado.

Se observarmos os primeiros "documentos de design" para o TeX escritos anteriormente (veja TEXDR.AFTe TEX.ONE, publicado na Digital Typography ), fica claro que Knuth estava projetando um sistema destinado principalmente à tipografia de The Art of Computer Programming (ele disse (por exemplo, aqui ) que os principais usuários que ele tinha em mente eram ele e sua secretária), com a idéia de que, adequadamente modificada, pode ser útil de maneira mais geral. Para salvar a digitação, o que é preciso fazer repetidamente (por exemplo, toda vez que o TAOCP precisar incluir uma citação de um autor, você deverá mover-se verticalmente em uma certa quantidade, definir um certo salto de linha, escolher uma certa fonte, digitar o tipo de letra). aspas alinhadas à direita, escolha outra fonte, digite o nome do autor…), havia macros.

Você pode adivinhar o resto. O que temos no TeX é um caso de "acidentalmente completo de Turing" ( mais ), exceto que aconteceu no meio de uma comunidade (cientistas da computação e matemáticos, e o próprio DEK também deve "culpar") quem foi (infelizmente) inteligente demais para ignorar isso. (Diz a lenda que Michael Spivak nunca havia programado antes de encontrar o TeX, mas ficou tão empolgado que acabou escrevendo o AMS-TeX, na época um dos conjuntos mais complicados de macros existentes.) Como o TeX foi escrito para ser portátil em um grande número de sistemas (o que era muito importante na época), sempre havia a tentação de fazer tudo no TeX. Além disso, por causa de sua experiência em escrever compiladores, Knuth escreveu o TeX como um compilador e, ocasionalmente, o descreveu como um, e se o programa que funciona com a sua entrada é um "compilador", então certamente você está programando, certo?

Você pode ler um pouco mais sobre como Knuth não pretendia fazer nenhuma programação no TeX e como ele "inseriu muitos dos recursos de programação do TeX somente depois de chutar e gritar", nesta resposta . Quaisquer que fossem suas intenções, como eu disse, as pessoas começaram a descobrir maneiras de (ab) usar o sistema de macro TeX para realizar proezas surpreendentes de programação. Knuth encontrado este fascinante e (além de adicionar algumas características em si TeX) incluiu algumas delas no Apêndice D “truques sujos” de O Livro Didático, mas acontece que, apesar do nome, que “nove dos exemplos dez nele são usado na implementação do LaTeX ”.

Deixe-me colocar de outra maneira: o LaTeX, o sistema de macro que Leslie Lamport escreveu sobre o TeX, como uma idéia , é excelente. Criar documentos de maneira semântica, estruturada e orientada para humanos, em vez da orientada por página do TeX (Knuth), (ou como Lamport o chamou, lógico e não visual ) é excelente. Mas implementar algo tão complicado quanto o LaTeX usando macros TeX em vez de em uma linguagem de programação "adequada" é, na minha opinião e pelo menos se fosse feito hoje, algo entre um erro gigante e um ato de perversidade desonesta. Até Knuth fica chocado que as pessoas não estendam apenas o programa TeX em vez de fazer tudo nas macros TeX.

Hoje existem maneiras muito melhores de fazer “programação”; você pode usar um programa externo em qualquer um dos muitos idiomas amplamente disponíveis nos computadores da maioria das pessoas ou pode usar o LuaTeX e o programa no Lua (e fazer um trabalho melhor do que nunca com as macros do TeX, porque você pode manipular estruturas internas e algoritmos no nível certo). E, se você fizer o que é certo, poderá ter programas que funcionam melhor ou mais rapidamente do que os implementados nas macros do TeX.

A tarefa de tornar os programas no TeX mais rápidos é quase divertida quando vista sob esse aspecto e me lembra as palavras finais do artigo que descreve outra linguagem de programação “acidentalmente Turing complete”: a adorável “ On the Turing Completeness of MS ” de Tom Wildenhain PowerPoint ( vídeo ) do ano passado:

Enquanto o PPTXTM prova a possibilidade teórica do desenvolvimento do PowerPoint, […]. O trabalho também precisa ser feito na otimização de aplicativos do PowerPoint. Há muito potencial aqui para explorar o buffer automático do PowerPoint do próximo slide, o qual, por meio de um posicionamento cuidadoso do slide, pode ser usado para aumentar bastante o desempenho do aplicativo.

A anedota que Lipton descreve é ilustrativa. Não apenas nunca existiu uma semântica formal do TeX, como também é improvável que exista uma. É uma linguagem muito "esquisita" para isso e (como espero ter explicado acima) nem sequer é uma linguagem. Por exemplo, você pode pensar que está escrevendo macros como funções, mas introduz um único caractere disperso (até mesmo um espaço ), e o TeX o trata imediatamente como uma instrução de digitação.

Resumindo: o TeX volta à composição tipográfica na primeira oportunidade e, quando expande as macros, o faz de má vontade (impaciente em chegar ao seu trabalho "real" de tipografia), e essas expansões podem depender de centenas de tipos de "estados" dentro o programa TeX (os valores de parâmetros como \hsizeou \baselineskip, o conteúdo de caixas e outros registros ...), e é por isso que qualquer semântica formal do TeX deve necessariamente ser algo que leve em consideração todo o estado do programa e toda a sua memória, até que acabamos com algo como “o significado do código TeX é o que quer que o TeX faça”, de uma forma mais complexa que o próprio programa TeX.

Tão bom (se eu o convenci) que o TeX não era uma linguagem de programação e não funciona como a real, não há semântica formal e existem maneiras melhores de programar hoje - mas tudo isso não ajuda no seu questão real / problema, que é que, na prática, muitos documentos voltados para o processamento por TeX fazer uso complicado macros (como LaTeX e TikZ), edifícios impressionantes de complexidade monstruosa construída em cima uns dos outros. Como podemos torná-lo mais rápido e criar "passes de otimização"?

Você não chegará lá com semântica formal IMO. Eu pensei recentemente sobre isso, e a seguir estão alguns pensamentos preliminares.

Minha impressão é que Knuth foi um dos escritores de compiladores experientes na década de 1960 (foi por isso que ele foi convidado a escrever o livro de compiladores que se transformou em The Art of Computer Programming ), e o TeX (de várias maneiras) escreveu da maneira que os compiladores eram. escrito na década de 1970, digamos. As técnicas e o design do compilador melhoraram desde então, e o programa TeX também pode ser. Aqui estão algumas coisas que podem ser feitas, acelerando as coisas:

• No fundo, o TeX é escrito como uma "rotina interpretativa", onde os "olhos" e "boca" do TeX (suas rotinas de entrada) entregam instruções ao seu "estômago" (suas rotinas semânticas), para serem executadas uma a uma. (Você pode ver uma lista na parte 15 do programa TeX .) Por exemplo, quando os olhos / boca do TeX se encontram \hfillou \hskipem sua entrada, o estômago recebe um comando "hskip", no qual ele atua. Isso é semelhante ao que é chamado de intérpretes de bytecode hoje, e pode haver valor em refatorar o programa TeX para emitir esses bytecodes / opcodes explicitamente, para que possamos usar técnicas de compilador existentes (hoje mais convencionais hoje). Ou pelo menos armazená-las em cache para evitar refazer o trabalho. Obviamente, existem muitos desafios:

  • A execução de um comando no “estômago” geralmente ainda envolve a leitura da entrada, ou seja, o trabalho das rotinas de entrada e rotinas semânticas não ocorre em fases separadas. Por exemplo, o comando "hskip", se fornecido \hskip(em vez de dizer \hfill), invocará scan_gluea leitura de uma especificação de cola da entrada, o que, por sua vez, pode envolver a expansão de macros etc. até que sejam encontrados tokens suficientes para a cola, deixando a pilha de entrada em um estado substancialmente diferente.

  • Motores como eTeX e pdfTeX e XeTeX e LuaTeX introduzem novos comandos e primitivas (as primitivas eTeX / pdfTex são praticamente usadas por todos na prática); você precisará apoiá-los também, não apenas aqueles do programa TeX original do Knuth.

• Poderíamos fazer algo como “execução especulativa”, processando parágrafos futuros (talvez começando em pontos de verificação naturais como novas seções ou capítulos) em paralelo (usando múltiplos núcleos), acompanhando todo o estado interno do TeX que eles usam (dependem) e jogando afastar esse trabalho (e refazê-lo) se depois descobrirmos que um parágrafo anterior acaba alterando parte desse estado. No momento, o TeX é executado inteiramente sequencialmente em 1 processador; o hardware típico mudou-se em uma direção diferente e vários núcleos estão disponíveis.

• Ainda mais simples, poderíamos simplesmente armazenar em cache o trabalho (qual estado do TeX foi acessado e modificado) por uma determinada seção do arquivo de entrada. (Podemos fazer isso em cache no nível da entrada - o resultado líquido da expansão de todas as macros - ou no nível de qual conjunto de caixas foram montadas ou até o estado total do programa.) Por exemplo, o conteúdo interno um \begin{tikzpicture} … \end{tikzpicture}é improvável que dependem muito de estado TeX como o número de page counter, então quando nós recompilar o documento TeX podemos simplesmente reutilizar todo o trabalho - se ter mantido a par da informação suficiente para saber que é seguro fazê-lo. (É claro que o TikZ em particular tem maneiras de externalizar isso e incluir os resultados, mas a ideia é mais geral.)

• Podemos usar técnicas (por exemplo, aquelas usadas na programação funcional) para fazer algum processamento TeX com “buracos” - por exemplo, agora, quando você escreve \ref{foo}no LaTeX para se referir a um número de seção (digamos futuro), ele funciona apenas em dois passes de compilação: primeiro todo o documento é processado (todos parágrafos tipografia, flutuadores posicionados em páginas, etc) com os números de secção a ser escrito para um ficheiro auxiliar, em seguida, numa segunda passagem todoso trabalho é feito novamente, com o número da seção realmente disponível neste momento. (Esse tipo de invasão pode ter sido inevitável na época, e eu sei que o impacto no tempo de execução é "apenas um fator constante", mas ...). Em vez disso, e se pudéssemos simplesmente processar o documento com um "buraco" ( uma caixa com conteúdo indeterminado, mas com alguma largura estimada) deixada para o número da seção e, no final do processamento do documento, preencher a caixa? (Sim, nossa largura estimada pode dar errado e o parágrafo pode precisar de reprocessamento e, consequentemente, até a página, mas poderíamos fazer o trabalho se necessário, ou aceitar, por velocidade, um modo no qual permitiremos uma largura errada para o número da seção.)

• Técnicas semelhantes podem funcionar para a edição interativa de um documento TeX: quando você edita um parágrafo, ele pode ser processado “ao vivo”, com parágrafos futuros simplesmente movendo-se pela cozinha (digamos). Sabemos que é possível, pois já existem implementações TeX (comerciais) que fazem isso, por exemplo, BaKoMaTeX e Texpad e as antigas Textures . (Veja o vídeo na página inicial do BaKoMa-TeX e similarmente do TeXpad, por exemplo, este vídeo - eu tentei o último e era insuportavelmente buggy na prática.)

• Não deve ser subestimado: o valor de mostrar as coisas ao usuário, tornando o TeX mais debugável. No momento, os usuários veem apenas sua entrada TeX e não têm idéia exatamente do que o trabalho está fazendo, por exemplo, quanto tempo gasta na quebra de linhas de parágrafos ou na macroexpansão (e de quais macros), quais caixas ele está montando e jogando fora, quais promoções estão sendo escritas por qual pacote, etc. Eu (talvez otimista) acredito que existem usuários que gostariam de ver essas informações e que seriam úteis, por exemplo, saber se o pacote estranho que eles estão usando para sombreamento equações com um gradiente em segundo plano são baratas (adicionando pouco ao tempo de processamento) ou não. Ao ver onde um monte de trabalho desnecessário está sendo realizado, eles podem jogar fora um pouco dele (pelo menos até a impressão final). (Isso é parecido com compiladores ou outras ferramentas que inserem informações de criação de perfil em programas.) Tornar o TeX mais transparente e depurável pode ser uma enorme melhoria de usabilidade, por exemplo. (O TeX já é bastante fácil de usar e depurável para a IMO do tempo, se usarmos o TeX comum com poucas macros, mas não com o LaTeX ou como a maioria dos usuários o encontra hoje.)

Além disso, qualquer trabalho futuro provavelmente deve levar em consideração o LuaTeX, que é a melhor modificação do TeX que temos atualmente.

Todos esses são apenas pensamentos ociosos (não implementei nenhum deles, para saber o esforço necessário ou quanto ganho acelerávamos), mas espero que isso ajude a responder à sua pergunta ou lhe dar idéias para futuras direções. .

Não, que eu saiba, não houve nenhum trabalho para formalizar o TeX do tipo em que você está interessado.

(O que segue é um comentário subjetivo e pessoal). Eu acho que é uma ideia interessante e bem colocada, e sua motivação para usá-la para realizar otimizações parece razoável - outra questão relacionada é se você pode definir um formato de bytecode para acelerar a interpretação. Por outro lado, a ideia tem duas desvantagens.

Primeiro, não está claro para mim que há um grande potencial de otimizações (por exemplo, que tipo de transformação de preservação de programa poderia ser realizada para acelerar a computação?), Pois pode ser que a semântica da linguagem esteja intimamente relacionada à análise o fluxo de caracteres e, portanto, pouco adaptável ao design de representações intermediárias favoráveis ​​à otimização.

Segundo, a necessidade de melhorias na velocidade de interpretação do TeX não está bem estabelecida: a velocidade de construção da velocidade do lote permaneceu razoável graças a melhorias no hardware. Os casos em que as acelerações podem ser bem-vindas são pacotes gráficos complexos (as apresentações beamer podem demorar um pouco para serem construídas), pacotes incorporando cálculos avançados (mas outro idioma pode ser mais apropriado) e casos de uso que exigem reconstrução rápida para feedback instantâneo do usuário (mas, em seguida, incrementalidade, em vez de otimização, pode ser o ponto; uma semântica formal certamente ajudaria a raciocinar sobre implementações incrementais).

Ou seja: isso soa como um tópico divertido e instrutivo, mas não está claro para mim que as justificativas práticas para fazer o trabalho são fortes. Se alguém estava interessado em fazer isso por curiosidade, isso soa como uma excelente aventura, mas, caso contrário, pode haver outras maneiras de empregar o mesmo conjunto de habilidades cujo impacto seria mais procurado pelos usuários finais.