Combing generator results and writing result to stream

Question

Currently I can generate expression trees.

expression_tree([_|N_s],N_s, [number(0)]).
expression_tree([_|N_s0],N_s1, [op(neg),[E1]]) :-
    expression_tree(N_s0,N_s1, E1).
expression_tree([_|N_s0],N_s2, [op(add), [E1, E2]]) :-
    expression_tree(N_s0,N_s1, E1),
    expression_tree(N_s1,N_s2, E2).

generate_expression(N_c, E) :-
    length(N, N_c),
    expression_tree(N,[], E).

?- 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)]]]]]]] ;
N = 4,
E = [op(neg), [[op(add), [[number(0)], [number(0)]]]]] ;
N = 4,
E = [op(add), [[number(0)], [op(neg), [[number(0)]]]]] ;
N = 4,
E = [op(add), [[op(neg), [[number(0)]]], [number(0)]]] ;
N = 5,
E = [op(neg), [[op(neg), [[op(neg), [[op(neg), [[number(0)]]]]]]]]]

where N is the number of nodes for the tree.

I can also independently generate sequence numbers.

sequence_number(Sequence_number) :-
    sequence_numbers(1, Sequence_number).

sequence_numbers(I, I).
sequence_numbers(I, K) :-
    J is I + 1,
    sequence_numbers(J, K).

?- sequence_number(N).
N = 1 ;
N = 2 ;
N = 3 ;
N = 4 ;
N = 5 ;
N = 6 

I can also generate and output the expressions but not with the correct sequence numbers

print_expression(Stream, Prefix, Suffix, Sequence_number, E) :-
    write(Stream,Prefix),
    format(Stream, '~|~`0t~d~7+', Sequence_number),
    write(Stream,", "),
    write(Stream,E),
    write(Stream,Suffix),
    nl(Stream).

print_expressions_a(Stream, Prefix, Suffix, Sequence_number, N) :-
    generate_expression(N, E),
    print_expression(Stream, Prefix, Suffix, Sequence_number, E).

print_expressions_a :-
    Stream = user_output,
    Prefix = '(',
    Suffix = ')',
    Sequence_number = 1,
    N = 4,
    print_expressions_a(Stream, Prefix, Suffix, Sequence_number, N).

