Древесные оптимизации раздувают программы #332
Description
Проблема
Опыт самоприменения с глубокими оптимизациями (-OA + древесные) показал, что компилятор склонен раздувать программы (много примеров в #319, в свёрнутых комментариях). Программы раздуваются по двум причинам:
- прогонка может мультипликативно увеличить количество предложений,
- специализация может строить огромное количество переспециализированных экземпляров.
Под переспециализированными экземплярами мы понимаем избыточное количество экземпляров, которые не способствуют каким-либо интересным нетривиальным преобразованиям. Как правило, это специализации по каким-либо аккумуляторным переменным.
Сейчас эта проблема решается ручным анализом причины каждого очередного распухания и купированием его ad hoc (много примеров — коммиты к #319, предлагается даже специальный инструмент для купирования — #331). Но это не дело.
Ожидаемое поведение
Компилятор не должен существенно раздувать программу, раздутие в общем случае должно быть умеренным, не более чем в 10 раз. Но при этом допускать интересные преобразования вроде специализации (в широком смысле) простых интерпретаторов (вроде скрипта древесных оптимизаций).
Понятно, что обеспечить эту численную характеристику (×10) для нетривиальных символьных преобразований нельзя, речь идёт о том, что на наборе типичных программ (сам Рефал-5λ без ручных разметок, MSCP-A, SCP4, другие, которые найдутся) среднее раздутие (размер RASL’а) должно быть не более, чем на порядок, чем при компиляции без древесных оптимизаций.
Но при этом возможность интересных преобразований должна допускаться.
С точки зрения математики обе цели противоречивы: допускать нетривиальные преобразования и ограничивать объём преобразованной программы. Это, вроде как, следует из теоремы Райса-Успенского. Но с точки зрения практики можно найти приемлемый компромисс, когда можно писать и специализируемые интерпретаторы, и программы распухают не сильно.