User:Кирилл Булыгин/Prolog

This page is about the programming language. For the sense of an introduction, see prologue. For other uses of "Prologue", see Prologue (disambiguation). For the company, see Cyan Worlds.

Кирилл Булыгин/Prolog

Paradigm	Logic programming
Designed by	Alain Colmerauer
First appeared	1972
Major implementations
BProlog, Ciao Prolog, ECLiPSe, GNU Prolog, Logic Programming Associates, Poplog Prolog, P#, Quintus, SICStus, Strawberry, SWI-Prolog, tuProlog, YAP-Prolog
Dialects
ISO Prolog, Edinburgh Prolog
Influenced
Visual Prolog, Mercury, Oz, Erlang, Strand, KL0, KL1, Datalog

Пролог is a general purpose logic programming language associated with artificial intelligence and computational linguistics.

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

Prolog has its roots in formal logic, and unlike many other programming languages, Prolog is declarative: The program logic is expressed in terms of relations, represented as facts and rules. Execution is triggered by running queries over these relations.

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

The language was first conceived by a group around Alain Colmerauer in Marseille, France, in the early 1970s and the first Prolog system was developed in 1972 by Alain Colmerauer and Phillipe Roussel.

Язык был впервые задуман группой Алана Кулмероэ в Марселе (Франция) в начале 1970-х годов. Первая Пролог-система была разработана в 1972 году Аланом Кулмероэ и Филиппом Расселом.

Prolog was one of the first logic programming languages, and remains among the most popular such languages today, with many free and commercial implementations available. While initially aimed at natural language processing, the language has since then stretched far into other areas like theorem proving, expert systems, games, automated answering systems, ontologies and sophisticated control systems. Modern Prolog environments support the creation of graphical user interfaces, as well as administrative and networked applications.

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

Programming in Prolog / Программирование на Прологе

Main article: Prolog syntax and semantics

In Prolog, program logic is expressed in terms of relations, and execution is triggered by running queries over these relations. Relations and queries are constructed using Prolog's single data type, the term. Relations are defined by clauses. Given a query, the Prolog engine attempts to find a resolution refutation of the negated query. If the negated query can be refuted, i.e., an instantiation for all free variables is found that makes the union of clauses and the singleton set consisting of the negated query false, it follows that the original query, with the found instantiation applied, is a logical consequence of the program.…v

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

^…This makes Prolog (and other logic programming languages) particularly useful for database, symbolic mathematics, and language parsing applications. Because Prolog allows impure predicates, checking the truth value of certain special predicates may have some deliberate side effect, such as printing a value to the screen. Because of this the programmer is permitted to use some amount of conventional imperative programming when the logical paradigm is inconvenient. It has a purely logical subset, called "pure Prolog", as well as a number of extralogical features.

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

Data types / Типы данных

Prolog's single data type is the term. Terms are either atoms, numbers, variables or compound terms.

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

• An atom is a general-purpose name with no inherent meaning. Examples of atoms include x, blue, 'Taco', and 'some atom'.

• Атом — это универсальное имя без присущего смысла. Примеры атомов: x, синий, 'Тако' и 'некоторый атом'.

• Numbers can be floats or integers.

• Числа могут быть числами с плавающей запятой или целыми.

• Variables are denoted by a string consisting of letters, numbers and underscore characters, and beginning with an upper-case letter or underscore. Variables closely resemble variables in logic in that they are placeholders for arbitrary terms.

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

• A compound term is composed of an atom called a "functor" and a number of "arguments", which are again terms. Compound terms are ordinarily written as a functor followed by a comma-separated list of argument terms, which is contained in parentheses. The number of arguments is called the term's arity. An atom can be regarded as a compound term with arity zero. Examples of compound terms are truck_year('Mazda', 1986) and 'Person_Friends'(zelda,[tom,jim]).

• Сложный терм состоит из атома, названного "функтором", и нескольких "аргументов", которые также являются термами. Сложный терм обычно записывается как функтор, за которым в скобках стоит лист из термов-аргументов, перечисленных через запятую. Число аргументов называется арностью терма. Атом можно рассматривать как сложным терм с нулевой арностью. Примеры сложных термов: грузовик_год('Mazda', 1986), 'Человек_Друзья'(зелда,[том,джим]).

Special cases of compound terms:

Специальные виды сложных термов:

• A List is an ordered collection of terms. It is denoted by square brackets with the terms separated by commas or in the case of the empty list, []. For example [1,2,3] or [red,green,blue].

