автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Механизмы исполнения кода в открытых расширяемых системах на основе шитого кода

од

На правах рукописи

■" О .

ГАСАНЕНКО Михаил Леонидович

МЕХАНИЗМЫ ИСПОЛНЕНИЯ КОДА В ОТКРЫТЫХ РАСШИРЯЕМЫХ СИСТЕМАХ НА ОСНОВЕ ШИТОГО КОДА

05.13.13. - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург - 1996

Работа выполнена в Санкт-Петербургском институте информатики и автоматизации РАН

Научный руководитель: доктор физико-математических наук,

профессор Баранов С.Н.

Официальные оппоненты: доктор физико-математических наук,

профессор Тузов В.А. кандидат физико-математических наук Плисс O.A.

Ведущая организация: Санкт-Петербургский государственный университет.

Защита состоится " " ^лмдЛрЯ 1996 г. в часов на заседании диссертационного совета Д.003.62.01 при Санкт-Петербургском институте информатики и автоматизации РАН по адресу: 199178, Санкт-Петербург 14 линия, д. 39.

С диссертацией можно ознакомиться в библиотеке диссертационного совета Д. 003.62,01.

"Автореферат разослан " " 1996 г.

Ученый секретарь

диссертационного совета ]

. кандидат технических наук у A.B. Копыдьцов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Традиционный подход к программированию для фон-неймановской архитектуры (процедурное программирование с тремя классическими структурами управления, расширенное, объектно-ориентированными возможностями), приводящий к созданию огромных по объёму и потребляемым ресурсам программных систем, надежность которых снижается, исчерпал себя. Способ разбиения задач на подзадачи, естественным образом вытекающий из традиционного подхода (структуризация; оформление достаточно больших осмысленных совокупностей действий в виде процедур; поддержка прикладных областей посредством библиотек; упрятывание деталей реализации; организация методов работы с данными в виде иерархии классов объектов), больше не в состоянии справляться с возрастающей сложностью решаемых задач, то есть приводить более сложные современные задачи к оставшемуся приблизительно прежним уровню человеческих способностей. Как и прежде, организация кода в виде, наиболее удобном для восприятия и работы, остается проблемой первостепенной важности. Несмотря на возросшую выразительную силу алголоподобных языков программирования, зазор между нашим восприятием решаемых задач и средствами, предлагаемыми традиционными языками программирования, все еще очень велик. Синтаксис языков программирования по-прежнему ориентирован на понятия, отражающие особенности предоставляемой языком виртуальной машины, а не решаемой задачи. Способ обработки программных единиц отражает логику работы аппаратуры, а не отношения между соответствующими программным единицам понятиями (к сожалению, не все понятия можно реализовать как объекты).. Серьезным недостатком является то. что организация программных единиц сильно отличается от организации знаний о решаемой задаче; например, одному понятию могут соответствовать разбросанные по всей программе фрагменты кода, расположение которых определяется только требуемой очередностью исполнения.

" Необходим поиск новых подходов, и одним из гозмотамх путей выхода из кризиса является разработка новых методик организации исполнения кода, использующих нетрадиционные средства организации передач управления, нетрадиционные структуры управления и методы исполнения. Необходимо отметить, что традиционные алгодоподоонн« языки (например, Си, Пасглль) очень плохо приспособлены для чакич

- г -

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

Цель настоящей диссертационной работы состояла в исследовании и формальном описании воздействия манипуляций с элементами стека интерпретации на поток управления, обосновании нетрадиционных структур управления и разработке новых схем исполнения кода.

Методика исследования. Для исследования механизмов исполнения язык Форт был выбран по причине простой структуры исполнимого кода и возможности вмешательства в процессы исполнения и порождения кода. (Еще одной отличительной чертой Форта является "мелкозернистая модульность" - всякая имеющая самостоятельный смысл часть программы становится программной единицей.) Изначально автором работы была создана система ВасГОИТНШ, расширяющая язык Форт механизмом откатов и связанными с ним структурами управления. В дальнейшем система ВасГОКТН совершенствовалась и использовалась для практического опробования получаемых результатов.

