Язык программирования пролог сообщение
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
Горячие клавиши и основные команды:
Запуск программы осуществляется двумя способами:
Язык программирования пролог сообщение
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). grandmama(X, Y):- mama(X, Z), papa(Z, Y). |
или
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), можно интерпретировать следующим образом:
Рассмотрим несколько примеров. Пусть в программе заданы следующие факты (предикаты) и правила:
mama(‘Наташа’, ‘Даша’). mama(‘Даша’, ‘Маша’). mama(‘Наташа’, ‘Вася’). |
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.
Например, пусть имеется запрос на определения внучек и внуков «Наташи»:
?- mama(‘Наташа’, Y), (mama(Y, Z); papa(Y, Z)), write(Z); write(‘Всё’). |
Ответ:
Маша ;
Маша ;
Всё ;
Примечание. Выделенная жирным часть соответствует правилу определения бабушки (grandmama).
Процедура доказательства (перебора с возвратами) приведена в табл. 10.2.
Некоторые операции и предикаты SWI-Prolog
№ п/п | Предикат запроса | Проверяемый предикат базы знаний | Результат |
1 | mama(‘Наташа’, Y) | mama(‘Наташа’, ‘Даша’) | Y = ‘Даша’ |
2 | mama(Y, Z) ≡ mama(‘Даша’, Z) | mama(‘Наташа’, ‘Даша’) | backtracking |
3 | mama(Y, Z) ≡ mama(‘Даша’, Z) | mama(‘Даша’, ‘Маша’) | Z = ‘Маша’ |
4 | write(Z) ≡ write(‘Маша’) | ‘Маша’ | |
5 | mama(Y, Z) ≡ mama(‘Даша’, Z) | mama(‘Наташа’, ‘Вася’) | backtracking |
6 | papa(Y, Z) ≡ papa(‘Даша’, Z) | papa(‘Вася’, ‘Маша’) | backtracking |
7 | mama(‘Наташа’, Y) | mama(‘Даша’, ‘Маша’) | backtracking |
8 | mama(‘Наташа’, Y) | mama(‘Наташа’, ‘Вася’) | Y = ‘Вася’ |
9 | mama(Y, Z) ≡ mama(‘Вася’, Z) | mama(‘Наташа’, ‘Даша’) | backtracking |
10 | mama(Y, Z) ≡ mama(‘Вася’, Z) | mama(‘Даша’, ‘Маша’) | backtracking |
11 | mama(Y, Z) ≡ mama(‘Вася’, Z) | mama(‘Наташа’, ‘Вася’) | backtracking |
12 | papa(Y, Z) ≡ papa(‘Вася’, Z) | papa(‘Вася’, ‘Маша’) | Z = ‘Маша’ |
13 | write(Z) ≡ write(‘Маша’) | ‘Маша’ | |
14 | write(‘Всё’) | ‘Всё’ |
1) Указанная последовательность имеет место, если в SWI-Prolog после вывода на консоль имени внучки (внука) нажимать клавишу «;» (поиск альтернативного доказательства).
2) Жирным выделены строки, для которых выполнение предиката истинно.
Рекурсия – процесс повторения элементов самоподобным образом. Рекурсия (в программировании) – алгоритмический метод, заключающийся в возможности обращения правила (функции, процедуры) к самому себе один или более раз.
На вопрос predok(‘Вася’, ‘Миша’) ответ будет положительным.
Второй пример использования рекурсии – расчет факториала.
На вопрос fact(6, F) ответ будет «F = 720».
Любая рекурсивная процедура в Прологе должна включать, как минимум два правила:
1) нерекурсивное правило, определяющее его вид в момент прекращения рекурсии;
10.7. Управление процессом вывода
В Прологе имеется два стандартных предиката, которые позволяют управлять процедурой перебора с возвратами:
— fail (false) – предикат, который всегда возвращает ложь;
Первый из них используется для организации циклов, а второй для ускорения процедуры перебора.
Если мы желаем узнать всех предков «Миши» и при этом, чтобы выдача предков на консоль была выполнена автоматически, а не в диалоговом режиме (путем нажатия «;» после каждого ответа), тогда запрос должен выглядеть следующим образом:
?- writeln(‘Предки Миши:’), predok(A, ‘Миша’), writeln(A), fail; true. |
Ответ:
Предки Миши:
Юля
Вася
Коля
Таким образом, предикат fail выполняет принудительный откат и заставляет Пролог заново передоказывать все предыдущие подцели с новыми значениями переменных. Передоказательству в приведенном примере будет подвержен только предикат predok(A, ‘Миша’), т.к. предикаты write и writeln не генерируют новые значения переменных. Если после предиката fail находятся другие предикаты правила, указываемые через «,» (логическое И), то они никогда не будут выполнены.
Рассмотрим более сложный пример: выяснить всех правнуков «Коли».
?- roditel(‘Коля’, A), write(‘Правнуки (‘), write(A), writeln(‘):’), roditel(A, B), writeln(B), fail; true. |
Ответ:
Правнуки (Юля):
Миша
Маша
Правнуки (Света):
Рома
Леша
10.8. Способы организации циклов
В Прологе отсутствуют конструкции циклов с параметром, пред- и постусловием, но с помощью соответствующих механизмов можно организовать разные типы циклов.
1 способ. Используя рекурсию.
2 способ. Используя предикат, который можно передоказать, и предикат fail.
?- predok(A, B), write(A), write(‘ является предком ‘), writeln(B), B == ‘Миша’; true. |
Ответ:
Вика является предком Коля
Вася является предком Коля
Коля является предком Юля
Юля является предком Миша
Такая конструкция соответствует циклу с постусловием.
4 способ. Организация цикла со счетчиком, используя предикат repeat и динамическое добавление фактов в базу знаний (программу).
Следует отметить, что в некоторых реализациях языка Пролог отсутствует встроенный предикат repeat. Тогда данный предикат надо определить в программе следующим образом
Приведенная программа будет циклически выдавать на экран квадраты чисел от 1 до 10. В качестве счетчика используется предикат (факт) count, который динамически добавляется и удаляется из базы знаний.
Существуют также другие способы организации циклов.
В Прологе нет такой распространенной и часто используемой структуры хранения данных как массивы, но зато есть развитые возможности работы со списками. Список – упорядоченный набор элементов одного типа. В отличие от массивов, количество элементов которых строго фиксировано (в большинстве языков программирования), списки позволяют модифицировать, добавлять или удалять из него элементы.
Списки в Прологе заключаются в квадратные скобки, например [1, 2, 8, 123] или [‘Пн’, ‘Вт’, ‘Четверг’]. Список, не содержащий ни одного элемента «[]», называется пустым. Каждый непустой список состоит из двух частей: головы и хвоста. Головой является первый элемент списка, хвостом – все остальное.
Списки и его составные части
Список | Голова | Хвост |
[1, 2, 8, 123] | 1 | [2, 8, 123] |
[‘Пн’, ‘Вт’, ‘Четверг’] | ‘Пн’ | [‘Вт’, ‘Четверг’] |
[1.25] | 1.25 | [] |
[] | не определена | не определен |
В программе голова отделяется от хвоста символом «|».
Часто используемыми операциями при работе со списками являются:
1. Проверка наличия элемента в списке.
?- member(2, [1, 3, 45, 2, 74]),
write(‘Да’);
write(‘Нет’).
2. Добавление элемента в список. Для данной операции не требуется отдельного правила, если элемент X добавляется в начало списка List
3. Конкатенция двух списков.
% 1 параметр – первый список % 2 параметр – второй список % 3 параметр – результат объединения двух списков concat([], L2, L2). concat([X|L1], L2, [X|L3]):- concat(L1, L2, L3). |
?- concat([1, 2], [3, 45], L),
write(L).
4. Удаление элемента из списка и задание обратного порядка следования элементов списка.
% 1 параметр – удаляемый элемент % 2 параметр – исходный список % 3 параметр – рабочий список % 4 параметр – перевернутый список без элемента delete(_, [], L, L). delete(X, [X|L], L1, L2):- delete(X, L, L1, L2). delete(X, [Y|L], L1, L2):- X \== Y, delete(X, L, [Y|L1], L2). |
% 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. Разделение списка на два.
% 1 параметр – элемент, задающий разбиение % 2 параметр – исходный список % 3 параметр – элементы, меньшие или равные 1 параметру % 4 параметр – элементы, большие 1 параметра split(_, [], [], []). split(Y, [X|L], [X|L1], L2):- X =@ Y, split(Y, L, L1, L2). |
?- split(7, [1, 3, 1, 45, 1, 33], L1, L2),
writeln(L1),
writeln(L2).