• Лист — это упорядоченный набор термов. Он обозначается квадратными скобками с термами, перечисленными через запятую, или, в случае пустого листа, []. Например, [1,2,3] или [красный,зелёный,синий].

• Strings: A sequence of characters surrounded by quotes is equivalent to a list of (numeric) character codes, generally in the local character encoding or Unicode if the system supports Unicode. For example, "to be, or not to be".

• Строка — это последовательность символов, окружённая двойными кавычками. Эквивалентна листу (числовых) кодов символов, главным образом, в локальном наборе символов, либо в Юникоде, если система поддерживает Юникод. Например, "быть или не быть".

Rules and facts / Правила и факты

Prolog programs describe relations, defined by means of clauses. Pure Prolog is restricted to Horn clauses. There are two types of clauses: Facts and rules. A rule is of the form

Head :- Body.

and is read as "Head is true if Body is true". …v

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

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

и читается как "Голова истинна, если Тело истинно".

^…A rule's body consists of calls to predicates, which are called the rule's goals. The built-in predicate ,/2 (meaning a 2-arity operator with name ,) denotes conjunction of goals, and ;/2 denotes disjunction. Conjunctions and disjunctions can only appear in the body, not in the head of a rule.

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

Clauses with empty bodies are called facts. An example of a fact is:

cat(tom).

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

кот(том).

which is equivalent to the rule:

cat(tom) :- true.

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

кот(том) :- true.

The built-in predicate true/0 is always true.

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

Given the above fact, one can ask:

is tom a cat?

?- cat(tom).
Yes

С учётом вышеприведённого факта можно спросить:

является ли том котом?

?- кот(том).
да

what things are cats?

?- cat(X).
X = tom

какие вещи являются котами?

?- кот(X).
X = том

Due to the relational nature of many built-in predicates, they can typically be used in several directions. For example, length/2 can be used to determine the length of a list (length(List, L), given a list List) as well as to generate a list skeleton of a given length (length(X, 5)), and also to generate both list skeletons and their lengths together (length(X, L)).…v

Благодаря реляционной природе многих встроенных предикатов их обычно можно использовать несколькими способами. Например, length/2 ("длина") можно применить для определения длины листа (length(Лист, L) с заданным листом Лист), для создания заготовки листа определённой длины (length(X, 5)), а также для одновременной генерации и заготовки листа, и его длины (length(X, L)).

^…Similarly, append/3 can be used both to append two lists (append(ListA, ListB, X) given lists ListA and ListB) as well as to split a given list into parts (append(X, Y, List), given a list List). For this reason, a comparatively small set of library predicates suffices for many Prolog programs.

Аналогично, append/3 ("присоединить") можно использовать и для соединения двух листов (append(ЛистА, ЛистБ, X) с заданными листами ЛистА и ЛистБ), и для разделения определённого листа на пары (append(X, Y, Лист) с заданным листом Лист). По этой причине сравнительно небольшого набора библиотек предикатов достаточно для многих программ на Прологе.

As a general purpose language, Prolog also provides various built-in predicates to perform routine activities like input/output, using graphics and otherwise communicating with the operating system. These predicates are not given a relational meaning and are only useful for the side-effects they exhibit on the system. For example, the predicate write/1 displays a term on the screen.

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

Evaluation / Вычисление

Execution of a Prolog program is initiated by the user's posting of a single goal, called the query. Logically, the Prolog engine tries to find a resolution refutation of the negated query. The resolution method used by Prolog is called SLD resolution. If the negated query can be refuted, it follows that the query, with the appropriate variable bindings in place, is a logical consequence of the program. In that case, all generated variable bindings are reported to the user, and the query is said to have succeeded.…v

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

^…Operationally, Prolog's execution strategy can be thought of as a generalization of function calls in other languages, one difference being that multiple clause heads can match a given call. In that case, the system creates a choice-point, unifies the goal with the clause head of the first alternative, and continues with the goals of that first alternative. If any goal fails in the course of executing the program, all variable bindings that were made since the most recent choice-point was created are undone, and execution continues with the next alternative of that choice-point. This execution strategy is called chronological backtracking. For example:

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

mother_child(trude, sally).

father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).

sibling(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).

мать_ребёнок(лиза, салли).

отец_ребёнок(том, салли).
отец_ребёнок(том, эрика).
отец_ребёнок(майк, том).

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

родитель_ребёнок(X, Y) :- отец_ребёнок(X, Y).
родитель_ребёнок(X, Y) :- мать_ребёнок(X, Y).

This results in the following query being evaluated as true:

?- sibling(sally, erica).
Yes

В результате следующий вопрос будет определён как истинный:

?- брат_или_сестра(салли, эрика).
да

This is obtained as follows: Initially, the only matching clause-head for the query sibling(sally, erica) is the first one, so proving the query is equivalent to proving the body of that clause with the appropriate variable bindings in place, i.e., the conjunction (parent_child(Z,sally), parent_child(Z,erica)). The next goal to be proved is the leftmost one of this conjunction, i.e., parent_child(Z, sally). Two clause heads match this goal.…v

Это получено следующим образом. Изначально есть единственная голова предложения, соответствующая вопросу брат_или_сестра(салли, эрика), так что доказательство вопроса эквивалентно доказательству тела этого предложения с соотвествующим связыванием переменных, то есть эквивалентно доказательству конъюнкта (родитель_ребёнок(Z,салли), родитель_ребёнок(Z,эрика)). Следующей целью, которая должна быть доказана, является самая левая цель этого конъюнкта, то есть родитель_ребёнок(Z, салли). Этой цели соответствуют головы двух предложений.

^…The system creates a choice-point and tries the first alternative, whose body is father_child(Z, sally). This goal can be proved using the fact father_child(tom, sally), so the binding Z = tom is generated, and the next goal to be proved is the second part of the above conjunction: parent_child(tom, erica). Again, this can be proved by the corresponding fact. Since all goals could be proved, the query succeeds. Since the query contained no variables, no bindings are reported to the user. A query with variables, like:

Система создаёт точку выбора и пробует первую альтернативу, телом которой является отец_ребёнок(Z, салли). Эта цель может быть доказана с использованием факта отец_ребёнок(том, салли), так что создаётся связывание Z = том, и следующей целью для доказательства становится вторая часть вышеприведённого конъюнкта: отец_ребёнок(том, эрика). Снова цель может быть доказана соответствующим фактом. Поскольку все цели могут быть доказаны, вопрос оказывается успешным. Поскольку вопрос не содержал переменных, пользователю не сообщается никаких связываний. Вопрос с переменными, такой, как:

?- father_child(Father, Child).

enumerates all valid answers on backtracking.

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

перечисляет все допустимые ответы с помощью перебора с возвратами.

Notice that with the code as stated above, the query ?- sibling(sally, sally). also succeeds. One would insert additional goals to describe the relevant restrictions, if desired.

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

Loops and recursion / Циклы и рекурсия

Iterative algorithms can be implemented by means of recursive predicates.

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

Negation / Отрицание

The built-in Prolog predicate \+/1 provides negation as failure, which allows for non-monotonic reasoning. The goal \+ illegal(X) in the rule

legal(X) :- \+ illegal(X).

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

легальный(X) :- \+ нелегальный(X).

is evaluated as follows: Prolog attempts to prove the illegal(X). If a proof for that goal can be found, the original goal (i.e., \+ illegal(X)) fails. If no proof can be found, the original goal succeeds. Therefore, the \+/1 prefix operator is called the "not provable" operator, since the query ?- \+ Goal. succeeds if Goal is not provable. This kind of negation is sound if its argument is "ground" (i.e. contains no variables). Soundness is lost if the argument contains variables. In particular, the query ?- legal(X). can now not be used to enumerate all things that are legal.

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

Examples / Примеры

Here follow some example programs written in Prolog. Далее следует несколько примеров программ, написанных на Прологе.

Hello world

An example of a query:

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

?-

Пример вопроса (nl/0 записывает символ новой строки в текущий выходной поток):

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

?-

Compiler optimisation / Оптимизация при компилировании

Any computation can be expressed declaratively as a sequence of state transitions. As an example, an optimizing compiler with three optimization passes could be implemented as a relation between an initial program and its optimized form:

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

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

программа_оптимизированная(Прог0, Прог) :-
    оптимизационный_проход_1(Прог0, Прог1),
    оптимизационный_проход_2(Прог1, Прог2),
    оптимизационный_проход_3(Прог2, Прог).

or equivalently using DCG notation:

или эквивалентно в нотации DC-грамматики ("грамматики, основанной на определённых предположениях", DCG):

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

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

The QuickSort sorting algorithm, relating a list to its sorted version:

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

partition([], _, [], []). 
partition([X|Xs], Pivot, Smalls, Bigs) :- 
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).
 
quicksort([])     --> []. 
quicksort([X|Xs]) --> 
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller), [X], quicksort(Bigger).

