Руководство к пользованию TURBO PROLOG

append([1,2,3],[5,6],L) and writelist(L).

Теперь попробуйте поработать с такой целью:

append([1,2],[3],L),append(L,L,LL),writelist(LL).

/* Программа 12 */

domains

i_list = integer*

predicates

append(i_list,i_list,i_list)

writelist(i_list)

clauses

append([],List,List).

append([[X|L1],List2,[X|L3]) if

append(L1,List2,L3).

writelist([]).

writelist([Head|Tail]) if

write(Head),nl,writelist(Tail).

Один предикат может иметь несколько приложений

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Если посмотреть на предикат append с декларативной точки

зрения, то мы определили отношение между тремя списками. Это

отношение также имеет место, если списки List1 и List2 извес-

тны, а список List2 - нет или если известен только список

List3. Чтобы найти, например, какие два списка могут быть об-

ъединены в некоторый известный список, можно воспользоваться

следующей целью:

append(L1,L2,[1,2,4])

Турбо Пролог отыщет решения, приведенные ниже, и даст такой

ответ:

L1=[],L2=[1,2,4]

L1=[1],L2=[2,4]

L1=[1,2],L2=[4]

L1=[1,2,4],L2=[]

4 solytions

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

append, чтобы найти, какой список должен быть присоединен к

списку [3,4], чтобы в результате получился список [1,2,3,4].

Для этого следует задать цель

append(L1,[3,4],[1,2,3,4]).

Турбо Пролог найдет такое решение: L1 = [1,2].

Предикат append был определен как отношение между набором

входных данных и набором выходных данных, причем это отноше-

ние можно использовать двумя способами. Следовательно, можно

задавать любой из следующих двух вопросов:

"Какие выходные данные соответствуют заданным входным ?"

"Какие входные данные соответствуют заданным выходным ?"

Упражнение. Поправьте предложения для предиката member в

программе 11 и постройте предложения для предиката evenmember

(четный_член) так, чтобы можно было разрешить такую цель, как

evenmember(2,[1,2,3,4,5,6]).

и чтобы при задании цели

evenmember(X,[1,2,3,4,5,6]).

на экране появился ответ:

X=2

X=4

X=6

3 solutions

5. ЗАНЯТИЕ 3:

НЕУСТАННЫЙ ПОИСК РЕШЕНИЙ В ТУРБО ПРОЛОГЕ

Эта глава делится на две основные части. В первой из них

мы подробно исследуем процесс, используя который Турбо Пролог

пытается добиться соответствия цели с предложением. Этот про-

цесс называется унификацией и соответствует передаче парамет-

ров в других языках программирования.

Во второй части мы изучим, каким образом в Турбо Прологе

осуществляется управление поиском решений для заданных целей.

Сюда входят приемы, которые дают возможность программе выпол-

нить задачу, выполнение которой при других обстоятельствах

было бы невозможно. Это могло объясняться либо слишком боль-

шим временем поиска,либо (что менее вероятно при работе с Ту-

рбо Прологом)тем, что система выходит за пределы свободной

памяти.

Установка соответствия, унификация термов

Рассмотрим программу 13 в рамках (внешней) цели

writeln_by(X,Y)

/* Программа 13 */

Domains

title,autor = symbol

pages = integer

publication = book(title,page)

Predicates

writeln_by(autor,publication)

long_novel(title)

Clauses

writeln_by(fleming,book("DR NO",210)).

writeln_by(melvill,book("MOBY DICK",600)).

long_novel(Title):-writeln_by(_,book(Title,Lenght)),

Lenght > 300.

Когда Турбо Пролог пытается удовлетворить указанную цель,

он должен по очереди пробовать каждое предложение для преди-

ката written_by (написана), чтобы добиться соответствия между

параметрами Х,У и параметрами в каждом предложении для ука-

занного предиката. Эта операция установки соответствия между

термами называется унификацией.

Поскольку в рассматриваемой цели Х и У представляют собой

свободные переменные, а свободную переменную можно унифициро-

вать с любым другим термом, самое первое предложение для пре-

диката written_by унифицируется с предложением, описывающим

цель:

writeln_by( X , Y )

| |

writeln_by(fleming,book("MOBY DICK",600)).

Таким образом, переменная Х становится связанной со значением

fleming (Флеминг), а переменная У связывается с книгой book

"MOBY DICK", 600). Поэтому Турбо Пролог ответит:

X=fleming,Y=book("MOBY DICK",600)

1 Solution

Если, с другой стороны, задать для программы 13 такую

цель, как

wrutlen_by(X,book("MOBY DICK",Y)).

то вновь будет сделана попытка выполнить унификацию с первым

предложением для предиката written_by:

wrutlen_by( X ,book("MOBY DICK",Y))

| |

wrutlen_by(flemling,book("DR NO",210))

Поскольку переменная Х свободна, она связывается со значением

fleming, после чего делается попытка установить соответствие

между

book("DR NO",200)

и

book("MOBY DICK",Y)

Составной терм можно унифицировать с другим составным термом,

если оба они содержат один и тот же функтор, имеют одинаковое

число аргументов, а все подтермы попарно унифицируются. В

данном случае функтор - один и тот же (book), а число подтер-

мов в обеих ситуациях равно двум. Однако константа MOBY DISK

может быть унифицирована только либо сама с собой, либо со

свободной переменной. Таким образом, соответствие между конс-

тантами MOBY DISK и DR NO недопустимо, и унификации не проис-

ходит.

Теперь Турбо Пролог пытается установить соответствие меж-

ду

wrutlen_by( X ,book("MOBY DICK",Y))

и

wrutlen_by(melvill,book("MOBY DICK",600))

Свободная переменная Х унифицируется (и становится связанной)

с константой melville (Мелвил). Составные термы

book("MOBY DICK",Y)

----------------------

сноска! *) Ошибка. Очевидно, что рассмотренная цель имеет два реше-

ния, и ни одно из них не совпадает с указанным в тексте.

(Прим.перев.)

и

book("MOBY DICK",600)

унифицируются, поскольку оба они содержат один и тот же функ-

тор book, имеют одинаковое число аргументов, константа MOBY

DISK унифицируется сама с собой, а константу 600 можно унифи-

цировать со свободной переменной У. Таким образом, цель удов-

летворяется, и Турбо Пролог отвечает:

X=melvill,Y=600

1 Solution

И наконец, рассмотрим выполнение цели

long_novel(X)

Когда Турбо Пролог пытается удовлетворить цель, он проверяет,

не существует ли соответствующий факт или левая часть какого

-нибудь правила. В данном случае достигается соответствие с

левой частью правила

long_novel(X)

|

long_novel(Title):-

wrutlen_by(_,book(Title,Lenght)),Lenght>300.

так как свободную переменную Х можно унифицировать с любым

другим термом и, в частности, с другой свободной переменной.

Далее Турбо Пролог делает первое предложение в правой части

этого правила текущей подцелью, после чего происходит унифи-

кация с первым фактом для предиката written_by:

wrutlen_by(Name,book(Title,Lenght)),

wrutlen_by(fleming,book("DR NO",210)),

Переменная Length (число_страниц) связывается при этом с кон-

стантой 210.

Теперь рассматривается второе предложение в правой части

правила для предиката long_novel (длинный_роман)

Lenght>300

и оно становится текущей подцелью. Перед тем, как провести

унификацию, связанная переменная Length заменяется на значе-

ние, с которым она связана, т.е. 210. Поскольку неравенство

210>300

представляет собой допустимое сравнение двух целых чисел, та-

кое сравнение выполняется и, конечно же, возвращает ложь. Те-

перь Турбо Пролог пытается произвести другую унификацию под-

цели

wrutlen_by(Name,book(Title,Lenght))

(см.следующий раздел) и связывает переменную Title (название)

с константой "MOBE DICK", а переменную Length - с константой

600. После этого подцель

Lenght>300

унифицируется с переменной Length, замененной на константу

600 (т.е. на значение, с которым она связана), что действи-

тельно приводит к успеху. Поэтому подцель для предиката

long_novel также удовлетворяется, когда переменная Title свя-

зана со значением "MOBY DICK". В результате Турбо Пролог вы-

водит на экран:

X="MOBY DICK"

1 Solution

