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

Размещено на http://www.Allbest.Ru/

Размещено на http://www.Allbest.Ru/

Размещено на http://www.Allbest.Ru/

Московский институт радиотехники, электроники и автоматики

Технический университет

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

Бебчик А.М.

Россия, г. Москва

Аннотация

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

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

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

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

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

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

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

Свертка является аналогом циклов в алгоритмических языках программирования и представляет собой конструкцию итеративного схемного описания. Так, например, свертка (#I = 1..3)[I]R, определенная в рамках некоторого реляционного выражения, в процессе компиляции будет преобразована в схему

[1]R#([2]R#[3]R),

где R - идентификатор отношения,

I - операторная переменная свертки,

1..3 - диапазон изменения значения переменной свертки (использование бесконечных интервалов при определении диапазонов в языке S-FLOGOL запрещено).

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

Язык S-FLOGOL является современным объектно-ориентированным языком программирования высокого уровня. В нем реализуется основные принципы объектно-ориентированного программирования: инкапсуляция, наследование и полиморфизм. Инкапсуляция обеспечивается разбиением программы на модули и заключением элементов описания направленных отношений в домены скрытой и открытой части модуля. При этом каждый программный модуль рассматривается как отдельный класс, включающий в себя множество собственных отношений. При подключении модуля в качестве родительского все отношения его открытой части оказываются в области видимости дочернего модуля. Наследование с точки зрения теории направленных отношений [1] рассматривается как продолжение описания отношения, поэтому в случае, если в области видимости вызова конкретного отношения оказалось несколько определений отношений, имена которых идентичны вызываемому, то строится новое отношение с именем вызова, в котором все правые части (реляционные выражения) видимых отношений соединяются операцией «объединения». Полиморфизм направленных отношений заключается в возможности задания множества отношений с одинаковым именем (идентификатором и списком индексов), но различной входной и выходной арностью, то есть количеством входов и выходов отношения. Причем арность отношения в общем случае может зависеть от параметров вызова. Арность задается в спецификаторе отношения, размещаемом в элементе описания перед его именем, и вычисляется непосредственно в вызове отношения. Кроме этого в спецификаторе могут указываться свойства функциональности и тотальности прямого и обратного отношений. Эти свойства сохраняются в сорте элемента, представляющего отношение в сетевой форме и в дальнейшем используются при выполнении скомпилированного запроса.

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

3. Котляров А.В. Построение интерпретаторов и компиляторов. СПб: Наука и техника. 2001. - 224 стр.

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

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

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