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

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ

Р Г Б ОД

л >•■ nun <ппр На правах рукописи

j ЖЩ UJO УДК 519.685: 681.3.068

ХАЛАТЯН Тигран Гургенович

РАЗВИТИЕ МЕТОДОВ И СРЕДСТВ ПРОГРАММИРОВАНИЯ НА ОСНОВЕ КОМПЬЮТЕРНОГО ИСЧИСЛЕНИЯ ДРЕВОВИДНЫХ СТРУКТУР

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва- 1997

Работа выполнена в Институте проблем управления Российской Академии наук

Научный руководитель -

кандидат технических наук, старший научный сотрудник Ю.С. Затуливетер

Официальные оппоненты:

доктор технических наук, профессор,

Э..А. Трахтёнгерц кандидат физико-математических наук, доцент, И.Б. Задыхайло

. Ведущая организация:

Научно-исследовательский вычислительный центр МГУ

на зас , аД002.68.01 Института

проблем управления по адресу: 117806, Москва, ГСП-7, ул. Профсоюзная, 65

С диссертацией можно ознакомиться в библиотеке Института проблем управления.

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

(НИВЦ МГУ)

1998 г. в

часов

Ученый секретарь специализированного совета к.т.н.

Е.В. Юркевич

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

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

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

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

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

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

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

Задачи работы:

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

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

. 3. Разработка эффективных способов мобильной реализации языка программирования, с локализацией машинно-зависимого ядра и оптимизацией динамического распределения памяти.

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

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

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

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

Реализованные средства программирования могу г использоваться для создания программного продукта в исследовательских и научных целях. Сферы практического применения ограничены лишь недостаточным для коммерческих применений сервисом и использованием операционной системы MS-DOS.

Практическая реализация.

Разработанный в диссертации язык ПАРСЕК использован в прикладных работах Института проблем управления РАН как инструмент программирования.

Результаты диссертации использованы в разработках Центра компьютерных технологий "Комтек-М" РАЕН для исследований по улучшению характеристик ядра действующей информационно-управляющей системы.

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

ЛIIp<)<7aimsi pauoi i.i. Но теме диссертации был сделан доклад на Ш Международной конференции "Развитие и применение oi крьп ых систем" (Москва. 1996 г.).

Материалы диссертации использовались в курсе лекций "Архитектура вычислительных систем", прочитанных студентам V курса МФТИ, специализирующихся по кафедре "Телекоммуникационные системы, комплексы и сети" (Москва,. 1996-97 г.)

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

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

Во_видении даегся постановка задачи и обоснование

актуальности работы. Приведено краткое содержание -диссертации.

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

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

В данной главе характеризуются также истоки и состояние проблемы программирования посредством демонстрации частных примеров/решений (Programming by Demonstration). Анализируются существующие подходы индуктивного вывода (Inductive Inference), лежащие в основе направления известного под названием "обучение по примерам" (Learning by Example). Показаны нарастающие тенденции влияния этой тематики на ' формирование нового направления программирования по частным решениям, ориентированного на конечного пользователя.

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

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

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

Целенаправленная ориентация на структуры предполагает использование древовидных структур не только фрагментарно-эврнстнчески, но и на уровне универсальной сквозной 4

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

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

Еще одним узким местом современных технологий

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

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

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

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

Теория индуктивного вывода (Gold, 1967; Angluin, 1980-83) представляет собой математическую модель обучения по примерам. Примеры делятся на позитивные и негативные (контрпримеры): Синтезируемая функция индуктивно выводится из позитивных примеров, а негативные примеры помогают отсечь ложные обобщения. Для решения задачи надо выбрать пространство правил (гипотезу), в котором надо искать решение и в котором решение mojjcho найти.

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

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

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

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

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

Практические системы обладают встроенной "базой знаний", в которую заложена информация о связях между объектами системы в данной предметной области, что позволяет системе «угадывать» хорошие решения.

Другим методом, помогающим преодолеть проблему «большого количества примеров». является постепенная адаптация системы в ходе работы пользователя. Если пользователь повторяет одни и те же действия в процессе работы, система может запоминать их последовательность и повторять их автоматически. В таких случаях теряется не так много времени на обучение большому количеству примеров, так как процесс обучения и процесс работы совмещены.

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

