ЦЕЛЬ: Разработка эффективных инструментов для изучения и практического использования метавычислений, а также методики их применения для автоматизации программирования.

ОСНОВАНИЯ:

В 70-е годы Й.Футамура (1971), В.Турчин (1977), А.Ершов (1977) теоретически показали, что метавычисления (частичные вычисления, смешанные вычисления)

могут быть использованы для автоматического преобразования программ, в частности, интерпретаторов в компиляторы.

В 1985 году Н.Джоунсу и его коллегам (Дания) удалось построить простой метавычислитель, который оказался первым самоприменимым (что было основной

целью). Это дало возможность (как и было предсказано теорией) автоматически породить генератор компиляторов, который принимает на входе интерпретатор некоторого языка, а на выходе выдает компилятор того же языка (в выходной язык данного метавычислителя).

Параллельно В.Турчиным и его группой в Москве (т.е. нами) разрабатывается проект более сложного метавычислителя - суперкомпилятора, который пока еще (в силу его сложности) не самоприменим, но обладает задатками, которые обещают в случае успеха в деле самоприменения разрешить ряд трудностей, с которыми сталкиваются исследователи при использовании метавычислителей джонсовского типа. Нами накоплен значительный опыт по созданию и исследованию метавычислителей над языками Схема, Лисп, Рефал, а также опыт по отображению результата суперкомпиляции в эффективный машинный код (системы Рефал Плюс, Рефал-6).

Работы по созданию практических инструментов для метавычислений над разными языками ведут в настоящее время группы Н.Джоунса в Копенгагене, Й.Футамуры в Японии, П.Худака в Йельском университете (США), Д.Вейса в Стэнфордским университете (США) (перечень далеко не полный), и над языком Рефал - В.Турчиным в Нью-Йорке, Р.Глюком в Вене и нашей группой в Москве.

ОЖИДАЕМЫЕ РЕЗУЛЬТАТЫ:

Предполагается построить новую версию суперкомпилятора, уже самоприменимого, на основе развития идей Турчина (с учетом, в частности, результатов Джоунса и Сергея Романенко, создавшего практическую систему частичных вычислений Unmix над языком программирования Схема). Эта работа фактически уже ведется Глюком на базе суперкомпилятора Турчина, его опыт обнадеживает, но показывает необходимость (и направление) существенного перепроектирования всей системы.

В Москве вся работа ведется на базе языка Рефал, наиболее эффективную версию которого создали и развивают дальше Рутен Гурин и Сергей Романенко.

В рамках языка Рефал в настоящее время создается также новая версия суперкомпилятора с прозрачной и простой внутренней структурой для широкого использования в работах по метавычислениям. (Рутен Гурин и Сергей Абрамов)

Ожидается дальнейшее развитие возможностей отображения (генерации кода), главным образом в части автоматического выбора представлений данных для обрабатываемой программы. (Аркадий Климов)

До сих пор все метавычислители успешно работали лишь с чисто функциональными языками программирования, что ограничивает их применимость. Имеется в виду снять ограничения на чистую функциональность входного языка так, чтобы, не создавая помех метавычислителю, обеспечить его применимость ко многим задачам, которые на практике не укладываются в рамки функциональных языков (обработка сложных графов, моделирование и т.п). (Андрей Климов)

Идут интенсивные исследования в области автоматического обращения функций. Предложены расширения языка Рефал со встроенной операций обращения и в настоящее время ведется работа как по реализации расширенной версии языка, так и по разработке и практическому воплощению методов метавычислений для нее. (Александр Романенко)

Будут разработаны методики и учебное пособие (с емкими примерами) по использованию метавычислителей для автоматизации программирования. На основе первого опыта применения суперкомпилятора будут подготовлены пакеты для решения некоторых классов задач.

СОСТАВ МОСКОВСКОЙ ГРУППЫ:

Абрамов Сергей Михайлович, Институт программных систем РАН;

Гурин Рутен Федорович, Институт теоретической и экспериментальной физики;

Климов Андрей Валентинович, Институт прикл. математики им. М.В.Келдыша РАН;

Климов Аркадий Валентинович, Институт проблем передачи информации РАН;

Романенко Александр Юрьевич, Институт физической химии РАН;

