prolog - predicado de "soluciones" de orden superior

lambda-prolog

Question

Estoy usando una variante de Prolog de orden superior que carece de findall .

Hay otra pregunta sobre la implementación de nuestro propio findall aquí: Obtención de una lista de soluciones en Prolog .

La implementación ineficiente es:

parent(pam, bob). %pam is a parent of bob
parent(george, bob). %george is a parent of bob

list_parents(A, Es, [X|Xs]) :-
   parent(X, A),
   /+ member(X, Es),
   list_parents(A, [X|Es], Xs).
list_parents(A, Es, []).

El eficiente

necesita un predicado de orden superior de "soluciones":

list_parents(X, Ys) :- solutions(parent, [X, W], 1, Ys)

¿Qué es solutions ? ¿Puedo implementar mi propio predicado de solutions en un Prolog lambda de orden superior?

Answer 1

Si su Prolog tiene algún tipo de asignación no reversible, como las variables globales de SWI-Prolog, podría implementar (cuidado, código simple) de esta manera:

:- meta_predicate solutions(0, ?).
:- meta_predicate solutions(+, 0, ?).

solutions(G, L) :-
    solutions(G, G, L).

solutions(P, G, L) :-
    ( nb_current(solutions_depth, C) -> true ; C=1 ),
    D is C+1,
    nb_setval(solutions_depth, D),
    atom_concat(solutions_depth_, D, Store),
    nb_setval(Store, []),
    (   G,
        nb_getval(Store, T),
        nb_setval(Store, [P|T]),
        fail
    ;   nb_getval(Store, R)
    ),
    nb_delete(Store),
    nb_setval(solutions_depth, C),
    reverse(R, L).

El uso de variables ''globales'' resulta en una ejecución más eficiente WRT la base de datos dinámica (afirmar / retraer), y (en SWI-prolog) puede usarse incluso en aplicaciones multiproceso.

editar

Gracias a @false comment, movió el corte (s) antes de reverse / 2, e introdujo un stack para llamadas reentrantes: por ejemplo

?- solutions(X-Ys,(between(1,3,X),solutions(Y,between(1,5,Y),Ys)),S).
S = [1-[1, 2, 3, 4, 5], 2-[1, 2, 3, 4, 5], 3-[1, 2, 3, 4, 5]].

Answer 2

Sí , si findall/3 no estuviera disponible, podría implementarlo, por ejemplo, a través de la base de datos dinámica .

Por ejemplo, para el caso de uso concreto de los padres:

list_parents(_) :- parent(P, _), assertz(parent(P)), false. list_parents(Ps) :- phrase(retract_parents, Ps). retract_parents --> ( { retract(parent(P)) } -> [P], retract_parents ; [] ).

Consulta de muestra:

?- list_parents(Ps). Ps = [pam, george].

Puede combinar esto con sort/2 para un rendimiento asintóticamente óptimo, evitando la sobrecarga cuadrática de la solución "ingenua" para eliminar duplicados.

Sin embargo, ten cuidado : primero, esto no es seguro para subprocesos . Para que sea seguro para subprocesos, debe agregar más información relativa al subproceso actual.

En segundo lugar, si implementa findall/3 pleno findall/3 esta manera, debe encargarse de llamadas findall/3 anidadas .

Una forma de hacerlo es afirmar dos tipos de términos:

• solution(S) , como solution(parent(pam)) , que indica una solución concreta que se encontró al retroceder a través de la última llamada findall/3
• mark , lo que indica que un nuevo findall/3 comienza aquí

Al recopilar soluciones, solo procede a la mark más reciente.

Vea el libro de Richard O''Keefe para una buena introducción a estos temas.