Вот почему текстовые редакторы (TELS, Tourmaline), графические редакторы (Metamouse, Chimera, The Geometer's Sketchpad, Mondrian, Triggers), а также системы для работы с документами (SmallStar, Eager) составляют абсолютное бопьшинство практических индуктивных систем.

Другими применениями индуктивных систем являются средства программирования (синтеза программ) на конкретных данных (Pygmalion, Tinker), средства создания интерфейсов пользователя (Peridot, Gamet).

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

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

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

д При описании информационных объектов и

_а систем используются формулировки типа: А состоит ^ из а, Ь, с. В теории множеств этой формулировке соответствует дефиниция А={а,Ь,с}. В нашем случае для "раскрытия" объекта используется элементарное " "А дерево в геометрической форме (верхний рисунок), ■уа Для каждого из компонентов а, Ь, с можно

"а1 применить это же правило раскрытия. Получается иерархическая структура в "вертикальной" древовидной форме (нижний рисунок).

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

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

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

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

1

1

_____ На третьем этапе производится непосредственно

программирование, которое и завершает построение компьютерной реализации задачи в целом.

В общем виде математическое решение задачи имеет следующий вид: Я[0]=Я<>,

Ч[1+1]=П(яИ. ЧН]. я[1-2], ..., ЧГР1. х[1], 1),

у[1]=Г2(яМ, я[М], Ч[1-2].....Ч[0], х[(], I),

1=0,1,2,...;

где яр], хЭД, у[(] - древовидные структуры, изменяющиеся со временем, причем хЭДеУ, уЭДеХ, О.Х/УсО, О -

множество всех деревьев. При этом яЭД - текущее состояние, хМ -внешние воздействия, уОД - реакция системы на внешние воздействия.

Функции П(), Г2( ) определяют изменение переменных я|д], у И на каждом такте времени 1=0,1,2,... . Эти функции также определяются посредством деревьев.

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

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

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

Дерево Номер Содер- Связь Связь Связь

вершины жимое prev deep next

TOBJ 1 OBJ - с верш. 2 -

FrA 2 A с верш. 1 с верш. 3 с верш. 5

