Внедрение 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

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

Answer 2

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

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 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, также небезопасно использовать решение с прерываниями. Также последний аргумент не является стойким. Все это оставлено читателю для выполнения этих дополнительных требований и соответствующих альтернативных путей.