» Главная
eXcode.ru » Статьи » Другие » Стили и методы программирования
» Новости
» Опросы
» Файлы
» Журнал



Пользователей: 0
Гостей: 12





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




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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

′C:"SICS Prolog"program.pl′.

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

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

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

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

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

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

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

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


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


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


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


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

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

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

Рассмотрим, как исполняется программа на языке 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).
Пример 6.3.1.

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

?-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).
Листинг 6.3.2. Статический лабиринт

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

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

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

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

repeat.
repeat:-repeat.

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

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

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

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

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

Есть теорема, доказывающая, что в принципе недетерминированный конечный автомат всегда можно преобразовать в детерминированный. Идея преобразования — склейка состояний, как показано на рис. 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).
Листинг 6.4.1. Вводимый лабиринт

Пример файла 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. В этом отношении Е является таким выражением, которое после подстановки текущих значений переменных конкретизируется7) в композициювстро енных функций от константных аргументов. Эта композиция вычисляется, и переменная Х унифицируется как ее значение.

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

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

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

1) В отличие от клауз, посылки логических формул ни в каком смысле не могут считаться последовательно достигаемыми.
2) Внутри языка они называются атомами.
3) В части реализаций эти ограничения могут распространяться и на функции, определенные программистом.
4) Мысознательно отказались от сопоставления двух видов целей в PROLOG с конъюнкцией и дизъюнкцией, поскольку их семантика принципиально отличается от семантики этих логических связок.
5)

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

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

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


6) Здесь мы не оговорились: в данном случае предложения лучше трактовать как операторы, поскольку как утверждения их в данном случае рассматривать невозможно.
7) Здесь мы употребили термин конкретизация, поскольку используются именно текущие значения переменных, согласования не происходит.
К началу статьи





Добавил: MadvEXДата публикации: 2006-02-28 02:02:23
Рейтинг статьи:3.00 [Голосов 5]Кол-во просмотров: 10382

Комментарии читателей

Всего комментариев: 362

2018-12-16 09:29:48
Egbrvthg
WHEN Manchester Citys youngsters talk about the &#8220;onion bag it might not be what you think. Saturday Premier League match preview featuring Man City v ChelseaAmpadus father Kwame spent five ye. "tch, he says he&#8217;s fit and ready to go, his general fitness is good but his match fitness is lacking." [url=https://www.soldeshuarache.fr/adidas%20rozmiar%2022-ID2304974.html]adidas rozmiar 22[/url] Sunday Premier League match preview featuring Arsenal v BurnleyThe Sun. He commented:?I think above all about signing players aged 28 or 29. reconnaissance His decision is in his mind but he is happy and happy to stay here and play for us. "Chelsea TV1Kyle Jameson has been signed by ChelseaJameson, who started his career at Everton before ending up at Southport, will join the academy ranks at the club." [url=http://www.aaa7.fr/stan%20smith%20vulc%20all%20white-ID61310.html]stan smith vulc all white[/url] or the face of a young child behind the Chelsea goalHeroic Burnley fan saves child from getting a ball in the face against Chelsea6Ashley Barnes tried his luck from outside the box in the 19th minute that almost knocked out a young childSky Sports6Burnley battled back to land a 1-1 draw with the league leaders after the near-missSky Sports6A quick-thinking fan saved the day by blocking the rasping strikeHis wayward drive flashed wide of the goal and was on course to hit one supporter flush in the face that would have caused serious damage. legislature "s, results and live match commentaryArsenal manager Arsene Wenger&#039;s best referee rantsThe Sun." push through a deal for the Ўк17million-rated player in the transfer window but was unable to agree terms in time. flux [url=http://www.verasoie.fr/adidas%20superstar%20up-ID37651.html]adidas superstar up[/url] The Belgian saw his header hit the post before Antonio Valencia picked up the loose ball and crossed for Zlatan Ibrahimovic to head in the equaliser.

Reference: http://www.albinismo.eu/rss.xml

