PLComp

Эта небольшая заметка посвящена нескольким новостям по нашей тематике. Во-первых, хочу напомнить, что в июне прошла конференция PLDI 2022 и многие из представленных там работ имеют компиляторную тематику. Вот программа конференции: https://pldi22.sigplan.org/program/program-pldi-2022/ Во-вторых, давайте поговорим о весьма достойных книгах, которые официально только готовятся к печати и выйдут в 2022-2023 гг. Нас ждет третье издание классики Engineering a Compiler. Второе издание вышло в 2012 году и мне, увы, пока не удалось установить, в чем же особенности нового издания. Судя по всему, новая версия знаменитого учебника выйдет в этом сентябре: https://www.amazon.com/Engineering-Compiler-Keith-D-Cooper/dp/0128154128 В феврале 2023 года выйдет Essentials of Compilation в издательстве MIT: https://mitpress.mit.edu/books/essentials-compilation Материал в разных редакциях давно уже публиковался на github: https://github.com/IUCompilerCourse/Essentials-of-Compilation Еще одна довольно известная онлайн-книга скоро будет напечатана. Речь об SSA Book. Официально она теперь называется SSA-based Compiler Design: https://link.springer.com/book/9783030805142 Ждем ее ближе к февралю 2023 года. Наконец, упомяну о настоящем "долгострое": новой версии классики Programming Languages: An Interpreter-Based Approach" от Samuel Kamin. Новый автор и известный компьютерный ученый, Norman Ramsey, работал над своей версией еще, кажется, с 2005 года. На протяжении многих лет черновые варианты учебника адресно рассылались отдельным профессорам в разных университетах. И, вот, наконец, в этом октябре книга под официальным названием Programming Languages Build, Prove, and Compare будет напечатана: https://www.cambridge.org/ru/academic/subjects/computer-science/programming-languages-and-applied-logic/programming-languages-build-prove-and-compare

Первая часть цикла докладов об автоматизации программирования в СССР доступна на youtube. Цель — напомнить о хорошо забытых идеях и алгоритмах, не вдаваясь в подробности биографий их авторов и детали устройства вычислительных машин. Цикл состоит из четырех частей: 1. Программирующие программы (50-е годы). 2. Трансляторы (60-70-е годы). 3. Метавычисления. 4. Синтез программ. Кстати, идея доклада возникла случайно. Для планируемой к изданию энциклопедии «Истории отечественного программирования» нужны были статьи. Ко мне обратились поздно и я написал обзорную заметку, текстом которой был не очень доволен. Увы, проект энциклопедии так, похоже, и не состоялся. Но ссылки интернет хранит: https://rcc.msu.ru/ru/enciklopediya-istoriya-otechestvennogo-programmirovaniya К счастью, материал не пропал, а был серьезно развит и переработан для выступления на C++ Russia (спасибо Тимуру Сафину за приглашение выступить!). https://youtube.com/watch?v=0bTdplAlGYg P.S. На днях на C++ Russia состоится несколько компиляторных докладов с уклоном в LLVM. Я для себя выделил этот доклад: https://cppconf.ru/talks/595fef990d9342c1b34179bff9c057ab/

