Составные термы

Терм распознается как составной на структурном уровне. Существуют предикаты, обеспечивающие доступ к имени функтора, арности и аргументам составного терма. Одним из таких системных предикатов является functor(Term,F,Arity). Этот предикат истинен, если главный функтор терма Term имеет имя F и арность Arity. Пример успешной цели – functor (отец (аран, лот), отец, 2). Предикат functor, как и типовые предикаты, может быть определен таблицей фактов типа functor (f (X,..., X), f, N) для каждого функтора f арности N. Такими фактами будут, например, functor (отец (X, Y), отец, 2), functor (сын (X, Y), сын, 2).... В большинстве версий языка Пролог константы рассматриваются как функторы арности 0, что приводит к соответствующему расширению таблицы.

Использование предиката functor может по разным причинам привести к безуспешным вычислениям. Такая цель, как functor (отец (X, Y), сын, 2), не может быть унифицирована ни с одним фактом таблицы. Кроме того, на типы аргументов целей functor наложены некоторые ограничения. Например, третий аргумент предиката functor, соответствующий арности терма, не может быть атомом или составным термом. Нарушение подобных ограничений приводит к безуспешным вычислениям. Следует различать безуспешные вычисления и вычисления, приводящие к сообщению об ошибке. Сообщение об ошибке может возникнуть из-за бесконечного числа решений, например, при вопросе functor (X, Y, Z)?.

Предикат functor обычно используется одним из двух способов. Первый способ нахождение имени функтора и арности заданного терма. Например, ответом на вопрос functor (отец (аран, лот), X, Y)? будет {X = отец, У= 2}. Второй способ-построение терма с определенным именем функтора и арностью. Такой вопрос, как functor (Т, отец, 2), имеет ответ Т = отец (X, Y).

Парным системным предикатом к предикату functor является предикат arg(N, Term, Arg), обеспечивающий доступ не к имени функтора, а к аргументам. Цель arg (N, Term, Arg) истинна, если Arg N-й аргумент терма Term. Пример истинной цели - arg (1, отец (аран, лот), аран).

Как и functor/3, предикат arg/3 обычно используется одним из двух способов. Первый способ-нахождение определенного аргумента составного терма. Вопрос, поясняющий подобное использование, arg (2, отец (аран, лот), X)?. Ответом на вопрос будет Х = лот. При втором способе использования происходит конкретиза­ция переменного аргумента терма. Например, при успешном решении вопроса arg (1, отец (X, лот), аран?) устанавливается соответствие Х = аран.

Можно, как и раньше, считать, что предикат arg определен так, будто существует бесконечная таблица фактов. Пример фрагмента такой таблицы:

arg (1, отец (X, Y), X). arg (2, отец (X, Y), Y). arg (1, сын (X, Y), X,...).

Вычисления, использующие предикат arg, безуспешны, если цель не может быть унифицирована с соответствующим фактом таблицы. Пример такой цели – arg (1, отец (аран, лот), авраам). Безуспешные вычисления возникают и в случае нарушения типовых ограничений, например если первый аргумент-атом. Цели вида arg (1, X, Y) приводят к сообщениям об ошибке.

Рассмотрим пример использования предикатов functor и arg при анализе термов. Программа 9.2 задает отношение subterm (T1, T2), истинное, если Т1-подтерм терма Т2. По причинам, изложенным ниже, ограничимся случаем, когда Т1 и Т2 – основные термы.

Первое предложение программы 9.2, определяющее отношение subterm, утверждает, что любой терм является собственным подтермом. Второе предложение утверждает, что Sub является подтермом составного терма Term, если Sub – подтерм одного из аргументов терма Term. Определяется число аргументов т. е. арность главного функтора терма. Это число используется в качестве счетчика цикла во вспомогательном предикате subterm/3, итерационно проверяющем все аргументы.

Первое предложение процедуры subterm/3 уменьшает значение счетчика и рекурсивно обращается к процедуре subterm. Второе предложение процедуры paccмат ривает случай, когда Sub является подтермом N-го аргумента терма.

sub term (Sub, Term) ¬

Sub- подтерм основного терма Term.

subterm(Term, Term).

subterm (Sub, Term)¬-

compound (Term), functor(Term,F,N), subterm (N, Sub, Term).

subterm (N, Sub, Term)¬

N>1, N1:= N-l, subterm(Nl,Sub, Term).

subterm (N, Sub, Term) ¬

arg(N, Term, Arg), subterm (Sub, Arg).

Программа 9.2 Нахождение подтермов терма.

Процедура subterm может быть использована двумя способами: для проверки того, что первый аргумент является подтермом второго, и для порождения подтермов заданного терма. Заметим, что порядок предложений определяет порядок порождения подтермов. Порядок предложений программы 9.2 приводит к тому, что сначала порождаются подтермы первого аргумента, потом – второго и т. д. Изменение порядка предложений приводит к изменению порядка появления решений.

