О работах Валентина Федоровича Турчина по кибернетике и информатике

Климов А.В.

Аннотация. Кратко описана история, контекст, основные идеи, мотивация и цели исследований В.Ф. Турчина по философии, кибернетике, информатике и математике. Более подробно представлена история работ В.Ф. Турчина по методам преобразований программ, называемых суперкомпиляцией.

Основные этапы жизни В.Ф. Турчина

Валентин Федорович Турчин (14.02.1931–07.04.2010) после окончания Физического факультета Московского государственного университета в 1952 году работал в Физико-энергетическом институте в г. Обнинске. Вскоре после защиты докторской диссертации по физике медленных нейтронов он был приглашен академиком М.В. Келдышем в Институт прикладной математики АН СССР и в 1964 году переехал в г. Москву. При этом В.Ф. Турчин сменил не только место жительства, но и направление своей научной работы с физики на кибернетику и информатику, заявив, что теоретически физика приближается к своему «кризису», для разрешения которого необходима глубокая автоматизация обработки физических и математических теорий, формально-языковых моделей с помощью компьютеров. В качестве первых шагов к этой большой цели во второй половине 1960-х годов он разработал язык обработки символьной информации Рефал, а в 1970-е годы заложил основы методов глубокого преобразования программ, названных им суперкомпиляцией. В те же годы сложилась группа его учеников – студентов и аспирантов МГУ, МИФИ и Физтеха.

В 1972 году В.Ф. Турчин перешел на работу в Центральный научно-исследовательский институт автоматизации систем в строительстве (ЦНИПИАСС), где возглавил лабораторию, в которой вместе со своими учениками продолжал разработку Рефала, его приложений и суперкомпиляции. Летом 1974 года его уволили с работы за правозащитную деятельность и выступления в защиту А.Д. Сахарова и А.И. Солженицына. До отъезда в 1977 году в США он был безработным и продолжал научную работу дома. Еженедельные научные семинары с его учениками по вторникам не прерывались все годы. Когда не стало возможным проводить семинары в институтах, собирались на квартирах.

Приехав в США в 1978 году В.Ф. Турчин полтора года работал в Курантовском институте в г. Нью-Йорке (Courant Institute of Mathematical Sciences) в отделе Якоба Шварца (Jacob T. Schwartz), автора языка SETL. После этого до выхода на пенсию в 1999 он был профессором Городского университета г. Нью-Йорка (The City College of the City University of New York, CC CUNY). В эти годы он выполнил все свои главные работы по суперкомпиляции и основаниям математики, основы которых заложил еще на родине.

Трилогия В.Ф. Турчина

В 1977 году незадолго до отъезда из СССР, делясь планами перед расставанием, Валентин Федорович рассказал о своем замысле научно-философской «трилогии», часть которой он уже тогда реализовал, а над оставшимися направлениями собирался работать в последующие годы:

