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

Сентенциальное программирование: PROLOG

Разбить на страницы
Показывать лекцию целиком

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

Язык логического программирования PROLOG представляет собой одну из моделей сентенциального программирования. Мы используем лишь те возможности языка PROLOG, которые согласуются с принятым в 1996 г. стандартом . Как руководство по программированию на языке PROLOG можно использовать, скажем, книгу . В ней содержится наименьшее число недочетов и откровенных ошибок, а также наибольшее число практических советов по сравнению с другими известными автору пособиями.

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

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

Второй находкой, перенесенной авторами языка PROLOG из специализированных программ (для логики и искусственного интеллекта) в языки программирования, стала система обработки неудач. Успешно произведенная унификация является лишь разрешением выполнить некоторое действие. После проверки других условий, возможно, мы будем вынуждены вернуться и выбрать другой вариант.

Третья находка языка PROLOG, перенесенная в программирование из метода резолюций, — это стандартизация цели. Целью доказательства в методе резолюций всегда является получение пустого дизъюнкта, то есть стирание доказываемого выражения (с логической точки зрения, приведение его к абсурду). Точно так же и в языке PROLOG: успешное исполнение программы означает стирание поля зрения.

Четвертая находка создателей языка PROLOG взята из ограничения классической логики. Хорновские формулы

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

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

Когда рассматривается исполнение программы в нетрадиционном языке (например, PROLOG -программы), то естественно воспринимать конкретную реализацию языка как новую машину нетрадиционной архитектуры с высокоуровневыми командами (в данном случае как PROLOG -машину).

Данные, используемые PROLOG -машиной, размещаются во всех частях поля памяти и имеют общую структуру.

Рассмотрим на уровне абстрактного синтаксиса структуру данных, обрабатываемых языком PROLOG. Все данные языка PROLOG являются термами. Термы построены из атомов при помощи функциональных символов. Атомами могут быть переменные и константы, в свою очередь, делящиеся на имена и числа. Функциональные символы являются именами и называются функторами. Среди функторов выделяются детерминативы, которые в реализации делятся на предикаты и встроенные функции (функции обычно используются внутри выражений, а предикаты являются основными единицами управления и обычно используются вне скобок как основной функциональный символ выражения). Детерминативы должны быть описаны в программе, а остальные функторы рассматриваются просто как структурные единицы и могут оставаться неописанными.

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

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

И, наконец, в поле памяти помещается сама PROLOG -программа, которая естественно структурируется на две части, нередко перемешанные в тексте самой программы, но обычно разделяемые при использовании внешней памяти: база данных и база знаний.

База данных состоит из фактов, представляющих собой предикат, примененный к термам.

База знаний состоит из предложений (клауз). Каждое предложение имеет вид, подобный хорновской формуле

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

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

В любой момент исполнения программы база данных и база знаний могут быть модифицированы.

Теперь перейдем к конкретному представлению данных.

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

Константы языка PROLOGВнутри языка они называются атомами. в конкретном синтаксисе делятся на имена (идентификаторы, начинающиеся с маленькой буквы либо совокупность нескольких специальных символов типа <, =, $ ), символы и числа (символы отождествляются с целыми числами, являющимися их кодами). Произвольная последовательность символов может быть сделана единой константой, например:

'C:\"SICS Prolog"\program.pl'.

Любое константное имя может служить функтором. Функторы различаются арностью (т. е. количеством аргументов), таким образом, может быть сразу несколько функторов с одним и тем же именем. Например, write(a(1)) и write(a(1),file1) используют различные функторы. Некоторые функции могут быть описаны как операции (инфиксные, префиксные либо постфиксные). В отличие от почти всех остальных языков, операции рассматриваются лишь как сокращение для выразительности. Например, x+y означает в точности то же, что и +(x,y).

Для некоторых из предопределенных в системе функций и предикатов имеются дополнительные ограничения на аргументыВ части реализаций эти ограничения могут распространяться и на функции, определенные программистом.. Например, в функции load(f) f должно быть именем файла.

Поле зрения (цель), содержащее непосредственно обрабатываемые программой данные, состоит из последовательности термов, разделенных либо запятыми (в этом случае они понимаются как "последовательно достигаемые подцели"), либо символами |, в этом случае подцели "альтернативны".Наиболее важным и классическим является случай последовательно достигаемых подцелей, через который определяется и семантика альтернативных подцелейМы сознательно отказались от сопоставления двух видов целей в PROLOG с конъюнкцией и дизъюнкцией, поскольку их семантика принципиально отличается от семантики этих логических связок..

В конкретном представлении предложение, например,

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 — очевидную неудачу.

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

father(ivan,vasilij).

В принципе, все остальные структуры языка PROLOG выражаются через элементарные, определенные выше. Но некоторые из структур прагматически настолько важны, что получили отдельное оформление и более эффективную реализацию. Это, прежде всего, списки и строки. Список, в принципе, определяется как терм, построенный из других термов и пустого списка [] применением двухместного функтора .(head,tail). Выстроенная в стандартном порядке композиция

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

понимается как линейный список и обозначается [a,b,. . . ,z].

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

[t,u|L].

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

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

