Текст книги "Программирование на языке пролог"

Автор книги: У. Клоксин

Соавторы: К. Меллиш
сообщить о нарушении

Текущая страница: 12 (всего у книги 26 страниц)

6.6. Воздействие на процесс возврата

В Прологе есть два встроенных предиката, изменяющих нормальную последовательность событий, происходящих в процессе возврата. Предикат « !» устраняет возможности для повторного согласования целевых утверждений, а предикат repeatсоздает новые альтернативы там, где их не было ранее.

Отсечение

Символ отсечения ('!') можно рассматривать как встроенный предикат, который лишает Пролог-систему возможности изменить некоторые из решений, принятых ею ранее. Более подробное описание отсечения смотрите в гл. 4.

repeat

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

repeat.

repeat:– repeat.

Что произойдет, если мы поместим предикат repeatкак целевое утверждение в одно из наших правил?

Во-первых, это целевое утверждение согласуется с базой данных, так как имеется соответствующий факт – первое утверждение определения предиката repeat.Во-вторых, если в процессе возврата вновь будет достигнуто это место, то Пролог будет иметь возможность испробовать альтернативу – правило (второе утверждение). При использовании правила порождается другое целевое утверждение repeat.Так как оно сопоставляется с фактом для предиката repeat,то это целевое утверждение вновь согласуется с базой данных. Если процесс возврата снова дойдет до этого места, то Пролог вновь использует правило там, где он ранее использовал факт. Чтобы доказать согласованность вновь порожденного целевого утверждения, он снова выберет факт. И так далее. В действительности в процессе возврата целевое утверждение repeatможет быть согласовано бесконечное число раз. Обратим внимание на существенность порядка, в котором записаны утверждения для предиката repeat.(Что произойдет, если факт будет записан после правила?)

Для чего нужно порождать целевые утверждения, которые всегда будут согласовываться в процессе возврата? Они нужны для того, чтобы создавать правила, в которых имеется возможность выбора вариантов, из правил, которые такой возможности не содержат. И тем самым мы можем заставить их порождать каждый раз различные значения.

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

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, где показано, как необдуманное использование ';' затрудняет понимание программ.

call(X)

Предполагается, что 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),…

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

not(X)

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

Чем отличаются следующие два вопроса?

/* 1 */?– принадлежит(Х,[а,b,с]), write(X).

/* 2 */?– not(not(принадлежит(Х,[а,b,с]))), write(X).

Может показаться, что между ними нет никакой разницы, так как в запросе 2 принадлежит(Х,[а,b,с,])согласуется, поэтому not(принадлежит(Х,[а,b,с,]))не согласуется и not(not(принадлежит(Х,[а,b,с])))согласуется. Это правильно лишь отчасти. В результате первого вопроса будет напечатан атом ' а', а в результате второго – неконкретизированная переменная.Рассмотрим, что происходит при попытке доказать согласованность первого целевого утверждения из второго вопроса:

1. Целевое утверждение принадлежитсогласуется, и Xконкретизируется значением а.

2 Предпринимается попытка доказать согласованность первого целевого утверждения not,которая заканчивается неудачей, так как целевое утверждение принадлежит,являющееся его аргументом, согласуется с базой данных. Теперь вспомним, что, когда целевое утверждение не согласуется, все конкретизированные переменные, такие как Xв нашем примере, должны теперь «забыть», что они обозначали до сих пор. Следовательно, Xстановится неконкретизированной.

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

4. Предпринимается попытка выполнить целевое утверждение writeс неконкретизированным значением X. И, как описано в разд. 6.9, неконкретизированные переменные печатаются специальным образом.

6.8. Равенство

В этом разделе коротко рассматриваются различные встроенные предикаты, используемые для проверки равенства элементов и позволяющие делать их равными.

X=Y

Когда Пролог встречает целевое утверждение X=Y, то он пытается сделать Xи Yравными, сопоставляя их друг с другом. Если сопоставление возможно, то целевое утверждение считается согласованным (а Xи Y, возможно, становятся более конкретизированными). В противном случае целевое утверждение считается несогласованным. Более полное обсуждение этого предиката приведено в разд. 2.4. Предикат равноопределен таким образом, как если бы имел место факт

X = X.

Убедитесь, что вы понимаете, как это определение работает.

X=Y

Предикат ' =' является противоположным по отношению к предикату ' =' с точки зрения согласованности с базой данных. Это значит, что X=Yсогласовано, если X=Yне согласовано, и наоборот. Если целевое утверждение X = Yсогласовано ( Xи Yне могут быть сопоставлены друг с другом), то не произойдет никаких изменений в конкретизации Xи Y. Если бы ' =' не был встроенным предикатом, то мы могли бы определить его на Прологе следующим образом:

X = Y:– X = Y,!, fail .X = Y.

X==Y