• Философская часть: концепция метасистемного перехода, изложенная в книге «Феномен науки: кибернетический подход к эволюции» [8, 36]. Он ввел и продемонстрировал на многих примерах понятие метасистемного перехода (МСП) как единообразного кванта эволюции от зарождения живого мира до появления человека и развития культуры с ее высшей точкой – наукой. С точки зрения В.Ф. Турчина эта эволюционная картина дает также представления о добре и зле, о смысле жизни: добро – это то, что способствует созиданию и развитию, зло – это разрушение и препятствование эволюции, основа смысла жизни – представление о творческом бессмертии, как о личном вкладе в бесконечную эволюцию. Работу над кибернетической философией он продолжил в 1990-е годы вместе с Франсисом Хейлигеном (Francis Heylighen) и Клиффом Джослином (Cliff Joslyn) в рамках основанного ими проекта «Принципы кибернетики» («Principia Cybernetica») [2]. В 1990-е годы он выпустил несколько статей по концепции метасистемного перехода, кибернетической онтологии и эпистемологии [20, 21, 23].
• Социальная часть: приложение концепции метасистемного перехода к развитию общества и социальным вопросам, развитое в книге «Инерция страха: социализм или тоталитаризм» [13, 35]. Здесь он дал свой взгляд на историю человечества, выделив в ней три этапа, три уровня по методу интеграции людей в общество: физическое принуждение (рабство), экономическое принуждение (капитализм) и свободная интеграция, к которой человечество еще идет. Для обозначения этой общественной организации будущего он использовал слово «социализм». С точки зрения В.Ф. Турчина переход от капитализма к социализму – это крупномасштабный метасистемный переход. Поскольку эволюция не детерминирована и метасистемные переходы могут происходить по-разному, при попытках построения новых уровней возможны тупики, откаты, а не только последовательное движение вперед к усложнению организации (как принято считать в концепции «прогресса»). Социализм в СССР – это пример попытки построить общество, интегрированное на основе идей и духовной культуры общества, но неудачной. Получился не социализм, а тоталитаризм, в котором индивиды потеряли свое главное свойство – творческую свободу, – в то время как удачный МСП создает новый уровень управления с целью интеграции подсистем в систему, не разрушая основных свойств подсистем, а сохраняя, используя и развивая их.
• Научная часть: использование концепции метасистемного перехода к получению научных результатов. Валентин Федорович говорил, что новую философскую концепцию невозможно «разрекламировать» и «внедрить в умы» без демонстрации ее плодотворности для получения конкретных достижений. Только если философия предоставляет правила для ума, помогающие порождать новые идеи и анализировать происходящие в науке и обществе процессы, она увлечет людей. Когда В.Ф. Турчин делился такими планами в 1977 году, одно из его достижений в области программирования было создано, второе уже складывалось на уровне общих принципов и методов, а третье он создал уже в США:
• язык программирования Рефал,
• суперкомпиляция,
• кибернетические основания математики.

Рефал как метаязык

В.Ф. Турчин пропагандировал точку зрения на науку как на формально-языковое моделирование реальности, а не как на процесс познания каких-либо абсолютных истин. В частности, математика изучает свойства самих формальных моделей, а не каких-либо идеальных объектов. С появлением компьютеров человечество получило независимый от человеческого ума инструмент работы с языковыми моделями. С этого времени человек может не заниматься рутинными манипуляциями с символами, а возлагать их на компьютер, оставив за собой деятельность по разработке алгоритмов и программ. Появление компьютеров и программирования как вида человеческой деятельности – это крупномасштабный метасистемный переход в истории человечества в целом и науки в частности, направленный на автоматизацию обработки формально-языковых моделей.

Следующий метасистемный переход – автоматизация самого программирования с использованием компьютеров, которая стала развиваться сразу же на заре вычислительной техники, и появление языков программирования и программирующих программ – трансляторов. В результате сами программы становились объектами манипулирования.

В середине 1960-х годов В.Ф. Турчин создал язык Рефал [29-31] как метаязык для обработки текстов на формальных языках с целью дать дальнейшее развитие этому метасистемному переходу. В те времена Рефал был языком более высокого уровня, чем существовавшие языки для обработки символьной информации Lisp, SNOBOL и другие. В 1970-е годы в СССР Рефал активно использовался для написания трансляторов, макрогенераторов, интерпретаторов, а также других видов преобразования текстов и языковых моделей: аналитические вычисления (компьютерная алгебра), задачи искусственного интеллекта, построение математических доказательств и т.п.

Например, одной из крупных задач, которую он тогда поставил, и которая не решена до сих пор – компьютерная проверка математических текстов по трактату Н. Бурбаки. Как-то Валентин Федорович попросил С.А. Романенко, тогда студента МГУ, провести эксперименты по раскрыванию определений в текстах на формальном языке из первого тома трактата Н. Бурбаки «Теория множеств». Неожиданно оказалось, что даже самые простые формулы экспоненциально взрывались по размеру. Мне запомнилось, как Сергей развернул на два стола рулон распечатки с БЭСМ-6 со сплошной формулой на базовом языке трактата, порожденной из терма длиной в несколько символов в высокоуровневых понятиях, и Валентин Федорович с изумлением на нее смотрел, ходил по комнате, думал, а потом произнес непонятные мне тогда слова: «Надо совершать метасистемный переход!».

