Transitive closure with logic-programming-based transitions
Stephen Horne
I'm thinking of writing a utility which needs to build digraphs using
a transitive closure. The set of transitions from each state would
most reasonably be defined using a unification-like approach that
derives a set of next-state structures from a start-state structure.
I need to define the rules and goals for the unification at run-time,
and I need support for integer arithmetic with at least three forms of
integer division - rounding down, rounding up, and failing divides if
rounding would be needed. Obviously indirect means of achieving these
such as via a remainder operator would be fine.
Most likely I'm going to work in C++, and use a simple unification
engine. For one thing, the app will have to do a lot of other stuff
that I already have C++ libraries for.
The utility is a code generator for tree structures and related
algorithms. The reason for needing a code generator rather than a
simple library relates to the way summary information is handled in
each node. A policy-based C++ template library could do the job in
theory, but would not be practical or maintainable.
Actually, the code generator already exists, but is overcomplicated
with special-case handling and at the same time pretty naive and
feature-incomplete. The basic aim of the above digraph is to analyse
the cases that are needed in a simple and consistent manner.
Normal problem sizes for the unification engine will be small -
anything from around 10 to around 100 rules would be my guess.
I can certainly deal with this, and the search for relevant
information on implementing unification is why I've been lurking here
for a bit. But...
1. Implementing a unification engine from scratch seems a bit stupid
even if I only need a basic one. Does anyone know of a simple
unification library written in C or C++? Failing that, Pascal,
Modula 2, or Ada? - If it's reasonably small I can always port.
2. I was curious as to whether Prolog can handle the full transitive
closure and digraph building, even though I don't really need it.
My first impression is that the state of the transitive closure
process should be represented as a structure, with members for the
part-built digraph and the queue of states needing to be
evaluated. A complete solution would then be a structure
containing the full digraph and an empty queue.
The start state for the transitive closure could either be a fact
in the rules, or could be an extra member of the goal structure.
The latter seems more reasonable, and intermediate goals during
the unification should probably see this member as the current
from-state for the closure. The functor would probably indicate
different states in the manipulation of the structure, along the
lines of...
- chosen state to handle
- found set of next-states for current state
- digraph extended and next-states pushed to queue
Adding nodes and edges to the digraph itself is non-trivial, but
presumably do-able.
Is this reasonable?
Can anyone point me to some example code that does something
similar?
Another question I have is more general. The unification in Prolog is
basically a depth-first search. It could be considered a transitive
closure itself, but every description I've read suggests it evaluates
a full tree even if intermediate goals recurr. The details of
unification should prevent cycling, though, provided the transitive
closure of intermediate goals is finite - you can't have unification
cycles, and a state can only recur after backtracking.
If the transitive closure of intermediate goals is infinite (which can
occur with recursive structures such as lists), no amount of
recurring-state optimisation can fix it.
Even so, similar search problems are often optimised by detecting the
recurring states, and there are some common approaches to doing that
efficiently. Game trees, for instance, may use Zobrist hashes.
Presumably, there has been work done along these lines for logic
programming. Can anyone give me some pointers on where to look? Any
papers aimed at a reasonably-intelligent-newbie level should be fine,
though I prefer a high English-to-math ratio.
Stephen Horne
<sh006...@blueyonder.co.uk> wrote:
>1. Implementing a unification engine from scratch seems a bit stupid
> even if I only need a basic one. Does anyone know of a simple
> unification library written in C or C++? Failing that, Pascal,
> Modula 2, or Ada? - If it's reasonably small I can always port.
I have found VTProlog - an ancient (1986) Prolog interpreter written
in Pascal. 1500-ish lines of code so it should suit my purposes,
though translating all those nested procedures to C++ will be a pain.
My other questions remain open - I can't afford £130 for a second-hand
"the art of prolog" :-(
Stephen Horne
Actually, I withdraw that.
For some reason, I've completely missed the "Generate State Machine /
Graph" thread until just now. I just downloaded "Logic, Programming
and Prolog" which has some chapters which seem to cover relevant
ground, so special thanks go to the authors Ulf Nilsson and Jan
Maluszynski.