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

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

13.1. КОНКРЕТИЗАЦИЯ

745

стандартом, объекты были отброшены, зато последовательно была проведе-

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

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

тельные условия.

Из других существующих версий языка стоит отметить

Рефал-6

Ре-

фал+

[28], которые развивают одну и ту же линию. В реализации

Рефал+

отошли от представления, принятого в [69], с тем, чтобы воспользоваться

современными алгоритмами сборки мусора. Вместо стеков закопанных зна-

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

чение. В частности, такие объекты используются для описания графического

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

Рефале

. Далее,

имеется возможность объявить функцию откатной, и пытаться при невоз-

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

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

управления в языке

Рефал

.Из находок авторов

Рефал+

,помимо новой струк-

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

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

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

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

шой выигрыш в выразительности).

Наиболее заметным недостатком новых версий языка

Рефал

явилось от-

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

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

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

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

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

Стоит заметить, что нынешний язык

Рефал

находится в мягком концеп-

туальном противоречии со столь блестяще реализованной в нем же идеей ди-

намического вычисления программ. Решение исполнять ту функциональную

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

при создании

Рефала

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

аппарат метапреобразований. Аналогично, необходимо заметить, что

Рефал

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

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

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

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

чае ощущаемым наиболее остро.

746

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

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

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

‘прагматическое’ решение. Выигрыши от прагматизма будут минимальны-

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

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

ми.

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

ального программирования, поскольку

Рефал

великолепно подходит для &-

параллелизма (см. § A.7). Подстановки значений переменных в результиру-

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

в принципе можно было бы даже в этом варианте

Рефала

вычислять различ-

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

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

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

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

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

де ее составления в языке подготовлен.

Из литературы по языку

Рефал

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

[90, 5, 8], первое из которых имеется в общедоступном русском переводе, в

частности, на сайте .

Стоит заметить, что сентенциальное программирование, и особенно его

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

лепно сочетается с идеей ассоциативной памяти (см. стр. 21), и здесь воз-

можен прорыв одновременно на аппаратном и программном уровнях.

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

13.2.1. Общие концепции

Язык логического программирования

PROLOG

представляет собой дру-

гую модель сентенциального программирования, несовместимую

с моде-

лью

Рефала

Британско-канадская группа, создававшая

PROLOG

, рассмотрев ортого-

нальный

Рефал

у подход

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

Это — глубочайший теоретический результат и одно из редких прямых предупреждений,

сделанных теорией практике. Но даже прямые предупреждения, как правило, игнорируются

практиками, многие из которых не понимают самого понятия алгоритмической неразреши-

мости.

Конечно же, они не имели никаких сведений о

Рефал

е и работали совершенно неза-

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

747

тодологически-теоретическим анализом и неадекватным названием. В этом

проявилась коренная разница русской и англо-американской

школ науки:

В. Ф. Турчин проделал адекватный анализ, не устаревший за 30 лет, но он

не стремился к общепонятности и слишком большой популяризации (может

быть, потому, что ему не нужно было выбивать гранты). Создатели

PROLOG

с самого начала в значительной мере использовали теорию и методологию

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

носимые для его освящения. Тем самым теоретическая база сразу же оказа-

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

концептуального единства. Хуже другое. Это помешало осознанию реальных

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

тиворечили мифам и саморекламе.

PROLOG

вдохновлялся ограничением классического исчисления преди-

катов, предложенным Хорном. Как известно (см., например, книгу [63] и

Приложения), в классической логике в любой достаточно богатой теории

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

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

юнкциями импликаций вида

∀x

, . . . , x

∃y

, . . . , y

. . . (A

& ···&A

⇒ B) (13.6)

где каждая составляющая является элементарной формулой, и само доказан-

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

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

мулировать и нетривиально использовать что-либо похожее на A∨¬A. Такие

формулы называются хорновыми.

Далее, от лишних кванторов можно избавиться при помощи сколемиза-

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

которой являются все переменные, связанные ранее стоящими кванторами

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

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

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

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

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

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

законы развития науки и вообще эволюционирующих систем).

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

во на ‘нагло-американской’.

748

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

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

формул (хорновы импликации):

∀x

, . . . , x

& ···&A

⇒ B) (13.7)

Применив к последней формуле преобразование, выполненное лишь в клас-

сической логике, мы приходим к хорновым дизъюнктам:

∀x

, . . . , x

(¬A

∨ ··· ∨ ¬A

∨ B) (13.8)

Именно от последней формы представления хорновых утверждений получи-

ла имя основная структура данных языка

PROLOG

. Но тот факт, что импли-

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

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

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

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

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

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

