Пролог (язык программирования)

Пролог (англ. Prolog) — язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.

Пролог
Класс языка	Логическое программирование
Появился в	1972
Автор	Ален Колмероэ
Расширение файлов	.pl, .pro или .P
Основные реализации	B-Prolog, Ciao, ECLiPSe, GNU Prolog, Logic Programming Associates, Poplog Prolog, P#, Quintus, SICStus, Strawberry, SWI-Prolog, tuProlog, XSB, YAP-Prolog
Диалекты	ISO Prolog, Edinburgh Prolog, Turbo Prolog, Visual Prolog
Испытал влияние	Planner
Повлиял на	Visual Prolog, Mercury, Oz, Erlang, Strand, KL0, KL1, Datalog

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

Prolog является декларативным языком программирования: логика программы выражается в терминах отношений, представленных в виде фактов и правил. Для того чтобы инициировать вычисления, выполняется специальный запрос к базе знаний, на которые система логического программирования генерирует ответы «истина» и «ложь». Для обобщённых запросов с переменными в качестве аргументов созданная система Пролог выводит конкретные данные в подтверждение истинности обобщённых сведений и правил вывода.

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

Развитие

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

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

Язык Пролог в 1980-х годах был включён в ряд советских вузовских и школьных учебников информатики для изучения элементов математической логики, принципов логического программирования и проектирования баз знаний и моделей экспертных систем. С этой целью на IBM PC и ряде советских школьных компьютеров были реализованы учебные русскоязычные интерпретаторы Пролога.

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

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

Кроссплатформенность

Пролог реализован практически для всех известных операционных систем (ОС) и платформ (в том числе для Java и .NET). В число операционных систем входят: ОС для мейнфреймов, всё семейство Unix, Windows, ОС для мобильных платформ.

Архитектура

Многие современные реализации языка имеют внутреннее расширение за счёт ООП-архитектуры. Кроме несвободных решений также существуют свободные реализации Пролога. В 1996 году был принят стандарт ISO, получивший название ISO/IEC JTC1/SC22/WG17.

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

Синтаксис

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

В языке пролог исходное множество формул, для которого ищется пустая резольвента, представляется в виде так называемых «дизъюнктов Хорна»:

Термы

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

 atom
 'Atom'

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

 X is 2 + 2.

Структуры представляют собой совокупности термов, заключённые в круглые скобки, в том числе и другие структуры. Структура обозначается именем (функтором), которое располагается перед круглыми скобками.

 book( 'Название', '2009', 'Спб', authors( 'Первый автор', 'Второй автор' ) ).

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

 List = [ a, b, [ c, d ], e ].

Правила

Правила в Прологе записываются в форме правил логического вывода с логическими заключениями и списком логических условий. В чистом Прологе предложения ограничиваются дизъюнктами Хорна:

 Вывод :- Условие.

и читаются так: «Заголовок ИСТИНА, если тело ИСТИНА». Тело правила содержит ссылки на предикаты, которые называются целями правила.

Встроенные предикаты

,/2

Значение: оператор с двумя аргументами. Определяет конъюнкцию целей.

;/2

Оператор определяет дизъюнкцию.

Факты

Факты в языке Пролог описываются логическими предикатами с конкретными значениями. Факты в базах знаний на языке Пролог представляют конкретные сведения (знания). Обобщённые сведения и знания в языке Пролог задаются правилами логического вывода (определениями) и наборами таких правил вывода (определений) над конкретными фактами и обобщёнными сведениями. Предложения с пустым телом называются фактами. Пример факта:

 Кот( Иван ).

Этот факт эквивалентен правилу:

 Кот( Иван ) :- ИСТИНА.

Критика

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

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

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

Примеры

Hello World

?- write('Hello world!'), nl.
Hello world!
true.
 
?-

Brother

parent("Tom","Jake").
parent("Janna","Jake").
parent("Tom","Tim").
male("Tom").
male("Tim").
male("Jake").
female("Janna").

brother(X,Y):-
parent(Z,X),parent(Z,Y),male(X),X\=Y.

Вывод: (Jake, Tim) (Tim, Jake)

Старший

старше("Пётр", "Иван"). 
старше("Василий", "Тимофей"). 
старше("Тимофей", "Пётр").

старше(X, Y) :- старше(X, Z), старше(Z, Y).

? старше("Тимофей", V).
? старше(U, "Пётр").
? старше(U, V).

Выводы: 1. Тимофей старше Ивана 2. Василий старше Петра 3. Иван-самый младший; Василий — самый старший; Тимофей старше Петра.

См. также

• Лисп — функциональный язык программирования.

Литература

• Анатолий Адаменко, Андрей Кучуков. Логическое программирование и Visual Prolog (с CD). — СПб.: БХВ-Петербург, 2003. — 990 с. — ISBN 5-94157-156-9.
• Иван Братко. Алгоритмы искусственного интеллекта на языке PROLOG = Prolog Programming For Artificial Intelligence. — М.: Вильямс, 2004. — 640 с. — ISBN 0-201-40375-7.
• Карпов Ю.Г. Теория автоматов. — СПб, 2003. — 206 с. — ISBN 5-318-00537-3.
• Марков В. Н. Современное логическое программирование на языке Visual Prolog 7.5: учебник. — СПб.: БХВ-Петербург, 2016. — 544 с. — ISBN 978-5-9775-3487-1
• Маллас Дж. Реляционный язык Пролог и его применение. — М.: Наука, 1990. — 464 с. — ISBN 5-02-014509-2.

Стандарты

• ISO/IEC 13211-1:1995 Information technology — Programming languages — Prolog — Part 1: General core
• ISO/IEC 13211-2:2000 Information technology — Programming languages — Prolog — Part 2: Modules

Ссылки

• Статья Prolog в Прогопедии
• Международный стандарт ISO для языка Пролог