Пролог в Perl21.11.2023 14:00

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

% Конкантенация двух списков
append([], X, X).
append([W|X],Y,[W|Z]) :- append(X,Y,Z).

?- append([1], [2, 3], R),
  writef('Конкантенацией списков [1] и [2, 3] будет %d\n', [R]).
% Конкантенацией списков [1] и [2, 3] будет [1,2,3]

?- append([1], B, [1,2,3]),
  writef('Часть списка [1,2,3] после [1] будет %d\n', [B]).
% Часть списка [1,2,3] после [1] будет [2,3]

?- append(A, [2, 3], [1,2,3]),
  writef('Часть списка [1,2,3] до [2,3] будет %d\n', [A]).
% Часть списка [1,2,3] до [2,3] будет [1]

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

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

Поэтому функция получения N-го числа Фибоначчи не сможет вывернуться наизнанку: 

% N-е число Фибоначчи есть сумма двух предыдущих:
fibn(0, 1) :- !.
fibn(1, 1) :- !.
fibn(N, F) :-
  N_1 is N-1,
  N_2 is N-2,
  fibn(N_1, F_1),
  fibn(N_2, F_2),
  F is F_1 + F_2.

?- fibn(5, F), writef('fibn(5) = %d\n', [F]).
% fibn(5) = 8

?- fibn(N, 8), writef('8 = fibn(%d)\n', [N]).
% ERROR:    fibn/2: Arguments are not sufficiently instantiated

?- 8 is 5 + A, writef('8 = 5 + %d\n', [A]).
% ERROR:    is/2: Arguments are not sufficiently instantiated

Что же делать? Всё очень просто: нужно написать на прологе логическую арифметику. Помните как в первом классе школы приходилось носить счётные палочки и выкладывать их в виде списка единичек (фиг.1)?

Фигура 1. Счётные палочки

Фигура 1. Счётные палочки

Для чисел Фибоначчи понадобится только сложение и вычитание (plus/3 и minus/3): 

% Длина списка (количество элементов).
% Будет использоваться для перевода списка единичек в число
len([], 0).
len([1|T], R) :- len(T, C), R is 1+C.

% Генерирует список указанной длинны из единичек
gen(0, []).
gen(N, [1|T]) :- C is N-1, gen(C, T).

% Конкантенация двух списков
append([], X, X).
append([W|X],Y,[W|Z]) :- append(X,Y,Z).

% Используем append/3 в качестве операций сложения и вычитания
plus(A, B, R) :- append(A, B, R).
minus(R, B, A) :- append(A, B, R).

% N-е число фибоначчи на палочках для счёта
fib([], [1]) :- !.
fib([1], [1]) :- !.
fib(N, R) :-
  minus(N, [1], N1),   % N1 = N-1
  fib(N1, R1),
  minus(N, [1,1], N2), % N2 = N-2
  fib(N2, R2),
  plus(R1, R2, R).     % R = R1+R2 = fib(N-1) + fib(N-2)

?- len([1,1,1], N), writef('len(3) = %d\n', [N]).
% len(3) = 3

?- gen(3, A), writef('gen(3) = %d\n', [A]).
% gen(3) = [1,1,1]

?- plus([1,1,1], [1,1], N),
  len(N, L),
  writef('plus(3, 2) = %d\n', [L]).
% plus(3, 2) = 5

?- minus([1,1,1], [1,1], N),
  len(N, L),
  writef('minus(3, 2) = %d\n', [L]).
% minus(3, 2) = 1

fib(A) :- fib(A, R),
  len(A, An),
  len(R, Rn),
  writef('fib(%d) = %d\n', [An, Rn]).
?- fib([1,1,1,1,1]).
% fib(5) = 8

reverse_fib(A) :- fib(R, A),
  len(A, An),
  len(R, Rn),
  writef('%d = fib(%d)\n', [An, Rn]).
?- reverse_fib([1,1,1,1,1,1,1,1]).
% 8 = fib(5)

Теперь всё в порядке: мы можем использовать функцию fib/2 как для получения N-го числа, так и для получения порядкового номера числа Фибоначчи, просто передав в первый параметр неопределённую переменную, а во второй — определённую.

Реализации Пролога

Все примеры выше можно скопировать в файл x.pro и выполнить интерпретатором swi-prolog: 

$ swipl -q -f x.pro -t halt

swi-prolog нетипизирован и имеет множество библиотек и расширений, что позволяет на нём писать графические и WEB-приложения, клиенты и сервера. Остальные его интересные особенности:

  1. Назначать другой приоритет и ассоциативность операторам и создавать новые (:- op(900, xfx, user:(=>)).).

  2. Оператор --> используется для добавления неявного параметра, который необходим для распознавания грамматик.

  3. Имеет нечто похожее на ООП, а методами класса могут быть не только предикаты (функции возвращающие true/false), но и настоящие фунции возвращающие любые значения. Понятно, что эти методы-функции используются в операторе is.

На веб-страничке можно использовать tau-prolog полностью написанный на javascript.

Mercury типизирован и быстр.

Visual-prolog типизирован, требует описания деклараций предикатов в отдельных секциях и предоставляет билдер для создания GUI-приложений (как у Delphi, Lazarus, Visual Basic или Visual Age for SmallTalk).

Все эти реализации Пролога сейчас активно используются и развиваются.

Пролог в Perl

Но относится пролог к логическим языкам программирования вовсе не потому, что он может «переворачивать» написанные на нём функции, а потому, что вместо стека использует дерево вызова функций и, благодаря этому, может найти не одно, а все возможные решения запрограммированной задачи: 

