Пролог (англ. 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-м годам.[1] Будучи декларативным языком программирования, Пролог воспринимает в качестве программы некоторое описание задачи или баз знаний и сам производит логический вывод, а также поиск решения задач, пользуясь механизмом поиска с возвратом и унификацией.
Интерес к Прологу поднимался и затихал несколько раз, энтузиазм сменялся жёстким неприятием. Наиболее высоко был поднят интерес к языку Пролог, как к языку будущего, во время разработок японской национальной программы компьютеры пятого поколения в 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
- Оператор определяет дизъюнкцию.
Факты
правитьФакты в языке Пролог описываются логическими предикатами с конкретными значениями. Факты в базах знаний на языке Пролог представляют конкретные сведения (знания). Обобщённые сведения и знания в языке Пролог задаются правилами логического вывода (определениями) и наборами таких правил вывода (определений) над конкретными фактами и обобщёнными сведениями. Предложения с пустым телом называются фактами. Пример факта:
Кот( Иван ).
Этот факт эквивалентен правилу:
Кот( Иван ) :- ИСТИНА.
Критика
правитьПролог критикуется, в первую очередь, за неполную декларативную природу: создание сколько-нибудь сложных и практически полезных Пролог-программ в полностью декларативном стиле практически невозможно, программист вынужден прибегать к процедурным приёмам, что приводит к резкому возрастанию сложности создания и отладки программ, а также плохой контролируемости промежуточных результатов.[2]
Другим часто подвергаемым критике свойством языка является отсутствие типизации (при этом в Visual Prolog[3] — одном из объектно-ориентированных расширений языка — реализована строгая типизация, что, однако, снижает гибкость пролога).
В языке предопределён порядок обхода дерева решений «в глубину» и стандартизированы операторы, позволяющие вмешиваться в этот процесс (такие как оператор отсечения !
или ветвления ->
). Такая архитектура затрудняет автоматическое распараллеливание программ, которое позволило бы задействовать в поиске решения несколько процессоров или узлов сети.
Примеры
править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. Иван-самый младший; Василий — самый старший; Тимофей старше Петра.
См. также
править- Лисп — функциональный язык программирования.
Примечания
править- ↑ История языка Prolog . Дата обращения: 4 сентября 2004. Архивировано из оригинала 25 ноября 2004 года.
- ↑ Себеста Р.У. Основные концепции языков программирования = Concepts of programming languages. — 5-е изд. — М.: Вильямс, 2001. — ISBN 5-8459-0192-8.
- ↑ А также его прямом предшественнике Turbo Prolog
Литература
править- Анатолий Адаменко, Андрей Кучуков. Логическое программирование и 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.
- Стандарты
Ссылки
править