дом резолюций [79]. Этот метод поставил три идеи (унификация, стандарти-

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

ализацией которых явился исходный

PROLOG

. Но находки языка

PROLOG

не исчерпываются реализацией идей, взятых из теории. Они внесли суще-

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

Одной из сильнейших сторон метода резолюций явился алгоритм унифи-

кации выражений. Два выражения называются унифицируемыми, если они

могут быть приведены к одному и тому же виду подстановкой значений вме-

сто свободных переменных. В методе резолюций было показано, что для вы-

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

ходящий для двух выражений унифицирующую подстановку либо обосно-

вывающий, что такой подстановки нет.

Пример 13.2.1. Две последовательности выражений

f(x, ϕ(x, χ(y), a)) g(z, x) h(ϑ(u))

f(ω(b), ϕ(y, z, w)) u h(q)

(13.9)

Одновременно данное направление нанесло и существенный вред этой теории и методо-

логии, который был бы еще глубже, если бы у

PROLOG

с самого начала не было бы друга-

соперника

Рефала

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

749

где a, b — константы, а латинские буквы из конца алфавита — переменные,

унифицируются в

f(ω(b), ϕ(ω(b), χ(ω(b)), a)) g(χ(ω(b)), ω(b)) h(ϑ(g(χ(ω(b)), ω(b))))

(13.10)

подстановкой

x ← ω(b), y ← ω(b), u ← g(χ(ω(b)), ω(b)),

w ← a, z ← χ(ω(b)), q ← ϑ(g(χ(ω(b)), ω(b)))

(13.11)

А в следующей формуле

g(x) g(z) f(x, a)

h(y) g(ϕ(z)) f(b, x)

(13.12)

никакие два соответственных выражения унифицированы быть не могут.

Конец примера 13.2.1.

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

ная операция, как и конкретизация в

Рефале

. Но направления унификации

и конкретизации ортогональны.

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

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

хическая структура сочетается с линейной структурой внутри одного

уровня иерархии, то при унификации в

PROLOG

и в логике все выраже-

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

лишь иерархическая структура.

• Если конкретизация не заглядывает внутрь иерархии глубже, чем это

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

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

димо.

• Если при конкретизации переменные локальны, и их значения не влия-

ют на интерпретацию остальной области памяти, то при конкретизации

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

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

тивной части.

750

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

• Если при конкретизации в ходе установления значений переменных

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

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

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

та означает неудачу всей попытки унификации.

Заметим, что логический алгоритм унификации обладает свойством ча-

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

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

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

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

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

PROLOG

из специализи-

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

неудач.Успешно произведенная унификация (точно так же,как успешно про-

изведенное отождествление в языке

Рефал

) является разрешением выпол-

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

ищется следующая унификация. Если на некотором шаге унификация невоз-

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

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

Мы теперь запрещаем предыдущую успешную модификацию и пытаемся

испробовать другие возможности. Такие возвраты могут происходить один

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

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

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

Рефал

. В

PROLOG

неудача глобальна, но

исправима, а в

Рефале

локальна, но фатальна.

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

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

лись после подчиненных. Авторам неизвестно ни одно использование этого естественного

и многообещающего обобщения алгоритма унификации.

В конкретной первой реализации языка

PROLOG

, основные особенности которой ста-

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

соответственно, в реализации алгоритма унификации, которая, в частности, разрушает это

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

более общую конкретизирующую подстановку. Эта ошибка несущественна, она не влияет

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

ных термов, и некоторые реализаторы языка

PROLOG

с гордостью пишут, что они умеют

печатать и показывать на экране даже такие термы.

Желающие в качестве упражнения выловить ошибку самостоятельно, сравните алгорит-

мы унификации, описанные в книге [79] и в [41].

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

751

И, наконец, последняя находка метода резолюций, перенесенная в про-

граммирование, это стандартизация цели. Целью доказательства в методе

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

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

сурду). Точно так же и в языке

PROLOG

: успешное исполнение программы

означает стирание поля зрения.

Собственно хорновские формулы обладают еще одним важным свойством,

которое также послужило основой некоторых идей

PROLOG

-машины. Для

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

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

вод из исходной формулы и наследника цели. Никаких сочетаний исходных

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

бой (чего в общем случае не избежать) делать в принципе не нужно, хотя это

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

циально).

13.2.2. Поле зрения, поле памяти и PROLOG-программа

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

PROLOG

. Все

данные языка

PROLOG

являются термами. Термы построены из атомов (ко-

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

имена и числа) при помощи функциональных символов, которые также явля-