https://arxiv.org/pdf/1810.07951.pdf Don't Unroll Adjoint: Differentiating SSA-form Programs Michael J Innes, 2019 https://proceedings.neurips.cc/paper/2020/file/9332c513ef44b682e9347822c2e457ac-Paper.pdf Instead of Rewriting Foreign Code for Machine Learning, Automatically Synthesize Fast Gradients William S. Moses and Valentin Churavy, NeurIPS 2020 Обе статьи посвящены (обратному aka reverse-mode) автоматическому (или алгоритмическому) дифференцированию функций, представленных в форме Single Static Assignment aka SSA. И тем не менее, они описывают существенно различные подходы. Первая статья даёт краткое введение в обратное дифференцирование и распространённый подход на основе Wengert Lists. Чтобы перейти к SSA форме, к Wengert Lists необходимо добавить метки, условные и безусловные переходы и фи-узлы (φ nodes). Соответственно, статья вводит правила дифференцирования этих управляющих конструкций (control flow constructs). Дополнительно вводятся правила дифференцирования для чтения и записи в ячейки памяти, поскольку основной прицел статьи — императивные языки (и Julia в особенности). Забавно, что на практике (на текущий момент) основанная на описанном подходе библиотека Zygote не поддерживает деструктивную модификацию массивов, несмотря на её (библиотеки) широкое использование, в особенности во фреймворке для машинного обучения Flux. 😊 Несмотря на использование SSA-формы, первая статья подразумевает сравнительно высокоуровневое представление, близкое к исходному языку, до проведения оптимизаций. Вторая же статья рассматривает внедрение автоматического дифференцирования непосредственно в фреймворк LLVM в виде одного из проходов компиляции, выполняемого над низкоуровневым SSA-представлением, не зависящим от исходного языка и прошедшего ряд оптимизаций. Поэтому основное внимание она уделяет низкоуровневым аспектам: теневой памяти (shadow memory), кешам, обработке указателей, в том числе — вызовам функций по указателю, и переиспользованию информации с других проходов, таких как type-based alias analysis. Стремление проводить автоматическое дифференцирование настолько низкоуровневого представления продиктовано двумя соображениями. Во-первых, немедленная применимость к большому количеству промышленных языков — C, C++, Rust, Julia — без каких-либо изменений в самом языке. Во-вторых, оптимизация исходного кода может сильно упростить и ускорить порождаемый код расчёта градиента функции, в некоторых случаях — понизить сложность с квадратичной до линейной после применения loop-invariant code motion к исходному коду. Для подтверждения ускорения, авторы провели замеры производительности и сравнения с традиционными подходами на задачах ADBench от Microsoft и нескольких сторонних реализациях численного решателя дифференциальных уравнений. Результаты и графики приведены в статье. 😊 В любом случае, обе работы полагаются на "классические компиляторные техники", такие как dataflow analysis, alias analysis, abstract interpretation, и оптимизации. И потому представляют собой интереснейшее расширение "поля деятельности компиляторщиков" в сравнительно новую, но стремительно набирающую популярность, область.

https://arxiv.org/abs/2001.10490 Beyond Notations: Hygienic Macro Expansion for Theorem Proving Languages Sebastian Ullrich, Leonardo de Moura Большинство систем интерактивного доказательства теорем разрабатываются с прицелом на формализацию математики. Включая возможность использования специфической математической нотации, разработанной для некоторой теории. Такой как 𝛴, 𝛱 или ∫, которые используются не только в математическом анализе, но и в теории категорий, например. Характерная особенность приведённых обозначений, как и многих других — "захват переменных" аналогично тому, как переменные захватываются кванторами в логике и лямбда-абстракцией в лямбда-исчислении. При этом, поскольку системы интерактивного доказательства строятся поверх того или иного варианта лямбда-исчисления, математическую нотацию придётся выражать именно через лямбды, и как-то с ними взаимодействовать. В этот момент возникает вопрос "гигиены": мы не хотим, чтобы переменные перепутались и были связаны с неправильной лямбда-абстракцией, ообенно "невидимой" лямбдой, которая была автоматически сгенерирована в процессе трансляции другой нотации. Вопрос дополнительно осложняется естественным "инженерным" требованием: поскольку многие обозначения используют одинаковый синтаксис связывания переменных, мы хотели бы описать этот синтаксис и его семантику один раз, и просто переиспользовать во всех подходящих случаях. Примерами переиспользования синтаксиса связывания переменных могут служить те же нотации для сумм и произведений: 𝛴 и 𝛱. Статья демонстрирует как можно решить эту задачу при помощи типизированной системы макросов и несложного алгоритма, обеспечивающего гигиену. Само собой, за простоту приходится чем-то заплатить. В данном случае — ограниченной применимостью, поскольку алгоритм полагается на определённые свойства языка программирования. Наиболее существенное из них: выполнение программы осуществляется "построчно", по одному выражению верхнего уровня за раз, в порядке их записи в файле. Новую нотацию (на самом деле, любой макрос) могут использовать только выражения, записанные ниже определения макроса. И некоторые другие упрощающие предположения. Такое поведение часто встречается в системах интерактивного доказательства теорем, но сильно ограничивает применимость в языках программирования общего назначения. Для таких языков придётся пользоваться намного более сложным алгоритмом гигиены, как, например, в Racket. Кроме того, в статье рассматриваются вопросы интеграции макро-системы и систем "уточнения" (elaboration) и type-driven expansion, плюс реализация тактик в виде гигиенических макросов, чего до сих пор не встречалось в системах интерактивных доказательств. В итоге, несмотря на очевидную направленность на системы интерактивного доказательства, статья является отличным введением в проблематику, связанную с макросами, обеспечением гигиены, типизацией макросов, декларативным и императивным заданием макросов. Рекомендую всем читателям, ещё не знакомым, но интересующимся вопросами создания макро-систем в языках программирования. #macros #lean #elaboration #proofassistants

