Пролог

Эта статья о языке программирования. О повествовательном устройстве см. Пролог . Чтобы узнать о других значениях, см. Пролог (значения) .

Пролог

Парадигма	Логика
Разработано	Ален Кольмерауэр
Впервые появился	1972 год ( 1972 )
Стабильная версия	Часть 1: General core-Edition 1 (июнь 1995 г.; ( 1995-06 ) ) Часть 2: Модули, издание 1 (июнь 2000 г.; ( 2000-06 ) )
Дисциплина набора текста	Нетипизированный (единственный тип данных — «термин»)
Расширения имен файлов	.pl, .pro, .P
Веб-сайт	Часть 1: www. .iso .org /стандартный /21413 .html Часть 2: www. .iso .org /стандартный /20775 .html
Основные реализации
Амзи! Пролог , B-Prolog , Ciao , ECLiPSe , GNU Prolog , LPA Prolog , Poplog , P# , Quintus Prolog , Scryer Prolog , SICStus , Strawberry , SWI-Prolog , Tau Prolog , tuProlog , WIN-PROLOG XSB , YAP .
Диалекты
ISO Пролог , Эдинбургский Пролог
Под влиянием
Планировщик
Под влиянием
CHR , Clojure , Datalog , Erlang , Epilog , KL0 , KL1 , Logtalk , Mercury , Oz , Strand , Visual Prolog
Пролог в Wikibooks

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

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

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

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

Синтаксис и семантика

Основная статья: Синтаксис и семантика Пролога

В Прологе логика программы выражается в терминах отношений, и вычисления инициируются путем выполнения запроса по этим отношениям. Отношения и запросы строятся с использованием единственного типа данных Пролога — термина . Отношения определяются пунктами . По заданному запросу механизм Пролога пытается найти решение , опровергающее отрицательный запрос. Если отрицательный запрос может быть опровергнут, т. е. найдена реализация для всех свободных переменных, которая делает объединение предложений и одноэлементное множество, состоящее из отрицаемого запроса, ложным, из этого следует, что исходный запрос с примененным найденным экземпляром является логическое следствие программы. Это делает Пролог (и другие языки логического программирования) особенно полезными для баз данных, символьной математики и приложений синтаксического анализа языков. Поскольку Пролог допускает нечистые предикаты , проверка истинного значения некоторых специальных предикатов может иметь некоторый преднамеренный побочный эффект , например вывод значения на экран. По этой причине программисту разрешено использовать некоторое количество традиционного императивного программирования , когда логическая парадигма неудобна. Он имеет чисто логическое подмножество, называемое «чистым Прологом», а также ряд экстралогических особенностей.

Типы данных

Пролога Единственным типом данных является термин . Термины — это атомы , числа , переменные или составные термины .

• Атом — это имя символа , начинающееся со строчной буквы или заключенное в кавычки. Примеры атомов включают x, red, 'Taco', 'some atom', и 'p(a)'.
• Числа могут быть числами с плавающей запятой или целыми числами . Большинство основных систем Пролога поддерживают целые числа произвольной длины.
• Переменные обозначаются строкой, состоящей из букв, цифр и символов подчеркивания и начинающейся с заглавной буквы или подчеркивания. Переменные очень похожи на переменные в логике, поскольку они являются заполнителями для произвольных терминов.
• Составной терм состоит из атома, называемого «функтором», и ряда «аргументов», которые также являются термами. Составные термины обычно записываются в виде функтора, за которым следует список терминов-аргументов, разделенных запятыми, который содержится в круглых скобках. терма Количество аргументов называется арностью . Атом можно рассматривать как составной термин с нулевой арностью . Примером сложного термина является person_friends(zelda,[tom,jim]).

Особые случаи сложных терминов:

• Список — это упорядоченный набор терминов. Он обозначается квадратными скобками с терминами, разделенными запятыми, или, в случае пустого списка, []. Например, [1,2,3,4] или [red,green,blue].
• Строки : последовательность символов, заключенная в кавычки, эквивалентна списку (числовых) кодов символов, списку символов (атомов длины 1) или атому в зависимости от значения флага Пролога. double_quotes. Например, "to be, or not to be".

Правила и факты

Программы на Прологе описывают отношения, определяемые посредством предложений. Чистый Пролог ограничен предложениями Horn . Для определения программ Пролога используются два типа предложений Хорна: факты и правила. Правило имеет вид

Голова   : -   Тело  . 

и читается как «Голова верна, если Тело истинно». правила Тело правила состоит из вызовов предикатов, которые называются целями . Встроенный логический оператор ,/2 арности 2 (имеется в виду оператор с именем ,) обозначает соединение целей, а ;/2обозначает дизъюнкцию . Союзы и дизъюнкции могут появляться только в теле, а не в начале правила.

Предложения с пустым телом называются фактами . Пример факта:

человек  (  Сократ  ). 

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

человек  (  сократ  )   :-   правда  . 

Встроенный предикат true/0 всегда верно.

Учитывая вышеизложенный факт, можно спросить:

Сократ человек?

 ?-   человек  (  Сократ  ). 
   Да 

что такое люди?

 ?-   человек  (  Х  ). 
   Х   =   Сократ 

