Язык программирования пролог относится к

Пролог (язык программирования)

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

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

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

Содержание

Развитие

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

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

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

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

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

Кроссплатформенность

Архитектура

Многие современные реализации языка имеют внутреннее расширение за счёт ООП-архитектуры. Кроме несвободных решений также существуют свободные реализации Пролога. В 1996 году был принят стандарт ISO, получивший название ISO/IEC JTC1/SC22/WG17.

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

Синтаксис

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

Термы

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

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

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

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

Правила

Правила в Прологе записываются в форме правил логического вывода с логическими заключениями и списком логических условий. В чистом Прологе предложения ограничиваются дизъюнктами Хорна:

и читаются так: «Заголовок ИСТИНА, если тело ИСТИНА». Тело правила содержит ссылки на предикаты, которые называются целями правила.

Факты

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

Этот факт эквивалентен правилу:

Критика

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

Другим часто подвергаемым критике свойством языка является отсутствие типизации (при этом в Visual Prolog [3] — одном из объектно-ориентированных расширений языка — реализована строгая типизация, что, однако, снижает гибкость пролога).

Источник

Prolog урок 1. Язык логического программирования Prolog

Теоретические сведения о Prolog

История

Пролог был разработан в Марсельском университете во Франции Алэном Колмероэ и другими членами «группы искусственного интеллекта» в 1973 году. Данная команда энтузиастов разработала программу, предназначенную для доказательства теорем. Написана она была на Фортране, и использовалась при построении систем обработки текстов на естественном языке. Работала программа довольно медленно и назвалась Prolog (от Programmation en Logique на франц.). Программа послужила прообразом Пролога.

Язык логического программирования prolog — декларативный, что означает, что программа, написанная на нем, выглядит как набор логических описаний, определяющих цель, ради которой она и написана.

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

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

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

Области применения языка Prolog и декларативных языков в целом

Особенности языка

Версии и компиляторы

На сегодня существует довольно много реализаций Пролога. Но самый первый компилятор языка был создан Уорреном и Перейрой в 1977 году в Эдинбурге, компилятор предназначался для ЭВМ DEC–10. Тот самый компилятор, известный как реализация под названием «эдинбургская версия», фактически стал первым и единственным стандартом языка и послужил прототипом для многих последующих реализаций Пролога. Интересным фактом является то, что компилятор был написан на самом Прологе.

Изучать Пролог без привязки к конкретной его версии не совсем целесообразно. Версий Пролога очень много, но мы выберем наиболее известную в России и довольно эффективную версию Пролога — Турбо Пролог. Начинала разработку версии (реализации) фирма Borland International совместно с датской компанией Prolog Development Center (PDC). Первая версия вышла в 1986 году. Последняя совместная версия 1988 года вышла под номером 2.0.

Рис. 1. Сайт центра разработки Prolog (Prolog Developement Center)

Таким образом, в 1992 году вышла версия PDC Prolog 3.31, а в 1996 году, при участии группы питерских программистов, PDC выпустила систему Visual Prolog 4.0, у которой много достоинств, но мы не будем на них останавливаться.

Для работы мы выберем самый простой компилятор TPtolog (Турбо Пролог).

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

Загрузка Tprolog через Dosbox

Для работы в Tprolog с 68 битной системой необходимо использовать программу для эмуляции DOS (например, dosbox).

Алгоритм работы с программой следующий:

Работа в Tprolog

Горячие клавиши и основные команды:

Запуск программы осуществляется двумя способами:

Источник

Пролог (язык программирования)

ISO Prolog, Edinburgh Prolog, Turbo Prolog, Visual Prolog

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

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

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

Факты в базах знаний на языке Пролог представляют конкретные сведения (знания). Обобщённые сведения и знания в языке Пролог задаются правилами логического вывода (определениями) и наборами таких правил вывода (определений) над конкретными фактами и обобщёнными сведениями.

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

Содержание

Развитие

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

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

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

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

