17/12/2020, Peter Sovietov¶
Работа 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].
- Язык AbleC (расширение C11): http://melt.cs.umn.edu/ableC/
26/05/2020, Peter Sovietov¶
Halide — яркий пример современного и популярного DSL для высокопроизводительных вычислений (обработка изображений, нейросети). В работе по ссылке ниже представлена его формальная семантика. Достаточная, по большому счету, для разработки собственного компилятора Halide. Любопытно, что в описании трансляции в императивное представление использован формализм из области синтеза программ. Formal Semantics for the Halide Language https://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-40.pdf
11/05/2020¶
CBS — система для описания компонентной спецификации ЯП. В каком-то смысле это аналог LLVM для формальной семантики. Идея в том, чтобы транслировать ЯП в элементарные, строго определенные конструкции, называемые funcons. https://plancomps.github.io/CBS-beta/