Soddisfare una serie di obiettivi in ​​Prolog

Question

In Prolog spesso risolvo un problema fornendo un modello (una struttura contenente variabili) e quindi soddisfacendo una serie di vincoli su di esso. Un esempio semplice potrebbe essere:

go(T) :- 
    T = [_, _, _], 
    member(cat, T), 
    member(dog, T), 
    member(mouse, T). 

E in pratica l'insieme di vincoli viene generato un altro modo piuttosto che essendo fissato, e devo scrivere un predicato ricorsivo per soddisfare ogni vincolo a sua volta:

go(T) :- 
    T = [_, _, _], 
    findall(A, animal(A), As), 
    % satisy member(A, T) for each A in As 
    fill_in_animals(T, As) 

fill_in_animals(T, []). 
fill_in_animals(T, [A|Rest]) :- 
    member(A, T), 
    fill_in_animals(T, Rest). 

Si noti che la mia domanda non riguarda i vincoli relativi alle liste, e anche i parametri del vincolo non possono sempre essere generati facilmente come elenco da passare a un predicato di helper relativamente semplice come usato sopra. In pratica ho trovato l'helper è un predicato piuttosto sgraziato che scrivo ogni volta, che:

1. accetta un template, diversi parametri da utilizzare per il vincolo (e quindi per il legame variabili del modello di valori utili), e una variabile per indicare quale vincolo sta a.
2. Genera un vincolo per soddisfare in questa iterazione, applicandolo al modello.
3. Richiama automaticamente se stesso in modo che i restanti vincoli possano essere soddisfatti.

Quello che sto cercando è un predicato sulla falsariga di findall, ecc., Che soddisferà una serie di obiettivi, uno dopo l'altro. Qualcosa del tipo:

% satisfyall(:Goal) 
% backtracks on Goal but keeps all bindings from each fully satisfied goal. 

satisfyall((animal(A), member(A, T))) 

La risposta che sto cercando non deve essere in questa forma. In effetti, potrebbe esserci una contraddizione tra il backtracking su un obiettivo e il mantenimento di ogni set di binding da esso derivante.

Spero di aver spiegato il mio problema in modo che sia ragionevolmente chiaro cosa potrebbe essere d'aiuto. (Se non me lo faccia sapere.) Scuse in anticipo per la domanda prolissa!

Update (2 anni più tardi)

ci proverò più tardi oggi e aggiornare la mia domanda!

Nota che non ho mai detto che avrei aggiornato la domanda lo stesso giorno del tentativo. ;-)

@CapelliC mi ha guidato nella giusta direzione, e ho trovato un modello che sembra funzionare abbastanza bene:

?- Gs = [member(red),member(blue)], T = [_,_], foreach(member(G, Gs), call(G, T)). 
T = [red, blue] ; 
T = [blue, red] ; 

Answer 1

Sicuramente sai che il backtracking ha bisogno di per annullare le modifiche apportate al lavoro. Questo è il nocciolo dell'algoritmo di Prolog e la fonte del potere di Prolog.

È anche un punto debole, quando si tratta di calcoli più comuni, come quelli necessariamente coinvolti con effetti collaterali o loop.

Trovare il modo giusto per forzare le nostre regole a lavorare su un percorso deterministico può essere difficile, probabilmente perché non è questo il modo in cui dovrebbe funzionare Prolog.

Bene, ora, fermandosi sproloqui filosofia, vediamo cosa guru di Prolog hanno messo a disposizione a noi: SWI-Prolog offre libreria (aggregate), dove si trovano foreach, che penso che fa molto di quello che stai dopo:

?- foreach(animal(X), member(X,L)). 
L = [cat, dog, mouse|_G10698] . 

Studiare come integrato complesso potrebbe darvi qualche idea per la vostra applicazione (uso ?- edit(foreach). dalla console per ispezionare la fonte).

Nota che separa Generatore e Obiettivo, mentre nella tua domanda sono disperati uniti. Ovviamente, è necessario per poter tornare indietro a solo sulla parte del generatore.

BTW, prova a capire il piccolo elenco di esempio nella pagina del documento. È eccessivamente complicato da dif/2, ma dovrai davvero cogliere il comportamento dei binding per poter generalizzare i tuoi predicati ricorsivi.

HTH

Answer 2

La situazione che lei descrive in questione è un po 'diverso dal firma del predicato satisfyall/1 che hai fornito. Non è previsto il backtracking nell'esempio fill_in_animals, almeno non rispetto alle variabili che fluiscono da go/1. Potrebbe esserci "petit backtracking" nella soddisfazione dei sotto-obiettivi, ma l'obiettivo generale non fallisce lasciando intatti i binding.

Una soluzione banale e probabilmente inutile è l'utilizzo di maplist/2.Per esempio, il vostro esempio è facile da raggiungere in questo modo:

?- length(L, 3), maplist(animal, L). 
L = [cat, cat, cat] ; 
L = [cat, cat, dog] ; 
L = [cat, cat, mouse] ; 
L = [cat, dog, cat] ; 
... 
L = [mouse, mouse, dog] ; 
L = [mouse, mouse, mouse]. 

Si potrebbe andare avanti per utilizzare un database materializzato con l'aggiunta di un solo predicato:

% just flips the arguments of member/2 
memberof(L, A) :- member(A, L). 

Poi possiamo usare findall/3 per fare il lavoro :

Questo dovrebbe chiarire perché lambda.pl potrebbe essere d'aiuto. Non avrebbe bisogno il predicato aiutante, si potrebbe semplicemente scrivere:

?- findall(A, animal(A), Animals), 
    length(L, 3), 
    maplist(\Animal^member(Animal, Animals), L). 

(non testato)

Se siete veramente intenzionato a eludere la variabile vincolante e non vincolante, credo che si sta andando a creare un debugging nightmare per te stesso, ma SWI-Prolog ha un global variable facility che puoi usare. Ricordo vagamente di aver letto da qualche parte che asserta/retract non sono sufficienti per questa attività.

Più ci penso, più mi sembra che non ci sarà un'implementazione significativa di satisfyall/1 che differisce sostanzialmente da maplist/2, ma non vedo l'ora di scoprire che ho sbagliato.