Была ли когда-нибудь формализована семантика TeX (как языка программирования)?

Мне кажется, что макроязык, используемый может рассматриваться как некая система переписывания терминов или какой-то язык программирования с возможностью определения по имени.$\TeX$

Даже современные реализации двигатель (например, X e$\TeX$ ) интерпретировать код довольно прямым способом, и я не знаю ни одной попытки оптимизировать выполнение (как это могут сделать современные оптимизирующие интерпретаторы). Тем не менее, разработка правильной оптимизации проходит для такого языка, как$\mathit{Xe}\TeX$ будет очень трудным из-за «действия на расстоянии», которое могут иметь переопределения макросов, и возможности переопределения макросов, вызывая их по имени.$\TeX$

Таким образом, реализация гипотетического оптимизирующего интерпретатора для практике X звучит очень сложно, но также очень полезно, поскольку$\TeX$ используется во всей математике и науке, а медленные времена компиляции являются известным недостатком системы. Обратите внимание, что большую часть времени тратится на интерпретацию кода, а не на вычисление фактического набора текста, особенно когда используются вычислительно сложные пакеты (такие как).$\TeX$tikz

Возможно, формальная семантика для языка может стать началом решения проблемы. Так имеет семантику Язык программирования X когда-либо был формализован?$\TeX$

(С извинениями за длинный ответ, который идет в направлении, отличном от области сайта: честно говоря, я был удивлен, увидев этот вопрос в первую очередь….)

TeX был разработан для набора текста, а не для программирования; так что в лучшем случае это «странно», если рассматривать его как язык программирования.

- Дональд Кнут, Цифровая типография, страница 235

За последние пару лет я много читал о ранней истории (около 1977 года) TeX и о том, что написал Кнут. Я пришел к выводу, что в тот момент, когда мы говорим о «TeX (как языке программирования)» , что-то уже не так.

Если мы посмотрим на ранние «проектные документы» для TeX, написанные ранее (см. TEXDR.AFTИ TEX.ONEопубликованные в « Цифровой типографии» ), то станет ясно, что Кнут разрабатывал систему, в первую очередь предназначенную для набора текста «Искусство компьютерного программирования» (сказал он (например, здесь )). что основными пользователями, которые он имел в виду, были он и его секретарь), с идеей, что при соответствующей модификации это может быть полезно в более общем плане. Чтобы сохранить набор текста, для вещей, которые нужно было неоднократно делать (например, каждый раз, когда TAOCP требовалось включить цитату из автора, вы хотели бы перемещаться по вертикали на определенную величину, установить определенный линейный пропуск, подобрать определенный шрифт, набрать Выровняйте по правому краю, выберите другой шрифт, наберите имя автора…), были макросы.

Остальное можно угадать. То, что мы имеем в TeX, является случаем «случайно завершенного по Тьюрингу» ( подробнее ), за исключением того, что это произошло в среде сообщества (компьютерные ученые и математики, и сам DEK тоже «виноват»), которые были (к сожалению) слишком умный, чтобы игнорировать это. (Легенда гласит, что Майкл Спивак никогда не программировал до того, как столкнулся с TeX, но он был настолько увлечен этим, что закончил тем, что написал AMS-TeX, в то время один из самых сложных из существующих макросов.) Поскольку TeX был написан чтобы переноситься на большое количество систем (что в то время было большим делом), всегда был соблазн сделать все в TeX. Кроме того, из-за его опыта написания компиляторовКнут писал TeX, как компилятор, и иногда описывал его как один, и если программа, которая работает с вашим вводом, является «компилятором», то, конечно, вы программируете, верно?

В этом ответе вы можете прочитать немного больше о том, как Кнут не собирался заниматься программированием в TeX, и как он «включил многие функции программирования TeX только после того, как пнул и начал кричать» . Какими бы ни были его намерения, как я уже сказал, люди начали искать способы (ab) использовать макросистему TeX для достижения удивительных способностей программирования. Кнут нашел это увлекательное и (в дополнение к добавлению некоторых функций в сам TeX) включены некоторые из них в Приложении D «пакости» в The TeXbook, но оказывается , что, несмотря на название, что «девять из десяти примеров в них являются используется при реализации LaTeX ».