Кроссплатформенность

Архитектура

Многие современные реализации языка имеют внутреннее расширение за счет ООП-архитектуры. Кроме проприетарных решений также существуют свободные реализации Пролога. В 1996 году был принят стандарт ISO, получивший название ISO/IEC JTC1/SC22/WG17.

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

Синтаксис

Термы

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

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

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

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

Правила

В чистом Прологе предложения ограничиваются Дизъюнктами Хорна

Факты

Предложения с пустым Телом называются Фактами. Пример факта:

оно эквивалентно правилу:

Критика

Источник

Prolog

Prolog (от “PROgramming in LOGic”) — декларативный язык программирования общего назначения.

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

Стандарт языка дан в ISO/IEC 13211-1 (1995 год).

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

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

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

Prolog использует один тип данных, терм, который бывает нескольких типов:

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

Предикаты с несколькими аргументами могут действовать в нескольких направлениях в зависимости от того, какие из аргументов уже связаны, а какие — нет. Например, ….

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

Целью выполнения программы на Prolog является оценивание одного целевого предиката. Имея этот предикат и набор правил и фактов, заданных в программе, Prolog пытается найти привязки (значения) переменных, при которых целевой предикат принимает значение истинности.

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

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

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

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

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

Пролог реализован практически для всех известных операционных систем и платформ. В число операционных систем входят OS для мэйнфреймов, всё семейство Unix, Windows, OS для мобильных платформ.

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

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

Основные вехи развития языка Prolog

Prolog стал воплощением идеи использования логики в качестве языка программирования, которая зародилась в начале 1970-х годов, и само его название является сокращением от слов “programming in logic” (программирование в терминах логики). Первыми исследователями, которые занялись разработкой этой идеи, были Роберт Ковальски (Robert Kowalski) из Эдинбурга (теоретические основы), Маартен ван Эмден (Maarten van Emden) из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ (Alain Colmerauer) из Марселя (реализация). Популяризации языка Prolog во многом способствовала эффективная реализация этого языка в середине 1970-х годов Дэвидом Д. Г. Уорреном (David D.H. Warren) из Эдинбурга. К числу новейших достижений в этой области относятся средства программирования на основе логики ограничений (Constraint Logic Programming — CLP), которые обычно реализуются в составе системы Prolog. Средства CLP показали себя на практике как исключительно гибкий инструмент для решения задач составления расписаний и планирования материально-технического снабжения. А в 1996 году был опубликован официальный стандарт ISO языка Prolog.

Наиболее заметные тенденции в истории развития языка Prolog

В развитии языка Prolog наблюдаются очень интересные тенденции. Этот язык быстро приобрел популярность в Европе как инструмент практического программирования. В Японии вокруг языка Prolog были сосредоточены все разработки компьютеров пятого поколения. С другой стороны, в США этот язык в целом был принят с небольшим опозданием в связи с некоторыми историческими причинами. Одна из них состояла в том, что Соединенные Штаты вначале познакомились с языком Microplanner, который также был близок к идее логического программирования, но неэффективно реализован. Определенная доля низкой популярности Prolog в этой стране объясняется также реакцией на существовавшую вначале “ортодоксальную школу” логического программирования, представители которой настаивали на использовании чистой логики и требовали, чтобы логический подход не был “запятнан” практическими средствами, не относящимися к логике. В прошлом это привело к широкому распространению неверных взглядов на язык Prolog. Например, некоторые считали, что на этом языке можно программировать только рассуждения с выводом от целей к фактам. Но истина заключается в том, что Prolog — универсальный язык программирования и на нем может быть реализован любой алгоритм. Далекая от реальности позиция “ортодоксальной школы” была преодолена практиками языка Prolog, которые приняли более прагматический подход, воспользовавшись плодотворным объединением нового, декларативного подхода с традиционным, процедурным.

Источник

Язык программирования пролог относится к

10.1. Классификация языков программирования

