LENGTH optimization?

[Dan Cerys <cerys@bbn.com>]

    Are there any LISP implementations that attempt to make LENGTH
   of a list be a less than linear-time operation. I can imagine
   especially for immutable lists that this is easily achieved.
   Only SET-CDR! seems to be a fly in the ointment.

The Zetalisps of old (probably still true of Explorers and Genera) used to
provide an ART-Q-LIST array type.  Such arrays were a cross between a
general (ART-Q) array and a list.  Application of the wonderfully mnemonic
G-L-P function would return the "list" equivalent of the array.  Preventing
any flies from mucking about, SET-CDR! (RPLACD) on this "list" was an
error.  Because of these restrictions, it would seem that LENGTH of such
"lists" would require constant time, regardless of length (just like
determining LENGTH of an array).  However, I don't know if this was the
case. 

Dan