Позвольте мне сказать по-другому: LaTeX, макросистема, которую Лесли Лэмпорт написал поверх TeX, как идея , великолепна. Создание документов семантическим, структурированным, ориентированным на человека способом, а не ориентированным на страницы способом (Knuth) TeX (или, как назвал его Лэмпорт, логичным, а не визуальным ), является отличным решением. Но реализация чего-то столь же сложного, как LaTeX, с использованием макросов TeX, а не на «правильном» языке программирования, на мой взгляд и, по крайней мере, если бы это было сделано сегодня, где-то между гигантской ошибкой и актом бессмысленного извращения. Даже Кнут шокирован тем, что люди не просто расширяют программу TeX, а не делают все в макросах TeX.

Сегодня есть намного лучшие способы сделать «программирование»; вы можете использовать внешнюю программу на любом из многих языков, широко доступных на компьютерах большинства людей, или вы можете использовать LuaTeX и программу на Lua (и выполнять работу лучше, чем когда-либо, используя только макросы TeX, поскольку вы можете манипулировать внутренними структурами и алгоритмы на нужном уровне). И если вы все сделаете правильно, у вас могут быть программы, которые работают лучше или быстрее, чем реализованные в макросах TeX.

Задача ускорения работы программ в TeX выглядит довольно забавно, если смотреть в этом свете, и напоминает мне о последних словах статьи, описывающих другой «случайно завершенный по Тьюрингу» «язык программирования»: прекрасный том Тома Уилденхейна « О полноте Тьюринга» PowerPoint ( видео ) с прошлого года:

В то время как PPTXTM доказывает теоретическую возможность разработки PowerPoint, […]. Также необходимо выполнить работу по оптимизации приложений PowerPoint. Здесь есть большой потенциал для использования автоматической буферизации PowerPoint для следующего слайда, которая может быть использована для тщательного размещения слайдов для значительного повышения производительности приложений.

Анекдот , который описывает Липтон является иллюстративным. Не только никогда не существовало формальной семантики TeX, но и вряд ли таковой будет. Это слишком «странный» «язык» для этого, и (как я надеюсь, я объяснил выше) он даже не предназначен для языка. Например, вы можете подумать, что вы пишете макросы как функции, но вводите в них один случайный символ (даже пробел ), и TeX немедленно воспринимает его как инструкцию для набора текста.

Короче говоря, TeX возвращается к верстке при первой же возможности, и когда он расширяет макросы, он делает это неохотно (не терпится приступить к своей «реальной» работе по верстке), и эти расширения сами могут зависеть от сотен видов «состояний» внутри программа TeX (значения параметров, такие как \hsizeили \baselineskip, содержимое блоков и других регистров…), поэтому любая формальная семантика TeX обязательно должна быть чем-то, что учитывает все состояние программы и всю ее память, пока мы в итоге получится что-то вроде «смысл кода TeX - это то, что делает TeX», в форме, более сложной, чем сама программа TeX.

Так хорошо, (если я вас убедил) TeX не был задуман как язык программирования и не работает как настоящий, формальной семантики нет, и сегодня есть лучшие способы программирования - но все это не помогает с вашим Фактический вопрос / проблема заключается в том, что на практике многие документы, предназначенные для обработки TeX , используют сложные макросы (такие как LaTeX и TikZ), потрясающие здания чудовищной сложности, построенные друг на друге. Как мы можем сделать это быстрее и разработать «проходы оптимизации»?

Вы не попадете туда с формальной семантикой IMO. Я недавно думал об этом, и вот некоторые предварительные мысли.

У меня сложилось впечатление, что Кнут был одним из опытных авторов компиляторов в 1960-х годах (поэтому его попросили написать книгу по компиляторам, которая превратилась в Искусство компьютерного программирования ), а TeX (во многих отношениях) написан так, как это делали компиляторы. написано в 1970-х, скажем. Техника и дизайн компиляторов с тех пор улучшились, как и программа TeX. Вот несколько вещей, которые можно сделать, чтобы ускорить процесс:

• В сущности, TeX написан как «интерпретирующая подпрограмма», где «глаза» и «рот» (его подпрограммы ввода) TeX доставляют инструкции в «живот» (его семантические подпрограммы), которые выполняются одна за другой. (Вы можете увидеть список в части 15 программы TeX .) Например, когда TeX сталкивается с глазами / ртом \hfillили \hskipпри вводе, желудок получает команду «hskip», на которую он воздействует. Это похоже на то, что сегодня называют интерпретаторами байт-кода, и может быть целесообразным рефакторинг программы TeX для явной передачи этих байт-кодов / кодов операций, чтобы мы могли использовать существующие (более традиционные сегодня) методы компиляции. Или, по крайней мере, кешировать их, чтобы избежать повторной работы. Есть конечно много проблем:

  • Выполнение команды в «желудке» обычно все еще включает чтение ввода, то есть работа входных подпрограмм и семантических подпрограмм не происходит в отдельных фазах. Например, команда «hskip», если она задана \hskip(а не, скажем \hfill), будет вызывать scan_glueчтение спецификации клея из входных данных, что, в свою очередь, может включать расширение макросов и т. Д., Пока не будет найдено достаточно токенов для клея, оставляя входной стек в существенно другое состояние.

  • Такие движки, как eTeX и pdfTeX, XeTeX и LuaTeX, представляют новые команды и примитивы (примитивы eTeX / pdfTex практически используются всеми на практике); вам также нужно будет поддерживать их, а не только те, которые содержатся в оригинальной программе Knuth TeX.

• Мы могли бы сделать что-то вроде «спекулятивного выполнения», обрабатывая будущие абзацы (возможно, начиная с естественных контрольных точек, таких как новые секции или главы) параллельно (используя несколько ядер), отслеживая все внутреннее состояние TeX, которое они используют (зависят от), и выбрасывая уберите эту работу (и переделайте ее), если позже мы узнаем, что предыдущий параграф заканчивает тем, что изменяет часть этого состояния. На данный момент TeX работает полностью последовательно на 1 процессоре; типичное оборудование перемещается в другом направлении и доступно несколько ядер.

• Еще проще, мы могли бы просто кэшировать работу (к какому состоянию TeX обращались и изменяли) с помощью определенного раздела входного файла. (Мы могли бы сделать это кэширование на уровне ввода - итоговый результат расширения всех макросов - или на уровне того, какой набор блоков был собран, или вплоть до полного состояния программы.) Например, содержимое внутри \begin{tikzpicture} … \end{tikzpicture}вряд ли во многом зависят от TeX состояния , как номер страницы счетчика, поэтому , когда мы перекомпилировать документ TeX мы можем просто повторно использовать всю работу - если мы отслеживали достаточно информации , чтобы знать , что это безопасно. (Конечно, у TikZ, в частности, есть способы вывести это из себя и включить результаты, но идея более общая.)

• Мы можем использовать методы (например, те, которые используются в функциональном программировании), чтобы выполнить некоторую обработку TeX с «дырами» - например, прямо сейчас, когда вы пишете \ref{foo}в LaTeX для ссылки на (скажем, в будущем) номер раздела, он работает только в два этапа компиляции: сначала обрабатывается весь документ (наборы всех абзацев, расположение на страницах и т. д.), а номера разделов записываются во вспомогательный файл, затем на втором проходе всеработа сделана снова, на этот раз номер секции действительно доступен. (Этот вид взлома мог быть неизбежным в то время, и я знаю, что влияние на время выполнения - «только постоянный фактор», но ...) Вместо этого, что если бы мы могли просто обработать документ с «дырой» ( поле с неопределенным содержимым, но с приблизительной шириной), оставленное для номера раздела, затем в конце обработки документа заполните поле? (Да, наша расчетная ширина может оказаться неправильной, и абзацу может потребоваться повторная обработка и, следовательно, даже страница, но мы могли бы либо выполнить работу, если это необходимо, либо принять для скорости режим, в котором мы допустим неправильную ширину для номер раздела.)

