Интерпретатор языка Пролог

Аннотация

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

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

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

Приводится расчет затрат на разработку программного продукта.

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

Содержание

 

Введение.......................................................................................................... 4

1. Исследовательская часть............................................................................. 8

1.1. Роль реляционных языков в развитии вычислительной техники.......... 8

1.2. Основные механизмы дедукции............................................................ 10

1.3. Исчисление предикатов как язык для решения задач.......................... 12

1.3.1 Унификация и принцип резольвенции в исчислении предикатов...... 13

1.3.2. Методы поиска доказательства в исчислении предикатов................ 15

1.3.2.1. Исчисление предикатов при решении задач................................... 15

1.3.2.2. Стратегии перебора......................................................................... 16

1.3.2.3. Стратегии упрощения...................................................................... 17

1.3.2.4. Стратегии очищения........................................................................ 18

1.3.2.5. Формы доказательства с отфильтровыванием предшествующих вершин. 4

1.3.2.6. Стратегии поддерживающего множества......................................... 4

1.3.2.7. Стратегии упорядочения................................................................... 5

1.4. Анализ характеристик существующих интерпретаторов...................... 6

1.5. Необходимость разработки интерпретатора языка Пролог................. 8

1.6. Выбор языка программирования........................................................... 8

2. Конструкторская часть............................................................................. 10

2.1. Синтаксис программ на Прологе в нотации Бэкуса-Наура................. 10

2.2. Общая структура интерпретатора........................................................ 10

2.2.1. Принцип работы предкомпилятора................................................... 11

2.2.1.1. Работа лексического анализатора................................................... 11

2.2.1.2. Синтаксический анализатор............................................................ 12

2.2.1.3. Анализ арифметического выражения............................................. 13

2.2.1.4. Анализ параметров предикатов...................................................... 15

2.2.1.5. Проверка типов параметров............................................................ 15

2.3. Работа интерпретатора.......................................................................... 16

2.3.1. Выполнение обращений к базам данных........................................... 18

2.3.2. Вычисление арифметических выражений.......................................... 19

2.4. Объекты, используемые компилятором и интерпретатором............... 19

2.4.1. Объекты переменных TPrologVariable, TPrologVariables, TPrologVariableList, TPrologVariableStruct.................................................................................... 19

2.5.2. Стандартные функции и предикаты................................................... 21

2.6. Представление Пролог-программы в виде объектов........................... 21

2.7. Основные модули................................................................................... 23

2.8. Демонстрационная программа по выбору конфигурации компьютера. 25

3. Технологическая часть.............................................................................. 28

3.1. Требования по эксплуатации интерпретатора языка Пролог............. 28

3.2. Установка системы................................................................................. 28

3.3. Руководство пользователя программы интерпретатора языка Пролог. 29

3.3.1. Запуск программы.............................................................................. 29

3.3.2. Перечень функций, реализуемых системой....................................... 29

3.3.3. Редактирование Пролог-программы................................................. 29

3.3.4. Запуск программы на Прологе и ее отладка..................................... 34

3.3.5. Работа с меню...................................................................................... 35

3.4. Описание процесса выполнения программы, написанной на языке Пролог. 38

3.5. Общие сведенья об интерпретаторе...................................................... 39

3.6. Особенности работы Пролог-программы с базами данных................ 39

3.7. Описание стандартных предикатов....................................................... 40

3.8. Описание функций.................................................................................. 43

4. Организационно-экономическая часть.................................................... 45

4.1. Расчет затрат на разработку интерпретатора Пролог......................... 45

5. Промышленная экология и безопасность................................................ 47

5.1. Введение................................................................................................. 47

5.2. Анализ характера загрязнения окружающей среды при производстве вычислительной техники............................................................................... 48

5.2.1. Источники загрязнения....................................................................... 48

5.2.2. Очистка воздуха от вредных примесей.............................................. 50

5.3. Анализ влияния опасных и вредных факторов, при эксплуатации программы интерпретатора Пролог................................................................................ 52

5.3.1. Повышенный уровень шума на рабочем месте................................. 53

5.3.2. Опасный уровень напряжения электрической цепи, замыкание которой может произойти через человека............................................................................. 54

5.3.3. Пожарная опасность........................................................................... 55

5.3.4. Повышенный уровень электромагнитных излучений....................... 56

5.3.5 Повышенная яркость света.................................................................. 57

5.3.6. Прямая и отраженная блеклость........................................................ 58

5.3.7. Нарушение микроклимата рабочих помещений............................... 58