Заслуживает упоминания механизм введения новых операций в язык 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. Второй аргумент — шаблон операции; x обозначает выражение с приоритетом, строго меньшим приоритета операции; y — выражение с приоритетом, который меньше или равен приоритету операции, f — положение самого символа операции относительно аргументов. Таким образом, шаблон yfx для операции - означает, что выражение X-Y-Z понимается как (X-Y)-Z, шаблон xfy для запятой означает, что t,u,r понимается как t,(u,r),шаблон xfx для :- означает невозможность использования нескольких таких операций подряд без дополнительных скобок. Операции с меньшими приоритетами связывают свои аргументы сильнее. Один и тот же атом может быть определен и как унарная, и как бинарная операция.

Пример описаний операций показывает, что даже локальное использование различения конкретно- и абстрактно-синтаксических представлений программы дает возможность получить большие преимущества. В PROLOG не пришлось отдельно заниматься семантикой операций, поскольку в абстрактном синтаксисе их нет. Автоматически устраняются многие тонкие вопросы, связанные, в частности, с возможностью PROLOG -программы преобразовывать саму себя (см. упр. 7).

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

Джулией Робинсон доказано (см., напр. ), что для выражений первого порядка имеется эффективный алгоритм унификации, находящий для двух выражений унифицирующую подстановку либо обосновывающий, что такой подстановки нет.

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

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

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

А в двух последовательностях

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

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

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

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

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

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

Рассмотрим, как исполняется программа на языке PROLOG. В программе может быть одно целевое предложение, не имеющее головной части. Оно начинается с функтора :- или ?-. В программе, транслируемой и исполняемой в пакетном режиме, обычно используется первый функтор, а при задании цели с терминала в режиме диалога—второй. Разница между ними проявляется лишь в режиме диалога. Второй вариант цели позволяет пользователю после нахождения одного из решений продолжить выполнение программы для поиска следующего решения. Первый такой возможности ему не представляет, программа находит какое-нибудь решение и останавливается.

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

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

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

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

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

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

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

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).

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

Насколько каверзны вроде бы невинные предположения (например, условие, что подцели достигаются строго одна за другой и варианты перебираются в том же порядке), сделанные в языке PROLOG, видно из того, что при логически эквивалентной переформулировке одного из предложений программы

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

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

No

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

Есть еще одна особенность языка PROLOG, которая кажется явным ляпсусом, но на самом деле является отражением результата Косовского и др. (неизвестного реализаторам и пользователям языка PROLOG, но лучшими из них ощущаемого интуитивно) о несовместимости моделей отождествления PROLOG и Рефала. Вся работа системы PROLOG основана на предположении, что значения унифицируемых переменных набираются однозначно, и следующий вариант может получиться лишь в результате унификации с другим фактом либо предложением. Поэтому когда (как в случае со списками или строками) PROLOG встречается с неоднозначным отождествлением, он никогда не будет перебирать разные его варианты. Он либо выберет первый из них (например, при унификации неизвестных [X|Y] с уже известным списком Z X будет пустым списком), либо зациклится на бесконечном повторении одного и того же варианта (смотри предыдущую скобку, которая иллюстрирует сразу две неприятности: если к такой унификации вернутся, будет выбран 'новый' пустой список в качестве X ).

Для того, чтобы вычислить выражение, имеется предопределенная бинарная операция is. Она должна иметь вторым аргументом выражение, составленное из атомов при помощи функций. После применения X is 1+2 вместо X подставится 3. Даже выражение 1+2 остается в таком же виде, пока оно не попадет во второй аргумент is.

Внимание!

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

Рассмотренные до сих пор средства языка PROLOG не дают возможности сформулировать отрицание. Впрочем, отрицание и не может присутствовать в хорновых формулах, его наличие разрушает свойства, которые послужили основой для модели вычислений языка PROLOG. Но на практике оно нужно, и поэтому в языке PROLOG введен его суррогат. Этот суррогат дает возможность программисту минимально управлять точками возврата. Если в цели встал на первое место атом ! (называемый предикатом отсечения ), то он успешно унифицируется и уничтожает последнюю точку возврата. Предикат ! используется прежде всего для определения отрицания как явного неуспеха подцели.

Пример 6.3.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).
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, но зато сохраняются все его недостатки.

Внимание!

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

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

A:-A.

и этот операторЗдесь мы не оговорились: в данном случае предложения лучше трактовать как операторы, поскольку как утверждения их в данном случае рассматривать невозможно. выполнится, то программа зациклится. И по этой причине, и по причине ошибки в унификации предложения языка PROLOG, сохранив внешнюю форму логических, по существу отношения к логике уже не имеют.

Конечно же, несообразности были использованы и для получения новых эффектов. Рассмотрим следующее определение.

repeat.
repeat:-repeat.

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

Приведенное выше определение repeat писать в программах не нужно. В стандарте PROLOG задан встроенный предикат repeat, потенциально бесконечное число раз успешно унифицируемый. Реализованный в языке PROLOG перебор вариантов при всех своих недостатках довольно удачно моделирует недетерминированные алгоритмы в программе.

