Пролог

Пролог - это язык логического программирования, связанный с искусственным интеллектом и компьютерной лингвистикой . ^{[1] [2] [3]}

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

Язык был разработан и реализован в Марселе, Франция, в 1972 году Аленом Колмерауэром и Филиппом Русселем на основе процедурной интерпретации положений Хорна Робертом Ковальски . ^{[5] [6]}

Пролог был одним из первых языков логического программирования ^[7] и остается самым популярным таким языком сегодня, с несколькими доступными бесплатными и коммерческими реализациями. Язык был использован для доказательства теорем , ^[8] экспертных систем , ^[9] Термин переписывания , ^[10] системы типа , ^[11] и автоматизированного планирования , ^[12] , а также его первоначальный предполагаемой область применения, обработка естественного языка . ^{[13] [14]} Современные среды Prolog поддерживают создание графических пользовательских интерфейсов., а также административные и сетевые приложения.

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

Синтаксис и семантика [ править ]

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

Типы данных [ править ]

Единственный тип данных Пролога - это термин . Термины могут быть атомами , числами , переменными или составными терминами .

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

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

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

ИСО Пролог обеспечивает atom/1, number/1, integer/1и float/1предикаты для проверки типа . ^[16]

Правила и факты [ править ]

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

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

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

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

кот ( косолапый ).

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

кот ( косолапый )  : -  Верно .

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

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

Кривоголик - это кошка?

 ? -  кот ( косоглазый ).  да

что такое кошки?

 ? -  кот ( X ).  X  =  крючок

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

животное ( X )  : -  кошка ( X ).

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

 ? -  животное ( X ).  X  =  крючок

Из-за реляционной природы многих встроенных предикатов их обычно можно использовать в нескольких направлениях. Например, 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). По этой причине для многих программ на Прологе достаточно сравнительно небольшого набора библиотечных предикатов.

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

Казнь [ править ]

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

mother_child ( Trude ,  вылазка ). Father_child ( Том ,  Салли ). отец_ ребенок ( том ,  эрика ). Father_child ( Майк ,  Том ). брат ( X ,  Y )  : -  parent_child ( Z ,  X ),  parent_child ( Z ,  Y ). parent_child ( X ,  Y )  : -  Father_child ( X ,  Y ). parent_child ( X ,  Y )  : -  mother_child ( X ,  Y ).

Это приводит к тому, что следующий запрос оценивается как истинный:

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

Это получается следующим образом: Первоначально единственным совпадающим заголовком предложения для запроса 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). Опять же, это подтверждается соответствующим фактом. Поскольку все цели могут быть доказаны, запрос выполняется. Поскольку запрос не содержал переменных, пользователю не сообщается о привязках. Запрос с переменными, например:

? -  Father_child ( Отец ,  Дитя ).

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

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

Циклы и рекурсия [ править ]

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

Отрицание [ править ]

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

допустимо ( X )  : -  \ +  незаконно ( X ).

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

Программирование на Прологе [ править ]

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

Вот несколько примеров программ, написанных на Прологе.

Привет, мир [ править ]

Пример запроса:

? -  напишите ( 'Hello World!' ),  нл . Привет,  мир ! правда .? -

Оптимизация компилятора [ править ]

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

program_optimized ( PROG0 ,  Prog )  : -  optimization_pass_1 ( PROG0 ,  Prog1 ),  optimization_pass_2 ( Prog1 ,  Prog2 ),  optimization_pass_3 ( Prog2 ,  Prog ).

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

program_optimized  ->  optim_pass_1 ,  optim_pass_2 ,  optim_pass_3 .

Быстрая сортировка [ править ]

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

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

Паттерны дизайна [ править ]

Шаблон дизайна является общим для повторным использования решения для часто встречающихся проблем в разработке программного обеспечения . Некоторые шаблоны проектирования в Prolog - это скелеты, методы, ^{[19] [20]} клише, ^[21] схемы программ, ^[22] схемы описания логики, ^[23] и программирование более высокого порядка . ^[24]

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

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

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

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

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

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

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

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

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

Модули [ править ]

Для программирования в целом Prolog предоставляет модульную систему . Модульная система стандартизирована ISO. ^[27] Однако не все компиляторы Пролога поддерживают модули, и существуют проблемы совместимости между модульными системами основных компиляторов Пролога. ^[28] Следовательно, модули, написанные на одном компиляторе Пролога, не обязательно будут работать на других.

