Технология графического построения функционально-логических программ на языке S-FLOGOL

Размещено на http://www.allbest.ru/

Технология графического построения функционально-логических программ на языке S-FLOGOL

ANNOTATION

The functional-logic program creating graphical method is described. The method allows a user to create correct programs based on a directing relations net grammar representation. The net grammar representation is considered as the way to build a directing relations graphic image. Basic methods and tools for functional-logic program creating are discussed and demonstrated on some examples.

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

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

Функционально-логическая парадигма является объединением парадигм функционального и логического программирования и позволяет программисту описывать задачу на языке логики, предоставляя одновременно возможности функционального программирования для параллельного выполнения полученных запросов к системе. В докладе рассматривается графическое построение программ языка функционально-логического программирования высокого уровня S-FLOGOL (Small FLOGOL). Это модификация функционально-логического языка FLOGOL, построенного на базе теории направленных отношений [1]. Язык S-FLOGOL позволяет описывать сложные рекурсивные схемы при помощи формализма направленных отношений.

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

В теории направленных отношений [1] вводится понятие сетевого представления схем направленных отношений, являющееся основополагающим с точки зрения построения и выполнения запросов к системе. Запрос представляется как сетевая грамматика, порождающая сетевой язык, который и является результатом выполнения запроса. Таким образом, в простейшем случае программу можно представить как описанный в сетевой форме запрос к системе, который одновременно играет роль внутреннего представления программы. Более сложным является случай задания программы в виде шаблонного текста, приводимого к форме сетевой грамматики в процессе компиляции запроса к системе. Этот случай далее детально рассматривать не будем, считая, что мы строим программу в виде запроса к системе в сетевой форме.

В работах [1,2] показано, что сетевая форма направленных отношений может быть отображена графически, из чего следует, что построение программы можно производить, непосредственно описывая направленные отношения графическим способом. Этот факт и лег в основу графического построения функционально-логических программ на языке S-FLOGOL.

Определим, как должен выглядеть запрос к системе. Запросом к системе является сетевая грамматика G = (B_т, B_н, a, P), где B_т, B_н - соответственно терминальный и нетерминальный базисы; a - аксиома, определяющая вычисляемое отношение и принадлежащая B_н; P - система правил, левой частью которых является элементы нетерминального базиса, а правыми - соответствующие им определения в сетевой форме. Из всех вышеперечисленных составляющих сетевой грамматики графическому построению подлежать лишь правые части системы правил P, однако рассмотрим кратко и другие составляющие грамматики. Базисом называется тройка тройку (R,,), где R - множество сортов элементов, а и задают, соответственно, входную и выходную арность элемента сети [1]. Далее будем считать, что для указания элемента базиса, соответствующего элементу сети, достаточно указывать сорт последнего. В сетевом представлении арность будем понимать как количество входов и выходов элемента сети. Элемент сети соответствует некому отношению, а точки - элементам носителя, на котором определяется отношение.

В качестве примера, поясняющего графическое построение функционально-логической программы на языке S-FLOGOL, возьмем рекурсивно определенное отношение сложения на множестве натуральных чисел. Это функциональное тотальное отношение с арностью (2,1).

На рис.1. показано графическое представление сетевой формы рекурсивного определения отношения сложения в языке S-FLOGOL. Сетевая грамматика G определяется как ({S(1,1), N(0,1)},A(2,1),A,P) . К терминальному базису Bт относятся элементы S(1,1) (Succ) и N(0,1) (Null), а к нетерминальному - элемент A(2,1), который также является и аксиомой (вычисляемым отношением) грамматики. Фактически на рис.1в мы видим две сети, являющиеся правыми частями правил, входящих в сетевую грамматику. Левая часть этих правил одинакова для обеих сетей и представляет собой элемент A нетерминального базиса Bн. Интерпретация элементов Bт задается внешними процедурами, вычисляющими соответствующие значения.

Рисунок 1 - Представления схемы рекурсивного определения сложения

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

Для выполнения вышеуказанного условия добавление элементов и точек в сеть производится особым образом: выбирается существующий или создается новый сорт для нового элемента; добавляется новый элемент; добавляются n точек, где n - общее количество входов и выходов; добавляются дуги, попарно связывающие точки с соответствующими входами и выходами отношения. Других способов добавления элементов или точек в сеть не предусмотрено. Первоначальное создание самой сети выполняется по тем же правилам. Состояние сети после добавления нескольких элементов показано на рис.2а.

Однако, отсутствие механизмов добавления дуг и точек сети ставит проблему наличия общих точек у различных элементов сети. Под общей точкой понимается точка, связанная более чем с одним элементом сети. Например, на рис. 1в все точки являются общими. Для решения проблемы общих точек существуют два метода - слияние и расщепление. Слияние - структурное и графическое объединение двух и более точек, в результате которого все связи объединяемых точек становятся связями «слитой» точки. Такой метод позволяет связывать элементы между собой посредством общих точек. Результат слияния точек сети на рис. 2а показан на рис 2б.

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

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

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

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

Рисунок 2 - Построение сети методом слияния точек

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

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

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

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

ЛИТЕРАТУРА

1. Фальк В.Н. Теория направленных отношений и ее приложения // Дисс. … докт. техн. наук. М: - МЭИ. -2001.

2. Кутепов В.П., Фальк В.Н. Направленные отношения: теория и приложения // Изв. РАН. Техническая кибернетика, 1994. № 4,5.

3. Вавилов К.В. Программирование за… 1 (одну) минуту // Компьютер Price. - 2002. - № 31. - С. 288-293.

4. Бебчик Ан.М. Особенности визуализации объектов графического интерфейса FLOGOL-системы функционально-логического программирования. // Международный форум информатизации-2002:Доклады международной конференции "Информационные средства и технологии". 14-16 октября 2003г., в 3-х т.т. Т3.- М.:Янус-К, 2003. - 221с.

Размещено на Allbest.ru