Часть 5. S-FLOGOL-система функционально-логического программирования

5. S-FLOGOL-СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

ся возможности, допустимые как для задания позиционных, так и для клю-

чевых параметров. При этом надо учитывать, что в качестве имен парамет-

ров выступают их номера, что автоматически дает возможность использо-

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

Доступ к отношениям, определенным в других модулях информаци-

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

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

ношений, описанных в модулях-предках, можно не использовать квалифи-

цированные имена, если это согласуется с трактовкой списка родителей как описания их приоритета (в порядке уменьшения) для доступа к откры-

тым именам родителей и их предков.

5.2.2. Технология решения задач в S-FLOGOL-системе

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

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

прос к системе, вычисление этого отношения.

Отдельные модули информационной базы, сформированные при ра-

боте структурно-ориентированного текстового редактора системы, пред-

ставлены во внутреннем формате, не требующем дополнительного синтак-

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

FLOGOL: ЯЗЫК И СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 11

5. S-FLOGOL-СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

множества уже моделируются на уровне отношений, описываемых в грам-

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

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

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

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

ющих соответствующий элемент описания в доменном выражении. Выхо-

дами являются: сеть, представляющая правую часть элемента описания, и

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

тора системы происходит только пополнение множества правил граммати-

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

Трансляция запроса к системе. Запрос представляет собой реляцион-

ное выражение, условно рассматриваемое в корне доменного выражения – открытой части некоторого модуля информационной базы. Сам запрос в грамматике G1 представлен одним из правил для сорта OpenBase с неин-

дексированным именем Query. Аксиомой грамматики G1 является нетер-

минальный сорт Rules, а представленное им рекурсивное направленное от-

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

ношение, определенное запросом к системе. Имена нетерминальных сор-

тов в грамматике G2 представлены натуральными числами 0,1,..n. Отказ в

FLOGOL: ЯЗЫК И СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 12

5. S-FLOGOL-СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

языке S-FLOGOL от использования в операторах свертки не ограниченных сверху диапазонов натуральных чисел для задания значений переменных сверток гарантирует и существование числа n, и конечность графика зада-

ваемого грамматикой G1 направленного отношения, т.е. множества правил сетевой грамматики G2.

Вычисление отношения по грамматике G1 осуществляется сетевым ядром вычислений системы в режиме вычисления отношений на встроен-

ных в систему областях данных, в число которых входят конструкции (ис-

пользуется один нульарный и один бинарный конструктор) из натуральные чисел, строк и сетей в объединенном базисе грамматики G2, рассматрива-

емых как данные.

В общем случае результатом вычислений является направленное от-

ношение, порождаемое построенной сетевой грамматикой G2 при некото-

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

цель вычислений: либо поиск одного произвольного элемента графика от-

ношения, либо генерация всех его элементов. Прерывание процесса гене-

рации осуществляется пользователем через интерфейс системы. Основны-

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

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

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

шина дерева формируется путем применения правила грамматики к одно-

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

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

рой заключается в замене элемента сети на одну из определяющих его се-

FLOGOL: ЯЗЫК И СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 13

5. S-FLOGOL-СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

ние дерева в ширину имеет существенный недостаток, связанный с тем,

что для нахождения решения, расположенного на небольшой глубине от-

носительно корня дерева, необходимо обработать все вершины предыду-

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

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

терминального сорта, так и для нетерминального сорта в целом. В послед-

нем случае предполагается, что указанная квота назначается всем вхожде-

ниям элементов данного сорта в правые части правил сетевой грамматики.

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

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

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

терпретации.

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

ции вычислений направленных отношений. При этом в системе преду-

смотрены различные режимы вычислений, предназначенные для решения

FLOGOL: ЯЗЫК И СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 14

5. S-FLOGOL-СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

определенных классов задач. Основными режимами вычисления являются:

логический вывод, вычисление отношений в конструктивных базисах, вы-

числение рекурсивных функций и отношений на конкретных областях данных.

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

сти некоторой логической формулы первого порядка. Аксиома сетевой грамматики имеет арность (0,0) , терминальный базис составляют сорта,

интерпретируемые как конструкторы на эрбрановском универсуме, а не-

терминальный базис – сорта, соответствующие прямым и инверсным пре-

дикатным символам, правила для которых формируются по заданной фор-

муле. Правила редукции в данном режиме основаны на свойствах ортого-

нальности, функциональности и тотальности отношений. Если в результа-

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

лы доказана. Полученные в процессе вычислений непустые сети в терми-

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

вершиться.

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

ляется описание отношений, интерпретируемых как пустые на интересу-

ющих пользователя интерпретациях. Результатом вычислений в этом ре-

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