В процессе работы с системой ВасГСЖТН были исследованы методы воздействия на поток управления путем изменения стека интерпретатора и выявлены понятия, положенные в основу обобщения механизма откатов и формализма, описывающего механизм исполнения языка Форт. В результате экспериментов с самомодифицирующимися и динамически порождаемыми кодами был сформулирован критерий отличия программы от данных (программа и данные отличаются способом обработки), введено понятие позиции (активная для программы, пассивная для данных) и уточнено определение функциональной эквивалентности.

Был построен формализм, описывающий влияние манипуляций со стеком возвратов на поток управления и позволяющий проводить преобразования фрагментов кода путем эквивалентной замены по правилам математической логики. В основу «формализма легли выявленные при работе с системой ВасРСЖТН основные свойства элементарных операций, необходимых для организации передач управления (это операции доступа к стеку возвратов и операции передачи управлении с запоминанием адреса для возврата нь стеке возвратов

(вызов фрагмента кода), и операция EXIT передачи управления по адресу, находящемуся на вершине стека возвратов), понятия позиции и функциональной эквивалентности фрагментов кода.

Научная новизна. Предложен формализм, описывающий исполнение шитого кода с вкраплениями данных и влияние манипуляций с элементами стека интерпретатора (стека возвратов) на поток управления. Сформулирован критерий, позволяющий отличать код от вкраплений данных, введено понятие позиции, описывающее способ обработки кода или данных. Доказаны теоремы оС эквивалентности вызовов 1 и 2 порядка, формулирующие, в каких случаях и каким образом вызов функции может Сыть заменен открытой подстановкой ее тела. Предложено обобщение механизма откатов.

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

Язык Форт расширен механизмом откатов и новыми структурами управления (рекурсивный блок, два типа операторов отсечения, блок альтернатив, задание действий при откате, отрицание по неудаче, преобразование логического значения в успех/неуспех и наоборот, цикл AMONG), введены новые классы Форт-слов: итераторы и фильтры, что облегчает программирование переборов. Предложено обобщение механизма откатов.

Апробация работы. Результаты работы докладывались на семинарах лаборатории теории и технологии программирования, на международных конференциях: "EuroForth'94" (Винчестер, Великобритания, 1994), "euroFORTH'95" (Шлосс Дагштуль, ФРГ, 1995), "Региональная Информатика-95", (Санкт-Петербург, 1095), "euroFORTH'96" (Санкт-Петербург, 1996).

Публикации по работе. Основные результаты диссертации опубликованы в работах 11-73.

Объем и структура диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 56 наименований и приложения на дискете, содержит шесть рисунков и

имеет общий объем № страниц машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дана общая характеристика диссертационной работы: сформулированы актуальность проблемч, цель работы, методика исследования, научная новизна и теоретическая и практическая ценность.

В первой главе проведен обзор методов программирования, связанных с нестандартным использованием механизма исполнения кода и воздействием на стек интерпретатора. Описывается архитектура стековой машины с открытым интерпретатором и обосновывается, почему эта архитектура является наиболее удобным объектом для исследования того, как изменения, производимые на стеке интерпретатора, воздействуют на поток управления. Проведен обзор методов программирования, опирающихся на нестандартное использование интерпретатора кода и стека возвратов языка Форт. Дан обзор состояния дел в области формализации языка Форт (по материалам конференций EuroForth и Rochester Forth Conference за 1989-1995 гг., а также отечественных научных изданий за 1984-1995 гг.).

В современных ангелоподобных языках программирования (типичными примерами могут служить реализации языков С и Pascal для IBM PC фирмы Borland) операции обращения.к процедуре и возврата из нее являются сложными операциями, состоящими из, соответственно, создания записи .активации и передачи управления процедуре, и удаления записи активации и передачи управления назад. Методики организации передач управления путем изменения информации интерпретатора легче всего реализуются на стековсй машине с отдельным стоком возвратов. Все данные передаются черев стек данных, а записи активации вырождаются в ¿адреса возврата, хранящиеся на стеке возвратов. Появляется возможность выполнения амшк процедурами операций создания, удаления и подмены адресов возврата, т.е. записей активации. Интерпретатор кода с фиксированным алгоритмам работы, к стеку которого возможен доступ из программы, назван открытии интерпретатором. За кодом, используемым откршмм интерпретатором, оставлено традиционное фортовоко-:' название "шитый код".