1(-а1 3 a1 с верш. 2 - с верш. 4

| La2 4 a2 с верш. 3 - -

LB 5 В с верш. 2 - - -

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

третьей главе изложено описание языка ПАРСЕК -

раг

-"par

-А

LB

-'seq

-С

LD

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

*имя _программы*> Стендовая система програм-

-т rout начало программы мирования ПАРСЕК реализована

в среде MS-DOS. Текст программы и данные формируются в специальном редакторе, поддерживающем обработку древовидных конструкций. Транслятор (препроцессор) древовидной программы вырабатывает текст Си-программы, которая затем средствами Турбо-Си транслируется в исполняемый ЕХЕ-модуль.

На рисунке приведена структура ПАРСЕК-программ. Символьные строки в правой части вершины дерева после I ■ первого пробела образуют ком-

[в ментарий (например: строка

" "начало программы").

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

-r'parform список параметров

■'subrout раздел подпрограмм -|-@<*имя _функции 1 *> ■'parform

Т'return возврат из функции В

-т-@<*имя_функции 2*> -j-'parform -в -в

т

•'return В

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

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

Начальными конструкциями языка ПАРСЕК являются

древовидная запись операций присваивания и подстановки аргументов функции. ___

Присваивание операция функция выражение

Формульный вид а:=Ь 1+3 J1(x,y) @f2(x,y) а=х+3

Древовидная запись г-Н сг tu 43 F У j@f2 -х Ц' VL -х •"3

В язык включены также традиционные конструкции:

условный оператор - if, многовариантный выбор - case, цикл с предусловием - while - do, цикл с постусловием - repeat - until, операторы выхода из цикла - continue и break.

Далее в главе приведен список (в количестве 54) встроенных функций языка ПАРСЕК, включающий базовые функции работы с деревьями, работу со строками, работу с файлами и другие функции, типичные для языков программирования.

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

На рисунке приведен иллюстративный пример программы на языке ПАРСЕК, выводящей на экран результат сложения двух чисел, вводимых при запуске отранслированой программы через переменные x,v: --test.exe -3 7

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

jtest.tpt

L

rout

■'parform х

■у

.print

-х

V

В четвертой главе отражены особенности машинной реализации языка ПАРСЕК. Язык строится на математической основе в виде ограниченного универсального набора базовых конструкций, что существенно облегчает его «погружение» в компьютерную среду. Для воплощения принципов переносимости и ослабления машинной зависимости особое внимание уделено созданию ограниченного по объему машинно-зависимого ядра реализации, которое запрограммировано на языке Си.

р!а основе свойств исчисления древовидных структур и с учетом требований к эффективности излагаются общие принципы машинной ■ реализации языка. Язык ПАРСЕК разрабатывался как прототип инструментария, работающего в промежуточной информационно-компьютерной среде, который направлен на формирование единого информационного поля для данных и программ всех приложений независимо от компьютерных платформ. В данной среде программист формализует и интерпретирует объекты и системы на основе фундаментального свойства структурируемое™ информации.

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

Машинная реализация языка разбита на следующие уровни: 1. Машинный ( низовой). На этом уровне, в качестве типового компонента дерева, фигурирует объект "вершина". В форме ячейки цепного списка описана структура вершины и функции ее создания, уничтожения и изменения.

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

Программы низового уровня написаны на Си.

Базовый. На базовом уровне в форме цепного списка определенного вида описан объект дерево или древовидная

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

На базввом уровне решается задача организации ДС, как логической основы исчисления ДС.

Программы базового уровня написаны на Си с использованием объектов только машинного (низового) уровня.

3. Библиотечный (функциональный). На библиотечном уровне описаны функции работы с деревьями как с отдельными объекта ми. Сюда относятся функции ввода-вывода деревьев, функции преобразования деревьев, функции работы с содержимым вершин дерева и математические функции работы с переменными языка ПАРСЕК. К этому уровню относится и сам транслятор (препроцессор) с древовидного языка (функция обработки древовидной программы как частного случая деревьев).

Написан на Си с использованием объектов только базового

уровня.

Уровни 1-3 локализуют машинно-зависимое ядро языка.

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

5. Языки пользовательского уровня, в том числе и древовидные, предполагается реализовывать на языке нижнего уровня (ПАРСЕК). Приближение конструкций таких языков к привычным нотациям осуществляется на основе простого "древовидного стандарта", что должно существенно повлиять на их переносимость, надежность и простоту отладки.

Уровни 4-5 не зависят от машинных языков.

В конце главы исследуются вопросы динамического распределения памяти.

Языки низкого уровня (Ассемблер, Си) возлагают управление памятью на программиста. В этом они опираются на средства динамического распределения памяти операционных систем (например, MS-DOS, Windows 95/NT), которые позволяют программисту строить собственные эффективные решения по управлению памятью.

Языки высокого уровня (например, QBASIC и Visual BASIC фирмы Microsoft) используют встроенные решения, которые позволяют сильно упростить труд программиста, но не всегда позволяют ему достигать высокоэффективного использования ресурсов.

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

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

Алгоритмы динамического распределения можно условно разбить на две части: во-первых, собственно выделение и/или освобождение памяти по запросам, во-вторых, "сборка мусора", а именно уплотнение и переупорядочение памяти с целью использования так называемых "дырок" - свободных участков памяти ограниченной длины. Необходимость "сборки мусора" возникает поскольку программа непредсказуемым образом запрашивает участки памяти различных длин, так что не всегда удается размещать данные в освобождающиеся участки. При этом "сборка мусора" значительно понижает быстродействие и усложняет алгоритм распределения памяти.

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

В качестве оправной точки был использован алгоритм распределения памяти символьных строк, в котором вообще не проводится "сборка мусора"*'.

Перерасход памяти упомянутого метода удалось существенно снизить с помощью нового метода оптимизации

*) Суть алгоритма состоит в том, что строка не требует новой памяти, пока её длина изменяется в пределах выделенного участка памяти. Новый участок памяти выделяется, когда длина строки превысит длину предыдущего выделенного участка. При этом старый участок памяти далее не используется, образуя "дырку". В этом случае расход памяти на некоторых задачах зависит от числа запросов N и порядка N раз больше чем в случае статического распределения. (Под статическим распределением понимается выделение участка памяти определенной длины, если априори известна максимально возможная длина строки). Зависимость расхода памяти от числа запросов N требует чрезмерных затрат на "сборку мусора". 14

(названного парадоксальным) за счет выделения в процессе выполнения программы памяти с излишком, т.е. не сколько опрашивается, а больше. При каждом новом выделении памяти, её выделяется в к раз больше, чем длина последнего выделенного участка. Оказалось, что перерасход памяти в этом случае относительно статического распределения не зависит от- числа запросов 1\',а зависит только от коэффициента к. Была построена простая числовая функция выражения перерасхода. Задача поиска оптимального к свелась к нахождению минимума функции перерасхода. Был вычислен оптимальный коэффициент к=2. при котором значение функции перерасхода минимально. Доказано, что при "парадоксальном" методе перерасход памяти не может превышать 4-х кратный расход памяти статического распределения. Экспериментально подтверждено, что предложенный для ПАРСЕК способ управления памятью обеспечивает линейную зависимость расхода времени, в зависимости от повышения размера строк перемещаемых данных и общего количества данных программы, в то время как для других языков с автоматическим управлением памятью (например, QBAS1C и Visual BASIC фирмы Microsoft) характерно квадратичное возрастание временных затрат, обусловленных работой алгоритма сжатия. "Платой" за достигаемое быстродействие является хоть и неплотное, но контролируемое сверху, использование ресурса памяти.

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

Проблема индуктивного синтеза программ по демонстрациям частных примеров формулируется следующим образом. Дано:

1) Функциональный базис, в котором должно производиться индуктивное обобщение частных решений и который представлен:

во-первых, множеством вычислительных действий Y={Y|,Y2,...,Yn}, необходимых для построения общего решения;

во-вторых, набором предикатных (решающих) функций ф( Мф/ X •••. Фт( ))> необходимых для обусловленного связывания отдельных вычислительных действий из ¥ в общее решение.

2) Обучающая выборка частных решений Р'={Р,.....Рк}, где