use AI::Prolog;
use DDP;

my $database = << 'END_PROLOG';
  append([], X, X).
  append([W|X],Y,[W|Z]) :- append(X,Y,Z).
END_PROLOG

my $prolog = AI::Prolog->new($database);

$prolog->query("append(X,Y,[a,b,c]).");
while (my $result = $prolog->results) {
    p $result;
}

Указав только третий параметр предикату append мы получим все комбинации, которые бы могли сформировать список [a,b,c]: Так же нужно понимать, что пролог так устроен, что найдёт только первое решение при вызове метода $prolog->results, и приступит к поиску второго решения только при повторном вызове. Другими словами мы можем получить только одно или несколько первых решений поставленной цели, не тратя вычислительные ресурсы для поиска всех, как в примере выше: 

[
    [0] "append",
    [1] [],
    [2] [
            [0] "a",
            [1] "b",
            [2] "c"
        ],
    [3] [
            [0] "a",
            [1] "b",
            [2] "c"
        ]
]
[
    [0] "append",
    [1] [
            [0] "a"
        ],
    [2] [
            [0] "b",
            [1] "c"
        ],
    [3] [
            [0] "a",
            [1] "b",
            [2] "c"
        ]
]
[
    [0] "append",
    [1] [
            [0] "a",
            [1] "b"
        ],
    [2] [
            [0] "c"
        ],
    [3] [
            [0] "a",
            [1] "b",
            [2] "c"
        ]
]
[
    [0] "append",
    [1] [
            [0] "a",
            [1] "b",
            [2] "c"
        ],
    [2] [],
    [3] [
            [0] "a",
            [1] "b",
            [2] "c"
        ]
]

Этот модуль (AI: Prolog) — небольшой интерпретатор на perl-е. Он имеет крохотный набор встроенных функторов и даже собственную команду aiprolog. Огромным его недостатком является отсутствие механизма добавления функций perl в качестве предикатов в интерпретируемую программу.

Была попытка добавить синтаксический сахар (Language: Prolog: Sugar), чтобы писать программу на прологе в виде вызовов функций пёрла, однако получился синтаксический лимон: что там написано не разберёт и опытный перловик-прологовец.

Ещё один модуль (Language: Prolog: Yaswi) проксирует запросы из perl-а в swi-prolog. Но, опять же — пролог-программа не сможет вызвать функции из perl. Приводить пример с ним не буду, так как его интерфейс очень похож на интерфейс AI: Prolog.

Ну и Language: XSB позволяет проксировать запросы к интерпретатору пролога XSB.

Регистрация perl-функций для программы на другом языке

Я уже упоминал, что зарегистрировать perl-функцию, для того чтобы вызвать её из программы на языке prolog — не получится. Но может эту технологию не предоставляют и другие встраиваемые языки программирования?

Так Inline: Lua предлагает передавать ссылки на функции perl в качестве аргументов её функций и вызывать их внутри: 

use Inline Lua => << 'EOLUA'
function table_foreach (func, tab)
    for k, v in pairs(tab) do
      func(k, v)
    end
end
EOLUA
 
sub dump {
    my ($key, $val) = @_;
    print "$key => $val\n";
}
 
table_foreach( \&dump, { key1 => 1, key2 => 2 } );

А Tcl предоставляет полноценное встраивание perl-функций в свои программы: 

use Tcl;
 
my $int = Tcl->new;

sub tcl::fluffy_sub {
    print "Hi, I am a fluffy sub\n";
}
sub tcl::foo {
    print "Hi, I am foo\n";
    $tcl::foo++;
}

$tcl::foo = 'qwerty';
$int->export_to_tcl(subs_from=>'tcl', vars_from=>'tcl');
 
$int->Eval(<<'EOS');
package require Tk
 
button .b1 -text {a fluffy button} -command perl::fluffy_sub
button .b2 -text {a foo button} -command perl::foo
entry .e -textvariable perl::foo
pack .b1 .b2 .e
focus .b2
 
tkwait window .
EOS

Десятеричная система счисления

Использованная нами для вычисления чисел Фибоначчи единичная система счисления, которая каждое число хранит в виде списка единичек (а ля счётные палочки) неоправданно ресурсоёмка. На всего лишь миллиард (1 000 000 000) процессу не хватит памяти и он вылетит.

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

Выводы

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

  2. В пролог-программах нужно использовать десятичный счёт вместо машинных чисел, чтобы можно было использовать написанные предикаты как прямо, так и реверсивно, а если у них больше двух аргументов — то во всех возможных смыслах.

  3. На Прологе удобно писать программы-противники человека для игры в логические игры и стратегии: шахматы, карты, StarCraft или Warhammer 80000, для управления ботами в Half-Life, а так же программы-консультанты вроде Chat-GPT.

Список использованной литературы

  1. Косьмина Я.О. «Индексация предикатов в Прологе», 2004 / https://darviarush.narod.ru/notikoj/Indeksaciya.doc

  2. Косьмина Я.О. «Распределённая параллельная Пролог-система», 2005 / https://darviarush.narod.ru/notikoj/Prolog-Real.doc

  3. Logic Programming in Perl, 2005 by Douglas Wilson / https://metacpan.org/dist/AI-Prolog/view/lib/AI/Prolog/Article.pod

  4. Logic Programming with Perl and Prolog, Dec 15, 2005 by Robert Pratte / https://www.perl.com/pub/2005/12/15/perl_prolog.html/

© Habrahabr.ru