% _ — анонимная переменная (произвольный терм)
разделение([], _, [], []).
% Если Лист = [Голова|Хвост], то Голова — это первый элемент листа Лист, а Хвост — это лист из остальных его элементов.
разделение([Голова|Хвост], ОпорныйЭлемент, Малые, Большие) :-   
    % Если -> То ; Иначе — импликация
    (   Голова @< ОпорныйЭлемент ->
        Малые = [Голова|Остальные],
        разделение(Хвост, ОпорныйЭлемент, Остальные, Большие)
    ;   Большие = [Голова|Остальные],
        разделение(Хвост, ОпорныйЭлемент, Малые, Остальные)
    ).
 
быстраясортировка([]) --> [].
быстраясортировка([Голова|Хвост]) 
    { разделение(Хвост, Голова, Меньшие, Большие) },
    быстраясортировка(Меньшие), [Голова], быстраясортировка(Большие).

Dynamic programming / Динамическое программирование

The following Prolog program uses dynamic programming to find the longest common subsequence of two lists in polynomial time. The clause database is used for memoization:

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

:- dynamic(запомненное/1).

% assertz/1 добавляет утверждение в базу данных
запомни(Цель) :- ( запомненное(Цель) -> true ; Цель, assertz(запомненное(Цель)) ).

% ! — сбросить точки выбора
ноп([], _, []) :- !.
ноп(_, [], []) :- !.
ноп([X|Xs], [X|Ys], [X|Ls]) :- !, запомни(ноп(Xs, Ys, Ls)).
ноп([X|Xs], [Y|Ys], Ls) :-
    запомни(ноп([X|Xs], Ys, Ls1)), запомни(ноп(Xs, [Y|Ys], Ls2)),
    length(Ls1, L1), length(Ls2, L2),
    (   L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).

Example query:

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

