bmstu-iu9 / bmstu-iu9/refal-5-lambda
Древесные оптимизации раздувают программы
- Dominant language
- C++
- Stars
- 97
- Forks
- 40
- PR merge metrics
- No merged PRs in 30d
Description
Проблема
=======
Опыт самоприменения с глубокими оптимизациями (`-OA` + древесные) показал, что компилятор склонен раздувать программы (много примеров в #319, в свёрнутых комментариях). Программы раздуваются по двум причинам:
* прогонка может мультипликативно увеличить количество предложений,
* специализация может строить огромное количество переспециализированных экземпляров.
Под переспециализированными экземплярами мы понимаем избыточное количество экземпляров, которые не способствуют каким-либо интересным нетривиальным преобразованиям. Как правило, это специализации по каким-либо аккумуляторным переменным.
Сейчас эта проблема решается ручным анализом причины каждого очередного распухания и купированием его ad hoc (много примеров — коммиты к #319, предлагается даже специальный инструмент для купирования — #331). Но это не дело.
Ожидаемое поведение
===============
Компилятор не должен существенно раздувать программу, раздутие в общем случае должно быть умеренным, не более чем в 10 раз. Но при этом допускать интересные преобразования вроде специализации (в широком смысле) простых интерпретаторов (вроде [скрипта древесных оптимизаций](https://github.com/bmstu-iu9/refal-5-lambda/blob/672af493555673016affb2eaa932cfec1b3555c0/src/compiler/OptTree.ref#L188-L307)).
Понятно, что обеспечить эту численную характеристику (×10) для нетривиальных символьных преобразований нельзя, речь идёт о том, что на наборе типичных программ (сам Рефал-5λ без ручных разметок, MSCP-A, SCP4, другие, которые найдутся) **среднее раздутие (размер RASL’а) должно быть не более, чем на порядок, чем при компиляции без древесных оптимизаций.**
Но при этом возможность интересных преобразований должна допускаться.
С точки зрения математики обе цели противоречивы: допускать нетривиальные преобразования и ограничивать объём преобразованной программы. Это, вроде как, следует из теоремы Райса-Успенского. Но с точки зрения практики можно найти приемлемый компромисс, когда можно писать и специализируемые интерпретаторы, и программы распухают не сильно.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.