Предложения с телом называются правилами . Пример правила:

смертный  (  X  )   :-   человек  (  X  ). 

Если мы добавим это правило и спросим, ​​что такое смертные?

 ?-   смертный  (  X  ). 
   Х   =   Сократ 

Предикаты и программы

Предикат ) — это набор предложений , (или определение процедуры заголовки которых имеют одинаковое имя и арность. Мы используем обозначение имя/арность для обозначения предикатов. Логическая программа представляет собой набор предикатов. Например, следующая программа на Прологе, определяющая некоторые семейные отношения, имеет четыре предиката:

мать_ребёнка  (  Труда  ,   Салли  ). 
 
  отец_ребёнок  (  Том  ,   ​​Салли  ). 
  отец_ребенка  (  Том  ,   ​​Эрика  ). 
  отец_ребёнок  (  Майк  ,   Том  ). 
 
  родной брат  (  X  ,   Y  )        : -   родительский_ребенок  (  Z  ,   X  ),   родительский_ребенок  (  Z  ,   Y  ). 
 
  родитель_ребенок  (  X  ,   Y  )   : —   отец_ребенок  (  X  ,   Y  ). 
  родитель_ребенок  (  X  ,   Y  )   : —   мать_ребенок  (  X  ,   Y  ). 

Предикат father_child/2 имеет три предложения, все из которых являются фактами, и предикат parent_child/2 имеет два пункта, оба являются правилами.

Из-за реляционной природы многих встроенных предикатов их обычно можно использовать в нескольких направлениях. Например, length/2 может использоваться для определения длины списка ( length(List, L), учитывая список List) и генерировать скелет списка заданной длины ( length(X, 5)), а также генерировать как скелеты списков, так и их длины вместе ( length(X, L)). Сходным образом, append/3 может использоваться как для добавления двух списков ( append(ListA, ListB, X) заданные списки ListA и ListB), а также разбить заданный список на части ( append(X, Y, List), учитывая список List). По этой причине для многих программ на Прологе достаточно сравнительно небольшого набора библиотечных предикатов.

В качестве языка общего назначения Пролог также предоставляет различные встроенные предикаты для выполнения рутинных действий, таких как ввод/вывод , использование графики и иное взаимодействие с операционной системой. Этим предикатам не придается реляционного значения, и они полезны только для побочных эффектов, которые они оказывают на систему. Например, предикат write/1 отображает термин на экране.

Циклы и рекурсия

Итерационные алгоритмы могут быть реализованы с помощью рекурсивных предикатов.

Рассмотрим parent_child/2предикат, определенный в программе семейных отношений выше. Следующая программа на Прологе определяет отношение предка :

предок  (  X  ,   Y  )   : -   родительский_ребенок  (  X  ,   Y  ). 
  предок  (  X  ,   Y  )   :-   родитель_ребенок  (  X  ,   Z  ),   предок  (  Z  ,   Y  ). 

Он выражает, что X является предком Y, если X является родителем Y или X является родителем предка Y. Он рекурсивен, поскольку определяется в терминах самого себя (существует вызов предиката ancestor/2 в тексте второго пункта).

Исполнение

Выполнение программы на Прологе инициируется сообщением пользователем единственной цели, называемой запросом. Логично, что движок Пролога пытается найти решение , опровергающее отрицательный запрос. Метод разрешения, используемый Прологом, называется разрешением SLD . Если отрицательный запрос можно опровергнуть, из этого следует, что запрос с соответствующими привязками переменных является логическим следствием программы. В этом случае пользователю сообщается обо всех сгенерированных привязках переменных, и считается, что запрос выполнен успешно. С функциональной точки зрения стратегию выполнения Пролога можно рассматривать как обобщение вызовов функций в других языках, единственное отличие состоит в том, что одному вызову может соответствовать несколько заголовков предложений. В этом случае система создает точку выбора, объединяет цель с заголовком предложения первой альтернативы и продолжает работу над целями этой первой альтернативы. Если какая-либо цель не удалась в ходе выполнения программы, все привязки переменных, которые были сделаны с момента создания самой последней точки выбора, отменяются, и выполнение продолжается со следующей альтернативой этой точки выбора. Такая стратегия исполнения называется хронологической. обратный путь . Например, с учетом программы семейных отношений, определенной выше, следующий запрос будет оценен как true:

 ?-   брат  (  Салли  ,   Эрика  ). 
   Да 

Это достигается следующим образом: изначально единственный совпадающий заголовок предложения для запроса sibling(sally, erica) является первым, поэтому доказательство запроса эквивалентно доказательству тела этого предложения с соответствующими привязками переменных, то есть соединением (parent_child(Z,sally), parent_child(Z,erica)). Следующая цель, которую необходимо доказать, — это крайняя левая цель этого соединения, т. е. parent_child(Z, sally). Этой цели соответствуют два заголовка статей. Система создает точку выбора и пробует первую альтернативу, тело которой father_child(Z, sally). Эту цель можно доказать, используя тот факт father_child(tom, sally), поэтому привязка Z = tom генерируется, и следующей целью, которую необходимо доказать, является вторая часть приведенного выше союза: parent_child(tom, erica). Опять же, это можно доказать соответствующим фактом. Поскольку все цели могут быть доказаны, запрос завершается успешно. Поскольку запрос не содержал переменных, пользователю не сообщается ни о каких привязках. Запрос с переменными, например:

?-   отец_ребенок  (  Отец  ,   Ребенок  ). 

перечисляет все действительные ответы при возврате.

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

Отрицание

Встроенный предикат Пролога \+/1предоставляет отрицание как отказ , что позволяет проводить немонотонные рассуждения. Цель \+ illegal(X) в правиле

законно  (  X  )   :-   \+   незаконно  (  X  ). 

оценивается следующим образом: Пролог пытается доказать illegal(X). Если доказательство этой цели может быть найдено, первоначальная цель (т. е. \+ illegal(X)) терпит неудачу. Если доказательств не найдено, первоначальная цель достигнута. Следовательно \+/1 префиксный оператор называется «недоказуемым» оператором, поскольку запрос ?- \+ Goal.успешна, если цель недоказуема. Этот вид отрицания является правильным, если его аргумент «основной» (т. е. не содержит переменных). Разумность теряется, если аргумент содержит переменные и процедура доказательства завершена. В частности, запрос ?- legal(X). теперь нельзя использовать для перечисления всего, что является законным.

Программирование на Прологе

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

Ниже приведены примеры программ, написанных на Прологе.

Привет, мир

Пример базового запроса на нескольких популярных диалектах Пролога:

SWI-Пролог	GNU Пролог
?- напишите ( «Привет, мир!» ), nl . Привет, мир ! истинный . ?-	| ?- напишите ( «Привет, мир!» ), nl . Привет, мир ! да | ?-

Это сравнение показывает, что приглашение («?-» vs «| ?-») и статус разрешения («истина» vs «да», «ложь» vs «нет») могут отличаться от одной реализации Пролога к другой.

Оптимизация компилятора

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

program_optimized  (  Prog0  ,   Prog  )   : - 
     оптимизация_pass_1  (  Prog0  ,   Prog1  ), 
     оптимизация_pass_2  (  Prog1  ,   Prog2  ), 
     оптимизация_pass_3  (  Prog2  ,   Prog  ). 

или, что эквивалентно, используя DCG обозначение :

программа_оптимизированная   -->   оптимизация_пасс_1  ,   оптимизация_пасс_2  ,   оптимизация_пасс_3  . 

Быстрая сортировка

Алгоритм быстрой сортировки, связывающий список с его отсортированной версией:

раздел  ([],   _  ,   [],   []). 
  раздел  ([  X  |  Xs  ],   Pivot  ,   Smalls  ,   Bigs  )   :- 
     (     X   @<   Pivot   -> 
         Smalls   =   [  X  |  Rest  ], 
         раздел  (  Xs  ,   Pivot  ,   Rest  ,   Bigs  ) 
     ;     Bigs   =   [  X  |  Rest  ], 
         раздел  (  Xs  ,   Pivot  ,   Smalls  ,   Rest  ) 
     ). 
 
  быстрая сортировка  ([])       -->   []. 
  быстрая сортировка  ([  X  |  Xs  ])   --> 
     {   раздел  (  Xs  ,   X  ,   Меньше  ,   Больше  )   } , 
     быстрая сортировка  (  Меньше  ),   [  X  ],   быстрая сортировка  (  Больше  ). 

Пролога

Шаблон проектирования — это общее многократно используемое решение часто встречающейся проблемы при проектировании программного обеспечения . Некоторые шаблоны проектирования в Прологе представляют собой скелеты, методы, клише, диаграммы программ схемы логического описания, и программирование высшего порядка .

Программирование высшего порядка

Основные статьи: Логика высшего порядка и программирование высшего порядка.

Предикат более высокого порядка — это предикат, который принимает в качестве аргументов один или несколько других предикатов. Хотя поддержка программирования высшего порядка выводит Пролог за пределы области логики первого порядка, которая не позволяет количественно оценивать предикаты, ISO Prolog теперь имеет несколько встроенных предикатов более высокого порядка, таких как call/1, call/2, call/3, findall/3, setof/3, и bagof/3. Более того, поскольку произвольные цели Пролога могут быть созданы и оценены во время выполнения, легко писать предикаты более высокого порядка, такие как maplist/2, который применяет произвольный предикат к каждому члену данного списка и sublist/3, который фильтрует элементы, удовлетворяющие заданному предикату, а также допускает каррирование .

Для преобразования решений из временного представления (замены ответов при возврате) в пространственное представление (термины) в Прологе имеются различные предикаты всех решений, которые собирают в список все замены ответов данного запроса. Это можно использовать для понимания списка . Например, совершенные числа равны сумме своих собственных делителей:

 Perfect  (  N  )   :- 
      между  (  1  ,   inf  ,   N  ),   U   равно   N   //   2  , 
      findall  (  D  ,   (  между  (  1  ,  U  ,  D  ),   N   mod   D   =:=   0  ),   Ds  ), 
      sumlist  (  Дс  ,   Н  ). 

Это можно использовать для перечисления совершенных чисел и для проверки того, является ли число совершенным.

Другой пример: предикат maplist применяет предикат P ко всем соответствующим позициям в паре списков:

список карт  (  _  ,   [],   []). 
  список карт  (  P  ,   [  X  |  Xs  ],   [  Y  |  Ys  ])   : - 
    вызов  (  P  ,   X  ,   Y  ), 
    список карт  (  P  ,   Xs  ,   Ys  ). 

Когда P это предикат, который для всех X, P(X,Y) объединяет Y с одним уникальным значением, maplist(P, Xs, Ys) эквивалентно применению функции карты в функциональном программировании как Ys = map(Function, Xs).

Стиль программирования высшего порядка на Прологе был впервые использован в HiLog и λProlog .

Модули

Для программирования в целом Пролог предоставляет систему модулей , соответствующую стандарту ISO. Однако, хотя большинство систем Пролога поддерживают структурирование кода по модулям, практически ни одна реализация не соответствует модулям, являющимся частью стандарта ISO. Вместо этого большинство систем Пролога решили поддерживать в качестве де-факто стандарта модульную систему Quintus / SICStus . Однако дополнительные предикаты удобства, касающиеся модулей, предоставляются только некоторыми реализациями и часто имеют небольшие различия в своей семантике.

Некоторые системы решили реализовать концепцию модуля в виде компиляции из исходного кода в базовый ISO Prolog, как в случае с Logtalk . GNU Prolog изначально отказался от модулей ISO, выбрав вместо этого контекстное логическое программирование , в котором загрузка и выгрузка модуля (модуля) может выполняться динамически. Чао разработал строгую систему модулей, которая, будучи в основном совместимой со стандартом де-факто, используемым другими системами Пролога, поддается точному статическому анализу, поддерживает сокрытие терминов и облегчает программирование в целом. XSB использует другой подход и предлагает систему модулей на основе атомов . Последние две системы Пролога позволяют контролировать терминов . видимость не только предикатов, но и

Разбор

Основные статьи: Синтаксис и семантика Пролога § Грамматики определенных предложений и Грамматика определенных предложений.

Существует специальная нотация, называемая грамматиками определенного предложения (DCG). Правило, определенное через -->/2 вместо :-/2 расширяется препроцессором ( expand_term/2, средство, аналогичное макросам в других языках) в соответствии с несколькими простыми правилами переписывания, в результате чего получаются обычные предложения Пролога. В частности, перезапись снабжает предикат двумя дополнительными аргументами, которые можно использовать для неявного связывания состояния: аналогично монадам в других языках. DCG часто используются для написания анализаторов или генераторов списков, поскольку они также предоставляют удобный интерфейс для списков различий.

Метаинтерпретаторы и рефлексия

Пролог является гомоиконным языком и предоставляет множество возможностей для рефлексивного программирования (рефлексии). Его стратегия неявного выполнения позволяет написать краткий метациклический вычислитель (также называемый метаинтерпретатором ) для чистого кода Пролога:

решить  (  верно  ). 
  решить  ((  Подцель1  ,  Подцель2  ))   :-  
     решить  (  Подцель1  ), 
     решить  (  Подцель2  ). 
  решить  (  Глава  )   :-  
     предложение  (  Глава  ,   Тело  ), 
     ​​решить  (  Тело  ). 

где true представляет собой пустой союз, и clause(Head, Body) унифицируется с предложениями в базе данных формы Head :- Body.

Поскольку программы Пролога сами по себе являются последовательностями терминов Пролога ( :-/2 — инфиксный оператор ), которые легко читаются и проверяются с помощью встроенных механизмов (например, read/1), можно писать собственные интерпретаторы, которые дополняют Пролог специфичными для предметной области функциями. Например, Стерлинг и Шапиро представляют метаинтерпретатор, который выполняет рассуждения с неопределенностью, воспроизведенный здесь с небольшими изменениями:

решить  (  верно  ,   1  )   :-   !. 
  решить  ((  Подцель1  ,  Подцель2  ),   Определенность  :   - 
     !, 
     решить  (  Подцель1  ,   Определенность1  ), 
     решить  (  Подцель2  ,   Определенность2  ), 
     Определенность   минимальна   (  ,  Определенность1  )   Определенность2  . 
  решить  (  Цель  ,   1  )   :- 
     встроенный  (  Цель  ),   !,  
     Цель  . 
  решить  (  Глава  ,   Уверенность  )   :- 
     section_cf  (  Глава  ,   Тело  ,   Уверенность1  ), 
     решить  (  Тело  ,   Уверенность2  ), 
     Определенность   есть   Уверенность1   *   Уверенность2  . 

Этот интерпретатор использует таблицу встроенных предикатов Пролога в форме

встроенный  (  A   есть   B  ). 
  встроенный  (  читай  (  X  )). 
  % и т. д. 

и пункты, представленные как clause_cf(Head, Body, Certainty). Учитывая это, его можно назвать solve(Goal, Certainty) выполнить Goal и получить определенную степень уверенности в результате.

Полнота по Тьюрингу

Чистый Пролог основан на подмножестве логики предикатов первого порядка , предложений Хорна , которая является полной по Тьюрингу . Полноту Пролога по Тьюрингу можно показать, используя его для моделирования машины Тьюринга:

Тьюринг  (  Tape0  ,   Tape  )   : - 
     выполнить  (  q0  ,   [],   Ls  ,   Tape0  ,   Rs  ), 
     перевернуть  (  Ls  ,   Ls1  ), 
     добавить  (  Ls1  ,   Rs  ,   Tape  ). 
 
  выполнить  (  qf  ,   Ls  ,   Ls  ,   Rs  ,   Rs  )   :-   !. 
  выполнить  (  Q0  ,   Ls0  ,   Ls  ,   Rs0  ,   Rs  )   : - 
     символ  (  Rs0  ,   Sym  ,   RsRest  ), 
     один раз  (  правило  (  Q0  ,   Sym  ,   Q1  ,   NewSym  ,   Action  )), 
     действие  (  Action  ,   Ls0  ,   Ls1  ,   [  NewSym  |  RsRest  ],   Rs1  ), 
     выполнить  (  Q1  ,   Ls1  ,   Ls  ,   Rs1  ,   Rs  ). 
 
  символ  ([],   b  ,   []). 
  символ  ([  Sym  |  Rs  ],   Sym  ,   Rs  ). 
 
  действие  (  влево  ,   Ls0  ,   Ls  ,   Rs0  ,   Rs  )   : -   влево  (  Ls0  ,   Ls  ,   Rs0  ,   Rs  ). 
  действие  (  остаться  ,   Ls  ,   Ls  ,   Rs  ,   Rs  ). 
  действие  (  право  ,   Ls0  ,   [  Sym  |  Ls0  ],   [  Sym  |  Rs  ],   Rs  ). 
 
  влево  ([],   [],   Rs0  ,   [  b  |  Rs0  ]). 
  влево  ([  L  |  Ls  ],   Ls  ,   Rs  ,   [  L  |  Rs  ]). 

Простой пример машины Тьюринга определяется фактами:

правило  (  q0  ,   1  ,   q0  ,   1  ,   вправо  ). 
  правило  (  q0  ,   b  ,   qf  ,   1  ,   остаться  ). 

Эта машина выполняет увеличение на одно число в унарном кодировании: она перебирает любое количество ячеек «1» и добавляет в конце дополнительную «1». Пример запроса и результата:

?-   Тьюринга  ([  1  ,  1  ,  1  ],   Ts  ). 
  Ц знак   равно   [  1  ,   1  ,   1  ,   1  ]   ; 

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

Реализация

Дополнительная информация: Сравнение реализаций Пролога.

Пролог ISO

Prolog Международной организации по стандартизации (ISO) Технический стандарт состоит из двух частей. ИСО/МЭК 13211-1, опубликованный в 1995 году, он направлен на стандартизацию существующих практик многих реализаций основных элементов Пролога. Он прояснил аспекты языка, которые ранее были неоднозначными, и привел к созданию переносимых программ. Есть три исправления: Кор.1:2007, Кор.2:2012, и Кор.3:2017. ИСО/МЭК 13211-2, опубликованный в 2000 году, добавляет в стандарт поддержку модулей. Стандарт поддерживается ISO/IEC JTC1 / SC22 /WG17. рабочая группа. ANSI X3J17 — это Техническая консультативная группа США по этому стандарту.

Сборник

(WAM) на основе регистров . абстрактной машины Уоррена Для повышения эффективности код Пролога обычно компилируется в абстрактный машинный код, на который часто влияет набор команд Некоторые реализации используют абстрактную интерпретацию для получения информации о типе и режиме предикатов во время компиляции или компиляции в реальный машинный код для повышения производительности. Разработка эффективных методов реализации кода Пролога является областью активных исследований в сообществе логического программирования, и в некоторых реализациях используются различные другие методы выполнения. К ним относятся бинаризация предложений и виртуальные машины на основе стека .

Хвостовая рекурсия

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

Индексация терминов

Основная статья: Индексация терминов

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

Хеширование

Некоторые системы Пролога, такие как WIN-PROLOG и SWI-Prolog, теперь реализуют хеширование, чтобы помочь более эффективно обрабатывать большие наборы данных. Это имеет тенденцию давать очень большой прирост производительности при работе с большими корпусами, такими как WordNet .

Таблица

Основная статья: Табличное логическое программирование

Некоторые системы Пролога ( B-Prolog , XSB , SWI-Prolog , YAP и Ciao ) реализуют метод запоминания , называемый табличным , который освобождает пользователя от необходимости вручную сохранять промежуточные результаты. Таблизация — это компромисс между пространством и временем ; время выполнения можно сократить, используя больше памяти для хранения промежуточных результатов:

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

Таблица может быть расширена в различных направлениях. Он может поддерживать рекурсивные предикаты посредством разрешения SLG или линейного табличного представления. В многопоточной системе Пролога результаты табличного представления могут оставаться конфиденциальными для потока или совместно использоваться всеми потоками. А при поэтапном составлении таблиц составление таблиц может реагировать на изменения.

Аппаратная реализация

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

Sega реализовала Prolog для использования с Sega AI Computer, выпущенным для японского рынка в 1986 году. Prolog использовался для чтения ввода на естественном языке на японском языке через сенсорную панель .

Ограничения

Хотя Пролог широко используется в исследованиях и образовании, Пролог и другие языки логического программирования не оказали существенного влияния на компьютерную индустрию в целом. Большинство приложений невелики по промышленным стандартам, и лишь немногие из них превышают 100 000 строк кода. Программирование в целом считается сложным, поскольку не все компиляторы Пролога поддерживают модули, и существуют проблемы совместимости между системами модулей основных компиляторов Пролога. Переносимость кода Пролога между реализациями также была проблемой, но события, произошедшие с 2007 года, означали: «переносимость внутри семейства реализаций Пролога, производных от Эдинбурга/Квинтуса, достаточно хороша, чтобы обеспечить поддержку переносимых реальных приложений».

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

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

Расширения

На основе Пролога были разработаны различные реализации, расширяющие возможности логического программирования во многих направлениях. К ним относятся типы , режимы, логическое программирование с ограничениями (CLP), объектно-ориентированное логическое программирование (OOLP), параллелизм, линейная логика (LLP), и логического программирования высшего порядка возможности функционального логического программирования , а также совместимость с базами знаний :

Типы

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

Режимы

Спецификатор режима	Интерпретация
+	nonvar при входе
-	var при входе
?	Не указан

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

Ограничения

Программирование логики ограничений расширяет Пролог, включив в него концепции удовлетворения ограничений . Программа логики ограничений допускает ограничения в теле предложений, например: A(X,Y) :- X+Y>0. Он подходит для крупномасштабных комбинаторной оптимизации . задач и, таким образом, полезен для приложений в промышленных условиях, таких как автоматическое составление расписаний и планирование производства . Большинство систем Пролога поставляются по крайней мере с одним решателем ограничений для конечных областей, а часто также с решателями для других областей, таких как рациональные числа .

Объектная ориентация

Flora-2 — это объектно-ориентированная система представления знаний и рассуждений, основанная на F-логике и включающая в себя HiLog , транзакционную логику и отменяемое рассуждение .

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

Oblog — это небольшое портативное объектно-ориентированное расширение Пролога, созданное Маргарет МакДугалл из EdCAAD, Эдинбургский университет.

Objlog — это фреймовый язык, сочетающий объекты и Prolog II от CNRS, Марсель, Франция.

Prolog++ был разработан компанией Logic Programming Associates и впервые выпущен в 1989 году для ПК с MS-DOS. Была добавлена ​​поддержка других платформ, и в 1995 году была выпущена вторая версия. Книга Криса Мосса о Прологе++ была опубликована издательством Addison-Wesley в 1994 году.

Visual Prolog — это мультипарадигмальный язык с интерфейсами, классами, реализациями и объектными выражениями.

Графика

Системы Пролога, предоставляющие графическую библиотеку , — это SWI-Prolog . Visual Prolog , WIN-PROLOG и B-Prolog .

Параллельность

с открытым исходным кодом Prolog-MPI — это расширение SWI-Prolog для распределенных вычислений через интерфейс передачи сообщений . Также существуют различные параллельные языки программирования Пролог.

Веб-программирование

Некоторые реализации Пролога, особенно Visual Prolog , SWI-Prolog и Ciao , поддерживают на стороне сервера веб-программирование с поддержкой веб-протоколов HTML и XML . Существуют также расширения для поддержки форматов семантической сети , такие как платформа описания ресурсов (RDF) и язык веб-онтологии (OWL). Пролог также предлагался в качестве языка клиентской стороны . Кроме того, Visual Prolog поддерживает JSON-RPC и Websockets .

Adobe Flash

Cedar. Архивировано 19 октября 2010 г. на Wayback Machine. Это бесплатный базовый интерпретатор Пролога. Начиная с версии 4 и выше, Cedar имеет поддержку FCA (Flash Cedar App). Это обеспечивает новую платформу для программирования на Прологе с помощью ActionScript .

Другое

• F-logic расширяет Пролог фреймами/объектами для представления знаний .
• Логика транзакций расширяет Пролог логической теорией операторов обновления, изменяющих состояние. Он имеет как теоретико-модельную, так и процедурную семантику.
• OW Prolog был создан, чтобы решить проблему отсутствия в Прологе графики и интерфейса.

Интерфейсы для других языков

Существуют фреймворки, которые могут служить мостом между Прологом и другими языками:

• LPA Intelligence Server позволяет встраивать LPA Prolog для Windows в другие языки программирования, включая: C , C++ , C# , Java , Visual Basic (VB), Delphi , .NET , Lua , Python и другие. Он использует выделенный строковый тип данных, предоставляемый LPA Prolog.
• Интерфейс логического сервера прикладного программирования ( API ) позволяет расширять и встраивать Prolog в C , C++ , Java , Visual Basic (VB), Delphi , .NET и любой язык или среду, которые могут вызывать .dll или .so. Реализовано для Амзи! Prolog + Logic Server , но спецификация API может быть доступна для любой реализации.
• JPL — это двунаправленный мост Java Prolog, который по умолчанию поставляется с SWI-Prolog, позволяя Java и Prolog вызывать друг друга (рекурсивно). Известно, что он имеет хорошую поддержку параллелизма и находится в стадии активной разработки.
• InterProlog программирования, , библиотека мост между Java и Prolog, реализующая двунаправленный вызов предикатов/методов между обоими языками. Объекты Java могут быть отображены в термины Пролога и наоборот. Позволяет разрабатывать графические пользовательские интерфейсы (GUI) и другие функции на Java, оставляя логическую обработку на уровне Пролога. Поддерживает XSB и SWI-Prolog .
• Prova обеспечивает встроенную интеграцию синтаксиса с Java, обмен сообщениями агентов и правила реагирования. Prova позиционирует себя как систему сценариев на основе правил (RBS) для промежуточного программного обеспечения. Этот язык открывает новые возможности в сочетании императивного и декларативного программирования .
• PROL Встраиваемый движок Пролога для Java. Он включает в себя небольшую IDE и несколько библиотек.
• GNU Prolog для Java — это реализация ISO Prolog в виде библиотеки Java (gnu.prolog).
• Ciao предоставляет интерфейсы для C, C++, Java и реляционных баз данных.
• C#-Prolog — это интерпретатор Пролога, написанный на (управляемом) C#. Легко интегрируется в программы на C#. Характеристики: надежный и достаточно быстрый интерпретатор, интерфейс командной строки, Windows-интерфейс, встроенный DCG, XML-предикаты, SQL-предикаты, расширяемый. Доступен полный исходный код, включая генератор синтаксического анализатора, который можно использовать для добавления расширений специального назначения.
• Абстрактная машина Уоррена для PHP Компилятор и интерпретатор Пролога в PHP 5.3. Библиотека, которую можно использовать автономно или в рамках Symfony2.1, которая была переведена из работы Стефана Бюттчера на Java, которую можно найти [здесь Стефан .буттчер .org /кс /ты / ]
• tuProlog — это легкая система Пролога для распределенных приложений и инфраструктур, специально разработанная на основе минимального ядра, которую можно статически или динамически настраивать путем загрузки/выгрузки библиотек предикатов. TuProlog изначально поддерживает мультипарадигмальное программирование, обеспечивая чистую, бесшовную модель интеграции между Прологом и основными объектно-ориентированными языками, а именно Java для версии TuProlog Java и любым языком на основе .NET (C#, F#..) для tuProlog. NET-версия.
• Janus — это двунаправленный интерфейс между Прологом и Python, использующий переносимые низкоуровневые примитивы. Первоначально он был разработан для XSB Андерсоном и Свифтом. но был принят как совместная инициатива команд XSB, Ciao и SWI-Prolog.

История

Хронология ранних разработок в Прологе

Название Пролог было выбрано Филиппом Русселем по предложению жены как аббревиатура от programment en logique ( -французски по программирование в логике ). Он был создан примерно в 1972 году Аленом Кольмерауэром и Филиппом Русселем на основе предложенной Робертом Ковальски процедурной интерпретации статей Хорна, . Частично это было мотивировано желанием согласовать использование логики как декларативного языка представления знаний с процедурным представлением знаний, которое было популярно в Северной Америке в конце 1960-х и начале 1970-х годов. По словам Роберта Ковальски , первая система Пролога была разработана в 1972 году Колмерауэром и Филиппом Русселем. Первой реализацией Пролога был интерпретатор, написанный на Фортране Жераром Баттани и Анри Мелони. Дэвид Х.Д. Уоррен взял этот интерпретатор в Эдинбургский университет и там реализовал альтернативный интерфейс, который стал определять синтаксис «Эдинбургского Пролога», используемый в большинстве современных реализаций. Уоррен также реализовал первый компилятор для Пролога, создав влиятельный Пролог DEC-10 в сотрудничестве с Фернандо Перейрой. Позже Уоррен обобщил идеи, лежащие в основе Пролога DEC-10, и создал Абстрактную машину Уоррена .

Европейские исследователи ИИ отдавали предпочтение Прологу, а американцы — Лиспу , что, как сообщается, вызвало множество националистических дебатов о достоинствах языков. Большая часть современного развития Пролога возникла благодаря проекту «Компьютерные системы пятого поколения» (FGCS), который разработал вариант Пролога под названием «Kernel Language» для своей первой операционной системы .

Первоначально чистый Пролог был ограничен использованием средства доказательства резолюционной теоремы с предложениями Хорна вида:

Ч:- Б  1  , ..., Б  н  .
 

Применение средства доказательства теорем рассматривает такие предложения как процедуры:

чтобы показать/решить H, показать/решить B  1  и ... и B  n  .
 

Однако вскоре чистый Пролог был расширен, включив в него отрицание как неудачу , в которой отрицательные условия формы not(B _i ) проявляются в попытке и неудаче решить соответствующие положительные условия B _i .

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

Использование в промышленности

Пролог использовался в Watson . Watson использует программное обеспечение IBM DeepQA и платформу Apache UIMA (архитектура управления неструктурированной информацией). Система написана на различных языках, включая Java, C++ и Prolog, и работает под управлением операционной системы SUSE Linux Enterprise Server 11 с использованием инфраструктуры Apache Hadoop для обеспечения распределенных вычислений. Пролог используется для сопоставления с образцом деревьев синтаксического анализа естественного языка. Разработчики заявили: «Нам нужен был язык, на котором мы могли бы удобно выражать правила сопоставления с образцом для деревьев синтаксического анализа и других аннотаций (например, результатов распознавания именованных объектов), а также технология, которая могла бы очень эффективно выполнять эти правила. Мы обнаружили, что Пролог был идеальным выбором языка из-за его простоты и выразительности ». Пролог используется в платформе разработки Low-Code GeneXus , ориентированной на искусственный интеллект. с открытым исходным кодом Графическая база данных TerminusDB реализована на Прологе. TerminusDB предназначен для совместного построения и управления графами знаний .

См. также

• Сравнение реализаций Пролога
• Логико-лингвистическое моделирование . Метод построения системы, основанной на знаниях, использующей Пролог.
• Программирование набора ответов . Полностью декларативный подход к логическому программированию.
• Ассоциация логического программирования

Родственные языки

• Язык Gödel — это строго типизированная реализация параллельного программирования логики с ограничениями . Он построен на SICStus Prolog .
• Visual Prolog , ранее называвшийся PDC Prolog и Turbo Prolog, представляет собой строго типизированный объектно-ориентированный диалект Пролога, который сильно отличается от стандартного Пролога. Как Turbo Prolog, он продавался компанией Borland, но теперь разрабатывается и продается датской фирмой Prolog Development Center (PDC), которая первоначально его производила.
• Datalog — это подмножество Пролога. Он ограничен отношениями, которые могут быть стратифицированы, и не допускает составных терминов. В отличие от Пролога, Datalog не является полным по Тьюрингу .
• Mercury — это ответвление Пролога, предназначенное для разработки программного обеспечения в целом, со статической, полиморфной системой типов, а также системой режимов и детерминизма.
• GraphTalk — это собственная реализация абстрактной машины Уоррена с дополнительными объектно-ориентированными свойствами.
• В какой-то степени Пролог — это подмножество Planner . Идеи Planner позже получили дальнейшее развитие в « Метафоре научного сообщества» .
• AgentSpeak — вариант Пролога для программирования поведения агентов в многоагентных системах .
• Erlang начал свою жизнь с реализации на основе Пролога и поддерживает большую часть синтаксиса, основанного на унификации Пролога.
• Pilog — декларативный язык, построенный на основе PicoLisp , который имеет семантику Пролога, но использует синтаксис Лиспа.
• λProlog — это расширение ядра Пролога, которое включает полиморфную типизацию, модульное программирование и программирование высшего порядка, включая прямую поддержку терминов с операторами привязки переменных посредством так называемого синтаксиса λ-дерева и унификации шаблонов высшего порядка.

Дальнейшее чтение

• Блэкберн, Патрик; Бос, Йохан; Стригниц, Кристина (2006). Изучите Пролог прямо сейчас! . Публикации колледжа. ISBN  978-1-904987-17-8 . Архивировано из оригинала 26 августа 2007 г. Проверено 2 декабря 2008 г.
• Иван Братко , Программирование на Прологе для искусственного интеллекта , 4-е изд., 2012, ISBN   978-0-321-41746-6 . Дополнения к книге и исходный код
• Уильям Ф. Клоксин, Кристофер С. Меллиш: Программирование на Прологе: использование стандарта ISO . Спрингер, 5-е изд., 2003 г., ISBN   978-3-540-00678-7 . (Это издание обновлено для ISO Prolog. В предыдущих выпусках описывался Edinburgh Prolog.)
• Уильям Ф. Клоксин: пункт и эффект. Программирование на Прологе для работающего программиста . Спрингер, 2003 г., ISBN   978-3-540-62971-9 .
• Майкл А. Ковингтон , Дональд Нут, Андре Веллино, «Углубленное программирование на Прологе» , 1996, ISBN   0-13-138645-X .
• Майкл А. Ковингтон, Обработка естественного языка для программистов на Прологе , 1994 г., ISBN   978-0-13-629213-5
• М. С. Доу и К. М. Даве, Пролог для компьютерных наук , Springer Verlag, 1992.
• ISO/IEC 13211: Информационные технологии. Языки программирования. Пролог . Международная организация по стандартизации , Женева.
• Феликс Клюзак и Станислав Шпакович (при участии Януша С. Биня). Пролог для программистов . Академик Пресс Инк. (Лондон), 1985, 1987 г. (доступно по лицензии Creative Commons на сайтах .Google .с /сайт /прологпрепрограммерс / ). ISBN   0-12-416521-4 .
• Ричард О'Киф , «Искусство Пролога» , ISBN   0-262-15039-5 .
• Роберт Смит, Джон Гибсон, Аарон Сломан : «Поддержка двухуровневой виртуальной машины POPLOG для интерактивных языков», в «Направлениях исследований в области когнитивной науки», том 5: Искусственный интеллект , Эдс Д. Слиман и Н. Бернсен, Lawrence Erlbaum Associates, стр. 203– 231, 1992.
• Леон Стерлинг и Эхуд Шапиро , Искусство Пролога: продвинутые методы программирования , 1994, ISBN   0-262-19338-8 .
• Дэвид Х.Д. Уоррен, Луис М. Перейра и Фернандо Перейра, Пролог — язык и его реализация по сравнению с Лиспом. Архив бюллетеня ACM SIGART, выпуск 64. Материалы симпозиума 1977 года по искусственному интеллекту и языкам программирования, стр. 109–115.