Prolog all possible expressions of given x

Question

I have a prolog program with given grammar:

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

I have an abstract tree representation of my expressions. For example: mul(num(2),var(x)) which equals [*,2,x] is valid. I want to be able to create all expressions that satisfies a given x and solution. Using

allExpressions(Tree, X, Solution).

For example:

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

Due to my grammar it will obviously not be an unlimited set of equations for this. I have already programmed an evaluation(Tree, X, Solution) which calculates the answer given the X-variable. So what I need help to is to generate the possible set of equations for given x-variable and solution.

Any ideas to how I approach this? Thanks

Answer 1

That's easy: Since all of your arithmetic operations can only increase the value of expressions, it is simple to limit the depth when searching for solutions. Simply describe inductively what a solution can look like. You can do it for example with SWI-Prolog's finite domain constraints for addition and multiplication like this:

:- 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).

I leave the other operations as an exercise.

Example query and some results:

?- 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 for using a clean, non-defaulty representation for expression trees (var(x), num(N) etc.), which lets you use pattern matching when reasoning about it.