  Many metainterpreters found in the logic programming literature are
nondeterministic in the sense that the selection of program clauses is not
determined. Examples are the familiar "demo" and "vanilla" metainterpreters.
For some applications this nondeterminism is convenient. In some cases,
however, a deterministic metainterpreter, having an explicit selection of
clauses, is needed. Such cases include (1) conversion of OR parallelism into
AND parallelism for "committed-choice" processors, (2) logic-based,
imperative-language implementation of search strategies, and (3) simulation of
bounded-resource reasoning.
  Deterministic metainterpreters are difficult to write because the programmer
must be concerned about the set of unifiers of the children of a node in the
derivation tree. We argue that it is both possible and advantageous to write
these metainterpreters by reasoning in terms of object programs converted into
a syntactically restricted form that we call "chain" form, where we can forget
about unification, except for unit clauses. We give two transformations
converting logic programs into chain form, one for "moded" programs (implicit
in two existing exhaustive-traversal methods for committed-choice execution),
and one for arbitrary definite programs. As illustrations of our approach we
show examples of the three applications mentioned above.
