Преобразование условий в присваивания

[Mazdaywik]

Мотивация

Оптимизация программ, написанных на классическом Рефале-5. В классическом Рефале нет такой конструкции, как «присваивание», но потребность в ней есть. Поэтому часто в роли присваивания используют условие.

Вариант приемлемый, но имеет важный недостаток — быстродействие. Условие подразумевает возможность отката, т.е. перехода к следующему предложению или к следующему варианту сопоставления аргумента с образцом. В классической списковой реализации для этого требуется сохранять список аргумента функции в неизменности, т.е. переменные в выражении условия всегда должны копироваться.

Но бывают условия, откат в которых невозможен. Это или условия, которые всегда сопоставляются успешно, или условия, откатываться в которых дальше некуда.

Условия, которые всегда успешны — условия вида , Res : e.X, где e.X — несвязанная переменная. В общем случае в правой части может находиться не e-переменная, а жёсткое выражение того же формата, что и Res. Но выводить форматы компилятор пока не умеет — это пока слишком большая и объёмная задача.

Чтобы можно было заменить такое условие на присваивание, оно должно располагаться слева от =, который может либо начинать присваивание, либо конечное результатное выражение предложения.

Однако, такие условия нельзя заменять на присваивания, если справа от него не =, а другое условие. Условие справа может породить неуспех, который должен быть передан дальше налево — вставка = вместо , изменит семантику программы.

Условия, когда откатываться некуда. Неуспех в условии может либо перехватываться неоднозначным образцом слева (пробуется следующая подстановка), либо следующим предложением. Таким образом, откатываться некуда только если условие находится при однозначном образце последнего предложения. Частный случай последнего предложения — условие при присваивании.

Более тонкий вариант — если предложение не последнее, однако последующие образцы перестановочны с образцом перед условием. Формально откат возможен на следующие предложения, но они в принципе не смогут перехватить неуспех.

Реализация

Предлагается распознавать описанные выше условия на этапе рассахаривания, заменяя их на присваивания. Распознавание однозначного образца можно упростить — если на одном скобочном уровне нет двух e-переменных — образец является однозначным. Случаи однозначных образцов вида (e.A e.B) (e.B e.C) e.C предлагается оставить за рамками рассмотрения, т.к. они сравнительно редки на практике (реже образцов с открытыми переменными). Однако, можно воспользоваться анализом образца из рассахаривателя условий — его алгоритм предназначен для выявления открытых переменных и для него можно написать обёртку, возвращающую двоичный признак: однозначен или нет.

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

Альтернативные реализации

Существует компилятор классического Рефала-5 crefal, который умеет делать подобные оптимизации:

Cборник трудов по функциональному языку программирования Рефал. Том №2. Переславль-Залесский: Изд-во "Сборник", 2015, ISBN 978-5-9905410-2-3, - 156 с. http://refal.botik.ru/library/refal2015_issue-II.pdf (стр. 53)

[Mazdaywik]

Если разобраться, то задача очень простая. Особенно, выявление условий , Res : e.X перед присваиваниями или результатом. Единственная тонкость — выявление того, что переменная новая (неповторная).

Впрочем, преобразование условий в последних предложениях или перед присваиваниями тоже просто.

[Mazdaywik]

@dynamic-pie, эта задача добавлена к Вашей ВКР в дополнение к #248.

[Mazdaywik]

@dynamic-pie ушёл к другому научному руководителю. Тема на ВКР не выбрана.