?- lcs([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls). 
Ls = [m, j, a, u]

?- ноп([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls).
Ls = [m, j, a, u]

Modules / Модули

For programming in the large, Prolog provides a module system. The module system is standardised by ISO. However, not all Prolog compilers support modules and there are compatibility problems between the module systems of the major Prolog compilers. Consequently, modules written on one Prolog compiler will not necessary work on others.

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

Parsing / Синтаксический анализ

Main article: Definite clause grammar

There is a special notation called definite clause grammars (DCGs). A rule defined via -->/2 instead of :-/2 is expanded by the preprocessor (expand_term/2, a facility analogous to macros in other languages) according to a few straightforward rewriting rules, resulting in ordinary Prolog clauses. Most notably, the rewriting equips the predicate with two additional arguments, which can be used to implicitly thread state around, analogous to monads in other languages. DCGs are often used to write parsers or list generators, as they also provide a convenient interface to list differences.

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

Parser example / Пример синтаксического анализатора

A larger example will show the potential of using Prolog in parsing.

Для демонстрации потенциала использования Пролога в синтаксическом анализе приведём такой пример.

Given the sentence expressed in Backus-Naur Form:

<sentence>    ::=  <stat_part>
<stat_part>   ::=  <statement> | <stat_part> <statement>
<statement>   ::=  <id> = <expression> ;
<expression>  ::=  <operand> | <expression> <operator> <operand>
<operand>     ::=  <id> | <digit>
<id>          ::=  a | b
<digit>       ::=  0..9
<operator>    ::=  + | - | *

Пусть предложение выражено в форме Бэкуса—Наура:

<предложение> ::=  <утверждения>
<утверждения> ::=  <утверждение> | <утверждения> <утверждение>
<утверждение> ::=  <идентификатор> = <выражение> ;
<выражение>   ::=  <операнд> | <выражение> <оператор> <операнд>
<операнд>     ::=  <имя> | <цифра>
<имя>         ::=  a | b
<цифра>       ::=  0..9
<оператор>    ::=  + | - | *

This can be written in Prolog using DCGs, corresponding to a predictive parser with one token look-ahead:

sentence(S)                --> statement(S0), sentence_r(S0, S).
sentence_r(S, S)           --> [].
sentence_r(S0, seq(S0, S)) --> statement(S1), sentence_r(S1, S).

statement(assign(Id,E)) --> id(Id), [=], expression(E), [;].

expression(E) --> term(T), expression_r(T, E).
expression_r(E, E)  --> [].
expression_r(E0, E) --> [+], term(T), expression_r(plus(E0,T), E).
expression_r(E0, E) --> [-], term(T), expression_r(minus(E0, T), E).

term(T)       --> factor(F), term_r(F, T).
term_r(T, T)  --> [].
term_r(T0, T) --> [*], factor(F), term_r(times(T0, F), T).

factor(id(ID))   --> id(ID).
factor(digit(D)) --> [D], { (number(D) ; var(D)), between(0, 9, D)}.

id(a) --> [a].
id(b) --> [b].

Это может быть записано на Прологе с помощью DC-грамматик в соответствии с предикативным анализатором, просматривающим на одну лексему вперёд:

предложение(S) --> утверждение(S0), предложение_ост(S0, S).
предложение_ост(S, S) --> [].
предложение_ост(S0, последовательность(S0, S)) --> утверждение(S1), предложение_ост(S1, S).

утверждение(присвоить(И,В)) --> имя(И), [=], выражение(В), [;].

выражение(В) --> терм(Т), выражение_ост(Т, В).
выражение_ост(В, В)  --> [].
выражение_ост(В0, В) --> [+], терм(Т), выражение_ост(плюс(В0,Т), В).
выражение_ост(В0, В) --> [-], терм(Т), выражение_ост(минус(В0, Т), В).

терм(Т) --> коэффициент(К), терм_ост(К, Т).
терм_ост(Т, Т)  --> [].
терм_ост(Т0, Т) --> [*], коэффициент(К), терм_ост(умножить(Т0, К), Т).

коэффициент(имя(И))   --> имя(И).
коэффициент(цифра(Ц)) --> [Ц], { (number(Ц) ; var(Ц)), between(0, 9, Ц)}.

имя(a) --> [a].
имя(b) --> [b].

This code defines a relation between a sentence (given as a list of tokens) and its abstract syntax tree (AST). Example query:

?- phrase(sentence(AST), [a,=,1,+,3,*,b,;,b,=,0,;]).
AST = seq(assign(a, plus(digit(1), times(digit(3), id(b)))), assign(b, digit(0))) ;

Данный код определяет отношение между предложением (заданным как лист лексем) и его абстрактным синтаксическим деревом (АСД). Пример вопроса:

?- phrase(предложение(АСД), [a,=,1,+,3,*,b,;,b,=,0,;]).
АСД = последовательность(присвоить(a, плюс(цифра(1), умножить(цифра(3), имя(b)))), присвоить(b, цифра(0))) ;

The AST is represented using Prolog terms and can be used to apply optimizations, to compile such expressions to machine-code, or to directly interpret such statements. As is typical for the relational nature of predicates, these definitions can be used both to parse and generate sentences, and also to check whether a given tree corresponds to a given list of tokens. Using iterative deepening for fair enumeration, each arbitrary but fixed sentence and its corresponding AST will be generated eventually:

?- length(Tokens, _), phrase(sentence(AST), Tokens).
 Tokens = [a, =, a, (;)], AST = assign(a, id(a)) ;
 Tokens = [a, =, b, (;)], AST = assign(a, id(b))
 etc.

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

?- length(Токены, _), phrase(предложение(АСД), Токены).
Токены = [a, =, a, ;], АСД = присвоить(a, имя(a)) ;
Токены = [a, =, b, ;], АСД = присвоить(a, имя(b)) 
и так далее

Higher-order programming / Программирование в логике высшего порядка

Main articles: Higher-order logic and Higher-order programming

First-order logic does not allow quantification over predicates. A higher-order predicate is a predicate that takes one or more other predicates as arguments. Since arbitrary Prolog goals can be constructed and evaluated at run-time, it is easy to write higher-order predicates like maplist/2, which applies an arbitrary predicate to each member of a given list, and sublist/3, which filters elements that satisfy a given predicate, also allowing for currying.

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

To convert solutions from temporal representation (answer substitutions on backtracking) to spatial representation (terms), Prolog has various all-solutions predicates that collect all answer substitutions of a given query in a list. This can be used for list comprehension. For example, perfect numbers equal the sum of their proper divisors:

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

perfect(N) :-
    between(1, inf, N), U is N // 2,
    findall(D, (between(1,U,D), N mod D =:= 0), Ds),
    sumlist(Ds, N).
    
совершенное(N) :-
    between(1, inf, N), U is N // 2,
    findall(D, (between(1,U,D), N mod D =:= 0), Ds),
    sumlist(Ds, N).

This can be used to enumerate perfect numbers, and also to check whether a number is perfect.

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

Meta-interpreters and reflection / Метаинтерпретаторы и рефлексия

Prolog is a homoiconic language and provides many facilities for reflective programming (reflection). Its implicit execution strategy makes it possible to write a concise meta-circular evaluator (also called meta-interpreter) for pure Prolog code. Since Prolog programs are themselves sequences of Prolog terms (:-/2 is an infix operator) that are easily read and inspected using built-in mechanisms (like read/1), it is easy to write customized interpreters that augment Prolog with domain-specific features.

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

Soundness and completeness / Разумность и полнота

Pure Prolog is based on a subset of first-order predicate logic, Horn clauses, which is Turing-complete. The completeness of Prolog can be shown by using it to simulate a Turing machine:

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

turing(Tape0, Tape) :- 
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).
 
perform(qf, Ls, Ls, Rs, Rs) :- !. 
perform(Q0, Ls0, Ls, Rs0, Rs) :- 
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).
 