В области развития языков программирования В.Ф. Турчин ожидал взрыва числа специализированных проблемно-ориентированных языков. Один из принципов, который он сформулировал в концепции метасистемного перехода, – закон разрастания предпоследнего уровня, гласит: когда складывается новый уровень управления, подсистемы предыдущего уровня под его воздействием приобретают разнообразие и размножаются количественно. Развитие в 1960-е и 1970-е годы формальных и программных средств описания языков, систем программирования интерпретаторов и компиляторов (называемых компиляторами компиляторов), макрогенераторов – это было становление метасистемы над языками программирования. В результате облегчалось создание новых языков, следствием чего должен был стать рост их числа и качества. В.Ф. Турчин подчеркивал, что языкотворчество – это естественное свойство человека. Каждая прикладная область должна порождать свой формальный язык. Ощущая важность этой задачи, Валентин Федорович сам продемонстрировал, как строить макросистемы, используя Рефал в качестве макроязыка [34].

Интересно, что этот прогноз В.Ф. Турчина поначалу не сбылся. В 1980-е годы макросистемы вышли из моды. К 1990-м годам вообще стало казаться, что новые языки программирования перестали появляться. О метаязыках вообще и о Рефале в частности стали реже вспоминать. У тех, кто помнил о словах Турчина, могло возникнуть сомнение в «прогностической силе» концепции МСП. Но вот наступили 2000-е, и вдруг снова вернулась мода на языкотворчество и, как в 1960–70-е годы, стали плодиться языки программирования (например, языки «сценариев», scripting languages), структурированные форматы представления данных (например, на базе XML), языки спецификации интерфейсов, структуры и поведения различных систем и прочие виды языков. Естественно предположить, что вернется и мода на метаязыки типа Рефала или еще более высокого уровня.

Появление суперкомпиляции

После первых шагов по использованию Рефала для обработки формальных текстов, практически ощутив сложность задач, В.Ф. Турчин устремился к поиску путей дальнейшей автоматизации создания метапрограмм – программ, порождающих и преобразующих программы. Он говорил, что мы должны научиться так же легко обрабатывать программы на ЭВМ, как обрабатываем числа на Фортране. Определения языков программирования в виде программ – интерпретаторы, компиляторы – должны также стать объектом преобразований. Это еще один метасистемный переход.

Концепция метасистемного перехода была для В.Ф. Турчина не только понятийным аппаратом, с помощью которого он анализировал явления, но и «руководством к действию». Изучая, как происходят метасистемные переходы, он выявлял типовые шаблоны и приемы, подмечал общие закономерности и пользовался ими для конструирования новых метасистемных переходов с целью ускорить развитие интересовавших его научных направлений. Большой материал и примеры давала метаматематика и математическая логика. По аналогии с ними рождалась суперкомпиляция как метод преобразования определений языков на Рефале.

Впервые В.Ф. Турчин высказал эти идеи на семинаре в ИПМ зимой 1971–72 года (к сожалению, точнее дату восстановить невозможно). Он написал на доске простую программу – интерпретатор арифметических выражений на Рефале – и предложил провести вычисления «в общем виде» с заданным выражением, но неизвестными числовыми аргументами. Позже он учил нас, что введение переменных и выкладки «в общем виде» – это стандартный прием совершения метасистемного перехода в математике, который надо позаимствовать в программировании и методах обработке программ. А в тот раз, проделав неформально вычисления над вызовом функции с переменными, он получил на доске текст, напоминающий результат трансляции арифметического выражения в команды машины, и воскликнул: «Смотрите, компилирует!». Это было то, что сейчас называется специализацией программ по частично заданным аргументам.

Вскоре после этого В.Ф. Турчин изложил эту технику применительно к Рефалу в формальном виде [32]. Эта публикация 1972 года отсчитывает начало истории суперкомпиляции. Но это был еще базовый уровень, названный в следующей, более подробной публикации 1974 года [33] прогонкой. В первой работе [32] он также определил на базе прогонки алгоритм обращения алгоритмов. По (не совсем) удивительному совпадению, язык Пролог, в который встроена похожая техника обращения, появился также в 1972 году.