Рассмотрим вопрос subterm (a,f(X, Y))?, в котором второй аргумент – неосновной. В процессе решения в некоторый момент возникает цель subterm (a, X). Применение первого правила приведет к решению Х = а. Эта же цель будет редуцироваться с помощью второго правила, редукция построит цель compound (X), решение которой приведет к ошибке. Это, конечно, нежелательный эффект.

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

Программа 9.2 – типичная программа, использующая анализ структуры. Рассмотрим еще один пример: подстановку подтерма в терм.

Реляционная схема общей программы подстановки подтерма в терм – substitute (ОId, New, ОIdTerm, NewTerm), где NewTerm – терм, полученный заменой всех вхождений подтерма Old в терме OldTerm на подтерм New. Отношение, задаваемое программой, обобщает отношение подстановки элемента в список [см. упражнение 3.3(1)] и отношение подстановки элемента в бинарное дерево (логическая программа 3.26).

Программа 9.3 немного сложнее программы 9.2, но следует тойже основной схеме. Предложения процедуры substitute/4 анализируют три основных случая. В последнем, относящемся к составным термам, происходит обращение к вспомогательному предикату substitute/5, который реализует итерационную подстановку в подтермы. Арность главного функтора терма является начальным значением счетчика цикла, это значение последовательно уменьшается и используется для управления итерациями. Приведем конкретный пример, проясняющий интересные детали, скрытые в тексте программы. Протокол решения вопроса substitute (cat, dog, owns (jane, cat), X)? приведен на рис. 9.2.

Унификация вопроса с фактом программы 9.3 безуспешна. Терм owns (jane, cat) не является константой, поэтому второе правило тоже неприменимо.

Применимо третье правило substitute. Рассмотрим второе обращение к предикату functor. Переменным Name и Arity уже сопоставлены значения owns и 2 в предыдущем обращении к этому предикату, поэтому в рассматриваемом обращении

substitute (Old, New, OldTerm, NewTerm) ¬

NewTerm получается из терма OldTerm заменой всех вхождений подтерма Old на подтерм New.

substitute (Old, New, Old, New).

substitute (Old, New, Term, Term)¬

constant (Term), Term¹Old.

substitute (Old, New, Term, Term)¬

compound (Term),

functor (Term,F, N),

functor (Term 1, F, N),

substitute (N, Old, New, Term, Term 1).

substitute(N,Old, New, Term, Tennl) ¬

N>0,

arg(N, Term, Arg),

substitute (Old, New, Arg, Arg 1),

arg(N,Terml,Argl),

N1:=N - 1,

substitute (N1,0ld,New, Term, Term 1).

substitute (0, Old, New, Term, Term 1).

Программа 9.3. Программа подстановки термов.

substitute(cat,dog,owns(jane,cat),X) {X=owns(jane,cat)}

constant(owns(jane,cat)) f

substitute(cat,dog,owns(jane,cat),X)

compound(owns(jane,cat)),

functor(owns(jane,cat),F,N) {F=owns,N=2}

functor(X,owns,2) {X=owns(X1,X2)}

substitute (2,cat,dog,owna(jane,c at),owns (XI,X2))

2 >0

arg(2,owns(jane,cat),Arg) {Arg=cat}

substitute(cat,dog,cat,Argl) {Argl=dog}

arg(2,owns(Xl,X2),dog) {X2=dog}

Nl:= 2-1 {N1=1}

substitute(l,cat,dog,owns(jane,cat),owDs(Xl,dog))

1 > 0

arg(l,owns(jane,cat),Arg2) {Arg2=jane}

substitute(cat,dogJ ane,Arg3) {Arg3=jane}

constant (jane)

jane¹cat

arg(l,owns(Xl,dog),jane) {Xl=jane}

N2 := 1-1 {N2=0}

substitute(0,cat,dog,owns(jane,cat),owns(jane,dog))

0 >0 f

substitute(0,cat,dog,owns(jane”cat),owns (jane,dog))

true

Результат: Х = owns(jane,dog)

Рис. 9.2. Протокол предиката подстановки.

Cтроится терм, служащий шаблоном ответа, который заполняется в процессе вычисления. Это явное построение терма успешно выполнялось с помощью неявной унификации в предыдущих программах на Прологе. Обращение к цели substitute/5 приводит к успешному сопоставлению значений аргументам терма Term 1, В нашем примере второму аргументу сопоставляется значение dog, а аргументу XI сопоставляется значение jane.

Два обращения к процедуре arg в процедуре substitute/5 используются по-разному. Первое обращение выделяет аргумент, второе – сопоставляет аргументу значение.

В обычных языках подстановка в терм производится с помощью деструктивного присваивания, что в Прологе исключено. Программа 9.3 является типичным примером управления изменением структуры данных в Прологе. Новый терм строится рекурсивно по мере анализа исходного терма с помощью логических взаимосвязей между подтермами термов.

