§ 42. Встроенные предикаты в логических языках программирования. Простейшие программы

Определения и обозначения

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

Предикат — запись отношения между объектами с именем и фиксированным числом аргументов. Например, родитель(Анна, Борис) может обозначать, что Анна — родитель Бориса. Имя предиката и число его аргументов помогают системе понять, какое именно отношение проверяется.

Встроенный предикат — предикат, заранее реализованный в языке и доступный без определения в программе. Например, read и write отвечают за ввод и вывод. Они нужны, чтобы программа могла выполнять типичные действия, для которых не требуется каждый раз описывать собственное правило.

Унификация — подбор значений переменных, делающий два терма одинаковыми. Если системе нужно сопоставить пару(а, X) и пару(а, 5), она может связать X со значением 5. Унификация лежит в основе поиска ответа на запрос и сопоставления его с фактами и правилами.

Как это устроено

Смысл встроенного предиката и способ его выполнения заранее известны интерпретатору — программе, которая читает и выполняет код Пролога. Пользовательские предикаты, напротив, получают смысл из фактов и правил, записанных в программе. Такое разделение удобно: общие операции, например ввод или сравнение чисел, не нужно заново описывать для каждой задачи.

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

Арифметическая запись сама по себе для Пролога является термом, а не командой вычислить число. Поэтому запись X = 2 + 3 связывает X с выражением 2 + 3, но не превращает его в 5. Предикат is устроен иначе: он вычисляет выражение справа, а полученный результат связывает с переменной слева, например X is 2 + 3.

Предикаты арифметического сравнения проверяют отношения между числами, а не между текстовыми записями. Сначала интерпретатор вычисляет выражения по обе стороны сравнения, затем проверяет условие: например, 3 + 2 > 4 истинно. Все переменные в этих выражениях должны быть связаны заранее, иначе вычислить числовое значение невозможно.

Простейшая программа может считать данные, проверить их и вывести результат. Предикат read получает введённое значение, write выводит текст или значение, а nl переводит вывод на новую строку. Запятая объединяет цели в последовательность: следующая цель выполняется после успешного выполнения предыдущей, поэтому сначала можно считать число, а затем проверить его и сообщить ответ.

Основные встроенные предикаты и операции

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

Разбор задач

Вычислить 7 * 8 и связать результат с R

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

1. Записываем запрос: R is 7 * 8.
2. Интерпретатор вычисляет правую часть: 7 * 8 = 56.
3. Результат связывается с R, поэтому ответ системы — R = 56.

Если написать R = 7 * 8, вычисления не произойдёт: унификация сопоставит R с термом, представляющим произведение. Проверка простая: посмотрите, стоит ли is между переменной и выражением, которое нужно вычислить.

Определить знак введённого числа

Нужно считать X, затем проверить, больше ли оно нуля, меньше ли нуля или равно нулю. Для трёх исходов зададим отдельные правила с числовыми условиями и сообщениями. Запятая задаёт порядок: сначала ввод, затем проверка, после неё вывод результата.

1. Основной предикат можно записать так: знак :- read(X), сообщить(X), nl.
2. Добавляем правило сообщить(X) :- X > 0, write(положительное).
3. Для остальных случаев задаём сообщить(X) :- X < 0, write(отрицательное) и сообщить(X) :- X =:= 0, write(ноль).
4. Запускаем запрос знак. Если введено −4, условие X < 0 выполняется, и программа выводит «отрицательное».

В каждой ветви условие проверяет числовое значение X, поэтому значение должно быть считано до вызова сообщить. Ровно одна из трёх проверок подходит для обычного числа. Предикат nl после сообщения переводит курсор на следующую строку.

Найти сумму чисел от 1 до N

Для суммы удобно уменьшать задачу: сумма от 1 до N равна N плюс сумма от 1 до N − 1. Так появляется рекурсивное правило — правило, которое вызывает тот же предикат для меньшего аргумента. Чтобы процесс закончился, отдельно задаём базу: сумма чисел от 1 до 0 равна 0.

1. Записываем базовый случай: сумма(0, 0).
2. В рекурсивном правиле проверяем N > 0 и вычисляем N1 is N - 1.
3. Находим сумму( N1, S1 ), затем вычисляем S is S1 + N.
4. Для N = 4 получаем цепочку: сумма(4) = 4 + сумма(3), далее 3 + сумма(2), 2 + сумма(1), 1 + сумма(0).
5. Базовый случай даёт 0, поэтому итог равен 1 + 2 + 3 + 4 = 10.

Правило можно записать в виде: сумма(N, S) :- N > 0, N1 is N - 1, сумма(N1, S1), S is S1 + N. Уменьшение N приводит к нулю, где срабатывает база, а затем результаты складываются при возвращении по цепочке вызовов. Ответ для N = 4: 10.

Типичные ошибки

Запись X = 2 + 3 вместо X is 2 + 3 не вычисляет выражение, потому что знак = означает унификацию. Эту ошибку допускают, перенося в Пролог привычный смысл равенства из арифметики. Проверьте себя: если нужен именно результат вычисления, справа ставьте выражение после is и ожидайте числовое значение переменной.

Попытка использовать несвязанную переменную в арифметическом выражении не позволяет интерпретатору вычислить число. Например, X is Y + 1 не сработает, пока Y неизвестна. Сначала считайте или вычислите Y, а затем выполняйте выражение; перед запуском просмотрите порядок целей.

Унификацию и арифметическое сравнение путают из-за похожих знаков и общего впечатления, что оба действия «сравнивают». Но = сопоставляет термы, а, например, > проверяет отношение между вычисленными числами. Для самопроверки спросите себя, нужно ли установить совпадение записей или выяснить, какое число больше.

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

Связь с другими темами

Чтобы разбирать запросы в Прологе, нужно знать факты, правила, переменные и механизм унификации: без них непонятно, как система находит ответы. Арифметические предикаты опираются на знакомые из математики и информатики выражения и отношения сравнения, но требуют явно запускать вычисление. Позже встроенные предикаты помогают строить экспертные системы, решатели задач и программы, использующие рекурсивный поиск. Эти программы применяют заданные правила и перебирают возможные решения.

Что запомнить

• Встроенный предикат уже реализован в языке.
• Запрос к программе проверяется с помощью сопоставления и унификации.
• Предикат is вычисляет выражение справа и связывает результат с переменной слева.
• Арифметические предикаты сравнивают числовые значения, а не просто текстовые записи.
• Предикаты read, write и nl обеспечивают простейший ввод и вывод.
• Рекурсивная программа должна иметь условие остановки.
• Запятая в запросе объединяет цели, которые должны быть выполнены последовательно.