У

Доступ к стеку интерпретации можно рассмотреть и с несколько иной точки зрения. Стек, на котором при вызове создаются записи активации, является стеком только с точки зрения механизма отведения памяти: к параметрам и переменным, расположенным в записи активации, допускается произвольный доступ. В отношении адресов возврата, однако, действуют более строгие ограничения: эти адреса создаются и обрабатываются только интерпретатором кода в соответствии с принципом L1F0 ("последним вошел - первым вышел"). В работе показано, что отход от этих ограничений в отношении адресов возврата полезен и открывает новые возможности (в частности, позволяет реализовывать нетрадиционные структуры управления и методы исполнения, такие, как бэктрекинг или исполнение, управляемое данными, известное также как процессно-ориентированное программирование или data-driven approach).

Среди методов программирования, использующих стек возвратов, наибольший интерес для нас представляют методы организации передач управления. Обычно для этого определяется вспомогательная процедура; после того, как эта процедура вызвана, на стеке возвратов находятся указатели текущей позиции всех исполняемых фрагментов шитого кода, кроме кода самой вспомогательной процедуры (позиция в ее коде хранится в указателе интерпретации IP). Вспомогательная процедура изменяет содержимое стека возвратов; до тех пор, пока не выполнен выход из вспомогательной процедуры, эти изменения не вызывают передачи управления. При выходе из вспомогательной процедуры IP загружается значением с вершины стека возвратов, т.е. происходит передача управления в соответствующее место (см. рис. 1 а-з).

Сделан обзор методов программирования на Форте, использующих манипуляции адресами возврата. Среди них особое место занимает независимо появившаяся в СССР и на Западе методика исполнения данных (data-driven approach, процессно-ориентированное программирование), основная идея которой состоит з том, что действия по обработке данных ассоциируются с самими данными, а задача просмотра данных, их анализа и и выполнения соответствующих действий БОБЛОжена на интерпретатор данных. При этом присущая данным структурированность. выявляемая сравнительно несложным интерпре-

I (CALL) |ref(»31> |

all a12

a13

a21 a

| EXIT |

a22

| R> | PUP | REF-t [ >R | REF® | >R | ЕХГт] a31 a32 аЗЗ а34 а35 а36 а37

6

S г а

S 3 р В а ш

& 8 <

с a

a J а» л к а>

н г &

S

к

в

1-1

I '■" IRP

а12

а13

a21

a 13

a13

I '" Irp

-rp

a/7

a31

a37

a21

a22

a 13

в г д e ж з

Рис.1. Организация передачи управления посредством изменения содержимого стека интерпретации на примере слова (CALL), осуществляющего вызов фрагмента кода, ссылка на который скомпилирована непосредственно за словом (CALL). Слово (CALL) определено как: : (CALL) R> DUP REF+ >R REF@ >R ;

снять адрес (a 12) со стека возвратов; продублировать; к одной копии а12 прибавить размер ссылки на шитый код (получить а 13), поместить на стек возвратов; из второй копии а12 (адреса ссылки на шитый код) получить адрес вызываемого фрагмента кода (а21); поместить его на стек возвратов; выйти из процедуры (при этом вершина стека возвратов загружается в IP, т.е. становится вершиной стека интерпретации).

а - код, использующий слово (CALL); 6 - скомпилированный код функции (CALL); в - стек интерпретации до вызова слова (CALL); г - стек интерпретации сразу после вызова слова (CALL); д - стек и in ерпретации перед выходом из слова (CALL); с - стек интерпретации после выхода из слова ' (CALL); ж - стек интерпретации перед выходом из вызванного словом (CALL) фрагмента кода; з - стек интерпретации после выхода из вызванного словом (CALL) фрагмента кода. Условные обозначения: all, а12, ...-адреса элементов шитого кода.

IP - "указатель интерпретации" - вершина стека интерпретации. Изменение IP влечет немедленную передачу управления.

Стек возвратов - содержит все элементы стека интерпретации, за исключением вершины. Изменения на стеке возвратов не приводят к немедленной передаче > правления:

RP - указатель вершины стека возвратов.

ret\a21) - ссылка на фрагмент шитого кода, начинающийся по адресу а21.

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

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

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

