Это самый необычный язык, с которым мне когда-либо приходилось сталкиваться. Существует мнение, что тексты программ на Прологе ближе к человеческому мышлению, нежели тексты программ на императивных языках (C, Pascal и др.). Не верьте этому. Пролог является скорее головоломкой, чем языком программирования, а процесс создания программ очень похож на разгадывание кубика-рубика.
Пролог — язык для фанатов рекурсии и головоломок. В нём нет циклов, но это не спасает от зацикливания (пример с лабиринтом ниже). В основе императивных языков лежит алгоритм, который можно описать блок-схемой или псевдокодом. В Прологе алгоритм не нужен, но это только на первый взгляд.
Вам надо написать такой набор логических рассуждений (как правило рекурсивных), который при обработке интерпретатором превращается в алгоритм. Это одновременно баг и фича языка.
Говорят, что писать программы на Прологе намного сложнее, чем читать их. Так оно и есть, я проверил. Знакомство с этим языком я советую начать со статьи на хабре. Нет, правда, отличная статья!
Три примера решения задачек на Прологе
Зачем это нужно?
Это эзотерический язык, не более. Поиск на гитхабе не выдаёт каких-либо значимых проектов. Пролог может быть интересен программистам, которые любят головоломки. Но я бы советовал не спешить, ведь есть более заманчивые языки: Haskel, Lisp или Ассемблер. Да и вообще не стоит забывать, что жизнь — это не только программирование 🙂
Есть узкий класс задач, для которых Пролог хорошо подходит. Например, с его помощью можно быстренько решить какую-нибудь логическую задачку (загадка Эйнштейна, поиск путей на графе, обход лабиринта и т.д.). Всё остальное проще запрогать на not(prolog) . Потому что глупо представлять строчку текста в виде бинарного дерева.
У меня Пролог был в ВУЗе на курсе искусственного интеллекта. Студентам, которых заставляют изучать этот язык, я сочувствую. Писать программы сложно. Классика жанра — конкатенация двух списков, всего две строчки кода. Я не смог самостоятельно реализовать это за три часа.
С другой стороны, когда долго над чем-то сидишь и наконец-то оно заработало… хочется улыбаться.
Пролог привлекает прежде всего своей необычностью. Думай рекурсивно, забудь про циклы!
Нам понадобится…
Насколько мне известно, самым популярным интерпретатором является SWI-Prolog. Еще встречаются GNU Prolog и Visual Prolog. Для установки под Windows идем на сайт проекта. Под линуксом достаточно установить пакет swi-prolog .
Писать программы можно в любом редакторе. Подсветка синтаксиса есть в Kate, Gedit, Medit, Sublime Text через плагин, наверняка Vim и Emacs. Редакторы ошибочно могут определять язык как Perl из-за расширения .pl .
Забавный пример
Я хочу подкинуть камень в огород Пролога. То счастье, которое нам обещают маркетологи, запросто может оказаться источником геморроя. Вот пример, выглядящий безобидно:
/* описываем конфигурацию лабиринта: */ door(1, 2). %существует дверь из первой во вторую комнаты door(2, 3). %из второй в третью и т. д. door(3, 4). /* … */ door(1, 4).
door(X, Y):-door(Y, X). %если есть дверь из Y в X, то есть дверь из X в Y
Пролог — попытка объяснить без программирования
Поначалу код работает так, как от него ожидается:
?- door(2, 3). true ?- door(3, 2). true
Но если спросить у интерпретатора о существовании прохода, которого на самом деле нет…
?- door(99, 100).
…то он ничего не сможет ответить, потому что войдет в ступор зациклится. Чтобы понять, почему так происходит, вводим команду trace . Она поможет отследить, что же на самом деле делает интерпретатор и почему так происходит. Очень помогает при написании программ, берите на заметку.
[trace] ?- door(99, 100). Call: (6) door(99, 100) ? creep Call: (7) door(100, 99) ? creep Call: (8) door(99, 100) ? creep Call: (9) door(100, 99) ? creep Call: (10) door(99, 100) ?
Что тут происходит? Не находя ответа в базе фактов, интерпретатор переходит к предикату door(X, Y):-door(Y, X). и пытается его удовлетворить новым проходом по базе фактов, затем снова цепляется за предикат, и т.д. Бесконечная рекурсия или зацикливание?
Правильный ответ — рекурсия, ведь в Прологе нет циклов! Я так и не смог придумать как исправить предикат, чтобы он работал правильно.
Полезные ссылки
- Книга Ивана Братко в HTML рассказывает всё об этом языке.
- Видеокурс по логическому программированию хорош тем, что много говорится о парадигме и идеях, лежащих в основе языка, да и программировании как таковом.
- Базовые предикаты — исходники простеньких задачек.
- Ещё несколько примеров.
- Форум, посвященный Прологу. Здесь можно и помощи попросить.
- Если вам понравился Пролог, то советую почитать GEB.
А ещё тут есть три разных оператора “равно”: = , =:= , is .
Все статьи
- Строгий календарь 2022
- Строгий календарь 2021
- Ушёл в отпуск
- Осваиваем мониторинг с Prometheus. Часть 3. Настройка Prometheus server
- Строгий календарь 2020
- Осваиваем мониторинг с Prometheus. Часть 2. PromQL и метки
- Осваиваем мониторинг с Prometheus. Часть 1. Знакомство и установка
- Ускоряем установку пакетов в Debian (libeatmydata)
- Строгий календарь 2019
- Оконный менеджер i3
- Строгий календарь 2018
- Мой лончер на базе Dmenu
- Как случайно не выключить сервер по ssh
- Делаем загрузочный образ из контейнера
- Использование утилиты debootstrap
- Запускаем Debian в chroot-окружении
- Строгий календарь 2017
- Запускаем Debian в контейнере systemd-nspawn
- Ручная установка минимального Debian-based Linux (Install Debian the Archlinux way)
- Trap — обработка сигналов и ошибок в Bash
- Мои впечатления от Gentoo Linux
- Жизнь с комфортом в Openbox WM
- Гистограммы в гнуплоте
- Особенности гнуплота под Windows
Источник: laurvas.ru
Язык программирования Пролог
Данную лекцию нужно рассматривать не как учебник по языку Пролог , а только как краткий «ликбез», который служит для иллюстрации принципов продукционного программирования, описанных выше.
Синтаксис
ТЕРМЫ
Объекты данных в Прологе называются термами . Терм может быть константой, переменной или составным термом (структурой). Константами являются целые и действительные числа, например:
(некоторые реализации Пролога не поддерживают действительные числа).
К константам относятся также атомы, такие, как:
голди, а, атом, +, :, ‘Фред Блогс’, [] .
Атом есть любая последовательность символов, заключенная в одинарные кавычки. Кавычки опускаются, если и без них атом можно отличить от символов, используемых для обозначения переменных. Приведем еще несколько примеров атомов:
Полный синтаксис атомов описан ниже.
Как и в других языках программирования, константы обозначают конкретные элементарные объекты, а все другие типы данных в Прологе составлены из сочетаний констант и переменных.
Имена переменных начинаются с заглавных букв или с символа подчеркивания «_». Примеры переменных:
X, Переменная, _3, _переменная .
Если переменная используется только один раз, необязательно называть ее. Она может быть записана как анонимная переменная, состоящая из одного символа подчеркивания «_». Переменные, подобно атомам, являются элементарными объектами языка Пролог.
Завершает список синтаксических единиц сложный терм, или структура. Все, что не может быть отнесено к переменной или константе, называется сложным термом. Следовательно, сложный терм состоит из констант и переменных.
Теперь перейдем к более детальному описанию термов.
КОНСТАНТЫ
Константы известны всем программистам. В Прологе константа может быть атомом или числом.
ATOM
Атом представляет собой произвольную последовательность символов, заключенную в одинарные кавычки. Одинарный символ кавычки, встречающийся внутри атома, записывается дважды. Когда атом выводится на печать, внешние символы кавычек обычно не печатаются. Существует несколько исключений, когда атомы необязательно записывать в кавычках. Вот эти исключения:
Заметим, что атом, начинающийся с /* , будет воспринят как начало комментария, если он не заключен в одинарные кавычки.
Как правило, в программах на Прологе используются атомы без кавычек.
Атом, который необязательно заключать в кавычки, может быть записан и в кавычках. Запись с внешними кавычками и без них определяет один и тот же атом.
Внимание: допустимы случаи, когда атом не содержит ни одного символа (так называемый ‘нулевой атом’) или содержит непечатаемые символы. (В Прологе имеются предикаты для построения атомов, содержащих непечатаемые или управляющие символы.) При выводе таких атомов на печать могут возникнуть ошибки.
ЧИСЛА
Большинство реализации Пролога поддерживают целые и действительные числа. Чтобы выяснить, каковы диапазоны и точность чисел, следует обратиться к руководству по конкретной реализации.
ПЕРЕМЕННЫЕ
Понятие переменной в Прологе отличается от принятого во многих языках программирования. Переменная не рассматривается как выделенный участок памяти. Она служит для обозначения объекта, на который нельзя сослаться по имени. Переменную можно считать локальным именем для некоторого объекта.
Синтаксис переменной довольно прост. Она должна начинаться с прописной буквы или символа подчеркивания и содержать только символы букв, цифр и подчеркивания.
Переменная, состоящая только из символа подчеркивания, называется анонимной и используется в том случае, если имя переменной несущественно.
ОБЛАСТЬ ДЕЙСТВИЯ ПЕРЕМЕННЫХ
Областью действия переменной является утверждение. В пределах утверждения одно и то же имя принадлежит одной и той же переменной. Два утверждения могут использовать одно имя переменной совершенно различным образом. Правило определения области действия переменной справедливо также в случае рекурсии и в том случае, когда несколько утверждений имеют одну и ту же головную цель. Этот вопрос будет рассмотрен далее.
Единственным исключением из правила определения области действия переменных является анонимная переменная, например, «_» в цели любит (Х,_) . Каждая анонимная переменная есть отдельная сущность. Она применяется тогда, когда конкретное значение переменной несущественно для данного утверждения. Таким образом, каждая анонимная переменная четко отличается от всех других анонимных переменных в утверждении.
Переменные, отличные от анонимных, называются именованными , а неконкретизированные (переменные, которым не было присвоено значение) называются свободными .
СЛОЖНЫЕ ТЕРМЫ, ИЛИ СТРУКТУРЫ
Структура состоит из атома, называемого главным функтором , и последовательности термов, называемых компонентами структуры. Компоненты разделяются запятыми и заключаются в круглые скобки.
Приведем примеры структурированных термов:
Число компонент в структуре называется арностью структуры. Так, в данном примере структура собака имеет арность 1 (записывается как собака/1 ), а структура родитель — арность 2 ( родитель/2 ). Заметим, что атом можно рассматривать как структуру арности 0.
Для некоторых типов структур допустимо использование альтернативных форм синтаксиса. Это синтаксис операторов для структур арности 1 и 2, синтаксис списков для структур в форме списков и синтаксис строк для структур, являющихся списками кодов символов.
СИНТАКСИС ОПЕРАТОРОВ
Структуры арности 1 и 2 могут быть записаны в операторной форме, если атом, используемый как главный функтор в структуре, объявить оператором (см. «Логический подход к построению систем ИИ» ).
СИНТАКСИС СПИСКОВ
В сущности, список есть не что иное, как некоторая структура арности 2. Данная структура становится интересной и чрезвычайно полезной в случае, когда вторая компонента тоже является списком. Вследствие важности таких структур в Прологе имеются специальные средства для записи списков.
СИНТАКСИС СТРОК
Строка определяется как список кодов символов. Коды символов имеют особое значение в языках программирования. Они выступают как средство связи компьютера с внешним миром. В большинстве реализации Пролога существует специальный синтаксис для записи строк. Он подобен синтаксису атомов.
Строкой является любая последовательность символов, которые могут быть напечатаны (кроме двойных кавычек), заключенная в двойные кавычки. Двойные кавычки в пределах строки записываются дважды «».
В некоторых реализациях Пролога строки рассматриваются как определенный тип объектов подобно атомам или спискам. Для их обработки вводятся специальные встроенные предикаты. В других реализациях строки обрабатываются в точности так же, как списки, при этом используются встроенные предикаты для обработки списков. Поскольку все строки могут быть определены как атомы или как списки целых чисел, и понятие строки является чисто синтаксическим, мы не будем более к нему возвращаться.
УТВЕРЖДЕНИЯ
Программа на Прологе есть совокупность утверждений. Утверждения состоят из целей и хранятся в базе данных Пролога. Таким образом, база данных Пролога может рассматриваться как программа на Прологе. В конце утверждения ставится точка «.». Иногда утверждение называется предложением.
Основная операция Пролога — доказательство целей, входящих в утверждение.
Существуют два типа утверждений:
- факт — это одиночная цель, которая, безусловно, истинна;
- правило — состоит из одной головной цели и одной или более хвостовых целей, которые истинны при некоторых условиях.
Правило обычно имеет несколько хвостовых целей в форме конъюнкции целей.
Конъюнкцию можно рассматривать как логическую функцию И. Таким образом, правило согласовано, если согласованы все его хвостовые цели.
собака (X) :- родитель (X.Y),собака (Y). человек(Х) :-мужчина(Х) .
Разница между правилами и фактами чисто семантическая. Хотя для правил мы используем синтаксис операторов (более подробное рассмотрение операторного и процедурного синтаксисов выходит за рамки нашего курса), нет никакого синтаксического различия между правилом и фактом.
собака (X) :- родитель(Х,У),собака(У) . может быть задано как
:-собака (X) ‘,’ родитель(Х.У) .собака (Y) .
Запись верна, поскольку :- является оператором «при условии, что» , а ‘,’ — это оператор конъюнкции. Однако удобнее записывать это как
собака ( X ) :-родитель ( X.Y ),собака ( Y ).
и читать следующим образом: » Х — собака при условии, что родителем Х является Y и Y — собака».
Структуру иногда изображают в виде дерева, число ветвей КОТОРОГО равно арности структуры.
ЗАПРОСЫ
После записи утверждений в базу данных вычисления могут быть инициированы вводом запроса.
Запрос выглядит так же, как и целевое утверждение, образуется и обрабатывается по тем же правилам, но он не входит в базу данных (программу). В Прологе вычислительная часть программы и данные имеют одинаковый синтаксис. Программа обладает как декларативной, так и процедурной семантикой . Мы отложим обсуждение этого вопроса до последующих лекций. Запрос обозначается в Прологе утверждением ?- , имеющим арность 1. Обычно запрос записывается в операторной форме: за знаком ?- следует ряд хвостовых целевых утверждений (чаще всего в виде конъюнкции).
Приведем примеры запросов:
?-собака(X). ?- родитель(Х.У),собака (Y) .
‘?-‘(собака(Х)) С?-‘) ‘,'(родитель(Х„У»,собака (Y)) .
Последняя запись неудобна тем, что разделитель аргументов в структуре совпадает с символом конъюнкции. Программисту нужно помнить о различных значениях символа ‘,’.
Запрос иногда называют управляющей командой (директивой), так как он требует от Пролог-системы выполнения некоторых действий. Во многих реализациях Пролога для управляющей команды используется альтернативный символ, а символ ?- обозначает приглашение верхнего уровня интерпретатора Пролога. Альтернативным символом является :- . Таким образом,
— это управляющая команда, в результате выполнения которой печатается атом собака. Управляющие команды будут рассмотрены ниже при описании ввода программ.
ВВОД программ
Введение списка утверждений в Пролог-систему осуществляется с помощью встроенного предиката consult . Аргументом предиката consult является атом, который обычно интерпретируется системой как имя файла, содержащего текст программы на Прологе. Файл открывается, и его содержимое записывается в базу данных. Если в файле встречаются управляющие команды, они сразу же выполняются.
Возможен случай, когда файл не содержит ничего, кроме управляющих команд для загрузки других файлов. Для ввода утверждений с терминала в большинстве реализации Пролога имеется специальный атом, обычно user. С его помощью утверждения записываются в базу данных, а управляющие команды выполняются немедленно.
Помимо предиката consult , в Прологе существует предикат reconsult . Он работает аналогичным образом. Но перед добавлением утверждений к базе данных из нее автоматически удаляются те утверждения, головные цели которых сопоставимы с целями, содержащимися в файле перезагрузки. Такой механизм позволяет вводить изменения в базу данных. В Прологе имеются и другие методы добавления и удаления утверждений из базы данных. Некоторые реализации языка поддерживают модульную структуру, позволяющую разрабатывать модульные программы.
В заключение раздела дадим формальное определение синтаксиса Пролога, используя форму записи Бэкуса-Наура, иногда называемую бэкусовской нормальной формой ( БНФ ).
запрос ::- голова утверждения правило ::– голова утверждения :- хвост утверждения факт ::- голова утверждения голова утверждения ::-атом | структура хвост утверждения ::- атом структура, термы ::-терм [,термы] терм ::- число | переменная | атом | структура структура ::-атом (термы)
Данное определение синтаксиса не включает операторную, списковую и строковую формы записи.
Полное определение дано в приложении А . Однако, любая программа на Прологе может быть написана с использованием вышеприведенного синтаксиса. Специальные формы только упрощают понимание программы. Как мы видим, синтаксис Пролога не требует пространного объяснения. Но для написания хороших программ необходимо глубокое понимание языка.
Источник: intuit.ru
6: Сентенциальное программирование: PROLOG
Привет, Вы узнаете про сентенциальное программирование, Разберем основные ее виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое сентенциальное программирование, prolog , настоятельно рекомендую прочитать все из категории Стили и методы программирования.
Общие концепции
Язык логического программирования 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 .
В любой момент исполнения программы база данных и база знаний могут быть модифицированы.
Теперь перейдем к конкретному представлению данных.
В конкретном синтаксисе переменные языка представлены именами, состоящими из букв и начинающимися с большой буквы либо с символа подчеркивания _. Переменная _ называется анонимной переменной и считается различной во всех своих вхождениях.
Константы языка PROLOG 2 в конкретном синтаксисе делятся на имена (идентификаторы, начинающиеся с маленькой буквы либо совокупность нескольких специальных символов типа
‘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].
Для обозначения присоединения нескольких данных термов к началу списка имеется стандартная операция
Строки рассматриваются как линейные списки кодов символов и обозначаются последовательностью символов, взятой в двойные кавычки:
«Ну, получили то, что искали? Ответьте 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 — константы, а латинские буквы из конца алфавита — переменные, унифицируются в
подстановкой
А в двух последовательностях
никакие два соответственных выражения унифицированы быть не могут.
Уже в приведенном примере видно, что унификация — глобальная операция.
Заметим, что логический алгоритм унификации обладает свойством частичного исполнения: если унифицировать две подструктуры, то после исполнения унифицирующей подстановки можно продолжить унификацию остальных подструктур, и результат унификации не изменится . Об этом говорит сайт https://intellect.icu . Так что выражения могут унифицироваться одно за другим
Более того, можно было бы унифицировать любые соответственные друг другу внутренние подвыражения в произвольном порядке, лишь бы объемлющие унифицировались после подчиненных. Автору неизвестно ни одно использование этого естественного и многообещающего обобщения алгоритма унификации.
В первой реализации языка PROLOG, основные особенности которой стали в дальнейшем фактическим стандартом, создатели допустили ошибку в понимании и, соответственно, в реализации алгоритма унификации, которая, к примеру, разрушает свойство частичного исполнения и может привести к излишней конкретизации, в то время как можно было бы найти более общую конкретизирующую подстановку. Эта ошибка несущественна, она не влияет на подавляющее большинство программ, но иногда она приводит к появлению бесконечных термов, и некоторые реализаторы языка PROLOG с гордостью пишут, что они умеют печатать и показывать на экране даже такие термы.
Желающие в качестве упражнения выловить ошибку самостоятельно, сравните алгоритмы унификации, описанные в книге [ 30 ] и [ 12 ] .
Рассмотрим, как исполняется программа на языке 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).
Источник: intellect.icu