?- print_expressions_a.
(0000001, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;
(0000001, [op(neg),[[op(add),[[number(0)],[number(0)]]]]])
true ;
(0000001, [op(add),[[number(0)],[op(neg),[[number(0)]]]]])
true ;
(0000001, [op(add),[[op(neg),[[number(0)]]],[number(0)]]])
true ;
false.

Notice the sequence numbers are all 0000001.

Which is generating choice-points, so I modified it using forall

print_expressions_b(Stream, Prefix, Suffix, Sequence_number, N) :-
    forall(
        generate_expression(N, E),
        print_expression(Stream, Prefix, Suffix, Sequence_number, E)
    ).

print_expressions_b :-
    Stream = user_output,
    Prefix = '(',
    Suffix = ')',
    Sequence_number = 1,
    N = 4,
    print_expressions_b(Stream, Prefix, Suffix, Sequence_number, N).

?- print_expressions_b.
(0000001, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
(0000001, [op(neg),[[op(add),[[number(0)],[number(0)]]]]])
(0000001, [op(add),[[number(0)],[op(neg),[[number(0)]]]]])
(0000001, [op(add),[[op(neg),[[number(0)]]],[number(0)]]])
true.

which is still wrong.

---

The output I seek is

(0000001, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
(0000002, [op(neg),[[op(add),[[number(0)],[number(0)]]]]])
(0000003, [op(add),[[number(0)],[op(neg),[[number(0)]]]]])
(0000004, [op(add),[[op(neg),[[number(0)]]],[number(0)]]])

Where each sequence number is unique and sequential starting from 0 or 1 and can be written to a file. For this example the stream is set to user_output to simplify the question.

If I add the sequence number generator into the mix

print_expressions_c(Stream, Prefix, Suffix, N) :-
    generate_expression(N, E),
    sequence_number(Sequence_number),
    print_expression(Stream, Prefix, Suffix, Sequence_number, E).

print_expressions_c :-
    Stream = user_output,
    Prefix = '(',
    Suffix = ')',
    N = 4,
    print_expressions_c(Stream, Prefix, Suffix, N).

?- print_expressions_c.
(0000001, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;
(0000002, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;
(0000003, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;
(0000004, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;
(0000005, [op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]])
true ;

the sequence numbers are now correct, but new expressions are never generated because the sequence number generator is using a choice point to generate the next sequence number and so the predicate sequence_number, does not backtrack to the generate_expression predicate to get a new expression.

So, can I use two generators that rely on backtracking in succession? If so, how?

Supplement

This is related to my earlier questions on tree generators.
I am aware that this should be done with dcg, and that the data structure should be changed, but while I am trying to understand this, seeing it this way is easier to comprehend.

Related SO Questions

• What are the uses of the fail predicate in Prolog?
• How to use backtrack to increment a variable infinitely in Prolog
• Algorithm improvement for enumerating binary trees
• How to enumerate combinations using DCGs with CLP(FD) and multiple constraints

Answer 1

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, [Goal1,Goal2,...,Goaln]).

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.

Answer 2

from a purely pragmatic viewpoint, a counter it's easily implemented (in SWI-Prolog) with non backtrackable assigmnent:

print_expressions_d(Stream, Prefix, Suffix, N) :-
    generate_expression(N, E),
    inc(Sequence_number),
    print_expression(Stream, Prefix, Suffix, Sequence_number, E).

print_expressions_d :-
    Stream = user_output,
    Prefix = '(',
    Suffix = ')',
    N = 4,
    nb_setval(counter,1),
    print_expressions_d(Stream, Prefix, Suffix, N).

inc(V) :- nb_getval(counter,V), C is V+1, nb_setval(counter,C).

Answer 3

/* --
1. use `bagof` to obtain a list of the solutions to query `generate_expression(N, E)` .
2. use recursion to :
    2a. iterate each item in the list .
    2b. then assign it a sequence number .
    2c. then print it  .
-- */

/*
example usage :

?- print_expressions_f .
(0000001, generate_expression(4,[op(neg),[[op(neg),[[op(neg),[[number(0)]]]]]]]))
(0000002, generate_expression(4,[op(neg),[[op(add),[[number(0)],[number(0)]]]]]))
(0000003, generate_expression(4,[op(add),[[number(0)],[op(neg),[[number(0)]]]]]))
(0000004, generate_expression(4,[op(add),[[op(neg),[[number(0)]]],[number(0)]]]))
true ;
false.
*/

print_expressions_f :-
    Stream = user_output,
    Prefix = '(',
    Suffix = ')',
    N = 4,
    print_expressions_f(Stream, Prefix, Suffix, N).

print_expressions_f(Stream, Prefix, Suffix, N) :-
    Query = generate_expression(N, E) ,
    bagof(Query,Query,BagofE) ,
    print_expressions_f_every(Stream, Prefix, Suffix, BagofE) .

print_expressions_f_every(Stream, Prefix, Suffix, BagofE) :-
    print_expressions_f_each(Stream, Prefix, Suffix, BagofE, 10'1) .

print_expressions_f_each(Stream, Prefix, Suffix, BagofE, Sequence_number) :-
    [] = BagofE ,
    true .

print_expressions_f_each(Stream, Prefix, Suffix, BagofE, Sequence_number) :-
    [BagofE_head|BagofE_tail] = BagofE ,
    print_expression(Stream, Prefix, Suffix, Sequence_number, BagofE_head) ,
    Sequence_number_next #= Sequence_number + 1 ,
    print_expressions_f_each(Stream, Prefix, Suffix, BagofE_tail, Sequence_number_next) .