Суперкомпиляция

Никогда ранее не участвовал в подобных дискуссиях. Попробую … По поводу отличия суперкомпиляции от частичных вычислений. Идеи разработки оптимизаторов на основе метаинтерпретации возникли в 70-х годах. Тогда, независимо, А.П. Ершовым (Новосибирск), В.Ф. Турчиным (Москва) и Ё. Футамарой (Япония) были обозначены направления исследований в этой области. Таким образом, появились три термина, соответственно: смешанные вычисления, суперкомпиляция, generalized computations. Попытки решить поставленные задачи сразу обнаружили принципиальные трудности; что и не удивительно - любая более-менее содержательная задача на оптимизацию (как таковая) алгоритмически неразрешима. Здесь, кстати, ответ по поводу "циклов". В 80-х годах N.D. Jones принял кардинальное решение по упрощению оригинальных идей Ершова, Турчина и Футамары. Появился термин "частичные вычисления". Именно в частичных вычислениях, благодаря принципиальному упрощению, и были достигнуты основные успехи. Попробую объяснить, не вдаваясь в технические подробности, какое упрощение предложил Jones. Рассмотрим конечный набор элементарных преобразований: t1, …, tN. Другими словами - исчисление. Задача состоит в умелом автоматическом жонглировании этими элементарными преобразовании с целью оптимизации программы. Jones предложил разбить множество {t1, …, tN} на два подмножества { t1, …, tK } и { tK+1, …, tN }. Далее, он решил принять на работу ещё одного фокусника и разделил сферу ответственности между этими двумя цирковыми служащими. Первый фокусник, в первую смену, жонглирует преобразованиями { t1, …, tK }. Во вторую смену, второй фокусник берет результат работы первого фокусника и жонглирует с ним преобразованиями { tK+1, …, tN }. То, что получится после второй смены, и называется результатом преобразований при частичных вычислениях. Чтобы прочувствовать насколько при этом Jones ограничил возможности оптимизации, полезно провести следующую аналогию. Рассмотрим машину Тьюринга (МТ). Программист является жонглером конечного набора элементарных преобразований, допустимых в МТ {t1, t2, здвинуть_указатель_влево, здвинуть_указатель_вправо, t5, t6}. Композиция этих преобразований позволяет показать фокус с любым алгоритмом. Далее, мы разделим множество элементарных преобразований МТ на два {t1, t2, здвинуть_указатель_влево} и {здвинуть_указатель_вправо, t5, t6}; наймем на работу двух программистов и выдадим им инструкцию, аналогичную Jones-овской. Вопрос: что они смогут запрограммировать?