Semantics for variable/atom clashes

We have decided to retain the `atom overrides variable' principle, despite the plausible intuitive reasons given in the recent discussion favouring the extension of the `longest path wins' principle to LHS paths containing variables, and note that this solution appears to have been implicitly advocated in an earlier communication in 1996 by Jim Kilbury. We adduce the following reasons for this decision:

1. The `longest path wins' strategy is easily enforced by the simple expedient of declaring the variables and their values. In this case, the desired QDATR-like behaviour is manifested. Declared variables are purely syntactic abbreviations, though combinations of variables are explosive ( combinations for a sequence of y occurrences of the same variable and x declared values for this variable).

   In ZDATR, the semantics of declared variables therefore differ from the semantics of on-the-fly variables.

2. We also consider cases such as the following:

          <a> == foo
          <$a $b $c> == bar

   where query path <a b> matches <a>, but query path <a b c> matches <$a $b $c>, i.e. where there is a path containing variables which is longer than the query path.

   If the `atom overrides variable' principle does not hold, but the `longest path wins' principle is extended to variables, then nondeterministic path/tree search of arbitrary depth (depending on the length of defined paths and query paths) is involved in matching <a b>.

   In this case, DATR matching is only deterministic relative to local nodes if paths are matched `holistically' (possibly the original intention). If variables are not involved, matching is, in addition, left-to-right deterministic at the level of individual attributes (assuming coding of the equations as a decision tree). But if variables are involved, this is not necessarily true, as the above example shows.

   Since matching in DATR is intended to be deterministic, we take this as a breach of the `spirit of DATR'.

3. We have not come across cases which cannot be dealt with using the ZDATR semantics for variables, if slight reformulations are accepted.
4. The incorporation of an `any' or `else' variable mechanism makes DATR even more useful, both for product development on a large scale and as a teaching device, e.g. for integrating (early) Kay or Koskenniemi type systems into DATR.
5. All in all, the cost-benefit ratio of incorporating a new algorithm for non-deterministic tree search appears to us not to justify pursuing this line. Prolog implementers can easily use internal `hidden' housekeeping properties to achieve this end, of course, but, these conspire to disguise the complexity of the problem.