С 1974 года, будучи безработным, В.Ф. Турчин не мог публиковаться в СССР, и появление суперкомпиляции на свет произошло на серии еженедельных семинаров зимой 1974-75 годов, которые проходили в АСУрыбпроекте – Центральном проектно-конструкторском и технологическом институте автоматизированных систем управления Министерства рыбного хозяйства СССР, где тогда работал один из постоянных участников семинара Э.А. Вартапетян. У меня сохранились пожелтевшие листки конспекта тех лекций. Всего было 7 семинаров. Точных дат не сохранилось, кроме четвертого: он был 11 февраля 1975 года. Возможно, первые три были до зимней сессии с перерывом на студенческие каникулы, но может, семинары и не прерывались.

Тогда были изложены все основные идеи суперкомпиляции. В частности, на третьем семинаре В.Ф. Турчин рассказал, как путем трех метасистемных переходов с помощью суперкомпилятора породить компилятор по интерпретатору и компилятор компиляторов – аналог того, что позже получило название проекций Футамуры. (Й. Футамура получил эти результаты раньше: две первые проекции описаны в статье 1971 года [1], а третья проекция – для компилятора компиляторов – в рабочем отчете 1973 года.)

Суперкомпиляция является образцом построения сложной формальной системы путем совершения нескольких метасистемных переходов. Именно в таком виде В.Ф. Турчин представил ее на тех семинарах:

• Первый МСП над вычислениями: переход от конкретных состояний к представлению множеств состояний с переменными (называемых конфигурациями), от конкретных вычислений к вычислениям с переменными (называемых прогонкой), от вычисления по одному пути к процессу развертывания потенциально бесконечного дерева, представляющего все пути вычислений.
• Второй МСП над прогонкой: свертка бесконечного дерева в конечный граф путем выполнения операций зацикливания и обобщения.
• Третий МСП над операциями свертки: различные стратегии остановки процесса прогонки, выполнения обобщения и перестроек дерева и графа. Второй и первые версии третьего уровня В.Ф. Турчин назвал конфигурационным анализом. (Заметим, что разделение на уровни МСП иногда неоднозначно, если они возникли одновременно.)
• Другие МСП над вычислениями и над прогонкой: окрестностный анализ – обобщенные вычисления с двумя видами переменных (вторые естественно назывались метапеременными) с целью получить не только дерево и граф вычислений, но и множества состояний и множества конфигураций, которые проходят те же пути конкретных или обобщенных вычислений. В.Ф. Турчин задумал окрестностный анализ для совершенствования конфигурационного анализа как еще один уровень управления, позволяющий удачнее подбирать точки обобщения и зацикливания. Позднее С.А. Абрамов предложил и другие интересные применения окрестностного анализа, включая тестирование [26].

До отъезда из СССР Валентину Федоровичу не удалось ничего опубликовать по собственно суперкомпиляции. Лишь в сборнике трудов 1977 года [37], изданном в ЦНИПИАСС без указания авторов, чтобы не упоминать имя В.Ф. Турчина, удалось вставить в главе «Техника использования Рефала» в конце раздела «Трансляционные задачи» три страницы (92–95) с изложением формул, порождающих компилятор и компилятор компиляторов.

За год до отъезда, осенью 1976 года, Валентин Федорович узнал о том, что близкие по целям исследования ведет А.П. Ершов, называвший свой подход смешанными вычислениями. Они встречались один раз в Москве в гостинице «Академическая» и обменивались идеями. Можно предположить, что они тогда сопоставили понятие генерирующего расширения, введенного А.П. Ершовым, и схемы порождения компилятора и компилятора компиляторов В.Ф. Турчина, поскольку в статье [27] Андрей Петрович называет формулу второго МСП, выражающую генерирующее расширение через специализатор (суперкомпилятор), теоремой о двойной прогонке В.Ф. Турчина.

Развитие суперкомпиляции В.Ф. Турчиным

