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

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

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

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

7.10. Просеивай Двойки, Просеивай Тройки

 
Просеивай Двойки,
Просеивай Тройки,
Эратосфена Решето,
Пусть все кратные им отсеем,
Простые числа получим зато.
 

Аноним

Простое число – это целое положительное число, которое делится нацело только на 1 и на само себя. Например, число 5 – простое, а число 15 – нет, поскольку оно делится на 3. Один из методов построения простых чисел называется «решетом Эратосфена». Этот метод, «отсеивающий» простые числа, не превышающие N, работает следующим образом:

1. Поместить все числа от 2 до N в решето.

2. Выбрать и удалить из решета наименьшее число.

3. Включить это число в список простых.

4. Просеять через решето (удалить) все числа, кратные этому числу.

5. Если решето не пусто, то повторить шаги 2-5.

Чтобы перевести эти правила на Пролог, мы определим предикат целыедля получения списка целых чисел, предикат отсеятьдля проверки каждого элемента решета и предикат удалитьдля создания нового содержимого решета путем удаления из старого всех чисел, кратных выбранному числу. Это новое содержимое опять передается предикату отсеять.Предикат простые– это предикат самого верхнего уровня, такой что простые(N, L)конкретизирует Lсписком простых чисел, заключенных в диапазоне от 1до Nвключительно.

простые(Предел,Рs):– целые(2,Предел,Is),отсеять(Is,Рs).

целые (Min,Max,[Min|Oct]):-Min=‹Max,!, М is Min+1,целые(М,Мах,Ост).

целые(_,_,[]).

отсеять([],[]).

отсеять([I|Is],[I|Ps]):-удалить(I,Is,Нов),отсеять(Нов,Рs).

удалить(Р,[],[]).

удалить (P,[I|Is],[I|Nis]):-not(0 is I mod Р),!,удалить(Р,Is,Nis).

удалить (P,[I|Is],Nis):-0 is I mod Р,!,удалить(Р,Is,Nis).

Продолжая эту арифметическую тему, рассмотрим Пролог-программу, реализующую рекурсивную формулировку алгоритма Евклида для нахождения наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) двух чисел. Целевое утверждение нод(I,J,K)доказуемо, если Kявляется наибольшим общим делителем чисел Iи J. Целевое утверждение нок(I,J,K)доказуемо, если Kявляется наименьшим общим кратным чисел Iи J:

нод(I,0,I).

нод(I,J,K):– R is I mod J, нод(J,R,K).

нок(I,J,K):– нод(I,J,R), K is (I*J)/R.

Заметим, что из-за особенностей способа вычисления остатка эти предикаты не являются «обратимыми». Это означает, что для того чтобы они работали, необходимо заблаговременно конкретизировать переменные Iи J.

Упражнение 7.10.Если числа X, Yи Z таковы, что квадрат Z равен сумме квадратов Xи Y(т. е. если Z²= X²+ Y²), то про такие числа говорят, что они образуют Пифагорову тройку.Напишите программу, порождающую Пифагоровы тройки. Определите предикат pythagтакой что, задав вопрос

?– pythag(X,Y,Z).

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

7.11. Символьное дифференцирование

Символьным дифференцированием в математике называется операция преобразования одного арифметического выражения в другое арифметическое выражение, которое называется производной.Пусть Uобозначает арифметическое выражение, которое может содержать переменную х.Производная от Uпо хзаписывается в виде dU/dxи определяется рекурсивно с помощью некоторых правил преобразования, применяемых к U.Вначале следуют два граничных условия. Стрелка означает «преобразуется в»; Uи Vобозначают выражения, а с– константу:

dc/dx→  0

dx/dx→  1

d(-U)/dx→  -(dU/dx)

d(U+V)/dx → dU/dx+dV/dx

d(U-V)/dx→  dU/dx-dV/dx

d(cU)/dx→  c(dU/dx)

d(UV)/dx→  U(dV/dx) + V(dU/dx)

d(U/V)dx→  d(UV ^-1)/dx

d(U ^c)/dx→  cU ^{c - l}(dU/dx)

d(lnU)/dx→  U ^-1(dU/dx)