Языки программирования в зависимости от базовых конструкций языка, заложенных в структуру программы можно разбить на четыре категории [9]:

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

Программа, написанная на объектно-ориентированном языке, представляет собой набор объектов, взаимодействующих между собой посредством посылки сообщений. Каждый объект характеризуется информационной составляющей (набором атрибутов) и поведенческой (набор событий и методов). Работа программы представляет собой последовательный обмен сообщениями (вызов методов) между объектами. К объектно-ориентированным языкам относятся Object Pascal, Visual Basic, С++, Java и т.д. Следует отметить, что в любом объектно-ориентрованном языке имеется возможность процедурного программирования.

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

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

Другая классификация языков программирования основана на стиле программирования [30]:

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

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

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

10.2. Основные вехи развития языка Пролог

Идеи использования логики в качестве языка программирования зародилась в начале 1970-х годов. Первыми исследователями, которые занялись разработкой этой идеи, были Роберт Ковальски (Robert Kowalski) из Эдинбурга (теоретические основы, статьи 1971 и 1974 г.), Маартен ван Эмден (Maarten van Emden) из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ (Alain Colmerauer) из Марселя (реализация, 1973 г.). В 1973 году «группа искусственного интеллекта» во главе с Аленом Колмероэ создала в Марсельском университете программу, предназначенную для доказательства теорем. Эта программа использовалась при построении систем обработки текстов на естественном языке. Программа доказательства теорем получила название Prolog (фр. PROgrammation en LOGique) и послужила прообразом Пролога. Ходят легенды, что автором этого названия была жена Алена Колмероэ. Программа была написана на Фортране и работала довольно медленно.

Популяризации Пролога во многом способствовали:

— эффективная реализация (интерпретатор/компилятор) этого языка для ЭВМ DEC-10 Дэвидом Д. Г. Уорреном (David D.H. Warren) из Эдинбурга в 1977 г. Послужила прототипом для многих последующих реализаций Пролога. Что интересно, компилятор был написан на самом Прологе. Эта реализация Пролога, известная как «эдинбургская версия», фактически стала первым и единственным стандартом языка;

— разработка Кларком и Маккейбом (Великобритания) в 1980 году версии для персональных ЭВМ;

На сегодня существует довольно много реализаций Пролога. Наиболее известные из них следующие: BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, МПролог, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic iis Workbench, Strawberry Prolog, SWI-Prolog, Turbo Prolog (PDC Prolog, Visual Prolog), UNSW Prolog и т. д. В нашей стране были разработаны такие версии Пролога как Пролог-Д (С. Григорьев), Акторный Пролог (А. Морозов), а также Флэнг (А. Манцивода, В. Петухин).

5 ISO – International Organization of Standardization (Международная организация по стандартизации).

6 IEC – International Electrotechnical Commission (Международная комиссия по электротехнике).

10.3. Основные понятия Пролога

При формальном описании синтаксиса конструкций алгоритмических языков часто используется так называемая «нормальная форма Бэкуса-Наура» (БНФ), разработанная в 1960 Джоном Бэкусом и Питером Науром. Впервые БНФ была применена Питером Науром при записи синтаксиса языка Алгол-60 [30]. Основными конструкциями БНФ являются следующие.

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

Часть синтаксической конструкции, заключенная в квадратные скобки, является необязательной (может присутствовать или отсутствовать), например

означает, что целое число можно определить через положительное целое число, перед которым может стоять знак минус.

Символ «*» обозначает, что часть синтаксической конструкции может повторяться произвольное число раз (ноль и более). Заметим, что иногда вместо символа «*» используют фигурные скобки « ». Например, положительное целое число в нотации БНФ можно следующим образом:

Т.е. положительное целое число состоит из одной или нескольких цифр.

Программа на Прологе состоит из предложений (утверждений). Каждое предложение заканчивается точкой.

Предложение имеет вид