На днях, и даже в одно и то же время, прошли два ежегодных российских мероприятия, в том числе и на темы языков и компиляторов. Это -- Национальный Суперкомпьютерный Форум (НСКФ) и Открытая конференция ИСП РАН. По НСКФ доступны тезисы докладов: https://2021.nscf.ru/nauchno-prakticheskaya-konferenciya/tezisy-dokladov/ В телеграм-канале Открытой конференции есть ссылки на видеозаписи докладов: https://t.me/ispras/390 Я выбрал по одному докладу с каждого мероприятия и далее расскажу, чем эти доклады меня привлекли. На НСКФ меня более всего заинтересовал доклад "Теории имен А.Питтса и М.Габбая и детерминированное параллельное объектно-ориентированное программирование имеют общую основу" от Климова А. В. и Адамовича А. И. Этот доклад основан на статье "Адамович А. И., Климов А. В. О теориях имен и ссылок в формальных языках и последствиях для функционального и объектно-ориентированного программирования //Научный сервис в сети Интернет. – 2021. – Т. 23. – С. 3-21.". Статья, кстати говоря, доступна онлайн: https://keldysh.ru/abrau/2021/theses/30.pdf Авторы рассматривают фундаментальные вопросы формализации понятий имен и ссылок, а также пытаются определить промежуточный класс языков между функциональными (широкие возможности анализа и трансформации программ) и объектно-ориентированными (производительная обработка сложных структур данных). Оригинальные результаты в этой статье не приведены, но привлечение внимания к работам по номинальным техникам от А. Pitts и его коллег, считаю полезным. Добавлю, что исследования авторов станут понятнее, если посмотреть их более раннюю статью "Подход к построению системы детерминированного параллельного программирования на основе монотонных объектов": https://pat.keldysh.ru/~anklimov/papers/2019-Adamovich_Klimov--An_Approach_to_Construction_of_a_Deterministic_Parallel_Programming_System--Vestnik_SibGUTI--submitted-revised.pdf На Открытой конференции ИСП РАН было много интересных докладов и я надеюсь, что к некоторым из них мы еще на PLComp вернемся. Я выделил для себя доклад "Статический анализ, динамическое формирование и кооперативная векторизация программ для гибридных many-core процессоров", моего бывшего коллеги Владимира Роганова. Выбор доклада, разумеется, субъективный, поскольку в разработке инструментального ПО процессора, о котором рассказывает Владимир, я принимал активное участие несколько лет назад. Так или иначе, мне кажется, полезно и интересно узнать, какие необычные и непростые задачи стоят перед разработчиками компиляторов/симуляторов/ассемблеров/... спецчипов с гетерогенной и массово-параллельной архитектурой. К примеру — JIT-распараллеливание на уровне множеств ядер или вопросы написания кода для VLIW-ускорителя c неоднородным доступом к ресурсам. P.S. Непосредственно перед Владимиром выступал я, но тема моего доклада уже совсем экзотическая :) #conf

