Supercompilation: homeomorphic embedding, call-by-name, partial evaluation
Sergei Anatolievich Romanenko · Keldysh Institute Preprints · 2018
1 Введение В препринте [19] были рассмотрены основные принципы и базовые понятия «суперкомпиляции», представляющей собой метод анализа и преобразования программ, основанный на выполнении программы не для конкретных входных данных, а в «общем» виде (для произвольных входных данных, представленных в «символической» форме).Цель суперкомпиляции -построение конечного «графа конфигураций».«Конфигурации», находящиеся в узлах графа, изображают множества возможных состояний вычислительного процесса, а дуги графа -возможные переходы между множествами состояний.Основные операции, с помощью которых строится граф конфигураций, -это прогонка, обобщение и зацикливание.Прогонка -это порождение новых конфигураций из уже имеющихся.Неограниченное применение прогонки, как правило, приводит к построению бесконечного дерева конфигураций [19].Однако целью суперкомпиляции является получение конечного графа конфигураций, и эта цель может быть достигнута с помощью двух других операций: обобщения и зацикливания.Обобщение -это замена одной конфигурации на другую, «более абстрактную», представляющую больше состояний, чем представляла исходная конфигурация.А зацикливание -это сведение конфигурации к эквивалентной конфигурации (уже встречавшейся ранее).Важно отметить, что обобщение конфигураций является самой сложной частью суперкомпиляции, поскольку именно в процессе обобщения возникает возможность принимать различные решения, от которых зависит конечный результат суперкомпиляции.С одной стороны, при каждом обобщении происходит потеря информации, поскольку расширяется множество состояний, описываемых конфигурацией, и снижается точность анализа вычислительного процесса (ради которого, собственно говоря, и выполняется суперкомпиляция).И, в худшем случае, может получиться программа, совпадающая с исходной (с точностью до имен переменных и функций).Другими словами, суперкомпиляция может вырождаться в тождественное преобразование (польза от которого -весьма сомнительна).С другой стороны, если выполнять обобщение недостаточно энергично, это может привести к тому, что процесс суперкомпиляции никогда не завершится, поскольку будут бесконечно порождаться всё новые и новые конфигурации.Таким образом, необходимо использовать какие-то стратегии, которые, с одной стороны, гарантировали бы завершаемость процесса суперкомпиляции, но, с другой стороны, приводили бы к получению нетривиальных результатов суперкомпиляции.Этот вопрос, в силу его сложности, подробно в препринте [19] не рассматривался, и ему посящен Раздел 2 данного препринта.Кроме того, в Разделе 3 рассматриваются особенности суперкомпиляции