Prolog урок 2. Базы фактов, цели и запросы

Нормальная форма Бэкуса-Наура

Для начала вспомним нормальную форму Бэкуса-Наура (БНФ), которая была создана для формального описания синтаксиса языков программирования в 1960 году. Ее авторы — Джон Бэкус и Питер Наур.

Итак, в БНФ приняты следующие обозначения:

Символ ::= читаемый как «по определению» («это», «есть»). Слева от символа располагается объясняемое понятие, справа — разъясняющая конструкция. Например,

<Имя> ::= <Идентификатор>

Части выражения, используемые для обозначения синтаксической конструкции языка, берутся в угловые скобки; в нашем примере это <Имя> и <Идентификатор>.

Символ | означает  логическое  «или» и применяется для разделения различных равнозначных альтернативных объяснений определяемого понятия.

Используя данный символ можно, например, определить десятичную цифру:

<цифра> ::= 0|1|2|3|4|5|6|7|8|9

Если часть конструкции заключена в квадратные скобки [], то это означает, что она является необязательной, т.е. может отсутствовать.

Так запись

<Целое число> ::= [-]<Положительное целое число>

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

Символ * указывает на то, что стоящая перед ним синтаксическая конструкция может повторяться произвольное количество раз (начиная с ноля и выше). Вместо символа *  иногда используются фигурные скобки ( {, } ), по сути равнозначные ему.

Снова определим положительное целое число, используя  нотацию БНФ :

<Положительное целое число> ::= <цифра>[<цифра>]*.

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

Структура программы на языке Prolog

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

1. Constants

Необязательный раздел определения констант.

2. Domains

Раздел описания доменов (аналогичен описанию типов данных).

В Turbo Prolog можно выделить простые типы данных:
char — символьный тип
integer — целое число
real — вещественное число
string — последовательность символов типа char, которая заключена в кавычки
symbol — последовательность букв латинского алфавита, цифр и знаков подчеркивания, которая начинается со строчной буквы (тогда без кавычек) или заключена в кавычки (тогда можно с прописной буквы)
3. Predicates

Раздел описания предикатов (аналогичен разделу описания процедур и функций); по сути представляет собой шаблон написания фактов в разделе Clauses.

4. Clauses

Утверждения (аналог: тело основной программы).

5. Goal

Целевое утверждение – «цель».

domains
 	a=symbol
predicates
 	likes (a,a)
clauses 
 	likes (mary,apples).

likes(mary,apples)

Факты и правила

Часто программу, написанную на Прологе, называют базой знаний.

Предложения-правила имеют вид:

A:- B1,… , Bn.

Где A — это заголовок или голова предложения, а B1,..., Bn – это тело.

Факт обычно утверждает, что между объектами выполнено некоторое отношение и состоит из:

• отношения
• объекта или объектов, заключенных в круглые скобки (аргументы)
• завершается точкой (.)

Пример факта:

likes  (bill, dogs).

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

Если факт состоит только из заголовка, то можно сказать, что факт – это предложение, у которого тело пустое.

Аргументом факта или предиката может быть константа, переменная или составной объект; от их числа зависит так называемая местность (n-местность) факта.

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

В следующем примере наводите курсор на части конструкций, и появится подсказка:

[simple_tooltip content='предикат или факт']likes[/simple_tooltip] [simple_tooltip content='аргументы'] (bill, dogs).[/simple_tooltip]  - Билл любит собак.
[simple_tooltip content='предикат или факт'] bird [/simple_tooltip] [simple_tooltip content='аргумент'](vorobej). [/simple_tooltip] Птица – воробей.

Таким образом, в примере likes — это имя двухаргументного предиката (факта), у которого строковая константа «bill» является первым аргументом, а «dogs» — вторым аргументом.

domains 
  a=symbol
  b=integer
predicates
  age(a,b)
clauses
 age(...,...).
 ...(...,...).
 ...(...,...).

Цели

Цель — это формулировка задачи, которую программа должна решить. Цель также служит «триггером» для запуска программы.

Турбо-Пролог использует как внутренние цели, которые содержатся в программе, так и внешние цели, которые вводятся с клавиатуры после запуска программы. Здесь существует два варианта:

1. Если цель является фактом, то Турбо-Пролог отвечает True (истина) или False (ложь):

goal
likes(mary,apples).

Дословно: Мэри любит яблоки.

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

goal
likes(mary,X).

Дословно: Что любит Мэри?

* Понятие переменной в Прологе будет рассмотрено в следующем уроке.

Так, наш пример может быть как фактом, так и целью:

likes(mary,apples). — Мэри любит яблоки и Любит ли Мэри яблоки?

Алгоритм составления программы

Программа для компилятора TProlog состоит из разделов, рассмотренных в примере:

domains
 	a=symbol

predicates
 	likes (a,a)

clauses 
 	likes (mary,apples).
	likes(mary,oranges).
  	color(apples,red).

goal
 	likes(mary,X),write("mary lyubit ", X).

Результатом примера будет: «mary lyubit apples».

В данном примере цель записана в виде раздела GOAL прямо в программе, но нужно иметь в виду, что чаще всего цели, требующие логический ответ (правда или ложь), записываются в окне Dialog (goal в программе тогда не пишется)

Бесконечный цикл

В примере, описанном выше, в результате выдается значение только первого из трех фактов:

clauses 
 	likes (mary,apples).
	likes(mary,oranges).
  	color(apples,red).
goal
 	likes(mary,X),write("mary lyubit ", X).

Результат выдает только apples. Хотя еще есть oranges.

Раздел gaol того же примера, но с бесконечным циклом будет выглядеть так:

goal
 	likes(mary,X),write("mary lyubit ", X),nl,fail.

nl — означает переход на следующую строку (каждое значение выводится с новой строки).
Результат:
«mary lyubit apples».
«mary lyubit oranges».

Код программы целиком:

domains
 	a=symbol
predicates
 	likes (a,a)
clauses 
 	likes (mary,apples).
	likes(mary,oranges).
  	color(apples,red).	
goal
 	likes(mary,X),write("mary lyubit ", X),nl,fail.

Рассмотрим еще один пример.

domains
  a=symbol
predicates
  построил (a,a)
  хранится (a,a)
  ворует (a,a)
  ловит (a,a)
  треплет (a,a)
  доит (a,a)
  бранится (a,a)
  будят (a,a)
clauses 
  построил (джек,дом).
  хранится (пшеница, чулан_дома).
  ворует (птица_синица, пшеница).
  ловит (кот, птица_синица).
  треплет (кот, птица_синица).
  треплет (пес, кот).
  доит (старушка, корова).
  бранится (пастух, старушка).
  будят (два_петуха, пастух).

? - построил (Х, дом). 
/*Кто построил дом?*/

? – ловит (кот, Y)
/*Кого ловит кот?*/

? – бранится (X,Y).	
/*Кто с кем бранится?*/

? – хранится (X, чулан_дома), ворует (X,Y).          
/*Что хранится в чулане дома и кто ворует это */

goal
  postroil(X,house),write(X),nl,fail.

domains
	a=symbol
	b=integer
predicates
	birthday(a,b,a)
	likes(a,a)
clauses
	birthday(nataly, 8, september).
	birthday(yana, 25, august).
	birthday(nina, 28, september).
	birthday(peter, 2, august).
	birthday(ivan, 12, august).
	likes(nataly, books).
	likes(nataly, sport).
	likes(yana, books).
	likes(yana, dances).
	likes(peter, music).
	likes(peter, dances).
	likes(ivan, sport).
	likes(ivan, books).
Goal
/* birthday(X,Y,september),write(X," rodilas ", Y, " sentyabrya"),nl,fail.*/ 
…   ,  write(…), nl, fail.

domains
	a=symbol
	b=integer
predicates
	 teach(a,a,a,b)
	 vedomost(a,a) 
clauses
	teach(prz, assistent,ivanova,2 ).
	teach(toi, docent, morozov,4).
	teach(mpi,docent, petrova, 5).
	vedomost(toi, exam).
	vedomost(prz, zach).
	vedomost(mpi, exam). 
Goal
/* vedomost(X,exam) ,write("exam po predmetu ", X),nl,fail. */
…   ,  write(…), nl, fail.