ной выше. В режиме вычисления отношений на конкретных областях дан-

ных, с внешней функциональной интерпретацией терминальных сортов

FLOGOL: ЯЗЫК И СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 15

5. S-FLOGOL-СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

данных процесс вычислений оперирует с «размеченными» сетями, в кото-

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

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

строк символов и сетей как формальных объектов) используются все рас-

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

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

Основными проблемами, определяющими стратегию вычисления, являют-

ся выбор сети, выбор элемента и выбор правила для выполнения подста-

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

ний и вручную, задавая по своему усмотрению значение некоторых пара-

метров, например, устанавливая приоритеты при выборе элементов для подстановки, определяя порядок применения правил для элементов неко-

торого нетерминального сорта и др.

5.3. Особенности реализации S-FLOGOL-системы функциональнологического программирования.

Особенности языка S-FLOGOL (Small Function and LOGic Oriented

Language) как языка системы функционально-логического программиро-

вания были рассмотрены в предыдущем разделе. Ниже описываются

FLOGOL: ЯЗЫК И СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 16

5. S-FLOGOL-СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

принципы организации и реализация структурно-ориентированного и гра-

фического редакторов системы как основных инструментальных средств поддержки разработки и отладки S-FLOGOL-программ. S-FLOGOL-

система функционально-логического программирования построена на базе теории направленных отношений [1], причем реализация вычислений в си-

стеме непосредственно опирается на сетевое представление схем направ-

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

ментов).

Программные объекты языка S-FLOGOL включают имеющую мо-

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

структурно-ориентированный текстовой редактор для задания схем направленных отношений при формировании запросов и построения мно-

гомодульных программ,

графический редактор для построения и корректировки сетевой грам-

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

ления, а также

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

жимы вычислений.

5.3.1. Текстовый редактор.

Текстовый редактор системы предназначен для формулировки запро-

сов и для создания и редактирования модулей информационной базы. В

основе редактора лежит оригинальная технологии ввода программ, бази-

рующаяся на альтернативно-списковой форме грамматики языка [6]. Крат-

FLOGOL: ЯЗЫК И СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 17

5. S-FLOGOL-СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

ты с редактором. Согласно грамматике языка, для раскрытия каждого син-

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

ния. Использование в языке S-FLOGOL понятия выражения некоторого типа как основного синтаксического понятия позволяет в значительной мере унифицировать наборы инструментов. После выбора нужного вари-

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

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

ются аналогичным образом. Для выделения фрагмента, представляющего собой экземпляр текста для некоторого синтаксического понятия, доста-

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

в форме имени синтаксического понятия с цветовым отражением степени его раскрытия: «не раскрыт», «частично раскрыт», «полностью раскрыт».

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

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

щих опциональные элементы (например, ELSE-часть в условной кон-

струкции), отказ от опции должен допускать при дальнейшем редактиро-

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

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

FLOGOL: ЯЗЫК И СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 18

5. S-FLOGOL-СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

выбрать нужный опциональный элемент и раскрыть его. Ввод и редакти-

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

ков»), а также числовых констант производится в специальном окне ввода с автоматическим синтаксическим контролем. Предусмотрена возмож-

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

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

стью ввода. Редактирование частично или полностью раскрытых фрагмен-

тов программы осуществляется путем их сворачивания и повторного вы-

бора варианта раскрытия. На рис. 5.4 показан вид пользовательского экра-

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

Редактор имеет расширенную систему работы с буферами обмена,

определяющую свой буфер для элементов одного и того же типа. Вставка

Рис. 5.4. Окно структурно-ориентированного редактора

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

FLOGOL: ЯЗЫК И СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 19

5. S-FLOGOL-СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

Отказ от ручного ввода синтаксических элементов предполагает авто-

матическое структурирование текста программы. Для решения этой задачи был разработан алгоритм [Бебчик, 2004a], в основу которого положен принцип табуляции не поместившихся в поле ввода элементов с учетом уровней их вложенности во внутреннем древовидном представлении про-

граммы.

После завершения ввода программа компилируется во внутреннее се-

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

струментальные средства конструирования текстов S-FLOGOL программ описана в работах [6] и [7], краткое содержание которых приведено в При-

ложении.

5.3.2. Графический редактор.

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

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

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

Создание сетевой грамматики основано на технологии графического про-

граммирования [9], позволяющей пользователю на каждом шаге редакти-

рования графически строить всегда корректное описание сетевой грамма-

тики. Центральным интерфейсным элементом формирования и отображе-

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

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

жаются промежуточные и окончательные результаты вычислений. Постро-

ение правила грамматики заключается в создании нового правила в дереве

FLOGOL: ЯЗЫК И СИСТЕМА ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 20