Prolog is/2, arguments not sufficiently instantiated

Question

I'm working on an assignment where I have created a parser for a prefix-notation arithmetic language. I need to write a predicate which builds an ast for any given value V (i.e. generate an ast A such that whenever A is evaluated it's value is V). My idea was simple enough:

genAst(Val, Env, Ast) :-
   ev(Ast, Env, Val).

where ev is the evaluate-predicate. When I run this I get the error on the title concerning this part of the ev-predicate:

ev(xer_(power(N)), Env, V) :-
   integer(N),
   V is Env^N. %THIS LINE

where both V and N are unbound. I'm struggling to think of another elegant way to do this, does anyone know how I could make prolog generate integers for these two variables?

I hope this was understandable :)

Answer 1

As posed, your problem seems unsolvable, then I think I would approach the whole problem differently, generating all ASTs up to a max num of tokens.

genAst(Val, Env, Ast) :-
    length(Tokens, N),
    (N > 10, !, fail ; true),
    phrase(sum(Ast), Tokens),
    ev(Ast, Env, Val).

sum(sum(A,B)) --> [+], mul(A), sum(B).
sum(N) --> mul(N).

mul(mul(N,X)) --> [*], xer(X), num(N).
mul(N) --> xer(N).

xer(exp(x,N)) --> [^,x], num(N).
xer(var(x)) --> [x].
xer(N) --> num(N).

%num(num(X)) --> [X], {var(X) -> between(1,9,X) ; integer(X)}.
num(num(X)) --> [X], {X=2;X=3}.

yields

?- genAst(6,2,A).
A = sum(num(3), num(3)) ;
A = mul(num(3), var(x)) ;
A = mul(num(3), num(2)) ;
A = mul(num(2), num(3)) ;
A = sum(mul(num(2), var(x)), var(x)) ;
A = sum(mul(num(2), var(x)), num(2)) ;
A = sum(mul(num(2), num(2)), var(x)) ;
A = sum(mul(num(2), num(2)), num(2)) ;
A = sum(exp(x, num(2)), var(x)) ;
A = sum(exp(x, num(2)), num(2)) ;
A = sum(var(x), sum(var(x), var(x))) ;
A = sum(var(x), sum(var(x), num(2))) ;
A = sum(var(x), sum(num(2), var(x))) ;
A = sum(var(x), sum(num(2), num(2))) ;
A = sum(var(x), mul(num(2), var(x))) ;
A = sum(var(x), mul(num(2), num(2))) ;
A = sum(var(x), exp(x, num(2))) ;
A = sum(num(2), sum(var(x), var(x))) ;
A = sum(num(2), sum(var(x), num(2))) ;
A = sum(num(2), sum(num(2), var(x))) ;
A = sum(num(2), sum(num(2), num(2))) ;
A = sum(num(2), mul(num(2), var(x))) ;
A = sum(num(2), mul(num(2), num(2))) ;
A = sum(num(2), exp(x, num(2))) ;
false.

Limiting the length of the input in this DCG is required because of the right recursive non terminal sum//1

Answer 2

Use library(clpfd). It contains exactly that kind of functionality. And there is no need to generate concrete values, as long as you do not need them!

?- X #= Y^Z.
Y^Z#=X.

?- X #= Y^Z, [Y,Z]ins 1..3.
 Y^Z#=X,
Y in 1..3,
Z in 1..3.

?- X #= Y^Z, [Y,Z]ins 1..3, labeling([], [Y,Z]).
X = Y, Y = Z, Z = 1 ;
X = Y, Y = 1,
Z = 2 ;
X = Y, Y = 1,
Z = 3 ;
X = Y, Y = 2,
Z = 1 ;
X = 4,
Y = Z, Z = 2 ;
X = 8,
Y = 2,
Z = 3 ;
X = Y, Y = 3,
Z = 1 ;
X = 9,
Y = 3,
Z = 2 ;
X = 27,
Y = Z, Z = 3.