Информация об изменениях

Сообщение Re[7]: Простые, но эффективные реализации компиляторов от 24.07.2024 11:28

Изменено 28.07.2024 14:45 Sinclair

Старый текст
Новый текст
Разница

Re[7]: Простые, но эффективные реализации компиляторов

Здравствуйте, cppguard, Вы писали:

C>Блок с выражениями типа "a = b" испольняется один раз, блок с выражениями типа "a : a + b" исполняется столько раз, сколько есть итераций. Каждый из них не зависит от другого, поэтому оба можно генерировать независимо.
Ну и прекрасно. Так и пишем:

function generateCode(ast, targetBuilder)
{
   generateInitBlock(ast, targetBuilder)
   generateIterationBlock(ast, targetBuilder);
}

function generateInitBlock(ast, targetBuilder)
{
   let initExpressions = getInitExpressions(ast);
   for(var initExpression of initExpressions)
     generate(initExpression, targetBuilder);
}

const getInitExpressions = (ast) => ast.expressions.filter(e => isInitExpression(e));
const getIterExpressions = (ast) => ast.expressions.filter(e => isIterExpression(e));


function generateIterationBlock(ast, targetBuilder)
{
   let iterationExpressions = getIterationExpressions(ast);
   generateIterationCycle(targetBuilder, header = ..., body = (b) => generateSingleIteration(iterationExpressions, targetBuilder);
}

S>>Выглядит как-то сложно. Блоки нужно генерировать тогда, когда уже есть все нужные данные.
S>>1. Построили полный список ячеек.
S>>2. Построили граф зависимостей.
S>>3. Отсортировали ячейки в соответствии с топологией зависимостей (тут я немного плаваю, но, судя по всему, вы уже решили эту задачу)
S>>4. Породили адреса для каждой ячейки
S>>5. Сгенерировали код.

C>Вот контрпример:
C>

C>b = 1
C>a = b
C>b : a + b
C>

C>Если не разделять шаг инициализации и шаг итерации, то получается циклическая зависимость и простой топологической сортировкой задача не решается, нужно обрабатывать блоки "=" и ":" отдельно.
Эмм, ну значит надо разделять шаг инициализации и итерации. Не вижу в этом ничего особенного.
Для начала можно это делать "на ходу", как в примере выше, где каждый раз, как нам нужны "только init" или "только iter", мы бежим по списку и выполняем фильтрацию.
Если окажется, что фильтры по ходу компиляции отрабатывают многократно, то можно это соптимизировать, поменяв форму дерева.
Вначале у нас было "дерево" вида
{
expressions: AnyExpression[] // AnyExpression = InitExpression | IterExpression
}
Берём и преобразуем его к виду

{ 
  initExpressions: InitExpression[],
  iterExpressions: IterExpression[]
}

Можно это делать при помощи двукратного вызова фильтра. А можно — за один проход:

const splitAst = fold(ast, { initExpressions:[], iterExpressions:[] }, 
  (sa, expr) => expr is InitExpression 
    ? { [...sa.initExpressions, expr], sa.iterExpressions}
    : { sa.initExpressions, [...sa.iterExpressions, expr]})
}

И дальше уже пользуемся готовыми массивами.
Оптимизировать инициализацию не надо, т.к. она в любом случае исполняется один раз. Так что при выборе порядка размещения ячеек надо анализировать только граф зависимостей в iter-части.

C>Да, в этом и основная суть DSL. Только с "=" такое не прокатит, потому что это выражение для инициализации. А итеративное вычисление задаётся в виде "a : a + b".
То есть порядок вычисления выражений внутри итерации семантически не важен, т.к. справа в любом случае берутся "старые" значения?

Re[7]: Простые, но эффективные реализации компиляторов

function generateCode(ast, targetBuilder)
{
   generateInitBlock(ast, targetBuilder)
   generateIterationBlock(ast, targetBuilder);
}

function generateInitBlock(ast, targetBuilder)
{
   let initExpressions = getInitExpressions(ast);
   for(var initExpression of initExpressions)
     generate(initExpression, targetBuilder);
}

const getInitExpressions = (ast) => ast.expressions.filter(e => isInitExpression(e));
const getIterExpressions = (ast) => ast.expressions.filter(e => isIterExpression(e));


function generateIterationBlock(ast, targetBuilder)
{
   let iterationExpressions = getIterationExpressions(ast);
   generateIterationCycle(targetBuilder, header = ..., body = (b) => generateSingleIteration(iterationExpressions, targetBuilder);
}

C>b = 1
C>a = b
C>b : a + b
C>

{ 
  expressions: AnyExpression[] // AnyExpression = InitExpression | IterExpression
}

Берём и преобразуем его к виду

{ 
  initExpressions: InitExpression[],
  iterExpressions: IterExpression[]
}

Можно это делать при помощи двукратного вызова фильтра. А можно — за один проход:

const splitAst = fold(ast, { initExpressions:[], iterExpressions:[] }, 
  (sa, expr) => expr is InitExpression 
    ? { [...sa.initExpressions, expr], sa.iterExpressions}
    : { sa.initExpressions, [...sa.iterExpressions, expr]})
}