Prolog tutte le possibili espressioni di una data x

Question

Ho un programma prolog con una grammatica data:

sum --> [+], mult, sum | mult | num.
mult --> [*], num, xer.
xer --> [x] | [^], [x], num.
num --> [2] | [3] ... etc

Ho una rappresentazione astratta ad albero delle mie espressioni.Biru: mul(num(2),var(x)) che equivale a [*,2,x] è valido.Voglio essere in grado di creare tutte le espressioni che soddisfano una data x e soluzione.Servendosi

allExpressions(Tree, X, Solution).

Biru:

?- allExpressions(Tree, 2, 6)
Tree = mul(num(3),x)
Tree = sum(num(2),mul(num(2),var(x))
etc.

A causa della mia grammatica, ovviamente non sarà un insieme illimitato di equazioni per questo.Ho già programmato un evaluation(Tree, X, Solution) che calcola la risposta data alla variabile X.Quindi quello che ho bisogno di aiuto è generare il possibile insieme di equazioni per una determinata variabile x e soluzione.

Qualche idea su come mi avvicino a questo?Grazie

Answer 1

E facile:Poiché tutte le tue operazioni aritmetiche possono solo aumentare il valore delle espressioni, è semplice limitare la profondità durante la ricerca di soluzioni.Descrivi semplicemente induttivamente come può apparire una soluzione.Puoi farlo ad esempio con i vincoli di dominio finito di SWI-Prolog per l'addizione e la moltiplicazione come questo:

:- use_module(library(clpfd)).

expression(var(x), X, X).
expression(num(N), _, N) :- phrase(num, [N]).
expression(mul(A,B), X, N) :-
        N1 * N2 #= N,
        N1 #> 1,
        N2 #> 1,
        expression(A, X, N1),
        expression(B, X, N2).
expression(sum(A,B), X, N) :-
        N1 + N2 #= N,
        N1 #> 1,
        N2 #> 1,
        expression(A, X, N1),
        expression(B, X, N2).

Lascio le altre operazioni come esercizio.

Esempio di query e alcuni risultati:

?- expression(Tree, 2, 6).
Tree = mul(var(x), num(3)) ;
Tree = mul(num(2), num(3)) ;
    [...solutions omitted...]
Tree = sum(num(2), mul(num(2), var(x))) ;
Tree = sum(num(2), mul(num(2), num(2))) ;
    [...solutions omitted...]
Tree = sum(sum(num(2), num(2)), num(2)) ;
false.

+ 1 per l'utilizzo di una rappresentazione pulita e non predefinita per gli alberi di espressione (var(x), num(N) ecc.), che consente di utilizzare il pattern matching quando si ragiona su di esso.