5.3.8. Защита от психофизиологических факторов..................................... 59

5.4. Анализ использования защитных экранов для снижения влияния опасных и вредных факторов, во время работы на автоматизированном рабочем месте......... 60

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

5.4.1.1. Защита от электростатического и электромагнитного воздействий. 61

5.4.1.2. Защита от рентгеновского излучения............................................. 61

5.4.1.3. Защита от ультрафиолетового излучения...................................... 61

5.4.2. анализ основных типов защитных экранов, которые приемлемы для снижения влияния вредных и опасных факторов, во время с программным средством. 62

5.4.2.1. Сетчатый (частичная защита зрения).............................................. 62

5.4.2.2. Стеклянный двухслойный с заземлением (частичная защита зрения, частичная защита здоровья).......................................................................................... 62

5.4.2.3. Стеклянный многослойный с заземлением (полная защита зрения, полная защита здоровья)....................................................................................................... 63

5.5. Расчет необходимого звукопоглощения, при работе с АРМ............... 63

Заключение.................................................................................................... 66

Литература.................................................................................................... 67

Приложения................................................................................................... 68

Приложение 1................................................................................................ 68

Приложение 2................................................................................................ 73

Приложение 3................................................................................................ 81

Приложение 4................................................................................................ 87

Введение

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

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

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

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

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

В любой системе экспертных консультаций обязательно должны иметься следующие три компоненты:

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

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

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

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

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

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

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

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

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

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

1 Исследовательская часть 1.1 Роль реляционных языков в развитии вычислительной техники

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

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

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

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

·            Процедурные языки;

·            Функциональные языки;

·            Реляционные языки.

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

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

Возможны три точки зрения программиста на Пролог-программу.

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

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

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

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

1.2 Основные механизмы дедукции

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

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

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

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

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

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

1.3 Исчисление предикатов как язык для решения задач

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

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

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

Мы обычно пользуемся языком для того, чтобы делать утверждения, касающиеся интересующей нас области. Отношения между языком и описываемой им областью определяется семантикой этого языка. Правильно построенные формулы исчисления предикатов как раз являются теми выражениями, которые мы будем использовать в качестве утверждений, касающихся интересующей нас области. Говорят, что правильно построенные формулы принимают значения T или F в зависимости от того, являются эти утверждения в этой области истинными или ложными. Приемы обращения с правильно построенными формулами позволяют строить умозаключения, относящиеся к некоторой области, и, следовательно, могут представить интерес при создании принятия решения, требующего такого умозаключения.[2]

1.3.1 Унификация и принцип резольвенции в исчислении предикатов

Унификация – процесс, являющийся основным в формальных преобразованиях, выполняемых при нахождении резольвент.

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

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

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

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

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

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

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

Принцип резольвенции непротиворечив и полон. Непротиворечивость означает, что если когда-нибудь мы придем к пустому предложению, то исходное множество обязано быть неудовлетворимым. Полнота означает, что если исходное множество неудовлетворимо, то, в конце концов, мы придем к пустому предложению.[2]

  1.3.2 Методы поиска доказательства в исчислении предикатов 1.3.2.1 Исчисление предикатов при решении задач

Иногда достаточно только знать, следует ли логически правильно построенная формула W из некоторого множества S правильно построенных формул. Если W не следует из S, то, возможно, мы захотим знать, следует ~W из S. Конечно, в силу неразрешимости исчисления предикатов не всегда можно установить, следует ли W из S.

В других приложениях нужно знать значение элемента x (если он существует), при котором данная правильно построенная формула W (содержащая x в качестве переменной) логически следует из некоторого множества S правильно построенных формул. Иными словами, мы хотели бы знать, следует ли логически правильно построенная формула , и если да, то каков тот частный случай переменной x. Проблема поиска доказательства правильно построенной формулы , исходя из S, является обычной проблемой доказательства в исчислении предикатов, но для построения удовлетворяющего частного случая требуется, чтобы метод доказательства был "конструктивным".

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

1.3.2.2 Стратегии перебора

Непосредственное применение принципа резольвенции соответствует простой процедуре полного перебора при построении опровержения. Такой перебор мы начинается множества S, к которому добавляется резольвенты всех пар предложений в S с тем, чтобы образовать множество R. Затем добавляются резольвенты всех пар предложений в R с тем, чтобы образовать множество R(R(S))=R²(S), и т.д. Этот метод перебора как правило непригоден для практики, так как множества R(S), R²(S),… слишком быстро разрастаются. Практические процедуры доказательства определяются стратегиями перебора, применяемыми для его ускорения. Такие стратегии бывают трех типов: стратегии упрощения, стратегии очищения и стратегии упорядочения.[2]