Краткий обзор алгоритма унификации в Турбо Прологе

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Свободную переменную можно унифицировать с любым термом.

В результате эта переменная связывается с этим термом.

Константа (например, целое число) может быть унифицирова-

на сама с собой или со свободной переменной.

Составной терм можно унифицировать с другим составным

термом, если оба они содержат один и тот же функтор и имеют

одинаковое число аргументов. Кроме того, все подтермы должны

быть унифицированы попарно. (Списки рассматриваются как спе-

циальная разновидность составных термов.)

До проведения унификации связанные переменные заменяются

на значения, с которыми они были связаны.

Таким образом, унификация обеспечивает:

- присваивание значений переменным (т.е. передачу пара-

метровв);

- доступ к структурам данных посредством общего механизма

установки соответствия;

- определенные разновидности проверок на совпадение.

Управление поиском решений

В этом разделе мы посмотрим на некоторые приемы, которыми

можно пользоваться в Турбо Прологе для управления поиском ре-

шений, соответсвующих нашим целям.

Давайте начнем с программы 14 и посмотрим на нее в свете

такой цели, состоящей из двух подцелей:

likes(X,wine) and likes(books).

/* Программа 14 */

Domains

name,thing=symbol

Predicates

likes(name,thing)

reads(name)

is_inquisitive(name)

Удовлетворение второй подцели начинается с процедуры по-

иска, причем поиск проводится заново. При этом считается, что

Х = john. Первое предложение

likes(john,wine)

не удовлетворяет подцель

likes(X,books)

так как wine (вино) - это совсем не то, что books (книги).

Следовательно, Турбо Пролог должен проверить следующее пред-

ложение, но lance (Ланс) не соответствует значению переменной

Х (john), поэтому поиск продолжается и переходит к третьему

предложению

likes(Z,books) if reads(Z) and is_inquisitive(Z).

Параметр - это переменная и поэтому соответствует пере-

менной Х; кроме того, вторые параметры согласованы. Поскольку

Х соответствует , Турбо Пролог требует, чтобы переменная

также была связана со значением john.

Теперь мы знаем, что наша подцель соответствует левой

части правила. Продолжение поиска определяется третьим основ-

ным принципом:

Если подцель соответствует левой части правила, то далее

следует удовлетворять правую часть этого правила. Правая

часть составляет новый набор подцелей.

Исходя из этого принципа, мы получаем следующее дерево

целей:

likes(X,wine) likes(X,books)

------------------ ------------------

likes(john,wine) likes(Z,books)

/ |

reads(Z) is_inquisitive(Z)

Дерево целей включает теперь подцели

reads(Z)

и

inquisitive(Z)

причем переменная Z имеет значение john. Теперь Турбо Пролог

будет искать факты, соответствующие обеим подцелям. Получаю-

щееся в результате окончательное дерево целей показано ниже:

likes(X,wine) likes(X,books)

------------------ ------------------

likes(john,wine) likes(Z,books)

/ |

reads(Z) is_inquisitive(Z)

-------- -----------------

reads(john) is_inquisitive(john)

Теперь мы знаем, что наша первоначальная цель удовлетво-

рена. Это вытекает из четвертого основного принципа:

Цель считается удовлетворенной, если для всех терминаль-

ных вершин (листьев) дерева целей найдены соответствующие

факты.

Турбо Пролог использует результаты процедуры поиска раз-

личными способами, и это зависит от того, каким образом такая

процедура была начата. Если цель - это подцель в правиле, то

Турбо Пролог пытается удовлетворить следующую подцель в том

же правиле. Если цель - это вопрос, исходящий от пользовате-

ля, то Турбо Пролог непосредственно отвечает:

X=john

1 solution

Как мы уже видели в главе 3, однажды удовлетворив цель,

Турбо Пролог осуществляет возврат в поиске альтернативных ре-

шений. Кроме того, он будет делать возврат, если анализ под-

цели закончился неудачно. Он будет пытаться заново удовлетво-

рить предыдущую подцель так, чтобы неудавшаяся подцель была

удовлетворена при новых значениях переменных.

Чтобы выполнить подцель, Турбо Пролог начинает поиск с

первого предложения для предиката. Здесь могут быть два исхо-

