Пролог: Изучение с нуля

Добрался таки до пролога. Чтобы не потерять, все источники собираю в одном месте.

Реализации:

• SWI-Prolog,
• GNU Prolog,
• B Prolog,
• SICStus Prolog (платный, 30 дневный trial выдаётся по запросу),
• Strawberry Prolog (Light версия распространяется бесплатно).

Редакторы кода:

• PceEmacs (встроенный Emacs для SWI-Prolog),
• Emacs (prolog-mode),
• Visual Prolog,
• Prolog Development Tool for Eclipse.

Источники первичной информации:

• Wikipedia: Prolog,

       Большая статья из которой можно почерпнуть практически всю доступную информацию о языке Prolog.

• Wikibooks: Prolog,

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

• Prolog ISO/IEC 13211-1:1995 - стандарт языка,

       В 1995 году был принят стандарт языка, но к сожалению в свободном доступе его обнаружить не удалось, есть только черновик в PostScript формате.

• Prolog: ISO Standard documents.

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

Туториалы:

• Prolog Tutorial,
• A Prolog Introduction for Hackers,

Книги:

• "Программирование на языке Пролог", У. Клоксин К. Меллиш ("Programming in Prolog" by W.F. Clocksin and C.S. Mellish),
• "Декларативное программирование", И.А.Дехтяренко,
• Программирование на языке Пролог для искусственного интеллекта, И. Братко,
• Learn Prolog Now by Patrick Blackburn, Johan Bos and Kristina Striegnitz  (бесплатная онлайн-версия).

Задачи:

• 99 Prolog problems,

Другое:

• Free stuff for programming in Prolog,
• The Prolog Dictionary,
• Higher-order logic programming in Prolog (статья о программировании с правилами высшего порядка, сама статья в pdf лежит отдельно).

Очень краткое введение

Пролог – это декларативный логический язык программирования. Основными его конструкциями являются логические предложения (например: human('Socrat') :- true.), на основании которых пролог строит некоторые логические выводы. Предложения объединяются в правила с помощью операции and, которая обозначается знаком ','. Предложение при проверке может создавать побочные эффекты, что используется для ввода/вывода.

Краткий путеводитель по синтаксису

% Это строчный комментарий
/* А это блочный комментарий */

goal(X, Y) :-   % goal - это цель, для которой мы собираем правила,
                % имя цели всегда начинается с маленькой буквы.
                % результат у цели - это всегда true или false.
                % X, Y - параметры цели.

    X > Y       % Первое утверждение, которое утверждает что X больше Y.

    ,           % Разделитель между утверждениями, означает логическое И.

    X + 1 == Y  % Второе утверждение, которое может быть верным,
                % только если Y = X + 1.

    .           % Точка означает конец описания цели.

/*
 * Суммирую:
 * Имя цели всегда с маленькой буквы,
 * Параметры цели, и все другие переменные с большой буквы,
 * Утверждения разделяются запятой,
 * Описание цели всегда заканчивается точкой.
 */

prolog('logic language').
% Так записываются некоторые факты,
% и по сути являются сокращениями для цели,
% которая всегда возвращает true.
% в данном случае эквивалент выглядел бы так:
% prolog('logic language') :- true.

% Цели могут быть рекурсивными.
% Посчитаем сумму от 0 до X.
sum(0, 0).   % факт используется для остановки рекурсии.
sum(X, Result) :-
    Y is X - 1,             % is - это по сути присвоение значения.
    sum(Y, SubResult),      % Рекурсивный вызов.
    Result is X + SubResult.


% Цель, которая будет использоваться при запуске программы,
% имя 'main' выбрано мною произвольно.
main :-
    % запрашиваем значение факта
    prolog(Which),
    % выводим значение на экран
    format('prolog is a ~a.', [Which]),

    % newline
    nl,

    % задаём значение X
    X is 100,
    % считаем сумму от 0 до 100
    sum(X, Result),
    % выводим результат с помощью printf-like функции
    format('sum(0, ~a) = ~a.', [X, Result]),

    % newline.
    nl.

/*
 * Вывод программы при запуске:
 * prolog is a logic language.
 * sum(0, 100) = 5050.
 */

Типы данных

Атом: атом или 'атом', начинается с маленькой буквы или обрамляется одинарными кавычками.

Строка: "Строка", обрамляется двойными кавычками, по факту представляет список из чисел – кодов ASCII символов строки.

Число: 10, целые (-1,0,1), плавающая запятая (0.123, 123.456).

Список: [0, 1, 2], набор элементов перечисленных через запятую и обрамлённых квадратными скобками. Элементы могут быть разнородными (разных типов). Списки можно деструктурировать через синтаксис [Head | Tail].

 

Первые результаты

Теперь, с помощью новоприобретённых знаний, можно написать несколько известных примеров:

HelloWorld.pro:

main :- writeln('Hello, Prolog World!'). 

Factorial.pro:

% factorial implementation

factorial(1, 1).

factorial(X, Result) :-

    X > 0,

    X1 is X - 1,

    factorial(X1, Result1),

    Result is X * Result1.

main :-

    factorial(7, X),

    writeln(X). 

Fibonachi.pro:

% Fibbonachi sequence implementation

fib(0, 1).

fib(1, 1).

fib(X, Result) :-

    X1 is X - 1,

    X2 is X - 2,

    fib(X1, Result1),

    fib(X2, Result2),

    Result is Result1 + Result2.

main :-

    fib(7, X),

    writeln(X). 

QuickSort.pro:

qsort([], []).

qsort([X], [X]).

qsort([Head | Tail], Result) :-

    partition(Head, Tail, Left, Right),

    qsort(Left, LeftSorted),

    qsort(Right, RightSorted),

    append(LeftSorted, [Head | RightSorted], Result).

partition(_, [], [], []).

partition(Pivot, [Head | Tail], [Head | Left], Right) :-

    Head =< Pivot,

    partition(Pivot, Tail, Left, Right).

partition(Pivot, [Head | Tail], Left, [Head | Right]) :-

    Head > Pivot,

    partition(Pivot, Tail, Left, Right).

append([], Right, Right).

append([Head | Left], Right, [Head | Result]) :-

    append(Left, Right, Result).

main :-

    qsort([1, 5, 4, 6, 3, 2], X),

    writeln(X). 

 

Какие ещё есть логические языки программирования?

Путём нехитрых поисков в источниках близким к прологу собрал такой список:

• Curry Language, "A Truly Integrated Functional Logic Language":

        Расширение языка Haskell для реализации логического программирования.

• Mercury Project,

       Mercury is a new logic/functional programming language, which combines the clarity and expressiveness of declarative programming with advanced static analysis and error detection features.

• Oz Language,

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

• ALF – Algebraic logical functional language,

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