Вводная трехчасовая лекция о перспективных направлениях в области компиляции для спецпроцессоров и аппаратных ускорителей https://www.youtube.com/watch?v=1m8oAQCTSeY #dsl #smt #autotuning #superoptimization #egraph

Тем не менее несколько моментов вызывают вопросы, если не к подходу в целом, то к его реализации в JastAdd. Во-первых, как упоминалось ранее, отношения (Relations) задаются "внешним" по отношению к дереву образом, и авторы для этого используют обычный императивный код на Java, да ещё и опирающийся на неявные, генерируемые фреймворком методы. Мне такой способ не кажется декларативным и особо высокоуровневым. Во-вторых, несмотря на то, что дерево разбора превращается в направленный граф общего вида, возможность реализации Control Flow Analysis и Data Flow Analysis остаётся под вопросом. Возможно, этому мешают ограничения на неизменяемость графа, связанные с мемоизацией (в свою очередь, необходимой для эффективной работы алгоритмов). В частности, это накладывает ограничения на построение отношений между "обычными" и узлами в NTA. В любом случае, для прояснения деталей предлагаемого подхода читателю предлагается ознакомиться со статьёй, благо, она достаточно проста для понимания. Механизм Relational RAGs весьма мощный и универсальный – его полезно иметь в виду при реализации самых разных аспектов работы с языками программирования, не только статического анализа. 😊 #dsl #rag #static #analysis

https://arxiv.org/pdf/2002.06187v1.pdf Reusing Static Analysis across Different Domain-Specific Languages using Reference Attribute Grammars Авторы немного поскромничали с названием статьи — в работе используются не просто ссылочные атрибутные грамматики (Reference Attribute Grammars, RAGs), а их расширение — реляционные ссылочные атрибутные грамматики (Relational Reference Attribute Grammars) и конкретно фреймворк JastAdd. Если говорить совсем по-простому, то авторы предлагают решение аналога Expression Problem в области языков и алгоритмов статического анализа (N языков x M алгоритмов) при помощи языка промежуточного представления (Intermediate Representation, IR). Идея не нова, но есть нюанс. 😊 При традиционном подходе к (универсальному) IR, как, например, в проекте LLVM, один и тот же IR используется для всех типов статического анализа и трансформаций. С одной стороны, это действительно позволяет переиспользовать алгоритмы анализа для всех языков, которые транслируются в данный IR. Но с другой стороны, такой IR с необходимостью должен содержать информацию, требующуюся каждому реализованному алгоритму и преобразованию. Это приводит к "раздуванию" IR, как видно по тому же LLVM, но также это приводит и к "радуванию" транслятора язык->IR, поскольку разработчику приходится строить корректный IR со всей требуемой информацией даже если он использует только один алгоритм анализа, который опирается на одну десятую доступных данных. Это едва ли можно считать проблемой General-Purpose фреймворка, но для работы с Domain-Specific языками может заметно повысить сложность и трудоёмкость реализации. Другой пример нежелательного дублирования может возникнуть при применении одного и того же алгоритма к разным элементам IR. Так, авторы рассматривают применение алгоритма нахождения циклических зависимостей в программах на Java как на уровне классов, так и на уровне пакетов. Поскольку в IR эти концепции будут представлены разными узлами, применение в точности одного и того же алгоритма к ним может оказаться невозможно, и потребует дублирования кода. Разумеется, на этот фактор влияют как встроенные возможности обобщённого программирования языка реализации, так и архитектура системы анализа и трансформации вокруг IR. Но авторы предлагают подход, по построению лишённый указанных проблем: для каждого вида и алгоритма статического анализа использовать собственный IR, содержащий только ту информацию, которая необходима, и ничего лишнего! 😊 Несомненно, такой подход был бы крайне неудобным и неэффективным, если бы не фреймворк реляционных ссылочных атрибутных грамматик. Он зиждится на нескольких столпах: 1. нетерминальные атрибуты (Nonterminal Attributes, NTA aka Higher-Order Attributes) позволяют лаконично и декларативно задавать преобразования AST->AST, что сильно облегчает построение специализированных IR для каждого отдельного вида статического анализа; 2. ссылочные атрибуты позволяют добавлять рёбра, связывающие произвольные узлы, превращая дерево в направленный граф общего вида, что сильно расширяет спектр применимых алгоритмов анализа; 3. наконец, отношения (Relations) между узлами задают рёбра "внешним" по отношению к графу способом, что позволяет "автоматически" получить ссылки из узлов IR к соответствующим узлам в исходном дереве DSL. В качестве иллюстрирующих примеров авторы приводят уже упомянутый анализ циклов как для DSL, описывающего конечные автоматы, так и для языка Java на уровне классов и пакетов по отдельности, и алгоритм выявления случаев "затенения" переменных, снова для Java и для языка Modelica. Для полноты картины, авторы приводят результаты анализа производительности реализованных алгоритмов на наборе открытых Java-проектов по сравнению с традиционной реализацией на основе паттерна "посетитель" (Visitor Pattern). Благодаря механизмам мемоизации внутри фреймворка Relational RAGs (использовался JastAdd), производительность не уступает, а в некоторых случаях и превосходит традиционную реализацию, которую невозможно переиспользовать.

