ADT ListLISP

[Michael van Acken <KK120y2@mail.lvr.de>]

Thanks to Tim we have some additional module outlines to discuss.  We
will readily agree with the abstract types for queues and stacks,
although I would change a detail or two (e.g., I would make `Pop' the
inverse operation to `Push').  Did anyone have a look at the Tim's
AcStack and AcQueue modules and have some suggestions to add?

The concrete implementation of ListLISP is not so straightforward.
How do we encode the lispish data structure?  And: Do we allow
sharing of list elements between lists?  With this I mean that a list
tail may appear in multiple lists, e.g.

  ListA o---o---o
                 \
                  o---o---o
                 /
  ListB         o

Here we have two lists, that share their last three elements.  I
would
prefer to have this keep of sharing in the specs, as an alternative
to
the more restricted double-linked list.

Back to the data structure:

(* variant 1 *)
  ListDesc* = RECORD
    (AcContainer.ContainerDesc)
    car-: AcObject.Object;
    cdr-: List;
  END;

Problem: The empty list is encoded as NIL.  This means that a call
like `l.Empty()' will either trap (if `l' is empty), or return TRUE
otherwise. 

(* variant 2 *)
  ConsCell = POINTER TO ConsCellDesc;
  ConsCellDesc = RECORD
    car-: AcObject.Object;
    cdr-: ConsCell;
  END;
  ListDesc* = RECORD
    (AcContainer.ContainerDesc)
    head: ConsCell;
  END;

Not exactly lispish, but IMO the best we can do.

Comments?

-- mva