После эмиграции В.Ф. Турчина в США работы по суперкомпиляции в России продолжались его учениками. Постепенно к нему присоединялись исследователи из других университетов в Западной Европе, особенно в Дании на факультете информатики (Datalogisk Institut), возглавлявшемся Нилом Джоунсом (Neil D. Jones), где был разработан свой метод специализации программ – частичные вычисления (partial evaluation). В последние годы наблюдается взрыв работ по суперкомпиляции многих авторов в разных странах. Но здесь мы ограничимся рассказом о линии работ самого В.Ф. Турчина и отметим лишь наиболее важные статьи других авторов.

В первые годы работы в США в Курантовском институте (1978–1979) Валентин Федорович изложил накопившиеся к тому времени идеи по Рефалу и суперкомпиляции в большом отчете [10]. Ряд тех идей до сих пор не освоены продолжателями и ожидают своего развития и реализации, в частности: грамматики путей вычисления и основанные на них понятия метадифференцирования и метаинтегрирования и метасистемные формулы. Эта техника лежит на следующем метауровне по сравнению с конфигурационным анализом, у которого основным объектом работы являются конфигурации. Здесь же объектом становятся представления множеств путей, графов конфигураций. Этой работой В.Ф. Турчин наметил следующий метасистемный переход, порождающий суперкомпиляторы более высокого уровня. Однако только недавно удалось построить первый двухуровневый суперкомпилятор [4], правда на других идеях (что лишний раз демонстрирует неоднозначность и недетерминированность метасистемных переходов).

В 1980-е годы, работая в CC CUNY, с небольшой группой американских учеников он создал и реализовал на IBM PC новую версию Рефала – Рефал-5 [19], а также разработал серию суперкомпиляторов для языка Рефал. Хотя первые суперкомпиляторы и используемые компьютеры были слабые, удалось провести первые эксперименты [6, 9, 16] и наметить подходы к решению различных задач с помощью суперкомпиляторов [11], в частности, к доказательству теорем [12].

В 1987 году Динес Бьёрнер (Dines Bjørner) организовал семинар в Дании по частичным и смешанным вычислениям (Workshop on Partial Evaluation and Mixed Computation, Gammel Averns, Denmark), в котором участвовали лидеры этого направления Н. Джоунс, А.П. Ершов, В.Ф. Турчин, Й. Футамура и их ученики. На том семинаре В.Ф. Турчин представил работу [18] о первом практичном свистке – правиле останова прогонки и обобщения конфигурации. Предыдущие версии свистков были либо слишком ресурсоемкими, либо не давали хороших остаточных программ в автоматическом режиме и требовали слишком подробных «подсказок» от пользователя. Можно считать, что этим закончилась разработка первого круга методов, на котором можно реализовать суперкомпилятор.

В том же году вышла журнальная статья по суперкомпиляции [15], на которую принято ссылаться.

С 1989 года возобновились регулярные контакты Валентина Федоровича с его российскими учениками. Вместе с Татьяной Ивановной он почти каждый год приезжал в Россию, и во время его пребывания проходили интенсивные семинары в Москве, Обнинске (1990) и Переславле-Залесском.

В конце 1980-х годов Валентин Федорович подготовил черновик книги о суперкомпиляции. Но она так и осталась незавершенной. В ней он детально описал устройство второй версии своего суперкомпилятора SCP2. Копии написанных глав были розданы участникам семинара по суперкомпиляции в г. Обнинске летом 1990 года, поэтому иногда на нее ссылаются как на «обнинскую книгу».

В начале 1990-х годов он вернулся к идее построения более мощного суперкомпилятора на основе преобразований грамматик путей. Сузив класс грамматик (по сравнению с отчетом-80 [11]) до регулярных выражений, он вчерне разработал методы, описанные в статье 1993 года [22]. Однако, они не были доведены до конкретных алгоритмов и стратегий и еще ждут продолжения.

В 1994 году у Валентина Федоровича в США стажировался А.П. Немытых, и они начали работу над четвертой версией суперкомпилятора Рефала SCP4, которую в течение следующих лет А.П. Немытых довел до законченного вида [5, 28].

В 1995 году Мортен Сёренсен (Morten Heine Sørensen) и Роберт Глюк (Robert Glück) предложили [7] использовать вполне-квази-порядок (well-quasi-order) на термах (гомеоморфное вложение) в качестве свистка. Валентину Федоровичу этот метод очень понравился, и с этого момента он предлагал использовать его в качестве основного в суперкомпиляторах.

