Семантика языка Prolog

Декларативная семантика программ на языке Пролог.

Язык Пролог является не алгоритмическим,
а

Декларативная семантика программ на языке Пролог.

Декларативная семантика программы
определяет, что истинно

Процедурная семантика программ на языке Пролог.

С другой стороны, чтобы определить

Процедурная семантика программ на языке Пролог.

Процедурная семантика ⎯ это
процедура вычисления

Процедурная семантика программ на языке Пролог.

Назовем эту процедуру именем «Вычислить».

Процедурная семантика языка Пролог
определяет встроенные в Пролог⎯систему
механизмы логического вывода. Рассмотрим
простейшие механизмы

Правило совпадения

Факты в программе не содержат
переменных, а вопрос ⎯ простой и
основной.

Правило обобщения факта

Факты в программе не содержат переменные,
а вопрос ⎯

Правило обобщения факта (Конкретизация переменных)

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

Вычисление конъюнктивного запроса

Процедура поиска ответа на конъюнктивный,
неосновной вопрос из программы, состоящей

SWI Prolog

Вычислительная модель языка Prolog

Алгоритм унификации – основа вычислительной модели языка Пролог

Унификация (или сопоставление)

Правила унификации термов

Правило 1.
Если термы Т1 и Т2 — константы, то

Правила унификации термов

Правило 2.
Если терм Т1—константа или составной
терм, а Т2 —

Правила унификации термов

Правило 3.
Если термы Т1 и Т2 —
неконкретизированные переменные,

Правила унификации термов

Правило 4.
Если Т1 и Т2 ⎯составные термы, то Т1

Явная операция унификации

При выполнении логического вывода скрыто от
пользователя выполняется большое число
операций

Примеры унификации термов

Пример 1.
?⎯2+1=1+2.
no
Составные термы 2+1 и 1+2 не
сопоставимы, и операция

Примеры унификации термов

Пример 2.
?⎯2+1\=1+2.
yes
Операция отрицания сопоставления термов
2+1 и 1+2 успешна.

Примеры унификации термов

Пример 2.
?⎯2+X=2+1.
X=1
yes
Операция сопоставления термов 2+X и 2+1
успешна.

Общая схема согласования целевых утверждений.

Самым общим случаем Пролог⎯программы
является программа, включающая как
факты,

Общая схема согласования целевых утверждений.

Процесс вычисления начинается с
некоторого исходного вопроса Q,

Общая схема согласования целевых утверждений (продолжение)

Допустим, что логическая программа P
состоит из

Общая схема согласования целевых утверждений (продолжение)

1) Цели запроса обрабатываются слева направо,

Общая схема согласования целевых утверждений (продолжение)

2) Предложения программы просматриваются интерпретатором сверху

Общая схема согласования целевых утверждений (продолжение)

3) Если цель Gi сопоставима с

Общая схема согласования целевых утверждений (продолжение)

Редукцией цели Gi с помощью программы

Общая схема согласования целевых утверждений (продолжение)

На каждом этапе вычисления существует
некоторая конъюнкция

Общая схема согласования целевых утверждений (продолжение)

4) Если цель Gi сопоставима с

Общая схема согласования целевых утверждений (продолжение)

5) Когда мы таким образом достигнем

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

Шаг 1 вычисления запроса

Для вычисления запроса “? ⎯ dark(X),big(X). “ интерпретатор

Шаг 2 вычисления запроса

Шаг 2. Текущая резольвента Q2 является конъюнкцией целей black(X),big(X).

Шаг 3 вычисления запроса

Шаг 3. Текущая резольвента Q3 включает одну цель G31

Шаг 4 вычисления запроса

Шаг 4. Текущая резольвента Q4=Q2 является конъюнкцией целей black(X),big(X).

Шаг 5 вычисления запроса

Шаг 5. Текущая резольвента Q5=Q1 является конъюнкцией целей dark(X),big(X).

Шаг 6 вычисления запроса

Шаг 6. Текущая резольвента Q5 является конъюнкцией целей

Шаг 7 вычисления запроса

Шаг 7. Текущая резольвента Q6 включает одну цель

Дерево поиска

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

Дерево поиска

Для каждого утверждения программы, заголовок которого унифицируется с выделенной

Дерево поиска

Лист дерева называется успешной вершиной, если существует подстановка, удовлетворяющая

Дерево поиска

dark(X),big(X).

Редукция цели dark(X)

black(X), big(X).

black(’кот’)

{X=’кот’}

big(’кот’)

{X=’кот’}

неуспех

brown(X), big(X).

brown('медведь')

{X=’медведь’}

успех

успех

big(’медведь’)

X=’медведь’

успех

Механизм автоматического возврата (backtracing)

Когда выполнение программы достигает
тупиковой вершины отмеченной словом
"неуспех", автоматически

Механизм автоматического возврата (backtracing)
Выполнение алгоритм поиска решения можно
представить как обход лабиринта,

Механизм автоматического возврата (backtracing). Понятие маркера.

Для того, чтобы представить работу
механизма автоматического

Механизм автоматического возврата (backtracing). Понятие маркера.

Для каждой цели в запросе Пролог⎯система
создает

Пример поиска решений с возвратом.

Пусть программа «Однокурсники» содержит следующие утверждения:
student_course(X,Y):⎯student(X,K1),

Пример поиска решений с возвратом.

Пусть требуется согласовать запрос:
?⎯ student_course(X,Y).
Этот

Поиск первого решения

При просмотре фактов student в программе маркеры будут передвигаться

Поиск второго решения