ются атомами (а именно, именами), и называются функторами. Среди функ-

торов выделяются детерминативы. Детерминативы в реализации делятся на

предикаты и встроенные функции (функции). Функции обычно используют-

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

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

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

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

могут оставаться неописанными.

В конкретном синтаксисе переменные языка — имена, состоящие из букв

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

. Пере-

менная

называется анонимной переменной и считается различной во всех

своих вхождениях.

Константы языка

PROLOG

в конкретном синтаксисе — имена (иденти-

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

Внутри языка они называются атомами

752

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

специальных символов типа <,=.$),символы и числа (символы отождествля-

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

вательность символов может быть сделана единой константой, например:

’C:\”SICS Prolog”\program.pl’

В конкретном синтаксисе имена функторов являются константами,не явля-

ющимися строкой символов в кавычках. Они различаются арностью, таким

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

Некоторые функции могут быть описаны как операции (инфиксные, пре-

фиксные либо постфиксные), но это рассматривается лишь как синтаксиче-

ский сахар, и в принципе переводится в стандартную форму

function(arg_1,..., arg_n)

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

дополнительные ограничения на аргументы

. В частности, можно указать,

что аргументом может служить имя файла, атом, переменная и т. п.

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

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

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

вательно достигаемые цели”), либо символами |, в этом случае цели “альтер-

нативны”. Наиболее важным и классическим случаем является случай по-

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

семантика и альтернативных целей

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

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

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

И, наконец, в поле данных помещается сама

PROLOG

-программа, кото-

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

самой программы, но обычно разделяемые при использовании внешней па-

мяти: база данных и база знаний. Более общий вид имеет база знаний.

База знаний состоит из предложений (клауз). Каждое предложение имеет

вид, подобный

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

ные программистом.

Мы сознательно отказались от сопоставления двух видов целей в

PROLOG

с конъюнкци-

ей и дизъюнкцией, поскольку их семантика принципиально отличается от семантики этих

логических связок.

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

753

grandfather(X,Z) :- parent(X,Y), father(Y,Z).

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

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

но достигаемые цели.

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

группируются вместе:

parent(X,Y) :- mother(X,Y).

parent(X,Y) :- father(X,Y).

Порядок предложений существенен.

База данных состоит из фактов.Факты могут выражаться в одном из трех

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

но приводящее к успеху (успех — это стирание целей). Поэтому он может

быть записан:

father(ivan,vasilij):-true.

Здесь мы встретились с одной из двух стандартных целей.

true

обозначает

очевидную удачу, а

fail

— очевидную неудачу.

Во-вторых, специально для фактов имеется скоропись:

mother(maria,soﬁa).

В принципе все остальные структуры языка

PROLOG

выражаются через

элементарные. Но некоторые из них прагматически настолько важны, что по-

лучили отдельное оформление и более эффективную реализацию. Это пре-

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

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

[]

применением двухместного

функтора

.(head,tail)

. Но выстроенная в стандартном порядке композиция

.(a,.(b,..., .(z,[])...))

понимается как линейный список и обозначается

[a,b,...,z]

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

имеется стандартная операция

[t,u|L]

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

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

"Ну, получили то, что искали? Ответьте y или n."

754

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

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

PROLOG

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

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

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

PROLOG

:- op(1200,xfx,’:-’).

:- op(1200,fx, [’:-’,’?-’]).

:- op(1000,xfy,’,’).

:- op(700, xfx,[=,is,<,=<,==]).

:- op(500, yfx,[+,-]).

:- op(500, fx, [+,-,not]).

:- op(400, yfx,[*,/,div]).

Первый аргумент в этих описаниях — приоритет операции. Он может

быть от 1 до 1500. Второй аргумент — шаблон операции.

обозначает выра-

жение с приоритетом, строго меньшим приоритета операции,

—выражение

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

— поло-

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

шаблон

yfx

для операции

означает, что

X-Y-Z

понимается как

(X-Y)-Z

, ша-

блон

xfy

для запятой означает, что

t,u,r

понимается как

t,(u,r)

, шаблон

xfx

для

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

без дополнительных скобок. Операции с меньшими приоритетами связыва-

ют сильнее. Один и тот же атом может быть определен и как унарная, и как

бинарная операция.

Внимание!

То, что некоторый функтор определен, как операция, не зна-

чит, что он вычисляется. Это просто изменение конкретно-син-

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

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

нюю или внешнюю функцию.При этом совершенно необязатель-

но делать его операцией.

В частности, бинарная операция

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

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

числяет это выражение. Даже выражение вида

1+2

остается в таком же виде,

пока оно не попадет во второй аргумент