Некоторые идеи опережают свою эпоху на десятилетия. Автор данной заметки к оным безусловно относит систему META II, представленную еще в 1964 году. Среди прочих эта работа впечатлила Дональда Кнута, послужив одним из источников вдохновения для атрибутных грамматик. Автор всего на 6 страницах легкого текста статьи[1] описывает виртуальную машину для разбора входной строки и предметно-ориентированный язык, схожий с расширенной версией БНФ (форме Бэкуса-Науэра). В качестве иллюстрации возможностей META II показано, как этот предметно-ориентированный язык позволяет транслировать выражения из упрощенного варианта Алгола (VALGOL) в инструкции абстрактной стековой машины; естественно, что и языки алгебраических выражений[3] тоже легко разбираются META II. Но самый интересный аспект META II это возможность метакомпиляции: опорный предметно-ориентированный язык можно выразить в терминах самого себя, что позволяет пошагово расширять исходные виртуальную машину и язык (см. инструкцию в [3]). Предполагалось, что пользователи реализуют виртуальную машину (всего 19 инструкций), после чего, запустив на ней код для языка META II, будут раскручивать компилятор до нужного состояния. Более того, первая версия META II тоже была написана на метаязыке-предшественнике (META), после чего повторно реализована уже на самой META II. Кульминацией публичных исследований автора стал язык TREE-META[2], применявший те же идеи к преобразованию дерева абстрактного синтаксиса. Помимо теоретических работ Кнута META II стала предтечей более современного формализма - PEG, который набирает все большую популярность в прикладных разработках[4]. Схожие идеи легли в основу систем OMeta[5] и Ohm[6]. О META II тепло отзывались Алан Кэй, Джо Армстронг и другие известные ислледователи языков программирования. В Интернете можно найти множество реализаций виртуальной машины META II, среди которых и версия для Python 3[7] от автора заметки. Литература: 1. http://www.chilton-computing.org.uk/acl/literature/reports/p025.htm - исходная публикация 2. https://en.wikipedia.org/wiki/TREE-META - кульминация развития исходной системы авторами 3. http://www.bayfronttechnologies.com/mc_tutorial.html - подробная интерактивная демонстрация возможностей метакомпилирующих систем, отталкивающееся от META II 4. https://www.python.org/dev/peps/pep-0617/ - реализация разбора в Python 3 5. https://en.wikipedia.org/wiki/OMeta - современное развитие идей META II 6. https://ohmlang.github.io/ - еще более современная система 7. https://github.com/vkazanov/pymetaii - реализация META II на Python 3 от автора данной заметки 8. https://github.com/stevenbagley/metaii - реализация на Common Lisp 9. https://github.com/EyeBool/Meta-II-Compiler - реализация на C++ 10. https://github.com/siraben/meta-II - реализация на Scheme #classic #parsing #metaii #peg