1.3.2.3 Стратегии упрощения

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

Исключение тавтологий.

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

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

Иногда появляется возможность означить (выяснить значение истинности) литералы, и это оказывается удобнее, чем включать соответствующие предложения в S. Такое означивание легко провести для константных частных случаев. Например, если предикатная буква E обозначает отношение равенства, то означивание константных частных случаев типа E(7,3), когда они появляются, провести легко, хотя нам бы не хотелось добавлять к S полную таблицу, содержащих много константных частных случаев литералов E(x,y) и ~E(x,y).

Если какой-нибудь литерал предложения получает значение истинности T, то все предложения можно отбросить, не нарушая при этом свойства невыполнимости оставшегося множества. Если же какой-нибудь литерал при означивании получает значение истинности F, то из этого предложения можно исключить данное вхождение литерала.[2]

Исключение подслучаев.

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

 - подслучай предложения ,

 - подслучай предложения ,

 - подслучай предложения

 - подслучай предложения .

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

1.3.2.4 Стратегии очищения

Стратегии очищения основаны на тех теоретических результатах в теории доказательства с помощью резольвенций, в которых утверждается, что для нахождения опровержения не нужны все резольвенции. Иными словами, достаточно выполнить резольвенции только для предложений, удовлетворяющих определенным требованиям. Обозначим через  объединение множества S и множества всех резольвент всех пар предложений из S , удовлетворяющих критерию C. Ясно, что .

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

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

1.3.2.5 Формы доказательства с отфильтровыванием предшествующих вершин

Доказательство с отфильтровыванием предшествующих вершин производится с использованием AF-графа. Граф опровержения имеет AF-форму, если каждая из его вершин соответствует одному из следующих предложений:

1.         базовому предложению;

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

3.         предложению, непосредственно следующему за двумя небазовыми предложениями A и B, из которых B предшествует A (отсюда термин отфильтровывание предшествующих вершин).

Граф в виде лозы представляет собой частный случай графа в AF-форме: каждая из его вершин соответствует либо предложению 1, либо предложению 2. Но граф типа лозы существует не для всех неудовлетворимых множеств. Ниже приведен пример такого графа.[2]

Рис 1.1. Вид графа в AF-форме.

  1.3.2.6 Стратегии поддерживающего множества

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

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

1.3.2.7 Стратегии упорядочения

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

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

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

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

1.4 Анализ характеристик существующих интерпретаторов

В настоящее время существует несколько интерпретаторов и компиляторов языка Пролог.

СиПролог (CProlog). Поставщиком является отдел архитектуры Университета Эдинбурга. Эта версия переносится практически на любой 32-разрядный компьютер с операционной системой UNIX. Синтаксис СиПролога совпадает с синтаксисом DEC-10 Пролога. Встроенного редактора не существует. У отладчика имеются всего четыре команды:

Call - вызов первой фразы предиката

Back To - вызов второй и последующих фраз

Exit - процедура выполнена успешно

Fail - система достигла конца множества фраз.[2]

Квинтус Пролог (Quintus Prolog). Поставляется фирмой Quintus Computer Systems Inc. Он Предназначен для ЭВМ под управлением UNIX и VMS. Квинтус Пролог можно запускать либо как самостоятельный процесс, либо через специальный интерфейс с редактором EMACS. Отладчик аналогичен отладчику СиПролога, но обладает большим количеством команд.[2]

Пролог-2. Поставляется фирмой Expert Systems Int. Работает под управлением MS-DOS. Поддерживает свой механизм виртуальной памяти, что позволяет писать программы, работающие с большим количеством данных. Из-за особого механизма виртуальной памяти программу необходимо разбивать на модули и указывать явно, должен ли находится модуль в реальной памяти или возможно его размещение в виртуальной. Имеется встроенный редактор. Отладчик аналогичен отладчику СиПролога.[2]

Эрити Пролог (Arity Prolog). Поставщик Arity Corp. Работает под управлением MS-DOS или совместимой операционной системы. Имеет механизм виртуальной памяти со страничной организацией. Встроенного редактора нет, отладчик аналогичен предыдущим.[2]

