Методические указания по языку «Пролог» (стр. 3 )

Примеры:

D isзаканчивается успехом и D

становится равным 5

4 is 2 * 4 - 4 заканчивается успехом

2 * 4 - 4 is 4 заканчивается неудачей

a is 3 + 3 заканчивается неудачей

X is 4 + а заканчивается неудачей

2 is 4 - X заканчивается неудачей

Обратите внимание, что предикат is требует, чтобы его первый аргумент был числом или неконкретизированной переменной. Поэтому М - 2 is 3 записано неверно. Предикат is не является встроен­ным решателем уравнений.

Системные предикаты =:=, -\-, , - и - определены как инфиксные операторы и применяются для сравнения результатов двух арифметических выражений.

Для предиката @ доказательство целевого утверждения X@Y заканчивается успехом, если результаты вычисления арифметических выражений X и Y находятся в таком отношении друг к другу, кото­рое задается предикатом @.

Такое целевое утверждение не имеет побочных эффектов и не может быть согласовано вновь. Если X или Y - не арифметические выражения, возникает ошибка.

С помощью предикатов описываются следующие отношения:

X =:= Y X равно Y

X=\=Y Хне равно Y

X <Y X меньше Y

X >Y X больше Y

X <= Y X меньше или равно Y

X >= V X больше или равно Y

Использование предикатов иллюстрируют такие примеры:

а 5 заканчивается неудачей

5 + 2 + 7 5 + 2 заканчивается успехом

3 + 2 =:= 5 заканчивается успехом

3 + 2 = 5 заканчивается неудачей

2+1 =\= 1 заканчивается успехом

N>3 заканчивается успехом, если

N больше 3, и неудачей в противном

cлучае

3 Рекурсия

Рекурсия является мощным методом программирования. В Про­логе она приобретает особую важность, поскольку здесь отсутствуют циклические конструкции while...do... и repeat...until, присущие обычным языкам программирования. В данной главе на числовых примерах показаны идеи рекурсии.

Обычная стратегия решения задач состоит в том, чтобы разбить исходную задачу на более мелкие подзадачи, решить их, а затем объ­единить подзадачи с тем, чтобы получить решение исходной задачи. !? этом и заключается стратегия «разделяй и властвуй». Может по­требоваться разбиение подзадачи на еще более мелкие и решение их но частям.

Если подзадача есть уменьшенный вариант исходной задачи, то t «особ ее разбиения и решения идентичен примененному к исходной задаче.

Такой процесс называется рекурсией. Для того чтобы описанный метод решения был результативным, он должен в конце концов при­нести к задаче, решаемой непосредственно. Решить ее позволяют ут­верждения, называемые граничными условиями.

Пример 3.1.1

Рассмотрим способы определения n-го терма в последовательности:

1,1,2,6,24,120,720,...

Первый вариант описания таков: нулевой терм равен 1, первый герм получается при умножении 1*1, второй терм - при умножении 1 *1*2, третий - при умножении 1*1*2*3, и в общем случае, n-й терм получается при умножении 1*1*2*3*... *n.

С другой стороны, нулевой терм есть 1, а n-й терм есть (п - 1)-й терм, умноженный на n. Данное определение является рекурсивным, поскольку разбивает задачу нахождения n-го терма на задачи на­хождения сначала (n-l)-ro терма и умножения его затем на п.

Ясно, что оба определения эквивалентны, ибо, например, задача вычисления третьего терма с помощью рекурсивного определения водится к задаче вычисления второго терма и умножения его на 3. Задача вычисления второго терма сводится к задаче вычисления нулевого терма и умножения его на 1. Поскольку нулевой терм равен 1, вычислим первый терм - он будет равен 1. Это в свою очередь позво­ляет нам вычислить второй терм - он равняется 2, а затем - третий терм, равный 6.

Для обозначения факта, что N-й член последовательности равен V, воспользуемся предикатом посл(М, У). Рекурсивное определение выражается следующими утверждениями Пролога:

