Илья Ключников
28 марта 2011 г.
В заметке Обобщение конфигураций при суперкомпиляции упоминалось, что при суперкомпиляции чего-то более-менее нетривиального приходится делать обобщения - заменять конфигурацию на более общий случай (чтобы добиться завершаемости суперкомпилятора).
В суперкомпиляторном фольклоре то, что сейчас называется обобщением изначально называлось перестройкой конфигурации. Исторически рассматривалось два вида перестройки: перестройка сверху и перестройка снизу.
Почему перестройка сверху и снизу? Потому что дерево конфигураций строится сверху вниз и решение об обобщении (в большинстве суперкомпиляторов) принимается на основании анализа путей в ветвей дерева. Традиционно для принятия такого рода решений использовалось отношение гомеоморфного вложения, но сейчас используются и другие критерии, работающие по похожей схеме. Схема такова: рассматривается ветвь дерева и затем либо (1) ей позволяют расти дальше или (2) в ней находятся и обвиняются (считаются подозрительными) два узла - верхний и нижний.
А дальше - либо перестраивается нижний узел (обобщается нижняя конфигурация), либо перестраивается верхний узел (обобщается верхняя конфигурация). Во втором случае из строящегося дерева конфигураций выкидывается целое поддерево (в котором лежит путь от верхнего узла к нижнему).
Как должна проходить перестройка - сверху или снизу? (Политико-сатирический контекст вопроса появился после рождения терминов.)
У обоих подходов есть свои весомые “за”. Если суперкомпилятор пишется на чистом функциональном языке (или хотя бы в функциональном стиле, - с неизменяемыми структурами), то удобнее перестраивать снизу. И не возникает вопросов “неужели мы строили, чтобы сломать?”
Однако, при перестройке снизу могут возникать различные “краевые случаи”, которые нужно рассматривать особо (не будем на них сейчас останавливаться, - они в разных суперкомпиляторах проявляются по-разному).
Что касается перестройки сверху, то у такой перестройки есть один большой (теоретический) плюс: завершаемость суперкомпилятора, “перестраивающего сверху” доказать легче, чем завершаемость суперкомпилятора, “перестраивающего снизу” (из-за меньшего количества, а то и вовсе отсутствия тех самых нехороших краевых случаев). Мне думается, что именно по этой причине Сёренсен исследовал суперкомпиляторы, перестраивающие сверху (Сёренсен первым начал /формально/ доказывать завершаемость суперкомпиляторов).
В свете последних работ Саймона Пейтона Джонса и его студента Макса Болингброка у перестройки конфигураций появился еще один “политико-сатирический” контекст интерпретации. Более чем современный.
История вопроса такова. В первой версии своего суперкомпилятора (который написан на Хаскеле, а значит, по-функциональному) Саймон и Макс перестраивали конфигурации (называя это немного по-другому: split) снизу. Во второй версии своего суперкомпилятора их концепция изменилась
Вот какие поучительные выводы приходят на ум после чтений работ упомянутых англичан, чутко чувствующих российские реалии: в современных условиях перестройка сверху является ситуацией исключительной и без откатов тут не обойтись.
31 мая 2011 г.
Статью Пейтона Джонса и Болингброка не приняли на ICFP.