Недетерминированную модель вычислений, соответствующую PROLOG, можно определить в общем виде следующим образом:

  • Имеются точки разветвления, допускающие переходы без проверки условий выбора вариантов — точки недетерминированного разветвления.
  • Вычислительный процесс выбирает в такой точке любое из возможных продолжений.
  • Некоторые из возможных продолжений объявляются тупиковыми, или тупиками, т. е. такими, которые не приводят вычислительный процесс к заранее определенной цели. Принципиально, что тупик продолжения не может определиться в точке разветвления.
  • Успешным вычислением называется такая последовательность выбираемых продолжений в каждой точке недетерминированного разветвления, которая приводит процесс к цели (т. е. ни одно из выбранных продолжений не является тупиком).
    •

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

    Есть теорема, доказывающая, что в принципе недетерминированный конечный автомат всегда можно преобразовать в детерминированный. Идея преобразования — склейка состояний, как показано на рис. 6.1. При этом, содержательно говоря, мы создаем линейный порядок на множестве альтернатив и выбираем альтернативы в строгом соответствии с этим порядком. Именно так с самого начала поступили в языке PROLOG. Беды в этом нет. В то время, когда создавался язык PROLOG, идея совместности (т. е. безразличия некоторых последовательностей предложений к порядку их исполнения) и недетерминированности (т. е. ситуации, когда один и тот же оператор в одном и том же контексте может давать разные результаты) как положительного фактора была только что осознана. А те, кто делают что-либо принципиально новое, почти всегда забывают согласовать свою находку с другими принципиальными достижениями того же времени, предпочитая локализовать новизну и в остальных пунктах работать как можно более традиционно. Беды начались, когда особенности конкретного упорядочивания стали беспощадно использоваться в хакерском духе, да еще и выставляться как принципиальные новации.

    (рис 6.1) Преобразование недетерминированного поиска в детерминированный

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

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

    Поскольку структура программы и структура Поля зрения практически изоморфны, естественно ставить вопрос о динамическом порождении PROLOG -программ. Кроме этого высокоуровневого соображения, есть и прагматическое, которое можно извлечь из нашей программы 6.3.2. В нашу программу мы были вынуждены записать и определение лабиринта.Конечно же, можно было бы прочитать с помощью встроенной функции read определение лабиринта и записать его в список, но тогда мы почти утратили бы все преимущества языка PROLOG, не избавившись при этом ни от одного его недостатка. Гораздо естественнее иметь возможность прочитать базу данных из файла.

    Для этой цели в PROLOG был введен встроенный предикат consult(file[.pl]). Он читает предложения и факты из файла и помещает их в конец программы, тем самым оставляя в неприкосновенности ранее данные определения предикатов. С его использованием наша программа может быть переписана в следующем виде.

    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).

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

    Есть еще один класс встроенных отношений, которые действуют как встроенные функции, но не требуют явной активизации операцией is. К ним, в частности, относятся многие действия над списками. Рассмотрим, например, предикат append(E1,E2,E3). Он корректно унифицируется, когда объединение первых двух списков является третьим. Соответственно, он может использоваться для вычисления любого из своих трех аргументов, если два других заданы. Например,

    append(X,Y,Z)

    при Z=[a,b,c,d], Y=[c,d] унифицируется как X=[a,b].

    Очень жаль, что в PROLOG таким же образом не реализованы арифметические функции!

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

    Метапредикат assert(P:-P1,. . . ,Pn) помещает свой аргумент в PROLOG - программу. Имеются несколько его вариантов, располагающие новое предложение или факт в начало или в конец программы. Метапредикат retract(P:-P1,. . . ,Pn), наоборот, удаляет из программы предложение или факт, унифицируемый с его аргументом.

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

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

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

    retractall(Name / Arity)

    Этот предикат удаляет все предложения и факты, говорящие о предикате Name арности Arity. Естественно, при этом удаляется лишь определение. Если Вы его использовали, то нужно потрудиться удалить также использующие предложения. Поэтому предикаты лучше удалять целыми содержательно связанными группами, и концентрировать все такие удаления в одном предложении для каждой группы.

    Динамическое порождение программ — метод, исключительно сильный, когда применен в подходящей обстановке и корректно, и исключительно опасный, когда применен в неподходящем окружении либо хоть чуть-чуть некорректно. В традиционных языках ему всячески препятствуют. Там он (по причине очень многих практических провалов) имеет одиозную репутацию. Но эта репутация связана прежде всего с тем, что такой рискованный и красивый метод требует высокой проработки идей, а в традиционном программировании мы, пытаясь его применить, вынуждены прорабатывать глупейшие технические проблемы (строить множество подпорок, см. словарь).

    Внимание!

    В новых версиях языка PROLOG предикаты, которые Вы намерены динамически видоизменять, нужно объявить. Например, dynamic(connect).

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

  • var(Term). Унифицируется, если Term свободная переменная.
  • nonvar(Term). Унифицируется, если textsfTerm не свободная переменная.
  • integer(Term) Успешен, если Term является целым числом (именно числом, а не выражением).
  • float(Term) Успешен, если Term является действительным числом.
  • number(Term) Успешен, если Term является числом.
  • atom(Term) Успешен, если Term является атомом.
  • string(Term). Успешен, если Term является строкой.
  • atomic(Term). Успешен, если Term является неделимым значением (число, строка или атом).
  • compound(Term). Успешен, если Term является сложным выражением.
  • ground(Term). Успешен, если Term не содержит свободных переменных.
    •

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

  • functor(Term, Functor, Arity) Унифицируется, если Term является термом с главным функтором Functor арности Arity. Term, являющийся переменной, унифицируется с новой переменной. Если Term является атомом либо числом, то его арностью считается 0, а функтором он сам.
  • arg(Arg, Term, Value) Выделение аргумента терма Term по его номеру Arg.Номера начинаются с 1. Естественно, что данный предикат может быть использован и для определения номера аргумента в терме.
  • Term =.. List Унифицируется, если List является списком, головой которого является функтор терма Term, а оставшиеся члены задают аргументы (сравните с тем, что ниже рассматривается в языке LISP!) Если не использовать его как операцию, то имя этого предиката Univ. Естественно, он может работать в обе стороны, разбирая либо собирая терм.
    •

    Примеры.

    ?- send(hello, X) =.. List.
