locatives; supported-p? alternatives-p?

[miller@cs.rochester.edu]

Hi,

I've got an algorithm that's begging for locatives (i.e. for those of
you who don't recall lispms: a way to refer to, say, the car or cdr of a
cons cell (for destructive update) w/o having the cell in front of you).
My question is, is there some version of these (even "internal" that I
can use inside a (with-all-due-respect ...))?

Application:

Lets call "?x" a variable. Variables can have values, and can become
unbound (via backtracking), but you can't assign a variable to have a
different value than it already has. (yep, prolog model of assignment).

here's what a "list" might look like... thanks to binding variables to
lists of other variables... where -> denotes a binding.

(?x->:b . ?y->(?z->:c . ?q->nil))

to denote the list (:b :c)

Now the reason locatives come in handy: when we bind ?x, it would be
extremely handy to update the locative for ?x in the above list with the
binding. In this manner the above list would be represented (at some
point in the run time) as

(:b :c)

and if we, e.g. backtrack the binding to ?q we'd update the locative to
put back the variable, e.g.

(:b :c . ?q)

I'm pursuing this, because it turns out about 70% or so of the time my
system uses to run some benchmarks is in examining such lists, and
getting rid of the variables. Instead of where it should be spending
most of the time: in unification.

I realize I can keep track of all parent cons cells instead of having
direct locatives, or use extensible vectors and offsets instead of
lists; right now I'm looking for the highest efficiency solution which
would seem to be the locative. Extensible vectors are slower than lists
for small sizes (I've metered), esp. on consing up new vectors.

Other suggestions are welcome, of course! 

Thanks for taking the time to read this!!

Brad Miller
miller@cs.rochester.edu