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



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





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




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

Язык логического программирования 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]Кол-во просмотров: 9514

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

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

2018-04-20 21:21:20
Ctfmetav
He’s missed some time in the preseason, but that’s most likely a product of the organization being cautious with what is by far their most valuable asset.; decision now must be made before several hundred in a cramped studio, and the millions watching at home.Reigning Champions - April 9, 2018Twins Win Home Opener, Open Homer Wonder - April 6, 2018.
[url=http://pramayenterprises.com/swe.asp?p_id=cement-jogger-pants]cement jogger pants[/url]
[url=http://pramayenterprises.com/swe.asp?p_id=kevin-durant-shoes-grey]kevin durant shoes grey[/url]

Maryland has won home games over Illinois, Indiana, and Rutgers as well.This was especially true when the Lions lost Liam Williams at a critical point in the match for taking out a Blues player in the air twice over a short period of time.
The Astros need a top-tier pitcher for their rotation, the Pirates would like another ace to pair wi.

2018-04-20 16:52:44
HrafdceUnery
get best results cialis cialis store in dubai only here candian cialis
п»ї<a href="http://jvrimages.com/">cialis 20 mg</a> the price of cialis in mexico cialis pakistan price cialis alle erb
buy legal fda approved cialis the cialis costume hat visit web site homemade cialis
http://jvrimages.com/#cialis+official+site cialis prix inde cialis phone number cialis cialis panorama

2018-04-19 21:29:07
Kcxzrurj
Will his age (33 next June) be a barrier to sustainable success, power or otherwise.That is, until Ramos popped up on injury reports as well.Singleton’s scouting grades: Hit: 60, Power: 60, Run: 30, Arm: 40, Field: 50, Overall: 55Duffy’s sco.
[url=http://www.4designlearn.com/home.asp?p_id=lebron-1-red]lebron 1 red[/url]
[url=http://www.4designlearn.com/home.asp?p_id=air-jordan-13]air jordan 13[/url]

If Darlington is forced to start at quarterback, Lamar Jackson will likely become the backup QB.Steelers Franchise Bell, Extend Brown - The Runner Sports.
However, the same cannot be said about Joe Girardi.

2018-04-19 06:30:11
Bfrzhfmm
&#8221;Astros broadcaster Robert Ford: &#8220;At a loss for words after learning about the death of José Fernández.It is too early to tell if the new-look Cavaliers will be able to challenge the behemoth that the Warriors have become.Despite his natural strength and power potential, Moran doesn’t swing for the fences, focusing on ma.
[url=http://www.hassan-ibrahim.com/home.asp?p_id=kevin-durant-9-shoes]kevin durant 9 shoes[/url]
[url=http://www.hassan-ibrahim.com/home.asp?p_id=lebron-13-buy-shoes]lebron 13 buy shoes[/url]

Although the last two years has seen theВ Bucs struggle against backup quarterbacks.Kasperi Kapanen put a backhander through Braden Holtby for a tie score, a goal that withstood a coach&#8217;s challenge for offsides.
Other Current Roster Options:The one thing about a LeBron James team is you always have another ball-handler in James.

2018-04-18 04:05:38
Lspyblwt
Barring injuries, this could be the best Eastern Conference game in the first month of the season.Cole&#8217;s addition to the Houston roster suddenly turns a starting rotation from a strong one tha.&nbsp;**Special thanks toВ Pitcher ListВ for allowing the use of their videos in this article.
[url=http://www.edwinngo.com/Thank.asp?p_id=kd-shoes-womens-orange]kd shoes womens orange[/url]
[url=http://www.edwinngo.com/Thank.asp?p_id=jordan-10-doernbecher]jordan 10 doernbecher[/url]

The toughest test during this stretch was at Virginia Tech, where the Hokies played UNC close the entire game before falling 75-70.&#8220;Sutes&#8221;Suter was injured in the Wild&#8217;s game against the Dallas Stars Saturday when.
You won&#8217;t get much in the trade market for Estrada, Bautista, or Martin.

2018-04-17 09:52:09
Qjlgccrr
2017 Starting Rotation:LHP John LesterRHP Kyle HendricksRHP Jake ArrietaRHP John LackeyLHP Mike Montgomery&nbsp;Losing: Aroldis Chapman, Closer.For a team who says that they want to get younger, bringing in a player who will be 40 next April is contradicting.g games on his own, anyway, so it would be best for his career and the Lakers’ future if they two of them split paths.
[url=http://www.kigalibusservices.com/Pages/Career.asp?p_id=vans-ski-trousers]vans ski trousers[/url]
[url=http://www.eesofttech.com/Management.asp?p_id=vans-authentic-gris]vans authentic gris[/url]

If Fischer can get additional playing time at the NHL level, he should be able to break into the starting roster lineup for next season.He has also had 20 caps for Scotland with six tries.
3,905), about 55 miles southwest of Houston, and enjoys fishing in his free time.

2018-04-17 04:44:41
Naydbfgr
sene-maulIvory Coast vs Senegal abandoned in 88th minute after player is rugby tackled by pitch inva.Getty Images4Sam Allardyce&#8217;s side were hammered at home to Sunderland with fans turning on the.
Getty Images7Jose Mourinho in the summer digged at Liverpool as he said they were to small for someo."der as fans sneak into stadiumSHAW NO CERTAINTYGareth Southgate tells Luke Shaw he must start playing for Manchester United to regain England spotKylian Me SoftlySergio Ramos tells Kylian Mbappe he is welcome at Real Madrid ahead of France vs Spain friendlyRAHEEM RECOVERYRaheem Sterling is fit for Manchester City&#039;s crunch Premier League clash at Arsenal#pogdaddyLoving son Paul Pogba visits dad Fassou Antoine in hospital to celebrate his 79th birthday after Frenchman is ruled out of Spain friendly through injuryFeeling smallInjured Chris Smalling looks down in the dumps after limping away from restaurant with his leg brace onHit the Gym, JackGareth Southgate warns Jack Wilshere to prove his fitness if he wants to win back an England spotCHILLINGNo time for cold feet as SunSport visit Fulham&#039;s training ground for a spot of cryotherapy treatmentICE COOL KIDJermain Defoe reveals cryotherapy chamber sessions are helping him stay young but his mum is ruining vegan diet by serving up meatUNITED RANT BOYSPolice are investigating Manchester United fans for homophobic chanting at ChelseaZaha had &#039;no passion&#039;Gareth Southgate sensationally claims Wilfried Zaha did not have the heart to play for England United are understood to prefer a permanent move for Depay as Mourinho looks to release funds to bring in players himself."
[url=http://www.spyndi.fr/France-doudoune-u5691-hommes-moncler-doudounes-lapin-cafГ©-chapeau--grande-marque-pas-cher-Lille,boutique-pas-cher-Lille-Moncler-Lyon-cv126.html]moncler lyon[/url]
[url=http://www.sfcrea.fr/C-adidas-superstar-sneakers.html]adidas superstar sneakers[/url]

West Ham could also be in the hunt and Wilshere is believed to have a soft spot for the club as kid after?once sharing a picture of him in Hammers colours on social media.Yet Arsenals only major signing so far this summer is Swiss midfielder Granit Xhaka.
[url=http://www.rovlicensing.com/Main.asp?Featured=nike-run-roshe-nere]nike run roshe nere[/url]

2018-04-17 03:01:07
Frswdtko
"On top of that Belgium international Benteke, 26, cost Palace Ўк27m from Liverpool in July and more s.""Sub Rooneys 250th United goal took him past Sir Bobby Charlton, who was at Stoke to see the end of his 44-year reign as the clubs greatest scorer."
"So I said, &#8220;You hum it, I&#8217;ll play itmheathsmith19th November 201612:49 pmFirst yellow of."related storiesTEAM NEWSSergio Aguero starts as Pep Guardiola leaves Kevin De Bruyne on bench and Jo.
[url=http://www.sfcrea.fr/C-basket-adidas-homme-stan-smith.html]basket adidas homme stan smith[/url]
[url=http://www.sfcrea.fr/C-adidas-tennis.html]adidas tennis[/url]

The Belgian forward is in superb form with 16 goals in his last 15 appearances."However, more importantly to most fans, United legend Gary Nevillle?emphasised the importance of the."
[url=http://www.roserviceingurgaon.in/ro.php?vendita=nike-roshe-run-safari]nike roshe run safari[/url]

2018-04-16 18:29:29
Velqzdgg
Getty Images1Wayne Rooney has been benched for United&#8217;s EFL Cup Final against SouthamptonRooney was struggling for fitness in a week where he rejected interest from China."There was no other way, because if theyre not going to change, I had to change."
"reak with glamorous wife ElisabettaEngland 88 Chelsea 0Nathaniel Chalobah is about to make his 88th youth cap and still hasn&#039;t played for ChelseaSPECIAL GIANTeen sensation Gianluigi Donnarumma to be offered new deal as Chelsea and Man Utd circleFrench flightMan United and Chelsea summer target Blaise Matuidi admits he wanted to leave Paris Saint-GermainAymen HigherChelsea and Everton target Aymen Abdennour confirms he held transfer talks with English clubs Getty Images5Lindelof has been capped six times by SwedenGetty Images5The Blues allegedly face stiff competition from Paris Saint-Germain and Inter MilanAt 29, Luiz is no spring chicken either, and Chelsea will be keen to ensure they have safeguards in place when Conte decides to ring the changes."Reuters4Chelsea struggled to break down West Brom&#8217;s stubborn defenceKeep up to date with ALL t.
[url=http://www.sfcrea.fr/C-chaussure-pas-cher-adidas.html]chaussure pas cher adidas[/url]
<a href="http://www.guardian-protection.fr/T-shirts-Adidas-T-S4684-(SurvГ©tement-Adidas)-DE8780.html" alt="survГ©tement adidas">survГ©tement adidas</a>

Everton boss Ronald Koeman - who has been robbed of his star players services for this season and beyond - also made contact with the Donegal man to check on him.Barcelona visit Paris Saint-Germain in the quarter-final of the Champions LeagueThe Sun.
[url=http://www.roserviceingurgaon.in/ro.php?vendita=ctr360-nike-id]ctr360 nike id[/url]

2018-04-16 16:44:38
Vkfjkypb
Pulis has previously been given a heros reception by Palace fans after saving the club from? relegat." is set to miss the whole of February with suspected knee ligament damageHowever a boost for Spurs is that Kieran Tripper looks to have recovered from his own hip problem, but isnt expect to start in front of the in-form Kyle Walker."
"am &#8211; LWWLWBurnley &#8211; LLWLLYour sayWhere can I watch itUnfortunately, the game will not be broadcast live, but highlights will be shown on Match Of The Day 2 on Monday, December 19 at 10."Liverpool have scored 40 goals in their 14 competitive games so far this season ЁC their best tally after 14 games since 1895-96 (48 goals).
[url=http://www.maink.it/Vendita-Negozio-Piumini-Pregevole-Moncler-Hip-Hop-Donna-Euchore-Marca-Popolare-Piumino-Moncler-Originale-TT1450.html]piumino moncler originale[/url]
[url=http://www.krizzee.com/Outlet-Training-Zapatillas-Jordan-Flight-Flex-Trainer-NiГ±os-54956002-Negro-Rojo-Anthracite-Osc-Tenis-Jordan-Flight-23-TT1045.html]tenis jordan flight 23[/url]

Mancienne&#8217;s misery was then compounded when he was sent off late on.laim Marca but Real Madrid&#8217;s loss would certainly be a Premier League clubs gain and with just two and bit weeks left until the deadline of the transfer window is there to be a huge deal still before it closes.
[url=http://www.rovlicensing.com/Main.asp?Featured=nike-mercurial-2009]nike mercurial 2009[/url]
Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

Какой жанр комп. игр вам нравится?
Стратегии
24% (55)
Action
17% (39)
RPG
36% (82)
RTS
1% (3)
Симуляторы
8% (18)
Квесты
7% (15)
Логические
3% (6)
Другой
5% (11)

Проголосовало: 229
Программистское народное ругательство: motherhacker!
Рейтинг: 5/10 (3)
Посмотреть все анекдоты