Child(liz, tom):-parent (tom, liz)

Самарский государственный технический университет

Кафедра вычислительной техники

О.В. Прохорова

 

ОСНОВЫ ПРОГРАММИРОВАНИЯ на языке Пролог.

Курс лекций

 

 

Самара 2017

 

Оглавление

1. Базовые понятия языка Пролог. 4

1.1. Факты.. 4

1.2. Вопросы.. 5

1.3. Переменные. 6

1.4. Конъюнкция целей. 7

1.5. Правила. 8

1.6. Конъюнкция в правилах. 9

1.7. Переменные в теле правила. 11

2. Синтаксис Пролога. 12

2.1. Константы.. 13

2.2. Переменные. 14

2.3. Структуры.. 15

2.4. Операторы - тоже функторы.. 17

2.5. Арифметика. 17

2.6. Операции сравнения. 19

2.7. Сопоставление. 20

2.8. Второе значение операции “=” в Прологе. 23

2.9. Примеры сопоставления структур. 24

3. Декларативная семантика Пролог-программ.. 24

3.1. Дизъюнкция целей. 26

3.2. Процедурная семантика. 26

3.3. Соотношение между процедурным и декларативным смыслом.. 30

4. Организация работы со списками в Прологе. 31

4.1. Представление списка диаграммой. 31

4.2. Процедуры обработки списков. 34

4.3. Встроенные предикаты. Ввод\ вывод. 37

4.4. Ввод-вывод списков. 39

5.1. Отсечение. 40

5.3 Сортировка списков. 47

6. Встроенные предикаты. Поиск на Прологе. 52

6.1. Отрицание как неудача. 52

6.2. Алгоритм поиска на Прологе. 54

6.3. Чтение и запись информации с файлов. 57

6.4. Обработка символов. 58

6.5. Метапредикаты. Встроенные предикаты обработки термов. 61

6.6. Предикаты работы с базой данных. 62

6.7 Поиск в лабиринте. 63

7. Сравнительная характеристика языков программирования. 67

Библиографический список. 68

 

Базовые понятия языка Пролог

 

Пролог -

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

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

 

Родственные отношения

 

Рассмотрим дерево родственных отношений:

Факты

Введем отношение -родитель- (parent) между объектами.
parent (tom, bob).

Это факт, определяющий, что Том является родителем Боба.

parent - имя отношения, tom, bob - его аргументы. Теперь можно записать программу, описывающую все дерево родственных отношений.

parent (pam, bob). parent (tom, bob). parent (tom, liz). parent (bob, ann). parent (bob, pat). parent (mary, ann). parent (pat, juli).

 

Эта программа состоит из семи предложений (утверждений).
Каждое утверждение записано фактом в виде отношения parent.
При записи фактов надо соблюдать следующие правила:

• Имена всех отношений и объектов с маленькой буквы.
• Сначала записывается имя отношения, затем в круглых скобках через запятую объекты.
• В конце ставится точка.

Еще пример факта:                           like (bob, pam).

Совокупность фактов в прологе называют базой данных.

Вопросы

К составленной базе данных можно задать вопросы..

Вопрос в обычном прологе начинается с ?-
Вопрос записывается также, как и факт.
Например:

? - parent (bob, pat).

Yes

Когда пролог получает вопрос, он пытается сопоставить его с базой данных. Такой факт находится, ответ: да (yes).

?-parent (bob,mary). no

Ответ будет нет (no), так как такого факта в базе данных нет.

 

Переменные

Можно задать вопрос и узнать, кто родитель liz:

?-parent (X, liz).

X= tom

Здесь X - переменная. Ее величина неизвестна и она может принимать значения. В данном случае ее значением будет объект, для которого это утверждение истинно.

?-parent (X, bob). X=tom X=pam

Можно задать вопрос, кто является чьим родителем.
Или найти такие X и Y, что X является родителем Y.

?-parent (X, Y).

X= pam
Y= bob
Y= tom
X= bob
и т.д.

Конъюнкция целей

Можно задать более общий вопрос: Кто является родителем родителя juli. Так как нет отношения grandparent, то можно разбить на два вопроса:

1. кто родитель juli. Предположим- Y.

2. кто родитель Y. Предположим- X.

?-parent (Y, juli), parent (X, Y). X=bob Y=pat

При поиске решения сначала находится Y, а затем по второму условию Х.
Вопрос:        Кто внуки тома?:

?-parent (tom, Y), parent (Y, X). Y=bob X=ann Y=bob X=pat

И наконец, есть ли у ann и pat общий родитель?

?-parent (Y, ann), parent(Y, pat). Y=bob

 

Правила

  Введем отношение peбенок child, обратное к parent "родитель".
Можно было бы определить аналогично:  

                   child (liz, tom).

Но можно использовать, что отношение child обратно к parent и записать в виде утверждения- правила:  

                 child(Y, X):-parent (X, Y).

Правило читается так:

Для всех X и Y
Y -child X, если
X -parent Y.

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

       child(Y, X):- parent (X, Y).

 

Голова - head

Тело - body

Если условие parent (X, Y). выполняется, то логическим следствием из него будет утверждение child(Y, X).

Рассмотрим, как правило используется прологом.

Зададим вопрос        ?-child(liz, tom).

  В программе нет данных о child. Но есть правило, которое верно для всех X Y, в том числе для liz и tom. Мы должны применить правило для этих значений. Надо подставить в правило вместо X - tom, a вместо Y - liz.

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

child(liz, tom):-parent (tom, liz).

Условная часть приняла вид            parent (tom, liz).

   Теперь надо выяснить выполняется ли это условие. Исходная цель child(liz,tom) заменяется подцелью parent (tom, liz)., которая выполняется, поэтому пролог ответит "yes".