List = [send, hello, X]
?- Term=.. [send, hello, X]
Term = send(hello,X)

    free_variables(Term, List) List унифицируется как список новых переменных, каждая из которых равна свободной терма Term.

    atom_codes(Atom, String) Преобразование атома в строку и наоборот.

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

    Организация вычислений и ввода-вывода

    Во многих случаях даже в поисковой программе необходимо производить вычисления. В языке PROLOG имеется способ вычисления значения по аргументам. Это так называемые встроенные функции, которые могут быть заменены на свое значение, если их аргумент известен. Такими функциями служат, в частности, числовые арифметические операции. Заметим, что даже встроенная функция не вычисляется, пока не будет дан явный сигнал. У Вас в программе может, скажем, накопиться в качестве значения переменной выражение 1 + 1 + 1, но оно не будет равно 3.

    Для организации вычисления имеется специальное отношение X is E. В этом отношении Е является таким выражением, которое после подстановки текущих значений переменных конкретизируетсяЗдесь мы употребили термин конкретизация, поскольку используются именно текущие значения переменных, согласования не происходит. в композицию встроенных функций от константных аргументов. Эта композиция вычисляется, и переменная Х унифицируется как ее значение.

    Таким образом, можно постепенно накапливать вычисления, а затем в подходящий момент их произвести. Смотрите пример.

    ?- assert(a(1+1)).