Разбор [ править ]

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

Мета-интерпретаторы и рефлексия [ править ]

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

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

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

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

решить ( правда ,  1 )  : -  !. решить (( Subgoal1 , Subgoal2 ),  Определенность )  : -  !,  решить ( Subgoal1 ,  Certainty1 ),  решить ( Subgoal2 ,  Certainty2 ),  Определенность  в  мин ( Certainty1 ,  Certainty2 ). решить ( Goal ,  1 )  : -  builtin ( Goal ),  !,  Goal. решения ( руководитель ,  Определенность )  : -  clause_cf ( Head ,  Body ,  Certainty1 ),  решить ( Body ,  Certainty2 ),  Определенность  является  Certainty1  *  Certainty2 .

Этот интерпретатор использует таблицу встроенных предикатов Пролога вида ^{[29] : 327}

встроенный ( A  - это  B ). встроенный ( прочтите ( X )). % так далее.

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

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

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

Тьюринга ( TAPE0 ,  ленты )  : -  выполнить ( q0 ,  [],  Ls ,  TAPE0 ,  РТС ),  обратный ( Ls ,  LS1 ),  Append ( 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 ). действие ( left ,  Ls0 ,  Ls ,  Rs0 ,  Rs )  : -  left ( Ls0 ,  Ls ,  Rs0 ,  Rs ). действие ( остаться ,  Ls ,  Ls ,  Rs ,  Rs ). действие ( справа ,  Ls0 ,  [ Sym | Ls0 ],  [ Sym | Rs ],  Rs ). left ([],  [],  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 ]  ;

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

Реализация [ править ]

ISO Prolog [ править ]

Стандарт ISO Prolog состоит из двух частей. ИСО / МЭК 13211-1, ^{[26] [30],} опубликованный в 1995 году, направлен на стандартизацию существующих практик многих реализаций основных элементов Пролога. Это прояснило аспекты языка, которые ранее были неоднозначными, и привело к созданию переносимых программ. Есть три исправления: Cor.1: 2007, ^[31] Cor.2: 2012, ^[32] и Cor.3: 2017. ^[33] ISO / IEC 13211-2, ^[26], опубликованный в 2000 году, добавляет в стандарт поддержку модулей. Стандарт поддерживается рабочей группой ISO / IEC JTC1 / SC22 / WG17 ^[34] . ANSI X3J17 - это техническая консультативная группа США по стандарту.^[35]

Компиляция [ править ]

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

Хвостовая рекурсия [ править ]

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

Индексация срока [ править ]

Поиск предложений, которые невозможно сопоставить с термином в запросе, зависит от количества предложений линейно. При индексировании терминов используется структура данных, которая позволяет выполнять поиск в сублинейном времени . ^[38] Индексирование влияет только на производительность программы, оно не влияет на семантику. Большинство Прологов используют индексирование только по первому термину, поскольку индексирование по всем терминам является дорогостоящим, но методы, основанные на словах с кодировкой полей или наложенных кодовых словах, обеспечивают быстрое индексирование по всему запросу и заголовку. ^{[39] [40]}

Хеширование [ править ]

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

Таблинг [ править ]

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

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

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

Аппаратная реализация [ править ]

Во время проекта компьютерных систем пятого поколения предпринимались попытки реализовать Prolog в аппаратном обеспечении с целью достижения более быстрого выполнения с помощью выделенных архитектур. ^{[44] [45] [46]} Кроме того, Prolog имеет ряд свойств, которые позволяют ускорить выполнение за счет параллельного выполнения. ^[47] Более поздний подход заключался в компиляции ограниченных программ Пролога в программируемую пользователем вентильную матрицу . ^[48] Однако быстрый прогресс в области аппаратного обеспечения общего назначения постоянно опережает более специализированные архитектуры.

Ограничения [ править ]

Хотя Пролог широко используется в исследованиях и образовании, Пролог и другие языки логического программирования не оказали существенного влияния на компьютерную индустрию в целом. ^[49] Большинство приложений небольшие по промышленным стандартам, некоторые из них превышают 100 000 строк кода. ^{[49] [50]} Программирование в целом считается сложным, потому что не все компиляторы Prolog поддерживают модули, и существуют проблемы совместимости между модульными системами основных компиляторов Prolog. ^[28] Переносимость кода Пролога между реализациями также была проблемой, но разработки с 2007 года означали: «Переносимость в рамках семейства реализаций Пролога, производных от Edinburgh / Quintus, достаточно хороша для поддержки переносимых реальных приложений». ^[51]

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

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

