Retracting backtracking
To summarize the question, you would like to:
- generate expressions using a generator that uses iterative deepening
- number each solution with consecutive integers.
Thus, the core problem you are facing is preserving information over backtracking.
This is of course impossible in pure Prolog: Doing so would destroy the most elementary properties we expect from relations, in particular our expectation that backtracking undoes everything that happened in the current branch of the computation.
A pure solution, therefore, is to eliminate backtracking!
I'm not joking: We will now change the entire search for solutions in such a way that each solution is found without backtracking, even though the program looks as if it used backtracking. In fact, the program will even stay the same, but we interpret it differently than plain Prolog would do it. This strategy allows us to carry a counter with us, and equip each solution we find with consecutive integers.
In essence, I am now implementing backtracking within Prolog, i.e., I am implementing backtracking without using Prolog's built-in mechanism for backtracking, so that I am free to extend it as I want.
Reifying backtracking
to reify = "to make it a thing" (from Latin: res, rei f. = matter, thing, affair)
First, I will represent the whole program differently, so that it easier to reason about it. The representation I shall use avoids the defaulty representation for regular Prolog goals, and instead uses lists of goals. I will represent each clause as a fact of the form:
head_body(Head, [Goal
1,Goal
2,...,Goal
n]).
This change is purely syntactical (even though it helps enormously for further processing within our programs), and can be easily automated:
head_body(expression_tree([_|N_s],N_s, [number(0)]), []).
head_body(expression_tree([_|N_s0],N_s1, [op(neg),[E1]]),
[expression_tree(N_s0,N_s1, E1)]).
head_body(expression_tree([_|N_s0],N_s2, [op(add), [E1, E2]]),
[expression_tree(N_s0,N_s1, E1),
expression_tree(N_s1,N_s2, E2)]).
We can interpret this program with a meta-interpreter like the following:
mi([G-[]|_], G).
mi([Gs0|Rest], G) :-
findall(G0-Body, (Gs0 = G0-[First|Others],
head_body(First, Body0),
append(Body0, Others, Body)), Nexts, Rest),
mi(Nexts, G).
Note that backtracking no longer occurs in this interpreter in the search for solutions, except for collecting all matching clauses, and actually reporting any solutions, which is only part of the interface but not of the core logic.
Note also that the append/3 call can be eliminated by using list differences in the clause representation. I leave this as a very easy exercise.
To use this interpreter, we change our main predicate to read:
generate_expression(N_c, E) :-
length(N, N_c),
mi([E-[expression_tree(N,[],E)]], E).
Sample query:
?- generate_expression(N, E).
N = 1,
E = [number(0)] ;
N = 2,
E = [op(neg), [[number(0)]]] ;
N = 3,
E = [op(neg), [[op(neg), [[number(0)]]]]] ;
N = 3,
E = [op(add), [[number(0)], [number(0)]]] ;
N = 4,
E = [op(neg), [[op(neg), [[op(neg), [[number(0)]]]]]]] .
This is equivalent to what you already have, and so it does not help a lot currently. By the way, maybe it is now a good time to get rid of this "have we got enough brackets yet" notation, so that future solutions are a bit easier to read. Consider for example terms of the form op_arguments/2 to represent expressions, or better yet simply Prolog terms of the form (+)/2 etc.
Enumerating solutions
Now back to the main point: The key advantage of using a meta-interpreter is that it lets us change how plain Prolog would execute such programs.
In our case, now is the time to introduce a counter for solutions. Our first attempt could look like this:
mi(Alts0, S0, S, G) :-
( Alts0 = [G0-[]|Rest] ->
( S #= S0,
G = G0
; S1 #= S0 + 1,
mi(Rest, S1, S, G)
)
; Alts0 = [Gs0|Rest],
findall(G0-Body, ( Gs0 = G0-[First|Others],
head_body(First, Body0),
append(Body0, Others, Body)), Alts, Rest),
mi(Alts, S0, S, G)
).
With the invoking predicate looking like this:
generate_expression(N_c, S, E) :-
length(N, N_c),
mi([E-[expression_tree(N,[],E)]], 0, S, E).
This almost solves the issue, but we still have the following problem:
?- generate_expression(_, S, _).
S = 0 ;
S = 0 ;
S = 0 ;
S = 1 ;
S = 0 ;
S = 1 ;
S = 2 ;
S = 3 ;
S = 0 ;
S = 1 ;
S = 2 ;
S = 3 ;
S = 4 ;
S = 5 ;
S = 6 ;
S = 7 ;
S = 8 ;
S = 0 ;
S = 1 .
So, solutions are enumerated, but there's still backtracking: The backtracking happens in length/2, and for each new length that is being tried, the counter is reset.
Fair from the start
We therefore now change the interpreter to implement a fair computation strategy right from the start. By fair, we mean that every solution that exists is eventually found.
Iterative deepening is one such strategy. I leave this as an exercise, and implement breadth-first search in this example. Obtaining breadth-first search is easy: We simply append new alternatives. In fact, since we are now about to implement fairness as a fundamental property of the interpreter, we can also simplify the program to read:
head_body(expression_tree([number(0)]), []).
head_body(expression_tree([op(neg), [E1]]),
[expression_tree(E1)]).
head_body(expression_tree([op(add), [E1, E2]]),
[expression_tree(E1),expression_tree(E2)]).
A fair meta-interpreter, implementing breadth-first search and enumerating solutions:
mi(Alts0, S0, S, G) :-
( Alts0 = [G0-[]|Rest] ->
( S #= S0,
G = G0
; S1 #= S0 + 1,
mi(Rest, S1, S, G)
)
; Alts0 = [Gs0|Rest],
findall(G0-Body, ( Gs0 = G0-[First|Others],
head_body(First, Body0),
append(Body0, Others, Body)), Alts1),
append(Rest, Alts1, Alts),
mi(Alts, S0, S, G)
).
Our main predicate:
generate_expression(S, E) :-
mi([E-[expression_tree(E)]], 0, S, E).
And here we go:
?- generate_expression(S, E).
S = 0,
E = [number(0)] ;
S = 1,
E = [op(neg), [[number(0)]]] ;
S = 2,
E = [op(neg), [[op(neg), [[number(0)]]]]] ;
S = 3,
E = [op(add), [[number(0)], [number(0)]]] ;
S = 4,
E = [op(neg), [[op(neg), [[op(neg), [[...]]]]]]] ;
S = 5,
E = [op(neg), [[op(add), [[number(0)], [number(0)]]]]] ;
S = 6,
E = [op(add), [[number(0)], [op(neg), [[number(0)]]]]] ;
S = 7,
E = [op(add), [[op(neg), [[number(0)]]], [number(0)]]] .
Stay pure folks!
Using this pure approach to solve the issue gives us some hope to generalize this to other combinators, since the different concerns can be addressed in comparative isolation, and the original programs can stay the way they are.
Note also that I let the toplevel do the printing. If necessary, I can always write these solutions anywhere I want using impure predicates, but first and foremost each solution is available as a predicate argument that I can actually reason about within Prolog.