В 1996 году В.Ф. Турчин написал две последние статьи [24, 25] с обзором достижений и его видению направлений работ по суперкомпиляции. Возможно, Валентин Федорович уже чувствовал, что силы покидают его, и он подводил итоги.

За последние два десятилетия его учениками была проведена большая работа по упрощению методов суперкомпиляции, их шлифовке, наработке новых приемов и реализации разнообразных версий суперкомпиляторов для простых модельных языков. Но это уже другая история. Сам В.Ф. Турчин больше интересовался работами по суперкомпиляции реальных языков, например, Java [3], и выходу в практику. В последние годы наблюдается взрыв интереса к суперкомпиляции, о котором Валентин Федорович мечтал, но уже не застал.

Кибернетические основания математики

Еще одно научное достижение В.Ф. Турчина лежит в области оснований математики. Валентин Федорович был конструктивистом по духу, близким школе А.А. Маркова. Он говорил, что никакой актуальной бесконечности не существует. Есть только языковые модели и потенциально бесконечные процессы, перечисления. Как и А.А. Марков, он стремился свести все математические понятия к конструктивным, алгоритмическим. Его не смутила неудача конструктивной математики, пытавшейся все свести к алгоритмам. Он увидел ограниченность марковского конструктивного подхода в том, что система получилась замкнутой, не способной к развитию. Сведя всё к детерминированным алгоритмам, мы получили мир, в котором последовательности метасистемных переходов «вырождаются», «насыщаются», перестают порождать новое качество.

В конце концов ему удалось построить «открытую» конструктивную систему, расширив мир алгоритмов моделью пользователя, математика. Произошел метасистемный переход, аналогичный появлению физических теорий, в которых появляется понятие наблюдателя. Колесики его теории, названной кибернетическими основаниями математики (Cybernetic Foundation of Mathematics), моделируют многократное применение метасистемных переходов. В этой теории он фактически продемонстрировал, что такое формализованные метасистемные переходы в действии. В результате ему удалось дать конструктивную интерпретацию понятия множества и аксиом Цермело-Френкеля на основе расширенного понятия алгоритма.

В 1983 году он закончил книгу по кибернетическим основаниям математики, которая была издана лишь в виде университетского отчета [14]. После этого он сжал материал до двух статей, которые были приняты к публикации в журнале, но с условием, что он сократит их до одной статьи [17]. К сожалению, опубликованная версия из-за чрезмерной плотности информации стала плохо читабельной. Полная версия еще ждет своего издания и перевода на русский язык.

Естественно предположить, что Валентин Федорович планировал объединить работы по суперкомпиляции и кибернетическим основаниям. Он говорил, что не верит в плодотворность методов машинного доказательства теорем на основе логического вывода, и искал конструктивные подходы. Алгоритмические определения математических понятий могут стать объектом преобразований и вывода с помощью методов, похожих на суперкомпиляцию. В свою очередь, суперкомпиляция может обогатиться средствами эффективных конструктивных доказательств утверждений о программах.

Заключение

История суперкомпиляции насчитывает уже почти 40 лет. Ею занимается уже третье поколение ученых. В.Ф. Турчин спешил получить инструмент преобразования программ для реализации своих следующих идей по обработке формально-языковых моделей. Но история движется гораздо медленнее. Сейчас, когда мы имеем несколько экспериментальных суперкомпиляторов, ясно, что ни в 1970-е годы на БЭСМ-6, ни в 1980-е годы на персональных компьютерах невозможно было эксплуатировать систему такого рода. Но с начала нового тысячелетия, когда мы получили на своих рабочих столах компьютеры гигагерцовой мощности и с гигабайтной памятью, наконец, стало получаться. Более того, естественно предположить, что новые проблемы автоматизации параллельного программирования на суперкомпьютерах будущего не будут решены без таких методов.

Времена суперкомпиляции и аналогичных по вычислительной сложности методов настали. Вслед за Валентином Федоровичем мы сейчас называем эту область информатики метавычислениями – вычислениями над программами.