каждое решение Р| (¡=1, 2, .... к) представлено вычислительной траекторией действий из V в виде последовательности действий Р>= {1 -» ... Уу}, решающей вычислительную задачу

частного примера Р^

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

В данной работе процедура обобщения строится и исследуется в ограничениях, присущих автоматной модели.

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

Математические блоки вычислительного устройства:

где: (У1]еОх - текущие входные данные, с5у[1]е13у - текущие выходные данные, МЩлОД - текущее значение совокупной памяти вычислительного устройства, У - множество базовых вычислительных действий, ф - базовый набор предикатных (решающих) функций.

Исполнительный блок обеспечивает реализацию

вычислительных действий из базового набора У по преобразованию данных в памяти М[1] и вычисляет значения х[1] предикатных функций (р над памятью КОД. Для реализации

действий У; £ V исполнительному блоку в момент времени I необходимо получить идентификатор/код команды, который несет переменная уОД е V, значение которой вырабатывает командный блок.

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

Чтобы синтезировать искомые автоматы (алгоритмы) общих решений командный блок вычислительного устройства заменяется на блок синтеза (см. рисунок).

Общая схеми синтеза программ:

Прежняя связь у[г] "размыкается", а на входы Р и Б поступают "обучающие" примеры (частные решения) в виде последовательности Р,еР имен действий из V, каждая из которых представляет собой обучающий пример в виде демонстрации детального решения ¿-го частного случая.

Рассмотрение проблемы проводится на примере конкретной алгоритмической задачи, а именно, синтеза алгоритма сортировки чисел по частным примерам. Пусть из входной последовательности положительных и отрицательных чисел необходимо получить две выходных последовательности содержащих отдельно положительные и отрицательные числа, например: {5-» -2-» 4-» -3} => {5-> 4} и {-2-> -3}, Для задачи сортировки исходные данные модели принимают вид:

1) Последовательность входных чисел: Ох = {5 -2 4 -3}, с!х[1] - элемент Р*.

2) Результат работы вычислительного устройства (выходные данные): = {5 4} и {-2 -3}, с!^] - элемент

3) Множество действий необходимых для реализации синтезируемого алгоритма сортировки:

У = {Начало, У^ У2, У3, Конец}, где Начало - начальное действие, У! - прочитать очередное число из входного набора, У2 - поместить число в набор положительных чисел, У3 -поместить число в набор отрицательных чисел, Конец -закрывающее действие.

4) Набор предикатных функций для вычисления свойств данных:

ф()=(ф|(). ФгО). гДе

гмгц. /0, входная последовательность пуста, Ф^ и)- \ 1) входная последовательность не пуста;

со (МГЙ)= -Г вх°Дное число меньше нуля, 2 11, входное число больше или равно нулю;