Предикат '==' выполняет значительно более строгую проверку на равенство, чем предикат '='. Это значит, что если X==Yвыполняется, то и тем более выполняется X=Y. А обратное заключение не всегда имеет место. Отличие '==' состоит в том, что он более строг к переменным. Предикат '=' предполагает, что не-конкретизированная переменная может быть равна чему угодно, так как она сопоставима с чем угодно. С другой стороны, предикат '==' предполагает, что неконкретизированная переменная может быть равна другой неконкретизированной переменной, лишь когда они уже сцеплены друг с другом. Иначе проверка на равенство заканчивается неудачей. Таким образом, возможен следующий диалог:

?– X==Y.

нет

?– X==X.

X=_23

?– X = Y, X == Y. X = _23, Y = _23

?– присоединить([А|В],С) == присоединить(Х,Y).

нет

?– присоединить ([А|В],С) == присоединить([А|В],С).

А = _23, В = _24, С = _25

Х == Y

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

Х== Y:– X == Y,!, fail.

Х== Y.

6.9. Ввод и вывод данных

Предикаты для ввода и вывода литер и термов обсуждались в гл. 5. Здесь мы резюмируем наши знания о каждом из этих предикатов.

get0(X)

Это целевое утверждение согласуется с базой данных, если Xможет быть сопоставлена с очередной литерой в текущем входном потоке данных. Цель get0выполняется лишь один раз (его нельзя согласовать повторно). Операция перехода к очередной литере не переделывается при возврате, так как не существует способа поместить литеру обратно в текущий входной поток данных.

get(X)

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

skip(X)

Этот предикат читает и пропускает литеры в текущем входном потоке данных до тех пор, пока не встретится литера, сопоставимая с X. Предикат skipвыполняется только один раз.

read(X)

Этот предикат читает очередной терм из текущего входного потока данных и сопоставляет его с X. Предикат readвыполняется только один раз. Вводимый терм должен заканчиваться точкой '.' которая не становится частью этого терма. После точки должна следовать по крайней мере одна управляющая литера. Точка удаляется из текущего входного потока данных.

put(X)

Этот предикат записывает целое число Xв виде литеры (кодом которой и является X) в текущий выходной поток данных. Предикат putвыполняется только один раз. Если Xнеконкретизирован, то фиксируется ошибка.

nl

Записывает в текущий выходной поток данных последовательность управляющих литер, вызывающую переход на «новую строку». В случае вывода на дисплей все литеры, выводимые после nl, будут размещены на следующей строке страницы; nlвыполняется только один раз.

tab(X)

Записывает X«пробелов» в текущий выходной поток данных. Если Xнеконкретизирован, то фиксируется ошибка, tabвыполняется только один раз.

write(X)

Этот предикат записывает терм Xв текущий выходной поток данных, writeвыполняется только один раз. Каждая неконкретизированная переменная, входящая в X, записывается как уникальное имя, начинающееся с подчеркивания ('_'), за которым следует уникальное число, как, например, '_239'. Переменные, сцепленные в пределах одного аргумента предиката write,при печати будут иметь одинаковые имена. Предикат writeучитывает при печати термов имеющиеся объявления операторов. Так, например, инфиксный оператор будет напечатан между своими аргументами.

display(X)

Предикат displayработает в точности таким же способом, что и write,за тем исключением, что он игнорирует все объявления операторов. Предикат displayпечатает любую структуру, начиная с ее функтора, за которым в круглых скобках печатается список аргументов.

op(X,Y,Z)

Этот предикат объявляет оператор, имеющий приоритет X, позицию и ассоциативность Yи имя Z. Спецификация позиции и ассоциативности выбирается из числа следующих атомов:

fx fy xf yf xfx xfy yfx yfy

Если объявление оператора корректно, то opсчитается согласованным. Более подробно этот предикат описан в разд. 5.5.

6.10. Обработка файлов

Предикаты для изменения текущего входного и текущего выходного потоков данных были введены в гл. 5. Здесь мы резюмируем наши знания о каждом из этих предикатов.

see(X)

Этот предикат открывает файл X, если он еще не открыт, и определяет, что текущим входным потоком данных становится файл X. Если Xнеконкретизирована или Xконкретизирована именем несуществующего файла, то фиксируется ошибка.

seeing(X)

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

seen

Этот предикат закрывает текущий входной поток данных (файл) и определяет, что текущим входным потоком данных становится клавиатура терминала (user).

tell(X)

Этот предикат открывает файл X, если он еще не открыт, и определяет, что текущим выходным потоком данных, в который производится запись, является указанный файл. Если Xнеконкретизирована, то возникает ошибка. Если tellиспользуется для. переключения выходного потока на еще неоткрытый файл и файл с именем, определяемым Xне существует, то файл с таким именем создается. Иначе, если файл, определяемый X, уже существует, то предшествующее содержимое файла уничтожается.

telling (X)

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

told

Этот предикат закрывает текущий выходной поток данных (файл) и записывает маркер конца файла в соответствующий файл. Текущим выходным потоком данных становится дисплей терминала ( user).