Список литературы

1. Futamura Y. Partial evaluation of computing process – an approach to a compiler-compiler // Systems, Computers, Controls, Volume 2, Issue 5, 1971. – P.45-50.
2. Heylighen F., Joslyn C., Turchin V.F. Principia Cybernetica Web. 1993-2005. – URL: http://pcp.vub.ac.be.
3. Klimov And.V. An approach to supercompilation for object-oriented Languages: the Java Supercompiler case study // A.P. Nemytykh (ed.) Proceedings of the First International Workshop on Metacomputation in Russia (July 2-5, 2008, Pereslavl- Zalessky, Russia). – Pereslavl-Zalessky: Ailamazyan University of Pereslavl, 2008. – P.43-53.
4. Klyuchnikov I.G., Romanenko S.A. Towards Higher-Level Supercompilation // Andrei P. Nemytykh (ed.) Second International Valentin Turchin Memorial Workshop on Metacomputation in Russia, META 2011 (July 1-5, 2010, Pereslavl- Zalessky, Russia). – Pereslavl-Zalessky: Ailamazyan University of Pereslavl, 2010. – P.82-101.
5. Nemytykh A.P., Pinchuk V.A., Turchin V.F. A Self-Applicable Supercompiler // Olivier Danvy, Robert Glück, Peter Thiemann (eds.), Dagstuhl Seminar on Partial Evaluation (February 12-16, 1996, Dagstuhl Castle, Germany). Lecture Notes in Computer Science, volume 1110. – Springer, 1996. – P.322-337.
6. Nirenberg R., Turchin D.V., Turchin V.F. Experiments with a Supercompiler // Proceedings of the 1982 ACM Symposium on LISP and Functional Programming (August 15-18, 1982, Pittsburgh, PA, USA). – ACM, 1982. – P.47-55.
7. Soerensen M.H., Glueck R. An algorithm of generalization in positive supercompilation // J. W. Lloyd (ed.) International Logic Programming Symposium (December 4-7, 1995, Portland, Oregon). – MIT Press, 1995. – P.465-479.
8. Turchin V.F. The Phenomenon of Science: A Cybernetic Approach to Human Evolution. – New York: Columbia University Press, 1977. – XVII, 348 p.
9. Turchin V.F. A supercompiler system based on the language Refal // ACM SIGPLAN Notices, Volume 14, Issue 2, 1979. – P.46-54.
10. Turchin V.F. The Language Refal – the Theory of Compilation and Metasystem Analysis. Technical Report 20. – Courant Institute of Mathematical Sciences, New York University, 1980. – 245 p.
11. Turchin V.F. Semantic definitions in REFAL and the automatic production of compilers // Neil D. Jones (ed.) Semantics- Directed Compiler Generation, Proceedings of a Workshop (January 14-18, 1980, Aarhus, Denmark). Lecture Notes in Computer Science, volume 94. – Springer, 1980. – P.441-474.
12. Turchin V.F. The use of metasystem transition in theorem proving and program optimization // Automata, Languages and Programming, 7th Colloquium (July 14-18, 1980, Noordweijkerhout, The Netherland). Lecture Notes in Computer Science, volume 85. – Springer, 1980. – P.645-657.
13. Turchin V.F. The Inertia of Fear and the Scientific Worldview. – New York: Columbia University Press, 1981. – 300 p.
14. Turchin V.F. The Cybernetic Foundation of Mathematics. – The City College of the City Univeristy of New York, 1983. – 190 p.
15. Turchin V.F. The concept of a supercompiler // ACM Transactions on Programming Languages and Systems, Volume 8, Issue 3, 1986. – P.292-325.
16. Turchin V.F. Program transformation by supercompilation // Harald Ganzinger, Neil D. Jones (eds.), Programs as Data Objects, Proceedings of a Workshop (October 17-19, 1985, Copenhagen, Denmark). Lecture Notes in Computer Science, volume 217. – Springer, 1986. – P.257-281.
17. Turchin V.F. A Constructive Interpretation of the Full Set Theory // The Journal of Symbolic Logic, Volume 52, Issue 1, 1987. – P.172-201.
18. Turchin V.F., The algorithm of generalization in the supercompiler // Dines Bjørner, Andrei P. Ershov, Neil D. Jones (eds.), Partial Evaluation and Mixed Computation, Proceedings of the IFIP TC2 Workshop. – North-Holland, 1988. – P.531-549.
19. Turchin V.F. REFAL-5 Programming Guide and Reference Manual. – Holyoke MA: New England Publishing Co., 1989.
20. Turchin V.F. The Cybernetic Ontology of Action // Kybernetes, Volume 22, Issue 2, 1993. – P.10-30.
21. Turchin V.F. On Cybernetic Epistemology // Systems Research, Volume 10, Issue 1, 1993. – P.1-28.
22. Turchin V.F. Program transformation with metasystem transitions // The Journal of Functional Programming, Volume 3, Issue 3, 1993. – P.283-313.
23. Turchin V.F. A Dialogue on Metasystem Transition // World Futures, Volume 45, Issue 1-4, 1995. – P.5-58.
24. Turchin V.F. Metacomputation: Metasystem Transitions plus Supercompilation // Olivier Danvy, Robert Glück, Peter Thiemann (eds.), Dagstuhl Seminar on Partial Evaluation (February 12-16, 1996, Dagstuhl Castle, Germany). Lecture Notes in Computer Science, volume 1110. – Springer, 1996. – P.481-509.
25. Turchin V.F. Supercompilation: techniques and results // Dines Bjørner, Manfred Broy, Igor V. Pottosin (eds.), Perspectives of System Informatics, Second International Andrei Ershov Memorial Conference (June 25-28, 1996, Akademgorodok, Novosibirsk, Russia). Lecture Notes in Computer Science, volume 1181. – Springer, 1996. – P.227-248.
26. Абрамов С.М. Метавычисления и их приложения. – Москва: Наука. Физматлит, 1995. – 128 с.
27. Ершов А.П. О сущности трансляции // Программирование, № 5, 1977. – С.21-39.
28. Немытых А.П. Суперкомпилятор SCP4: общая структура. – М.: Editorial URSS, 2007.
29. Турчин В.Ф., Метаязык для формального описания алгоритмических языков // Цифровая вычислительная техника и программирование. – Москва: Советское радио, 1966. – С.116-124.
30. Турчин В.Ф. Метаалгоритмический язык // Кибернетика, № 4, 1968. – С.45-54.
31. Турчин В.Ф. Программирование на языке РЕФАЛ. Препринты ИПМ АН СССР № 41, № 43, № 44, № 47, № 49. – Москва: ИПМ АН СССР, 1972.
32. Турчин В.Ф. Эквивалентные преобразования рекурсивных функций, описанных на языке Рефал // Труды симпо- зиума «Теория и методы построения систем программирования» (Киев-Алушта). 1972. – С.31-42.
33. Турчин В.Ф., Эквивалентные преобразования программ на Рефале // Автоматизированная система управления строительством. Труды ЦНИПИАСС. – Москва: ЦНИПИАСС, 1974. – С.36-68.
34. Турчин В.Ф., РЕФАЛ-макрокод // Труды Всесоюзного семинара по вопросам макрогенерации. – Тбилиси: ВЦ АН ГССР, 1975. – С.150-165.
35. Турчин В.Ф. Инерция страха. Социализм и тоталитаризм. – Нью-Йорк: Изд-во «Хроника», 1978
36. Турчин В.Ф. Феномен науки: кибернетический подход к эволюции. – Москва: Наука, 1993. – 295 с.
37. Турчин В.Ф. и др. Базисный РЕФАЛ и его реализация на вычислительных машинах (методические рекомендации). Фонд алгоритмов и программ для ЭВМ в отрасли «Строительство», специальный раздел, Вып. V-40. – Москва: ЦНИПИАСС, 1977. – 258 с.

Об авторе: Институт прикладной математики им. М.В. Келдыша РАН
klimov@keldysh.ru

Материалы международной конференции SORUCOM 2011 (12–16 сентября 2011 года)
Статья помещена в музей 10.12.2012 с разрешения авторов