2018-11-21 20:45:51
Williamillit
Где взять кредит без справок и поручителей? Займы взять онлайн на карту [url=https://onlinecredit247.ru/]Займ на карту без кредитной истории[/url] Доступные экспресс кредиты наличными быстро без справок и поручителей

2018-11-20 12:19:46
Williamillit
Как купить машину в кредит с плохой кредитной историей? Срочные займы на карту https://onlinecredit247.ru/ Взять деньги в долг мгновенно можно круглосуточно, а также в выходные дни

2018-09-15 12:48:31
Justin
Вам нужен кредит для вашего бизнеса или личных целей? Мы оказываем финансовую помощь компаниям и частным лицам с удобной для кармана процентной ставкой в размере 3% годовых. Наши условия дешевы и понятны.

Свяжитесь с нами сегодня и будет финансироваться в течение 2-4 рабочих дней. E-mail: unique2aal@gmail.com

2018-08-23 04:33:31
SusanAldrich
Эффект от использования капсул не исчезает и после лечения, поскольку Эроктив отличается накопительным действием. Eroctive можно применять с 18 лет без дальнейших возрастных ограничений. Покупка средства на официальном ресурсе гарантирует безопасность биокомплекса. Натуральный состав не имеет противопоказаний кроме индивидуальных аллергических реакций на отдельные ингредиенты. Осторожность должны проявить мужчины, имеющие в анамнезе: аллергические реакции на компоненты, в том числе, продукты пчеловодства; болезни сосудистой системы; стойкую гипертонию; неврологические нарушения. <a href=http://otzyvy-vrachej.com/>маловерие</a> Удовлетворять в сексе на 100% женщин, не терпеть фиаско в постели, стать уверенным в своих силах поможет Xtrazex. Пройдите курс лечения вместе с ним и убедитесь в его эффективности сами. Растворимые таблетки Xtrazex для потенции. Разнообразные трудности в постели преследуют всех представителей слабого пола. И иногда возникающие проблемы могут стать причиной серьезного конфликта со второй половинкой. А полное игнорирование тревожной симптоматики нередко приводит к тому, что мужчина становится импотентом, ввиду чего развиваются проблемы на психологическом уровне.

2018-07-06 15:10:34
Fkpjtzpv
after already snubbing Gunners himselfCESC MATEAntonio Conte won title on Sep 24."High-profile names such as Carlos Tevez, Oscar and Hulk have all made big-money moves to China in?recent weeks."
"The former Barcelona star pulled the ball back across goal and found left wing-back Marcos Alonso, who ran onto the pass and smashed home."rt’s daily LIVE blogThe Gunners boss is believed to be lining up moves for Dortmund&#8217;s Marco Reus and West Ham&#8217;s Dimitri Payet should talks with Ozil and Sanchez fail. [url=http://www.bruiloftband.be/Chaussures-Habillées-Gucci-Chaussure-Besson-DFG7369.html]chaussure besson[/url]
[url=http://www.edenimmobilier.fr/Nike-Air-Max-2013-Material-Bleu-Blanc-Chaussures-Homme-Air-Max-On-ID4290.html]air max on[/url]
http://www.webadidas.fr/W-adidas-solde.html]adidas solde[/url]

"ootball is on TV today Our guide to this week&#039;s live matchespomp and circumstancePortsmouth fans told to back ex-Disney boss Michael Eisner&#039;s &#039;dream ticket to the Premier League&#039;MOMENT TO REFLECTFootball League clubs pay tribute to victims of Westminster terror attack ahead of Saturday fixtureseyes on the prize&#039;I just focus on my job&#039; Tottenham and Liverpool 16-year-old Fulham target Ryan Sessegnon reveals allmickey mouse clubDisney supremo&#039;s takeover of Pompey edges closer as club enters exclusive talks with billionaireWE WILL REMEMBERFootball League clubs to hold minute&#039;s silence to remember those who died in London terror attack The Frenchman fashioned the first chance of the game by waltzing past three Owls defenders down the right, squaring for Murrays whose low effort was well beaten away by Keiren Westwood."" card, updates and title fight build-up Teenage sensation Kylian Mbappe named in France squad for first timeMbappes 12 Ligue 1 goals have helped Monaco to the top of the table and his speed and power has caught the attention of all of Europes top clubs."

2018-06-19 16:40:55
Yvmewpxu
Hes the goal pig at United because the team revolves around him." incredible years, I have decided that now is the right time to finish my career as a professional footballer."
"came famous in her native Brazil after being spotted getting changed at Sao Paolo airport, which earnt her the nickame &#8216;The Naked Hottie of Congonhas&#8217;."The midfielder has played just 18 times and scored one goal for United after joining them in July 2015 for Ўк6. [url=http://www.studiomerliniortodonzia.it/cgi-bin/pagmod.asp?shop=vans+old+skool+2013]vans old skool 2013[/url]
[url=http://www.birbesi.it/contatti_7.asp?sconto=puma-600-ignite]puma 600 ignite[/url]
[url=http://www.birbesi.it/contatti_7.asp?sconto=crossfit-5-reebok]crossfit 5 reebok[/url]

Not only will Guardiola be a key factor but City are going to spend a massive amount this summer to give Pep all the tools he needs to succeed in his first season at the Etihad."Maybe it is Chelsea, maybe it is another team who made the Champions LeagueI dont want to lose him but I can understand if he wants to go."

2018-06-06 14:15:03
Frtwspwwtl
"&#8220;I understand that for them it is special to play against the world champions, I understand also that they can only defend with tough tackling." Both Rashford and Mkhitaryan have made a real difference to United since coming on. [url=http://www.leclothing.com/shoesecco.asp?id=ecco%20ontario%20boot]ecco ontario boot[/url] &#8220;He is ambitious and wants to continue to develop. But the fans want to see progress immediately and the bickering and in-fighting will only continue. [url=https://www.avpcbarbadas.com/D-rihanna-x-puma-suede-creeper-collection.html]rihanna x puma suede creeper collection[/url] Referee Feliz Zwayer suspended play for eight minutes before Schmidt finally departed. " the keeper move on, the club hierarchy would expect the bidding to start at no less than Ўк15million." [url=http://www.kavergruppa.org/shoesecco.asp?id=necco%20ceresani]necco ceresani[/url] He is still highly regarded in the game but the City keeper knows he will never pull on the gloves for them again under Pep Guardiola. Robbie Brady scores an amazing free kick for Burnley against ChelseaForm GuideSwansea: LWWLWLBurnley.

2018-05-29 19:13:45
Hiiiuplb
"Dall&#8217;altra parte per&#242; c&#8217;&#232; una grande squadra, la migliore insieme ai nerazzurr." A parlare sono per&#242; i numeri: 649 gli uomini e 71 le donne alla partenza di Gto e 223 contro 28 per Out. "Il PalaNorda, che si preannuncia pronto a riempirsi e scaldarsi, aprirЁ¤ le porte per il match di domenica con fischio dЎЇinizio alle 18: le rossoblЁґ riceveranno lЎЇImoco Conegliano." [url=http://www.francautocorallo.it/siamo.asp?adit=adidas-sneaker-superstar]adidas sneaker superstar[/url] "Beh,sarebbe una &#8220;fine&#8221; niente male, avendo assaporato l&#8217;Europa League fino ai giro." #NAME? tute adidas donne "La notizia era nellЎЇaria, cЎЇerano solo le condizioni del croato da verificare, reduce comЎЇera da febbre alta e gastroenterite." "VertematiAgrigento: Vaughn 23, Mian 15, Chiarastella 9, Mocavero 15, Piazza 10, De Laurentis 2, Anello, Giunta, Di Viccaro, Giovanatto." [url=http://www.lanellodiresalomone.com/PAGINE.asp?adit=adidas-world]adidas world[/url] "punta dalla Ў°PЎ± maiuscola, che il suo Dna, con ogni probabilitЁ¤, invocherebbe giorno e notte." giacchette adidas "La classifica generale vede saldamente al comando Sportiello con648voti, allЎЇinseguimento - anche se staccatissimi - ci sono Biava e DramЁЁ con 175." "A questo punto si potr&#224; ricordare Yara Gambirasio, ma si vedr&#224; anche come reagir&#224; il ." zx camo [url=http://www.francautocorallo.it/siamo.asp?adit=adidas-barricade]adidas barricade[/url] " F1: Hamilton in poleAlonso 5Ўг, Vettel soltanto 13ЎгHamilton (in pole) al centro, alla sua destra Nico Rosberg(3Ўг) e alla sua sinistra Ricciardo (2Ўг)(Foto by DIEGO AZUBEL)Il britannico Lewis Hamilton (Mercedes) ha confermato le previsioni della vigiliaconquistando la prima pole position della stagione 2014 di F1 e domenica (il Gp in programma alle 7 , ore italiana, su Sky) partirЁ¤ davanti a tutti nel Gran PremiodЎЇAustralia."

Riferimento: http://www.leonardograssi.it/sitemap.xml

2018-05-25 15:19:39
Pdjvuqxdem
"De Gea was on the verge of a switch on the final day of last summers transfer window, only for a dea." Fulham had thrown away a 3-1 half-time lead to trail 4-3 before Ayite scored his second goal of the game from three yards when he converted a Tomas Kalas header. <a href=https://www.avpcbarbadas.com/D-puma-quarter-zip.html>puma quarter zip</a> Millers chief Stubbs said: I keep saying the same things every week and if it doesnt change Ill leave players out. "LIKELY LINE-UPSLudogorets (4-2-3-1): Borjan: Minev, Moti, Palomino, Natanael: Dyakov, Anicet: Cafu, ." <a href=http://www.sandrabalan.com/D-adidas-superstar-with-rainbow-stripes.html>adidas superstar with rainbow stripes</a> ola answers with exasperation at &#039;quadruple&#039; questionReuters7City skipper Vincent Kompany looks set for another spell on the sidelinesBut Juves Ўк50million price tag and the good progress being made by the injured Kompany meant they pulled the plug. Action Images via Reuters5Utd?defender Eric Bailly picks up a yellow card from ref Anthony Taylor at AnfieldThe defender said: I think we have more than enough to do well. <a href=http://tilodieng.co.za/buyshirt.php?p_id=good%20polo>good polo</a> "Although football is my grand passion, I must start to think about the future." "So what is the process, when can we expect an outcome and what punishment could be meted outSunSport looks at the FA disciplinary process."
Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

Какой вид спорта вы предпочитаете?
Футбол
28% (61)
Баскетбол
9% (20)
Волейбол
8% (18)
Теннис
5% (10)
Легкая атлетика
2% (5)
Хоккей
5% (11)
Лыжный спорт
3% (6)
Всеми
3% (7)
Другим
18% (38)
Я не дружу со спортом!
19% (41)

Проголосовало: 217
Разговор двух инeтчиков:
- Как ты думаешь чем рай отличаеться от ада?
- В раю просто есть интернeт!!!
Рейтинг: 9/10 (1)
Посмотреть все анекдоты