Yes
?- assert(b(2 * 2)).
Yes
?- a(X), b(Y), Z is X + Y.
X = 1+1
Y = 2*2
Z = 6

    Внимание!

    is не является присваиванием! Для того, чтобы убедиться в этом, исполните простейшее предложение языка PROLOG:

    ?- X is 1, X is X + 1.

    Лучше всего и естественней всего вводятся в PROLOG -программу данные, полностью соответствующие синтаксису предложений и фактов языка. Если файл данных не очень велик, то для ввода достаточно воспользоваться уже описанным нами предикатом consult.

    Конечно же, имеется и более традиционная система ввода-вывода. Опишем ее базовые возможности.

    open(SrcDest, Mode, Stream, Options)

    Открытие файла. SrcDes является атомом, содержащим имя файла в обозначениях системы Unix. Mode может быть read, write, append или update. Два последних способа открытия используются, соответственно, для дописывания в существующий файл и для частичного переписывания его. Stream либо переменная, и тогда ей присваивается целое число, которое служит для идентификации файла, либо атом, и тогда он служит внутри программы именем файла. Options могут быть опущены, среди них нам важна одна опция: type(binary), которая позволяет записать коды в двоичный файл. Опции образуют список.

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

    seek(Stream, Offset, Method, NewLocation)

    Method — это метод отсчета относительной позиции. bof отсчитывает ее с начала файла, current от нынешней точки, eof от конца. Переменная NewLocation унифицируется с новой позицией, отсчитываемой обязательно с начала.

    Предикат close(Stream) комментариев не требует.

    read(Stream, Term)

    Переменная Term унифицируется с термом, прочитанным из потока Stream.

    read_clause(Stream, Term)

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

    read_term(Stream, Term, Options)

    Аналогично read, но позволяет установить целый ряд возможностей, регулирующих представление терма. Смотрите подробнее в документации конкретной PROLOG -системы.

    writeq(Stream, Term)

    Term пишется в Stream, вставляются кавычки и скобки, где нужно.

    write_canonical(Stream, Term)

    Term пишется в Stream таким способом, чтобы его однозначно прочитала любая PROLOG -программа, а не только Вы и Ваша программа на Вашей системе.

    Есть способ читать и писать символы, а через них строки и прочее, но это настолько примитивно и уродливо, что можно дать практический совет:

    Внимание!

    Если Вам нужно ввести в PROLOG файл иноязычного или просто обычного формата либо вывести из него в предписанном Вам не укладывающемся в систему термов формате, напишите переходник на Рефале или на Perl.

    Тем не менее вот минимальный (и практически полный) список предикатов символьного и двоичного ввода и вывода.

    get_byte(Stream, Byte)

    Byte рассматривается как целое число и унифицируется со следующим байтом входного потока. Конец файла читается как -1.

    get_char(Stream, Char)

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

    get(Stream, Char)

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

    skip(Stream, Char)

    Пропускает все, пока не встретится символ Char либо конец файла. Само первое вхождение Char также будет пропущено.

    put(Stream, Char)

    Вывод одного символа либо байта. Char унифицируется либо как целое число из диапазона [0, 255], либо как атом с именем из одного символа.

    nl(+Stream)

    Вывести перевод строки.

    Страницы:

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

    Язык логического программирования PROLOG представляет собой одну из моделей сентенциального программирования. Мы используем лишь те возможности языка PROLOG, которые согласуются с принятым в 1996 г. стандартом . Как руководство по программированию на языке PROLOG можно использовать, скажем, книгу . В ней содержится наименьшее число недочетов и откровенных ошибок, а также наибольшее число практических советов по сравнению с другими известными автору пособиями.

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

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

    Второй находкой, перенесенной авторами языка PROLOG из специализированных программ (для логики и искусственного интеллекта) в языки программирования, стала система обработки неудач. Успешно произведенная унификация является лишь разрешением выполнить некоторое действие. После проверки других условий, возможно, мы будем вынуждены вернуться и выбрать другой вариант.

    Третья находка языка PROLOG, перенесенная в программирование из метода резолюций, — это стандартизация цели. Целью доказательства в методе резолюций всегда является получение пустого дизъюнкта, то есть стирание доказываемого выражения (с логической точки зрения, приведение его к абсурду). Точно так же и в языке PROLOG: успешное исполнение программы означает стирание поля зрения.

    Четвертая находка создателей языка PROLOG взята из ограничения классической логики. Хорновские формулы

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

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

    Когда рассматривается исполнение программы в нетрадиционном языке (например, PROLOG -программы), то естественно воспринимать конкретную реализацию языка как новую машину нетрадиционной архитектуры с высокоуровневыми командами (в данном случае как PROLOG -машину).

    Данные, используемые PROLOG -машиной, размещаются во всех частях поля памяти и имеют общую структуру.

    Рассмотрим на уровне абстрактного синтаксиса структуру данных, обрабатываемых языком PROLOG. Все данные языка PROLOG являются термами. Термы построены из атомов при помощи функциональных символов. Атомами могут быть переменные и константы, в свою очередь, делящиеся на имена и числа. Функциональные символы являются именами и называются функторами. Среди функторов выделяются детерминативы, которые в реализации делятся на предикаты и встроенные функции (функции обычно используются внутри выражений, а предикаты являются основными единицами управления и обычно используются вне скобок как основной функциональный символ выражения). Детерминативы должны быть описаны в программе, а остальные функторы рассматриваются просто как структурные единицы и могут оставаться неописанными.

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

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

    И, наконец, в поле памяти помещается сама PROLOG -программа, которая естественно структурируется на две части, нередко перемешанные в тексте самой программы, но обычно разделяемые при использовании внешней памяти: база данных и база знаний.

    База данных состоит из фактов, представляющих собой предикат, примененный к термам.

    База знаний состоит из предложений (клауз). Каждое предложение имеет вид, подобный хорновской формуле

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

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

    В любой момент исполнения программы база данных и база знаний могут быть модифицированы.

    Теперь перейдем к конкретному представлению данных.

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

    Константы языка PROLOGВнутри языка они называются атомами. в конкретном синтаксисе делятся на имена (идентификаторы, начинающиеся с маленькой буквы либо совокупность нескольких специальных символов типа <, =, $ ), символы и числа (символы отождествляются с целыми числами, являющимися их кодами). Произвольная последовательность символов может быть сделана единой константой, например:

    'C:\"SICS Prolog"\program.pl'.

    Любое константное имя может служить функтором. Функторы различаются арностью (т. е. количеством аргументов), таким образом, может быть сразу несколько функторов с одним и тем же именем. Например, write(a(1)) и write(a(1),file1) используют различные функторы. Некоторые функции могут быть описаны как операции (инфиксные, префиксные либо постфиксные). В отличие от почти всех остальных языков, операции рассматриваются лишь как сокращение для выразительности. Например, x+y означает в точности то же, что и +(x,y).

    Для некоторых из предопределенных в системе функций и предикатов имеются дополнительные ограничения на аргументыВ части реализаций эти ограничения могут распространяться и на функции, определенные программистом.. Например, в функции load(f) f должно быть именем файла.

    Поле зрения (цель), содержащее непосредственно обрабатываемые программой данные, состоит из последовательности термов, разделенных либо запятыми (в этом случае они понимаются как "последовательно достигаемые подцели"), либо символами |, в этом случае подцели "альтернативны".Наиболее важным и классическим является случай последовательно достигаемых подцелей, через который определяется и семантика альтернативных подцелейМы сознательно отказались от сопоставления двух видов целей в PROLOG с конъюнкцией и дизъюнкцией, поскольку их семантика принципиально отличается от семантики этих логических связок..

    В конкретном представлении предложение, например,

    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 — очевидную неудачу.

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

    father(ivan,vasilij).

    В принципе, все остальные структуры языка PROLOG выражаются через элементарные, определенные выше. Но некоторые из структур прагматически настолько важны, что получили отдельное оформление и более эффективную реализацию. Это, прежде всего, списки и строки. Список, в принципе, определяется как терм, построенный из других термов и пустого списка [] применением двухместного функтора .(head,tail). Выстроенная в стандартном порядке композиция

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

    понимается как линейный список и обозначается [a,b,. . . ,z].

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

    [t,u|L].

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

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

    Заслуживает упоминания механизм введения новых операций в язык 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. Второй аргумент — шаблон операции; x обозначает выражение с приоритетом, строго меньшим приоритета операции; y — выражение с приоритетом, который меньше или равен приоритету операции, f — положение самого символа операции относительно аргументов. Таким образом, шаблон yfx для операции - означает, что выражение X-Y-Z понимается как (X-Y)-Z, шаблон xfy для запятой означает, что t,u,r понимается как t,(u,r),шаблон xfx для :- означает невозможность использования нескольких таких операций подряд без дополнительных скобок. Операции с меньшими приоритетами связывают свои аргументы сильнее. Один и тот же атом может быть определен и как унарная, и как бинарная операция.

    Пример описаний операций показывает, что даже локальное использование различения конкретно- и абстрактно-синтаксических представлений программы дает возможность получить большие преимущества. В PROLOG не пришлось отдельно заниматься семантикой операций, поскольку в абстрактном синтаксисе их нет. Автоматически устраняются многие тонкие вопросы, связанные, в частности, с возможностью PROLOG -программы преобразовывать саму себя (см. упр. 7).

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

    Джулией Робинсон доказано (см., напр. ), что для выражений первого порядка имеется эффективный алгоритм унификации, находящий для двух выражений унифицирующую подстановку либо обосновывающий, что такой подстановки нет.

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

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

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

    А в двух последовательностях

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

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

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

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

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

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

    Рассмотрим, как исполняется программа на языке PROLOG. В программе может быть одно целевое предложение, не имеющее головной части. Оно начинается с функтора :- или ?-. В программе, транслируемой и исполняемой в пакетном режиме, обычно используется первый функтор, а при задании цели с терминала в режиме диалога—второй. Разница между ними проявляется лишь в режиме диалога. Второй вариант цели позволяет пользователю после нахождения одного из решений продолжить выполнение программы для поиска следующего решения. Первый такой возможности ему не представляет, программа находит какое-нибудь решение и останавливается.

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

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

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

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

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

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

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

    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).

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

    Насколько каверзны вроде бы невинные предположения (например, условие, что подцели достигаются строго одна за другой и варианты перебираются в том же порядке), сделанные в языке PROLOG, видно из того, что при логически эквивалентной переформулировке одного из предложений программы

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

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

    No

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

    Есть еще одна особенность языка PROLOG, которая кажется явным ляпсусом, но на самом деле является отражением результата Косовского и др. (неизвестного реализаторам и пользователям языка PROLOG, но лучшими из них ощущаемого интуитивно) о несовместимости моделей отождествления PROLOG и Рефала. Вся работа системы PROLOG основана на предположении, что значения унифицируемых переменных набираются однозначно, и следующий вариант может получиться лишь в результате унификации с другим фактом либо предложением. Поэтому когда (как в случае со списками или строками) PROLOG встречается с неоднозначным отождествлением, он никогда не будет перебирать разные его варианты. Он либо выберет первый из них (например, при унификации неизвестных [X|Y] с уже известным списком Z X будет пустым списком), либо зациклится на бесконечном повторении одного и того же варианта (смотри предыдущую скобку, которая иллюстрирует сразу две неприятности: если к такой унификации вернутся, будет выбран 'новый' пустой список в качестве X ).

    Для того, чтобы вычислить выражение, имеется предопределенная бинарная операция is. Она должна иметь вторым аргументом выражение, составленное из атомов при помощи функций. После применения X is 1+2 вместо X подставится 3. Даже выражение 1+2 остается в таком же виде, пока оно не попадет во второй аргумент is.

    Внимание!

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

    Рассмотренные до сих пор средства языка PROLOG не дают возможности сформулировать отрицание. Впрочем, отрицание и не может присутствовать в хорновых формулах, его наличие разрушает свойства, которые послужили основой для модели вычислений языка PROLOG. Но на практике оно нужно, и поэтому в языке PROLOG введен его суррогат. Этот суррогат дает возможность программисту минимально управлять точками возврата. Если в цели встал на первое место атом ! (называемый предикатом отсечения ), то он успешно унифицируется и уничтожает последнюю точку возврата. Предикат ! используется прежде всего для определения отрицания как явного неуспеха подцели.

    Пример 6.3.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).
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, но зато сохраняются все его недостатки.

    Внимание!

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

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

    A:-A.

    и этот операторЗдесь мы не оговорились: в данном случае предложения лучше трактовать как операторы, поскольку как утверждения их в данном случае рассматривать невозможно. выполнится, то программа зациклится. И по этой причине, и по причине ошибки в унификации предложения языка PROLOG, сохранив внешнюю форму логических, по существу отношения к логике уже не имеют.

    Конечно же, несообразности были использованы и для получения новых эффектов. Рассмотрим следующее определение.

    repeat.