https://dl.acm.org/doi/pdf/10.1145/3428297 Macros for Domain-Specific Languages "Yo dawg I heard you like macros so I put macros in your macros so you can expand while you expand!" Как ни забавно, эта фраза верно передаёт содержание статьи, а именно, два главных нововведения авторов: 1) введение пользовательской макросистемы для разрабатываемого пользователем же DSL (на макросах хост-языка, Racket в данном случае), и 2) переиспользование macro expander из хост-языка для реализации пользовательской системы макросов (за счёт предоставления API к определённым функциям macro expander). Звучит круто, но зачем это нужно? Почему нельзя обойтись макросами хост-языка? На это снова можно выделить две причины. Первое — это новые name binding constructs, работающие не так, как в хост-языке. Например, в статье рассматривается реализация PEG DSL, в котором конструкции захвата подвыражения и связывания его с именем могут находиться внутри звезды Клини. Но в таком случае эти имена связываются не с одним подвыражением, а со всем подсписком внутри списка выражений, порождённого звездой Клини. Например, в выражении

(define-peg arith-expr
  (=> (seq (: e1 term) (* (seq (: op* (alt "+" "-")) (: e* term))))
    (left-associate-binops e1 op* e*)))

идентификаторы op* и e* связываются со списками операторов и термов соответственно (так как находятся "под звёздочкой"), в то время как e1 связывается с одним термом. По сравнению со стандартным связыванием имён в функциях или let-выражениях такие связывания работают "шиворот навыворот", а потому требуют реализации "руками". В данном примере такая реализация написана авторами PEG DSL на макросах хост-языка, но если мы хотим чтобы пользователи DSL могли запрограммировать binding constructs по собственному вкусу, нам придётся предоставить им развитую макро-систему поверх нашего DSL. Вторая причина связана с тем, что авторы называют "hosted DSL". Мне кажется, иначе это можно было бы назвать "deeply embedded DSL". Суть в том, что DSL, который мы реализуем на макросах, является не просто синтаксическим сахаром, а требует полноценного конвейера компиляции, начиная (потенциально) с парсера вводимого нами синтаксиса, продолжая специфическим разрешением имён, нетривиальными binding context и scoping rules, возможно, проверкой типов или другим статическим анализом корректности программ, и заканчивая полноценным IR и оптимизациями. Для того чтобы дать пользователям писать макросы для такого DSL с помощью макро-системы хост-языка, нам придётся открыть доступ к внутренностям нашего компилятора чтобы пользователи могли порождать AST или даже IR нашего DSL, и "скармливать" его далее компилятору. В противном случае макросы смогут порождать только разрозненные куски (скомпилированного) DSL, связанные между собой вызовами анонимных (или не очень) функций хост-языка, которые компилятор нашего DSL проанализировать и оптимизировать уже не сможет. Так вот, чтобы получить преимущества и того, и другого, нам придётся предоставить отдельную макро-систему поверх нашего hosted DSL. А поскольку реализовать хорошую макросистему (гигиеничную, с разделением фаз и интегрирующуюся с системой модулей хост-языка) очень непросто, было бы полезно переиспользовать возможности macro-expander хост-языка. Статья предлагает API, позволяющий это сделать. #scheme #racket #macros #dsl