symbol([], b, []). 
symbol([Sym|Rs], Sym, Rs). 
 
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs). 
action(stay, Ls, Ls, Rs, Rs). 
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs). 
 
left([], [], Rs0, [b|Rs0]). 
left([L|Ls], Ls, Rs, [L|Rs]).

тьюринг(Лента0, Лента) :-
    выполнить(q0, [], Ls, Лента0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Лента).
 
выполнить(qf, Ls, Ls, Rs, Rs) :- !.
выполнить(Q0, Ls0, Ls, Rs0, Rs) :-
    знак(Rs0, Зн, RsRest),
    once(правило(Q0, Зн, Q1, НовЗн, Действие)),
    действие(Действие, Ls0, Ls1, [НовЗн|RsRest], Rs1),
    выполнить(Q1, Ls1, Ls, Rs1, Rs).
 
знак([], b, []).
знак([Зн|Rs], Зн, Rs).
 
действие(влево, Ls0, Ls, Rs0, Rs) :- влево(Ls0, Ls, Rs0, Rs).
действие(стоять, Ls, Ls, Rs, Rs).
действие(вправо, Ls0, [Зн|Ls0], [Зн|Rs], Rs).
 
влево([], [], Rs0, [b|Rs0]).
влево([L|Ls], Ls, Rs, [L|Rs]).

A simple example Turing machine is specified by the facts:

В качестве примера простая машина Тьюринга задана фактами:

rule(q0, 1, q0, 1, right). 
rule(q0, b, qf, 1, stay).

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

This machine performs incrementation by one of a number in unary encoding: It loops over any number of "1" cells and appends an additional "1" at the end. Example query and result:

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

?- turing([1,1,1], Ts). 
Ts = [1, 1, 1, 1] ;

?- тьюринг([1,1,1], Лента).
Лента = [1, 1, 1, 1] ;

This illustrates how any computation can be expressed declaratively as a sequence of state transitions, implemented in Prolog as a relation between successive states of interest.

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

Implementation / Реализация

ISO Prolog / ISO Пролог

The ISO Prolog standard: ISO/IEC 13211-1 published in 1995, aims to standardise the existing practices of the many implementations of the core elements of Prolog. It has clarified aspects of the language that were previously ambiguous and leads to portable programs. The standard is maintained by the ISO X3J17 committee. The standard does not cover modules, libraries or DCGs.

Стандарт ISO Пролога: ISO/IEC 13211-1 опубликован в 1995 году для стандартизации существующих методов, используемые во многих реализациях ключевых элементов Пролога. Он прояснил аспекты языка, прежде бывшие неоднозначными, и привёл к переносимости программ. Стандарт утверждён комитетом ISO X3J17. Стандарт не охватывает модули, библиотеки и DC-грамматики.

Compilation / Компиляция

For efficiency, Prolog code is typically compiled to abstract machine code, often influenced by the register-based Warren Abstract Machine (WAM) instruction set. Some implementations employ abstract interpretation to derive type and mode information of predicates at compile time, or compile to real machine code for high performance. Devising efficient implementation techniques for Prolog code is a field of active research in the logic programming community, and various other execution techniques are employed in some implementations. These include clause binarization and stack-based virtual machines.

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

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

Prolog systems typically implement a well-known optimization technique called tail call optimization (TCO) for deterministic predicates exhibiting tail recursion or, more generally, tail calls: A clause's stack frame is discarded before performing a call in a tail position. Therefore, deterministic tail-recursive predicates are executed with constant stack space, like loops in other languages.

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

Tabling / Табулирование

Some Prolog systems, (BProlog, XSB and Yap), implement an extension called tabling, which frees the user from manually storing intermediate results.

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

Implementation in hardware / Реализация в аппаратном обеспечении

During the Fifth Generation Computer Systems project, there were attempts to implement Prolog in hardware with the aim of achieving faster execution with dedicated architectures. Furthermore, Prolog has a number of properties that may allow speed-up through parallel execution. A more recent approach has been to compile restricted Prolog programs to a field programmable gate array. However, rapid progress in general-purpose hardware has consistently overtaken more specialised architectures.

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