repeat:-repeat.

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

    Приведенное выше определение repeat писать в программах не нужно. В стандарте PROLOG задан встроенный предикат repeat, потенциально бесконечное число раз успешно унифицируемый. Реализованный в языке PROLOG перебор вариантов при всех своих недостатках довольно удачно моделирует недетерминированные алгоритмы в программе.

    Недетерминированную модель вычислений, соответствующую PROLOG, можно определить в общем виде следующим образом:

  • Имеются точки разветвления, допускающие переходы без проверки условий выбора вариантов — точки недетерминированного разветвления.
  • Вычислительный процесс выбирает в такой точке любое из возможных продолжений.
  • Некоторые из возможных продолжений объявляются тупиковыми, или тупиками, т. е. такими, которые не приводят вычислительный процесс к заранее определенной цели. Принципиально, что тупик продолжения не может определиться в точке разветвления.
  • Успешным вычислением называется такая последовательность выбираемых продолжений в каждой точке недетерминированного разветвления, которая приводит процесс к цели (т. е. ни одно из выбранных продолжений не является тупиком).
    •

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

    Есть теорема, доказывающая, что в принципе недетерминированный конечный автомат всегда можно преобразовать в детерминированный. Идея преобразования — склейка состояний, как показано на рис. 6.1. При этом, содержательно говоря, мы создаем линейный порядок на множестве альтернатив и выбираем альтернативы в строгом соответствии с этим порядком. Именно так с самого начала поступили в языке PROLOG. Беды в этом нет. В то время, когда создавался язык PROLOG, идея совместности (т. е. безразличия некоторых последовательностей предложений к порядку их исполнения) и недетерминированности (т. е. ситуации, когда один и тот же оператор в одном и том же контексте может давать разные результаты) как положительного фактора была только что осознана. А те, кто делают что-либо принципиально новое, почти всегда забывают согласовать свою находку с другими принципиальными достижениями того же времени, предпочитая локализовать новизну и в остальных пунктах работать как можно более традиционно. Беды начались, когда особенности конкретного упорядочивания стали беспощадно использоваться в хакерском духе, да еще и выставляться как принципиальные новации.

    (рис 6.1) Преобразование недетерминированного поиска в детерминированный

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

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

    Поскольку структура программы и структура Поля зрения практически изоморфны, естественно ставить вопрос о динамическом порождении PROLOG -программ. Кроме этого высокоуровневого соображения, есть и прагматическое, которое можно извлечь из нашей программы 6.3.2. В нашу программу мы были вынуждены записать и определение лабиринта.Конечно же, можно было бы прочитать с помощью встроенной функции read определение лабиринта и записать его в список, но тогда мы почти утратили бы все преимущества языка PROLOG, не избавившись при этом ни от одного его недостатка. Гораздо естественнее иметь возможность прочитать базу данных из файла.

    Для этой цели в PROLOG был введен встроенный предикат consult(file[.pl]). Он читает предложения и факты из файла и помещает их в конец программы, тем самым оставляя в неприкосновенности ранее данные определения предикатов. С его использованием наша программа может быть переписана в следующем виде.

    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).

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

    Есть еще один класс встроенных отношений, которые действуют как встроенные функции, но не требуют явной активизации операцией is. К ним, в частности, относятся многие действия над списками. Рассмотрим, например, предикат append(E1,E2,E3). Он корректно унифицируется, когда объединение первых двух списков является третьим. Соответственно, он может использоваться для вычисления любого из своих трех аргументов, если два других заданы. Например,

    append(X,Y,Z)

    при Z=[a,b,c,d], Y=[c,d] унифицируется как X=[a,b].

    Очень жаль, что в PROLOG таким же образом не реализованы арифметические функции!

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

    Метапредикат assert(P:-P1,. . . ,Pn) помещает свой аргумент в PROLOG - программу. Имеются несколько его вариантов, располагающие новое предложение или факт в начало или в конец программы. Метапредикат retract(P:-P1,. . . ,Pn), наоборот, удаляет из программы предложение или факт, унифицируемый с его аргументом.

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

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

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

    retractall(Name / Arity)

    Этот предикат удаляет все предложения и факты, говорящие о предикате Name арности Arity. Естественно, при этом удаляется лишь определение. Если Вы его использовали, то нужно потрудиться удалить также использующие предложения. Поэтому предикаты лучше удалять целыми содержательно связанными группами, и концентрировать все такие удаления в одном предложении для каждой группы.

    Динамическое порождение программ — метод, исключительно сильный, когда применен в подходящей обстановке и корректно, и исключительно опасный, когда применен в неподходящем окружении либо хоть чуть-чуть некорректно. В традиционных языках ему всячески препятствуют. Там он (по причине очень многих практических провалов) имеет одиозную репутацию. Но эта репутация связана прежде всего с тем, что такой рискованный и красивый метод требует высокой проработки идей, а в традиционном программировании мы, пытаясь его применить, вынуждены прорабатывать глупейшие технические проблемы (строить множество подпорок, см. словарь).

    Внимание!

    В новых версиях языка PROLOG предикаты, которые Вы намерены динамически видоизменять, нужно объявить. Например, dynamic(connect).

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

  • var(Term). Унифицируется, если Term свободная переменная.
  • nonvar(Term). Унифицируется, если textsfTerm не свободная переменная.
  • integer(Term) Успешен, если Term является целым числом (именно числом, а не выражением).
  • float(Term) Успешен, если Term является действительным числом.
  • number(Term) Успешен, если Term является числом.
  • atom(Term) Успешен, если Term является атомом.
  • string(Term). Успешен, если Term является строкой.
  • atomic(Term). Успешен, если Term является неделимым значением (число, строка или атом).
  • compound(Term). Успешен, если Term является сложным выражением.
  • ground(Term). Успешен, если Term не содержит свободных переменных.
    •

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

  • functor(Term, Functor, Arity) Унифицируется, если Term является термом с главным функтором Functor арности Arity. Term, являющийся переменной, унифицируется с новой переменной. Если Term является атомом либо числом, то его арностью считается 0, а функтором он сам.
  • arg(Arg, Term, Value) Выделение аргумента терма Term по его номеру Arg.Номера начинаются с 1. Естественно, что данный предикат может быть использован и для определения номера аргумента в терме.
  • Term =.. List Унифицируется, если List является списком, головой которого является функтор терма Term, а оставшиеся члены задают аргументы (сравните с тем, что ниже рассматривается в языке LISP!) Если не использовать его как операцию, то имя этого предиката Univ. Естественно, он может работать в обе стороны, разбирая либо собирая терм.
    •

    Примеры.

    ?- send(hello, X) =.. List.
