This subsection provides an alternative encoding of `bags',
^{4.3}
in order for the `consume_guide' predicate to be deterministic. The revised
parser can then be shown to be minimal.

An empty bag is represented by the constant `bag'. A nonempty bag
consists of three parts: an element, a (representation of a) number
indicating how often this element occurs in the bag, and the rest of
the bag. Furthermore, the elements in the bag are ordered in
some standard order. For example, in Prolog the bag
{*a*, *b*, *a*, *a*, *b*, *c*}
is represented as:

This technique is easily inherited in
() where I encode such an
example as:

For clarity I write such a bag as:

and use the usual list notation.

The parser is modified as follows. The predicate which calls the
parser will contain an extra predicate,
,
which
encodes a list as a bag. Furthermore this bag is given as the input
argument to
*parse*/3; the output argument is the empty bag, the
constant `
bag'.

The `consume_guide' predicate is now defined for such bags, as follows:

This definition of the predicate `consume_guide' is deterministic
given the first two arguments, and given the fact that the elements of
the bag are always constants. The modified version of the parser is
minimal.

1998-09-30