Непейвода Н.Н., Скопин И.Н. Основания программирования

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

13.2. УНИФИКАЦИЯ

755

Пример описаний операций показывает, что даже локальное использо-

вание различения конкретно- и абстрактно-синтаксических представлений

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

PROLOG

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

ном синтаксисе их нет. Заодно автоматически устраняются многие тонкие

вопросы, связанные, в частности, с возможностью

PROLOG

-программы пре-

образовывать саму себя. Смотри упр. 3.

13.2.3. Управление исполнением программы

Рассмотрим, как исполняется программа на языке

PROLOG

. В программе

может быть один целевой дизъюнкт, не имеющий головной части. Он начи-

нается с функтора

или

. В программе, транслируемой и исполняемой в

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

с терминала в режиме диалога — второй. Разница между ними проявляется

лишь в режиме диалога. Второй вариант цели позволяет пользователю после

нахождения одного из решений продолжить выполнение программы для по-

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

программа находит первое решение и останавливается.

Цель состоит из последовательности термов, разделенных запятыми. Эта

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

называется запросом. Переменные, входящие в запрос, носят особый статус.

Их значения в ходе последовательных унификаций накапливаются в скрытой

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

стве ответа на запрос. В каждый момент рассматривается первый из термов

данной последовательности. Если его детерминатив не является встроенной

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

предложение, голова которого унифицируется с этим термом. При этом пре-

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

торых совпадает с детерминативом первого терма. Если таких предложений

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

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

начиная с первого.

Полученная унифицирующая подстановка применяется ко всем термам

в поле зрения и к хвосту успешно унифицированного предложения. После

этого хвост заменяет унифицированную голову, и выполнение возобновляет-

ся. Исполнение считается успешным, если на некотором шаге цель исчезает.

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

756

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

термов не найдется унифицируемого с ним предложения.

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

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

менные дожили в поле зрения до соответствующей унификации. Если пе-

ременная уже получила постоянное значение либо значение, в котором она

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

как новые. Таким образом, конкретные имена переменных имеют значение