да.

1. Начало соответствующего предложения найдено. После

этого происходит следующее.

а) Если существует другое предложение, которое, быть мо-

жет, еще раз удовлетворит цель, то первое такое предложение

помечается указателем, соответствующим точке возврата.

б) Все свободные переменные в подцели которым соответст-

вуют значения в начальной части предложения, получают эти

значения (т.е. такие переменные становятся связанными).

в) Если соответствующее предложение представляет собой

левую часть правила, то такое правило должно быть удовлетво-

рено. Это достигается за счет рассмотрения правой части пра-

вила в качестве новой цели.

2. Найти начало соответствующего предложения невозможно,

и цель не достигается. Турбо Пролог осуществляет возврат и

пытается удовлетворить предыдущую подцель заново. Все пере-

менные, которые были свободными до того, как эта подцель была

в прошлый раз удовлетворена, становятся свободными вновь.

Прежде всего Турбо Пролог отыскивает предложение, на

которое установлен указатель. Если поиск безрезультатен то

возврат осуществляется еще раз. Если возвраты приводят к ис-

черпанию предложений для всех подцелей, то цель не достигает-

ся.

Использование предиката fail

В Турбо Прологе определен стандартный предикат, который

вынуждает возврат - fail (неудача). Предикат fail вызывает то

же действие, что отношение 2 = 3. Чтобы продемонстрировать

использование этого предиката, воспользуемся программой 15.

/* Программа 15 */

Domains

name=symbol

Predicates

father(name,name)

everybody

Clauses

father(leonhard,katerine).

father(carl,jason).

father(carl,marylin).

everybody if

father(X,Y) and

write(X," is ",Y,"'s father\n") and

fail.

Целью father (Х, У) можно воспользоваться в двух различ-

ных ситуациях:

- в качестве вопроса к системе Турбо Пролог (внешняя

цель);

- в правой части правила (внутренняя цель), например:

grandfather(X,B) if father(X,Y) and father(Y,B)

Если father (Х, У) - внешняя цель, то Турбо Пролог, как

обычно, будет выдавать все возможные решения:

X=....,Y=....

.... solutions

Если же father (Х, У) - внутренняя цель, то, как только

она будет удовлетворена, Турбо Пролог перейдет к следующей

подцели и выведет на экран только одно решение. Тем не менее,

предикат everybody (все) в программе 15 пользуется предикатом

fail, что приводит к нарушению обычного механизма.

В результате обработки предиката everybody выполнение

программ приводит к более ясным и наглядным ответам. Сравните

между собой ответы на две следующие цели:

Цель: father(X,Y)

X=leonhard,Y=katherine

X=carl,Y=jason

X=carl,Y=marilyn

3 solutions

Цель: everybody

leonhard is katherine's father

carl is jason's father

carl is marilyn's father

No solution

Чтобы получать последующие решения для подцели father (Х,

У), предикат everybody пользуется механизмом возврата. При

этом делается попытка удовлетворить правую часть этого преди-

ката:

father(X,Y) and write(X," is ",Y,"'s father\n") and fail.

Содержащиеся здесь подцели следует обрабатывать слева направо.

Первая подцель

father(X,Y)

может быть удовлетворена, если Х = leonard (Леонард), а У =

katherine (Кэтрин). Поэтому Турбо Пролог переходит к следую-

щей подцели - к стандартному предикату write. Он выполняет

стоящую перед ним задачу, осуществляя вывод нескольких значе-

ний, после чего начинается обработка последней подцели -

стандартного предиката fail.

Предикат fail нельзя удовлетворить ни при каких обстоя-

тельствах, поэтому Турбо Пролог вынужден сделать возврат.

Предикат write удовлетворить заново нельзя (иными словами,

невозможно предложить новые решения), поэтому Турбо Пролог

должен сделать возврат вновь, возвращаясь тем самым к первой

подцели.

Теперь обнаруживается новое решение, а именно: Х = carl

(Карл), У = sam (Сэм). После этого Турбо Пролог может перейти

к следующей подцели, в связи с чем будет осуществлен вывод

соответствующих значений, и, наконец, будет достигнута пос-