Criticism / Критика

Although Prolog is widely used in research and education, Prolog and other logic programming languages have not had a significant impact on the computer industry in general. Most applications are small by industrial standards with few exceeding 100,000 lines of code. Software developed in Prolog has been criticised for having a high performance penalty, but advances in implementation have made some of these arguments obsolete.

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

Extensions / Расширения

Various implementations have been developed from Prolog to extend logic programming capabilities in numerous directions. These include constraint logic programming (CLP), object-oriented logic programming (OOLP), concurrency, Linear Logic (LLP), functional and higher-order logic programming capabilities, plus interoperability with knowledge bases:

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

Constraints / Ограничения

Constraint logic programming is important for many Prolog applications in industrial settings, like time tabling and other scheduling tasks. Most Prolog systems ship with at least one constraint solver for finite domains, and often also with solvers for other domains like rational numbers.

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

Higher-order programming / Программирование в логике высшего порядка

HiLog and λProlog extend Prolog with higher-order programming features.

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

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

Logtalk is an object-oriented logic programming language that can use most Prolog implementations as a back-end compiler. As a multi-paradigm language, it includes support for both prototypes and classes, protocols (interfaces), component-based programming through category-based composition, event-driven programming, and high-level multi-threading programming.

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

Oblog is a small, portable, Object-oriented extension to Prolog by Margaret McDougall of EdCAAD, University of Edinburgh.

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

Concurrency / Параллелизм

Prolog-MPI] is an open-source SWI-Prolog extension for distributed computing over the Message Passing Interface.

Prolog-MPI — это расширение SWI-Prolog с открытым исходным кодом, предназначенное для распределённых вычислений через интерфейс передачи сообщений (MPI).

Other / Другое

• F-logic extends Prolog with frames/objects for knowledge representation.
• OW Prolog has been created in order to answer Prolog's lack of graphics and interface.

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

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

• The Gödel programming language is a strongly-typed implementation of Concurrent constraint logic programming. It is built on SICStus Prolog.

• Язык программирования Гёдель (Gödel) — это реализация параллельного ограничительного логического программирования со строгим контролем типов, построенная на SICStus Prolog.

• Visual Prolog, also formerly known as PDC Prolog and Turbo Prolog. Visual Prolog is a strongly typed object-oriented dialect of Prolog, which is considerably different from standard Prolog. As Turbo Prolog it was marketed by Borland, but it is now developed and marketed by the Danish firm PDC (Prolog Development Center) that originally produced it.

• Visual Prolog, ранее известный как PDC Prolog и Turbo Prolog. Visual Prolog — это объектно-ориентированный диалект Пролога со строгим контролем типов, который значительно отличается от стандартного Пролога. Как Turbo Prolog он продавался фирмой Borland, но сейчас он разрабатывается и продаётся датской фирмой PDC ("Центр разработки Пролога"), которая изначально создала его.

• Datalog is a subset of Prolog. It is limited to relationships that may be stratified and does not allow compound terms. In contrast to Prolog, Datalog is not Turing-complete.

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

• CSC GraphTalk is a proprietary implementation of Warren's Abstract Machine, with additional object-oriented properties.

• GraphTalk "Корпорации вычислительной техники" (CSC) — это собственническая реализация абстрактной машины Варрена с дополнительными объектно-ориентированными свойствами.

• In some ways Prolog is a subset of Planner. The ideas in Planner were later further developed in the Scientific Community Metaphor.

• В некотором отношении Пролог является подмножеством языка программирования Planner. Идеи Planner позже были развиты научным сообществом.

History / История

The name Prolog was chosen by Philippe Roussel as an abbreviation for programmation en logique (French for programming in logic). It was created around 1972 by Alain Colmerauer with Philippe Roussel, based on Robert Kowalski's procedural interpretation of Horn clauses. It was motivated in part by the desire to reconcile the use of logic as a declarative knowledge representation language with the procedural representation of knowledge that was popular in North America in the late 1960s and early 1970s. According to Robert Kowalski, the first Prolog system was developed in 1972 by Alain Colmerauer and Phillipe Roussel. The first implementations of Prolog were interpreters, however, David H. D. Warren created the Warren Abstract Machine, an early and influential Prolog compiler which came to define the "Edinburgh Prolog" dialect which served as the basis for the syntax of most modern implementations.

