BUGS list

Reductor

Код модифицируется корректно, но не реализована модификация списка переменных

Graph coloring with DSATUR

Похоже сейчас алгоритм раскраски графа работает корректно.

Структура программы для аллокации переменных

Мне не нравится как предлагается сделать аллокацию переменных: сначала сделали только на стеке, а потом предложили сделать и на регистрах. А если можно (и нужно) и на регистры и на стек?

Но в целом ведь аллокация разделяется на 2 фазы:

1. Анализ программы, определение количества необходимых ячеек памяти по времени жизни переменных

   allocate (var list, stmt list) --> <(var, address) list>

2. И собственно замена по всей программе ссылок на переменную на ссылке по адресу или обращение к регистру

   replace_vars ((var, address) list, stmt list) --> ((var, address) list, stmt' list)

Вот исходя из этого и нужно строить функции аллокации. Но, как же смешивать разные методы аллокации? Может быть лучше такой цепочкой:

`prepare_alloc (var list) --> <(var, address) list> --> 'allocate_on_reg' --> 'allocate_on_stack' --> <(var, address) list>`

Однако разные функции аллокации могут нуждаться в различных дополнительных параметрах...

Аллокация переменных

Прежде всего нужно пройтись по программе и удалить неиспользуемые переменные! Это можно сделать методом от обратного - пройтись по АСт и выбрать только те переменные к которым есть обращение.

Аллокация регистров с помощью раскраски графа

Что-то не так, на выходе получается код который сводится к паре инструкций. Если раскраска графа корректная,значит неправильно применяю граф зависимостей.

Пока оставлю как есть...

Я не правильно применяю аллокацию на регистрах: нужно это делать только на промежуточные переменные! Иначе действительно программа "закупоривается".

Partial evaluator

Код получается сложным, а я сделал только две математические операции. Может быть попробовать преобразовывать АСТ выражения в список команд стековой машины?

  (x - a) + b ==> [(+, x); (-, a); (+, b)]

А упрощение проводить просто беря попарно элементы списка и вычисляя константы? Работает только для сложения.вычитания

Правила преобразования (в скобках - поддерево выражения)

  (x - b) * c == c * (x - b) == (x * c) - {b * c}
  (b - x) * c == c * (b - x) == {c * b} - (x * c)
  (x + a) - b == x + {a - b}
  (a - x) + b == {a + b} - x

  где x,y - не константы; a,b,c - константы; в скобках - подвыражения; в фигурных скобках - вычисляемая константа

Правил может быть много, их лучше записывать в виде конкретной функции. Тогда как правильно применять множество таких функций? Наверно функция должна быть такой transformation:: <Expression> -> <Expression> option

Например, есть преобразование которое выносит константы в отдельное подвыражение:

  (x - b) + c => x - (b + c)
  (b - x) + c => (b + c) - x
  (x - b) - c => x - (b + c)
  (b - x) - c => (b - c) - x     

  (x + b) + c => x + (b + c)
  (x + b) - c => x + (b - c)
  (b + x) + c => (b + c) + x
  (b + x) - c => (b - c) + x

  (x + a) * b => (x * b) + (a * b) 
  (x - a) * b => (x * b) - (a * b)
  (x * a) * b => x * (a * b)
  (x / a) * b => x * (b / a)

  (x + a) / b => (x / b) + (a / b) => c * x + d
  (x - a) / b => (x / b) - (a / b) => c * x - d
  (x * a) / b => x * (a / b)
  (x / a) / b => x * (b / a)

  a / (x + b) => ---
  a / (x - b) => ---
  a / (x * b) => (a / b) / x
  a / (x / b) => (a * b) / x

  x / a => {1 / a} * x // может использоваться для ускорения вычислений, так как деления всегда медленее умножения

  (x / y) * y => x
  - (- x) => x

  (x / 1) => x
  (x / x) => 1
  (x * 1) => x
  (x * 0) => 0
  (x + 0) => x
  (x - 0) => x
  (0 - x) => -x

И есть преобразование которое вычисляет константные выражения.

Порядок применения этих преобразований имеет значение. Хотя тут тоже можно навязать форму:

• сначала применяются все трансформации
• а потом происходит вычисление константных выражений

Преобразования должны идти "снизу" АСД к корню.

Рабочий алгоритм оказался такой. Используя рекурсию,

• применяем все известные редукторы к заданному узлу
• в зависимости от узла рекурсивно обходим подвыражения узла
• и снова применяем все редукторы к вновь созданному узлу

Errors handling

Я не понимаю как сделать удобно сделать обработку ошибок. И не понимаю какую стратегию выбрать. Варианты стратегий:

• Генерировать текст с описанием ошибки, и выкидывать исключения
• Генерировать текст с описанием ошибки, и использовать ROP
• Генерировать специальную структуру которую потом можно обрабатывать

И в любых вариантах неясно как адресовать место ошибки... Вот например такой текст программы:

  (let (x 0) (if (x) (0) (1)))

Как указать что в условии применяется переменная ошибочного типа? А Если там будет вложение с перекрывающимся переменными:

  (let (x #t) (if (x) ((let (x 0) (if (x) (0) (1)))) (1)))

Конечно удобно если есть двумерный текст, а если его нет? Как задать координаты узла дерева?

Можно указывать номер под-узла начиная от корневого: "1.2.1.1.1.2". А нумерация начинается слева направо.

Правда, такой подход приведет к "засорению" кода дополнительными инструкциями генерации пути узла при обходе дерева. А нужна функция которая по заданному выражению и пути выдает нужный узел (поддерево).

Нужно пробовать!

Uniquify

Надо понять и переделать процедуру переименования на уникальные имена. Мне не ясно как обрабатывать вот такой код:

1:  (let ([x (let ([x 0]) x)]) x)

2:  (let ([x (let ([x 0] x)]) (if (let ([x 0]) x) (x) (let ([x 0]) x)))

Правильно ли транслировать вот так:

1U:  (let ([t1 (let ([t2 0]) t2)]) t1)

2U:  (let ([t1 (let ([t2 0] t2)]) (if (let ([t3 0]) t3) (t1) (let ([t4 0]) t4)))

Да, получается так.

Реализация, должна учитывать область определения, но в то же время сисок переменных глобален. Вот допустим есть такое выражение:

1:  (let ([x 0]) (let ([y 0]) (let ([z 0]) y)))
2:  (let ([x (let ([y 0]) y)]) y) -- здесь ошибка: обращение с переменной которая не видна из текущего пространства имен

Пример 2 показывает, что при плоском глобальном списке переменных возможна ситуация когда возможно обращение к переменной из другого пространства имен. Однако, если использовать стэк, то можно решить эту проблему. Или нет?

  (let ([x -- объявление переменной -- ((x . ?))
        (let ([y 0]) y) -- вложенное обяъвление -- ((y . ?) (x . ?))
        ]) -- вложенное объявление закрыто -- ((x . ?))
        y) -- а вот теперь использование переменной невозможно: нет объявленной переменной

Ну тогда получается что нужно два списка переменных: первый для проверки области видимости, второй для отображение имен переменных

  (let ([x -- объявление переменной -- ((t1 . x)) ++ ()
           (let ([y 0]) y) -- вложенное обяъвление -- ((t2 . y) (t1 . x)) ++ ()
        ]) -- вложенное объявление закрыто -- ((t1 . x)) ++ ((t2 .y))
        y) -- а вот теперь использование переменной невозможно: нет объявленной переменной
           -- объявление закрыто -- () ((t2 . y) (t1 . x))