List = [send, hello, X]
?- Term=.. [send, hello, X]
Term = send(hello,X)

    free_variables(Term, List) List унифицируется как список новых переменных, каждая из которых равна свободной терма Term.

    atom_codes(Atom, String) Преобразование атома в строку и наоборот.

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

    Организация вычислений и ввода-вывода

    Во многих случаях даже в поисковой программе необходимо производить вычисления. В языке PROLOG имеется способ вычисления значения по аргументам. Это так называемые встроенные функции, которые могут быть заменены на свое значение, если их аргумент известен. Такими функциями служат, в частности, числовые арифметические операции. Заметим, что даже встроенная функция не вычисляется, пока не будет дан явный сигнал. У Вас в программе может, скажем, накопиться в качестве значения переменной выражение 1 + 1 + 1, но оно не будет равно 3.

    Для организации вычисления имеется специальное отношение X is E. В этом отношении Е является таким выражением, которое после подстановки текущих значений переменных конкретизируетсяЗдесь мы употребили термин конкретизация, поскольку используются именно текущие значения переменных, согласования не происходит. в композицию встроенных функций от константных аргументов. Эта композиция вычисляется, и переменная Х унифицируется как ее значение.

    Таким образом, можно постепенно накапливать вычисления, а затем в подходящий момент их произвести. Смотрите пример.

    ?- assert(a(1+1)).