ЦЕЛЬ: Разработка эффективных инструментов для изучения и практического использования некоторого подкласса МЕТАВЫЧИСЛЕНИЙ, а именно обращения программ, а также методики их применения для автоматизации рограммирования. Область метавычислений включает в себя преобразования и оптимизацию алгоритмов, например,специализацию, частичные и смешанные вычисления, суперкомпиляцию, и просто компиляцию. К этой же области относится обращение программ.

ОСНОВАНИЯ:

В 70-е годы Й.Футамура (1971), В.Турчин (.1977), А.Ершов (1977) теоретически показали, что метавычисления (частичные вычисления, смешанные вычисления) могут быть использованы для автоматического преобразования программ, в частности, интерпретаторов в компиляторы.

В 1985 году Н.Джоунсу и его коллегам (Дания) удалось построить простой метавычислитель, который оказался первым саиоприпенимым (что было основной целью). Это дало возможность (как и было предсказано теорией) автоматически породить генератор компиляторов, который принимает на входе интерпретатор некоторого языка, а на выходе выдает компилятор того же языка (в выходной язык

данного метавычисличеля ).

Параллельно В.Турчиным и его группой в Москве (т.е. нами) разрабатывается проект более сложного метавычислителя – суперкоьпилятора, который пока еще (в силу его сложности) не самоприменим, но обладает задатками, которые обещают в случае успеха в деле самоприменения разрешить ряд трудностей, с которыми сталкиваются исследователи при использовании метавычислителей джоунсовского типа.

Впервые обратную задачу в рамках метавычислений в языке Рефал рассматривал В.Ф.Турчин в 1972 году [Турчин 72], был предложен общий метод решения:

Реализация Универсального Решающего Алгоритма (УРА) и метавычисления над ним с помощью суперкомпилятора, в результате чего должны быть получены отдельные решения, обратные функции, выдающие эти решения, а также генератор таких обратных функций, было сделано несколько реализаций УРА (С.А.Романенко,С.М.Абрамов), однако, (возможно, по причине недостаточной мощности суперкомпилятора - к УРА его применить пока, невозможно)сколько-нибудь серьезных задач с помощью этой реализации решить не удалось.

В 1986-1987 годах я предложил другой подход к решению обратных задач; исследование возможности и получение алгоритмов непосредственного обращения функций - с тем чтобы исследовать и, возможно, облегчить продвижение по общему пути. Первые результаты - методы обращения графа конфигураций для Рефала - были представлены на первой конференции по частичным и смешанным вычислениям [Romanenko 88],

В результате дальнейшей работы были получены вполне эффективные методы обращения. В качестве базового средства сконструирован язык, являющийся модификацией известного языка программирования Рефал, представляющий собой разновидность функционально-логического языка [Reddy 86], объединяющего достоинства функционального и логического направлений в программировании. Основные чеpты предлагаемого языка: симметричность, множество-значные функции, переменные в данных - позволяют формулировать и решать обратные задачи естественным образом. Эти результаты были доложены на симпозиуме по “Частичным вычислениям и преобразованиям программ, основанным на семантике”, который состоялся в Йельском университете в 1991 году,и опубликованы в докладах симпозиума (Romanenko 91].

К зиме 1992 года первая версия языка была реализована на IBM PC, построен также инвертор функций, в настоящее время я завершаю работу над формальным описанием языка и метавычислений на нем и собираюсь продолжать реализацию с

тем, чтобы завершить создание простого суперкомпилятора в системе, а не только интерпретатора. Реализация осуществляется на языке Рефал Плюс, созданном

Р.Гуриным и С.Романенко [Турин,Романенко 91]. В ближайшее время предполагается исследовать возможность автоматического построения инвертора из интерпретатора

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

Перспективное применение этих методов можно рассматривать в узком и широком смысле.

В узком смысле предлагаемый подход позволяет формулировать и решать задачи автоматизации программирования в различных конкретных областях, к которым относятся, например, обращение трансляторов [Sarbo,Moritz 89], автоматическое построение компилятора НА язык, для которого задан интерпретатор (задача построения компилятора ДЛЯ языка по его интерпретатору, как было отмечено выше, уже решается с помощью частичных вычислений) и неявная спецификация программ вообще [Runcinian,Jagger 90].

