Alain Colmerauer

24.01.1941

Robert "Bob" Anthony Kowalski

15.05.1941

История

Разработка языка Prolog началась в 1970 году Аланом Кулмероэ и Филиппом Русселом. Они хотели создать язык, который мог бы делать логические заключения на основе заданного текста. Название Prolog является сокращением от "PROgramming in LOGic". Этот язык был разработан в Марселе в 1972 году Принцип резолюции Ковальского, сотрудника Эдинбургского университета, казался подходящей моделью, на основе которой можно было разработать механизм логических выводов. С ограничением резолюции на дизъюнкты Хорна унификация привела к эффективной системе, где неустранимый недетерминизм обрабатывался с помощью процесса отката, который мог быть легко реализован. Алгоритм резолюции позволял создать выполняемую последовательность, необходимую для реализации спецификаций, подобных приведенному выше отношению flight.

Первая реализация языка Prolog с использованием компилятора Вирта ALGOL-W была закончена в 1972 году, а основы современного языка были заложены в 1973 г. Использование языка Prolog постепенно распространялось среди тех, кто занимался логическим программированием, в основном благодаря личным контактам, а не через коммерциализацию продукта. В настоящее время существует несколько различных, но довольно похожих между собой версий. Хотя стандарта языка Prolog не существует, однако версия, разработанная в Эдинбургском университете, стала наиболее широко используемым вариантом. Недостаток разработок эффективных приложений Prolog сдерживал его распространение вплоть до 1980 г.

Краткий обзор языка

В отличие от других языков Prolog не является универсальным языком программирования. Он ориентирован на решение задач с использованием исчисления предикатов.

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

flight (номep_peйсa. пункт_отправления, пункт_назначения. время_отправления. время_прибытия) 
тогда все рейсы из Лос-Анджелеса в Балтимор можно задать либо в виде прямых рейсов через оператор

flight(номер_рейса,Лос-Анджелес. Балтимор. время_отправления, время_прибытия) 
либо в виде рейсов с промежуточной посадкой

flight (номер_рейса1, Лос-Анджелес, X, Время_отправления1, время_прибытия1)

flight (номер_рейса2, X, Балтимор, время_отправления2, время_прибытия2)

время_отправления2 >= время_прибытия+ЗО

Это означает, что вы определяете город X, в который можно попасть рейсом из Лос-Анджелеса и откуда можно улететь в Балтимор, причем самолет в Балтимор вылетает по крайней мере, через 30 минут после прилета рейса из Лос-Анджелеса, чтобы осталось время на пересадку. Здесь не задан никакой алгоритм, заданы только условия для получения правильного решения. Если мы сможем задать подобный набор условий, язык сформирует последовательность действий, необходимую для выбора подходящего рейса.

Программа на языке Prolog состоит из набора фактов, определенных отношений между объектами данных (фактами) и набором правил (образцами отношений между объектами базы данных). Эти факты и правила вводятся в базу данных через операцию consult. Для работы программы пользователь должен ввести запрос - набор термов, которые все должны быть истинны. Факты и правила из базы данных используются для определения того, какие подстановки для переменных в запросе (называемые унификацией) согласуются с информацией в базе данных.

Язык Prolog, как интерпретатор, приглашает пользователя вводить информацию. Пользователь набирает запрос или имя функции. Выводится значение (истина - yes, или ложь - nо) этого запроса, а также возможные значения переменных запроса, присвоение которых делает запрос истинным (то есть унифицирует запрос). Если ввести символ ";", тогда отображается следующий набор значений переменных, унифицирующий запрос, и так до тех пор, пока не исчерпается весь набор возможных подстановок, после чего Prolog печатает no и ждет следующего запроса. Возврат каретки воспринимается как прекращение поиска дополнительных решений.

Хотя выполнение программы на языке Prolog основывается на спецификации предикатов, оно напоминает выполнение программ на аппликативных языках LISP или ML Разработка правил языка Prolog требует того же рекурсивного мышления, что и разработка программ на этих аппликативных языках. Язык Prolog имеет простые синтаксис и семантику. Поскольку он ищет отношения между некоторыми рядами объектов, основными структурами данных являются переменная и список. Правило ведет себя подобно процедуре, за исключением того, что концепция унификации более сложна, чем относительно простой процесс подстановки параметров в выражения.