go-prolog May 4 2019 at 00:28

Просто о Прологе

10 min

6.2K

Entertaining tasksProlog*

+15

Comments 11

Tzimie May 4 2019 at 09:57

Меня всегда интересовало, как это работает на реальных, а не игрушечных примерах в NP полных задачах, где единственный выход — задавать эвристики? Как они задаются? Как отслеживать прогресс поиска когда он думает час, другой, и непонятно,, сколько осталось, пара минут или миллиард лет

go-prolog May 4 2019 at 11:37

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

nickolaym May 5 2019 at 01:02

Это не "просто о прологе".
Это навалить кучу кода без комментариев и пробелов, нате, читайте! Пробелы-то чем провинились?

Что этот код должен был проиллюстрировать?
Тяп-ляп-реализацию какого-то дерева? "Смотрите, как можно быстро фигачить на прологе"?

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

То, что у пролога список доступен для прямого паттерн-матчинга, сподвигает к плохим — с соображений ФП — практикам каждый раз писать операции обработки списков в виде явных циклов (ну хорошо, хорошо, рекурсий).
Как насчёт переписать всё это с использованием fold? Не станет более читаемо?

Одно из достоинств пролога (и его же беда) — то, что можно как проверять гипотезы, так и из любого набора входных аргументов пытаться доукомплектовать непротиворечивый набор оставшихся. То есть, нет в чистом виде деления на in- и out-параметры.
Если мы эмулируем ФП с монадой Maybe, подразумевая, что "вот это у нас входы, вот это у нас выходы", — то будет один стиль программирования. Если пишем биекцию f(X,Y) как функции X(Y) и Y(X), то совсем другой, учитывающий, например, что там, где в одном направлении происходит свёртка, в другом будет развёртка списка, к примеру. И потребуется пропетлять между всякими зацикливаниями. И смысл отсечек разный.

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

Но это будет — непросто о прологе.

go-prolog May 5 2019 at 02:13

Да, спасибо за отзыв,
это просто пример представления задач на Прологе. Эти "тяп-ляп" дают решение, достаточно эффективное.

Это навалить кучу кода без комментариев и пробелов, нате, читайте!

Тут же не очередной "туториал" для обучения — это иллюстрация, задачу можно представить логическим представлением и да, довольно быстро. Перед каждым правилом было объяснение, а отсутствие пробелов, только в пределах строки, по моему читабельно.
На "свертку" действительно похоже, ее можно реализовать как мета-предикат, а используют в основном findall(), setof()…
И про разделение входных и выходных параметров интерестно, меня как раз "забавляет" возможность описать конкатенацию, а применять ее как деление, это же возможности унификации, а не просто паттерн-метчинг, это описание отношений между параметрами правила:

append([],X,X).
append([H|T],X,[H|Y]):-append(T,X,Y).

?>append(X,Y,[a,b,c]).

такое приведет к разделению списка, это именно ~~иммутабельные переменные~~ неизвестные X,Y значения которых нужно установить.
Эрланг (который приходиться использовать для оформления кода), имея похожую запись, не приводит к такому эффекту, все же разные основы:

append([],X)->X;
append([H|T],X)->[H|append(T,X)].

nickolaym May 5 2019 at 14:28

Поскольку за декларативностью всё равно прячется императивность, — то оказывается важно, в каком порядке будут перебраны варианты, отвечающие предикату.
Разбиение списка [x0,x1,...,xn] может давать перебор с головы или с хвоста:
[]+[x0,x1,...,xn], [x0]+[x1,...,xn], ..., [x0,x1,...,xn]+[]
соответственно, код будет разный — смотря чего хотелось.
Банально, от перестановки веток зависит

% чуть эффективнее, если первый список пустой
cat1([],Ys,Ys).
cat1([X1|Xs],Ys,[X1|XYs]) :- cat1(Xs,Ys,XYs).

% эффективнее для непустых первых списков (вторая ветка матчится единожды)
cat2([X1|Xs],Ys,[X1|XYs]) :- cat2(Xs,Ys,XYs).
cat2([],Ys,Ys).

% типа, балансируем нагрузку!
cat3a([],Ys,Ys).
cat3a([X1|Xs],Ys,[X1|XYs]) :- cat3b(Xs,Ys,XYs).
cat3b([X1|Xs],Ys,[X1|XYs]) :- cat3a(Xs,Ys,XYs).
cat3b([],Ys,Ys).

Криво (непродуманно) (недодуманно) (не предназначенно для неправильных сочетаний in/out-параметров) написанный код легко можно вогнать в рекурсию.
Например, cat(_,[1,2,3],Zs) — то есть, "список, хвостом которого является [1,2,3]".
В случае с cat1 он даст Zs = [1,2,3], [_a,1,2,3], [_a,_b,1,2,3] и т.д.
В случае с cat2 — уйдёт в бесконечность.
Тут даже отсечки не помогут...

go-prolog May 5 2019 at 19:18

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

natural(0).
natural(X+1):-natural(X).

Тогда сумма двух чисел, она же разность:

nsumma(0,X,X).
nsumma(X+1,Y,Z+1) :- nsumma(X,Y,Z).

Произведение выглядит вот так:

nmult(0,_,0).
nmult(X+1,Y,Z) :- nmult(X,Y,Z1), nsumma(Y,Z1,Z).

С помощью него выполнить деления не получается, такая цель зацикливается:

?- nmult(X,Y,0+1+1+1+1+1+1).
X = 0+1, Y = 0+1+1+1+1+1+1 ;
X = 0+1+1, Y = 0+1+1+1 ;
ERROR: Out of global-stack.

Но добавим ограничения, типа, все числа в заданном диапазоне, можно вот так:

tonatural(0,0).
tonatural(N,X+1) :- N>0, N1 is N-1, tonatural(N1,X).

nrange(A,B,N):-A<B, tonatural(A,N).
nrange(A,B,N):-A<B, A1 is A+1, nrange(A1,B,N).

И умножение будет разложением на множители, где неизвестные лежат в указанном диапазоне :

?- nrange(0,10,X), nrange(0,10,Y), nmult(X,Y,0+1+1+1+1+1+1).
X = 0+1,  Y = 0+1+1+1+1+1+1 ;
X = 0+1+1, Y = 0+1+1+1 ;
X = 0+1+1+1, Y = 0+1+1 ;
X = 0+1+1+1+1+1+1, Y = 0+1 ;