Внедрение Prolog findall

Question

Мне было поручено реализовать версию findall в Prolog без использования каких-либо встроенных программ Prolog, кроме not и cut - так что в основном в чистом Prolog.

Я пытаюсь найти в дереве всех прямых потомков и вернуть результаты в виде списка.

parent(a, b).
parent(b, c).
parent(b, d).
parent(e, d).

То, что я до сих пор это:

find(X, L) :- find2(X, [], L).
find2(X, Acc, L) :- parent(Y, X), find2(Y, [Y|Acc], L).
find2(_, Acc, Acc).

Что я хочу получить, когда я войду, например:

find(a,X).

было бы:

X = [b, c, d]

(Порядок не важен)

Однако вместо этого я получаю:

X = [b, c] ;
X = [b, d] ;
X = [b] ;
X = [].

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

Спасибо

Answer 1

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

find(X, Loa) :- find(X, [], Loa), !.
find(X, Acc, Loa) :- dec(Y, X), uList(Y, Acc, AccNew), find(X, AccNew, Loa).
find(_, Acc, Acc).

dec(X,Y) :- parent(X,Y).
dec(X,Y) :- parent(X,Z), dec(Z,Y).

uList(X, [], [X])  :- !.
uList(H, [H|_], _) :- !, fail.
uList(X, [H|T], L) :- uList(X, T, Rtn), L = [H|Rtn].

Answer 2

Помимо подтверждения данных по ходу дела, вы также можете использовать дополнительный логический предикат, такой как nb_setarg / 3. Затем, как только родитель найден, вы не можете вернуться за nb_setarg и найти другого родителя. Все ранее найденные решения должны оставаться в термине, который вы использовали в nb_setarg, а после исчерпания всех результатов термин nb_setarg является ответом. Пример SWI-Prolog хорош, но это просто счетчик. Попробуйте сделать это со списком (или еще лучше: списком различий), который создается по мере продвижения.

Answer 3

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

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

Answer 4

Вот решение, которое использует очереди и потоки SWI-Prolog. Он использует старый существующий API и что-то делает с движками Тарау. Я предполагаю, что создание потока скопирует шаблон и цель. И тогда я предполагаю, что очередь отправки снова сделает копию каждого решения.

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

% threadall(+Term, +Goal, -List)
threadall(T, G, L) :-
   message_queue_create(J, [max_size(1)]),
   thread_create(threadall3(T, G, J), _, [detached(true)]),
   thread_get_message(J, A),
   threadall2(J, A, L),
   message_queue_destroy(J).

% threadall3(+Term, +Goal, +Queue)
threadall3(T, G, J) :-
   G, thread_send_message(J, the(T)), fail.
threadall3(_, _, J) :-
   thread_send_message(J, no).

% threadall2(+Queue, +Term, -List)
threadall2(J, the(T), [T|L]) :- !,
   thread_get_message(J, A),
   threadall2(J, A, L).
threadall2(_, no, []).

Вот пример запуска. Надеюсь, я правильно сделал бухгалтерию. Поток был создан с помощью detach(true), поэтому нам не нужен некоторый дескриптор, когда поток завершается. Очередь сообщений явно уничтожена. Вот несколько примеров выполнения SWI-Prolog, мы видим, что он работает как положено:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.23)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam

?- threadall(X, between(0, 5, X), L).
L = [0, 1, 2, 3, 4, 5].

?- threadall(X-Y, (between(0, 2, X), 
                   threadall(Z, between(0, 2, Z), Y)), L).
L = [0-[0, 1, 2], 1-[0, 1, 2], 2-[0, 1, 2]].

Наш код реализует только обычный счастливый путь: мы реализуем только the/1 а также no/0 сообщение. Далее, так как мы не используем setup_call_cleanup/3 также небезопасно использовать решение с прерываниями. Также последний аргумент не является стойким. Все это оставлено читателю для выполнения этих дополнительных требований и соответствующих альтернативных путей.