Этот набор правил легко написать на Прологе, поскольку мы можем представить арифметические выражения как структуры и использовать знаки операций как функторы этих структур. Кроме того, сопоставление целевого утверждения с заголовком правила мы можем использовать как сопоставление образцов. Рассмотрим цель d(E,X, F), которая считается согласованной, когда производная выражения  Eпо константе <sup>[12]12
  Имеется в виду константа в смысле Пролога. – Прим. ред.


[Закрыть]</sup> Xесть выражение F. Помимо знаков операций +, -, *, /, которые имеют встроенные определения, нам нужно определить операцию ^, такую, что X^Yозначаете x ^y, а также одноместную операцию ~, такую что ~Хозначает «минус X». Эти определения операций введены исключительно для того, чтобы облегчить распознавание синтаксиса выражений. Например, после того как dопределен, можно было бы задать следующие вопросы:

?– d(x+1,x,X).

X = 1+0

?– d(x*x-2,x,X).

 X = х*1+1*х-0

Заметим, что само по себе простое преобразование одного выражения в другое (на основе правил) не всегда дает результат в приведенной (упрощенной) форме. Приведение результата должно быть записано в виде отдельной процедуры (см. разд. 7.12). Программа дифференцирования состоит из определений дополнительных операций и построчной трансляции приведенных выше правил преобразования в утверждения Пролога:

?– op(10,yfx,^).

?– op(9,fx,~).

d(X,X,1):-!.

d(C,X,0):– atomic(C).

d(~U,X,~A):– d(U,X,A).

d(U+V,X,A+B):– d(U,X,A), d(V,X,B).

d(U-V,X,A-В):– d(U,X,A), d(V,X,B).

d(C*U,X,C*A):– atomic(C), C=X, d(U,X,A),!.

d(U*V,X,B*U+A*V):– d(U,X,A), d(V,X,B).

d(U/V,X,A):– d(U*V^~1),X,A).

d(U^C,X,C*U^(C-1)*W):– atomic(C),C=X,d(U,X,W).

d(log(U),X,A*U^(~1)):– d(U,X,A).

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

Как уже говорилось, данная программа выдает решения в неприведенной форме (т. е. без упрощений). Например, всякое вхождение х*1может быть приведено к х, а всякое вхождение вида х*1+1*х-0может быть приведено к 2*х. В следующем разделе рассматривается программа алгебраических преобразований, которую можно использовать для упрощения арифметических выражений. Примененный способ очень похож на тот, каким выше выводились производные.

7.12. Отображение структур и преобразование деревьев

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

преобразовать([],[]).

преобразовать([А|В],[С|D]):– заменить(А,С),преобразовать(В,D).

Поскольку отображение имеет довольно широкое применение, мы можем определить предикат отобспистакой, что целевое утверждение отобспис(Р, L, M)согласуется с базой данных, применяя предикат Рк каждому элементу списка Lи образуя в результате новый список М. При этом предполагается, что предикат Римеет два аргумента: первый аргумент для передачи «входного» элемента, а второй аргумент – для измененного элемента, подлежащего включению в список М.