Турбо Пролог (Turbo Prolog). Поставщик Borland Int. Работает под управлением MS-DOS. Является полноценным компилятором, вследствие чего обладает строгим контролем типов. Создан собственный оконный интерфейс с четырьмя окнами: редактор, отладчик, консоль и окно сообщений об ошибках. Сообщения отладчика аналогичны сообщениям отладчика СиПролога.[6]

Visual Prolog. Поставщик Prolog Development Center. Работает под управлением Windows 3.1 и выше. Обладает развитым оконным интерфейсом. Позволяет создавать полноценные приложения для Windows с использованием окон. Сообщения отладчика аналогичны СиПролог.

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

1.5 Необходимость разработки интерпретатора языка Пролог

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

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

1.6 Выбор языка программирования

На выбор языка программирования влияют следующие факторы:

1.          характер решаемой задачи;

2.          имеющиеся в наличии системные библиотеки;

3.          поддреживаемые компилятором платформы.

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

1.          гибко работать с динамически выделяемой памятью;

2.          иметь объектно-ориентированное расширение;

3.          иметь средства обработки исключительных ситуаций;

4.          получать высокоскоростной код.

Перечисленным требованиям удовлетворяют С++ и Паскаль. До недавнего времени Паскаль (и его диалект Delphi) значительно уступал С++ по возможности формирования высокоскоростного кода. Но теперь в компилятор Delphi 4 был встроен оптимизатор, который позволяет формировать высокоскоростной код.

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

Borland Delphi 4 генерирует код для операционных систем Windows 95, 98 и NT. Имеет средства визуального построения приложений.

2 Конструкторская часть 2.1 Синтаксис программ на Прологе в нотации Бэкуса-Наура

Программа::=предложение <предложение>

Предложение::=утверждение, управляющая команда

Утверждение::=голова.проб_символ

Голова :- хвост.проб_символ

Голова if хвост.проб_символ

Управляющая команда::=

целевое утверждение

<,целевое утверждение>.проб_символ

Голова::=целевое утверждение

Хвост::=целевое утверждение

<,целевое утверждение>

Целевое утверждение::=атом|структура

Проб_символ::=пробел, возврат каретки[6]

2.2 Общая структура интерпретатора

Интерпретатор языка Пролог состоит из следующих частей:

·           Предкомпилятор;

·           Интерпретатор.

Предкомпилятор выполняет перевод исходных данных в объекты интерпретатора. Исходными данными для предкомпилятора являются:

·                    Текст программы;

·                    Типы пользователя;

·                    Описания внешних данных (структур баз данных);

·                    Описания предикатов программы.

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

2.2.1 Принцип работы предкомпилятора

Предкомпилятор состоит из двух основных частей:

·            Лексический анализатор

·            Синтаксический анализатор.

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

Синтаксический анализатор на основе массива лексем, полученных от лексического анализатора, формирует объект программы.

2.2.1.1 Работа лексического анализатора

Для удобства работы лексический анализатор склеивает весь текст программы в одну длинную строку. Такое склеивание можно проводить, так как максимальная длина строки в Delphi 4 равна 2 гигабайтам. При склеивании строк, в конце каждой строки ставится пара символов Enter и пробел. Это делается для того, чтобы удобно можно было вычислить положение лексемы в тексте программы.

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

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

Если ни одно из условий не было выполнено, то выдается сообщение об ошибке.

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

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

2.2.1.2 Синтаксический анализатор

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

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

Предложение в Прологе имеет следующий формат:

ИмяПредиката (Параметр1, Параметр2, …) if

Условие1(Параметр11, Параметр12, …),

Условие2(Пераметр21, Параметр22, …),

УсловиеN(ПараметрN1, ПараметрN2, …).

При синтаксическом анализе, во-первых, проверяется заголовок предложения. Проверяется имя предиката и параметры (их количество и тип) и наличие слова “if”. Если в качестве параметра стоит переменная, то считается, что переменная может быть любого типа, а константы подвергаются жесткому контролю.

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

·        Все условия разделены запятыми друг от друга;

·        Цепочка условий заканчивается точкой;

·        Внутри условия все скобки (круглые и квадратные) должны быть закрыты.

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

·        Вызов предиката, если первая лексема - имя предиката;

·        Вызов базы данных, если первая лексема - имя базы данных;

·        Вычисление арифметического выражения - во всех остальных случаях.

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

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

2.2.1.3 Анализ арифметического выражения

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

Среди всего массива лексем находится оператор с наинизшим приоритетом, причем операции, которые находятся внутри скобок в рассмотрение не берутся. В Прологе приоритеты операций распределены следующим образом:

1. *,/

2. +,-