У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ Страница 35

Мы можем использовать наше определение 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 необходимо предусматривать отсечение дальнейших вариантов, как только порождается литера, удовлетворяющая заданным условиям.

6.7. Формирование составных целевых утверждений

В правилах и вопросах вида 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 есть мать

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

человек(адам).

человек(ева).

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

Этот вариант более традиционен и, возможно, проще для чтения. Для многих Пролог-систем он может быть более эффективным по сравнению с использованием ';'.

Результатом отсечения является невозможность изменить выбор альтернатив, обусловленных наличием дизъюнкций, сделанный с момента сопоставления с правилом, содержащим отсечение (см. гл. 4). Вследствие этого имеется ряд случаев, когда программа, содержащая отсечения, не может быть преобразована в обычную программу без использования дизъюнкций. Однако в общем случае не рекомендуется чрезмерно часто использовать ';'. В качестве предостережения отсылаем вас к гл. 8, где показано, как необдуманное использование ';' затрудняет понимание программ.

Предполагается, что X конкретизирован термом, который может быть интерпретирован как целевое утверждение. Целевое утверждение саll(X) считается согласованным, если попытка доказать согласованность X завершается успехом. Целевое утверждение call(X) не согласуется с базой данных, если попытка доказать согласованность X заканчивается неудачей. На первый взгляд этот предикат может показаться излишним, поскольку, естественно, возникает вопрос: почему аргумент call не может быть записан непосредственно как целевое утверждение? Например, целевое утверждение

…, саll(принадлежит(а,Х)),…

всегда может быть заменено следующим:

…, принадлежит(a,X),…

Однако если мы создаем целевые утверждения, используя предикат '=..' или ему подобные, то возможны обращения к целевым утверждениям, функторы которых неизвестны на момент ввода программы в Пролог-систему. Так, например, в определении предиката consult в разд. 7.13 нам надо иметь возможность рассматривать любой терм, прочитанный после ?-, как целевое утверждение. Предполагая, что Р, Х и Y конкретизированы функтором и аргументами соответственно, можно использовать call следующим образом:

…, Z =… [P,X,Y], call(Z),…

Последний фрагмент программы можно рассматривать как способ выражения обращения к целевому утверждению следующего вида:

…, P(X,Y),…

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

Предполагается, что X конкретизирован термом, который может быть интерпретирован как целевое утверждение. Целевое утверждение not(X) считается согласованным с базой данных, если попытка доказать согласованность X заканчивается неудачей. Целевое утверждение not(X) считается несогласованным, если попытка доказать согласованность X успешно завершается. В этом плане предикат not очень похож на call, за тем исключением, что согласованность или несогласованность аргумента, рассматриваемого как целевое утверждение, приводит к противоположному результату.