Сергей Романенко
12 мая 2009 г.
“Откуда есть пошла” суперкомпиляция? Сейчас мы уже как-то привыкли к тому, что всё новое придумывают иностранцы, что они же это новое изготавливают и продают, а мы потом всё это покупаем за нефть. Однако, в случае с суперкомпиляцией дело обстоит на так: она была изобретена в России. Ну, точнее, в СССР. Причём придумал её не программист, а физик: Валентин Фёдорович Турчин:
Точнее, сначала он в 1966 году придумал “метаалгоритмический язык” Рефал, предназначенный для обработки алгоритмов, записанных на каких-то языках программирования.
Турчин В.Ф.. Метаязык для формального описания алгоритмических языков, сб. “Цифровая вычислительная техника и программирование”, изд-во “Советское радио”, М.-Л., 1966.
Турчин В.Ф. Метаалгоритмический язык. — Кибернетика № 4, 1968. С. 116−124. DJVU PDF
Со второй из статей можно ознакомиться (на выбор - в формате djvu или pdf), а первую из них, я когда-то держал в руках, а где добыть сейчас - не знаю…
Через некоторое время Турчин задумался над такой мыслью: если Рефал, в принципе, годится для обработки программ на любых алгоритмических языках, то, по определению, должен быть пригоден и для обработки программ на нём же самом. (Задним числом эта мысль кажется очевидной.) :-)
Правда, “обработка” программ тоже бывает разная… Например, раскраска ключевых слов в программа - это, можно считать, тоже “обработка” программы. Турчина же заинтересовал особый вид “обработки”, вытекающий из идеи “метасистемного перехода”. Что понимает Турчин под “метасистемным переходом”, можно прочитать в его книге:
Тема эта - интересная, но очень обширная, поэтому мы сейчас в неё не будем углубляться, а рассмотрим только один частный случай, относящийся к исполнению программ.
Рассмотрим некоторый алгоритмический язык. (Заметим в скобках, что понятие “алгоритмический язык” не совсем совпадает с понятием “язык программирования”. Например, язык машин Тьюринга очевидным образом является “алгоритмическим языком”, но “языком программирования” его обычно не называют. :-) ) Допустим, у нас есть программа на этом языке, которую нам хочется “выполнить”, применив к некоторым “исходным данным”. (Впрочем, в некоторых языках, например, в λ-исчислении, разницы между “данными” и “программой” не существует.)
Понятно, что “выполнить” программу можно только в том случае, если есть некий субъект, который её “понимает” и умеет выполнять. Этим субъектом может быть “железным” устройством (вроде процессора компьютера), программой или человеком. Для краткости, будем называть этого субъекта “интерпретатором”.
Итак, берём интерпретатор, программу и исходные данные и всё это запускаем. Интерпретатор начинает задумчиво “жевать” программу и данные. Всю эту (до боли знакомую) ситуацию назовём “основной системой”, находящейся на “основном уровне”.
А теперь представим, что над основным уровнем есть ещё “метауровень”, на котором находится другой субъект, который с большим интересом наблюдает за тем, что происходит в основной системе. Вот это всё и называется “метасистемой”. (Правда, затрудняюсь сейчас сказать, нужно ли считать, что основная система находится внутри метасистемы, являясь её частью, или же метасистема и система разделены? Это, видимо, вопрос определения…)
Ну, а переход от ситуации, когда есть только основная система, к ситуации, когда возникает метасистема, как и следует ожидать, называется “метасистемным переходом”.
Имеем ли мы дело с метасистемными переходами в программировании? Не знаю, как там насчёт теоретиков, но программисты-практики сталкиваются с ними каждый день. Ну, например, что представляет из себя процесс отладки? Отладчик исполняет программу + данные по-шагам, а над ними тяжело дышит программист, который тщетно пытается понять, что происходит. Этот программист и находится на “метауровне” и, стало быть, является “метасистемой” (или её частью). Однако же, идея “автоматизации программирования” (жалко, что про этот изящный термин ныне почти забыли), подразумевает, что было бы хорошо, если бы всех программистов можно было повыгонять и заменить из на бездушные машины и/или программы.
Т.е., в идеале, поведение одной программы должна была бы изучать другая программа, а не человек. А над этой программой, естественно, можно было бы поставить другую программу (сидящую на мета-мета-уровне), и т.д. Но, как говорится, “гладко было на бумаге, да забыли про овраге”. Светлая и завлекательная мечта об “автоматизации программирования” так мечтой и осталась. Хотя, кое-что сделать всё же удалось…
Итак, Турчин задумался о том, как можно было бы построить метасистему (в виде программы), наблюдающую за Рефал-программой, обрабатывающей какие-то данные. И вскорости он обнаружил, что на метауровне имеются кое-какие возможности изучать поведение программы “в общем виде”, т.е. для целых классов входных данных, а не только для какого-то конкретного набора исходных данных (как в случае отладки). Говоря по-простому, обнаружилась возможность перейти от “арифметики” а “алгебре” (в школьном понимании этого слова). Например, то, что 3*(2+1) = 3*2+3*1 - это факт из арифметики. А то, что для любых a, b, и c верно a*(b+c) = a*b+a*c - уже факт из алгебры.
Так появилась система преобразований Рефал-программ, получившая название “прогонка” (driving). Слово “прогонка” появилось из-за того, что “конкретные” данные проходят через процесс вычислений “естественным” путём, а вот в случае “обобщённых” данных, изображающих целые классы “конкретных” данных, дело обстоит хуже: их приходится пропихивать через процесс вычислений буквально пинками, для которых, кстати, в прогонке используются прямо-таки садистские названия: “сужение” и “расщепление”. Сразу на ум приходит сцена в духе “Преступления и наказания”: стоит на метауровне субъект с топором и то обтёсывает “обобщенные данные”, то расщепляет…
Прогонка была описана Турчиным в статьях
В.Ф.Турчин, Эквивалентные преобразования рекурсивных функций, описанных на языке РЕФАЛ. В сб.: Труды симпозиума “Теория языков и методы построения систем программирования’’, Киев-Алушта: 1972. Стр. 31-42. DJVU scan, PDF scan , DJVU LaTeX, PDF LaTeX
Турчин В.Ф. Эквивалентные преобразования программ на РЕФАЛе. Автоматизированная система управления строительством. Труды ЦНИПИАСС, N 6. ЦНИПИАСС. Москва, 1974. Стр. 36-68. DJVU PDF
Главный недостаток статьи 1972 года в том, что сборник трудов симпозиума был напечатан на серой бумаге бедными серыми буквами. Поэтому, в некоторых местах текст можно прочитать только с помощью сильной лупы. Понятно, что при попытке оцифровать эту статью возникли ну очень большие трудности. Пришлось проявить смекалку и изобретательность. Результат можете оценить сами. Выглядит довольно мерзко (хотя читать уже можно без лупы). Поэтому, пришлось перенабрать статью через LaTeX. Этот вариант выглядит чистенько, но зато в нём не ощущается “аромат эпохи” и возраст текста…
В статьях 1972 и 1974 года описана система преобразований Рефал-программ
(прогонка), а также её применение для решения “обратных” задач. А
именно, допустим, что на Рефале описана некая функция f, которая для
любого входного x выдаёт True или False (если завершается). И вот,
Турчин показывает, что с помощью прогонки можно решать “обратную
задачу”: подбирать для f такие значения x, что f(x) = True.
С точки зрения чистой теории в этом нет ничего удивительного, поскольку
известно, что область определения любой рекурсивной функции является
рекурсивно-перечислимой. Интерес был в том, что прогонка позволяла
искать решения не тупым полным перебором, а вполне разумным способом.
Например, в статьях рассматривается вопрос о решении уравнений вида
a+x=b, где a и b - натуральные числа, представленные в двоичной системе
счисления, а сложение определено как сложение “в столбик” в виде функции
на Рефале. И получилось, что поиск x с помощью прогонки делается не
перебором, а вычитанием “в столбик”. Получалось, что компьютер, получив
алгоритм сложения в виде программы автоматически находил разумный
алгоритм вычитания.
Должен сказать, что описанное в статьях было тогда же реализовано в виде программ на Рефале (хотя в самих статьях это и не отражено). Турчин написал реализацию прогонки на Рефале, а “хождение на машину” (как это тогда называлось) и отладку поручил (или, скажем более точно, доверил :-) ) мне. К слову, программы тогда набивались на перфокартах, а “машиной” была могучая БЭСМ-6 (которая, правда, несколько уступала американской CDC-6600).
И, действительно, всё работало по теории: обратные задачи решались… А решения печатались на широченных лентах бумаги.
Однако же, если внимательно вчитаться в статью 1972 года, то у тех, кто знаком с Прологом, наверняка возникнет ощущение чего-то знакомого… Ну да, “обобщённое отождествление” - это “унификация”. Стало быть, Турчин ничего нового не придумал: просто взял Пролог, перекрасил, - и выдал за своё. :-) Но это не совсем так. Или, точнее, совсем не так. Ведь, как утверждают сведущие люди:
Язык Пролог был изобретен французским математиком-программистом Колмэрауе в 1972 году как язык логического программирования для проведения экспериментов в области “искусственного интеллекта” на ЭВМ.
Т.е. в 1972 году Колмэрауе сидел и придумывал Пролог как раз в то самое время, когда Турчин придумывал прогонку. И, естественно, друг о друге они ничего не знали.
Также есть и различия на содержательном уровне:
Пролог основан на “унификации”, а унификация симметрична по отношению к своим двум аргументам. А прогонка основана на “обобщённом алгоритме отождествления”, который асимметричен, и представляет собой сопоставление выражения, содержащего переменные с образцом. При этом “сужения” (подстановки) над образцом не выполняются, а переменные из образца “принимают значения”.
Турчин следовал своей методологии “метасистемного перехода”. Сначала - основной уровень (т.е. Рефал и обычные вычисления), затем - метауровень (на котором наблюдается и изучается поведение основной системы). Поэтому, прогонка - это надстройка над “обыкновенным” функциональным языком программирования (Рефалом). Программист может сначала написать и отладить программу на традиционном языке и традиционными методами. А после этого - засунуть эту программу в прогонку.
Колмэрауе пошёл другим путём. Он объявил, что нужно отказаться от традиционных (неправильных?) языков и методов программирования, и заменить их на новый (правильный?) язык Пролог. Наверное, он при этом надеялся, что программистское сообщество удастся уговорить свернуть с неправильной кривой дорожке на правильную. И многих уговорить удалось! Но не всех… И для этих “не всех” подход Турчина, наверное, выглядит не таким экстремистским, как у Колмэрауе.
Понятно, что прогонка - это только первый шаг на пути построения интересной метасистемы. И Турчин активно занялся дальнейшим продвижением на пути к суперкомпиляции. Но вскоре возникли небольшие затруднения, связанные не с самой научной работой, а, скажем так, с “объемлющей метасистемой” (в виде тогдашних начальников СССР). В результате, Турчина сначала выгнали с работы, а потом и вовсе предложили выбирать: либо поехать далеко-далеко на Восток, либо поехать далеко-далеко на Запад. Вот так Турчин и превратился из советского/российского учёного в американского…
Но не будем отвлекаться от темы, т.е. суперкомпиляции.
Итак, Турчин был изгнан с работы. В нынешнее время, когда стало модно получать зарплату “в конвертиках”, даже трудно осознать суть проблемы. Нет “официальной работы” - всегда можно найти частную лавочку, в которой - понятно что… Но в эпоху “развитого социализма” частных лавочек не существовало. “Выгнать с работы” означало на самом деле ещё и лишить возможности найти работу в другом месте.
Нет работы - нет зарплаты. А если рассматривать научный аспект, то нет работы - нет возможности что-то опубликовать, поскольку опубликовать научную статью можно было только проделав некоторые обязательные действия по месту работы!
Поэтому, между 1974 и 1979 годами - публикаций нет. Точнее, в 1977 году Турчину удалось-таки (с помощью маленькой военной хитрости) опубликовать аж 4 (!) страницы, посвящённых суперкомпиляции. Вот они, эти страницы, однако:
Анекдотическая подробность этого дела заключалась в том, что книга, в довершение всего, была издана вообще анонимно(!). Кроме этого, все авторы получили официальные справки, что да, они являются авторами таких-то и таких-то страниц. У меня до сих пор лежит моя справка (в качестве диковинки, передающий “аромат эпохи”):
(Во избежание недоразумений сразу поясню, что дурь исходила от высшего начальства, а вовсе нет от тех людей, которые выписывали и подписывали эти справки. Они-то как раз делали всё, что могли, чтобы хоть как-то протащить книгу в печать.)
Что касается 4-х страниц, вставленных потихоньку в книгу в процессе её “редакторской правки”, так они - просто шедевр научной прозы. В эти 4 страницы Турчину удалось втиснуть:
“Проекции Футамуры” - вопрос тонкий и имеющий свою интересную историю. Его нужно рассматривать отдельно. Поэтому я изложу его сейчас чисто формально и мимоходом, не рассчитывая, что моё описание будет кому-нибудь понятно (кроме тех, кто уже заранее знает, о чём речь).
Допустим, что у нас есть программа f, исходные данные для которой
разбиты на две части: “статическую” часть x и “динамическую” часть y.
Обозначим через f(x,y) результат применения программы f к исходным
данным (x,y). Тогда “специализатором” называется такая программа s, что
s(p,x)(y) = p(x,y)
Допустим, что p - программа, результатом применения которой к исходным
данным d является p(d). Тогда “интерпретатором” называется такая
программа i, что
i(p,d) = p(d)
Теперь, используя свойства s и i, мы можем построить такую цепочку
равенств:
p(d) = i(p,d) = s(i,p)(d) = s(s,i)(p)(d) = s(s,s)(i)(p)(d)
из которой легко(!) видно, что
s(i,p) - скомпилированная программа.s(s,i) - скомпилированный компилятор для языка, который
интерпретирует i.s(s,s) - скомпилированный компилятор компиляторов (преобразующий
интерпретаторы в компиляторы).Впрочем, как потом выяснилось, Ёсихико Футамура додумался до s(i,p) и
s(s,i) ещё в 1971 году:
Про s(s,s) в этой статье не было ничего сказано, и это выглядело
загадочно: первые 2 шага сделал - а почему не сделал третий? Не
догадался? Но потом обнаружился некий отчёт, в котором s(s,s) было
выписано. Так что, загадка только усугубилась. Если знал и понимал,
почему не упомянул в статье про s(s,s)?
В общем, как бы то ни было, Футамура действительно самым первым
додумался и до s(i,p), и до s(s,i), и до s(s,s). Поэтому,
в соответствии с научными традициями и принципами справедливости, эти штуки и
называются “проекциями Футамуры”.
Однако же, когда Футамура опубликовал свою статью в 1971, на неё никто не обратил внимания. И только когда другие “дозрели” и начали додумываться до того же самого, эта статья была замечена и оценена.
Можно ли считать, что Футамура изобрёл и суперкомпиляцию? Вопрос тонкий. Для практической реализации проекций Футамуры полноценная суперкомпиляция не нужна: вполне достаточно “частичных вычислений”. А с точки зрения суперкомпиляции, частичные вычисления - это некоторый экстремальный, вырожденный случай суперкомпиляции. Ну, а для особого, частного случая, можно использовать и особые методы, специально “заточенные” под этот особый случай. Вот и получается, что по решаемой задаче, частичные вычисления это частный случай суперкомпиляции, а по применяемым методам - различаются. Впрочем, это - отдельная интересная тема… А мы вернёмся к суперкомпиляции.
К сожалению, с 1979 года приходится читать уже на английском языке…
Оказавшись в Нью-Йоркском Городском университете Турчин, первым делом, занялся публикацией того, что ему не удалось втиснуть в 4 страницы, пока он находился в СССР:
Turchin, V. F. 1979. A supercompiler system based on the language REFAL. SIGPLAN Not. 14, 2 (Feb. 1979), 46-54. DOI=10.1145/954063.954069
Turchin, V.F. The Language REFAL, the Theory of Compilation, and Metasystem Analysis. Courant Institute Report #20, New York, 1980. DJVU PDF
Turchin, V. F. 1980. The Use of Metasystem Transition in Theorem Proving and Program Optimization. In Proceedings of the 7th Colloquium on Automata, Languages and Programming (July 14 - 18, 1980). J. W. Bakker and J. v. Leeuwen, Eds. Lecture Notes In Computer Science, vol. 85. Springer-Verlag, London, 645-657.
Turchin, V. F., Nirenberg, R. M., and Turchin, D. V. 1982. Experiments with a supercompiler. In Proceedings of the 1982 ACM Symposium on LISP and Functional Programming (Pittsburgh, Pennsylvania, United States, August 15 - 18, 1982). LFP ‘82. ACM, New York, NY, 47-55. DOI=10.1145/800068.802134
Все публикации существуют в оцифрованном виде. К сожалению, по правилам игры, установленным правообладателями, кое-что не находится в открытом доступе. Впрочем, некоторые проницательные люди утверждают, что запустив eMule/aMule из сделав поиск по ключевым словам “Turchin” и “supercompilation”, кое-что можно найти…)
Ну вот, можно считать, что мы подошли к концу ранней истории суперкомпиляции. Хороший обзор этого периода можно найти у Сёренсена:
Сёренсена заинтересовал следующий вопрос. У Турчина суперкомпиляция всегда рассматривалась применительно к языку Рефал. Верно ли, что суперкомпиляция применима только к Рефалу. Как и следовало ожидать, оказалось, что можно и без Рефала. Можно и объяснить без Рефала. Что Сёренсен и сделал. Так сказать, реализовал лозунг: “Без царя - а правительство рабочее!”