Приводится обзор двух циклов работ по формализации языка Форт, проведенных Я.Пёйалом (Тартусский университет, Эстония) и Б.Стоддартом и П.Нэггсом (B.Stoddart, P.Knaggs, Teesside Univerclty, Великобритания). Первый из этих подходов позволяет проверять корректность только стековых эффектов Форт-программ (что, однако, дает возможность' диагностировать большинство ошибок), второй позволяет следить за состоянием всей системы. Оба подхода работают исключительно в предположении о последовательном исполнении кода (структуры управления являются особыми случаями и не разбиваются на более элементарные понятия), ввиду чего эти формализмы неприменимы для анализа передач управления, вызываемых изменениями на стеке возвратов. Подход, предложенный наш, позволяет анализировать нестандартные передачи управления, вызываемые манипуляциями со стеком возвратов, дополняя существующие подходы.

Вторая глава посвящена описанию методики использования манипуляций адресами возврата для организации передач управления. За основу модельной системы - стековой машины с открытым интерпретатором - взят ANSI-стандарт языка Форт (American National Standard for Information Systems - Programming Languages - Forth, ANSI X3.215-1934), принятый в 1994 г., и сделаны дополнительные пред-

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

Для описания эффекта команд передачи управления предложены диаграммы стека интерпретации - запись, аналогичная диаграммам стекового эффекта. Диаграмма изменения стека интерпретации выглядит как

( R&IP: состояние-до — состояние-после )

последние элементы состояний стека интерпретации, изображенных на диаграмме, соответствуют IP, остальные - стеку возвратов.

В третьей главе описывается экспериментальная система BacFORTH, являющаяся расширением языка Форт механизмом откатов (backtracking). Система BacFORTH включает в себя набор нетрадиционных структур управления, которые могут использоваться совместно с традиционными, увеличивая выразительную силу языка. Описывается методика эффективной реализации механизма откатов путем нестандартного использования адресного интерпретатора. Система BacFORTH послужила основой для обобщения механизма откатов, описанного в главе 5, и сыграла значительную роль при работе в области формализации механизма исполнения языка Форт (глава'4).

Система BacFORTH включает в себя следующие нетрадиционные структуры управления:

- конструкцию START.. .DIVE.. .EMERGE (рекурсивный блок), позволяющую реализовать' рекурсию без вспомогательных рекурсивных процедур;'

- структурный оператор отсечения, позволяющий задавать границы, в пределах которых производится отсечение;

- отлаженный оператор отсечения (также структурный), позволяющий отложить принятие решения о том, нужно ли отсечение на

указанном участке;

- конструкции, осуществляющие преобразование логического значения в успех/неуспех и наоборот;

- конструкции, позволяющие задавать действия при откате;

- отрицание по неудаче;

- блок альтернатив, соответствующий прологовскому ИЛИ.

Система ВасРОКТН позволяет совместно использовать процедуры-предикаты и логические значения.

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

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

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

Четвертая глава посвящена исчислению, описывающему влияние манипуляций адресам/ возврата на поток упргшленпн. Вводятся основные понятия, используемые для формального описания таких действий, принимается система обозначений. Основные сьсшгтва фрагментов шитого кода аксиоматизируются, для прочих свойств, принимаются определения, исследуются свойства фрагментов шитого кода, оггера-

ций вызова и возврата, операторов перехода.

Введены понятия эквивалентности для фрагментов шитого кода и позиции для элементов и фрагментов шитого кода.

Эквивалентность фрагментов кода определяется как функциональная эквивалентность, однако это понятие также требует уточнения. В качестве примера приведен парадокс с функцией DUMP, распечатывающей шестнадцатиричный дамп своего кода. Любое изменение кода функции DUMP приведет к изменению распечатки, т.е. даже когда две версии процедуры DUMP очевидно должны быть эквивалентны, имеет место случай, когда их исполнение приводит к очевидно неэквивалентным результатам (на экран выводятся разные тексты).

Ключ к разрешению этого парадокса в том, что в приведенном примере код функции DUMP выступает и в роли программы, и в роли данных. Два эквивалентных (но не совпадающих) фрагмента кода, переданные как данные функции DUMP, приводят к несовпадающим результатам. Однако в чем же тогда отличие программы от данных? Отличие программы от данных - способ обработки. Программа обрабатывается только одним способом - исполнением с помощью интерпретатора кода, данные обрабатываются любыми другими методами.

Вводится понятие позиции, (название подчеркивает, что способ обработки зависит не от самого элемента шитого кода, а от контекста, в котором он находится).

Определение. Элемент шитого кода находится в активной позиции, если он обрабатывается только посредством интерпретатора кода. Позиция называется пассивной, если элемент шитого кода служит в качестве данных для одной из функций и интерпретатором кода не обрабатывается. В противном случае (если элемент шитого кода обрабатывается и как код, и как данные) позиция называется смешанной. Позиция называется безразличной, если элемент шитого кода не обрабатывается ничем. Она является частным случаем как активной позиции, так и пассивной.

Для фрагментов шитого кода понятие позиции вводится несколько иначе.

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

фрагмента шитого кода; фрагмент шитого кода может содержать и элементы данных, используемые только им самим).

Модуль но-уровн ев ий подход при построении, теории. При построении исчисления мы пользуемся знаниями о стековых аффектах фор-товских слов. Любой программист легко может предсказать стековые эффекты; кроме того, есть формализмы, которые позволяют сделать это же более строго. Эти неформальные знания, равно как и формальные системы, не являются частью нашего исчисления. Поэтому мы объявляем формальные и неформальные знания двумя взаимозаменяемыми модулями, после чего можем пользоваться любым из них (важно, что и те, и другие знания корректны).

Фундаментальным для фрагмента шитого кода свойством оказывается свойство игнорировать верхний элемент стека (т.е. не зависеть от Еерхнего элемента стека и не изменять его). Вводится опе-. ация : если I - фрагмент шитого кода, то ( Ь ) - фрагмент кода, который ведет себя как I, но игнорирует верхний элемент ^ стека: для любого значения N (М обозначает также фрагмент кода, оставляющий N на вершине стека):

N 51 ( Ь ) — I N

где символ *» обозначает эквивалентность фрагментов кода.

Аналогично вводится операция 1?1: И( I ) - фрагмент кода, который ведет себя как Ь, но игнорирует верхний элемент стека возвратов. Определяется свойстзо Э1: 1:31 (фрагмент кода 1 обладает свойством 51) если существует фрагмент кода х такой, что I 51( х ). Исследуются свойства операции 51( I ), вводится обратная операция 31-1)( Ь ).

