Перебор в Прологе. Механизм прямой трассировки и механизм возврата.

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

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

Связь между X и Y можно определить с помощью следующих трех правил:

Правило 1: если X < 3, то Y = 0

Правило 2: если 3< = X и X < 6, то Y = 2

Правило 3: если 6 < = X, то Y = 4

На Прологе это можно выразите с помощью бинарного отношения f( X, Y) так:

f( X, 0): - X < 3. % Правило 1

f( X, 2): - 3 =< X, X < 6. % Правило 2

f( X, 4): - 6 =< X. % Правило 3

В этой программе предполагается, конечно, что к моменту начала вычисления f( X, Y) X уже конкретизирован каким-либо числом; это необходимо для выполнения операторов сравнения.

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

Трассировка. меньше(X.Y): -

X< Y, write(X),

write ('меньше, чем'), write(Y).

меньше(Х.У): -

Y< X, write(Y),

write ('меньше, чем'), write(X).

Целевое утверждение? - меньше (5, 2). сопоставляется с головой первого утверждения при Х=5 и У=2. Однако не удается согласовать первый член конъюнкции в теле утверждения X< Y. Значит, Пролог не может использовать первое утверждение для согласования целевого утверждения меньше(5, 2). Тогда Пролог переходит к следующему утверждению, голова которого сопоставима с целевым утверждением. В нашем случае это второе утверждение. При значениях переменных Х=5 и Y=2 тело утверждения согласуется. Целевое утверждение меньше(5, 2) доказано, и Пролог выдает сообщение " 2 меньше, чем 5". Запрос? -меньше (2, 2). сопоставляется с головой первого утверждения, но тело утверждения согласовать не удается. Затем происходит сопоставление с головой второго утверждения, но согласовать тело опять-таки оказывается невозможно. Поэтому попытка доказательства целевого утверждения меньше(2, 2) заканчивается неудачей.

Такой процесс согласования целевого утверждения путем прямого продвижения по программе мы называем прямой трассировкой (forward tracking).

Отсечение в прологе, виды отсечений.

Специальное целевое утверждение «!, », называемое отсечением. Отсечение реализуетяс следующим образом: после согласования ЦУ, стоящего перед отсечением, все предположения с тем же предикатом расположенные после отсечения не рассматриваются.

Удаление отсечений из программы может привести к изменению ее декларативного смысла. Но бывают также такие случаи, когда отсечение на него не влияло. Использование отсечений последнего типа требует меньшей осторожности, и поэтому такие отсечения иногда называют " зелеными отсечениями". С точки зрения наглядности программы такие отсечения " невинны" и их использование вполне приемлемо. При чтении программы их можно просто игнорировать. Напротив, отсечения, влияющие на декларативный смысл, называются " красными". Красные отсечения — это такие отсечения, которые делают программу трудной для понимания, и их нужно применять с особой осторожностью.

f( X, 0): - X < 3, !.

f( X, 2): - X < 6, !.

f( X, 4).

Примеры, использующие отсечение:

1) Вычисление максимума

max(X, Y, X): -X> Y,!.

max(X, Y, Y): -X< Y.

? -max(10, 15, Y), write(Y). %15Yes.

2) Принадлежность элемента списку

member(El, [El|_]): -!.

member(El, [_|Tail]): -member(El, Tail).

? -member(a, [a, c]). %Yes

3) Добавление элемента в список

add(El, Lst, [El|Lst]).

? -add(a, Lst1, Lst2), Lst1=[b, v, c], write(Lst2). %[a, b, v, c]Yes.

add(El, Lst, Lst): -member(El, Lst),!.

add(El, Lst, [El|Lst]).

? -add(a, Lst1, Lst2), Lst1=[b, a, c], write(Lst2).%No

Операторная запись.

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

: - op( 600, xfx, родитель).

Такая запись сообщит Прологу, что мы хотим использовать " родитель " в качестве оператора с приоритетом 600 и типом 'xfx', обозначающий одну из разновидностей инфиксного оператора. Форма спецификатора 'xfx' указывает на то, что оператор, обозначенный через 'f', располагается между аргументами, обозначенными через 'х'.

Существуют три группы типов операторов, обозначаемые спецификаторами:

1) инфиксные операторы трех типов: xfx xfy yfx

2) префиксные операторы двух типов: fx fy

3) постфиксные операторы двух типов: хf yf

Спецификаторы выбраны с таким расчетом, чтобы нагляднее отразить структуру выражения, в котором 'f' соответствует оператору, а 'x' и 'y' представляют его аргументы.

Между 'x' и 'y' есть разница. Если аргумент заключен в скобки или не имеет структуры (является простым объектом), тогда его приоритет равен 0; если же он структурный, тогда его приоритет равен приоритету его главного функтора. С помощью 'x' обозначается аргумент, чей приоритет должен быть строго выше приоритета оператора (т e. его номер строго меньше номера приоритета оператора); с помощью 'y' обозначается аргумент, чей приоритет выше или равен приоритету оператора.

Типовые предикаты Пролога.

Типовые предикаты - позволяющие определить к какому типу относится объект.

1) var( X) - Эта цель успешна, если X в текущий момент — не конкретизированная переменная.

2) nonvar( X) - Эта цель успешна, если X — терм, отличный от переменной, или если X — уже конкретизированная переменная.

3) atom( X) - Эта цель истинна, если X обозначает атом.

4) integer( X)- Цель истинна, если X обозначает целое.

5) atomic( X) - Цель истинна, если X обозначает целое или атом.

⇐ Предыдущая 123 Следующая ⇒