ледняя подцель - предикат fail, который снова приведет к воз-

врату, и так далее.

Упражнение. Набейте программу 15 и выполните следующие

две цели:

father(X,Y).

everybody.

Почему решения в последнем случае завершаются словом False

(ложь)? Чтобы догадаться до правильного ответа, введите пред-

ложение

everybody

в качестве второго предложения для предиката everybody, и

выполните цель заново.

Предотвращение возврата, элемент отмены

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

В Турбо Прологе присутствует элемент, который при опреде-

ленных обстоятельствах предотвращает возврат. Такой элемент

называется отменой и записывается в виде восклицательного

знака (!). Его действие очень простое:

- осуществление возврата после отмены невозможно.

Отмена имеет два основных применения.

1. Когда вам заранее известно, что определенные возмож-

ности никогда не приведут к осмысленным решениям, поэтому де-

лать возвраты к таким возможностям было бы потерей времени и

ресурсов памяти. Если в такой ситуации результирующая прог-

рамма будет пользоваться отменой, то она будет выполняться

быстрее, расходуя при этом меньший объем памяти.

2. Когда отмена диктуется логикой программы.

В последующих примерах мы будем пользоваться некоторыми

схематическими правилами Турбо Пролога r1, r2 и r3; все они

описывают один и тот же предикат r, а также некоторые подцели

a, b, c и т.д.

Использование отмены для предотвращения возврата к преды-

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

дущей подцели правила

~~~~~~~~~~~~~~~~~~~~~

Таким путем Турбо Прологу можно сообщить, что нас удов-

летворяет первое же решение для подцелей a и b. В качестве

конкретного примера рассмотрим программу 16. Она основана на

соображении, что два человека могут нравиться друг другу, ес-

ли они имеют хотя бы один общий интерес.

/* Программа 16 */

Domains

name, interest = symbol

interests = interest*

Predicates

findpairs

person(name,sex,interest)

member(interest,interest)

common_interest(interest,interest,interest)

Clauses

findpairs if person(Man,m,ILIST1) and

person(Woman,f,ILIST2) and

common_interest(ILIST1,ILIST2,_) and

write(Man," night like ",Woman) and nl and

fail.

findpairs:-write("-----------end of the list-----").

common_interest(IL1,IL2,X) if

member(X,Il1) and member(X,Il2) and !.

person(tom,m,[trvel,books,basebell]).

person(mary,f,[wine,books,swimming]).

member(X,[X|_]).

member(X,[_|L]) if member(X,L).

Использование отмены в предикате (об-

щий_интерес) служит причиной того, что этот предикат отыски-

вает только один общий интерес. Если бы отмена не использова-

лась, то одни и те же имена выводились бы на экран много раз

при условии наличия у людей (persons) многих общих интересов.

Использование отмены для предотвращения возврата к следу-

ющему предложению

Рассмотрим способ, которым можно сообщить Турбо Прологу,

что он выбрал правильное предложение для данного предиката.

Например, в схеме

r1 if ! and a and b and c.

r2 if ! and d.

r3 if c.

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

ного из предложений r1, r2 или r3. (Напомним, что r1, r2 и

r3 - это предложения для одного и того же предиката r.)

Наш следующий пример основывается на программе 9 (глава

4), в которой был определен предикат для факториала, причем

отмена там не использовалась:

factorial(1,1).

factorial(N,Res) if

N>1 and

N1=N-1 and

factorial(N1,Temp) and

Res=N*Temp.

Условие N > 1 было необходимо, поскольку иначе второе предло-

жение может быть удовлетворено при N = 1. Без этого условия

первый аргумент предиката factorial мог стать отрицательным и

программа вошла бы в бесконечный цикл (или исполнялась бы до

тех пор, пока не будет исчерпана память).

Однако, учитывая возможность отмены, мы можем построить

1=N-1 and

factorial(N1,Temp) and

Res=N*Temp.

Услпвие N > 1 было необходимо, посколфку инач┼ второе предло-

жение может быть удовлетворено при N ? 1. Без этого условия

первый аргумент предиката factorial мог стать отрицательным и

програм ╧

╧

Руководство к пользованию TURBO PROLOG

Подождите немного. Документ загружается.