Так как аргумент Xсопоставляется с удаляемым утверждением, то имеется возможность получить точное представление об удаляемом утверждении, даже если Xисходно означал некоторую структуру, содержащую множество неконкретизированных переменных. Это позволяет использовать предикат retractвместо предиката clause, в ситуации когда найденное утверждение сразу же удаляется. Такая ситуация как раз имеет место в определении предиката генатом (разд. 7.8).
6.5. Создание структур и работа с компонентами структур
Обычно когда мы хотим задать в программе на Прологе операции со структурой определенного вида, то мы делаем это, «упоминая» некоторым образом подобную структуру. Это значит, что если предикат используется для обработки множества структур различного вида, передаваемых ему в качестве аргумента, то обычно мы обеспечиваем отдельное утверждение для каждого класса структур. Хорошим примером такого подхода является программа для символьного дифференцирования, которая будет рассмотрена в разд. 7.1. В этой программе используются отдельные утверждения для функторов +, -, * и так далее. Мы знаем заранее, какие структуры могут появиться, и обеспечиваем утверждения для каждой из них.
В некоторых программах мы не можем предвидеть заранее все возможные структуры. Это имеет место, например, при написании программы «красивой печати», которая могла бы печатать произвольные структуры языка Пролог, размещая их в нескольких строках и используя отступы. (См. разд. 5.1, где представлена такая программа для печати списков.) Так, например, возможно, мы захотели бы напечатать терм
книга(629,автор(бронте, эмили),вх)
следующим образом:
книга
629
автор
бронте
эмили
вх
Важным моментом является то, что мы хотим, чтобы эта программа работала правильно, какую бы структуру мы ей ни задали. Понятно, что одна из возможностей сделать это – обеспечить отдельное утверждение для каждого функтора, какой только можно представить. Но это работа, которую мы никогда не завершим, потому что существует бесконечно много различных функторов! Написать подобную программу можно, используя встроенные предикаты для работы со структурами произвольного вида. Здесь мы опишем некоторые из них – это предикаты functor, argи ' =..'. Мы опишем также предикат name, выполняющий операции над атомами.
Предикат functorопределен таким образом, что functor(T,F,N)означает, что Т– это структура с функтором F, имеющим N аргументов.Этот предикат можно использовать двумя основными способами, В первом случае аргумент Туже имеет значение. Целевое утверждение считается несогласованным с базой данных, если Тне является ни атомом, ни структурой. Если Т– это атом или структура, то Fсопоставляется с функтором этой структуры, а Nприсваивается значение, равное числу аргументов функтора. Заметим, что в данном контексте считается, что атом – это структура с числом аргументов 0. Ниже приведено несколько примеров целевых утверждений с предикатом functor:
?- functor(f(a,b,g(Z)),F,N).
Z = _23, F = f ,N =3
?- functor(a+b,F,N).
F = +, N = 2
?- functor([a,b,c],F,N).
F =., N = 2
?- functor(apple,F,N).
F = apple, N = 0
?- functor([a,b,c],'.',3).
нет
?- functor([a,b,c],a,Z).
нет
Прежде чем перейти к обсуждению предиката arg,следует рассмотреть второй способ использования предиката functor.В этом случае первый аргумент целевого утверждения functor (Т, F, N)неконкретизирован. В этом случае два других аргумента должны быть конкретизированы, однозначно определяя функтор и число аргументов соответственно. Целевое утверждение такого вида всегда согласуется с базой данных, и в результате значением Тстановится структура с указанными функтором и числом аргументов. Таким образом, это некоторый способ созданияпроизвольных структур по заданным функтору структуры и числу ее аргументов. Аргументами такой структуры, созданной с помощью предиката functor,являются неконкретизированные переменные. Следовательно, эта структура будет сопоставима с любой другой структурой, имеющей тот же функтор и одинаковое число аргументов.
Предикат functorиспользуется для создания структуры в основном тогда, когда нам надо получить «копию» некоторой уже существующей структуры с новыми переменными в качестве аргументов. Мы можем ввести для этого предикат копирование,использующий functorкак целевое утверждение:
копирование(Старая, Новая):- functor(Cтapaя,F,N), functor(Hoвaя,F,N).
В этом определении подряд используются два целевых утверждения functor.Если целевое утверждение копированиеимеет конкретизированный первый аргумент и неконкретизированный второй, то произойдет следующее. Первое целевое утверждение functorбудет соответствовать первому способу использования этого предиката (так как первый аргумент этого предиката конкретизирован). Следовательно, Fи Nконкретизируются, получив в качестве значений функтор и число аргументов этой существующей структуры. Второе целевое утверждение functorсоответствует второму способу использования этого предиката. На этот раз первый аргумент неконкретизирован, и информация, задаваемая Fи N, используется для создания структуры Новая.Эта структура имеет те же функтор и число аргументов, что и Старая, но ее компонентами являются переменные. Таким образом, возможен следующий диалог:
?- копирование(sentence(np(n(john)), v(eats)),X).
X = sentence(_23,_24)
Мы используем подобную комбинацию целевых утверждений functorв определении предиката reconsultв разд. 7.13.
Предикат argвсегда должен использоваться с конкретизированными первым и вторым аргументами. Он применяется для доступа к конкретному аргументу структуры. Первый аргумент предиката argопределяет, какой аргумент структуры необходим. Второй аргумент определяет структуру, к аргументу которой необходим доступ. Пролог находит соответствующий аргумент и затем пытается сопоставить его с третьим аргументом предиката arg.Таким образом, цель arg(N,T,A)согласуется с базой данных, если N-й аргумент Тесть А. Давайте рассмотрим несколько целевых утверждений с arg.
?- аrg(2,отношение(джон,мать(джейн)),Х).
X = мать(джейн)
?- arg(1,a+(b+c),X).
X =а
?- arg(2,[a,b,c],X).
X = [b,c]
?-arg(l,a+(b+c),b).
нет
Иногда мы захотим использовать предикаты functorи argв ситуации, когда возможные структуры уже известны. Это связано с тем, что структура может иметь так много аргументов, что просто неудобно каждый раз перечислять их все. Рассмотрим пример, в котором структуры используются для описания книг. Мы могли бы иметь отдельную компоненту для названия книги, ее автора, издательства, года издания и так далее. Будем считать, что результирующая структура имеет четырнадцать компонент. Мы могли бы написать следующие полезные определения:
является _ книгой(книга(_,_,_,_,_,_,_,_,_,_,_,_,_,_)).
название(книга(Т,_,_,_,_,_,_,_,_,_,_,_,_,_),Т).
автор(книга(_,А,_,_,_,_,_,_,_,_,_,_,_,_),А).
. . .
В действительности мы можем записать это значительно более компактно следующим образом:
является_книгой(Х):- functor(X, книга, 14).
название(Х,Т):- является_книгой(Х), arg(1,X,T).
автор(Х,А):- является_книгой(Х), arg(2,X,T).
. . .
Предикаты functorи argдают один из способов создания произвольных структур и доступа к их аргументам. Предикат «=..» предоставляет альтернативный способ, полезный в том случае, когда необходимо одновременно получить все аргументы структуры или создать структуру по заданному списку ее аргументов. Целевое утверждение X=..Lозначает, что L есть список, состоящий из функтора структуры X, за которым следуют аргументы X. Такое целевое утверждение может быть использовано двумя способами, так же как и целевое утверждение functor.Если Xуже имеет значение, то Пролог создает соответствующий список и пытается сопоставить его с L. Напротив, если Xнеконкретизировано, то список будет использован для формирования соответствующей структуры, которая станет значением X. В этом случае голова списка должна быть атомом (этот атом станет функтором X). Ниже приведено несколько примеров целевых утверждений, содержащих =..:
?- имя(а,b,с) =.. X.
X = [имя,а,b,с]
?- присоединить([А|В],С, [A|D]) =..L.
A = _2, В = _3, С = _4, D = _5, L = [присоединить,[_2|_3],_4,[_2|_5]]
?- [a,b,c,d] =..L.
L = ['.',a,[b,c,d]].
?- (a+b) =.. L.
L = [+,a,b].
?- (a+b) =..
[+,A,B] A = а, В = b
?- [a,b,c,d] =..
[A|B] A = '.', В = [a,[b,c,d]]
?- X =.. [a,b,c,d]
X = a(b,c,d).
?- X =.. [присоединить,[a,b,],[c],[a,b,c]].
X = присоединить([а,b],[с],[а,b,с])
Примеры использования предиката =.. приведены в разд. 7.12.
В то время как предикаты functor, argи =..используются для формирования произвольных структур и доступа к их аргументам, предикат nameиспользуется для работы с произвольными атомами. Предикат nameсопоставляет атому список литер (их ASCII кодов), из которых состоит этот атом. Данный предикат можно использовать как для определения литер, составляющих указанный атом, так и для определения атома, содержащего заданные литеры. Целевое утверждение name(A, L)означает, что литеры, образующие атом А, являются элементами списка L. Если аргументу А уже присвоено значение, то Пролог создает список литер и пытается сопоставить его с L. В противном случае Пролог использует список Lдля создания атома, который станет значением А. Приведем примеры использования предиката name:
?- name(apple,X).
X = [97,112,112,108,100]
?- name(X,[97,l12,112,108,100]).
X = apple
?- name(apple,"apple").
да
?- name(apple,"pear").
нет
В разд. 9.5 предикат nameиспользуется для доступа к внутренней структуре слов английского языка, представляемых атомами Пролога.
6.6. Воздействие на процесс возврата
В Прологе есть два встроенных предиката, изменяющих нормальную последовательность событий, происходящих в процессе возврата. Предикат « !» устраняет возможности для повторного согласования целевых утверждений, а предикат repeatсоздает новые альтернативы там, где их не было ранее.
Символ отсечения ('!') можно рассматривать как встроенный предикат, который лишает Пролог-систему возможности изменить некоторые из решений, принятых ею ранее. Более подробное описание отсечения смотрите в гл. 4.
Встроенный предикат 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, где показано, как необдуманное использование ';' затрудняет понимание программ.
Предполагается, что 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,за тем исключением, что согласованность или несогласованность аргумента, рассматриваемого как целевое утверждение, приводит к противоположному результату.
Чем отличаются следующие два вопроса?
/* 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. Равенство