Язык PROLOG
Фразы Хорна (Horn clause) представляют собой подмножество фраз, содержащих только один позитивный литерал. В общем виде фраза Хорна представляется выражением.
В языке PROLOG эта же фраза записывается в таком виде (обратите внимание на символ точки в конце): р: -q1,…,qn. Такая фраза интерпретируется следующим образом:
"Для всех значений переменных в фразе p истинно, если истинны q1 и… и qn", т.е. пара символов ":-" читается как "если", а запятые читаются как "и".
PROLOG – это не совсем обычный язык программирования, в котором программа состоит в основном из логических формул, а процесс выполнения программы представляет собой доказательство теоремы определенного вида.
Фраза в форме: р: -q1,…,qn. может рассматриваться в качестве процедуры. Такая процедура предполагает следующий порядок выполнения операций.
- (1) Литерал цели сопоставляется с литералом р (унифицируется с р), который называется головой фразы.
- (2) Хвост фразы ql,…,qn конкретизируется подстановкой значений переменных (или унификаторов), сформированных в результате этого сопоставления.
- (3) Конкретизированные термы хвостовой части образуют затем множество подцелей, которые могут быть использованы другими процедурами.
Таким образом, сопоставление (или унификация) играет ту же роль, что и передача параметров функции в других, более привычных языках программирования.
Например, рассмотрим набор фраз языка PROLOG, представленных в листинге 8.1. Предположим, что a, b и с – какие-то блоки в мире блоков. Две первые фразы утверждают, что а находится на (on) b, a b находится на (on) с. Третья фраза утверждает, что X находится выше (above) Y, если X находится на (on) Y. Четвертая фраза утверждает, что X находится выше (above) Y, если существует какой-то другой блок Z, размещенный на (on) Y, и X находится выше (above) Y.
Листинг 8.1. Простая программа на языке PROLOG, определяющая отношение on (на).
on(а, b). on(b, с). above(X, Y): – on(X, Y). above(X, Y): – on(Z, Y), above(X, Z).
Очевидно, что от программы требуется вывести цель above (а, с) из этого множества фраз. Как это делается, мы увидим в разделе 8.3.2, но уже сейчас можно сказать, что процесс формулировки выражения цели включает обработку двух процедур above и использование двух фраз on.