Введение к работе
Актуальность темы. Традиционный подход к программированию для фон-неймановской архитектуры (процедурное программирование с тремя классическими структурами управления, расширенное, объектно-ориентированными возможностями), приводящий к созданию огромных по объёму и потребляемым ресурсам программных систем, надежность которых снижается, исчерпал себя. Способ разбиения задач на подзадачи, естественным образом вытекающий из традиционного подхода (структуризация; оформление достаточно больших осмысленных совокупностей действий в виде процедур; поддержка прикладных областей посредством библиотек; упрятывание деталей реализации; организация методов работы с данными в виде иерархии классов объектов), больше не в сосгоянии справляться с возрастающей сложностью решаемых задач, то есть приводить более сложные современные задачи к оставшемуся приблизительно прежним уровню человеческих способностей. Как и прежде, организация кода в виде, наиболее удобном для восприятия и работы, остается проблемой первостепенной важности. Несмотря на возросшую выразительную силу алголоподоОных языков программирования, зазор между нашим восприятием решаемых задач и средствами, предлагаемыми традиционными языками программирования, все еще очень велик. Синтаксис языков программирования по-прежнему ориентирован на понятия, отражающие особенности пре-достагляемой языком виртуальной машины, а не решаемой задачи. Способ обработки программных единиц отражает логику работы аппаратуры, а не отношения между соответствующими программным единицам понятиями (к сожалению, не все понятия можно реализовать как объекты).. Серьезным недостатком является то. что организация программных единиц сильно отличается от организации знаний о решаемой задаче; например, одному понятию могут соответствовать разбросанные по всей программе фрагменты кода, расположение которых определяется только требуемой очередностью исполнения.
" Необходим поиск новых подходов, и одним из розмок.ннх путей выхода из кризиса является разработка новых методик организации исполнения кода, использующих нетрадиционные средства организации передач управления, нетрадиционные структуры управления и методы исполнения. Необходимо отметить, что традиционные алгодоподооннн языки (например, Си, Пасглль) очень плохо приспособлены для чакич
методов программирования. Накопленного к настоящему времени опыта достаточно, чтобы утверждать, что нестандартное применение механизма исполнения кода может приводить к простым, эффективным и надежным решениям сложных задач; тем не менее, применяемые для этого методы пока недостаточно исследованы, и их формальное описание отсутствует.
Цель настоящей диссертационной работы состояла в исследовании и формальном описании воздействия манипуляций с элементами стека интерпретации на поток управления, обосновании нетрадиционных структур управления и разработке новых схем исполнения кода.
Методика исследования. Для исследования механизмов исполнения язык Форт был выбран по причине простой структуры исполнимого кода и возможности вмешательства в процессы исполнения и порождения кода. (Еще одной отличительной чертой Форта является "мелкозернистая модульность" - всякая имеющая самостоятельный смысл часть программы становится программной единицей.) Изначально автором работы была создана система BacFORTHUJ, расширяющая язык Форт механизмом откатов и связанными с ним структурами управления. В дальнейшем система BacFORTH совершенствовалась и использовалась для практического опробования получаемых результатов.
В процессе работы с системой BacFORTH были исследованы методы воздействия на поток управления путем изменения стека интерпретатора и выявлены понятия, положенные в основу обобщения механизма откатов и формализма, описывающего механизм исполнения языка Форт. В результате экспериментов с самомодифицирующимися и динамически порождаемыми кодами был сформулирован критерий отличия программы от данных (программа и данные отличаются способом обработки), введено понятие позиции (активная для программы, пассивная для данных) и уточнено определение функциональной эквивалентности.
Был построен формализм, описывающий влияние манипуляций со стеком возвратов на поток управления и позволяющий проводить преобразования фрагментов кода путем эквивалентной замены по правилам математической логики. В основу <5ормализма легли выявленные при работе с системой BacFORTH основные свойства элементарных операций, необходимых для организации передач управления (это операции доступа к стеку вогкратов R> и >R, операции передачи управления с запоминанием адреса для г.Огврата Wn стеке возвратов
(вызов фрагмента кода), и операция EXIT передачи управления по адресу, находящемуся на вершине стека возвратов), понятия позиции и функциональной эквивалентности фрагментов кода.
Научная новизна. Предложен формализм, описывающий исполнение шитого кода с вкраплениями данных и влияние манипуляций с элементами стека интерпретатора (стека возвратов) на поток управления. Оформулирован критерий, позволяющий отличать код от вкраплений данных, введено понятие позиции, описывающее способ обработки кода или данных. Доказаны теоремы об эквивалентности вызовов 1 и 2 порядка, формулирующие, в каких случаях и каким образом вызов функции может Сыть заменен открытой подстановкой ее тела. Предложено обобщение механизма откатов.
Теоретическая и практическая ценность. ' Разработан метод анализа кода для случаев, когда в коде встречаются элементы данных и применяются манипуляции с адресами возвратов. Предложенный формализм может использоваться для доказательства корректности кода или при создании оптимизирующих компиляторов с языка Форт или других языков, расширенных возможностями воздействия на стек интерпретатора.
Язык Форт расширен механизмом откатов и новыми структурами управления (рекурсивный блок, два типа операторов отсечения, блок альтернатив, задание действий при откате, отрицание по неудаче, преобразование логического значения в успех/неуспех и наоборот, цикл AMONG), введены новые классы Форт-слов: итераторы и фильтры, что облегчает программирование переборов. Предложено обобщение механизма откатов.
Апробация работы. Результаты работы докладывались на семинарах лаборатории теории и технологии программирования, на международных конференциях: "EuroForth'94" (Винчестер, Великобритания, 1994), "euroFORTH'95" (Шлосс Дагштуль, ФРГ, 1995), "Региональная Информатика-95", (Санкт-Петербург, 1095), "euroFORTH'96" (Санкт-Петербург, 1996).
Публикации по работе. Основные результаты диссертации опубликованы в работах 1-73.
Объем и структура диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 56 наименований и приложения на дискете, содержит иесть рисунков и
имеет общий объем № страниц машинописного текста.