Yes
?- assert(b(2 * 2)).
Yes
?- a(X), b(Y), Z is X + Y.
X = 1+1
Y = 2*2
Z = 6

    Внимание!

    is не является присваиванием! Для того, чтобы убедиться в этом, исполните простейшее предложение языка PROLOG:

    ?- X is 1, X is X + 1.

    Лучше всего и естественней всего вводятся в PROLOG -программу данные, полностью соответствующие синтаксису предложений и фактов языка. Если файл данных не очень велик, то для ввода достаточно воспользоваться уже описанным нами предикатом consult.

    Конечно же, имеется и более традиционная система ввода-вывода. Опишем ее базовые возможности.

    open(SrcDest, Mode, Stream, Options)

    Открытие файла. SrcDes является атомом, содержащим имя файла в обозначениях системы Unix. Mode может быть read, write, append или update. Два последних способа открытия используются, соответственно, для дописывания в существующий файл и для частичного переписывания его. Stream либо переменная, и тогда ей присваивается целое число, которое служит для идентификации файла, либо атом, и тогда он служит внутри программы именем файла. Options могут быть опущены, среди них нам важна одна опция: type(binary), которая позволяет записать коды в двоичный файл. Опции образуют список.

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

    seek(Stream, Offset, Method, NewLocation)

    Method — это метод отсчета относительной позиции. bof отсчитывает ее с начала файла, current от нынешней точки, eof от конца. Переменная NewLocation унифицируется с новой позицией, отсчитываемой обязательно с начала.

    Предикат close(Stream) комментариев не требует.

    read(Stream, Term)

    Переменная Term унифицируется с термом, прочитанным из потока Stream.

    read_clause(Stream, Term)

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

    read_term(Stream, Term, Options)

    Аналогично read, но позволяет установить целый ряд возможностей, регулирующих представление терма. Смотрите подробнее в документации конкретной PROLOG -системы.

    writeq(Stream, Term)

    Term пишется в Stream, вставляются кавычки и скобки, где нужно.

    write_canonical(Stream, Term)

    Term пишется в Stream таким способом, чтобы его однозначно прочитала любая PROLOG -программа, а не только Вы и Ваша программа на Вашей системе.

    Есть способ читать и писать символы, а через них строки и прочее, но это настолько примитивно и уродливо, что можно дать практический совет:

    Внимание!

    Если Вам нужно ввести в PROLOG файл иноязычного или просто обычного формата либо вывести из него в предписанном Вам не укладывающемся в систему термов формате, напишите переходник на Рефале или на Perl.

    Тем не менее вот минимальный (и практически полный) список предикатов символьного и двоичного ввода и вывода.

    get_byte(Stream, Byte)

    Byte рассматривается как целое число и унифицируется со следующим байтом входного потока. Конец файла читается как -1.

    get_char(Stream, Char)

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

    get(Stream, Char)

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

    skip(Stream, Char)

    Пропускает все, пока не встретится символ Char либо конец файла. Само первое вхождение Char также будет пропущено.

    put(Stream, Char)

    Вывод одного символа либо байта. Char унифицируется либо как целое число из диапазона [0, 255], либо как атом с именем из одного символа.

    nl(+Stream)

    Вывести перевод строки.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^