При необходимости применения дизъюнкции (логическое ИЛИ, ∨) используется символ «;», действующий до следующей дизъюнкции, окончания правила или закрывающей круглой скобки. Например,

Предложения бывают трех видов: факты, правила, вопросы.

А) Факт – это предложение, у которого нет тела. В терминах логики предикатов, факт – это и есть предикат. Он фиксирует (определяет) некоторое отношение между объектами. Например, факт, что Наташа является мамой Даши, может быть записан в виде (в SWI-Prolog строки-константы записываются в одинарных кавычках):

Факт представляет собой безусловно истинное утверждение. Если воспользоваться нормальной формой Бэкуса-Науэра, то предикат можно определить следующим образом:

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

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

Б) Правило – предложение, истинность заголовка которого в виде предиката зависит от истинности одной или нескольких формул, указанных в теле. Обычно правило содержит несколько хвостовых целей, которые должны быть истинными для того, чтобы само правило было истинным. В нотации БНФ правило будет иметь вид:

или
grandmama(X, Y):-
mama(X, Z), mama(Z, Y);
mama(X, Z), papa(Z, Y).

или
grandmama(X, Y):-
mama(X, Z), (mama(Z, Y); papa(Z, Y)).

В) Вопрос (запрос, цель) – предложение, состоящее только из тела. В нотации БНФ вопрос имеет вид:

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

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

Если цель достигнута, система отвечает «yes» («true»), в противном случае «no» («false»). Следует отметить, что ответ «no» на вопрос не всегда означает, что он отрицательный. Система может дать такой ответ и в том случае, когда у нее просто недостаточно информации, позволяющей положительно ответить на вопрос. Т.е. Пролог основан на т.н. «модели закрытого мира», в которой все, что можно получить на основе описания модели является истиной, а остальное – ложью.

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

Свободная переменная – переменная, которая еще не получила значения. Она не равняется ни нулю, ни пробелу; у нее вообще нет никакого значения. Такие переменные еще называют неконкретизированными.

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

Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно и то же имя переменной для обозначения разных объектов. Исключением из правила определения области действия является анонимная переменная, которая обозначается символом подчеркивания «_». Анонимная переменная предписывает интерпретатору (компилятору) проигнорировать значение аргумента (терма). Если в правиле несколько анонимных переменных, то все они отличаются друг от друга, несмотря на то, что записаны с использованием одного и того же символа («_»). Анонимные переменные могут записываться только в качестве терма предиката. Использовать их в выражениях (например, арифметических) нельзя. Пример использования анонимной переменной в вопросе «Есть ли у Даши мама?»:

Разновидности предложений Пролога, записанные в виде фраз Хорна (B ← A), можно интерпретировать следующим образом:

Рассмотрим несколько примеров. Пусть в программе заданы следующие факты (предикаты) и правила:

grandmama(X, Y):-
mama(X, Z), (mama(Z, Y); papa(Z, Y)).

grandpapa(X, Y):-
papa(X, Z), (mama(Z, Y); papa(Z, Y)).

Вопрос 1 – является ли Наташа мамой Даши:

Вопрос 2 – кто является мамой Даши:

Первая строка сообщения означает, что ответ найдет и мамой Даши является Наташа; вторая – что в базе знаний для оставшихся предложений не обнаружены другие мамы Даши.

Вопрос 3 – есть ли у Даши мама:

Вопрос 4 – найти всех мам и детей:

В данном случае после третьего ответа не выдается «false», т.к. в базе знаний были перебраны все предложения и они все истинны.

Вопрос 5 – для кого Наташа является бабушкой:

10.4. Краткие сведения об операциях и встроенных предикатах SWI-Prolog

В табл. 10.1 приведены некоторые операции и предикаты SWI-Prolog, которые в дальнейшем будут использоваться для иллюстрации примеров.

Некоторые операции и предикаты SWI-Prolog

10.5. Процедура вывода в Прологе

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

Например, пусть имеется запрос на определения внучек и внуков «Наташи»:

Ответ:
Маша ;
Маша ;
Всё ;

Примечание. Выделенная жирным часть соответствует правилу определения бабушки (grandmama).

Процедура доказательства (перебора с возвратами) приведена в табл. 10.2.

Некоторые операции и предикаты SWI-Prolog

1) Указанная последовательность имеет место, если в SWI-Prolog после вывода на консоль имени внучки (внука) нажимать клавишу «;» (поиск альтернативного доказательства).

2) Жирным выделены строки, для которых выполнение предиката истинно.

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

На вопрос predok(‘Вася’, ‘Миша’) ответ будет положительным.

Второй пример использования рекурсии – расчет факториала.

На вопрос fact(6, F) ответ будет «F = 720».

Любая рекурсивная процедура в Прологе должна включать, как минимум два правила:

1) нерекурсивное правило, определяющее его вид в момент прекращения рекурсии;

10.7. Управление процессом вывода

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

— fail (false) – предикат, который всегда возвращает ложь;

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

Если мы желаем узнать всех предков «Миши» и при этом, чтобы выдача предков на консоль была выполнена автоматически, а не в диалоговом режиме (путем нажатия «;» после каждого ответа), тогда запрос должен выглядеть следующим образом:

Ответ:
Предки Миши:
Юля
Вася
Коля

Таким образом, предикат fail выполняет принудительный откат и заставляет Пролог заново передоказывать все предыдущие подцели с новыми значениями переменных. Передоказательству в приведенном примере будет подвержен только предикат predok(A, ‘Миша’), т.к. предикаты write и writeln не генерируют новые значения переменных. Если после предиката fail находятся другие предикаты правила, указываемые через «,» (логическое И), то они никогда не будут выполнены.

Рассмотрим более сложный пример: выяснить всех правнуков «Коли».

Ответ:
Правнуки (Юля):
Миша
Маша
Правнуки (Света):
Рома
Леша

10.8. Способы организации циклов

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

1 способ. Используя рекурсию.

2 способ. Используя предикат, который можно передоказать, и предикат fail.

Ответ:
Вика является предком Коля
Вася является предком Коля
Коля является предком Юля
Юля является предком Миша

Такая конструкция соответствует циклу с постусловием.

4 способ. Организация цикла со счетчиком, используя предикат repeat и динамическое добавление фактов в базу знаний (программу).

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

Приведенная программа будет циклически выдавать на экран квадраты чисел от 1 до 10. В качестве счетчика используется предикат (факт) count, который динамически добавляется и удаляется из базы знаний.

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

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

Списки в Прологе заключаются в квадратные скобки, например [1, 2, 8, 123] или [‘Пн’, ‘Вт’, ‘Четверг’]. Список, не содержащий ни одного элемента «[]», называется пустым. Каждый непустой список состоит из двух частей: головы и хвоста. Головой является первый элемент списка, хвостом – все остальное.

Списки и его составные части

В программе голова отделяется от хвоста символом «|».

Часто используемыми операциями при работе со списками являются:

1. Проверка наличия элемента в списке.

?- member(2, [1, 3, 45, 2, 74]),
write(‘Да’);
write(‘Нет’).

2. Добавление элемента в список. Для данной операции не требуется отдельного правила, если элемент X добавляется в начало списка List

3. Конкатенция двух списков.

?- concat([1, 2], [3, 45], L),
write(L).

4. Удаление элемента из списка и задание обратного порядка следования элементов списка.

% 1 параметр – исходный список
% 2 параметр – рабочий список
% 3 параметр – перевернутый список
reverse([], Lr, Lr).
reverse([X|L], L1, Lr):- reverse(L, [X|L1], Lr).

?- delete(1, [1, 3, 1, 45, 1], [], L),
reverse(L, Lr),
write(Lr).

5. Разделение списка на два.

?- split(7, [1, 3, 1, 45, 1, 33], L1, L2),
writeln(L1),
writeln(L2).

Источник