Representation of bags.

This subsection provides an alternative encoding of `bags', <sup>4.3</sup> 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 $\cal {R}$($\cal {L}$) where I encode such an example as:

For clarity I write such a bag as:

$$\langle a/3, b/2, c/1 \rangle$$
and use the usual list notation.

The parser is modified as follows. The predicate which calls the parser will contain an extra predicate, $\mbox{\it list\_to\_bag}/2$, 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.