Заметим, что вторую цель arg и рекурсивное обращение к suhstitute/5 можно поменять местами. Измененное предложение процедуры substitute/5 логически эквивалентно исходному и в процессе работы программы 9.3 приводит к тому же результату. Однако процедурно эти два варианта совершенно различны.

Другой системный предикат, применяемый при анализе структур, бинарный оператор =.., имеющий в силу исторических причин название univ. Цель Term =..List выполнена, если голова списка List совпадает с именем функтора терма Term, а хвост является списком аргументов этого терма. Например, цель (отец (аран, лот) =.. [отец, аран, лот]) выполнена.

Подобно отношениям functor и arg отношение univ используется двояко - или для построения терма по заданному списку (например, вопрос (X =..[ отец аран, лот])? имеет решение Х = отец (аран, лот)), или для построения списка по заданному терму (например, вопрос (отец (аран, лот) =. .Xs)? имеет решение Xs = [отец, аран, лот]).

Программы, использующие предикаты functor и arg, в общем случае могут быть преобразованы в программы с отношением univ. Программа 9.4, дающая иное определение отношения subterm, эквивалентна программе 9.2. Как и в программе 9.2, здесь используется вспомогательный предикат, анализирующий аргументы, в дан­ном случае subterm_list. Предикат univ обеспечивает доступ к списку аргументов Args, подтермы которого находятся с помощью рекурсивного обращения к процедуре subterm_list.

sub term (Sub, Term) ¬

Sub подтерм основного терма Term

subterm(Term,Term).

subterm(Sub,Term)¬

compound (Term),

Term =.. [F | Args],

subterm._list(Sub,Args).

sublerm_lisl(Sub,[Arg | Args]) ¬

subterm(Sub, Arg).

subterm_1ist(SiibTArg | Args])¬

subterm list (Sub, Args).

Программа 9.4 Определение подтерма с помощью =..

Программы для анализа структур, использующие предикат univ, обычно оказываются проще. Однако использование предикатов functor и arg приводит в общем случае к более эффективнымпрограммам за счет отсутствия вспомогательных структур.

Использование предиката univ позволяет изящно задать правило дифференцирования сложных функций. Правило утверждает, что d/dx{f(g(x))} = d/dg(x){f(g(x))} * d/dx{g(x)}. В разд. 3.5 мы заметили, что данное правило нельзя выразить с помощью одного предложения, являющегося частью логической программы 3.29. В Прологе правило дифференцирования сложной функции можно задать следующим образом:

derivative (F_G_X, X, OF * DG)¬

F_G_X =..[F,G_X],

derivative (F_G_X, G_X, DF),

derivative (G_X,X,DG).

Предикат univ расщепляет функцию F_G_X на функтор F и аргументG_X, при этом одновременно проверяется, является ли она функцией одного аргумента. Рекурсивно вычисляются производная функции F от своего аргумента и производная функции G_X. Объединение этих вычислений приводит к решению.

Предикат univ может быть определен в терминах предикатов functor и arg. Однако для того, чтобы строить списки по термам и термы по спискам, нужны два различных определения. Одного определения недостаточно из-за ошибочных ситуаций, возникающих при использовании неопределенных переменных. Другие системные предикаты не допускают разнообразных использовании по тем же причинам.

Программа 9.5 а правильно строит список по терму. Обращение к предикату functor строит функтор F, а аргументы находятся рекурсивно с помощью предиката arqs. Первый аргумент предиката args – счетчик, значение которого возрастает по мере вычислений, так что аргументы будут входить в результирующий список в нужном порядке. Если значение переменной Term в программе 9.5 а не определено, то обращение к предикату functor приведет к сообщению об ошибке.

Term =.. List ¬

List - список, состоящий из функтора терма Term, за которым следуют аргументы

терма Term.

Term =..[F | Args] ¬

functor (Term,F,N),args(0,N,Term,Args).

args (I, N, Term, [Argi Args])¬

I<N,I1:= I+l, arg(Il, Term, Arg),args(Il,N, Term, Args).

args(N, N, Term, [ ]).

Программа 9.5а. Построение списка, соответствующего терму.

Term =.. List ¬

функтор терма Term является первым элементом списка List. остальные элементы списка – аргументы терма.

Term =..[F | Args] ¬

length(Args, N),functor(Term, F, N), args(Args, Term, l).

args([Arg | Args],Term, N)¬

arg(N,Term,Arg), Nl:= N+1, args(Args,Term,Nl).

args[ ],Term,N).

length(Xs,N) ¬-См. программу 8.11.

Программа 9.5б Построение терма, соответствующего списку.

Программа 9.5 б правильно строит терм по списку. Длина списка используется для определения числа аргументов. Обращение к предикату functor создает шаблон терма, а для заполнения аргументов шаблона используется другой вариант программы args. Если попытаться с помощью программы 9.5б строить список, то при решении цели length(Args.N) с неопределенными аргументами возникнет ошибочная ситуация.

Дата добавления: 2014-01-07