Расширения [ править ]

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

Типы [ править ]

Пролог - нетипизированный язык. Попытки ввести типы относятся к 1980-м годам ^{[55] [56],} а по состоянию на 2008 год все еще предпринимаются попытки расширить Prolog с помощью типов. ^[57] Информация о типах полезна не только для обеспечения безопасности типов, но и для рассуждений о программах на языке Prolog. ^[58]

Режимы [ править ]

Синтаксис Пролога не определяет, какие аргументы предиката являются входными, а какие - выходными. ^[59] Однако эта информация важна, и ее рекомендуется включить в комментарии. ^[60] Режимы предоставляют ценную информацию при рассмотрении программ Prolog ^[58], а также могут использоваться для ускорения выполнения. ^[61]

Ограничения [ править ]

Программирование логики ограничений расширяет Prolog, чтобы включить в него концепции, относящиеся к удовлетворению ограничений . ^{[62] [63]} Ограничение логической программа позволяет ограничения в теле статей, такие как: A(X,Y) :- X+Y>0. Это подходит для крупномасштабных комбинаторных оптимизационных задач ^[64] , и, таким образом , полезно для применения в промышленных установках, такие как автоматизированное время столы и планирование производства . Большинство систем Prolog поставляются по крайней мере с одним решателем ограничений для конечных областей, а также часто с решателями для других областей, таких как рациональные числа.

Ориентация на объект [ править ]

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

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

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

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

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

Графика [ править ]

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

Параллелизм [ править ]

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

Веб-программирование [ править ]

Некоторые реализации Prolog, особенно SWI-Prolog и Ciao, поддерживают веб-программирование на стороне сервера с поддержкой веб-протоколов, HTML и XML . ^[68] Существуют также расширения для поддержки семантических веб- форматов, таких как RDF и OWL . ^{[69] [70]} Пролог также был предложен в качестве клиентского языка. ^[71]

Adobe Flash [ править ]

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

Другое [ править ]

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

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

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

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

История [ править ]

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

Европейские исследователи искусственного интеллекта отдавали предпочтение Prolog, в то время как американцы предпочитали Lisp , что, как сообщается, вызвало множество националистических дебатов о достоинствах языков. ^[73] Большая часть современной разработки Prolog произошла от проекта компьютерных систем пятого поколения (FGCS), который разработал вариант Prolog под названием Kernel Language для его первой операционной системы .

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

H: - B 1 , ..., B n .

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

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

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

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

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

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

См. Также [ править ]

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

Связанные языки [ править ]

• Язык Гёделя - это строго типизированная реализация параллельного программирования с ограничениями . Он построен на SICStus Prolog.
• Visual Prolog , ранее известный как PDC Prolog и Turbo Prolog, представляет собой строго типизированный объектно-ориентированный диалект Prolog, который сильно отличается от стандартного Prolog. Как Turbo Prolog, он продавался Borland, но теперь он разработан и продается датской фирмой PDC (Prolog Development Center), которая изначально его выпустила.
• Datalog - это подмножество Prolog. Он ограничен отношениями, которые могут быть стратифицированными, и не допускает составных терминов. В отличие от Prolog, Datalog не является полным по Тьюрингу .
• Mercury - это ответвление Prolog, ориентированное на разработку программного обеспечения в целом со статической системой полиморфных типов, а также системой режимов и детерминизма.
• GraphTalk - это запатентованная реализация абстрактной машины Уоррена с дополнительными объектно-ориентированными свойствами.
• В некотором роде ^{[ какой? ]} Prolog - это подмножество Planner . Идеи в Planner были позже развиты в метафоре научного сообщества .
• AgentSpeak - это вариант Пролога для программирования поведения агентов в многоагентных системах .
• Erlang начал жизнь с реализации на основе Пролога и поддерживает большую часть синтаксиса, основанного на унификации Пролога.
• Pilog - это декларативный язык, построенный на основе PicoLisp , который имеет семантику Prolog, но использует синтаксис Lisp.

Ссылки [ править ]

Дальнейшее чтение [ править ]

В Викиучебнике есть дополнительная информация по теме: Пролог