CODEWITHSUNDEEP
prolog
user55776
user55776

Reputation:

Traversing/recording matched predicates

I have a sequence of relations and I want to traverse them like a graph by recording the matches as I go. Say for example we have the following bizzare situation in a system that supports the following library functions for graphical manipulation:

image(raw).
image(png).
image(bitmap).
image(tiff).
conversion(tiff2bitmap, tiff, bitmap).
conversion(bitmap2png, bitmap, png).
conversion(png2raw, png, raw).
conversion(raw2bitmap, raw, bitmap).
conversion(png2tiff, png, tiff).

operation(crop, raw, raw).

So in the above example if we wanted to crop a tiff, you would have to do the following:

For example, I could sit at the Prolog REPL and begin by asking what operation to convert a tiff to a bitmap with:

?- conversion(OP1, tiff, F1).
OP1 = tiff2bitmap,
F1 = bitmap .
?- conversion(OP2, F1, F2).
OP2 = tiff2bitmap,
F1 = tiff,
F2 = bitmap ;
OP2 = bitmap2png,
F1 = bitmap,
F2 = png 
... and so on

I want to be able to follow the following logic in Prolog but I do not know how to approach this. I think I need to use recursive rules and accumulators. We could work out how to crop a tiff using the following. I can solve the above manually like so:

/* the op is op in operation(op, x, x) */
conversions(Op, In, Steps) :-
  operation(Op, In, Out); /* no conversions necessary */
  conversion(C1, O1, O2),/* switch the incoming/outgoing to */
  conversion(C2, O2, O3), /* match successive conversions */
  conversion(C3, O3, O4), /* A->B, B->C, C->D */

  /* adding the matches C1-C3 to steps */

I would much prefer handle this automatically with accumulators and recursive rules but I do not know how to approach this.

Upvotes: 2

Views: 140

Answers (2)

mat
mat

Reputation: 40768

When describing lists, always consider using DCGs. In your case, you only need the following:

conversions(S, S) --> [].
conversions(S0, S) -->
        { conversion(Op, S0, S1) },
        [Op],
        conversions(S1, S).

You can now use iterative deepening to try increasingly longer lists of operations exhaustively, until you reach a desired target state. For example, to get from tiff to raw:

?- length(Ops, _), phrase(conversions(tiff, raw), Ops).
Ops = [tiff2bitmap, bitmap2png, png2raw] .

Upvotes: 1

user55776
user55776

Reputation:

After larsmans mentioned "path search", I searched and found a "TekTips question ". From this, the following seems to work:

image(raw).
image(png).
image(bitmap).
image(tiff).
conversion(tiff2bitmap, tiff, bitmap).
conversion(bitmap2png, bitmap, png).
conversion(png2raw, png, raw).
conversion(raw2bitmap, raw, bitmap).
conversion(png2tiff, png, tiff).

operation(crop, raw, raw).

sconversions(End, A, End, [Conv]) :-
    conversion(Conv, A, End).

sconversions(End, A, B, Ops) :-
    conversion(X, A, C),
    sconversions(End, C, B, TailOps),
    Ops = [X|TailOps].

convert(Op, A, Path) :-
    operation(Op, In, _),
    sconversions(In, A, In, Path).

convertKeep(Op, A, Path) :-
    operation(Op, In, Out),
    sconversions(In, A, In, CPath),
    sconversions(A, Out, A, RPath), /* backward */
    append(CPath, RPath, Path).

Conversions disregarding the output format:

?- convert(crop, tiff, Ops).
Ops = [tiff2bitmap, bitmap2png, png2raw, crop]

The following shows the conversions: ?- convertKeep(crop, tiff, Ops). Ops = [tiff2bitmap, bitmap2png, png2raw, crop, raw2bitmap, bitmap2png, png2tiff]

I am new to Prolog, visitors would be better off studying larsmans' answer.

Upvotes: 2

Related Questions