Содержание к диссертации
Введение
Глава I. Описание языка HETL 6
1.1. Особенности языка 6
1.2. Классы и атомы 9
1.3. Операции и вычисление выражений 13
1.4. Основы и процедуры 23
Глава 2. Транслятор с языка HETL 27
2.1. Общая характеристика транслятора и организация анализа 27
2.2. Синтез объектной программы 31
2.3. Мэдули поддержки 41
Глава 3. Модуль работы с ассоциативной, сетью во внешней памяти 43
3.1. Функции, выполняемые модулем 43
3.2. Отображение внешних имен во внутренние .. 47
3.3. Представление сети в виде В-дерева 49
Заключение 53
Приложение I. Синтаксические диаграммы языка HETL 55
Библиография 64
- Операции и вычисление выражений
- Общая характеристика транслятора и организация анализа
- Отображение внешних имен во внутренние
- Представление сети в виде В-дерева
Введение к работе
Широкое внедрение вычислительной техники обуславливает стремление к повышению интеллектуального уровня ЭВМ и к про -стоте их применения. Решение задач, связанных с попытками автоматизации процедуры выработки решения человеком, автоматизации процесса создания программ, улучшения взаимодействия с ЭВМ привело к разработке новых методов программирования,объеди-няемых в рамках направления, получившего название "искусственный интеллект" (далее ИИ) X fe, 45,A3,2-.1 ,2Ь].
Характерно, что ранее применявшийся критерий принадлежности поколению ЭВМ теперь включает программную оснащенность машины. Предполагается, что очередное поколение ЭВМ наряду с применением новейшей технологии СБИС будет обладать развитыми функциями решения задач "весьма высокого интеллектуального уровня" С 2.73 . При реализации этих функций должны найти свое применение методы и программные средства ИИ.
Одной из основных проблем, стоящей перед исследователями в области ИИ,является проблема представления знаний Lao.az^s]. Работы в данном направлении ведутся как по пути поиска универсальных механизмов, так и.по пути разработки специализированных методов представления.
Любой традиционный язык программирования обладает средствами, позволяющими представлять данные об объектах, входящих в предметную область решаемой задачи. Однако, разрыв между концептуальным уровнем формулировки задачи и уровнем структур данных языков программирования столь велик,.что их применение к программированию задач ИИ затруднительно. Использование идеи абстрактных типов данных 2,?,7,ЬЪ,ъ*0при проектировании языков
_ 4 -
программирования позволило значительно сократить этот разрыв, но не затронуло.одну из важнейших сторон знаний - их алгорит-
МИЧНОСТЬ L2»G
Языки программирования ИИ включают в себя формализацию выбранной концепции представления знаний, если в начале своего развития в языках разделялись средства описания фактов внешнего мира и средства их использования, то теперь наблюдается тенденция к разработке языковых конструкций, совмещающих декларативный и процедуралышй аспекты представления знаний (языки УТОПИСТ С31 , ДЕКАРТ Ь1 9шь Є353 , КЕЬС^з.ъоЗ). Языки подобного рода являются входными языками сложных систем программирования универсального или проблемно-ориентированного характера. Видимо это является необходимым условием.позво-ляющим говорить о возможностях представления знаний на этих языках, т.к. стоящая между входным и машинным языком система программирования и заполняет собой упомянутый выше разрыв.
Один из способов решения задачи представления знаний предложен Г.С.Цейтиным 231 . Им разработана и реализована экспериментальная система программирования, основанная на понятии ассоциативной сети. Его подход значительно отличается от вариантов ассоциативных сетей, обсуждаемых в работе ъ21 тем, что в вершине сети может находиться процедура или ее имя, вершины и дуги сети не типизируются и сеть рассматривается как основа модульной системы программирования.
Реализация системы, выполненная Г.С.Цейтиным, включает набор основных механизмов работы с сетью, доступный пользователю через набор макрокоманд ассемблера ОС ЕС. В связи с тем, что разработка программ ИИ носит, как правило, экспериментальный характер, большое значение приобретает скорость их разра-
ботки. Поэтому задача повышения уровня входного языка системы, решаемая в настоящей работе, является актуальной.
Работа выполнена на основании анализа принципов программирования на ассоциативных сетях, предложенных Г.С.Цейтиным, опыта использования системы макрокоманд для решения различных задач и анализа конструкций современных языков программирования. Ее результаты, опубликованные в Сіь.лчі состоят в том.что:
разработан и реализован язык высокого уровня hetl для программирования в системе с сетевым представлением информации;
показана применимость системы для решения задач построения трансляторов. При этом предложена схема реализации синтезирующей фазы транслятора с использованием очереди процедур, взаимодействующих через трехуровневый контекст;
предложен и реализован способ представления ассоциативной сети данных во внешней памяти ЭВМ в виде В-деревьев;
разработаны и реализованы средства поддержки разработки программ в системе.
Операции и вычисление выражений
Главной задачей при разработке языка являлась задача повышения уровня всходного языка системы программирования на ассоциативных сетях Ігзі . Существующий входной язык - язык макрокоманд ассемблера ОС ЕС, насчитывает порядка 35 макрокоманд, которые позволяют производить описание пакета, представляющего собой сеть, описание процедур и их использование. Работа с ассоциативной сетью предполагает возможности продвижения по сети, ее перестройки, построения новых сетевых структур и создания экземпляров заранее подготовленных пакетов и процедур. Макрокоманды обеспечивают полную поддержку процедур, то есть стековый режим управления памятью для локальных переменных,вызов процедур, расположенных как в памяти, так и в библиотеках, механизм удачного и неудачного завершения процедур. Для выполнения операций с числами и строками, которые могут быть значениями атрибутов, приходится пользоваться языком ассемблера.
При разработке языка НЕМ» автор стремился максимально полно включить возможности языка макрокоманд, то есть добиться того, чтобы пользователю не приходилось даже в самых сложных программах прибегать к языку ассемблера. Получившийся в результате язык унаследовал ряд черт, свойственных языку макрокоманд. Прежде всего этот язык программирования является входным языком системы, базирующейся на представлении информации в виде сети и поэтому обладает конструкциями,позволяющими как производить действия не меняющие сеть, так и создавать новые и перестраивать существующие сети. Терминальными значениями атрибутов (терминальными в том смысле, что из этих значений не могут исходить дуги) являются натуральные числа, строки и процедуры.
В языке предусмотрены обычные арифметические операции для чисел: сложение, вычитание, умножение, деление нацело с остат -ком; для строк разрешены только операции сравнения. Конкатенации строк нет, но файлы, доступные в языке как заранее описанные пакеты накапливают строки склеивая их, и, поэтому, конкатенацию строк можно производить помещая их в файл. Никаких "встроенных" функций для работы со строками или стандартных математических функций нет. Бітових значений нет, а логические константы представляются натуральными числами "о" и "і". Предполагается, что языком будут пользоваться для программирования не расчетных и экономических задач, а для задач символьной обработки.
ИЕТЬ - это бестиповый язык и, потому на нем можно написать программу, в которой операции применяются к недопустимым объектам. Более того, синтаксис языка строился исходя из возможно более простого метода анализа и поэтому усложнять класс грамматики ради синтаксического запрета ряда бессмысленных цепочек автор не решился. Понятно, что при пользовании языком большая часть ошибок обнаруживается в процессе счета, а не при трансляции. В связи с этим было решено особое внимание уделить средствам отладки, что определило включение в язык конструкции, вызывающей приостановку выполнения программы и обращение к средствам отладки, которые допускают просмотр состояния памяти в терминах исходной программы.
В языке нет специальных конструкций для ввода/вывода. Вместо них, в соответствии с идеологией системы, предполагается, что файлы оформляются как модули и средства обращения к ним ничем не отличаются от средств обращения к другим модулям. Помимо модулей, реализующих функции ввода/вывода,система содержит и другие модули, например, модуль динамических вызовов программ ассемблера и редактора связей, который используется транслятором с HETL , модуль, позволяющий работать с ассоциативной сетью во внешней памяти и т.д. Специальным модулем оформлено и средство динамической трансляции. Это средство расширения языка, с помощью которого можно во время выполнения программы обращением к одной из функций модуля скопить текст на HEEL во внутреннем файле и, с помощью другой функции, динамически оттранслировать полученный текст и привести его к виду, позволяющему в этой же программе воспользоваться динамически полученной единицей трансляции.
Программа на языке НЕТЬ представляет собой процедуру которая может обращаться к заранее подготовленным процедурам и модулям. Пакет, представляющий экземпляр модуля в памяти, состоит из вершин сети (среди которых выделена главная), соединенных дугами; он содержит, как правило, ряд процедур и общие данные для них. Тело процедуры состоит из последовательности возможно помеченных основ, среди которых есть основыдозволяющие определять переменные, работать с очередью процедур, сигнализировать неудачи, выполнять выходы из процедур и циклов, переходить к меткам, а также вычислять выражения. Самой сложной и мощной основой в языке является основа вычисления выражения, позволяющая как вычислить объект, для которого следует выполнить какие-то действия, так и осуществить перестройку сети,окружающую этот объект, условное предложение и предложение цикла могут вырабатывать значения и их разрешено использовать внутри выражения. В связи с тем, что ряд действий в сети.может закончиться неудачей, в язык введено понятие перехвата, которое позволяет сделать попытку перевычислить значение по другому возможному пути.
Общая характеристика транслятора и организация анализа
Объектным языком транслятора является язык макрокоманд системы программирования на ассоциативных сетях 1231 , то есть язык макроассемблера. Этот факт значительно упростил построение синтезирующей части транслятора и обусловил обращение к ассемблеру на последнем этапе трансляции для перевода программы в объектный код ОС ЕС. Структура транслятора традиционна, то есть выделяются фазы лексического и синтаксического анализа, фаза синтеза.
Языком реализации транслятора выбрана система макрокоманд все той же системы [233 » что привело к целому ряду особенностей реализации. Этот язык был выбран из исследовательских соображений в связи с малой изученностью применения системы для программирования задач построения трансляторов (задачи подобной проблематики решались в работе ІІ4І).
Транслятор может работать в трех режимах: в диалоговом, в пакетном, и в так называемом внутреннем режиме, В первом режиме источником ввода может быть как экран дисплея (через диалоговый режим работы системы JEC С 81), так и заданный раздел библиотеки, во втором - стандартный источник ввода ( STSIN ) , в третьем - внутренний файл. Третий режим работы позволяет из программы сформировать во внутреннем файле текст на HETL , его оттранслировать и тутяе использовать, Каждый из режимов представлен процедурой, устанавливающей среду ввода/вывода для транслятора и осуществляющей его вызов.
Реализация анализирующей фазы транслятора,как обычно, определилась двумя факторами: классом грамматики реализуемого языка и средствами реализации. Рассмотрение синтаксических диаграмм языка HETL (см.приложение I) позволяет утверждать,что его грамматика принадлежит классу Ы (2) til. То есть,читая исходный текст программы слева направо, заглядывая на две лексемы вперед, можно сделать однозначный выбор порождающего правила. Поддержка рекурсивных вызовов в системе макрокоманд и класс грамматики определили метод анализа - метод рекурсивного спуска 22].
Сканер, по традиции, сложившейся в системе, реализован модулем. Функции, выполняемые этим модулем, состоят из открытия, формирования очередной лексемы и возврата на одну лексему назад. Процедура формирования очередной лексемы ( GBTSIM ) не зависит от особенностей источника ввода. Для чтения очередной строки исходного текста она вызывает процедуру, которая должна находиться на дуге с именем ЕВАБЫЖВ , исходящей из главного узла пакета. В описании модуля этой дуги нет, она возникает при отождествлении главных узлов сканера и пакета,осуществляющего ввод. Таким образом, всякий пакет ввода, обладающий дугой ВЕАШЛЖЕ , ведущей в процедуру чтения строки, может быть совмещен со сканером, что используется для реализации работы транслятора в трех вышеперечисленных режимах. Еще одна "степень свободы" сканера связана со способом выделения ключевых слов и составных символов. Процедура GETSIM в начале работы вызывает процедуры, находящиеся на дугах с именами KBYWOBDS, DOUBLED, ТВ1ЕЫТ , удача выполнения которых говорит о распознавании ключевого слова, символа из двух или трех литер соответственно. Если же все процедуры потерпели неудачу, то сканер распознает и формирует лексему разделителя, идентификатора.числа или строки. Функция возврата на лексему назад в связи с классом грамматики реализована таким образом, что ее последовательный двухкратный вызов приводит к возврату на две лексемы назад.
Фаза синтаксического анализа, в соответствии с выбранным методом, реализована набором распознающих процедур, по одной на каждый нетерминал к (точнее, на каждую синтаксическую диаграмму) . Эти процедуры выделяют во входной цепочке ту подцепочку, которая выводится из N , рекурсивно обращаясь к другим процедурам. Так как язык не расчитан на параллельный с анализом однопроходный синтез (из-за необходимости идентификации), то процедуры вынуждены строить промежуточное представление программы. Этим представлением является сеть. Помимо этой работы, каждая из процедур решает еще две задачи, одна из них - это анализ и исправление ошибок, другая - подготовка информации для фазы синтеза.
Стандартное начало каждой анализирующей процедуры выполняет действия, помещающие имя процедуры в глобально доступную сеть. В случае обнаружения ошибки в анализируемой цепочке, что при используемом методе анализа удается сделать сразу, вызывается универсальная процедура реакции на ошибку. Ее функции состоят в том, чтобы выдать соответствующее сообщение об ошибке, скорректировать построенное промежуточное представление программы и, может быть, пропустив несколько лексем, вызвать процедуру, продолжающую анализ. Все эти действия однозначно определяются двумя обстоятельствами: именем текущей анализирующей процедуры и номером ошибки.
Отображение внешних имен во внутренние
Кроме операции перехвата запрос на значение может быть поставлен при анализе присваивания (это дуга DEST ведущая в переменную, наличие которой анализируется в приведенной выше процедуре тооит ) и процедурами, анализирующими вычисление объекта, если они обнаружат вхождение условного предложения или предложения цикла. Если же эти предложения содержат семантические ошибки, то есть они запрограммированы так, что не выдают значений, то синтезирующая процедура объемлющей конструкции откажется работать, так как не обнаружит в своем контексте вызова записи о размещении операнда. Такая ситуация приводит к прекращению синтеза и сопровождается специальной выдачей.
Некоторые синтезирующие процедуры зависят не только от глобального контекста (глобальные сети) и контекста вызова (промежуточное сетевое представление программы), но и от локального контекста. Под локальным контекстом понимается сеть, содержащая информацию, существенную для генерации текущей процедуры и перестраиваемую при переходе к генерации следующей процедуры. Локальный контекст содержит список объявленных переменных, модуль, обслуживающий работу с литерным пулом, текущий идентификатор неудачи. Локальный контекст перестраивается процедурой, генерирующей заголовок процедуры и используется другими генерирующими процедурами.
Таким образом, синтез объектного кода производится набором помещенных в очередь процедур, которые не получают параметров и не выдают результата. Вот информацию, необходимую для работы, они получают из глобального, локального контекстов и контекста вызова, причем глобальный контекст ими не меняется, локальный изменяется немногими процедурами, а изменение контекста вызова служит основным способом взаимодействия между синтезирующими процедурами.
Помимо модулей, реализующих файлы ввода/вывода, пользовательской программе доступны во время счета модуль отладки, модуль динамической трансляции и модуль работы с ассоциативной сетью во внешней памяти.
Модуль отладки получает управление при выполнении основы показа сети. В случае пакетной работы его функция состоит в выдаче состояния сети на АЦПУ ( макрокоманда KETSNAP ) и возврате управления. В случае диалогового режима, модуль приостанавливает выполнение пользовательской программы и выдает на экран сообщение о переходе в режим просмотра сети. В этом режиме пользователь может просмотреть всю сеть или задать выражение, вычисляющее объект. Модуль обращается к пакету динамической трансляции для получения выполнимого кода этого выражения. Результат вычисления выражения выдается на экран. В режиме отладки пользователь может задать произвольное число таких выражений, пустить программу дальше или остановить ее.
Обращение к модулю динамической трансляции аналогично обращению к модулю, реализующему файл. Пусть, например, мы хотим оттранслировать текст динамически формируемой процедуры: модуля DINOOMP позволяет собрать строки во внутренней файле, а функция BUILDS создает среду ввода/ вывода для транслятора таким образом, чтобы чтение производилось из этого внутреннего файла и вызывает транслятор. Результат его работы передается ассемблеру и редактору связей для получения кода в виде, готовом к немедленному использованию.
Под ассоциативной сетью во внешней памяти (в дальнейшем именуемую внешней сетью) будем понимать ориентированный мульти-граф, состоящий из вершин, соединенных дугами и предназначенный для представления и хранения информации об объектах любой природы. Вершины внешней сети могут быть именованными (в этом случае это атомы) или неименованными (тогда они называются узлами) . Дуги также разрешается именовать или оставлять безымянными. В качестве имени разрешается использовать строку или натуральное числом Вершины внешней сети являются представлениями объектов, а дуги интерпретируются как отношения между объектами. Неименованные дуги обычно используются для представления отношения принадлежности множеству. Таким образом, внешняя сеть не содержит процедур, а может содержать только их имена1. В качестве имен вершин и дуг разрешено использовать произвольную строку, В остальном структура внешней сети аналогична структуре сети, обрабатываемой системой.
Представление сети в виде В-дерева
Из определения внешней сети следует, что ее вершины и дуги могут быть именованными и неименованными. Имена вершин и дуг (внешние имена), которые указываются при обращении к функциям модуля, в целях унификации преобразуются к внутренним именам, представляющим собой целое число". Неименованные дуги и узлы также получают внутренние имена, что приводит к значительному упрощению представления сети во внешней памяти.
Для хранения внешних имен предусмотрен отдельный набор данных с прямой организацией. Каждый блок этого набора содержит внешние имена вместе со служебной информацией. Адресация этого набора осуществляется через хэш-таблицу, также хранящуюся во внешней памяти. В качестве адреса используется пара: "Номер блока - смещение в нем". Процедура выработки внутреннего имени реализована следующим образом. Вычисляется значение хэш-функпии по внешнему имени, оно определяет вход в цепочку хэш-синонимов, по таблице определяется адрес этого входа и цепочка просматривается для поиска совпадения заданного внешнего имени с существующими-. Если это имя уже существует, то выдается соответствующее внутреннее имя, записанное в служебной информации. В противном случае имя записывается в первый свободный блок с коррекцией конца цепочки. При отсутствии искомого внешнего имени выработка соответствующего внутреннего имени начинается с продвижения специального счетчика, значение которого вместе со значением хэш-функции, образуя пару, используется для вычисления номера пары. Этот номер и является внутренним представлением внешнего имени. При такой кодировке внешних имен их восстановление по внутреннему представлению выполняется вычислением левого числа пары,т.е . вычислением значения хэш-функции. Далее это число используется для входа в таблицу и извлечения адреса цепочки синономов, содержащей искомое внешнее имя.
Неименованные вершины получают внутренние имена по счетчику, а для неименованных дуг используется следующая процедура. В описываемой реализации зарезервированы два внешних имени,одно из которых используется для генерации внутренних имен неименованных дуг, а другое - для слежения за мощностью множеств. При требовании включить элемент в множество (что внешне выглядит как требование соединить неименованной дугой две вершины) определяется мощность узла-множества. Из значения мощности и служебного внешнего имени конкатенацией получается имя, внутреннее представление которого и определяет внутреннее имя данной неименованной дуги. Такая процедура обеспечивает в случае необходимости перебора элементов множества простой и эффективный цикл поиска. Начальная установка счетчиков производится таким образом, чтобы между всеми возможными дугами и вершинами, с одной стороны, и внутренними именами с другой, набор описанных алгоритмов осуществлял взаимно-однозначное соответствие.
После того как сеть унифицирована внутренними именами,задача ее представления сводится к следующей: представить во внешней памяти сеть, все вершины и дуги которой помечены натуральными числами.
Рассмотрим сеть, унифицированную внутренними именами (см. Рис.6). Очевидно, что если хранить в памяти тройки А, ,В , А, ,С , В, ,А , С,$,В (где A .C .f., , - внутренние имена), то будем обладать полной информацией о структуре этой сети. Для сокращения времени поиска хранение этих троек организовано в виде В-дерева L28,311 , Напомним, что В-де-ревом порядка К называется дерево, удовлетворяющее следующим условиям:
Таким образом, В-дерево представляет собой совершенно сбалансированное поисковое дерево, каждый узел которого выглядит как на рис.7, где К»- элемент, содержащий поисковый ключ, Р -ссылка к узлу с ключами, лежащими в интервале (К.Ч,К.Ч), В данной реализации в качестве ключа используется конкатенация внутренних имен узла и выходящей из него дуги. Таким образом элемент К представляющий тройку A, . ,В выглядит как на рис.8.
