PLComp

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), производительность не уступает, а в некоторых случаях и превосходит традиционную реализацию, которую невозможно переиспользовать.

www.tgoop.com/plcomp/80

1.3K viewsAlexander Chichigin, May 21, 2021 at 07:21

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), производительность не уступает, а в некоторых случаях и превосходит традиционную реализацию, которую невозможно переиспользовать.

BY PLComp