Имя Prolog (Пролог) было выбрано Филиппом Расселом как сокращение для programmation en logique (программирование в терминах логики, programming in logic). Он был создан около 1972 года Аланом Кулмероэ вместе с Филиппом Расселом на основе процедурной интерпретации Роберта Ковальского дизъюнктов Хорна. Создание частично было вызвано желанием примирить использование логики в качестве декларативного языка представления знаний с процедурной интерпретацией знаний, что было популярно в Северной Америке в конце 1960-х — начале 1970-х гг. По словам Роберта Ковальского, первая Пролог-система была разработана в 1972 году Аланом Кулмероэ и Филиппом Расселом. Первые реализации Пролога были интерпретаторами, тем не менее, Дэвид Варрен создал абстрактную машину Варрена, ранний и оказавший влияние компилятор Пролога, который определил диалект "эдинбургского Пролога", ставший основой для синтаксиса большинства современных реализаций.

Much of the modern development of Prolog came from the impetus of the fifth generation computer systems project (FGCS), which developed a variant of Prolog named Kernel Language for its first operating system.

Многие из современных разработок Пролога вызваны проектом компьютерных систем пятого поколения (FGCS), в рамках которого был разработан вариант Пролога Kernel Language (KL1) для его первой операционной системы.

Pure Prolog was originally restricted to the use of a resolution theorem prover with Horn clauses of the form:

H :- B1, ..., Bn.

Чистый Пролог изначально был ограничен использованием средства доказательства теорем методом резолюций с дизъюнктами Хорна в следующей форме:

H :- B1, ..., Bn.

The application of the theorem-prover treats such clauses as procedures:

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

to show/solve H, show/solve B1 and ... and Bn.

чтобы проявить/решить H, нужно проявить/решить B1 и ... и Bn.

Pure Prolog was soon extended, however, to include negation as failure, in which negative conditions of the form not(B_i) are shown by trying and failing to solve the corresponding positive conditions B_i.

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

Subsequent extensions of Prolog by the original team introduced Constraint logic programming abilities into the implementations.

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

See also

• Comparison of Prolog implementations

References

• William F. Clocksin, Christopher S. Mellish: Programming in Prolog: Using the ISO Standard. Springer, 5th ed., 2003, ISBN 978-3540006787. (This edition is updated for ISO Prolog. Previous editions described Edinburgh Prolog.)
• William F. Clocksin: Clause and Effect. Prolog Programming for the Working Programmer. Springer, 2003, ISBN 978-3540629719.
• Michael A. Covington, Donald Nute, Andre Vellino, Prolog Programming in Depth, 1996, ISBN 0-13-138645-X.
• Michael A. Covington, Natural Language Processing for Prolog Programmers, 1994, ISBN 0-13-62921
• Robert Smith, John Gibson, Aaron Sloman: 'POPLOG's two-level virtual machine support for interactive languages', in Research Directions in Cognitive Science Volume 5: Artificial Intelligence, Eds D. Sleeman and N. Bernsen, Lawrence Erlbaum Associates, pp 203-231, 1992.
• Leon Sterling and Ehud Shapiro, The Art of Prolog: Advanced Programming Techniques, 1994, ISBN 0-262-19338-8.
• Ivan Bratko, PROLOG Programming for Artificial Intelligence, 2000, ISBN 0-201-40375-7.
• Robert Kowalski, The Early Years of Logic Programming, CACM January 1988.
• ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization, Geneva.
• Alain Colmerauer and Philippe Roussel, The birth of Prolog, in The second ACM SIGPLAN conference on History of programming languages, p. 37-52, 1992.
• Richard O'Keefe, The Craft of Prolog, ISBN 0-262-15039-5.
• Patrick Blackburn, Johan Bos, Kristina Striegnitz, Learn Prolog Now!, 2006, ISBN 1-904987-17-6.
• David H D Warren, Luis M. Pereira and Fernando Pereira, Prolog - the language and its implementation compared with Lisp. ACM SIGART Bulletin archive, Issue 64. Proceedings of the 1977 symposium on Artificial intelligence and programming languages, pp 109 - 115.

External links

• comp.lang.prolog FAQ
• Prolog: The ISO standard
• DECsystem-10 Prolog User’s Manual (plain text) describes a typical Edinburgh Prolog
• Prolog Tutorial by J.R.Fisher
• Runnable examples by Lloyd Allison
• On-line guide to Prolog Programming by Roman Bartak
• Learn Prolog Now! by Patrick Blackburn, Johan Bos and Kristina Striegnitz
• Prolog and Logic Programming by Dr Peter Hancox
• Building Expert Systems in Prolog, online book by Amzi! Inc.
• Literate programming in Prolog
• Object Oriented Language: Prolog, OOLP and other extensions by Richard Katz
• Visual Prolog