Определение. Вызовом 1 порядка фрагмента шитого кода I называется помещение адреса I на вершину стека интерпретации (т.е. это передача управления с сохранениям адреса для возврата).

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

Теорема 1. (Эквивалентности вызова 1 порядка.)

Фрагмент кода Ь функционально эгаивзлентен вызову фрагмента кода

К1( I ). В принятой к тексте диссертации системе обозначений это

записывается как

[г Й1( Ь ) ; '] == Ь

Следствие: если фрагмент кода Ь не зависит от стека, возвратов, его вызов эквивалентен открытой подстановке Ь.

[г ; '3 == Ь

Описываются свойства операций перехода, из них выводятся свойства условного оператора. Доказывается корректность переопределения команд перехода через высокоуровневые процедуры, с использованием манипуляций со стеком возвратов.

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

Вводится понятие шитого кода 2 порядка - кода, исполняемого с использованием механизма откатов, реализованного по схеме "успех как вызов продолжения".

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

Определение. Вызовом 2 порядка называется такая передача управления вызываемому фрагменту кода, при которой адрес продолже-

ния помещается на L-стек, а на стеке возвратов оставляется информация о том, что при откате нужно убрать адрес продолжения с L-стека и передать управление фрагменту кода,, адрес которого находится на вершине стека возвратов.

Определение. Выходом Z порядка называется 1-вызов (т.е. вызов 1 порядка) продолжения.

Определяется понятие Ь-эквивалентности - эквивалентности при условии, что соблюдаются соглашения, применяющиеся при использовании механизма откатов. Запись (b) х у означает, что фрагмент кода х b-эквивалентен фрагменту кода у. Если х -« у , то и (Ь) х -- у .

Определяется операция BS1( t ), являвшаяся аналогом SI( t ) для исполнения с применением механизма откатов; аналогичная one рация BL1( t ) вводится и для L-стека; исследуются их свойства.

Определение. BS1( t ) - это фрагмент кода, ведущий себя как t, но игнорирующий вершину стека и при "прямом" исполнении, и при откате. В принятой в тексте диссертации системе обозначений это записывается как

BS1( t:RE ) - это такой фрагмент шитого кода, что

(b) N BS1( t ) >>:US1EI 'г[ N ; ] t N DROPS

Аналогично, BL1( t ) игнорирует ьершину стека продолжений и при прохождении вперед, и при откате.

Доказывается теорема эквивалентности вызова 2 порядка:

Теорема Z. (Эквивалентности вызова 2 порядка.)

2-вызов фрагмента кода BL1( t ) b-эквивалентен фрагменту кода t :

(b) Сг PRO BL1( t ) CONT ; ' ] t

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

Описывается оператор цикла AMONG, расширяющий гозмохшх г и механизма откатов. Механизм сткатсв может применяв ся н.г.и ¡'.лк средство реализации лои'.'.т р*'ше>шд "к глуоину", :ли к.чк с^длтао орг гишзацми перебора. t. первом мг/ч.че откат означает. что о;с[хд-

ная альтернатива отвергается (и необходимо восстановить измененные при ее опробовании структуры данных), во втором - что обработка очередного значения закончена, и должно быть выработано следующее. К сожалению, применять механизм откатов для того и другого одновременно возможно далеко не всегда. Во многих случаях организовать перебор вариантов с помощью классического (принятого в языках ПРОЛОГ и ПЛЭНЕР) механизма откатов нельзя. В цикле вида

<итератор> <тело>

когда итератор вырабатывает успех, управление передается в тело; когда тело завершается неуспехом, управление возвращается обратно в итератор. Недостатком этой схемы является то, что передать управление в итератор после успеха <тела>, то есть запросить следующее значение, не отвергая предыдущего (и не восстанавливая■измененные при его обработке данные), невозможно. Примером задачи, в которой нужно именно это, может служить задача порождения остов-ных деревьев ориентированного графа. При организации же перебора с помощью обычного цикла (или хвостовой рекурсии, как это делается в языке ПРОЛОГ) теряется возможность иметь модуль, отвечающий за перебор. Конструкция •

AMONG <итератор> EACH <тело> ITERATE <дальнейшие_действия>

передает управление итератору для Еыработки нового значения после успеха тела; при неуспехе тела состояние итератора восстанавливается .

Итератор здесь работает как сопроцесс со своим временем. После успеха тела создается новая копия процесса-итератора, в которую и делается откат (копирование сводится к копированию участка стека возвратов). При откате из тела делается откат к предыдущей копии процесса-итератора, и управление попадает в точку возврата, поставленную телом на предыдущей итерации.

Вводится понятие шитого кода i порядка для произвольного натурального i. Шитый код (ШК) 1 порядка - это применяемый в языке Фпрт шитый код, исполняемый интерпретатором с одним стеком (стеком возвратов; стек данных к интерпретатору не относится). Действие Фрагмента ШК (Ш1К) описывается двумя диаграммами стека (вхо-

да и выхода).

Шитый код 1 порядка получается применением метода "успех как вызов продолжения" к коду (Ы) порядка. Для хранения адресов продолжений заводится новый стек. Для исполнения ШК 1 порядка используется интерпретатор с 1 стеками; число состояний стека данных, описывающих эффект процедуры 1 порядка, равно 1 степени числа 2.

Шитый код второго порядка используется в системе ВасРСЖТН и пригоден для реализации языка ПРОЛОГ. Шитый код 3 порядка применен пока только в одной задаче - экспериментальной программе, выполняющей синтаксический анализ предложения на русском языке при известной морфологической информации.

Теоретическое значение понятий кода 1, 2 и 3 порядков. Существовали е различных способов исполнения кода позволило ввести .онятие механизма исполнения кода и воспринимать любой конкретный механизм исполнения как один из множества возможных. Механизмы исполнения кода 2 и 3 порядков являются примерами нетрадиционных механизмов исполнения кода.

В заключении изложены основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТН

1. Разработала методика эффективной реализации механизма откатов. Язык Форт расширен механизмом откатов и новыми структурами управления (рекурсивный блок, дез типа операторов отсечения, блок альтернатив, задание действий при откате, отрицание по неудаче, преобразование логического значения в успех/неуспех и наоборот). В язык введены новые классы слов - откатные итераторы и фильтры.

2. Дано формальное описание исполнения шитого кода с вкраплениями данных и воздействия манипуляций с адресами возврата на поток управления. Доказаны теоремы об эквивалентности вызовов 1 и 2 порядка.

3. Предложено обобшение механизма перебора с откатом. Введены понятия шитого кода 1, С и 3 порядков. Структура АМОМв позволяет откатному итератору управлять циклом с откатным телом, ¡цитируя откат в итератор при успехе тела.

4. Создана и внедрена в двух организациях чкипери.мйнт«нал система ВасГОЕТН, реализующая предложенные структуры управления.

Публикации автора по теме диссертации:

1. Гасаненко М.Л. Новые-синтаксические конструкции и бэктрекинг для языка Форт.//Проблемы технологии программирования. - СПб: СПИИРАН, 1993. - С.148-162.

2. Гасаненко М.Л. Формализация механизма передачи управления языка Форт.//IV Санкт-Петербургская международная конференция "Региональная Информатика-95", С.-Петербург, 15-18 мая 1995, тезисы докладов. - СПб:СПОИСУ, 1995. - С.129-130.

3. Gassanenko, М.L. BacFORTH: An Approach to Mew Control Structures.//Proc. of the EuroForth'94 conference, 4-6 November 1994, Royal Hotel, Winchester, UK. - P.39-41.

4. Gassanenko, M.L. Combined Addressing Model for 8086 Processor.//Proc. of the EuroForth'94 conference, 4->6 November 1994, Royal Hotel, Winchester, UK. - P.13-16.

5. Gassanenko, M.L. Formalization of Return Addresses Manipulations and Control Transfers.//Proc. of the euroFORTH'95 conference, 27-29 October 1995, International Centre for .Informatics, Dagstuhl Castle, Germany. - 18 p.

6. Gassanenko, M.L. Formalization of Backtracking in Forth. //Proc. of the euroFORTH'96 Conf., 4-6 October 1996. Hotel Rus, St.Petersbuig, Russia. - 26 p.

7. Gassanenko, M.L. Enhancing the Capabilities of Backtracking.//Proc. of the euroFORTH'96 Conf., 4-6 October 1996, Hotel Rus, St.Petersburg, Russia. - 9 p.

Надписано в печать'/"'/ЬТирлжШ Здки Ni

Отпечатано о И шгельегне С'ПбГТУ 19524. Слнкт-ПстсрСда, Падитстпчсска» ул., 29