https://www.jeffsmits.net/assets/articles/sle20-paper4.pdf
Gradually Typing Strategies
Статья рассказывает о применении популярной техники постепенной типизации (Gradual Typing) в необычной области -- к языку переписывания термов Stratego (который используется для "program normalization, type checkers, program analyses, code generators, and more"). Несмотря на отсутствие проверки типов в Stratego до сего момента, он тем не менее послужил для вдохновения авторов Haskell фреймворка SYB.
Использование Gradual Typing (постепенной типизации) мотивировано двумя факторами. Первый -- обратная совместимость, так как Stratego (в составе фреймворков Stratego/XT и Spoofax) используется в production-системах, разрабатываемых как в академии (researchr.org, conf.researchr.org, платформа онлайн-курсов TU Delft), так и в индустрии (где-то в недрах Oracle Labs). Второй -- высокая "динамичность" переписывания термов, которая в некоторых случаях используется (а кто-то скажет "эксплуатируется") для (временного) порождения нетипизируемых термов и превращения их обратно в типизируемые.
Дополнительно задача осложняется наличием в Stratego правил переписывания "высшего порядка" (называемых "стратегиями переписывания"), принимающих и применяющих другие правила переписывания (или стратегии). Отсюда возникает понятие Type-Preserving стратегий, реализующее ограниченную форму Higher-Kinded Types.
Кроме того, авторы применяют механизм "прозрачных" во время исполнения прокси-типов для того чтобы избежать накапливания лишних динамических преобразований типов при передаче правил переписывания из статически-типизированных стратегий в динамически-типизированные и обратно.
Проверка полученной системы типов на существующем проекте (учебный ассемблер для Java-байткода) продемонстрировала два достаточно ожидаемых результата: а) корректный динамический код написан так как если бы был статически типизирован, поэтому его легко аннотировать явными типами и почти не приходится при этом рефакторить; б) плохо протестированный динамический код содержит ошибки, которые легко обнаруживаются тайп-чекером (например, возврат списка вместо элемента — классика, сам на таком попадался).
#stratego #spoofax #gradual #types
Gradually Typing Strategies
Статья рассказывает о применении популярной техники постепенной типизации (Gradual Typing) в необычной области -- к языку переписывания термов Stratego (который используется для "program normalization, type checkers, program analyses, code generators, and more"). Несмотря на отсутствие проверки типов в Stratego до сего момента, он тем не менее послужил для вдохновения авторов Haskell фреймворка SYB.
Использование Gradual Typing (постепенной типизации) мотивировано двумя факторами. Первый -- обратная совместимость, так как Stratego (в составе фреймворков Stratego/XT и Spoofax) используется в production-системах, разрабатываемых как в академии (researchr.org, conf.researchr.org, платформа онлайн-курсов TU Delft), так и в индустрии (где-то в недрах Oracle Labs). Второй -- высокая "динамичность" переписывания термов, которая в некоторых случаях используется (а кто-то скажет "эксплуатируется") для (временного) порождения нетипизируемых термов и превращения их обратно в типизируемые.
Дополнительно задача осложняется наличием в Stratego правил переписывания "высшего порядка" (называемых "стратегиями переписывания"), принимающих и применяющих другие правила переписывания (или стратегии). Отсюда возникает понятие Type-Preserving стратегий, реализующее ограниченную форму Higher-Kinded Types.
Кроме того, авторы применяют механизм "прозрачных" во время исполнения прокси-типов для того чтобы избежать накапливания лишних динамических преобразований типов при передаче правил переписывания из статически-типизированных стратегий в динамически-типизированные и обратно.
Проверка полученной системы типов на существующем проекте (учебный ассемблер для Java-байткода) продемонстрировала два достаточно ожидаемых результата: а) корректный динамический код написан так как если бы был статически типизирован, поэтому его легко аннотировать явными типами и почти не приходится при этом рефакторить; б) плохо протестированный динамический код содержит ошибки, которые легко обнаруживаются тайп-чекером (например, возврат списка вместо элемента — классика, сам на таком попадался).
#stratego #spoofax #gradual #types
В среде компиляторщиков можно встретить утверждения в духе "SSA это функциональное программирование" и "в теории нет разницы между phi-функциями и базовыми блоками с параметрами". С инженерной же точки зрения различия, все-таки, имеются. В заметке ниже показан пример этих различий со сравнением императивного и функционального подходов к разработке компилятора:
http://blog.ezyang.com/2020/10/the-hidden-problem-with-basic-block-procedures-in-ssa/
Добавлю, что нельзя сказать, что одно из этих представлений в общем случае лучше, чем другое, с точки зрения вариантов проводимого анализа (см. также https://news.ycombinator.com/item?id=24872752 ). Но, в целом, можно отметить тенденцию использования базовых блоков с параметрами в высокоуровневых IR и для межпроцедурных преобразований, а phi-функций -- в низкоуровневых представлениях (вплоть до реализации мультиплексоров в описании генерируемой цифровой схемы).
#ssa
http://blog.ezyang.com/2020/10/the-hidden-problem-with-basic-block-procedures-in-ssa/
Добавлю, что нельзя сказать, что одно из этих представлений в общем случае лучше, чем другое, с точки зрения вариантов проводимого анализа (см. также https://news.ycombinator.com/item?id=24872752 ). Но, в целом, можно отметить тенденцию использования базовых блоков с параметрами в высокоуровневых IR и для межпроцедурных преобразований, а phi-функций -- в низкоуровневых представлениях (вплоть до реализации мультиплексоров в описании генерируемой цифровой схемы).
#ssa
Работа Strategic Tree Rewriting in Attribute Grammars заслуживает внимания попыткой объединения стратегического переписывания термов с атрибутными грамматиками.
https://www-users.cs.umn.edu/~evw/pubs/kramer20sle/kramer20sle.pdf
В последнее время интерес к забытым когда-то атрибутным грамматикам (АГ), похоже, вновь возрастает. Напомню, что АГ, формализованные Д. Кнутом еще в 1968 году, позволяют элегантным образом описывать задачи (статической) семантики и не сводятся только лишь к семантическим действиям какого-нибудь YACC. В случае АГ у нас, в общем случае, имеются как синтезированные, так и унаследованные атрибуты, позволяющие учесть контекст (это может быть, к примеру, таблица имен) при семантических вычислениях. Сами же вычисления могут производиться на графе, по готовности аргументов-атрибутов.
Существует ряд современных систем быстрого прототипирования DSL-компиляторов с использованием АГ, это, в частности, JastAdd, Kiama и Silver. В рассматриваемой статье система Silver (http://melt.cs.umn.edu/silver/ ) используется для реализации стратегий в виде атрибутов высшего порядка. Зачем это нужно? Дело в том, что на уровне стратегического переписывания тяжело работать с контекстной информацией. К примеру, классический подход от E. Visser предполагает динамическое создание правил в зависимости от контекста, что не назовешь элегантным решением. На уровне атрибутов с контекстом работать значительно удобнее, в то время, как преобразования программ выразительнее осуществляются с использованием стратегий.
В статье демонстрируется ряд примеров использования такого "смешанного" подхода, среди которых: оптимизация регулярных выражений на основе производных Бржозовского и нормализация for-цикла для Halide-подобного языка. Сложно сказать, насколько предложенный подход окажется успешным, но сама по себе система Silver в любом случае представляет интерес [1].
1. Язык AbleC (расширение C11): http://melt.cs.umn.edu/ableC/
#semantics #ag #dsl #stratego
https://www-users.cs.umn.edu/~evw/pubs/kramer20sle/kramer20sle.pdf
В последнее время интерес к забытым когда-то атрибутным грамматикам (АГ), похоже, вновь возрастает. Напомню, что АГ, формализованные Д. Кнутом еще в 1968 году, позволяют элегантным образом описывать задачи (статической) семантики и не сводятся только лишь к семантическим действиям какого-нибудь YACC. В случае АГ у нас, в общем случае, имеются как синтезированные, так и унаследованные атрибуты, позволяющие учесть контекст (это может быть, к примеру, таблица имен) при семантических вычислениях. Сами же вычисления могут производиться на графе, по готовности аргументов-атрибутов.
Существует ряд современных систем быстрого прототипирования DSL-компиляторов с использованием АГ, это, в частности, JastAdd, Kiama и Silver. В рассматриваемой статье система Silver (http://melt.cs.umn.edu/silver/ ) используется для реализации стратегий в виде атрибутов высшего порядка. Зачем это нужно? Дело в том, что на уровне стратегического переписывания тяжело работать с контекстной информацией. К примеру, классический подход от E. Visser предполагает динамическое создание правил в зависимости от контекста, что не назовешь элегантным решением. На уровне атрибутов с контекстом работать значительно удобнее, в то время, как преобразования программ выразительнее осуществляются с использованием стратегий.
В статье демонстрируется ряд примеров использования такого "смешанного" подхода, среди которых: оптимизация регулярных выражений на основе производных Бржозовского и нормализация for-цикла для Halide-подобного языка. Сложно сказать, насколько предложенный подход окажется успешным, но сама по себе система Silver в любом случае представляет интерес [1].
1. Язык AbleC (расширение C11): http://melt.cs.umn.edu/ableC/
#semantics #ag #dsl #stratego
Поздравляю читателей PLComp с предстоящими праздниками! Подведу некоторые итоги этого года.
1. Выход очередного, четвертого тома HOPL. https://t.me/plcomp/6
Замечательное, увлекательное чтение для всех, кто интересуется историей разработки ЯП.
2. Развитие подхода E-Graphs для создания систем оптимизации и синтеза программ. https://t.me/plcomp/8
Именно в этом году появились доступные реализации E-Graphs, в том числе и учебные. Следует ожидать постепенного внедрения подхода в компиляторы.
3. Практические применения SyGuS (синтаксически-управляемый синтез программ) в компиляторах.
Для BPF (https://t.me/plcomp/51), для сетевых процессоров (https://dl.acm.org/doi/abs/10.1145/3387514.3405852) и для DSP (https://www.cs.utexas.edu/~bornholt/papers/diospyros-lctes20.pdf ).
В будущем году, надеюсь, мы в PLComp также сможем оперативно реагировать на основные события в компиляторной/языковой тематике. Пока же предлагаю "заглянуть в будущее", посмотреть на работы предстоящих конференций.
1. ASPLOS 2021. https://asplos-conference.org/papers/
2. POPL 2021. https://popl21.sigplan.org/program/program-POPL-2021
3. CGO 2021. https://conf.researchr.org/info/cgo-2021/accepted-papers
#conf
1. Выход очередного, четвертого тома HOPL. https://t.me/plcomp/6
Замечательное, увлекательное чтение для всех, кто интересуется историей разработки ЯП.
2. Развитие подхода E-Graphs для создания систем оптимизации и синтеза программ. https://t.me/plcomp/8
Именно в этом году появились доступные реализации E-Graphs, в том числе и учебные. Следует ожидать постепенного внедрения подхода в компиляторы.
3. Практические применения SyGuS (синтаксически-управляемый синтез программ) в компиляторах.
Для BPF (https://t.me/plcomp/51), для сетевых процессоров (https://dl.acm.org/doi/abs/10.1145/3387514.3405852) и для DSP (https://www.cs.utexas.edu/~bornholt/papers/diospyros-lctes20.pdf ).
В будущем году, надеюсь, мы в PLComp также сможем оперативно реагировать на основные события в компиляторной/языковой тематике. Пока же предлагаю "заглянуть в будущее", посмотреть на работы предстоящих конференций.
1. ASPLOS 2021. https://asplos-conference.org/papers/
2. POPL 2021. https://popl21.sigplan.org/program/program-POPL-2021
3. CGO 2021. https://conf.researchr.org/info/cgo-2021/accepted-papers
#conf
Размещение сотен промежуточных значений современных программ в десятках регистров типичных процессоров - одна из первых проблем, с которой столкнулись разработчики языков высокого яровня. Со временем было показано, что в общем случае задача распределения регистров является NP-полной, что предполагает множество эвристических и частичных решений.
"A survey on register allocation" - обзор темы РР на 2008 год с пояснением ключевой терминологи и перечислением наиболее эффективных подходов к проблеме.
Много внимания уделяется вариантам алгоритмов раскраски графа, линейного сканирования (linear scan) и перспективным на момент написания статьи альтернативным подходам (целочисленное линейное программирование, multi-commodity flow problem и др.).
В 2008 году все крупные компиляторы перешли к использованию внутренних представляний со статически однократным присваиванием (SSA). Поэтому естественно, что половина обзора посвящена рассмотрению полезных в РР свойств популярнейшего представления и адаптации ключевых алгоритмов к нему.
Интересно, что в обзоре почти не упоминаются легковесное локальное (внутри базовых блоков) РР и тяжелое точное РР; рассматриваются прежде всего популярные в больших промышленных компиляторах решения.
Материал написан доступно и явно ориентирован на введение в курс дела старшекурсников или аспирантов; автор не только разбирается в материале, но и умеет его донести.
#registerallocation #survey
http://compilers.cs.ucla.edu/fernando/publications/drafts/survey.pdf
"A survey on register allocation" - обзор темы РР на 2008 год с пояснением ключевой терминологи и перечислением наиболее эффективных подходов к проблеме.
Много внимания уделяется вариантам алгоритмов раскраски графа, линейного сканирования (linear scan) и перспективным на момент написания статьи альтернативным подходам (целочисленное линейное программирование, multi-commodity flow problem и др.).
В 2008 году все крупные компиляторы перешли к использованию внутренних представляний со статически однократным присваиванием (SSA). Поэтому естественно, что половина обзора посвящена рассмотрению полезных в РР свойств популярнейшего представления и адаптации ключевых алгоритмов к нему.
Интересно, что в обзоре почти не упоминаются легковесное локальное (внутри базовых блоков) РР и тяжелое точное РР; рассматриваются прежде всего популярные в больших промышленных компиляторах решения.
Материал написан доступно и явно ориентирован на введение в курс дела старшекурсников или аспирантов; автор не только разбирается в материале, но и умеет его донести.
#registerallocation #survey
http://compilers.cs.ucla.edu/fernando/publications/drafts/survey.pdf
И мой комментарий к комментарию https://t.me/plcomp/64 по "A Survey on Register Allocation".
Статья-обзор по алгоритмам распределения регистров. Автор старается простыми словами объяснить на ходу базовую терминологию, чтобы читателю не пришлось на каждом шагу сверяться с другими источниками. В этом смысле содержание обзора можно было бы назвать доходчивым. Но, казалось бы, это не большое достижение -- на тему распределения регистров есть разделы в известных учебниках, а проект LLVM, кажется, вообще закрыл эту тему для компиляторщиков, мол, бери готовое и не думай, как оно устроено.
А теперь перейду к сути. Fernando M Q Pereira, автор рассматриваемого обзора, один из признанных современных специалистов в области распределения регистров. F.M.Q. — автор передового алгоритма Puzzle Solving и даже имеет патент на него. Что касается самого обзора, то это, на мой взгляд, обязательное чтение для компиляторщика-профессионала, которого интересуют вопросы порождения целевого кода, особенно для нетрадиционных, неортогональных архитектур. И при всей своей внешней доходчивости это нелегкое чтение, требующее серьезной квалификации.
В обзоре рассматриваются как классические подходы, так и подходы передовые, специализированные. Передовые настолько, что в реализации LLVM вы их не встретите. Речь, например, о распределении регистров прямо в форме SSA, а также о более экзотических техниках, в духе PBQP.
Важно, что перед нами действительно научный обзор, поэтому автор не скупится на изложение важных теоретических результатов. На этот счет, в частности, есть очень ценный, заключительный раздел по NP-полным (современным!) результатам из области распределения регистров.
#registerallocation
Статья-обзор по алгоритмам распределения регистров. Автор старается простыми словами объяснить на ходу базовую терминологию, чтобы читателю не пришлось на каждом шагу сверяться с другими источниками. В этом смысле содержание обзора можно было бы назвать доходчивым. Но, казалось бы, это не большое достижение -- на тему распределения регистров есть разделы в известных учебниках, а проект LLVM, кажется, вообще закрыл эту тему для компиляторщиков, мол, бери готовое и не думай, как оно устроено.
А теперь перейду к сути. Fernando M Q Pereira, автор рассматриваемого обзора, один из признанных современных специалистов в области распределения регистров. F.M.Q. — автор передового алгоритма Puzzle Solving и даже имеет патент на него. Что касается самого обзора, то это, на мой взгляд, обязательное чтение для компиляторщика-профессионала, которого интересуют вопросы порождения целевого кода, особенно для нетрадиционных, неортогональных архитектур. И при всей своей внешней доходчивости это нелегкое чтение, требующее серьезной квалификации.
В обзоре рассматриваются как классические подходы, так и подходы передовые, специализированные. Передовые настолько, что в реализации LLVM вы их не встретите. Речь, например, о распределении регистров прямо в форме SSA, а также о более экзотических техниках, в духе PBQP.
Важно, что перед нами действительно научный обзор, поэтому автор не скупится на изложение важных теоретических результатов. На этот счет, в частности, есть очень ценный, заключительный раздел по NP-полным (современным!) результатам из области распределения регистров.
#registerallocation
Telegram
PLComp
Размещение сотен промежуточных значений современных программ в десятках регистров типичных процессоров - одна из первых проблем, с которой столкнулись разработчики языков высокого яровня. Со временем было показано, что в общем случае задача распределения…
Next-gen Haskell Compilation Techniques
На мой взгляд, презентация интересна будет многим компиляторщикам. Автор приводит массу академических ссылок. В целом, речь идет о проблематике организации архитектуры современного компилятора. Мне, например, очень понравилась идея с использованием Datalog, которая дополнительно себя оправдала и с точки зрения производительности статического анализа.
https://docs.google.com/presentation/u/0/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26zpqXssQ/mobilepresent
#ghc #grin
На мой взгляд, презентация интересна будет многим компиляторщикам. Автор приводит массу академических ссылок. В целом, речь идет о проблематике организации архитектуры современного компилятора. Мне, например, очень понравилась идея с использованием Datalog, которая дополнительно себя оправдала и с точки зрения производительности статического анализа.
https://docs.google.com/presentation/u/0/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26zpqXssQ/mobilepresent
#ghc #grin
👍1
Самый ранний и задавший главные направления исследований в области компиляторов проект это, безусловно, оптимизирующий компилятор языка Fortran I. Работы над ним велись в середине 1950-х и примененные в компиляторе техники устарели, но, например, остроумный механизм распределения регистров продержался в Fortran еще много лет.
Распределение регистров в Фортране 1 проводится в два этапа. На вход первого этапа поступает список инструкций, использующих неограниченное число символьных регистров. Список разбивается на базовые блоки, то есть строится граф потока исполнения. При этом во всех ветвлениях (IF, вычисляемых GOTO) программисты на языке должны были сами (!) расставить вероятность перехода по каждой из ветвей. Вероятности впоследствии используются для моделирования частоты базовых блоков метдом Монте-Карло.
Во втором этапе, начиная от самого "горячего" из оставшихся необработанных блоков, строится регион, внутри которого будет проводится распределение регистров. Регион расширяется самым горячим из соседних базовых блоков до тех пор, пока не упирается в другие регионы или начало/конец графа. Специальным образом обрабатывается закольцованные регионы, то есть циклы.
Само выделение регистров происходит внутри каждого такого региона; при необходимости вытесняются регистры, наименее востребованные в оставшейся части региона (например, мертвые).
Материалы для интересующихся историей компиляторов:
https://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_i1/fortran.pdf - краткий современный обзор компилятора
http://archive.computerhistory.org/resources/text/Fortran/102663113.05.01.acc.pdf - оригинальная публикация 1957-го года.
#history #fortran #registerallocation
Распределение регистров в Фортране 1 проводится в два этапа. На вход первого этапа поступает список инструкций, использующих неограниченное число символьных регистров. Список разбивается на базовые блоки, то есть строится граф потока исполнения. При этом во всех ветвлениях (IF, вычисляемых GOTO) программисты на языке должны были сами (!) расставить вероятность перехода по каждой из ветвей. Вероятности впоследствии используются для моделирования частоты базовых блоков метдом Монте-Карло.
Во втором этапе, начиная от самого "горячего" из оставшихся необработанных блоков, строится регион, внутри которого будет проводится распределение регистров. Регион расширяется самым горячим из соседних базовых блоков до тех пор, пока не упирается в другие регионы или начало/конец графа. Специальным образом обрабатывается закольцованные регионы, то есть циклы.
Само выделение регистров происходит внутри каждого такого региона; при необходимости вытесняются регистры, наименее востребованные в оставшейся части региона (например, мертвые).
Материалы для интересующихся историей компиляторов:
https://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_i1/fortran.pdf - краткий современный обзор компилятора
http://archive.computerhistory.org/resources/text/Fortran/102663113.05.01.acc.pdf - оригинальная публикация 1957-го года.
#history #fortran #registerallocation
Некоторые разработки получают известность не в силу новаторских решений, а благодаря качественной инженерной работе и удобной сопроводительной документации. Пример - портативный компилятор lcc, ставший прообразом 8cc, chibicc, tcc и других свободно доступных небольших компиляторов.
Разработчики lcc задались целью сделать не просто полноценный компилятор языка Си, но еще и подробно документированный: проект написан в стиле "литературного программирования" Д.Кнута, когда код интегрирован в документацию (а не наоборот).
Более того, из такого "художественного" исходного кода можно собрать полноценную книгу, изданную под названием A Retargetable C Compiler: Design and Implementation. Вместе с книгой для разъяснения ключевых технических решений авторы опубликовали статьи, посвященные, например, распределению регистров и порождению кода.
lcc можно отнести к промежуточному варианту между простыми компиляторами, описываемыми в популярных книгах для программистов, и серьезными оптимизирующими компиляторами. Здесь есть внутреннее представление (лес ациклических графов внутри базовых блоков графа потока исполнения), используются отдельные популярные оптимизации.
Характерное для компилятора решение - распределение регистров. Оно локальное и восходящее, то есть проводится внутри базового блока проходом по списку инструкций. Регистры один за другим выделяются под значения до тех пор, пока не приходится искать значение для вытеснения в память. Вытесняются те значения, следующее использование которых в списке инструкций находится дальше всего.
В результате компилятор был портирован на множество платформ, стал основой для бесчисленных форков и даже использовался для скриптования популярного игрового движка id Tech 3 (см. Quake 3 Arena) компании idSoftware.
https://en.wikipedia.org/wiki/LCC_(compiler)
https://github.com/drh/lcc
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.2519&rep=rep1&type=pdf
https://en.wikipedia.org/wiki/Id_Tech_3
#lcc #history #registerallocation
Разработчики lcc задались целью сделать не просто полноценный компилятор языка Си, но еще и подробно документированный: проект написан в стиле "литературного программирования" Д.Кнута, когда код интегрирован в документацию (а не наоборот).
Более того, из такого "художественного" исходного кода можно собрать полноценную книгу, изданную под названием A Retargetable C Compiler: Design and Implementation. Вместе с книгой для разъяснения ключевых технических решений авторы опубликовали статьи, посвященные, например, распределению регистров и порождению кода.
lcc можно отнести к промежуточному варианту между простыми компиляторами, описываемыми в популярных книгах для программистов, и серьезными оптимизирующими компиляторами. Здесь есть внутреннее представление (лес ациклических графов внутри базовых блоков графа потока исполнения), используются отдельные популярные оптимизации.
Характерное для компилятора решение - распределение регистров. Оно локальное и восходящее, то есть проводится внутри базового блока проходом по списку инструкций. Регистры один за другим выделяются под значения до тех пор, пока не приходится искать значение для вытеснения в память. Вытесняются те значения, следующее использование которых в списке инструкций находится дальше всего.
В результате компилятор был портирован на множество платформ, стал основой для бесчисленных форков и даже использовался для скриптования популярного игрового движка id Tech 3 (см. Quake 3 Arena) компании idSoftware.
https://en.wikipedia.org/wiki/LCC_(compiler)
https://github.com/drh/lcc
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.2519&rep=rep1&type=pdf
https://en.wikipedia.org/wiki/Id_Tech_3
#lcc #history #registerallocation
BLISS - один из самых ранних портативных языков для системного программирования, первая версия которого (BLISS-10) была выпущена для PDP-10 еще в 1970-ом году. Наиболее широкое применение язык нашел во внутренних разработках компании DEC, где на BLISS вплоть до 90-х создавались компиляторы, операционные системы и низкоуровневые утилиты.
Но прославился этот язык благодаря версии для PDP-11, вышедшей в 1975 году. Компилятор BLISS-11 был на голову выше конкурентов вроде ранних компиляторов C и поражал воображение разработчиков ("we'd sit and chuckle at what it had done"). Реализацию описывали несколько диссертаций (одна из них - за авторством будущего основателя Adobe) и книга. Пример инновационности BLISS-11 - анализ жизни переменных в применении к глобальному распределению регистров.
Книга описывает собственный подход к анализу областей жизни переменных (потому что "no truly satisfactory solution exists in the literature"). Найденные области обозначались каждая двумя координатами в двухмерном пространстве. Координаты задавали вершины прямоугольников. Если области-прямоугольники времени жизни переменных пересекались, то такие области не должны были оказываться в одном регистре.
Каждая переменная получала рейтинг на основе расположения в коде (напр. глубины вложения циклов) и размера области жизни (меньше - лучше). Переменные сортировались по рейтингу, и за один проход одна за другой сопоставлялись с регистрами, если только при этом не случалось пересечения с уже сопоставленными с регистром переменными.
Позже эта проблема была сведена к NP-сложной задаче об упаковке в контейнеры; и в следующих версиях BLISS разработчики развили подход в семейство алгоритмов binpacking, к которым относится и популярный алгоритм линейного сканирования.
С закатом DEC зашла и звезда BLISS. Но в истории компиляторов реализация языка оставила значимый след: книга The Design of an Optimizing Compiler (1975) стала классикой, и без BLISS любое обсуждение истории компиляторов будет неполным.
Wulf, W.A., 1975. The design of an optimizing compiler.
Brender, Ronald F. 2002. The BLISS programming language: a history
#bliss #registerallocation #history
Но прославился этот язык благодаря версии для PDP-11, вышедшей в 1975 году. Компилятор BLISS-11 был на голову выше конкурентов вроде ранних компиляторов C и поражал воображение разработчиков ("we'd sit and chuckle at what it had done"). Реализацию описывали несколько диссертаций (одна из них - за авторством будущего основателя Adobe) и книга. Пример инновационности BLISS-11 - анализ жизни переменных в применении к глобальному распределению регистров.
Книга описывает собственный подход к анализу областей жизни переменных (потому что "no truly satisfactory solution exists in the literature"). Найденные области обозначались каждая двумя координатами в двухмерном пространстве. Координаты задавали вершины прямоугольников. Если области-прямоугольники времени жизни переменных пересекались, то такие области не должны были оказываться в одном регистре.
Каждая переменная получала рейтинг на основе расположения в коде (напр. глубины вложения циклов) и размера области жизни (меньше - лучше). Переменные сортировались по рейтингу, и за один проход одна за другой сопоставлялись с регистрами, если только при этом не случалось пересечения с уже сопоставленными с регистром переменными.
Позже эта проблема была сведена к NP-сложной задаче об упаковке в контейнеры; и в следующих версиях BLISS разработчики развили подход в семейство алгоритмов binpacking, к которым относится и популярный алгоритм линейного сканирования.
С закатом DEC зашла и звезда BLISS. Но в истории компиляторов реализация языка оставила значимый след: книга The Design of an Optimizing Compiler (1975) стала классикой, и без BLISS любое обсуждение истории компиляторов будет неполным.
Wulf, W.A., 1975. The design of an optimizing compiler.
Brender, Ronald F. 2002. The BLISS programming language: a history
#bliss #registerallocation #history
Распределение регистров - одна из старейших проблем построения компиляторов, первые работы по которой появились еще в 50-ые годы прошлого века. Как и в других NP-полных задачах недостатка в эвристических решениях нет. Тем не менее, в последние десятилетия разработчики все чаще используют один из двух глобальных подходов: линейное сканирование в динамических (JIT) компиляторах и раскраску графа в статических (AOT) компиляторах.
В своей диссертации Йозеф Эйсель (Josef Eisl) предлагает новый субглобальный подход к распределению регистров в динамических компиляторах, имеющий в основе следующие наблюдения:
1. Глобальные методы тратят много времени на редко исполняемый (холодный) код.
2. В современных динамически компилируемых языках после агрессивного встраивания функций (inline) появляются большие функции, где много холодного кода.
3. Крупные функции при глобальном охвате занимают много времени.
Выходит, что если сконцентрировать внимание алгоритма на горячих участках в ущерб холодным, то можно за то же время найти эффективное (или даже оптимальное!) распределение на отдельных важных участках кода.
В качестве важных участков Эйсель выбрал непересекающиеся последовательности базовых блоков - трассы (traces). Каждая трасса в зависимости от популярности получает свою политику распределения - быструю и неэффективную, долгую и эффективную, компромиссную или даже специализированную.
Интересно, что схожий подход уже применялся в трассирующих jit-компиляторах, но там трассы компилировались целиком, тогда как у Эйселя трассы выделяются только для распределения регистров.
Эйсель в сотрудничестве с Oracle реализовал подход в GraalVM, нового jit-компилятора для JVM, где тот показал сравнимую с актуальными версиями линейного сканирования производительность порожденного кода при меньшем времени РР. При этом распределение на трассах позволяет искать баланс между временем компиляции и производительностью распределения, а также открывает возможности для параллельной работы над трассами.
В настоящий момент код по умолчанию выключен, но доступен в Java версий от 10 и новее через опции
https://ssw.jku.at/General/Staff/Eisl/papers/phdthesis.pdf
#registerallocation #trace #graalvm #jvm
В своей диссертации Йозеф Эйсель (Josef Eisl) предлагает новый субглобальный подход к распределению регистров в динамических компиляторах, имеющий в основе следующие наблюдения:
1. Глобальные методы тратят много времени на редко исполняемый (холодный) код.
2. В современных динамически компилируемых языках после агрессивного встраивания функций (inline) появляются большие функции, где много холодного кода.
3. Крупные функции при глобальном охвате занимают много времени.
Выходит, что если сконцентрировать внимание алгоритма на горячих участках в ущерб холодным, то можно за то же время найти эффективное (или даже оптимальное!) распределение на отдельных важных участках кода.
В качестве важных участков Эйсель выбрал непересекающиеся последовательности базовых блоков - трассы (traces). Каждая трасса в зависимости от популярности получает свою политику распределения - быструю и неэффективную, долгую и эффективную, компромиссную или даже специализированную.
Интересно, что схожий подход уже применялся в трассирующих jit-компиляторах, но там трассы компилировались целиком, тогда как у Эйселя трассы выделяются только для распределения регистров.
Эйсель в сотрудничестве с Oracle реализовал подход в GraalVM, нового jit-компилятора для JVM, где тот показал сравнимую с актуальными версиями линейного сканирования производительность порожденного кода при меньшем времени РР. При этом распределение на трассах позволяет искать баланс между временем компиляции и производительностью распределения, а также открывает возможности для параллельной работы над трассами.
В настоящий момент код по умолчанию выключен, но доступен в Java версий от 10 и новее через опции
java -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler -Dgraal.TraceRA=true.
https://ssw.jku.at/General/Staff/Eisl/papers/phdthesis.pdf
#registerallocation #trace #graalvm #jvm
На Хабре несколько дней назад появилась статья, популярно поясняющая знаменитую технику реализации языка Scheme - Cheney on the M.T.A. Статья излагает историю названия и объясняет работу остроумного подхода к сборке мусора.
Исходный код Scheme здесь сначала должен быть преобразован в представление с продолжениями (см., например, книгу Compiling with Continuations). Функции этого представления один к одному компилируются в функции на языке C. Многочисленные временные значения, характерные для Scheme, сначала размещаются на стеке вызовов C. Во время работы программы стек вызовов функций C будет расти, так как при компиляции с продолжениями функции не возвращаются к точке исходного вызова.
При превышении допустимого размера стек сбрасывается вызовом longjmp. Размер проверяется, например, через численное значение адреса временной переменной. Перед сбросом живые значения из стека перемещаются в кучу для зачистки алгоритмом Чейни, мертвые же значения отбрасываются автоматически.
Техника сильно упрощает компиляцию Scheme в C (например, рекурсивные вызовы и их оптимизацию, легко выражаются продолжения), из-за чего ее используют минимум два популярных компилятора: Cyclone и Chicken.
Статья на Хабре: https://habr.com/ru/company/ruvds/blog/540502/
Подробности реализации техники от разработчика Chicken Scheme:
https://www.more-magic.net/posts/internals-gc.html
Реализация Cyclone: https://justinethier.github.io/cyclone/docs/Garbage-Collector
Оригинальная публикация по Cheney on the MTA: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3A988CF024FE807165D1CFA957445BC8?doi=10.1.1.54.7143&rep=rep1&type=pdf
Алгоритм сборки мусора Чейни: https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/p677-cheney.pdf
Компиляторы, использующий другие подходы к компиляции в язык C:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.8424&rep=rep1&type=pdf - Bigloo - компилятор Scheme и Standard ML
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.8788&rep=rep1&type=pdf - Gambit - компилятор Scheme
#garbagecollection #scheme
Исходный код Scheme здесь сначала должен быть преобразован в представление с продолжениями (см., например, книгу Compiling with Continuations). Функции этого представления один к одному компилируются в функции на языке C. Многочисленные временные значения, характерные для Scheme, сначала размещаются на стеке вызовов C. Во время работы программы стек вызовов функций C будет расти, так как при компиляции с продолжениями функции не возвращаются к точке исходного вызова.
При превышении допустимого размера стек сбрасывается вызовом longjmp. Размер проверяется, например, через численное значение адреса временной переменной. Перед сбросом живые значения из стека перемещаются в кучу для зачистки алгоритмом Чейни, мертвые же значения отбрасываются автоматически.
Техника сильно упрощает компиляцию Scheme в C (например, рекурсивные вызовы и их оптимизацию, легко выражаются продолжения), из-за чего ее используют минимум два популярных компилятора: Cyclone и Chicken.
Статья на Хабре: https://habr.com/ru/company/ruvds/blog/540502/
Подробности реализации техники от разработчика Chicken Scheme:
https://www.more-magic.net/posts/internals-gc.html
Реализация Cyclone: https://justinethier.github.io/cyclone/docs/Garbage-Collector
Оригинальная публикация по Cheney on the MTA: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3A988CF024FE807165D1CFA957445BC8?doi=10.1.1.54.7143&rep=rep1&type=pdf
Алгоритм сборки мусора Чейни: https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/p677-cheney.pdf
Компиляторы, использующий другие подходы к компиляции в язык C:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.8424&rep=rep1&type=pdf - Bigloo - компилятор Scheme и Standard ML
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.8788&rep=rep1&type=pdf - Gambit - компилятор Scheme
#garbagecollection #scheme
https://grosskurth.ca/bib/1997/cardelli.pdf
"Program Fragments, Linking, and Modularization" Luca Cardelli.
Статья поднимает вопрос корректности раздельной компиляции и линковки, и потому — я считаю — обязательна к прочтению для всех авторов языков программирования! 😃
Уже во введении на простейшем примере создания воображаемой программы, состоящей всего из двух модулей, разрабатываемых независимо, автор иллюстрирует, наверное, все проблемы, при этом возникающие. Между делом Карделли упоминает публичные репозитории артефактов (типа Maven Central или Nuget. Напомню, что статья опубликована в 1996 году!). Многие из обозначенных проблем линковки раздельно скомпилированных модулей до сих пор не решены ни в мейнстримных, ни в исследовательских языках.
В качестве основного результата Карделли предлагает, вероятно, первую формальную модель раздельной компиляции и последующей линковки, позволяющую строго рассмотреть вопрос о корректности этих процессов. Корректность в этом смысле приведённой простейшей системы модулей для просто типизированного лямбда-исчисления (в качестве модельного языка) формально доказывается. Автор, конечно же, указывает на необходимость расширения модели как в сторону более развитых языков (параметрический полиморфизм, ООП), так и в сторону более сложных систем модулей (параметризованные модули, "функторы" в духе Standard ML, первоклассные модули). Существуют ли такие работы, непосредственно продолжающие это исследование, мне не известно.
Однако, в качестве related work и дальнейшего чтения могу указать на работы по формализации (и доказательству корректности) раздельной компиляции для языка C в рамках проекта CompCert.
#separatecompilation #linking #modules #stlc
"Program Fragments, Linking, and Modularization" Luca Cardelli.
Статья поднимает вопрос корректности раздельной компиляции и линковки, и потому — я считаю — обязательна к прочтению для всех авторов языков программирования! 😃
Уже во введении на простейшем примере создания воображаемой программы, состоящей всего из двух модулей, разрабатываемых независимо, автор иллюстрирует, наверное, все проблемы, при этом возникающие. Между делом Карделли упоминает публичные репозитории артефактов (типа Maven Central или Nuget. Напомню, что статья опубликована в 1996 году!). Многие из обозначенных проблем линковки раздельно скомпилированных модулей до сих пор не решены ни в мейнстримных, ни в исследовательских языках.
В качестве основного результата Карделли предлагает, вероятно, первую формальную модель раздельной компиляции и последующей линковки, позволяющую строго рассмотреть вопрос о корректности этих процессов. Корректность в этом смысле приведённой простейшей системы модулей для просто типизированного лямбда-исчисления (в качестве модельного языка) формально доказывается. Автор, конечно же, указывает на необходимость расширения модели как в сторону более развитых языков (параметрический полиморфизм, ООП), так и в сторону более сложных систем модулей (параметризованные модули, "функторы" в духе Standard ML, первоклассные модули). Существуют ли такие работы, непосредственно продолжающие это исследование, мне не известно.
Однако, в качестве related work и дальнейшего чтения могу указать на работы по формализации (и доказательству корректности) раздельной компиляции для языка C в рамках проекта CompCert.
#separatecompilation #linking #modules #stlc
Распределение регистров и планирование инструкций - важные аспекты реализации бэкенда компилятора. Обе задачи NP-полны и связаны между собой: распределение может внести в код новые инструкции, планирование же меняет инструкции местами. Несмотря на это в популярных компиляторах решаются они, как правило, раздельно и используют эвристические подходы.
Последние два десятилетия много исследований было посвящено точным комбинаторным методам решения тех же самых задач: предложены методы на основе целочисленного программирования, PBQP, программирования в ограничениях и др. Слабость таких подходов - большое время поиска оптимальных решений, что заставляет исследователей упрощать задачу, делая методы неприменимыми в универсальных компиляторах.
Роберто Лозано (Roberto Castaneda Lozano) задался целью разработать одновременно точный и легкий в реализации подход, причем решающий задачи планирования инструкций и распределения регистров совместно. За основу он взял программирование в ограничениях (constraint programming), позволяющее удобно выразить условия обеих задач и для которого существуют мощные решатели.
Проект Unison заменяет три фазы LLVM: предварительное планирование инструкций, распределение регистров и финальное планирование. Распределение проводится глобальное, планирование же локальное - последнее упрощение дает ощутимый эффект при умеренной сложности.
В отличие от предшественников Unison не упрощает задачу распределения. Все практические аспекты проблемы учитываются в решениях: спиллинг, алиасинг (aliasing), рематериализация (rematerialisation), разбиение областей жизни переменных (live range splitting), слияние (coalescing) и др. Программирование в ограничениях позволяет выразить любые проблемы распределения регистров лаконично и просто.
Оптимальность имеет свою цену: поиск решений занимает много времени. Размер компилируемых функций - до 1000 инструкций. Наибольший эффект от Unison был показан на спецпроцессоре Hexagon с длинным машинным словом (VLIW), где важно оптимальное расписание: на некоторых тестах реальное время исполнения снижается на 40%.
Лозано предлагает использовать Unison как инструмент для порождения кода к спецпроцессорам, оценки эффективности эвристических решений, поиска оптимальных решений в отдельных функциях.
Презентация на конференции LLVM (2017): https://www.youtube.com/watch?v=kx64V74Mba0
Обобщающая исследования Лозано диссертация (2018 год): http://kth.diva-portal.org/smash/get/diva2:1232941/FULLTEXT01.pdf
Оценка производительности Unison (2017): https://www.diva-portal.org/smash/get/diva2:1119107/FULLTEXT01.pdf
Сайт проекта: https://unison-code.github.io/
Программирование в ограничениях: https://ru.wikipedia.org/wiki/Программирование_в_ограничениях
Программная статья от именитых исследователей (Nuno P. Lopes и John Regehr) о роли точных методов в будущих компиляторах: https://arxiv.org/pdf/1809.02161.pdf
#registeralloc #instructionscheduling #constraintprogramming #unison #llvm
Последние два десятилетия много исследований было посвящено точным комбинаторным методам решения тех же самых задач: предложены методы на основе целочисленного программирования, PBQP, программирования в ограничениях и др. Слабость таких подходов - большое время поиска оптимальных решений, что заставляет исследователей упрощать задачу, делая методы неприменимыми в универсальных компиляторах.
Роберто Лозано (Roberto Castaneda Lozano) задался целью разработать одновременно точный и легкий в реализации подход, причем решающий задачи планирования инструкций и распределения регистров совместно. За основу он взял программирование в ограничениях (constraint programming), позволяющее удобно выразить условия обеих задач и для которого существуют мощные решатели.
Проект Unison заменяет три фазы LLVM: предварительное планирование инструкций, распределение регистров и финальное планирование. Распределение проводится глобальное, планирование же локальное - последнее упрощение дает ощутимый эффект при умеренной сложности.
В отличие от предшественников Unison не упрощает задачу распределения. Все практические аспекты проблемы учитываются в решениях: спиллинг, алиасинг (aliasing), рематериализация (rematerialisation), разбиение областей жизни переменных (live range splitting), слияние (coalescing) и др. Программирование в ограничениях позволяет выразить любые проблемы распределения регистров лаконично и просто.
Оптимальность имеет свою цену: поиск решений занимает много времени. Размер компилируемых функций - до 1000 инструкций. Наибольший эффект от Unison был показан на спецпроцессоре Hexagon с длинным машинным словом (VLIW), где важно оптимальное расписание: на некоторых тестах реальное время исполнения снижается на 40%.
Лозано предлагает использовать Unison как инструмент для порождения кода к спецпроцессорам, оценки эффективности эвристических решений, поиска оптимальных решений в отдельных функциях.
Презентация на конференции LLVM (2017): https://www.youtube.com/watch?v=kx64V74Mba0
Обобщающая исследования Лозано диссертация (2018 год): http://kth.diva-portal.org/smash/get/diva2:1232941/FULLTEXT01.pdf
Оценка производительности Unison (2017): https://www.diva-portal.org/smash/get/diva2:1119107/FULLTEXT01.pdf
Сайт проекта: https://unison-code.github.io/
Программирование в ограничениях: https://ru.wikipedia.org/wiki/Программирование_в_ограничениях
Программная статья от именитых исследователей (Nuno P. Lopes и John Regehr) о роли точных методов в будущих компиляторах: https://arxiv.org/pdf/1809.02161.pdf
#registeralloc #instructionscheduling #constraintprogramming #unison #llvm
https://hal.inria.fr/hal-01499946/document
"A modular module system", Xavier Leroy
Утверждение, что (ML-style) система модулей не зависит от "базового" языка программирования, и может быть реализована почти для любого, а не только ML, широко известно и озвучивалось в литературе. Данная статья приводит конструктивное доказательство этого тезиса, реализуя такую (слегка упрощённую) систему модулей, в виде, явно параметризованном относительно синтаксиса и системы типов базового языка.
Несмотря на ряд упрощений по сравнению с системой модулей того же Standard ML, представленная модельная система содержит (и корректно реализует) все базовые возможности, включая структурную типизацию модулей, абстрактные типы, функторы, зависимость (типа) результата функтора от (типа) аргумента а также равенства между (абстрактными) типами.
> All in all, module type matching resembles subtyping in a functional language with records, with some extra complications due to the dependencies in functor types and signatures.
Статья составлена в духе Literate Programming, перемежая пояснительный текст и реальный рабочий код на языке OCaml. Реализация системы модулей ML с помощью системы модулей ML отсылает к традиции метациркулярных интерпретаторов Лисп. Леруа выражает надежду, что такой способ представления материала не только не запутает читателя, но и дополнительно прояснит связь конкретного и абстрактного синтаксиса как и практическую полезность (и даже необходимость) всех возможностей представленной системы. (По-видимому, метациркулярность системы не оставила Лисперов равнодушными, что привело к появлению реализации MiniML с полноценной системой модулей на Scheme: http://wiki.call-cc.org/eggref/4/miniML 😊)
Для иллюстрации приводятся два примера "надстраивания" реализованной системы модулей над "упрощённым C" в качестве императивного (процедурного) базового языка и Mini-ML в качестве функционального, приближенного к используемым на практике, в частности, реализующего типы высших порядков (Higher-Kinded Types).
Кратко обсуждаются вопросы (модульной) компиляции таких модулей. Упоминаются три основных варианта: компиляция самих модулей в виде структур данных, а функторов — в виде (полиморфных) функций, специализация функторов для всех применений в духе C++ templates и полное стирание модулей во время компиляции (аналогично девиртуализации вызовов методов в ООП). Но за деталями интересующиеся читатели отсылаются к соответствующим публикациям.
В заключительной части Леруа обсуждает ряд расширений модельной системы модулей — как реализованных на практике, так и не до конца проработанных даже в теории — но уже без фактической реализации.
Таким образом, статья представляет собой практическое введение в ML-style системы модулей и связанные вопросы, полезное как для пользователей таких систем, так и для авторов языков программирования, желающих реализовать собственную систему модулей. 😊
#modules #sml #ocaml #leroy #classic
"A modular module system", Xavier Leroy
Утверждение, что (ML-style) система модулей не зависит от "базового" языка программирования, и может быть реализована почти для любого, а не только ML, широко известно и озвучивалось в литературе. Данная статья приводит конструктивное доказательство этого тезиса, реализуя такую (слегка упрощённую) систему модулей, в виде, явно параметризованном относительно синтаксиса и системы типов базового языка.
Несмотря на ряд упрощений по сравнению с системой модулей того же Standard ML, представленная модельная система содержит (и корректно реализует) все базовые возможности, включая структурную типизацию модулей, абстрактные типы, функторы, зависимость (типа) результата функтора от (типа) аргумента а также равенства между (абстрактными) типами.
> All in all, module type matching resembles subtyping in a functional language with records, with some extra complications due to the dependencies in functor types and signatures.
Статья составлена в духе Literate Programming, перемежая пояснительный текст и реальный рабочий код на языке OCaml. Реализация системы модулей ML с помощью системы модулей ML отсылает к традиции метациркулярных интерпретаторов Лисп. Леруа выражает надежду, что такой способ представления материала не только не запутает читателя, но и дополнительно прояснит связь конкретного и абстрактного синтаксиса как и практическую полезность (и даже необходимость) всех возможностей представленной системы. (По-видимому, метациркулярность системы не оставила Лисперов равнодушными, что привело к появлению реализации MiniML с полноценной системой модулей на Scheme: http://wiki.call-cc.org/eggref/4/miniML 😊)
Для иллюстрации приводятся два примера "надстраивания" реализованной системы модулей над "упрощённым C" в качестве императивного (процедурного) базового языка и Mini-ML в качестве функционального, приближенного к используемым на практике, в частности, реализующего типы высших порядков (Higher-Kinded Types).
Кратко обсуждаются вопросы (модульной) компиляции таких модулей. Упоминаются три основных варианта: компиляция самих модулей в виде структур данных, а функторов — в виде (полиморфных) функций, специализация функторов для всех применений в духе C++ templates и полное стирание модулей во время компиляции (аналогично девиртуализации вызовов методов в ООП). Но за деталями интересующиеся читатели отсылаются к соответствующим публикациям.
В заключительной части Леруа обсуждает ряд расширений модельной системы модулей — как реализованных на практике, так и не до конца проработанных даже в теории — но уже без фактической реализации.
Таким образом, статья представляет собой практическое введение в ML-style системы модулей и связанные вопросы, полезное как для пользователей таких систем, так и для авторов языков программирования, желающих реализовать собственную систему модулей. 😊
#modules #sml #ocaml #leroy #classic
В традиционных алгоритмах распределения регистров на основе задач упаковки в контейнеры или раскраски графов трудно учесть дополнительные ограничения на доступ к регистрам.
Речь идет об архитектурах с нерегулярным доступом к регистрам (register aliasing, ограничения на использование конкретных регистров в командах). И это относится к x86, но в еще большей мере — к DSP-процессорам и другим специализированным архитектурам.
За последние 3 десятилетия исследователи предложили несколько подходов к проблеме, в том числе метод на базе задачи о квадратичном присваивании (quadratic assignment problem, или QAP), верней частном ее случае: partitioned boolean quadratic optimization problem, или PBQP.
Бернард Шольц (Bernhard Scholz) в работе 2002 года сформулировал распределение регистров как задачу PBQP и показал, что метод позволяет моделировать особенности сложных архитектур. PBQP - NP-полная задача, поэтому впоследствии для метода были разработаны эффективные эвристики, делающие время поиска решений приемлемым.
Интересным метод является не только из-за применимости к отдельным архитектурам:
- возможно регулировать время работы решателя, то есть алгоритм становится прогрессивным;
- решатель может, применяя или не применяя эвристику, находить субоптимальные или оптимальные решения;
- алгоритм пытается избегать применения эвристики и в большинстве случаев находит оптимальные решения.
Наилучшие относительно других подходов результаты PBQP показывает именно в нерегулярных архитектурах, ради которых решатель PBQP был реализован сначала в libfirm, после - и в LLVM.
Впоследствии исследования применимости PBQP в распределении регистров и порождении кода вдохновили эксперименты в применении метода, например, к тестированию памяти или методам машинного обучения.
Понятия регулярности и ортогональности архитектур процессоров в классической работе (1981): https://www.cs.auckland.ac.nz/compsci703s1c/resources/Wulf.pdf
Оригинальная публикация, представляющая PBQP (2002): http://www.complang.tuwien.ac.at/scholz/publications/lctes02.ps.gz
Развитие идей, обновленный алгоритм и новая эвристика (2006): https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.131.4551&rep=rep1&type=pdf
Разработчики libfirm о применении к SSA (2011): https://link.springer.com/content/pdf/10.1007/978-3-642-19861-8_4.pdf
Неформальный пост от разработчиков libfirm (2011): https://beza1e1.tuxen.de/articles/pbqp.html
Сама задача: https://en.wikipedia.org/wiki/Quadratic_assignment_problem
Тестирование памяти (2020): https://dl.acm.org/doi/fullHtml/10.1145/3427378
Машинное обучение (2018): https://arxiv.org/pdf/1710.01079.pdf
#pbqp #registeralloc #libfirm #llvm
Речь идет об архитектурах с нерегулярным доступом к регистрам (register aliasing, ограничения на использование конкретных регистров в командах). И это относится к x86, но в еще большей мере — к DSP-процессорам и другим специализированным архитектурам.
За последние 3 десятилетия исследователи предложили несколько подходов к проблеме, в том числе метод на базе задачи о квадратичном присваивании (quadratic assignment problem, или QAP), верней частном ее случае: partitioned boolean quadratic optimization problem, или PBQP.
Бернард Шольц (Bernhard Scholz) в работе 2002 года сформулировал распределение регистров как задачу PBQP и показал, что метод позволяет моделировать особенности сложных архитектур. PBQP - NP-полная задача, поэтому впоследствии для метода были разработаны эффективные эвристики, делающие время поиска решений приемлемым.
Интересным метод является не только из-за применимости к отдельным архитектурам:
- возможно регулировать время работы решателя, то есть алгоритм становится прогрессивным;
- решатель может, применяя или не применяя эвристику, находить субоптимальные или оптимальные решения;
- алгоритм пытается избегать применения эвристики и в большинстве случаев находит оптимальные решения.
Наилучшие относительно других подходов результаты PBQP показывает именно в нерегулярных архитектурах, ради которых решатель PBQP был реализован сначала в libfirm, после - и в LLVM.
Впоследствии исследования применимости PBQP в распределении регистров и порождении кода вдохновили эксперименты в применении метода, например, к тестированию памяти или методам машинного обучения.
Понятия регулярности и ортогональности архитектур процессоров в классической работе (1981): https://www.cs.auckland.ac.nz/compsci703s1c/resources/Wulf.pdf
Оригинальная публикация, представляющая PBQP (2002): http://www.complang.tuwien.ac.at/scholz/publications/lctes02.ps.gz
Развитие идей, обновленный алгоритм и новая эвристика (2006): https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.131.4551&rep=rep1&type=pdf
Разработчики libfirm о применении к SSA (2011): https://link.springer.com/content/pdf/10.1007/978-3-642-19861-8_4.pdf
Неформальный пост от разработчиков libfirm (2011): https://beza1e1.tuxen.de/articles/pbqp.html
Сама задача: https://en.wikipedia.org/wiki/Quadratic_assignment_problem
Тестирование памяти (2020): https://dl.acm.org/doi/fullHtml/10.1145/3427378
Машинное обучение (2018): https://arxiv.org/pdf/1710.01079.pdf
#pbqp #registeralloc #libfirm #llvm
👍1
Уильям Вульф (William Wulf) - исследователь в области компиляторов, сотрудничавший со знаменитой компанией DEC. Вульф - создатель раннего оптимизирующего компилятора языка BLISS и один из авторов классической книги The Design of an Optimizing Compiler (1975).
После работы над BLISS команда Вульфа переключилась на амбициозный проект PQCC (Production-Quality Compiler-Compiler Project), в рамках которого шла работа над универсальным компилятором компиляторов, целью которого было порождение всех этапов компилятора для новых архитектур из декларативных описаний - актуальной проблемы для DEC, продававшей разнородные платформы (семейства PDP и VAX, позже - Alpha).
Статья Compilers and Computer Architecture (1981) - выводы из этой работы. В ней Вульф указывает, что экономику разработки новых архитектур нельзя рассматривать без стоимости разработки сопутствующего компилятора. То есть дизайн набор инструкций нельзя создавать без учета будущих компиляторов.
Исходя из этих наблюдений Вульф предлагает принципы разработки компьютерных архитектур общего назначения:
1. Регулярность (regularity) - должен быть один способ делать что-либо, и он должен быть применим везде (например, ADD работает для всех регистров и типов данных).
2. Ортогональность (orthogonality) - аспекты архитектуры должны обсуждаться независимо, без взаимного влияния (режим адресации, к примеру, не должен влиять на выбор примитивов).
3. Композиционность (composability) - в регулярной и ортогональной архитектуре можно соединить различные аспекты произвольным образом (каждая из инструкций поддерживает работы с любым регистром и режимом адресации).
От базовых принципов статья переходит к принципам-следствиям: вопросам адресации, выбора примитивов, отклонения от принципов. Интересный вывод касается поддержки примитивов, специфичных для конкретных языков высокого уровня: "In many cases these turn out to be more trouble than they are worth".
Это очень интересная и по-прежнему актуальная статья от одного из известнейших специалистов по компиляторам своей эпохи. Пересказывать ее полностью нет смысла, остается только рекомендовать интересующимся темой компьютерных архитектур и неотделимой от нее темой разработки компиляторов.
Compilers and Computer Architecture (1981) - статья
https://en.wikipedia.org/wiki/William_Wulf - автор
https://en.wikipedia.org/wiki/BLISS - известнейшая работа автора
https://en.wikipedia.org/wiki/The_Design_of_an_Optimizing_Compiler - классическая книга автора
#bliss #pqcc #architecture #isa #history
После работы над BLISS команда Вульфа переключилась на амбициозный проект PQCC (Production-Quality Compiler-Compiler Project), в рамках которого шла работа над универсальным компилятором компиляторов, целью которого было порождение всех этапов компилятора для новых архитектур из декларативных описаний - актуальной проблемы для DEC, продававшей разнородные платформы (семейства PDP и VAX, позже - Alpha).
Статья Compilers and Computer Architecture (1981) - выводы из этой работы. В ней Вульф указывает, что экономику разработки новых архитектур нельзя рассматривать без стоимости разработки сопутствующего компилятора. То есть дизайн набор инструкций нельзя создавать без учета будущих компиляторов.
Исходя из этих наблюдений Вульф предлагает принципы разработки компьютерных архитектур общего назначения:
1. Регулярность (regularity) - должен быть один способ делать что-либо, и он должен быть применим везде (например, ADD работает для всех регистров и типов данных).
2. Ортогональность (orthogonality) - аспекты архитектуры должны обсуждаться независимо, без взаимного влияния (режим адресации, к примеру, не должен влиять на выбор примитивов).
3. Композиционность (composability) - в регулярной и ортогональной архитектуре можно соединить различные аспекты произвольным образом (каждая из инструкций поддерживает работы с любым регистром и режимом адресации).
От базовых принципов статья переходит к принципам-следствиям: вопросам адресации, выбора примитивов, отклонения от принципов. Интересный вывод касается поддержки примитивов, специфичных для конкретных языков высокого уровня: "In many cases these turn out to be more trouble than they are worth".
Это очень интересная и по-прежнему актуальная статья от одного из известнейших специалистов по компиляторам своей эпохи. Пересказывать ее полностью нет смысла, остается только рекомендовать интересующимся темой компьютерных архитектур и неотделимой от нее темой разработки компиляторов.
Compilers and Computer Architecture (1981) - статья
https://en.wikipedia.org/wiki/William_Wulf - автор
https://en.wikipedia.org/wiki/BLISS - известнейшая работа автора
https://en.wikipedia.org/wiki/The_Design_of_an_Optimizing_Compiler - классическая книга автора
#bliss #pqcc #architecture #isa #history
Представленный в 1969 году компилятор Fortran-H применял множество прежде трудных оптимизаций. Ключом к ним стала новаторская техника статического анализа: использование доминаторов узлов графа потока исполнения програмы.
Доминатором заданного узла называют такой узел, через который проходят все пути от входного узла к заданному. Непосредственные (то есть ближайшие к каждому из узлов) доминаторы образуют дерево доминаторов с корнем во входном узле графа.
Fortran-H показал, что в сочетании с анализом потоков данных отношение доминирования позволяет расширить до глобальной область применения локальных оптимизаций. К примеру, при помощи доминаторов проводилось удаление общих подвыражений: если среди доминаторов текущего узла уже вычислялось какое-либо выражение и ни один из операндов на пути к узлу не менялся, то результат выражения можно не вычислять повторно.
Одной из проблем использованного в Fortran-H метода поиска доминаторов стала высокая алгоритмическая сложность. Алгоритм Пурдома-Мура (Purdom-Moore, по именам разработчиков компилятора) элементарно объясняется и реализуется, но имеет квадратичную сложность.
Более эффективная версия алгоритма сложностью в O(m*log n) будет представлена только через 10 лет в статье 1979 года A Fast Algorithm for Finding Dominators in a Flowgraph за авторством Томаса Ленгауэра (Thomas Lengauer) и Роберта Тарьяна (Robert Tarjan).
Несмотря на наличие эффективного алгоритма доминаторы широко не использовались, пока в знаменитой публикации 1989 года (Efficiently Computing Static Single Assignment Form and the Control Dependence Graph) доминаторы не были использованы для размещения phi-узлов при построении SSA.
На волне обновленного интереса были предложены новые применения доминаторов: глобальная нумерация значений, глобальное планирование инструкций и прочие. Исследователи стали предлагать альтернативные алгоритмы поиска доминаторов, которые, впрочем, широкого распространения не получили, а алгоритм Ленгауэра-Тарьяна (или просто ЛТ) до сих пор широко используется, в том числе в GCC и LLVM.
https://en.wikipedia.org/wiki/Dominator_(graph_theory)
https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf - алгоритм Ленгауэра-Тарьяна (1979)
https://www.researchgate.net/profile/Edward-Lowry/publication/220421196_Object_code_optimization/links/564ca77708aedda4c13432b4/Object-code-optimization.pdf - описание реализации Fortran-H (1969), где впервые формулируется алгоритм Пурдома-Мура.
http://pages.cs.wisc.edu/~fischer/cs701.f08/ssa.pdf - получение SSA (1989)
https://www.doc.ic.ac.uk/~livshits/classes/CO444H/reading/dom14.pdf - предложение Купера по получению доминаторов путем анализа потоков данных (2001)
https://github.com/gcc-mirror/gcc/blob/master/gcc/dominance.c - реализация алгоритма ЛТ в GCC
#dominator #lengauertarjan #fortranh #llvm #gcc
Доминатором заданного узла называют такой узел, через который проходят все пути от входного узла к заданному. Непосредственные (то есть ближайшие к каждому из узлов) доминаторы образуют дерево доминаторов с корнем во входном узле графа.
Fortran-H показал, что в сочетании с анализом потоков данных отношение доминирования позволяет расширить до глобальной область применения локальных оптимизаций. К примеру, при помощи доминаторов проводилось удаление общих подвыражений: если среди доминаторов текущего узла уже вычислялось какое-либо выражение и ни один из операндов на пути к узлу не менялся, то результат выражения можно не вычислять повторно.
Одной из проблем использованного в Fortran-H метода поиска доминаторов стала высокая алгоритмическая сложность. Алгоритм Пурдома-Мура (Purdom-Moore, по именам разработчиков компилятора) элементарно объясняется и реализуется, но имеет квадратичную сложность.
Более эффективная версия алгоритма сложностью в O(m*log n) будет представлена только через 10 лет в статье 1979 года A Fast Algorithm for Finding Dominators in a Flowgraph за авторством Томаса Ленгауэра (Thomas Lengauer) и Роберта Тарьяна (Robert Tarjan).
Несмотря на наличие эффективного алгоритма доминаторы широко не использовались, пока в знаменитой публикации 1989 года (Efficiently Computing Static Single Assignment Form and the Control Dependence Graph) доминаторы не были использованы для размещения phi-узлов при построении SSA.
На волне обновленного интереса были предложены новые применения доминаторов: глобальная нумерация значений, глобальное планирование инструкций и прочие. Исследователи стали предлагать альтернативные алгоритмы поиска доминаторов, которые, впрочем, широкого распространения не получили, а алгоритм Ленгауэра-Тарьяна (или просто ЛТ) до сих пор широко используется, в том числе в GCC и LLVM.
https://en.wikipedia.org/wiki/Dominator_(graph_theory)
https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf - алгоритм Ленгауэра-Тарьяна (1979)
https://www.researchgate.net/profile/Edward-Lowry/publication/220421196_Object_code_optimization/links/564ca77708aedda4c13432b4/Object-code-optimization.pdf - описание реализации Fortran-H (1969), где впервые формулируется алгоритм Пурдома-Мура.
http://pages.cs.wisc.edu/~fischer/cs701.f08/ssa.pdf - получение SSA (1989)
https://www.doc.ic.ac.uk/~livshits/classes/CO444H/reading/dom14.pdf - предложение Купера по получению доминаторов путем анализа потоков данных (2001)
https://github.com/gcc-mirror/gcc/blob/master/gcc/dominance.c - реализация алгоритма ЛТ в GCC
#dominator #lengauertarjan #fortranh #llvm #gcc
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, в котором конструкции захвата подвыражения и связывания его с именем могут находиться внутри звезды Клини. Но в таком случае эти имена связываются не с одним подвыражением, а со всем подсписком внутри списка выражений, порождённого звездой Клини. Например, в выражении
По сравнению со стандартным связыванием имён в функциях или
Вторая причина связана с тем, что авторы называют "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
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
👍2
Некоторые идеи опережают свою эпоху на десятилетия. Автор данной заметки к оным безусловно относит систему 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
Автор всего на 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
👍5
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), производительность не уступает, а в некоторых случаях и превосходит традиционную реализацию, которую невозможно переиспользовать.
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), производительность не уступает, а в некоторых случаях и превосходит традиционную реализацию, которую невозможно переиспользовать.
👍8