Значение набора условий задается общим выражением: Х=(Х1,Х2)=(ф,(ММ), ф2(М[ф).

5) Обучающая выборка примеров: Р={Р1,Рг,Р3},где

Р|={Начало Конец},

Р2= {Начало У1 У2 У! -> У3 Конец},

Р3= {Начало У, У3 У, У2 Конец}.

Выборка частных решений Р={Р1, Р2, ••., Р„}, позволяющая синтезировать искомый автомат истинного общего решения на лвается представительным наборов примеров (ПНП).

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

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

____Предлагаемая процедура синтеза состоит из следующих

этапов:

1. Начальное приближение к минимальному автомату.

Построение начального приближения к искомому автомаг у начинается с вычисления значений х[(| решающих функций ф на

дугах вычислительных траекторий частных примеров. Для этого надо в схеме синтеза подать на исполнительный блок вычислительного устройства последовательность команд-действий у[0 обучающих решений Р4еР и снять на выходе ВУ вычисленные значения хр] для каждого ур]. Эти значения

получаются путем вычисления ф(М[ф после исполнения каждой "команды" ур], 1=1,2,..., сопровождаемой изменением состояния памяти Мр]. Проинтерпретировав таким образом выполнение всех вычислительных траекторий Р, исполнительный блок

вычисляет значения предикатных функций хр] (сверху каждой стрелки):

(0.0) '

Р,= {Начало-» Конец}.

[И

(1,0) (1,1) (1,1) (0,0) (0,0)

Р2={ Начало-» У]-» У2-» У]-» Уз-» Конец},

|2] |1] [4| [5] 161

(1,0) (1,0) (1,0) (0,1) (0,1)

Р3= {Начало-» У,-» У3н> У,-» У2-> Конец}.

[7] [8] (9) [10] 111]

Обобщение начинается над проинтерпретированными траекториями путем склеивания всех однотипных вершин состояний (с одинаковыми действиями). Дуги переходов при этом не разрываются. После склеивания всех однотипных вершин получается квазиавтомат, возможный предшественник искомого в классе автоматов Мура алгоритма общего решения, у которого состояния взаимно однозначны действиям, так что |<3|=|У|. В том счучае, если квазиавтомат не содержит противоречий, то он представляет собой искомый, но лишь частично определенный автомат. Он имеет минимальное количество состояний, поскольку их количество равно количеству используемых действий КЗ^ПЛ (меньше быть не может из-за нарушения функциональной полноты).

2. Расщепление "неоднозначных" состояний. Переназначение путей по "расщетеннъш"состояниям.

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

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

В результате разбиения вершин, ставших причиной неоднозначности множество состояний нового автомата увеличивается, так что КЗиомеМ^Ч- Если проводить минимально-возможное количество разбиений, снимающих все неоднозначности, то полученный автомат будет минимально возможным без неоднозначностей. В работе построен эвристический алгоритм устранения противоречий путем расщепления вершин.

3. Доопределение функции перехода автомата.

Начальный автомат без неоднозначностей уже полностью раскрывает функцию А2( ) в системе уравнений искомого автомата Мура:

При этом функция перехода А1( ) определена лишь частично, на основе переходов, полученных из обучающих частных примеров. После первого и второго этапов синтеза, т.е. после устранения противоречий, имеем частично определенный автомат искомого обобщения, в котором автоматные переходы определены лишь для отдельных значений хЭД. Далее на рисунке представлена функция перехода А1^,х) (при я=СЬ) для частично определенного начального и полностью доопределенного искомого автомата. Здесь с0...с3 это полная группа событий - все возможные для рассматриваемого примера "сортировка"