• Подобные методы могут работать для интерактивного редактирования документа TeX: когда вы редактируете абзац, он может обрабатываться «вживую», а будущие абзацы просто перемещаются по камбузу (скажем). Мы знаем, что это возможно, поскольку уже существуют (коммерческие) реализации TeX, которые делают это, например, BaKoMaTeX и Texpad и прежние текстуры . (Смотрите видео на домашней странице BaKoMa-TeX и аналогичных TeXpad, например, это видео - я попробовал последнее, хотя на практике это было невыносимо глючно.)

• Не стоит недооценивать: ценность показа вещей пользователю, делающая TeX более отлаживаемой. Прямо сейчас пользователи видят только свой ввод TeX и не знают точно, что делает TeX, например, сколько времени он тратит на разрыв строк для абзацев или на макроразложение (и из каких макросов), какие блоки он собирает и выбрасывая, какие специальные предложения пишутся каким пакетом и т. д. Я (возможно, оптимистично) считаю, что существуют пользователи, которые хотели бы видеть эту информацию и считают ее полезной, например, чтобы узнать, используются ли странные пакеты, которые они используют для затенения Уравнения с градиентом на заднем плане дешевы (мало добавляют времени обработки) или нет. Видя, где выполняется много расточительной работы, они могут выбросить часть ее (по крайней мере, до окончательного тиража). (Это похоже на компиляторы или другие инструменты, вставляющие информацию о профилировании в программы.) Например, повышение прозрачности и отладки TeX может стать огромным улучшением юзабилити. (TeX уже довольно удобен и отлаживаем для своего времени IMO, если мы используем в основном обычный TeX с очень небольшим количеством макросов, но не с LaTeX или с тем, как большинство пользователей сталкиваются с ним сегодня.)

Кроме того, любая будущая работа, вероятно, должна учитывать (основываться) на LuaTeX, который является лучшей модификацией TeX, которую мы имеем в настоящее время.

Все это просто бесполезные мысли (я не реализовал ни одной из них, чтобы знать, какое усилие требуется, или как много ускорения мы получим), но я надеюсь, что это каким-то образом ответит на ваш вопрос или даст вам идеи для будущих направлений. ,

Нет, насколько мне известно, не было работы по формализации TeX того вида, который вас интересует.

(Далее следует субъективный и личный комментарий). Я думаю, что это интригующая и правильно сформулированная идея, и ваша мотивация использовать ее для выполнения оптимизаций звучит разумно - еще один связанный с этим вопрос - можете ли вы определить для нее формат байт-кода, чтобы ускорить интерпретацию. С другой стороны, у этой идеи есть два недостатка.

Во-первых, мне не ясно, что существует большой потенциал для оптимизации (например, какой вид программно-сохраняющих преобразований можно выполнить для ускорения вычислений?), Так как может оказаться, что семантика языка тесно связана с синтаксическим анализом поток символов, и, следовательно, не очень вписывается в дизайн удобных для оптимизации промежуточных представлений.

Во-вторых, необходимость улучшения скорости интерпретации TeX не является обоснованной: скорость наращивания пакетной скорости остается разумной благодаря аппаратным улучшениям. Случаи, когда ускорения могут приветствоваться, представляют собой сложный графический пакет (для создания презентаций на beamer может потребоваться довольно много времени), пакеты, в которых используются расширенные вычисления (но тогда может оказаться более подходящим другой язык), и случаи использования, требующие быстрой перестройки для мгновенной обратной связи с пользователем (но затем в этом может быть смысл, а не оптимизация, а формальная семантика, конечно же, поможет рассуждать и о дополнительных реализациях).

То есть это звучит как забавная, поучительная тема, но мне не ясно, насколько сильны практические основания для выполнения работы. Если кто-то заинтересован сделать это из любопытства, это звучит как отличное приключение, но в противном случае могут быть другие способы использовать тот же набор навыков, воздействие которого будет более востребованным конечными пользователями.