У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

Рассмотрим встроенный предикат get0,который описан в гл. 5. Если Пролог пытается доказать согласованность целевого утверждения get0(X), то он понимает это как указание взять очередную литеру (букву, цифру, пробел или что-либо еще), которая была введена в систему, и попытаться сопоставить целочисленный код этой литеры со значением X. Если они будут сопоставимы, то целевое утверждение считается согласованным, в противном случае оно несогласовано. При этом нет никакого выбора – предикат get0всегда обрабатывает только текущую литеру, введенную в систему в момент обращения к предикату. При следующем обращении к целевому утверждению, включающему get0, он возьмет следующую литеру, но при этом опять не будет никакого выбора. Мы можем определить новый предикат new_getследующим образом:

new_get(X):- repeat, get0(X).

Предикат new_getобладает следующим свойством: он порождает одно за одним значения всех последующих литер (в порядке их поступления) как альтернативные решения. Почему так получается? Когда мы первый раз вызываем new_get(X),то подцель repeatсогласуется и подцель getO(X)тоже, при этом переменная Xконкретизируется очередной литерой. Когда мы инициируем возврат, то выясняется, что последним местом, где имелся выбор, является repeat. Пролог забывает все, что было сделано с того момента, а повторное согласование целевого утверждения repeatуспешно завершается. Теперь он вновь должен обратить свое внимание на getO(X).К этому моменту текущей литерой является следующая литера, и в результате Xполучает в качестве значения вторую литеру.

Мы можем использовать наше определение new_get,чтобы определить другой полезный предикат. Предикат getобычно является встроенным. Когда Пролог обрабатывает целевое утверждение get(X),он рассматривает его как указание читать литеры до тех пор, пока он не найдет очередную неуправляющую литеру, имеющую изображение при печати (пробел, признак конца строки и т. д.). Затем он пытается сопоставить целочисленный код этой литеры со значением X. Мы можем написать приблизительное определение предиката getследующим образом:

get(X):- new_get(X), X › 32.

Чтобы понять это определение, нужно вспомнить, что в кодировке ASCII все неуправляющие (печатаемые) литеры имеют код, превышающий 32, все остальные литеры имеют код, меньший или равный 32. Что происходит при попытке согласовать get(X)?Прежде всего new_get(X)сопоставляет X с текущей литерой, введенной в систему. Если ее код меньше или равен 32, то следующее целевое утверждение неверно и new_getбудет вынужден породить следующую литеру как следующее возможное решение. Эта литера будет затем сравнена с 32 и так далее. В конце концов new_getнайдет неуправляющую литеру, сравнение закончится успешно и код этой литеры будет возвращен в качестве результата get.

Упражнение 6.1.Приведенное определение предиката getне будет работать надлежащим образом, если мы обратимся к целевому утверждению get(X)с уже определенным значением X. Почему это происходит?

Неприятность, связанная с предикатом repeat,состоит в том, что он всегда имеет альтернативное решение. Следовательно, в процессе возврата repeatникогда не будут пересмотрены решения, принятые раньше, чем произошел последний вызов repeat,если только мы не отсечем каким-либо образом эту постоянную возможность выбора. В силу сказанного предыдущие определения должны быть переписаны следующим образом:

new_get(X):- repeat, get0(X).

get(X):- new_get(X), X › 32,!.

Заметим, что это определение по-прежнему работает, лишь если мы пытаемся согласовать get(X)с неконкретизированной значением переменной X. Из-за проблемы, связанной с механизмом возврата за repeat,в каждом применении new_getнеобходимо предусматривать отсечение дальнейших вариантов, как только порождается литера, удовлетворяющая заданным условиям.

В правилах и вопросах вида X:-Yили ?-Yтерм, появляющийся на месте Y, может состоять из единственного целевого утверждения либо представлять конъюнкцию целевых утверждений или их дизъюнкцию. Более того, можно употреблять в качестве целевых утверждений переменныеи успешно доказывать согласованность целевого утверждения, когда целевое утверждение в действительности не согласуется, используя для этого предикат not.Предикаты, представленные в этом разделе, позволяют реализовать эти сложные способы выражения целевых утверждений.

Функтор ',' (запятая) определяет конъюнкцию целевых утверждений. Этот функтор был введен в гл. 1. Если Xи Y– целевые утверждения, то целевое утверждение X, Yсогласуется с базой данных, если согласуется Xи Y. Если Xсогласуется и затем Yне согласуется, то делается попытка найти новое доказательство согласованности для X. Если Xне согласуется, то не согласуется и конъюнкция в целом. Это и составляет суть механизма возврата. Функтор Yявляется встроенным и определен как левоассоциативный инфиксный оператор, так что X, Y, Zэквивалентно (X,Y),Z.

Функтор ';' определяет дизъюнкцию (означающую или) целевых утверждений. Если Xи Y– целевые утверждения, то целевое утверждение X; Yсогласуется с базой данных, если согласуется Xили Y. Если Xне согласуется, то делается попытка доказать согласованность Y. Если и Yне согласуется, то не согласуется и дизъюнкция в целом. Мы можем использовать функтор ';' для того, чтобы выразить альтернативы в пределах одного утверждения. Например, будем считать, что некоторый объект является человеком, если этот объект – либо Адам либо Ева или если у объекта есть мать. Мы можем выразить это в одном правиле следующим образом:

человек(Х):- (Х=адам; Х = ева; мать(Х,Y)).

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

';' (Х = адам, ';'(Х=ева,мать(Х, Y)))

Таким образом, первая возможность соответствует тому, что X– это адам. Вторая возможность включает две альтернативы: Xэто ева или у Xесть мать