Subject: Re: Stacks (PUSH POP) with lists and vectors
From: Erik Naggum <erik@naggum.no>
Date: 1999/09/28
Newsgroups: comp.lang.lisp
Message-ID: <3147542211215804@naggum.no>

* Reini Urban
| The stack pointer for lists is at the front (as one might suspect), but
| for vectors it is reverse, the actual pointer is at the end.  (the
| fill-pointer)

  hm?  you didn't expect this?

| This might not harm anyone if only push/pop pairs are used.  Then you
| could switch your data structures internally between lists and adjustable
| vectors (with fill-pointers) at wish.  But what about peeking the stack?
| looking at the actual stack element without destroing (popping) it?  or
| even iterating over the stack.  I often use the push/pop macro for
| convenience, but when I want to switch to vectors I'm in trouble too.

  it seems that it is important to you that you know the underlying
  representation and that suggests to me that your design is weak.

  a PEEK macro could POP and PUSH it back before returning it.  a
  VECTOR-PEEK function could VECTOR-POP and VECTOR-PUSH it back.  in
  general, this is how similar peek functions are implemented.  any other
  way is just an optimization, not a change in semantics.

  a TRAVERSE function could REVERSE the stack first and POP all the way.
  (barring the quirk that REVERSE does not preserve non-simpleness.)

  I don't see the problem.

| Or seen from the other way, if push/pop would have been extended to
| adjustable arrays as well. this would have required an explicit and
| lengthy description of this problem then.

  I don't see why you would need that.

| The macro vs. function problem is a non-issue compared to the differences
| in left-end and right-end storage.

  in the above informal definitions of PEEK and TRAVERSE the storage layout
  is insignificant.

| perl overcame this problem by introducing shift/unshift for the left end
| modification of arrays and leaving push/pop handling the right end.
| (which is a quirky naming but okay for arrays only, perl has no native
| linked lists)

  the quirky naming scheme comes from shifting the argument vector in shell
  scripts.  "shift n" discards the n left-most argument, such that what
  remains are still numbered $1, $2, etc.  the operator has been with us
  since trusty old Bourne wrote his shell.

  it appears to me that Perl damages the aesthetic sense of the user and
  that the road back is tough indeed.

#:Erik