Причем * С?к С1=х[д=ср(М[У)

с,[1] = А1(Ч[Ы],хМ), УМ = А2(Ч[ф, 1=1,2,...

(в котором набор ф имеет две двоичные компоненты) условия перехода т 0,. " ~ ------------------

Фрагмент начального

(частично определенного) автомата

Фрагмент искомого (полностью определенного) автомата

X А,((2з,х) Гк) X А,(0,д)

с„=(0,0) К С„=(0,0) . к

с,=(0,1) ? С,=(0,1) К

с2=(1,0) <21 С2=(1,0) С>1

С,=(1,1) ? СгУС3 Чз.) Сэ=(1,1) <21

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

В результате для определенной выше задачи "сортировка" процедура синтеза дает следующий автомат:

02®-

' (7) С,

(3)С,

(4)С2 (5)С4

С)=(0,~)= с, ус, набор пуст С2=(1.~) = с2ус3 набор не пуст

Сз=(~, о = с^с3 N>0 С4=(~,о) = с0ус, N<0

Автоматный переход на диаграмме происходит по дуге, помеченной С(. только в том случае, если х[(]==С,. т.е. совпадают

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

Знак ~ означает любое значение из {0,1} (если {0,1} -алфавит значений предикатных функций Например, запись С,=(0,~) означает, что переход произойдет по дуге помеченной С!, когда х[1]==(0,~), что равносильно дизъюнкции хр]=(0,0) V х[1]=(0,1)«х[(]=со V с5.

В завершении главы описана экспериментальная система синтеза программ по частным решениям в среде ПАРСЕК. Все начальные, промежуточные и конечные данные и программы представлены в виде древовидных структур, что служит основой для построения перспективных технологий формирования и индуктивного развития унифицированного информационного поля.

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

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

- -sorî a.tdt На рисунке (слева) представлена древовидная

структура, представляющая диаграмму переходов автомата задачи "сортировка". Дерево, представляющее искомый автомат, синтезируется системой обобщения и соответствует классической автоматной диаграмме переходов (предыдущий рисунок). На основании дерева автомата, формируется ПАРСЕК-программа, которая затем транслируется в исполняемый ехе - модуль.

В приложении 1 представлена технология работы в стендовой системе программирования ПАРСЕК, представляющей низовой уровень программирования, построенного по принципам классического (алгоритмического) стиля.

За 4 года разработки и апробации системы ПАРСЕК решались разнообразные задачи как демонстрационные, так и в рамках плановых работ института. В частности, с помощью технологии ПАРСЕК была разработана система структурно-функционального моделирования компьютерных архитектур и на ее основе построена модель вычислительного устройства, представляющего собой двухпроцессорный фрагмент высокопроизводительного решающего поля, предназначенный для размещения на одном кристалле СБИС. Работа выполнялась в рамках проекта по разработке параллельной ЭВМ, который проводился по ГПТП "Перспективные информационные технологии". Также была решена задача сжатия телетекста, многочисленные задачи числового и нечислового характера.

В приложении 2 представлена экспериментальная технология натурного программирования, реализованная в системе ПАРСЕК, которая дает представление о верхнем (пользовательском) уровне программирования, построенном в соответствии с принципами индуктивного синтеза программ по частным решениям.

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

t

rrv>u

-Начало

■х=о-

Конец

h-Q'

-Y 1

-гХ=~1 юг

Ц-х=~о

433

h-rQ2

-Y2

-гХ=0~ •-Конец

TST-

-Y3

-гХ=0~ •-Конец LrX=i~ 431

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

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

1) разработан процедурный язык ПАРСЕК и система программирования, поддерживающие исчисление древовидных структур, что обеспечило возможность унификации программ в едином информационном поле исчисления древовидных структур;

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

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

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

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

ПУБЛИКАЦИИ

Основное содержание диссертации отражено в следующих публикациях:

1. Затуливетер Ю.С., Халатян Т.Г. Принципы построения компьютерного исчисления древовидных структур с открытой интерпретацией. Материалы III Международной конференции "Развитие и применение открытых систем", -М., 1996, с.100-101

2. Затуливетер Ю.С., Халатян Т.Г. ПАРСЕК - язык компьютерного исчисления древовидных структур с открытой интерпретацией. Стендовый вариант системы программирования. -М., 1997 (Препринт / Институт проблем управления РАН). 71с.

3. Затуливетер Ю.С., Халатян Т.Г. Синтез общих алгоритмов по демонстрациям частных примеров (Автоматная модель обобщения по примерам). -М., 1997 (Препринт / Институт проблем управления РАН). 72с.

В совместных работах автором внесен следующий личный вклад. В [1] предложена форма списковой организации памяти для древовидных структур и экспериментально апробирован набор базовых функций. В [2] предложен ряд базовых конструкций языка ПАРСЕК, разработан и реализован транслятор (в виде препроцессора) языка ПАРСЕК в язык СИ, разработан и обоснован алгоритм динамического управления памятью. В плане развития методологии программирования на основе исчисления древовидных структур в [2] автором запрограммированы следующие задачи: моделирование сетей Петри, словарь с быстрым поиском слов, "ханойская башня", синтаксический анализ. В работе [3] проанализированы существующие подходы к решению проблем индуктивного вывода, в рамках автоматной модели синтеза программ по частным решениям разработаны и запрограммированы алгоритмы расщепления неоднозначных состояний и доопределения частичного автомата до полного, разработаны древовидные формы представления автоматов и построена экспериментальная система синтеза программ в среде ПАРСЕК.

tax. If) Tup-flff МП