Данная глава посвящена устройству вычислений в Прологе. Дается представление о машине вывода Пролога. Рассматривается конструкция сложных термов и понятие отрицания в языке Пролог. Показывается, как использовать трассировку в PIE и отладчик системы Visual Prolog.
Основными механизмами машины вывода Пролога являются унификация и откат. При унификации термов и атомарных формул находится наибольший общий унификатор. Откат используется для поиска всех решений.
Формулы $$A$$ и $$B$$ называются унифицируемыми, если существует такая подстановка $$\theta$$ термов вместо переменных, что $$A\theta = B\theta$$. Подстановка ? называется при этом унификатором формул $$A$$ и $$B$$.
Например, формулы $$p(x)$$ и $$p(y)$$ унифицирует любая из подстановок $$\{x = y\}$$ и $$\{x = a, y = a\}$$.
Композицией подстановок $$\theta_1$$ и $$\theta_2$$ называется подстановка $$\theta = \theta_1 \theta_2$$, которая получается из подстановки $$\theta_1$$ применением к ее равенствам подстановки $$\theta_2$$, так что равенства $$x = t$$ преобразуются в равенства $$x = t\theta_2$$, с последующим удалением равенств вида $$y = y$$, и добавлением равенств $$z = s$$ из $$\theta_2$$ для переменных $$z$$, не встречающихся в левых частях равенств $$z = r$$ в подстановке $$\theta_1$$.
Например, композицией подстановок $$\{x = y\}$$ и $$\{y = a\}$$ является подстановка $$\{x = a, y = a\}$$.
Унификатор $$\theta$$ формул $$A$$ и $$B$$ называется наибольшим общим унификатором, если для любого другого унификатора $$\theta_1$$ этих формул найдется такая подстановка $$\theta_2$$2, что $$\theta_1=\theta \theta_2$$.
Например, наибольшим общим унификатором формул $$p(x)$$ и $$p(y)$$ является подстановка $$\theta = \{x = y\}$$. Если, в частности, $$\theta_1 = \{x = a, y = a\}$$, то, взяв $$\theta_2 = \{y = a\}$$, получим: $$\theta \theta_2=\theta_1$$.
Построение наибольшего общего унификатора двух формул сводится к последовательному выявлению и устранению их различий.
Множество рассогласований формул $$A$$ и $$B$$ — это самая левая пара несовпадающих термов, стоящих в этих формулах на одинаковых позициях.
Например, множество рассогласований формул $$p(x, f(g(y, h(z)), b))$$ и $$p(x, f(g(y, a), c))$$ равно $$\{h(z), a\}$$.
Алгоритм поиска наибольшего общего унификатора $$\theta$$ формул $$A$$ и $$B$$ заключается в следующем. На нулевой итерации полагается $$\theta_0=\varnothing$$, $$A_0 = A$$ и $$B_0 = B$$. На итерации $$k$$, начиная с $$k = 0$$, выполняются следующие действия:
Например, найдем наибольший общий унификатор формул $$p(x, x, f(g(a)))$$ и $$p(y, b, f(z))$$ с переменными $$x$$, $$y$$ и $$z $$ и константами $$a$$ и $$b$$. Множество рассогласований имеет вид: $$\{x, y\}$$. Применим к формулам подстановку $$\{x = y\}$$ и получим формулы $$p(y, y, f(g(a)))$$ и $$p(y, b, f(z))$$. Множество рассогласований этих формул равно $$\{y, b\}$$. Соответственно, применим к этой паре формул подстановку $$\{y = b\}$$ и получим формулы $$p(b, b, f(g(a)))$$ и $$p(b, b, f(z))$$. Множество рассогласований последних формул выглядит следующим образом: $$\{g(a), z\}$$. Применим к данным формулам подстановку $$\{z = g(a)\}$$ и получим полностью совпадающие формулы, равные $$p(b, b, f(g(a)))$$. Наибольший общий унификатор $$\theta$$ равен композиции подстановок:
$$\theta = \{x = y\}\{y = b\}\{z = g(a)\} = \{x = b, y = b, z = g(a)\}$$.
Процедурная семантика программы отвечает на вопрос, как устроены вычисления. Вычисления в классическом случае проводятся в соответствии с методом SLD-резолюции (Selected Linear Defined Resolution) [7, 9].
Пусть $$Q = ?- C_1, …, C_{i – 1}, C_i, C_{i + 1}, \dots, C_m $$ — запрос к логической программе, $$B_0:- B_1, \dots, B_n$$ — вариант $$D$$ правила $$A_0:- A_1, \dots, A_n$$, такой что в нем и в запросе нет совпадающих переменных, и $$\theta$$ — наибольший общий унификатор формул $$C_i $$и $$B_0$$.
SLD-резольвентой запроса $$Q$$ и правила $$D$$ с подстановкой $$\theta$$ называется запрос $$Q = ?- (C_1, \dots, C_{i – 1}, B_1, \dots, B_n, C_{i + 1}, \dots, C_m)\theta$$.
Положим $$Q_0 = Q$$. Частичным SLD-резолютивным вычислением называется последовательность троек $$(D_i, \theta_i, Q_i)$$, в которой $$Q_i$$ является SLD-резольвентой запроса $$Q_{i – 1}$$ и правила $$D_{i – 1}$$ с подстановкой $$\theta_{i – 1}$$. Такое вычисление называется успешным, если на некотором шаге $$n$$ получается пустой дизъюнкт: $$Q_n=\Box$$. Ответом на запрос, в случае успешного вычисления, является композиция подстановок $$\theta = \theta _1\theta _2\dots\theta _n$$, ограниченная переменными запроса $$Q$$.
Процедурным значением программы является множество простых замкнутых целей из эрбранова базиса, которые выводятся из программы с помощью SLD-резолютивного вывода. Вернемся к программе (см. п. 1.1):
млекопитающее("слон").
млекопитающее("зебра").
животное("страус").
животное("уж").
животное(X):- млекопитающее(X).
Рассмотрим цель $$Q_0 = ?- животное(слон)$$. SLD-резольвентой этого запроса и правила $$D_0$$ вида $$животное(A):- млекопитающее(A)$$ с подстановкой $$\theta_0= \{A = слон\}$$ является запрос $$Q_1 = ?- млекопитающее(слон)$$. SLD-резольвентной этого запроса и правила с пустым телом $$D_1 млекопитающее(слон)$$ с пустой подстановкой является пустой запрос. Таким образом, цель $$животное(слон)$$ выводится из программы. Легко проверить, что все цели из минимальной модели $$I_0$$ выводятся из программы, а остальные цели из эрбранова базиса не выводятся. Это верно и в общем случае: декларативное и процедурное значения классической логической программы совпадают.
Пространство вычислений в классическом Прологе представляется в виде дерева, вершинами которого являются SLD-резольвенты родителя и одного из правил, а ребра соответствуют унифицирующим постановкам. Корень дерева — это цель программы. Листьями являются пустые запросы, которые завершают успешные вычисления, и запросы, не имеющие SLD-резольвент, которые завершают тупиковые вычисления (рис. 2.1). Это дерево называется деревом SLD-резолютивных вычислений.
(рис 2.1) Дерево SLD-резолютивных вычислений для запроса животное(A)
Вычисления в языке Пролог соответствуют обходу дерева в глубину. Правила программы упорядочиваются сверху вниз. Выделяется самая левая подцель запроса, затем на каждом шаге вычисления к нему применяется первое еще неиспользованное правило программы для данного предикатного символа, при этом в стеке запоминается возможное разветвление — следующее правило. Когда вычисление заходит в тупик или успешно завершается, происходит возврат в точку последнего разветвления, при этом результаты всех предыдущих подстановок отменяются. Вычисления заканчиваются, когда стек разветвлений становится пустым. Недостатком такой стратегии является существование возможности попасть на бесконечную ветвь дерева вычислений, с которой программа не может выбраться, теряется полнота вычислений. Полнотой обладает обход дерева в ширину, он обнаруживает все успешные вычисления произвольного запроса. Но обход в ширину требует слишком большого расхода памяти, поэтому стандартной стратегией вычислений в Прологе является поиск в глубину.
Для того чтобы проследить за устройством вычислений в программе на языке Пролог возьмем следующий пример.
родитель("Иван", "Мария").
родитель("Анна", "Мария").
родитель("Мария", "Павел").
родитель("Мария", "Петр").
женщина("Мария").
женщина("Анна").
мать(X, Y):- женщина(X), родитель(X, Y).
Рассмотрим процесс поиска решений для цели
мать(X, Y).
Переменные X и Y в этой цели свободны, они не имеют значений при вызове предиката. Свободная переменная унифицируется с любым термом. Решением называется набор значений переменных.
С декларативной точки зрения, нужно найти все пары значений переменных, которые принадлежат бинарному отношению мать/2. Результат имеет вид:
X = Мария, Y = Павел X = Мария, Y = Петр X = Анна, Y = Мария
Когда программа приступает к вычислению ответа на запрос, она просматривает все предложения программы сверху вниз и находит первое из них, с заголовком которого унифицируется первая подцель. Переменные правила автоматически переименовываются, так чтобы среди них не было переменных запроса.
Первое правило, с заголовком которого унифицируется цель, имеет вид:
мать(X1, Y1):- женщина(X1), родитель(X1, Y1).
Атомарные формулы мать(X, Y) и мать(X1, Y1) унифицирует подстановка X1 = X, Y1 = Y.
Вычисления соответствуют принципу: заголовок правила истинен, если истинно его тело. Исходная простая цель заменяется последовательностью подцелей из тела правила. Новая цель имеет вид:
женщина(X), родитель(X, Y).
Это цель составная, конъюнктивная. В конъюнктивном запросе переменные с одинаковым именем должны получить одно и то же значение. Сначала вызывается первая подцель:
женщина(X).
При вызове каждой простой цели программа заново просматривает все предложения сверху вниз и ищет такие, с заголовками которых унифицируется текущая цель. Первое из этих правил (с пустым телом) имеет вид:
женщина("Мария").
Возле этого правила ставится точка возврата, для того чтобы при вычислении других вариантов ответа поиск вести с указанного места. Переменная X принимает значение, т. е. конкретизируется значением "Мария" (X = Мария), и это значение передается во вторую подцель, так что новая цель имеет вид:
родитель("Мария", Y).
Правила снова просматриваются сверху вниз, и цель унифицируется с заголовком правила
родитель("Мария", "Павел").
При этом Y = Павел. Возле этого правила также ставится точка возврата.
Тело правила при X = Мария, Y = Павел истинно, поэтому и заголовок мать(X, Y) истинен. В общем случае решение является композицией подстановок, ограниченной переменными цели. Итак, первое решение имеет вид:
X = Мария, Y = Павел.
Теперь делается откат к точке возврата, поставленной последней. При этом переменная Y освобождается от своего значения, а точка возврата удаляется. Цель
родитель("Мария", Y)
унифицируется с заголовком следующего правила (Y = Петр):
родитель("Мария", "Петр").
Само правило помечается точкой возврата. Найдено еще одно решение:
X = Мария, Y = Петр
Делается откат к последней точке возврата, при этом переменная Y освобождается от своего значения. Больше правил нет, поэтому эта точка возврата просто удаляется. Теперь идет откат к предыдущей цели, поиск решений для которой начинается с оставшейся точки возврата, при этом переменная X освобождается от своего значения, а точка возврата удаляется. Цель снова принимает вид:
женщина(X), родитель(X, Y).
Подцель
женщина(X)
унифицируется с заголовком следующего правила (X = Анна):
женщина("Анна").
Возле правила ставится точка возврата. Новая цель имеет вид:
родитель("Анна", Y).
Она унифицируется с заголовком правила (Y = Мария):
родитель("Анна", "Мария").
Возле этого правила также ставится точка возврата. Находится еще одно решение:
X = Анна, Y = Мария
Откат к последней точке возврата приводит только к ее удалению, то же самое происходит с предыдущей точкой возврата. Других решений нет.
Процедура вычислений в языке Пролог моделируется в виде дерева поиска (рис. 2.2). Вершины дерева соответствуют простым целям, а ребра — унифицирующим подстановкам. В дереве мы указали также решения — композиции подстановок. Процедура вычислений соответствует обходу дерева в глубину.
(рис 2.2) Дерево поиска для цели мать(X, Y)
Рассмотрим пример поиска решений для дизъюнктивной цели.
мужчина("Иван").
мужчина("Павел").
мужчина("Петр").
женщина("Мария").
женщина("Анна").
При поиске решений для дизъюнктивной цели:
женщина(X); мужчина(X).
сначала находятся решения до знака дизъюнкции, а потом после него. Переменные, разделенные знаками дизъюнкции, между собой не связаны. Поэтому решение имеет вид:
X = Мария X = Анна X = Иван X = Павел X = Петр
Если цель имеет несколько знаков дизъюнкции, то сначала находятся решения до первого знака, потом до второго, и т. д.
Итак, машина вывода Пролога использует для доказательства цели поиск в глубину. Цели доказываются всеми возможными способами, т. е. находятся все решения. Если цель не имеет переменных, то проверяется ее истинность или ложность. Если цель имеет решение, то говорят, что она успешна. Если цель не имеет решений, то она неуспешна. Цель без переменных успешна, если она истинна, и неуспешна в противном случае. Например, вызов предиката fail всегда неуспешный, так как этот предикат имеет значение ложь. С помощью него обычно создается "искусственный" неуспех. В противоположность этому цель succeed() всегда успешна, предикат succeed имеет значение истина. При неуспехе очередной цели Пролог откатывается назад, чтобы найти другие решения, до тех пор пока это возможно. Когда все точки возврата становятся удаленными, и новых целей нет, вычисления заканчиваются.
Переменные, имеющие значение, называют конкретизированными. Остальные переменные называют неконкретизированными. Если аргумент предиката при вызове этого предиката уже имеет значение, то такой аргумент называется входным аргументом, а если не имеет, то выходным аргументом.
Процесс вычислений можно проследить в PIE, включив трассировку. Для включения и выключения трассировки в PIE используется пункт меню Engine > Trace Calls. Протокол вычислений выводится в окне Dialog (рис. 2.3).
Используются следующие операторы:
CALL — вызов цели;RETURN — завершение (возврат результата);REDO — откат (возврат по успеху для поиска других решений);FAIL — возврат по неудаче.
(рис 2.3) Трассировка выполнения цели в PIE
Трассировка вычисления цели мать(X, Y) (см. п. 2.3) отображена на рис. 2.4. Она соответствует полному обходу дерева поиска в глубину (ср. с рис. 2.2).
(рис 2.4) Трассировка выполнения цели мать(X, Y) и обход дерева поиска
Отладчик Visual Prolog запускается с помощью команды меню Debug > Run. Точки останова ставятся с помощью клавиши F9. Переход к первой точке останова, а также переходы между точками останова выполняются с помощью клавиши F5. Окно просмотра значений переменных, которые они принимают в текущем предложении, открывается с помощью команды меню View > Variables for Current Clause (рис. 2.5). Проследить пошаговую процедуру вычислений можно с помощью клавиш F10 и F11.
(рис 2.5) Отладка программ в Visual Prolog
Упражнение 1.
Проследите
процедуру поиска всех птиц (см. листинг 1.1).
Термы бывают простые и сложные. Простые термы — это переменные и константы. Сложные термы — это составные термы и списки.
Составные термы определяются в Прологе так же, как и в математической логике, в виде $$f(t_1, t_2, \dots, t_n)$$ или $$g()$$ (в последнем случае скобки могут быть опущены), где $$f$$ — это $$n$$-арный функциональный символ, $$g$$ — нульарный, а $$t_1, t_2, \dots, t_n$$ — термы. Функциональные символы в языке Пролог называются функторами, а сложные термы называют еще структурами. Для того чтобы получить возможность использовать в программе на языке Visual Prolog составные термы, следует объявить домен этих термов — указать их тип (см. листинг 2.3).
Список — это конечная последовательность элементов. В виде составного терма список можно представить следующим образом: $$cons(1, cons(2, cons(3, nil)))$$, где функтор $$nil $$ обозначает пустой список. Для списков в языке Пролог имеется специальное обозначение. Элементы списка разделяются запятыми и заключаются в квадратные скобки: [1, 2, 3]. Пустой список обозначается [].
Первый элемент списка называется его головой, список остальных элементов — его хвостом. Терм [H | T] обозначает непустой список с головой H и хвостом T. Для списка [1, 2, 3] имеем: H = 1, T = [2, 3].
Для термов вида [1 | [2 | [3 | T]]] используется сокращение [1, 2, 3 | T]. Таким образом, с помощью знака "|" можно отделить как голову списка, так и несколько его первых элементов, после этого знака находится список оставшихся элементов.
Списки унифицируются поэлементно. Например, термы [1, 2, 3 | L] и [A, B | T] унифицирует подстановка A = 1, B = 2, T = [3 | L].
В языке Visual Prolog все элементы списка должны принадлежать одному и тому же домену. Домен списков указывается с помощью приписывания знака "*" к домену элементов списка (см. листинг 2.4).
Анонимная переменная унифицируется с любым термом, но ей не присваивается никакого значения. Так, терм [_, _] унифицируется с любым списком, состоящим ровно из двух элементов, а терм [_ | _] с любым непустым списком.
В следующей программе в виде составных термов описываются печатные издания, которые имеются в домашней библиотеке на книжной полке. Домен publication — это домен термов двух видов, которые представляют два типа печатных изданий — книги и журналы. В объявлении домена для каждого типа термов указывается имя функтора и имена доменов аргументов. Различные типы термов, принадлежащие одному домену, перечисляются через точку с запятой, они называются альтернативами.
publication = book(author, string Название, edition Издание);
magazine(string Название, integer Номер, integer Год).
author = author(string Фамилия, string Имя, string Отчество).
edition = edition(string Место, string Издательство, integer Год).
class facts
library: (publication).
clauses
library(magazine("Компьютерра", 2, 2009)).
library(magazine("Наука и жизнь", 11, 2012)).
library(book(author("Чехов", "Антон", "Павлович"),
"Избранное", edition("Москва", "АСТ, Астрель", 2003))).
library(book(author("Великова", "Людмила", "Викторовна"),
"Русский язык", edition("Москва", "МЦНМО", 2003))).
run():-
% Что есть в библиотеке?
library(X),
write(X), nl,
fail;
% Названия книг, изданных в 2003 году
library(book(_, Title, edition(_, _, 2003))),
write(Title), nl,
fail;
_ = readLine().
Упражнение 2.
Добавьте в программу "Библиотека" (см. листинг 2.3) новые факты, содержащие сведения о книгах и журналах. Используя анонимные переменные, найдите ответы на запросы:
В приведенной ниже программе списки используются для описания сведений об иностранных языках, которые изучает группа студентов.
class facts
knows: (string, string*).
clauses
knows("Даша", ["английский", "испанский", "французский"]).
knows("Маша", ["немецкий", "английский"]).
knows("Глаша", ["английский", "немецкий"]).
knows("Паша", ["английский"]).
run():-
knows(X, Y),
write(X, " - ", Y), nl,
fail;
_ = readLine().
Упражнение 3.
Добавьте в программу "Иностранные языки" (см. листинг 2.4) новые факты. Найдите с помощью программы ответы на запросы:
Для сравнения термов в языке Visual Prolog используются знаки < ("меньше"), <= ("меньше или равно"), > ("больше"), >= ("больше или равно"), = ("равно"), <> или >< ("не равно"). Сравниваемые термы должны принадлежать одному и тому же домену.
Порядок сложных термов по умолчанию определяется следующим образом: $$f(x, y, \dots, z, u, \dots) \leq f(x, y, \dots, z, v, \dots)$$, если $$u \leq v$$. Например,
tuple(5, 8) < tuple(6, 4) и [4, 5] > [1, 2, 3].
Порядок составных термов, домен которых содержит несколько альтернатив, соответствует порядку следования альтернатив в объявлении домена. Например (см. листинг 2.3):
magazine("Наука и жизнь", 6, 2010) >
book(author("Чехов", "Антон", "Павлович"), "Избранное",
edition("Москва", "ЭКСМО", 2012)).
Сравнивать можно только термы, которые не содержат неконкретизированных переменных. Исключение составляет знак равенства.
Знак равенства ($$term_1 = term_2$$) используется как для проверки равенства замкнутых термов, так и для означивания свободных переменных в результате процедуры унификации термов. В языке Visual Prolog требуется, чтобы в результате унификации все свободные переменные стали конкретизированными. Свободные переменные могут находиться в любой части равенства. Например, результат вызова подцели
2 = X, tuple(Y, tuple(4, X)) = tuple(3, Z)
имеет вид:
X = 2, Y = 3, Z = tuple(4, 2)
Унификация термов может выполняться с помощью знака двойного равенства ==. В этом случае, если термы не унифицируемы, возбуждается исключение.
Примером переменной, которая всегда неконкретизирована, является анонимная переменная.
Данный параграф посвящен проблеме отрицания в языке Пролог.
Рассмотрим программу:
супруг("Иван", "Анна").
мужчина("Иван").
мужчина("Петр").
мужчина("Степан").
С декларативной точки зрения цель $$\urcorner супруг(петр, анна)$$ не следует логически из программы, она не принадлежит ее минимальной модели. С другой стороны, это же утверждение верно и для цели $$супруг(петр, анна)$$. В логическом программировании принято "допущение о замкнутости мира" , в предположении которого цель $$\urcorner Q$$Q логически следует из программы, если цель $$Q$$ не следует логически из программы (ее минимальной модели). С процедурной точки зрения такая проблема в общем случае алгоритмически неразрешима.
Для выражения отрицания в языке Пролог используется предикат not/1. Из приведенной выше программы следует, что неженатыми мужчинами, которых можно найти с помощью запроса
?- мужчина(X), not(супруг(X, _)).
являются Петр и Степан, и только они.
Для вычисления целей с отрицаниями применяется правило "отрицания как неудачи" (Not by Failure) — метод SLDNF-резолюции [7]. Пусть $$Q_0 = ?- not(C_1), C_2, \dots, C_m$$ — запрос к программе, дерево SLD-резолютивных вычислений запроса $$?- C_1$$ конечно и все его ветви являются тупиковыми. Тогда SLDNF-резольвентой запроса $$Q_0$$ является запрос $$Q_1 = ?- C_2, \dots, C_m$$, полученный из $$Q_0$$ с помощью пустой подстановки. Если же вычисление запроса $$?- C_1$$ успешно, то запрос $$Q_0$$ терпит неуспех.
Таким образом, цель not(p) успешна в точности тогда, когда цель p неуспешна. При вычислении цели not(p) вызывается цель p. Если цель p имеет хотя бы одно решение и дерево вычислений этой цели конечно, то цель not(p) считается неуспешной. В противном случае, если дерево вычислений цели p конечно, но все его ветви — тупиковые, цель not(p) считается успешной. Откат под знаком отрицания после достижения цели не производится (для другого доказательства цели), значения из-под него не возвращаются. Под знаком отрицания неконкретизированные переменные считаются анонимными.
Упражнение 4.
Сформулируйте запрос к программе "Родственные отношения" (см. листинг 1.2): найти незамужних сестер (известных программе), т. е. незамужних женщин, у которых есть сестры или братья (для этого в программе нужно определить отношение "сестра"). Найдите ответ на этот запрос
Следующая программа посвящена вычислению возраста студентов и определению самых юных из них. Студент — самый юный, если моложе его по возрасту никого нет. Возраст определяется как разность между текущим годом и годом рождения. Сведения о датах рождения хранятся в базе данных. Текущий год считывается автоматически из системы.
domains
date = date(integer День, integer Месяц, integer Год).
class facts
dateOfBirth: (string Имя, date ДатаРождения).
clauses
dateOfBirth("Елизавета", date(2, 5, 1999)).
dateOfBirth("Тимофей", date(10, 10, 2000)).
dateOfBirth("Даниил", date(25, 2, 2000)).
% …
class predicates
age: (string Name, integer Age) nondeterm (o,o).
youngestPerson: (string Name, integer Age) nondeterm (o,o).
clauses
age(Name, Age):-
Time = time::new(),
Time:getDate(CurrentYear, _M, _D),
dateOfBirth(Name, date(_, _, YearOfBirth)),
Age = CurrentYear - YearOfBirth.
youngestPerson(Name, Age):-
age(Name, Age),
not((age(_, X), X < Age)).
run():-
youngestPerson(Name, Age),
write(Name, " - ", Age), nl,
fail;
_ = readLine().
Для определения текущего года в программе создается объект класса time. Переменная Time хранит указатель на объект класса time. Методы объектов вызываются следующим образом: пишется указатель на объект, ставится знак двоеточия, затем пишется имя предиката. Предикат getDate/3 возвращает текущую дату (установленную на компьютере) — год, месяц и день.
Упражнение 5.
В следующей программе отрицание используется для определения более сложных родственных отношений, чем те, что рассматривались ранее.
class facts - relatives
parent: (string Родитель, string Ребенок).
spouse: (string Муж, string Жена).
male: (string).
female: (string).
class predicates
sister: (string Сестра, string Чья) nondeterm (o,o).
bloodSister: (string Сестра, string Чья) nondeterm (o,o).
halfSister: (string Сестра, string Чья) nondeterm (o,o).
haveCommonFather: (string, string) nondeterm anyflow.
haveCommonMother: (string, string) nondeterm anyflow.
clauses
sister(X, Y):-
bloodSister(X, Y);
halfSister(X, Y).
bloodSister(X, Y):-
female(X),
haveCommonFather(X, Y),
haveCommonMother(X, Y).
halfSister(X, Y):-
female(X),
(haveCommonFather(X, Y),
not(haveCommonMother(X, Y));
haveCommonMother(X, Y),
not(haveCommonFather(X, Y))).
haveCommonFather(X, Y):-
male(Z),
parent(Z, X),
parent(Z, Y),
X <> Y.
haveCommonMother(X, Y):-
female(Z),
parent(Z, X),
parent(Z, Y),
X <> Y.
run():-
file::consult("family.txt", relatives),
sister(X, Y),
write(X, " - сестра для - ", Y), nl,
fail;
_ = readLine().
Найдите с помощью программы "Библиотека" ответы на запросы:
getDate/3).Найдите ответ на вопросы с помощью программы "Иностранные языки":
Дополните программу новыми фактами.
Определите через базовые отношения "родитель", "мужчина", "женщина" и "супруг" следующие отношения:
(см. листинг 2.6).
Напишите программу, которая выводит названия месяцев
Напишите программу, которая из набора точек с целыми координатами на плоскости выбирает пары ближайших к друг другу точек. Каждая точка хранится в отдельном факте вида:
point(pnt(-1, 3)).
Приведите пример таких фактов, определяющих отношения "родитель" и "мужчина", чтобы запросы
male(X), parent(X, _) и male(X), not(not(parent(X, _)))
имели разный набор решений.
Найдите процедурное значение программы "Птицы" (листинг 1.1).
Постройте дерево SLD-резолютивных вычислений для запроса ?- родитель(X, Y), родитель(Y, Z) к программе из листинга 2.1.
Данная глава посвящена устройству вычислений в Прологе. Дается представление о машине вывода Пролога. Рассматривается конструкция сложных термов и понятие отрицания в языке Пролог. Показывается, как использовать трассировку в PIE и отладчик системы Visual Prolog.
Основными механизмами машины вывода Пролога являются унификация и откат. При унификации термов и атомарных формул находится наибольший общий унификатор. Откат используется для поиска всех решений.
Формулы $$A$$ и $$B$$ называются унифицируемыми, если существует такая подстановка $$\theta$$ термов вместо переменных, что $$A\theta = B\theta$$. Подстановка ? называется при этом унификатором формул $$A$$ и $$B$$.
Например, формулы $$p(x)$$ и $$p(y)$$ унифицирует любая из подстановок $$\{x = y\}$$ и $$\{x = a, y = a\}$$.
Композицией подстановок $$\theta_1$$ и $$\theta_2$$ называется подстановка $$\theta = \theta_1 \theta_2$$, которая получается из подстановки $$\theta_1$$ применением к ее равенствам подстановки $$\theta_2$$, так что равенства $$x = t$$ преобразуются в равенства $$x = t\theta_2$$, с последующим удалением равенств вида $$y = y$$, и добавлением равенств $$z = s$$ из $$\theta_2$$ для переменных $$z$$, не встречающихся в левых частях равенств $$z = r$$ в подстановке $$\theta_1$$.
Например, композицией подстановок $$\{x = y\}$$ и $$\{y = a\}$$ является подстановка $$\{x = a, y = a\}$$.
Унификатор $$\theta$$ формул $$A$$ и $$B$$ называется наибольшим общим унификатором, если для любого другого унификатора $$\theta_1$$ этих формул найдется такая подстановка $$\theta_2$$2, что $$\theta_1=\theta \theta_2$$.
Например, наибольшим общим унификатором формул $$p(x)$$ и $$p(y)$$ является подстановка $$\theta = \{x = y\}$$. Если, в частности, $$\theta_1 = \{x = a, y = a\}$$, то, взяв $$\theta_2 = \{y = a\}$$, получим: $$\theta \theta_2=\theta_1$$.
Построение наибольшего общего унификатора двух формул сводится к последовательному выявлению и устранению их различий.
Множество рассогласований формул $$A$$ и $$B$$ — это самая левая пара несовпадающих термов, стоящих в этих формулах на одинаковых позициях.
Например, множество рассогласований формул $$p(x, f(g(y, h(z)), b))$$ и $$p(x, f(g(y, a), c))$$ равно $$\{h(z), a\}$$.
Алгоритм поиска наибольшего общего унификатора $$\theta$$ формул $$A$$ и $$B$$ заключается в следующем. На нулевой итерации полагается $$\theta_0=\varnothing$$, $$A_0 = A$$ и $$B_0 = B$$. На итерации $$k$$, начиная с $$k = 0$$, выполняются следующие действия:
Например, найдем наибольший общий унификатор формул $$p(x, x, f(g(a)))$$ и $$p(y, b, f(z))$$ с переменными $$x$$, $$y$$ и $$z $$ и константами $$a$$ и $$b$$. Множество рассогласований имеет вид: $$\{x, y\}$$. Применим к формулам подстановку $$\{x = y\}$$ и получим формулы $$p(y, y, f(g(a)))$$ и $$p(y, b, f(z))$$. Множество рассогласований этих формул равно $$\{y, b\}$$. Соответственно, применим к этой паре формул подстановку $$\{y = b\}$$ и получим формулы $$p(b, b, f(g(a)))$$ и $$p(b, b, f(z))$$. Множество рассогласований последних формул выглядит следующим образом: $$\{g(a), z\}$$. Применим к данным формулам подстановку $$\{z = g(a)\}$$ и получим полностью совпадающие формулы, равные $$p(b, b, f(g(a)))$$. Наибольший общий унификатор $$\theta$$ равен композиции подстановок:
$$\theta = \{x = y\}\{y = b\}\{z = g(a)\} = \{x = b, y = b, z = g(a)\}$$.
Процедурная семантика программы отвечает на вопрос, как устроены вычисления. Вычисления в классическом случае проводятся в соответствии с методом SLD-резолюции (Selected Linear Defined Resolution) [7, 9].
Пусть $$Q = ?- C_1, …, C_{i – 1}, C_i, C_{i + 1}, \dots, C_m $$ — запрос к логической программе, $$B_0:- B_1, \dots, B_n$$ — вариант $$D$$ правила $$A_0:- A_1, \dots, A_n$$, такой что в нем и в запросе нет совпадающих переменных, и $$\theta$$ — наибольший общий унификатор формул $$C_i $$и $$B_0$$.
SLD-резольвентой запроса $$Q$$ и правила $$D$$ с подстановкой $$\theta$$ называется запрос $$Q = ?- (C_1, \dots, C_{i – 1}, B_1, \dots, B_n, C_{i + 1}, \dots, C_m)\theta$$.
Положим $$Q_0 = Q$$. Частичным SLD-резолютивным вычислением называется последовательность троек $$(D_i, \theta_i, Q_i)$$, в которой $$Q_i$$ является SLD-резольвентой запроса $$Q_{i – 1}$$ и правила $$D_{i – 1}$$ с подстановкой $$\theta_{i – 1}$$. Такое вычисление называется успешным, если на некотором шаге $$n$$ получается пустой дизъюнкт: $$Q_n=\Box$$. Ответом на запрос, в случае успешного вычисления, является композиция подстановок $$\theta = \theta _1\theta _2\dots\theta _n$$, ограниченная переменными запроса $$Q$$.
Процедурным значением программы является множество простых замкнутых целей из эрбранова базиса, которые выводятся из программы с помощью SLD-резолютивного вывода. Вернемся к программе (см. п. 1.1):
млекопитающее("слон").
млекопитающее("зебра").
животное("страус").
животное("уж").
животное(X):- млекопитающее(X).
Рассмотрим цель $$Q_0 = ?- животное(слон)$$. SLD-резольвентой этого запроса и правила $$D_0$$ вида $$животное(A):- млекопитающее(A)$$ с подстановкой $$\theta_0= \{A = слон\}$$ является запрос $$Q_1 = ?- млекопитающее(слон)$$. SLD-резольвентной этого запроса и правила с пустым телом $$D_1 млекопитающее(слон)$$ с пустой подстановкой является пустой запрос. Таким образом, цель $$животное(слон)$$ выводится из программы. Легко проверить, что все цели из минимальной модели $$I_0$$ выводятся из программы, а остальные цели из эрбранова базиса не выводятся. Это верно и в общем случае: декларативное и процедурное значения классической логической программы совпадают.
Пространство вычислений в классическом Прологе представляется в виде дерева, вершинами которого являются SLD-резольвенты родителя и одного из правил, а ребра соответствуют унифицирующим постановкам. Корень дерева — это цель программы. Листьями являются пустые запросы, которые завершают успешные вычисления, и запросы, не имеющие SLD-резольвент, которые завершают тупиковые вычисления (рис. 2.1). Это дерево называется деревом SLD-резолютивных вычислений.
(рис 2.1) Дерево SLD-резолютивных вычислений для запроса животное(A)
Вычисления в языке Пролог соответствуют обходу дерева в глубину. Правила программы упорядочиваются сверху вниз. Выделяется самая левая подцель запроса, затем на каждом шаге вычисления к нему применяется первое еще неиспользованное правило программы для данного предикатного символа, при этом в стеке запоминается возможное разветвление — следующее правило. Когда вычисление заходит в тупик или успешно завершается, происходит возврат в точку последнего разветвления, при этом результаты всех предыдущих подстановок отменяются. Вычисления заканчиваются, когда стек разветвлений становится пустым. Недостатком такой стратегии является существование возможности попасть на бесконечную ветвь дерева вычислений, с которой программа не может выбраться, теряется полнота вычислений. Полнотой обладает обход дерева в ширину, он обнаруживает все успешные вычисления произвольного запроса. Но обход в ширину требует слишком большого расхода памяти, поэтому стандартной стратегией вычислений в Прологе является поиск в глубину.
Для того чтобы проследить за устройством вычислений в программе на языке Пролог возьмем следующий пример.
родитель("Иван", "Мария").
родитель("Анна", "Мария").
родитель("Мария", "Павел").
родитель("Мария", "Петр").
женщина("Мария").
женщина("Анна").
мать(X, Y):- женщина(X), родитель(X, Y).
Рассмотрим процесс поиска решений для цели
мать(X, Y).
Переменные X и Y в этой цели свободны, они не имеют значений при вызове предиката. Свободная переменная унифицируется с любым термом. Решением называется набор значений переменных.
С декларативной точки зрения, нужно найти все пары значений переменных, которые принадлежат бинарному отношению мать/2. Результат имеет вид:
X = Мария, Y = Павел X = Мария, Y = Петр X = Анна, Y = Мария
Когда программа приступает к вычислению ответа на запрос, она просматривает все предложения программы сверху вниз и находит первое из них, с заголовком которого унифицируется первая подцель. Переменные правила автоматически переименовываются, так чтобы среди них не было переменных запроса.
Первое правило, с заголовком которого унифицируется цель, имеет вид:
мать(X1, Y1):- женщина(X1), родитель(X1, Y1).
Атомарные формулы мать(X, Y) и мать(X1, Y1) унифицирует подстановка X1 = X, Y1 = Y.
Вычисления соответствуют принципу: заголовок правила истинен, если истинно его тело. Исходная простая цель заменяется последовательностью подцелей из тела правила. Новая цель имеет вид:
женщина(X), родитель(X, Y).
Это цель составная, конъюнктивная. В конъюнктивном запросе переменные с одинаковым именем должны получить одно и то же значение. Сначала вызывается первая подцель:
женщина(X).
При вызове каждой простой цели программа заново просматривает все предложения сверху вниз и ищет такие, с заголовками которых унифицируется текущая цель. Первое из этих правил (с пустым телом) имеет вид:
женщина("Мария").
Возле этого правила ставится точка возврата, для того чтобы при вычислении других вариантов ответа поиск вести с указанного места. Переменная X принимает значение, т. е. конкретизируется значением "Мария" (X = Мария), и это значение передается во вторую подцель, так что новая цель имеет вид:
родитель("Мария", Y).
Правила снова просматриваются сверху вниз, и цель унифицируется с заголовком правила
родитель("Мария", "Павел").
При этом Y = Павел. Возле этого правила также ставится точка возврата.
Тело правила при X = Мария, Y = Павел истинно, поэтому и заголовок мать(X, Y) истинен. В общем случае решение является композицией подстановок, ограниченной переменными цели. Итак, первое решение имеет вид:
X = Мария, Y = Павел.
Теперь делается откат к точке возврата, поставленной последней. При этом переменная Y освобождается от своего значения, а точка возврата удаляется. Цель
родитель("Мария", Y)
унифицируется с заголовком следующего правила (Y = Петр):
родитель("Мария", "Петр").
Само правило помечается точкой возврата. Найдено еще одно решение:
X = Мария, Y = Петр
Делается откат к последней точке возврата, при этом переменная Y освобождается от своего значения. Больше правил нет, поэтому эта точка возврата просто удаляется. Теперь идет откат к предыдущей цели, поиск решений для которой начинается с оставшейся точки возврата, при этом переменная X освобождается от своего значения, а точка возврата удаляется. Цель снова принимает вид:
женщина(X), родитель(X, Y).
Подцель
женщина(X)
унифицируется с заголовком следующего правила (X = Анна):
женщина("Анна").
Возле правила ставится точка возврата. Новая цель имеет вид:
родитель("Анна", Y).
Она унифицируется с заголовком правила (Y = Мария):
родитель("Анна", "Мария").
Возле этого правила также ставится точка возврата. Находится еще одно решение:
X = Анна, Y = Мария
Откат к последней точке возврата приводит только к ее удалению, то же самое происходит с предыдущей точкой возврата. Других решений нет.
Процедура вычислений в языке Пролог моделируется в виде дерева поиска (рис. 2.2). Вершины дерева соответствуют простым целям, а ребра — унифицирующим подстановкам. В дереве мы указали также решения — композиции подстановок. Процедура вычислений соответствует обходу дерева в глубину.
(рис 2.2) Дерево поиска для цели мать(X, Y)
Рассмотрим пример поиска решений для дизъюнктивной цели.
мужчина("Иван").
мужчина("Павел").
мужчина("Петр").
женщина("Мария").
женщина("Анна").
При поиске решений для дизъюнктивной цели:
женщина(X); мужчина(X).
сначала находятся решения до знака дизъюнкции, а потом после него. Переменные, разделенные знаками дизъюнкции, между собой не связаны. Поэтому решение имеет вид:
X = Мария X = Анна X = Иван X = Павел X = Петр
Если цель имеет несколько знаков дизъюнкции, то сначала находятся решения до первого знака, потом до второго, и т. д.
Итак, машина вывода Пролога использует для доказательства цели поиск в глубину. Цели доказываются всеми возможными способами, т. е. находятся все решения. Если цель не имеет переменных, то проверяется ее истинность или ложность. Если цель имеет решение, то говорят, что она успешна. Если цель не имеет решений, то она неуспешна. Цель без переменных успешна, если она истинна, и неуспешна в противном случае. Например, вызов предиката fail всегда неуспешный, так как этот предикат имеет значение ложь. С помощью него обычно создается "искусственный" неуспех. В противоположность этому цель succeed() всегда успешна, предикат succeed имеет значение истина. При неуспехе очередной цели Пролог откатывается назад, чтобы найти другие решения, до тех пор пока это возможно. Когда все точки возврата становятся удаленными, и новых целей нет, вычисления заканчиваются.
Переменные, имеющие значение, называют конкретизированными. Остальные переменные называют неконкретизированными. Если аргумент предиката при вызове этого предиката уже имеет значение, то такой аргумент называется входным аргументом, а если не имеет, то выходным аргументом.
Процесс вычислений можно проследить в PIE, включив трассировку. Для включения и выключения трассировки в PIE используется пункт меню Engine > Trace Calls. Протокол вычислений выводится в окне Dialog (рис. 2.3).
Используются следующие операторы:
CALL — вызов цели;RETURN — завершение (возврат результата);REDO — откат (возврат по успеху для поиска других решений);FAIL — возврат по неудаче.(рис 2.3) Трассировка выполнения цели в PIE
Трассировка вычисления цели мать(X, Y) (см. п. 2.3) отображена на рис. 2.4. Она соответствует полному обходу дерева поиска в глубину (ср. с рис. 2.2).
(рис 2.4) Трассировка выполнения цели мать(X, Y) и обход дерева поиска
Отладчик Visual Prolog запускается с помощью команды меню Debug > Run. Точки останова ставятся с помощью клавиши F9. Переход к первой точке останова, а также переходы между точками останова выполняются с помощью клавиши F5. Окно просмотра значений переменных, которые они принимают в текущем предложении, открывается с помощью команды меню View > Variables for Current Clause (рис. 2.5). Проследить пошаговую процедуру вычислений можно с помощью клавиш F10 и F11.
(рис 2.5) Отладка программ в Visual Prolog
Упражнение 1.
Проследите
процедуру поиска всех птиц (см. листинг 1.1).
Термы бывают простые и сложные. Простые термы — это переменные и константы. Сложные термы — это составные термы и списки.
Составные термы определяются в Прологе так же, как и в математической логике, в виде $$f(t_1, t_2, \dots, t_n)$$ или $$g()$$ (в последнем случае скобки могут быть опущены), где $$f$$ — это $$n$$-арный функциональный символ, $$g$$ — нульарный, а $$t_1, t_2, \dots, t_n$$ — термы. Функциональные символы в языке Пролог называются функторами, а сложные термы называют еще структурами. Для того чтобы получить возможность использовать в программе на языке Visual Prolog составные термы, следует объявить домен этих термов — указать их тип (см. листинг 2.3).
Список — это конечная последовательность элементов. В виде составного терма список можно представить следующим образом: $$cons(1, cons(2, cons(3, nil)))$$, где функтор $$nil $$ обозначает пустой список. Для списков в языке Пролог имеется специальное обозначение. Элементы списка разделяются запятыми и заключаются в квадратные скобки: [1, 2, 3]. Пустой список обозначается [].
Первый элемент списка называется его головой, список остальных элементов — его хвостом. Терм [H | T] обозначает непустой список с головой H и хвостом T. Для списка [1, 2, 3] имеем: H = 1, T = [2, 3].
Для термов вида [1 | [2 | [3 | T]]] используется сокращение [1, 2, 3 | T]. Таким образом, с помощью знака "|" можно отделить как голову списка, так и несколько его первых элементов, после этого знака находится список оставшихся элементов.
Списки унифицируются поэлементно. Например, термы [1, 2, 3 | L] и [A, B | T] унифицирует подстановка A = 1, B = 2, T = [3 | L].
В языке Visual Prolog все элементы списка должны принадлежать одному и тому же домену. Домен списков указывается с помощью приписывания знака "*" к домену элементов списка (см. листинг 2.4).
Анонимная переменная унифицируется с любым термом, но ей не присваивается никакого значения. Так, терм [_, _] унифицируется с любым списком, состоящим ровно из двух элементов, а терм [_ | _] с любым непустым списком.
В следующей программе в виде составных термов описываются печатные издания, которые имеются в домашней библиотеке на книжной полке. Домен publication — это домен термов двух видов, которые представляют два типа печатных изданий — книги и журналы. В объявлении домена для каждого типа термов указывается имя функтора и имена доменов аргументов. Различные типы термов, принадлежащие одному домену, перечисляются через точку с запятой, они называются альтернативами.
publication = book(author, string Название, edition Издание);
magazine(string Название, integer Номер, integer Год).
author = author(string Фамилия, string Имя, string Отчество).
edition = edition(string Место, string Издательство, integer Год).
class facts
library: (publication).
clauses
library(magazine("Компьютерра", 2, 2009)).
library(magazine("Наука и жизнь", 11, 2012)).
library(book(author("Чехов", "Антон", "Павлович"),
"Избранное", edition("Москва", "АСТ, Астрель", 2003))).
library(book(author("Великова", "Людмила", "Викторовна"),
"Русский язык", edition("Москва", "МЦНМО", 2003))).
run():-
% Что есть в библиотеке?
library(X),
write(X), nl,
fail;
% Названия книг, изданных в 2003 году
library(book(_, Title, edition(_, _, 2003))),
write(Title), nl,
fail;
_ = readLine().
Упражнение 2.
Добавьте в программу "Библиотека" (см. листинг 2.3) новые факты, содержащие сведения о книгах и журналах. Используя анонимные переменные, найдите ответы на запросы:
В приведенной ниже программе списки используются для описания сведений об иностранных языках, которые изучает группа студентов.
class facts
knows: (string, string*).
clauses
knows("Даша", ["английский", "испанский", "французский"]).
knows("Маша", ["немецкий", "английский"]).
knows("Глаша", ["английский", "немецкий"]).
knows("Паша", ["английский"]).
run():-
knows(X, Y),
write(X, " - ", Y), nl,
fail;
_ = readLine().
Упражнение 3.
Добавьте в программу "Иностранные языки" (см. листинг 2.4) новые факты. Найдите с помощью программы ответы на запросы:
Для сравнения термов в языке Visual Prolog используются знаки < ("меньше"), <= ("меньше или равно"), > ("больше"), >= ("больше или равно"), = ("равно"), <> или >< ("не равно"). Сравниваемые термы должны принадлежать одному и тому же домену.
Порядок сложных термов по умолчанию определяется следующим образом: $$f(x, y, \dots, z, u, \dots) \leq f(x, y, \dots, z, v, \dots)$$, если $$u \leq v$$. Например,
tuple(5, 8) < tuple(6, 4) и [4, 5] > [1, 2, 3].
Порядок составных термов, домен которых содержит несколько альтернатив, соответствует порядку следования альтернатив в объявлении домена. Например (см. листинг 2.3):
magazine("Наука и жизнь", 6, 2010) >
book(author("Чехов", "Антон", "Павлович"), "Избранное",
edition("Москва", "ЭКСМО", 2012)).
Сравнивать можно только термы, которые не содержат неконкретизированных переменных. Исключение составляет знак равенства.
Знак равенства ($$term_1 = term_2$$) используется как для проверки равенства замкнутых термов, так и для означивания свободных переменных в результате процедуры унификации термов. В языке Visual Prolog требуется, чтобы в результате унификации все свободные переменные стали конкретизированными. Свободные переменные могут находиться в любой части равенства. Например, результат вызова подцели
2 = X, tuple(Y, tuple(4, X)) = tuple(3, Z)
имеет вид:
X = 2, Y = 3, Z = tuple(4, 2)
Унификация термов может выполняться с помощью знака двойного равенства ==. В этом случае, если термы не унифицируемы, возбуждается исключение.
Примером переменной, которая всегда неконкретизирована, является анонимная переменная.
Данный параграф посвящен проблеме отрицания в языке Пролог.
Рассмотрим программу:
супруг("Иван", "Анна").
мужчина("Иван").
мужчина("Петр").
мужчина("Степан").
С декларативной точки зрения цель $$\urcorner супруг(петр, анна)$$ не следует логически из программы, она не принадлежит ее минимальной модели. С другой стороны, это же утверждение верно и для цели $$супруг(петр, анна)$$. В логическом программировании принято "допущение о замкнутости мира" , в предположении которого цель $$\urcorner Q$$Q логически следует из программы, если цель $$Q$$ не следует логически из программы (ее минимальной модели). С процедурной точки зрения такая проблема в общем случае алгоритмически неразрешима.
Для выражения отрицания в языке Пролог используется предикат not/1. Из приведенной выше программы следует, что неженатыми мужчинами, которых можно найти с помощью запроса
?- мужчина(X), not(супруг(X, _)).
являются Петр и Степан, и только они.
Для вычисления целей с отрицаниями применяется правило "отрицания как неудачи" (Not by Failure) — метод SLDNF-резолюции [7]. Пусть $$Q_0 = ?- not(C_1), C_2, \dots, C_m$$ — запрос к программе, дерево SLD-резолютивных вычислений запроса $$?- C_1$$ конечно и все его ветви являются тупиковыми. Тогда SLDNF-резольвентой запроса $$Q_0$$ является запрос $$Q_1 = ?- C_2, \dots, C_m$$, полученный из $$Q_0$$ с помощью пустой подстановки. Если же вычисление запроса $$?- C_1$$ успешно, то запрос $$Q_0$$ терпит неуспех.
Таким образом, цель not(p) успешна в точности тогда, когда цель p неуспешна. При вычислении цели not(p) вызывается цель p. Если цель p имеет хотя бы одно решение и дерево вычислений этой цели конечно, то цель not(p) считается неуспешной. В противном случае, если дерево вычислений цели p конечно, но все его ветви — тупиковые, цель not(p) считается успешной. Откат под знаком отрицания после достижения цели не производится (для другого доказательства цели), значения из-под него не возвращаются. Под знаком отрицания неконкретизированные переменные считаются анонимными.
Упражнение 4.
Сформулируйте запрос к программе "Родственные отношения" (см. листинг 1.2): найти незамужних сестер (известных программе), т. е. незамужних женщин, у которых есть сестры или братья (для этого в программе нужно определить отношение "сестра"). Найдите ответ на этот запрос
Следующая программа посвящена вычислению возраста студентов и определению самых юных из них. Студент — самый юный, если моложе его по возрасту никого нет. Возраст определяется как разность между текущим годом и годом рождения. Сведения о датах рождения хранятся в базе данных. Текущий год считывается автоматически из системы.
domains
date = date(integer День, integer Месяц, integer Год).
class facts
dateOfBirth: (string Имя, date ДатаРождения).
clauses
dateOfBirth("Елизавета", date(2, 5, 1999)).
dateOfBirth("Тимофей", date(10, 10, 2000)).
dateOfBirth("Даниил", date(25, 2, 2000)).
% …
class predicates
age: (string Name, integer Age) nondeterm (o,o).
youngestPerson: (string Name, integer Age) nondeterm (o,o).
clauses
age(Name, Age):-
Time = time::new(),
Time:getDate(CurrentYear, _M, _D),
dateOfBirth(Name, date(_, _, YearOfBirth)),
Age = CurrentYear - YearOfBirth.
youngestPerson(Name, Age):-
age(Name, Age),
not((age(_, X), X < Age)).
run():-
youngestPerson(Name, Age),
write(Name, " - ", Age), nl,
fail;
_ = readLine().
Для определения текущего года в программе создается объект класса time. Переменная Time хранит указатель на объект класса time. Методы объектов вызываются следующим образом: пишется указатель на объект, ставится знак двоеточия, затем пишется имя предиката. Предикат getDate/3 возвращает текущую дату (установленную на компьютере) — год, месяц и день.
Упражнение 5.
В следующей программе отрицание используется для определения более сложных родственных отношений, чем те, что рассматривались ранее.
class facts - relatives
parent: (string Родитель, string Ребенок).
spouse: (string Муж, string Жена).
male: (string).
female: (string).
class predicates
sister: (string Сестра, string Чья) nondeterm (o,o).
bloodSister: (string Сестра, string Чья) nondeterm (o,o).
halfSister: (string Сестра, string Чья) nondeterm (o,o).
haveCommonFather: (string, string) nondeterm anyflow.
haveCommonMother: (string, string) nondeterm anyflow.
clauses
sister(X, Y):-
bloodSister(X, Y);
halfSister(X, Y).
bloodSister(X, Y):-
female(X),
haveCommonFather(X, Y),
haveCommonMother(X, Y).
halfSister(X, Y):-
female(X),
(haveCommonFather(X, Y),
not(haveCommonMother(X, Y));
haveCommonMother(X, Y),
not(haveCommonFather(X, Y))).
haveCommonFather(X, Y):-
male(Z),
parent(Z, X),
parent(Z, Y),
X <> Y.
haveCommonMother(X, Y):-
female(Z),
parent(Z, X),
parent(Z, Y),
X <> Y.
run():-
file::consult("family.txt", relatives),
sister(X, Y),
write(X, " - сестра для - ", Y), nl,
fail;
_ = readLine().
Найдите с помощью программы "Библиотека" ответы на запросы:
getDate/3).Найдите ответ на вопросы с помощью программы "Иностранные языки":
Дополните программу новыми фактами.
Определите через базовые отношения "родитель", "мужчина", "женщина" и "супруг" следующие отношения:
(см. листинг 2.6).
Напишите программу, которая выводит названия месяцев
Напишите программу, которая из набора точек с целыми координатами на плоскости выбирает пары ближайших к друг другу точек. Каждая точка хранится в отдельном факте вида:
point(pnt(-1, 3)).
Приведите пример таких фактов, определяющих отношения "родитель" и "мужчина", чтобы запросы
male(X), parent(X, _) и male(X), not(not(parent(X, _)))
имели разный набор решений.
Найдите процедурное значение программы "Птицы" (листинг 1.1).
Постройте дерево SLD-резолютивных вычислений для запроса ?- родитель(X, Y), родитель(Y, Z) к программе из листинга 2.1.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.