В широком смысле описываемое направление можно рассматривать как часть более общего проекта использования метавычислений в программировании, основанного на языке Рефал, и развития новой парадигмы программирования, в которой предлагается новый подход к решению задач, традиционно относящихся к областям логического, объектно-ориентированного программирования и баз данных. При этом стоит особо подчеркнуть адекватность функциональных языков программирования для реализации на компьютерах с параллельной архитектурой, что выгодно отличает их от традиционных языков программирования. Распространение методов метавычислений в малодоступную для них ранее область объектно-ориентированного программирования [Klimov 91] позволит no-новому переформулировать задачи даже таких чисто “Фортранных” областей, как численный анализ, моделирование. Первые публикации, описывающие применение частичных вычислений в этих областях, уже появились [Berlin 89].

Л И Т Е Р А Т У Р А

С.М.Абрамов. Метавычисления и логическое программирование - в “Семиотические аспекты формализации интеллектуальной деятельности” (Всесоюзная школа-семинар “Боржоми-88”), Москва, 1988.

[Абрамов 91]

С.М.Абрамов. Метавычисления и логическое программирование. Программирование. #3. 1991.

[Гурин,Романенко 91]

Р.Ф.Гурин, С.А.Романенко. Язык программирования Рефал Плюс. М. 1991.

[Klimov 91]

A. Y. Romanenko. The Generation of Inverse Functions in Refal. Proceedings of the Workshop on Partial Evaluation and Mixed Computation, N.Jones, D.Bjorner, A.Ershov - eds. Gammel Avernaes, Denmark, 1988, pp. 427-444.

[Романенко 88]

А.Ю.Романенко. Построение обратных функций. - в “Семиотические аспекты формализации интеллектуальной деятельности” (Всесоюзная школа-семинар “Боржоми –88”), Москва, 1988.

А.Y.Romanenko. Inversion and Metacomputation, Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics Based Program Manipulation (June 1991, Yale University, New Haven, USA}, SIGPLAN Notices, Vol. 26, 1991, pp. 12-22.

[Ranciman, Jagger 90]

[Turchin 86 ]

Проект

СУБЪЕКТ ОБЩЕНИЯ

А.Ю.Романенко

Первоначальная идея проекта возникла у меня по прочтении последних работ Лефевра с изложением его рефлексивной модели человеческого суждения. Хотя он использует понятие "модель мира", реально в его работах используются не модели мира, не описания самих ситуаций и их образы, а бинарные оценки ситуаций или суждения о ситуациях и их рефлексивные отражения. Естественным расширением подели Лефевра мне кажется добавление в нее именно содержательных моделей мира, т.е. описание ситуаций и процедур перехода от одного множества ситуаций к другому. Бинарные суждения (“хорошо” и "плохо", "добро" и "зло") теперь связаны с ситуациями, а наша модель должна обладать памятью, хранящей эти процедуры, ситуации и их оценки. Естественная организация памяти - ассоциативная с поиском по образцу, причем образец может быть недоопределен (обобщенный образ). Для самодостаточности модели теперь не хватает только одного - связи с внешним миром, восприятия, позволяющего наполнять память, практически пустую вначале. Теперь модель обладает завершенностью и внутренней динамикой: при определенных допущениях о свойствах памяти, восприятия, суждения, ситуациях, процедурах может получиться довольно любопытная модель, которую я и называю пока субъектом общения.

Как было отмечено выше, модель субъекта общения содержит очень мало базовых конструкций: суждение, восприятие, память, ситуации, процедуры - проблема состоит в выборе того или иного представления (реализации) каждой из них. Модель суждений описана у Лефевра, для нашей модели этого достаточно. Адекватная модель восприятия должна быть построена для нашей системы - это совместная задача для психолога и кибернетика. Для моделирования памяти и описания ситуаций и процедур я предлагаю использовать существующие наработки и дальнейшее развитие языка Рефал и системы метавычислений на нем.

• компьютерная реализация модели Лефевра;

• обзор литературы, выбор и построение приемлемой модели восприятия;

• разработка единой модели памяти, описания ситуаций и процедур с рефлексией на базе Рефальского направления.