/* ГРАНИЧНОЕ УСЛОВИЕ - нулевой терм равен 1 посл(0,1).

/* РЕКУРСИВНОЕ УСЛОВИЕ - если (N-D-й терм равен U, то

/* N-й терм равен U * N

посл(N, V) :-

M is N-1,

посл(М, U),

V is U * N.

Ответом на вопрос

?-посл(3,Z).

будет.

Z=6

другие решения (да/нет) ? нет

Заметим, что если на вопрос Пролог-системы мы ответим «да» вместо «нет», то система попадает в бесконечный цикл. В гл. 8 мы по­кажем, как избежать такой ситуации.

Для того чтобы представить, каким образом Пролог находит от­вет, рассмотрим вопрос

?-посл(3,Х).

и опишем работу Пролога на двух этапах: разбиения и решения за­дачи.

Фаза разбиения

Первое обращение. Пролог пытается удовлетворить запрос посл(3,Х), используя первое утверждение процедуры описания по­следовательности посл(0,1). Поскольку первая компонента терма (0) не сопоставляется с первой компонентой запроса (3), попытка за­канчивается неудачей.

Теперь Пролог пытается использовать второе утверждение, опи­сывающее последовательность. На этот раз голова второго утвержде­ния посл(N,V) сопоставляется с запросом посл(3,Х), при этом N получает значение 3, а V связывается с X. Пролог переходит к дока­зательству целей в теле утверждения:

/*N=3

/*V=X

M is 3 - 1,

посл(М, U),

X is U * 3. / * откладывается

Первое целевое утверждение согласуется при М = 2. Второе целе­вое утверждение посл(2,U) приводит ко второму рекурсивному обра­щению. Пролог пытается согласовать третье целевое утверждение только при условии, что согласовано второе. Поэтому третье целевое утверждение откладывается.

Второе обращение. Для того чтобы согласовать посл(2,U), Про­лог пытается сопоставить посл(2,U) с первым утверждением проце­дуры поcл (0,1), но неудачно, поскольку первые компоненты термов не сопоставляются.

Однако удается сопоставить посл(2,U) с головой второго утверж­дения посл(N2,V2) при N2, равной 2, и V2, равной U. Теперь Пролог пытается согласовать тело утверждения:

/*N2=2

/*V2=U

M2 is 2 - 1,

посл(М2,U2),

U is U2 * 2. /* откладывается

Мы использовали то же утверждение, что и в первом обращении, но с меньшим аргументом N2.

Чтобы отличить второе обращение к утверждению от первого, присвоим переменным индекс 2. В общем случае индекс n у перемен­ной показывает, что она применяется при n-м обращении. Перемен­ные при первом обращении записаны без индексов.

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

Третье обращение. Чтобы согласовать посл(1,U2), Пролог пыта­ется сопоставить его с первым утверждением определения поcл(0,1), но неудачно. Однако удается сопоставить посл(1,U2) с головой вто­рого утверждения, причем N3 получает значение 1, a V3 связывается с U2. Следовательно, теперь надо согласовать цели:

/* N3=1

/*V3=U2

M3 is 1 - 1,

посл(M3,U3),

U2 is U3* 1. /* откладывается

Первое целевое утверждение согласуется при МЗ, равной 0.

Второе целевое утверждение посл(0,U3) Пролог пытается согла­совать, сопоставляя его с первым утверждением определения. На этот раз два терма успешно сопоставляются при U3, равной 1.

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

Фаза решения задачи

Согласование посл(1,U2). Самое последнее из отложенных це­левых утверждений - третье целевое утверждение в третьем обраще­нии: U2 is U3 * 1. Поскольку переменная U3 равна 1 в результате со­гласования второго целевого утверждения, U2 получает значение 1. Таким образом, посл(1,U2) согласуется при U2, равной 1.

Согласование посл(2,U). Предпоследнее отложенное целевое ут­верждение - третье целевое утверждение во втором обращении: U is U2 * 2. Так как переменная U2 равна 1 в результате согласования второго целевого утверждения, U получает значение 2. Итак, посл(2,U) согласуется при U, равной 2.

Согласование посл(3,Х). Предыдущее из отложенных целевых утверждений - третье целевое утверждение в первом обращении: X is U * 3. Поскольку переменная U равна 2 в результате согласования второго целевого утверждения, X получает значение 6. Целевое ут­верждение посл(З, Х) согласуется при X, равной 6.

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

Х=6

другие решения (да/нет)? Нет

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

Рис. 3.1.1. Трассировка запроса?- посл(3,Х).

Пример 3.1.2

Требуется написать процедуру для вычисления ряда

f(x, n)=1+х+х^2+х^З+...+х^n

при известных действительном числе x и натуральном числе n.

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

1+x+x^2+x^3+x^n

для данных х и n. Тогда голова утверждения будет выглядеть следу­ющим образом: f(X,N,S). (Напомним, что переменные в Прологе должны начинаться с заглавной буквы.)

Для того чтобы написать утверждения, мы должны преобразовать приведенное выше определение ряда в рекурсивное определение.

Это можно сделать, учитывая, что

f(х,0) = 1

f(x,1) = 1 + x = f(x,0) * x + l

f(х,2) = 1 + х + х^2 = f(х,1) * x + 1

…

…

…

f(х, n) = 1 + х + х^2 + х^n = f(х, n-1) * х + 1

Определим ряд рекурсивно:

f(х,0) = 1

f(x, n) = f(x, n - 1) * х + 1

Такому определению соответствуют следующие утверждения Пролога:

/* ГРАНИЧНОЕ УСЛОВИЕ

f(x,01).

/* РЕКУРСИВНОЕ УСЛОВИЕ

f(x, n,s) :-

M is N - 1,

f(X, M,R),

S is R*X + 1.

На рис.4.1.2 показано, как Пролог согласует запрос ?- f(2,3,T).

Рис. 3.1.2. Трассировка запроса ?- f(2,3,T).

Мы рассмотрели процесс разбиения задач на подзадачи и их решения. Так, в примере 4.1.1 для определения посл(4,V) нужно вычислить

посл(3,V2),посл(2,VЗ),...,посл(0,V5)

и построить решение, выбрав в качестве базиса граничное условие.

Рис.3.1.2. Трассировка запроса?- f(2,3,T).

Другой подход заключается в том, чтобы, начав с граничного условия, строить решение до тех пор, пока не будет решена исходная задача. Следуя данному подходу и пытаясь найти четвертый член в последовательности, мы должны начать с граничного условия 1, вы­числить значение первого терма 1*1, второго - 1*1*2, третьего -1*1*2*3 и, наконец, четвертого - 1*1*2*3*4. Такую стратегию мы называем восходящей.

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

Пример 3.2.1

Если применить восходящую стратегию к решению задачи, взятой из примера 4.1.1, мы получим следующие утверждения Пролога:

/* пoстp_пocл(NS, VS, N,V) строит N-й

/* терм последовательности - V

/* VS - это значение NS-гo терма

/* в построенной к данному моменту

/* последовательности

/* Требуемое решение:

постр_посл(N, V,N, V).

/* Построение следующего решения

постр_посл(NS, VS, N,V) :-

NSl is NS+1,

VSl is VS*NS1,

постр_посл (NS1, VS1 ,N, V).

Запрос включает граничное условие как решенную к настоящему времени задачу. На запрос

?- постр_посл(0,1,7,V).

получаем

V=5040

другие решения (да/нет)? нет

Альтернативным вариантом является определение еще одного утверждения, которое маскирует дополнительные параметры в постр_посл:

посл_п(N, V) :-постр_посл(0,1,N, V).

так что

?-nocл_п(7,V).

дает

V=5040

Определение рекурсии можно непосредственно выразить утверж­дениями Пролога.

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

Пример 3.3.1

Рассмотрим методы вычисления Х^n с помощью одного только умножения. Здесь n - натуральное число (натуральным числом явля­ется положительное целое число или нуль).

Очевидный способ - умножить X на себя n раз. Получим следую­щие утверждения:

степень(Х,0,1). /*Х^0 равно 1

степень(Х, N,R) :-

M is N - 1,

степень(X, M,Q),

R is Q * X.

Тогда ответом на запрос

?-степень(5,8,S).

будет:

S = 390625

Этот результат получен с помощью 8 умножений (рис.4.3.1).

Но можно также воспользоваться свойствами:

Х^n = Z * Z, где Z – Х^(n div 2), если n - четное, и

Х^n = Х^(n -1) * X, если n - нечетное,

и получить следующие утверждения:

степень_быстро(Х,0,1).

степень_быстро(Х, N,R) :-

О is N mod 2,

М is N div 2,

степень_быстро(Х, М,Q),

R is Q * Q.

степень_быстро(Х, N,R) :-

M is N - 1,

степень_быстро(Х, М,Q),

R is Q * X.

Во втором случае понадобится только 4 умножения (рис.4.3.2) при обработке запроса

?- степень_быстро(5,8,S).

и будет получен ответ

S - 390625

Заметим, что в третьем утверждении степень_быстро нам не нужно было проверять, является ли N нечетным. Мы предполагаем, что второе утверждение не сопоставляется с целью в том случае, ес­ли N mod 2 не равно 0, т. е. N не является четным. Следовательно, третье утверждение выбирается только тогда, когда N является не­четным (за исключением вопросов об альтернативных вариантах).