Суперкомпиляция
На работе защитился очень способный мальчик, который пришел к нам работать лет 7 назад еще студентом-третьекурсником, сначала тестером, затем программистом. Потом он вынуждено уходил в одну большую компанию, но вернулся, когда мы его хорошо позвали, из-за чего со мной до сих пор не разговаривает его бывшая начальница "там", моя однокурсница. Параллельно Илья поступил в аспирантуру ИПМ им. Келдыша и начал заниматься довольно экзотичной областью computer science -- суперкомпиляцией. Особенно необычно это сочеталось с его основным образованием -- ФАЛТ физтеха. Тем не менее, он по-настоящему влил новую струю в эту не очень хорошо проработанную область, результатом чего явилась защита диссертации.
Я расскажу немного,что такое суперкомпиляция и зачем она нужна.
Начнем с самого термина. Когда я его впервые услышал, он показался странным. Под "супер" в наше время понимается обычно превосходная степень. Тем не менее, есть такие слова как "супервизор" или "суперпозиция", где приставка "супер" выступает как что-то "сверху". Именно это имел ввиду замечательный ученый Валентин Турчин, когда придумал суперкомпиляцию в 1972г.
Турчин разрабатывал концепцию метасистемного перехода, в разных областях. Что такое метасистемный переход? Это переход от частного к общему. Например, от арифметики к алгебре. Или от доказательства, к теории доказательств. Или от одноклеточных организмов, к многоклеточным. Это фундаментальное понятие в эволюции систем. Суперкомпиляция -- это метасистемный переход в выполнении программ. Традиционно программу можно рассматривать просто как некоторую функцию, которая будучи скомпилированной и выполненной для определенных входных данных выдает определенные значения. Суперкомпиляция строит модель программы, и эквивалентными преобразованиями упрощает или специлизирует ее для определенного набора данных, получая другую, эквивалентную, но более эффективную программу. То есть это некоторый способ анализа и трансформации программ. На вход суперкомпилятора подается программа плюс (необязательно) некоторые знания о данных (ограничения, частичная специализация и т.п.), а на выходе -- оптимизированная программа.
Таким образом, процедура суперкомпиляции заключается в следующих шагах:
1. Исполнение исходного алгоритма над интересующими данными на некоторой метамашине с запоминанием всех произведенных вычислений.
2. Cвертка полученного списка вычислений таким образом, чтобы интересующие показатели алгоритма улучшились, а результат вычисления остался верным.
3. Обратное преобразование списка вычислений в код нового алгоритма.
Самое интересное в этом, как выполняется исполнение исходного алгоритма на метамашине, в терминах Турчина это называется прогонкой. Для этого строится полное дерево вычислений, в процессе чего приходится распознавать циклы. В результате чего получается граф с циклами, представляющий собой полную модель алгоритма. Над этим графом можно делать преобразования, легко доказывать, что программа остановится, специализировать его, если нужно, и в конце концов сгенерировать новую, преобразованную программу. То есть суперкомпилятор сначала декомпилирует программу во внутреннее представление, потом преобразует ее, оптимизирует, а затем компилирует обратно в исходный (или любой другой, если есть мета-модель, то это уже не важно) язык.
За подробным разбором примера суперкомпиляции простейшей программы я отошлю к этой статье.
Первоначально теория и практика суперкомпиляции была разработана Турчиным на функциональном языке Рефал для программ на нем же. И только в 90е годы стали появляться реализации для других языков. Илья реализовал суперкомпилятор SPSC на Скале, Хаскелле, Питоне и Руби для простого функционального языка первого порядка, и сделал его доступным для всех, в том числе и через Веб-интерфейс. Примеры его применения для модельных задач можно посмотреть там же на странице проекта или вот тут. Следующим шагом стала разработка HOSC, в котором в качестве входного языка уже был более богатый функциональный язык, являющийся подмножеством Хаскеля.
Все это чрезвычайно интересно, в мире такого рода исследованиями занимается в мире не так много людей, а у нас в стране и вовсе единицы. А результат может быть впечатляющим. Представьте, что суперкомпилятор может, например, преобразовывать произвольный интепретируемый DSL (domain specific language) в что-нибудь выполнимое. Как правило, DSL создаются для удобства программирования, а не выполнения. Поэтому они не оптимальны. И суперкомпилятор может снять все ненужные наслоения и получить оптимальную программу. Это уже возможно. Ну а в перспективе, применять суперкомпилятор можно было бы для любых программ. Как бы все вокруг быстрее заработало :)
Как вы уже догадались, более подробно о суперкомпиляции и метавычисленияхможно почитать на metacomputation-ru
P.S. Это несомненно приятное событие заставило меня вспомнить собственную неоконченную научную работу, поднять последнюю недописанную статью из архива и попробовать дописать ее. С 2002г ничего в "моей" области не поменялось, поэтому работа все еще актуальна. Это не computer science, а математика. И об этом я как-нибудь расскажу в следующий раз.
Я расскажу немного,что такое суперкомпиляция и зачем она нужна.
Начнем с самого термина. Когда я его впервые услышал, он показался странным. Под "супер" в наше время понимается обычно превосходная степень. Тем не менее, есть такие слова как "супервизор" или "суперпозиция", где приставка "супер" выступает как что-то "сверху". Именно это имел ввиду замечательный ученый Валентин Турчин, когда придумал суперкомпиляцию в 1972г.
Турчин разрабатывал концепцию метасистемного перехода, в разных областях. Что такое метасистемный переход? Это переход от частного к общему. Например, от арифметики к алгебре. Или от доказательства, к теории доказательств. Или от одноклеточных организмов, к многоклеточным. Это фундаментальное понятие в эволюции систем. Суперкомпиляция -- это метасистемный переход в выполнении программ. Традиционно программу можно рассматривать просто как некоторую функцию, которая будучи скомпилированной и выполненной для определенных входных данных выдает определенные значения. Суперкомпиляция строит модель программы, и эквивалентными преобразованиями упрощает или специлизирует ее для определенного набора данных, получая другую, эквивалентную, но более эффективную программу. То есть это некоторый способ анализа и трансформации программ. На вход суперкомпилятора подается программа плюс (необязательно) некоторые знания о данных (ограничения, частичная специализация и т.п.), а на выходе -- оптимизированная программа.
Таким образом, процедура суперкомпиляции заключается в следующих шагах:
1. Исполнение исходного алгоритма над интересующими данными на некоторой метамашине с запоминанием всех произведенных вычислений.
2. Cвертка полученного списка вычислений таким образом, чтобы интересующие показатели алгоритма улучшились, а результат вычисления остался верным.
3. Обратное преобразование списка вычислений в код нового алгоритма.
Самое интересное в этом, как выполняется исполнение исходного алгоритма на метамашине, в терминах Турчина это называется прогонкой. Для этого строится полное дерево вычислений, в процессе чего приходится распознавать циклы. В результате чего получается граф с циклами, представляющий собой полную модель алгоритма. Над этим графом можно делать преобразования, легко доказывать, что программа остановится, специализировать его, если нужно, и в конце концов сгенерировать новую, преобразованную программу. То есть суперкомпилятор сначала декомпилирует программу во внутреннее представление, потом преобразует ее, оптимизирует, а затем компилирует обратно в исходный (или любой другой, если есть мета-модель, то это уже не важно) язык.
За подробным разбором примера суперкомпиляции простейшей программы я отошлю к этой статье.
Первоначально теория и практика суперкомпиляции была разработана Турчиным на функциональном языке Рефал для программ на нем же. И только в 90е годы стали появляться реализации для других языков. Илья реализовал суперкомпилятор SPSC на Скале, Хаскелле, Питоне и Руби для простого функционального языка первого порядка, и сделал его доступным для всех, в том числе и через Веб-интерфейс. Примеры его применения для модельных задач можно посмотреть там же на странице проекта или вот тут. Следующим шагом стала разработка HOSC, в котором в качестве входного языка уже был более богатый функциональный язык, являющийся подмножеством Хаскеля.
Все это чрезвычайно интересно, в мире такого рода исследованиями занимается в мире не так много людей, а у нас в стране и вовсе единицы. А результат может быть впечатляющим. Представьте, что суперкомпилятор может, например, преобразовывать произвольный интепретируемый DSL (domain specific language) в что-нибудь выполнимое. Как правило, DSL создаются для удобства программирования, а не выполнения. Поэтому они не оптимальны. И суперкомпилятор может снять все ненужные наслоения и получить оптимальную программу. Это уже возможно. Ну а в перспективе, применять суперкомпилятор можно было бы для любых программ. Как бы все вокруг быстрее заработало :)
Как вы уже догадались, более подробно о суперкомпиляции и метавычисленияхможно почитать на metacomputation-ru
P.S. Это несомненно приятное событие заставило меня вспомнить собственную неоконченную научную работу, поднять последнюю недописанную статью из архива и попробовать дописать ее. С 2002г ничего в "моей" области не поменялось, поэтому работа все еще актуальна. Это не computer science, а математика. И об этом я как-нибудь расскажу в следующий раз.