# 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". А нумерация начинается слева направо.
Правда, такой подход приведет к "засорению" кода дополнительными инструкциями генерации пути узла при обходе дерева.
А нужна функция которая по заданному выражению и пути выдает нужный узел (поддерево).
Нужно пробовать!