отобспис((_,[],[]).

отобспис((P,[X|L],[Y|M]):– Q =..[P,X,Y],call(Q),отобспис(Р,L,М).

Об этом определении следует сказать несколько слов. Во-первых, определение содержит граничное условие (первое утверждение) и общий рекурсивный случай (второе утверждение). Во втором утверждении используется оператор '=..', формирующий целевое утверждение на основе предиката (Р), входного элемента (X)и переменной (Y), которую предикат Рдолжен конкретизировать, чтобы образовать измененный элемент. Затем делается попытка согласовать цель Q, в результате чего Yконкретизируется, образуя голову третьего аргумента данного вызова предиката отобспис. Наконец, рекурсивный вызов отображает хвост первого аргумента в хвост второго.

Функции предиката преобразоватьможет выполнять предикат отобспис. Полагая, что предикат заменитьопределен как в гл. 3, такое использование отобсписмогло бы выглядеть следующим образом:

?– отобспис(заменить,[уоu,аrе,а,computer],Z).

Z = [i, [am, not], a, computer]

Путем упрощения предиката отобсписполучается предикат обрабспис, который просто обрабатывает список, применяя некоторый предикат от одного аргумента к каждому элементу списка. При этом новый список не порождается.

обрабспис(_,[]).

обрабспис(Р,[Х|L]):-Q =…[Р,Х],call(Q),обрабспис(Р,L).

Заметим, что предикат печать_строкииз гл. 5 можно было бы заменить запросом вида обрабспис(put, L), где L– это строка, которую нужно напечатать.

Отображение применимо не только к спискам; оно может быть определено для структуры любого вида. Например, рассмотрим арифметическое выражение, составленное из функторов * и +, имеющих по два аргумента. Пусть мы хотим отобразить одно выражение в другое, устраняя при этом все умножения на 1. Это алгебраическое приведение могло быть определено с помощью предиката sтакого, что s(Op, L, R,Ans)означает, что выражение, состоящее из операции Орс левым аргументом Lи правым аргументом Rприводится к упрощенному выражению Ans. Факты, необходимые для устранения умножений на 1, могли бы выглядеть так (из-за коммутативности умножения нужны два факта):

s(*,X,1,X).

s(*,1,X,X).

Эта таблицы упрощений позволяет нам любое выражение вида 1*Х отобразить в X. Посмотрим, как можно воспользоваться этим в программе.

При приведении выражения Ес помощью такой таблицы упрощений, мы вначале должны привести левый аргумент Е, затем привести правый аргумент Еи, наконец, посмотреть, подходит ли этот приведенный результат под случаи, предусмотренные в нашей таблице. Если это так, то мы порождаем новое выражение в соответствии с указаниями таблицы. В качестве «листьев» дерева, представляющего выражение, фигурируют целые числа или атомы, поэтому для приведения листьев к ним самим в граничном условии мы должны использовать встроенный предикат atomic.Как и выше, мы можем использовать ' =..', чтобы разложить выражение Ена функтор и компоненты;

привести(Е,Е):– atomic(E), 1.

привести(Е,F):-Е =.. [Op,L,R],привести(L,Х),привести(R, Y),s(Op,X,Y,F).

Итак, предикат привестиотображает выражение Ев выражение F, используя для этого факты, имеющиеся в таблице упрощений s. А что делать, если невозможны никакие упрощения? Чтобы избежать в этом случае неудачного завершения s(Op,X, Y, F),мы должны поместить в конец каждого раздела таблицы упрощений, относящегося к определенному оператору, правило-ловушку. Приведенная ниже таблица упрощений содержит правила для сложения и умножения. Кроме того, в ней выделены правила-ловушки для каждого вида операций.

s(+,X,0,X).

s(+,0,X,X).

s(+,X,Y,X + Y) /* ловушка для + */

s(*,_,0,0).

s(*,0,_,0).

s(*,1,X,X).

s(*,X,1,X).

s(*,X,Y,X*Y). /* ловушка для * */

При наличии правил-ловушек возникает вопрос о выборе способа упрощения некоторых выражений. Например, если нам дано выражение 3+0, мы можем либо использовать первый факт, либо применить правило-ловушку для +. Благодаря способу упорядочения фактов, прежде чем применить правило-ловушку Пролог всегда будет пытаться применить правила для специальных случаев. Поэтому первое решение, полученное предикатом привести,всегда будет являться действительно упрощенным выражением (если оно возможно). Однако альтернативные решения будут иметь не самый простой вид из всех возможных.

Другое упрощение, используемое при выполнении алгебраических преобразований с помощью ЭВМ, известно как свертка констант. В выражении 3*4+aконстанты 3 и 4 могут быть «свернуты», что дает в результате выражение 12+а.Правила свертки констант могут быть добавлены всоответствующие места приведенной выше таблицы упрощений. Правило для сложения констант выглядит следующим образом:

s(+,X,Y,Z):– integer(X), integer(Y), Z is X+Y.

Соответствующие правила для других арифметических операций имеют аналогичный вид.

В коммутативных операциях, таких как умножение и деление, указанные выше упрощения могут давать различный эффект на выражениях, которые записаны по-разному, но алгебраически эквивалентны. Например, если правило свертки констант задано для умножения, то предикат привестисовершенно правильно преобразует 2*3*ав 6*а, но а*2*3или 2*а*3будут преобразовываться в самих себя. Чтобы понять, почему это так, подумайте над тем, как выглядят деревья, представляющие эти выражения (см. рис. 7.4).

В первом дереве самое нижнее умножение 2*3можно свернуть, получив 6, но во втором дереве нет поддеревьев, которые было бы можно свернуть. Однако, используя коммутативность умножения, можно добавить к таблице следующее правило, которое позволит справиться с данным конкретным случаем:

s(*,X*Y,W,X*Z):– integer(Y), integer(W), Z is Y*W.

Более общая алгебраическая система может быть построена путем простого добавления дополнительных s-утверждений вместо увеличения объема программы для привести.

Рис. 7.4

7.13. Применение предикатов clause и retract

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

Мы можем определить с помощью предиката clauseнекоторую версию процедуры listing.Определим предикат распеч1такой, что при согласовании цели распеч1(Х)с базой данных из последней будут выводиться на печать утверждения, заголовки которых совпадают с X. Поскольку определение распеч1включает использование предиката clause, у которого Xзадан как первый аргумент, то мы вынуждены поставить условие, что переменная Xконкретизирована таким образом, что главный функтор утверждения известен. Рассмотрим определение распеч1:

распеч1(Х):-clause(Х,Y),выв_утвержд(Х,Y),write('.'),nl,fail.

распеч1(Х).

выв_утвержд(Х,true):-!, write(X).

выв_утвержд(Х,Y):– write((X:– Y)).

При попытке согласовать с базой данных цель распеч1(Х)первое утверждение осуществляет поиск в базе данных такого утверждения, у которого заголовок совпадает с X. Если такое утверждение найдено, то оно выводится на печать и затем с помощью предиката failинициируется механизм возврата. Возвратный ход опять приводит нас к предикату clause,который находит другое такое же утверждение, если оно имеется, и т. д. Когда таких утверждений больше нет, цель clauseбольше не удается согласовать с базой данных. В этом случае будет выбрано второе утверждение определения предиката распеч1,и потому цель будет согласована с базой данных. «Побочным эффектом» этих действий является печать соответствующих утверждений. Определение предиката выв_утверждзадает способ печати найденных утверждений. Выделяется специальный случай, когда тело утверждения есть true.В этом случае на печать выводится только заголовок утверждения. Иначе на печать выводится заголовок и тело утверждения, соединенные функтором ':-'. Отметим, что использование «отсечения» здесь имеет целью указать, что в случае, когда тело есть true,можно применять только первое правило. Поскольку данный пример построен на использовании механизма возврата, то задание отсечения здесь существенно.

Встроенный предикат clauseможно также применить при написании Пролог-интерпретатора на самом Прологе. Это означает, что мы можем определить действия, которые представляют собой выполнение Пролог-программы, причем исполнителем этих действий также является Пролог-программа. Ниже приводится определение предиката интерпреттакого, что цель интерпрет(Х)согласуется в том и только в том случае, когда X, рассматриваемая как цель, согласуется с базой данных.

Предикат интерпретнапоминает встроенный предикат call,но является более ограниченным.

интерпрет(true):-!.

интерпрет((Gl,G2)):-!, интерпрет(G1), интерпрет(G2).

интерпрет(Цель):-clause(Цель,ЕщеЦели), интерпрет(ЕщеЦели).

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

Рассмотрим определение предиката consult.Разумеется, предикат consultпредусмотрен среди встроенных предикатов большинства Пролог-систем, однако интересно посмотреть, как он может быть определен на Прологе.

consult(Файл):-seeing(Input),sее(Файл),repeat,read(Tepм),обработать(Терм),seen,see(Input),!.

обработать(Терм):– маркер_конца_файла(Терм),!.

обработать((?– Q)):-!, call(Q),!, fail.

обработать(Утвержд):– assertz(Утвержд), fail.

Это определение отличается рядом интересных особенностей. Во-первых, цель seeing(Input)и ее партнер see(Input)призваны гарантировать, что текущий файл ввода не будет «забыт» после применения предикат consult.Во-вторых, предикат маркер_конца_файлаздесь использован без определения. По замыслу он должен быть истинным только в том случае, когда его аргумент конкретизирован термом, используемым для представления конца файла (который мог бы встретиться при выполнении read). Вразных реализациях Пролога для представления «конца файла» используются разные термы, поэтому маркер_конца_файлав разных реализациях может быть определен по-разному. Одно из возможных определений выглядит так:

маркер_конца_файла(конец_файла).

В определении предиката обработатьинтересна организация выполнения соответствующих действий для каждого терма, считанного из входного файла. Целевое утверждение обработатьдоказуемо только, когда его аргументом является маркер конца файла. Иначе после соответствующего действия имитируется неудача доказательства и инициируется механизм возврата, который возвращает программу к предикату repeat.Отметим важность «отсечения» в конце определения предиката consult.Оно фиксирует выбор, сделанный предикатом repeat [13]13
  Тем самым обеспечивает возможность вновь согласовать предикат consult. В противном случае механизм возврата никогда не смог бы миновать repeat, у которого всегда есть альтернативное решение. – Прим. ред.


[Закрыть].И последнее замечание. Если терм, считанный из файла, представляет собой вопрос (см. второе утверждение определения предиката обработать),то делается попытка немедленно согласовать соответствующую цель с помощью предиката call(см. разд. 6.7).

В качестве примера использования предиката retractздесь приведено определение полезного предиката уберивсе.При согласовании с базой данных целевого утверждения уберивсе(Х)все утверждения, заголовки которых совпадают с X, удаляются из базы данных. Поскольку в данном определении используется предикат retract,то переменная Xне может быть неконкретизированной, так как в противном случае не с чем будет сопоставлять утверждения из базы данных. Данное определение должно распознавать два вида утверждений с заголовками, совпадающими с X, – факты и правила. При обработке этих двух видов утверждений в вызове retractзадаются разные аргументы. В определении используется то свойство, что retractбудет срабатывать при возврате до тех пор, пока все утверждения, сопоставимые с его аргументами, не будут удалены из базы данных.

уберивсе(Х):– retract(X), fail.

уберивсе(Х):– retract((X:– Y)), fail. уберивсе(_).

В качестве примера использования предиката уберивсе здесь приведено определение предиката reconsultна Прологе. Назначение предиката reconsultсходно с назначением предиката consult,с той лишь разницей, что при reconsultкаждое считанное утверждение замещает существующее утверждение того же предиката, а не добавляется к нему (см. разд. 6.1).

reconsult(Файл):-уберивсе(сделано(_)),seeing(Старый),sее(Файл),repeat,read(Терм),проверить(Терм),seen,see(Старый),!.

проверить(Х):– маркер_конца_файла(Х),!.

проверить((?– Цели)):-!, call (Цели),!, fail.

проверить(Утверждение):-заголовок(Утверждение, Заголовок), запись_сделана(3аголовок), assertz(Утверждение), fail.

запись_сделана(3аголовок):– сделано(Заголовок),!.

запись_сделана(3аголовок):– functor(Заголовок,Func,Arity), functor(Proc,Func,Arity), asserta(cдeлaнo(Proc)), уберивсе(Ргос),!.

заголовок((А:– В), А):-!.

заголовок (А, А).

Это определение похоже на определение consult,в котором вместо предиката обработатьиспользуется предикат проверить.Основное различие заключено в предикате запись_сделана. Когда в файле появляется первое утверждение для данного предиката, то, прежде чем к базе данных будет добавлено хотя бы одно новое утверждение, из нее должны быть удалены все старые утверждения для данного предиката. Удаление этих утверждений нельзя откладывать до момента, когда в базе данных появятся их новые версии, поскольку в этом случае мы удалили бы из базы данных те утверждения, которые только что были введены. Как же определить, что некоторое утверждение в файле является первым для соответствующего предиката? Ответ заключается в том, что мы регистрируем в базе данных предикаты, для которых уже нашлись утверждения в файле. Это делается с помощью предиката сделано. Когда из файла считывается первое утверждение например, для предиката fooс двумя переменными, то имеющиеся утверждения удаляются и новое утверждение добавляется к базе данных. Кроме того, к базе данных добавляется факт:

сделано(foo(_,_)).

В дальнейшем, при чтении остальных утверждений для предиката too,мы сможем проверить, что старые утверждения уже удалены из базы данных. Тем самым удается избежать ошибочного удаления новых утверждений. Для данного определения важно, что мы не добавляем в базу данных что-нибудь вроде:

сделано(foо(а,Х)).

поскольку в этом случае аргумент предиката сделаноне обязательно совпадает с заголовком утверждения для foo.Пара запросов

…,functor(Заголовок,Func,Arity),functor(Proc,Func,Arity),…

конкретизирует Ргосструктурой, имеющей тот же функтор, что и заголовок Заголовок, но с переменными в качестве аргументов (см. разд. 6.5).