лишь внутри одного предложения (точно так же, как в

Рефале

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

следней из точек возврата (происходит откат), и испытывается следующее

по порядку предложение с тем же детерминативом. Если таких предложе-

ний больше не осталось, то происходит откат к следующей точке возврата, и

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

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

Стандартным ответом программы на запрос служит

Yes

, если программа

закончилась удачно, и

, если она закончилась неудачно. При удаче выво-

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

Так, например, если программа и ее база данных имеют вид

Программа 13.2.1

greater(X,Y):-greater1(X,Y).

greater(X,Y):-greater1(Z,Y),greater(X,Z).

greater1(X,f(X)).

estimation(X,Y):-greater(X,Y),known(Y).

known(f(f(f(f(a))))).

unknown(a).

unknown(b).

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

?-unknown(Y),estimation(Y,X).

будет

Y=a

X=(f(f(f(f(a))))

Yes

а при попытке ответа на запрос

?-estimation(b,X).

13.2. УНИФИКАЦИЯ

757

программа зациклится.

Насколько коварны вроде бы невинные предположения, сделанные в язы-

ке

PROLOG

, видно из того, что при логически эквивалентной переформули-

ровке одного из предложений программы

estimation(X,Y):-known(Y),greater(X,Y).

программа успешно ответит на второй запрос

Еще более ‘впечатляющий’ пример рассмотрен в упражнении 1.

Рассмотренные до сих пор средства языка

PROLOG

не дают возможности

сформулировать отрицание. Впрочем, отрицание и не может присутствовать

в хорновых формулах, его наличие разрушает все их хорошие свойства, по-

служившие основой для модели вычислений

PROLOG

. Но практически оно

нужно,и поэтому в языке

PROLOG

введен его суррогат. Этот суррогат заодно

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

Если в цели встал на первое место атом

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

то он успешно унифицируется и уничтожает последнюю точку возврата. Он

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

ха подцели. Рассмотрим, как с помощью

и списков программируется поиск

пути в лабиринте (и даже в произвольном ориентированном графе). Преди-

кат-операция

успешно унифицируется, если первый его аргумент является

элементом списка, который стоит на месте второго аргумента.

Программа 13.2.2 Статический лабиринт

way(X,X,[X]).

way(X,Y,[Y|Z]):-connect(U,Y), nomember(Y,Z),way(X,U,Z).

way(X,Y,[Y|Z]):-connect(U,Y), way(X,U,Z).

nomember(Y,Z):-member(Y,Z),!,fail.

nomember(Y,Z).

connect(begin,1).

connect(1,begin).

connect(1,2).

connect(2,3).

Если Вы проверяете данные примеры на системе

SICS Prolog

, то некоторые из них могут

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

Для получения описанных эффектов требуется переключить систему в режим совместимо-

сти со стандартом.

758

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

connect(3,1).

connect(3,4).

connect(4,end).

В ответ на запрос

?-way(begin,end,X).

программа выдаст

X = [end, 4, 3, 2, 1, begin]

Yes

Можно не определять

nomember

, а прямо написать предложение

way(X,Y,[Y|Z]):-connect(U,Y),not (member(Y,Z)),way(X,U,Z).

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

PROLOG

программу в программу с традиционным управлением, оставив из специфи-

ки языка лишь операцию унификации.

Как правило, при такой трансфор-

мации теряются главные преимущества языка

PROLOG

, но зато сохраняются

все его недостатки.

Прагматические соглашения о порядке выполнения действий в програм-

ме привели к тому, что, если мы запишем в форме языка

PROLOG

тривиаль-

ную тавтологию

A:-A.

и этот оператор

выполнится, то программа зациклится. И по этой причине,

и по причине ошибки в унификации, предложения языка

PROLOG

, сохранив

внешнюю форму логических, никакого отношения к логике уже не имеют.

Конечно же,несообразности были использованы и в положительном смы-

сле. Например, рассмотрим следующее определение.

repeat.

repeat:-repeat.

Если вставить теперь цель

repeat

в раскрытие другой цели, и позаботить-

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

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

PROLOG

и отладить свою программу. Когда он узнал о

, он облегченно вздохнул и перепи-

сал свою программу таким образом, что она стала изоморфной программе в обычном языке

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

Здесь мы не оговорились: в данном случае предложения лучше трактовать как операторы,

поскольку как утверждения их в данном случае рассматривать невозможно.

13.2. УНИФИКАЦИЯ

759

неудачей, а после удачи поставить

, то эти подцели будут повторяться вплоть

до удачи, и их побочные эффекты будут исполняться в цикле.

Перебор вариантов языка

PROLOG

— при всех своих недостатках доста-

точно удачное частное решение, как промоделировать недетерминированные

алгоритмы в программе.

Недетерминированную модель вычислений, соответствующую

PROLOG

можно определить в общем виде следующим образом:

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

вий выбора вариантов — точки недетерминированного разветвления;

2. Вычислительный процесс выбирает в такой точке любое из возможных

продолжений;

3. Некоторые из возможных продолжений объявляются тупиковыми, или

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

к заранее определенной цели. Принципиально, что тупик продолжения

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

4. Успешным вычислением называется такая последовательность выбира-

емых продолжений в каждой точке недетерминированного разветвле-

ния, которая приводит процесс к цели (т. е. ни одно из выбранных про-

должений не является тупиком).

Недетерминированным достижением цели называется существование успеш-

ного вычисления.Иными словами,если какая-то из последовательностей про-

должений приводит к цели, то цель процесса считается достигнутой. Неде-

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

композиции решаемой задачи, когда программист просто откладывает ‘на

потом’ вопрос, как будет организован перебор вариантов. Не всегда это ра-

ботает, но когда работает, это часто удобно (см. п. 10.2.3).

Есть теорема, доказывающая, что в принципе недетерминированный ко-

нечный автомат всегда можно преобразовать в детерминированный. Идея

преобразования — склейка состояний, как показано на рис. 13.3. при этом,

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

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

Именно так с самого начала поступили в языке

PROLOG

. Греха и беды в этом

нет (особенно в то время, когда создавался язык: идея совместности и неде-

терминированности как положительного фактора была только что осознана,

760

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

…

S12

…

Некоторые из них совпадают

…

S2x

S2z

…

S3x

S3c

…

S2x

S2z

S23

S3c

Рис. 13.3. Преобразование недетерминированного поиска в детерминирован-

ный

13.2. УНИФИКАЦИЯ

761

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

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

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

вать новизну и в остальных пунктах работать как можно более традицион-

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

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

как принципиальные новации.

Теорема про детерминирование конечного автомата дает лишь уверен-

ность в существовании успешного вычисления. Но она не дает никаких хоро-

ших оценок изменения сложности вычислений при детерминировании поис-

ка. Другой негативный аспект: даже если успешное вычисление существует,

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

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

маемы. Поэтому часто удобнее обработку описывать как недетерминирован-

ную, поручая решение задачи детерминирования, или, что то же, перебора

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

чила языковые формы в языке

PLANNER

построен чисто прагма-

тически на базе

FORTRAN

LISP

для решения задач искусственного интел-

лекта. Не привязываясь к особенностям синтаксиса этого языка, детермини-

рование-перебор в нем можно описать следующей схемой:

backtracking: non-deterministic case

<вариант1>;

...

<вариантk>

end-case

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

мо (где распознаются тупики), операторы

return-back

. Но структурная вло-

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

поэтому, а также потому, что в то время она еще не была идолизирована, в

PLANNER

использована переключательная схема:

backtracking: go to M1, ..., Mk

Конечно же,

PROLOG

, отделенный от

PLANNER

всего несколькими го-

дами, реализовал эту идею несравненно лучше. Здесь сработал еще и тот

эффект, что

PLANNER

не успел декларировать блестящие успехи

и осуще-

Насколько они реальны, в подобных случаях уже второй вопрос. Главное: успеть прокри-

чать о своем успехе и загадить экологическую нишу.

762

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

ствить захват экологической ниши.

13.2.4. Динамическое пополнение и порождение программы

Поскольку структура программы и структура поля зрения практически

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

PROLOG

программ. Кроме этого высокоуровневого соображения, есть и прагматиче-

ское, которое можно извлечь из нашей программы 13.2.2. В нее мы были вы-

нуждены записать и определение лабиринта. Конечно же, можно было бы

прочитать с помощью встроенной функции

read

определение лабиринта и

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

ка

PROLOG

, не избавившись при этом ни от одного его недостатка. Гораздо

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

Для этой цели в

PROLOG

был введен встроенный предикат

consult(ﬁle[.pl])

Он читает предложения и факты из файла и помещает их в конец програм-

мы, тем самым оставляя в неприкосновенности ранее данные определения

предикатов. С его использованием наша программа может быть переписана

в следующем виде.

Программа 13.2.3 Вводимый лабиринт

way0(X,Y,Z):-consult(labyr),way(X,Y,Z).

way(X,X,[X]).

way(X,Y,[Y|Z]):-connect(U,Y), not member(Y,Z),way(X,U,Z).

way(X,Y,[Y|Z]):-connect(U,Y), way(X,U,Z).

Пример файла

labyr.pl

connect(begin,1).

connect(1,begin).

connect(1,2).

connect(2,3).

connect(3,1).

connect(3,4).

connect(4,end).

Сравним программу 13.2.3 с теми программами, которые были рассмо-

трены при решениии той же задачи при помощи рекурсий в § 11.4. Эта про-

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

языка

PROLOG

,которые все равно не дают возможность решить задачу столь

13.2. УНИФИКАЦИЯ

763

же эффективно, как это делается на традиционном языке. В этом принципи-

альная разница языков

PROLOG

Рефал

делает символьные пре-

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

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

стилей на всех уровнях: и для создания прототипа программы, и для написа-

ния надпрограммы, и для написания подпрограммы.

PROLOG

приспособлен

для описания идеи решения, но отвратительно работает уже на уровне про-

тотипирования.

Первоначально предикат

consult

предназначался для ввода фактов, но за-

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

ных предложений. Поэтому был определен предикат

reconsult(ﬁle.pl)

, кото-

рый помещает введенные предложения и факты в начало программы, тем са-

мым заменяя данные в программе определения предикатов на содержащиеся

во внешней базе знаний.

Для динамического порождения фактов и предложений имеются функ-

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

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

предложениями. Из метапредикатов важнее всего два, перечисленных ниже.

Метапредикат

assert(P:-P1,...,Pn)

помещает свой аргумент в

PROLOG

программу. Имеются несколько его вариантов, помещающие новое предло-

жение или факт в начало или в конец программы. Метапредикат

retract(P:-

P1,...,Pn)

, наоборот, удаляет из программы предложение или факт, унифи-

цируемый с его аргументом.

С их помощью можно, в частности, сымитировать все предложенные на-

ми алгоритмы работы с лабиринтом, но при этом программа полностью поте-

ряет ясность структуры и станет крайне трудной для отладки и модификаций,

а эффективности, сравнимой с традиционным языком, достичь все равно не

удастся.

Многие из реализаций языка

PROLOG

включают пакет прогонки, позво-

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

PROLOG

-программы.

Как руководство по программированию на языке

PROLOG

можно исполь-

зовать, скажем, книгу [12].

Поскольку в 1996 г. принят стандарт языка

PROLOG

[83], мы использо-

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

Вариант сентенциального программирования, базирующийся на возвра-

тах и унификации, отлично сочетается с идеей машины потоков данных. По-

этому японцы попытались использовать его в своем проекте ЭВМ 5-го поко-

ления. Провал данного проекта надолго дискредитировал данное направле-

764

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

ние, но к нему придется вернуться в будущем на другой технической и, ви-

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

Тем более это неизбежно, потому что концепция унификации и возвра-

тов после неудач исключительно хорошо подходит для выражения ∨-парал-

лелизма (см. Приложение). Более того, уже имеются системы (в частности,

Muse

), реализующие этот вариант параллелизма в языке

PROLOG

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

рованы даже на разные классы параллельных вычислений. По аналогии мож-

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

реализации, принципиально отличные от общепринятых и имеющие другой

потенциал развития, если бы не сработал закон экологической ниши. Авто-

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

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

выразительно и эффективно исполняемые и на последовательных системах,

требуют другого варианта стиля программирования и другой методологии

с самого начала.

Алгол 68

сделал первый шаг в этом направлении, а затем

движение полностью прекратилось.

Развитию языка

PROLOG

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

ка к конкретной модели вычислений, которая была зафиксирована слишком

рано, в погоне за мнимой эффективностью. Фатально совершенно извращен-

ное понимание его места и роли. Значительную лепту вносит сюда монопо-

лизированный им и полностью извращающий суть дела термин ‘Логическое

прогораммирование’.

PROLOG

великолепная заготовка для языка моделиро-

вания идей.

Рассмотрим, что ему мешает в реальности стать таким языком. Как мы

уже неоднократно видели, главное препятствие — лишние возможности. В

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

провоцируют программиста к операционному мышлению и хакерскому сти-

лю. Так, в задаче о лабиринте, было бы естественно не зацикливание ис-

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

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

не хватает условий, что возможны такие-то варианты ограничений, делаю-

щие программу корректной.

Эклектичность

PROLOG

’а обусловлена двумя обстоятельствами. Прежде

всего, это установка на то, что логика Хорна достаточна для специфициро-

вания вычислений, поскольку, как было доказано, она эквивалентна маши-

не Тьюринга. С этим можно было бы согласиться, если бы решения реаль-

ных задач, которые апеллируют к базам данных-фактов и должны решать-