🚀 go-pugleaf

In article <2521@keele.keele.ac.uk>, csa09@seq1.keele.ac.uk (P. Singleton) writes:
about the trick of representing subsets of 1..N as 0, N-1 variables, 1:

> No doubt this is in "The Craft of Prolog", which I _still_ haven't
> bought, or even read much of, but can anyone cite an original or early
> appearance of this trick?

In the Quintus library, library(vsets) contains the text:
    Richard A. O'Keefe got this trick from
    Fernando C. N. Pereira who figured it out after
    Alain Colmerauer told him it could be done.

The fundmamental idea here is the use of variables as switches.  It doesn't
matter how the switches are distributed, the important thing is that
unifying two variables = closing a switch, and
having two distinct values at the ends of a chain of switches =
    "blowing a fuse" if all the switches are closed

For example, you can use this trick to implement "one out of N" constraints
in Prolog, where you can say, in effect:  X in 1..N, X ~= i.  (The neat
trick here is setting up a network of switches so that once N-1 values
have been ruled out, X is automatically bound to the remaining one.)

> I have generalised it to domains which may grow after some
> subsets have already been denoted: one way is to leave each list
> somewhat unbound at its tail, and a more ambitious variation uses
> sparse binary trees which should be more efficient for small subsets
> of large domains.  Dare I claim originality for these in my thesis?

Lists are not the important point.  library(vsets), for example, uses
compound terms (which makes fast "X ~= i" statements possible).
I have recently been trying to come up with a good representation for
intervals, and it looked as though sets would be no harder.  My current
idea is to use something would could fairly be called a sparse binary tree.
I wonder whether we have the same idea?  It sounds as though you're
further along.

-- 
I am writing a book on debugging aimed at 1st & 2nd year CS students using
C/Modula/Pascal-like languages.  Please send suggestions (other than "you
_must_ cite "C Traps and Pitfalls") to ok@goanna.cs.rmit.oz.au