Stacks (PUSH POP) with lists and vectors
Reini Urban
Maybe this was discussed before, but I couldn't find a pointer.
It was not discussued in any CLHS cleanup issue.
The problem is mainly improper naming:
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)
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.
This would not have been an issue if not only push/pop macros would have
been standardized, also the non-destructive generalized readers for such
an important abstract datatype (something like stack-first, stack-next).
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.
Not that peeking the stack is that important for the user. But I miss a
clear statement of the reverse problem (or a naming problem) in the CLHS
and CLtL2 with vector-pop/vector-push/vector-push-extend.
CLtL2 only explains this:
"It is instructive to compare vector-push, which is a function, with
push, which is a macro that requires a place suitable for setf. A vector
with a fill pointer effectively contains the place to be modified in its
fill-pointer slot."
The macro vs. function problem is a non-issue compared to the
differences in left-end and right-end storage.
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)
just my two cents.
--
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html
Barry Margolin
Reini Urban <rur...@sbox.tu-graz.ac.at> wrote:
>Another minor concern of mine which might annoy newbies.
>Maybe this was discussed before, but I couldn't find a pointer.
>It was not discussued in any CLHS cleanup issue.
>
>The problem is mainly improper naming:
>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)
This is due to the nature of these data structures: with lists, inserting
at the front is efficient; with vectors having fill pointers, appending to
the end is efficient (except when you have to grow the array).
>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.
Then you should abstract what you're doing into higher level operators,
perhaps using CLOS to hide the representation and allow you to change it.
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
David D. Smith
> Another minor concern of mine which might annoy newbies.
> Maybe this was discussed before, but I couldn't find a pointer.
> It was not discussued in any CLHS cleanup issue.
>
> The problem is mainly improper naming:
> 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)
>
> 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.
(defun peek (x n)
(if (listp x)
(nth n x)
(elt x (- (length x) n 1))))
(peek '(4 3 2 1) 1) => 3
(peek '#(1 2 3 4) 1) => 3
etc.
d
Kent M Pitman
> In article <37f0c2e0.16126608@judy>,
> Reini Urban <rur...@sbox.tu-graz.ac.at> wrote:
> >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)
>
> This is due to the nature of these data structures: with lists, inserting
> at the front is efficient; with vectors having fill pointers, appending to
> the end is efficient (except when you have to grow the array).
>
> >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.
>
> Then you should abstract what you're doing into higher level operators,
> perhaps using CLOS to hide the representation and allow you to change it.
Maybe something like:
(defgeneric top (stack))
(defmethod top ((x null)) (error "The stack is empty."))
(defmethod top ((x cons)) (car x))
(defmethod top ((x vector))
(let ((n (length x)))
(if (= n 0)
(error "The stack is empty.")
(aref x (1- n)))))
(defgeneric empty? (stack))
(defmethod empty? ((x null)) t)
(defmethod empty? ((x cons)) nil)
(defmethod empty? ((x vector)) (= (length x) 0))
Caveat: I didn't test this.
David Hanley
Reini Urban wrote:
> The problem is mainly improper naming:
> 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)
>
> 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.
That doesn't sound too hard, if fact it's so easy to deal with I bet
the simply won't bother ( or maybe add this function ):
(defun peek(x)
(if (consp x) (car x) (aref x (1- (length x))))
Obviously, the same could be done for push/pop.
dave
Erik Naggum
| 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
Dobes Vandermeer
>
> Barry Margolin <bar...@bbnplanet.com> writes:
>
> > In article <37f0c2e0.16126608@judy>,
> > Reini Urban <rur...@sbox.tu-graz.ac.at> wrote:
> > >for vectors it is reverse, the actual pointer is at the end. (the
> > >fill-pointer)
> >
> > at the front is efficient; with vectors having fill pointers, appending to
> > the end is efficient (except when you have to grow the array).
> >
> > >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.
> >
> > perhaps using CLOS to hide the representation and allow you to change it.
>
> Maybe something like:
>
> (defgeneric top (stack))
> (defmethod top ((x null)) (error "The stack is empty."))
> (defmethod top ((x cons)) (car x))
> (defmethod top ((x vector))
> (let ((n (length x)))
> (if (= n 0)
> (error "The stack is empty.")
> (aref x (1- n)))))
>
> (defgeneric empty? (stack))
> (defmethod empty? ((x null)) t)
> (defmethod empty? ((x cons)) nil)
> (defmethod empty? ((x vector)) (= (length x) 0))
>
> Caveat: I didn't test this.
And iteration over the "stack":
(defgeneric stack-nth (stack))
(defmethod (stack null) n) nil)
(defmethod (stack cons) n) (nth stack n))
(defmethod (stack vector) n) (aref stack (- (length x) n 1))
Plus a (do-stack ..) macro etc.
(Didnt actually test this either)
CU
Dobes