Функциональная модель параллельных вычислений и язык программирования "Пифагор"

[ <<< | Содержание | Предисловие | Введение | 1 | 2 | 3 | 4 | 5 | Заключение | П1 | П2 | П2 | Источники | >>> ]

© 2002 А.И. Легалов, Ф.А. Казаков, Д.А. Кузьмин, Д.В. Привалихин

4. Система интерпретации функциональных программ

Система интерпретации функциональных программ (СИФП) состоит из трех основных модулей:

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

Эти модули реализованы внутри монолитного исполняемого файла. Общая структура СИФП приведена на рис. 4.1.

Рис. 4.1. Структура системы интерпретации функциональных программ.

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

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

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

4.1. Структура транслятора

Транслятор состоит из лексического и синтаксического анализаторов (рис 4.2).

Рис. 4.2. Обобщенная структура транслятора.

Лексический анализатор (сканер) формирует лексемы и передает их синтаксическому анализатору. Задачей синтаксического анализатора является проверка синтаксиса и построение промежуточного представления программы. При этом синтаксический анализатор производит обращения к интерфейсам уже построенных объектов. Например, при построении объекта <список>, сначала создаётся объект <список>, а затем, по мере построения объектов - элементов списка, производятся обращения к методам уже частично построенного объекта <список> для добавления к нему элементов.

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

TProgram - класс, описывающий структуру всего исходного файла. Он содержит таблицу имён констант и функций, используемых в программе. Этот класс в данной версии транслятора имеет только одного представителя, т.е. транслятор не позволяет обработку нескольких файлов с текстами программ на ФЯПП. Поле NameOwner этого класса содержит значение NULL, поскольку он является владельцем глобального пространства имён и, кроме того, это позволяет, при поиске идентификатора в таблицах имён, проводить поиск по цепочке владельцев пространств имён, прекращая поиск, как только в поле NameOwner одного из объектов встретится значение NULL. Класс TProgram имеет метод, позволяющий запускать на выполнение или отладку по имени одну из функций из его таблицы имён функций.

Рис. 4.3. Классы, определяющие структуру промежуточного представления.

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

TExpression - класс, представляющий список термов, приведённый к постфиксной форме записи. Каждый из термов может иметь указатель на другой терм, что отражает альтернативную ветвь вычислений (так называемый else-терм).

TTerm - базовый класс, порождающий все классы, выступающие в качестве термов: TBlock, TAtom, TKW, TList, TID.

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

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

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

TList - класс, обеспечивающий представление всех трех разновидности списков языка: последовательные списки, параллельные списки и задержанные списки. Содержит список объектов, каждый из которых является представителем класса TExpression.

TID - класс, являющийся отражением идентификаторов в промежуточном представлении. Содержит поле с именем этого идентификатора.

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

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

4.2 Структура интерпретатора

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

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

1. класса TAtomFishka, предназначенного для хранения скалярных значений всех типов;
2. класса TListFishka, хранящего элементы классов последовательных, параллельных и задержанных списков, производных от Tfishka;
3. класса TObjectFishka, содержащего указатель на один из объектов, составляющих промежуточное представление программы, и служащий для разметки дуг информационного графа функциональными фишками.

Всех представителей описанных выше классов далее будем называть "фишками". Именно фишки и будут размещены на рёбрах графа в качестве его разметки.

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

1. Фишка - аргумент функции, в теле которой происходят текущие вычисления. Запрос объекту TProgram в качестве аргумента получает фишку - результат интерпретации введённого пользователем аргумента.
2. Булевская переменная, принимающая значение false при выполнении программы и false - при её пошаговой отладке. Это значение используется в процессе интерпретации выражений и сигнализирует ему о необходимости делать задержку после каждой операции интерпретации и выдавать на консоль данные, полученные при выполнении данной операции.

Результат вычислений каждого из объектов состоит из двух элементов:

1. Фишка - результат вычислений (в том числе и фишка ошибки).
2. Булевская переменная, значение TRUE которой является признаком того, что фишка-результат содержит в себе фишки ошибок либо сама является таковой. Это позволяет, не производя анализа полученной фишки определить успешность вычислений.

4.2.1 Интерпретация объектов TProgram, TFunction и TBlock

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

Рис. 4.4. Выполнение запроса на вычисление функции.

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

4.2.2 Интерпретация объекта TExpression

Объект класса TExpression представляет собой список термов выражения, приведённого к постфиксной форме:

term1:term2:term3:term4: ... :termn-1:termn.

Каждый из термов может быть атомом, ключевым словом, списком, блоком или идентификатором. Если рассматриваемое выражение является неименованным выражением какой либо функции или блока, то term_n должен быть ключевым словом: return - в случае функции и break - в случае блока. Term₁ не может быть идентификатором функции, поскольку слева от знака операции интерпретации должен стоять аргумент функции даже в том случае, если функция не использует аргумента.

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

Рис. 4.5. Вычисление выражения

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

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

4.2.3 Интерпретация объектов TAtom и TKW

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

4.2.4 Интерпретация объекта TList

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

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

Рис. 4.6. Интерпретация атомов и ключевых влов.

Рис. 4.7. Интерпретация списков.

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

4.2.5 Интерпретация объекта TID

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

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

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

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

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

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

Рис. 4.8. Интерпретация элемента таблицы имен.

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

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

4.2.6 Оператор интерпретации

Оператор интерпретации соответствует одноимённому программо-формирующему оператору информационного графа. Он осуществляет все действия, предусматриваемые правилами функционирования модели вычислений.

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

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

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

4.2.7 Правила интерпретации предопределенных операций

Интерпретация предопределенных операций задается правилами их выполнения заданными в описании ФЯПП (раздел 2.15).

4.3. Модуль управления

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

1. текстовый редактор;
2. вспомогательные утилиты, облегчающие просмотр отдельных функций;
3. окна отладки, аргументов, результатов.
4. Инструментальные панели и меню, позволяющие управлять доступом к транслятору, интерпретатору промежуточного представления и прочим функциям.

Более подробное описание модуля управления приведено в разделе 5.

4.4 Использованные средства разработки

Система реализована на языке С++ при использовании компилятора и среды разработки Microsoft Visual C++ 6.0. Для создания объектов-контейнеров была использована стандартная библиотека шаблонов STL (Standard Templates Library). При написании интерактивной среды разработки программ под Windows были также использованы классы библиотеки MFC (Microsoft Foundation Library).

Примечание. Сведения представлены по сосотоянию на январь 2002 г.

[ <<< | Содержание | Предисловие | Введение | 1 | 2 | 3 | 4 | 5 | Заключение | П1 | П2 | П2 | Источники | >>> ]