Pop/push, shift/unshift

simonsaid · October 23, 2007, 11:28am

the inconsistency in naming bothers me. I would imagine that it
comes from push/pop being older, and shift/unshift being added later
(probably I would guess that both of these are pre-ruby programming
ideas. I know I’ve seen push/pop before.)

I would like to see either push/pop changed to be
something/unsomething, or shift/unshift changed to be um, visualish
ideas of what’s going on (or whatever push/pop is.) my preference
would be push/pop changed to something/unsomething. or maybe
front_add, front_del, back_add, back_del.

just trying to get a gut-grip on these four array processes, and I’m
pushing and popping and shifting and unshifting left and right (and
back and forth?) and it’s taking a surprising amount of time to “grok”
them. does anyone think this is a naming convention that could benefit
with some change, or am I just being strange?

simonsaid · October 23, 2007, 11:51am

On Tue, 23 Oct 2007 12:53:02 +0900, Simon S. wrote:

just trying to get a gut-grip on these four array processes, and I’m
pushing and popping and shifting and unshifting left and right (and back
and forth?) and it’s taking a surprising amount of time to “grok” them.
does anyone think this is a naming convention that could benefit with
some change, or am I just being strange?

http://en.wikipedia.org/wiki/Stack_(data_structure)#Operations

The way I think of a stack is as, literally, a stack of plates. A
cafeteria with a stack of plates where the stack is placed on a spring
so
that when one plate is picked up (popped), the one below pops up and can
be accessed. The other plates aren’t accessible because they’re in the,
err, cabinet. When a plate is put on the stack, of course, it pushes
down the other plates.

-Thufir

simonsaid · October 23, 2007, 11:51am

On 23.10.2007 05:53, Simon S. wrote:

just trying to get a gut-grip on these four array processes, and I’m
pushing and popping and shifting and unshifting left and right (and
back and forth?) and it’s taking a surprising amount of time to “grok”
them. does anyone think this is a naming convention that could benefit
with some change, or am I just being strange?

I think you just should get used to the terminology. Whatever naming is
choosen it is artificial - you can always argue about whether the end
(highest index) or the beginning (lowest index) of the Array is the top
or bottom of the stack etc. So not changing is definitively the better
choice - just think about all the confusion created by all those people
who use this regularly. Also keep in mind that changing these would
break a hell lot of code.

Why don’t you just create yourself a simple test script that uses all of
those methods and invoke it whenever you need to remind yourself of the
proper wording?

Kind regards

robert

simonsaid · October 23, 2007, 11:51am

Quoth Simon S.:

just trying to get a gut-grip on these four array processes, and I’m
pushing and popping and shifting and unshifting left and right (and
back and forth?) and it’s taking a surprising amount of time to “grok”
them. does anyone think this is a naming convention that could benefit
with some change, or am I just being strange?

Push and pop have been around as instructions since the days of asm. The
common “visualisation” is to imagine a dinner-plate-stack-holder at a
buffet.
You push plates down into the spring-loaded stack to add more. When you
want
to remove a plate, you pop it out of the top of the stack. That’s
probably
not the best description of the idea, but you can always google for
push/pop.

HTH,

simonsaid · October 23, 2007, 12:41pm

On Oct 23, 10:50 am, “Simon S.” [email protected] wrote:

yawn oh, what? people have been using these terms for a long time?
oh wow, yeah, clearly important.

ahem but what about the idea that it’s four points of inter-related
methods? I guess that’s not as important as tradition…
One of the strengths of Ruby is that it borrows good things from
various other languages such as method names. Often it will have the
Lisp name of a method as well as the Smalltalk equivalent, for
instance ‘map’ is from Lisp and ‘collect’ is from Smalltalk although
they are equivalent.

If you’re new to programming and Ruby is one of your first languages
that won’t be obvious. Pushing and popping items on and off a stack
are basic ideas in Computer Science and it’s a good idea to be
familiar with the terms normally used as soon as possible. ‘shift’ and
‘unshift’ as Array operations I associate with Perl, and for people
who already know Perl, that is one less new name to learn.

Maybe ‘enque’ and ‘deque’ could be used as names for methods to put
items on the front of a Queue and remove items from the back somewhere
in Ruby - then you wouldn’t need push/pop and shift/unshift depending
on which end of the queue you were operating on.

But I can’t see any point in deliberately ignoring what has come
before - of course it is important to be familiar with terms people
have been using for a long time.

– Richard

simonsaid · October 23, 2007, 1:40pm

On Tuesday 23 October 2007 12:46 am, Konrad M. wrote:

Push and pop have been around as instructions since the days of asm. The
common “visualisation” is to imagine a dinner-plate-stack-holder at a
buffet.
You push plates down into the spring-loaded stack to add more. When you want
to remove a plate, you pop it out of the top of the stack. That’s probably
not the best description of the idea, but you can always google for
push/pop.

I always liked that visualization. The problem for me (and I’m not the
OP) is
that in Ruby you have to lift all the plates off, put the new plate on
the
bottom, and then put all the plates back. (Likewise when you want to
“pop”
that plate.) (Because Ruby uses push and pop on the end of the
array
instead of the beginning.)

It’s not a major problem, but it did surprise me the first time I ran
into it,
and I suppose this approach is a little easier to implement.

(And, if push and pop were built on a separate “stack” data structure
(instead
of being built on the array structure (with various other paradigms,
like
being able to access any item in the array via the index), this point
would
not come up.)

Randy K.

simonsaid · October 23, 2007, 1:45pm

2007/10/23, Randy K. [email protected]:

that in Ruby you have to lift all the plates off, put the new plate on the
bottom, and then put all the plates back. (Likewise when you want to “pop”
that plate.) (Because Ruby uses push and pop on the end of the array
instead of the beginning.)

I’m not sure what exactly you mean. #push and #pop just work as one
would expect from a LIFO.

It’s not a major problem, but it did surprise me the first time I ran into it,
and I suppose this approach is a little easier to implement.

(And, if push and pop were built on a separate “stack” data structure (instead
of being built on the array structure (with various other paradigms, like
being able to access any item in the array via the index), this point would
not come up.)

Frankly, I don’t understand your point. You can use an Array as LIFO
just the same. There is no additional lifting etc. involved. And for
this it’s completely irrelevant whether they use lowest or highest
index for their operation.

Kind regards

robert

simonsaid · October 23, 2007, 11:55am

yawn oh, what? people have been using these terms for a long time?
oh wow, yeah, clearly important.

ahem but what about the idea that it’s four points of inter-related
methods? I guess that’s not as important as tradition…

ahem

… I mean, tradition and mathematics, they’re key. just look at
edison and tesla.

simonsaid · October 23, 2007, 2:32pm

On Tuesday 23 October 2007 07:44 am, Robert K. wrote:

2007/10/23, Randy K. [email protected]:

On Tuesday 23 October 2007 12:46 am, Konrad M. wrote:

Push and pop have been around as instructions since the days of asm. The
common “visualisation” is to imagine a dinner-plate-stack-holder at a
buffet.
You push plates down into the spring-loaded stack to add more. When you
want
to remove a plate, you pop it out of the top of the stack. That’s
probably
not the best description of the idea, but you can always google for
push/pop.

I always liked that visualization. The problem for me (and I’m not the
OP) is
that in Ruby you have to lift all the plates off, put the new plate on the
bottom, and then put all the plates back. (Likewise when you want to
“pop”
that plate.) (Because Ruby uses push and pop on the end of the array
instead of the beginning.)

I’m not sure what exactly you mean. #push and #pop just work as one
would expect from a LIFO.

Well, it was partly an attempt at humor, and partly the result of some
strange
coding I did recently in a program to convert files in what I call
askRhk03
format to askRhk04 format.

In doing that, I had the need (or it seemed convenient) to both push and
pop
things on to the array, but then also access all the items in the array
in
order. (I.e., using something like array.each { }

But, the first time I attempted it, without noticing that a push
occurred on
the end of the array instead of the beginning, I got the wrong results.
(No
big deal, I just used array.reverse first.)

Randy K.

It’s not a major problem, but it did surprise me the first time I ran into
it,
and I suppose this approach is a little easier to implement.

(And, if push and pop were built on a separate “stack” data structure
(instead
of being built on the array structure (with various other paradigms, like
being able to access any item in the array via the index), this point
would
not come up.)

Frankly, I don’t understand your point. You can use an Array as LIFO
just the same. There is no additional lifting etc. involved. And for
this it’s completely irrelevant whether they use lowest or highest
index for their operation.

simonsaid · October 23, 2007, 2:38pm

Hi –

On Tue, 23 Oct 2007, Randy K. wrote:

not the best description of the idea, but you can always google for
I’m not sure what exactly you mean. #push and #pop just work as one
But, the first time I attempted it, without noticing that a push occurred on
the end of the array instead of the beginning, I got the wrong results. (No
big deal, I just used array.reverse first.)

Have a look at #shift and #unshift.

David

simonsaid · October 23, 2007, 2:47pm

On Oct 22, 11:53 pm, “Simon S.” [email protected] wrote:

just trying to get a gut-grip on these four array processes, and I’m
pushing and popping and shifting and unshifting left and right (and
back and forth?) and it’s taking a surprising amount of time to “grok”
them. does anyone think this is a naming convention that could benefit
with some change, or am I just being strange?

Some things you just have to get used to. And some things are worth
getting used to

I think push and pop are worthy, but I’ve never come to terms with
shift and unshift. Not only do they seem backwards to me, but the
words themselves have little mnemonic value. In my work I often alias
shift as pull. That fits nicely with push and pop. Unfortunately I’ve
yet to find a better substitute for unshift. I’ve tried things like
‘pot’ (for put on top) and ‘place’, and more recently ‘poke’, though
traditionally that is more akin to insert, but nothing has really
stood out as of yet.

T.

simonsaid · October 23, 2007, 4:02pm

On 10/23/07, [email protected] [email protected] wrote:

Maybe ‘enque’ and ‘deque’ could be used as names for methods to put
items on the front of a Queue and remove items from the back somewhere
in Ruby - then you wouldn’t need push/pop and shift/unshift depending
on which end of the queue you were operating on.

I like this:

class Array
alias :enqueue :push
alias :dequeue :shift
end

Then you get Queue semantics and the start of the queue is the first
element in the Array :-). (you could do enqueue → unshift, dequeue
→ pop if you rather have the first element of the queue the last in
the array).

Jesus.

simonsaid · October 23, 2007, 4:24pm

2007/10/23, Trans [email protected]:

ideas of what’s going on (or whatever push/pop is.) my preference
getting used to

I think push and pop are worthy, but I’ve never come to terms with
shift and unshift. Not only do they seem backwards to me, but the
words themselves have little mnemonic value. In my work I often alias
shift as pull. That fits nicely with push and pop. Unfortunately I’ve
yet to find a better substitute for unshift. I’ve tried things like
‘pot’ (for put on top) and ‘place’, and more recently ‘poke’, though
traditionally that is more akin to insert, but nothing has really
stood out as of yet.

If you do bourne shell programming then “shift” will be familiar.
From there it’s not too far to “unshift”.

Kind regards

robert

simonsaid · October 23, 2007, 4:09pm

Hi –

On Tue, 23 Oct 2007, Jesús Gabriel y Galán wrote:

alias :enqueue :push
alias :dequeue :shift
end

Then you get Queue semantics and the start of the queue is the first
element in the Array :-). (you could do enqueue --> unshift, dequeue
–> pop if you rather have the first element of the queue the last in
the array).

No thanks. #shift/#unshift are fine, and certainly I don’t want to
have to figure out what people have aliased enqueue and dequeue to
before I can understand their code.

David

simonsaid · October 23, 2007, 4:32pm

On 10/23/07, David A. Black [email protected] wrote:

→ pop if you rather have the first element of the queue the last in
the array).

No thanks. #shift/#unshift are fine, and certainly I don’t want to
have to figure out what people have aliased enqueue and dequeue to
before I can understand their code.

Fair enough, although the idea was to use such an object using just
queue semantics, so everybody knows what enqueue/dequeue do. Maybe
aliasing them in Array doesn’t make sense: what about having those
alias in a class Queue < Array or in the instance of the array you
plan to use just as a queue?

queue = []
class << queue
alias :enqueue :push
alias :dequeue :shift
end

Jesus.

simonsaid · October 23, 2007, 4:39pm

Hi –

On Tue, 23 Oct 2007, Jesús Gabriel y Galán wrote:

element in the Array :-). (you could do enqueue --> unshift, dequeue
alias in a class Queue < Array or in the instance of the array you
plan to use just as a queue?

queue = []
class << queue
alias :enqueue :push
alias :dequeue :shift
end

Now you’re talking You could even wrap it up like this:

module Queue
def self.extend_object(o)
class << o
alias enqueue push
alias dequeue shift
end
end
end

q = [].extend(Queue)

(I’m a big #extend fan.)

David

simonsaid · October 23, 2007, 4:43pm

On 23-Oct-07, at 10:32 AM, Bob H. wrote:

somewhere

Then you get Queue semantics and the start of the queue is the first
element in the Array :-). (you could do enqueue → unshift, dequeue
→ pop if you rather have the first element of the queue the last in
the array).

You have to be really careful here. Push/pop and shift/unshift are
not the same functions working on opposite ends of the array, no
matter what it sounds like from the documentation.

Of course I forgot to mention the specific problem for your scheme.
My previous email outlines how un/shift works (see below, I left it
quoted).

In your scheme you are using unshift to remove from the front, and
push to add to the back. As I mentioned shift moves the start point
of the array. Every time you use shift you ‘loose’ a cell of your
array before the start of the array. Unshift will re-use those lost
cells (Ruby might be doing something clever with these but I wouldn’t
count on it). Push will never reuse them since it is adding to the
end of the array. Consequently the Array used for the queue will get
larger and larger.

I guess this is just reinforcing David’s comment.

Cheers,
Bob

start, and so that cell still contains a reference to some object
clingy_shift

Bob H. – tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. – weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ – works on http://www.raconteur.info/
cms-for-static-content/home/

simonsaid · October 23, 2007, 4:34pm

On 23-Oct-07, at 10:02 AM, Jesús Gabriel y Galán wrote:

Hi,

class Array
alias :enqueue :push
alias :dequeue :shift
end

Then you get Queue semantics and the start of the queue is the first
element in the Array :-). (you could do enqueue → unshift, dequeue
→ pop if you rather have the first element of the queue the last in
the array).

You have to be really careful here. Push/pop and shift/unshift are
not the same functions working on opposite ends of the array, no
matter what it sounds like from the documentation.

There is an issue with shift that I think amounts to a bug. Shift/
unshift work at the beginning of the array, so shift conceptually
requires moving array elements around. Ruby (and other programming
languages too, specifically some implementations of Common Lisp)
optimise shift so as to not have to actually move anything in memory.
What it does is, more or less, to move the start of the array ‘right’
– so no movement but there is now some part of the array before the
start of the array. The bug is that Ruby doesn’t stomp on the cell of
the array that is being shifted before the start, and so that cell
still contains a reference to some object (and IT IS INVISIBLE).

You say this will never happen? or rarely? Well, it’s not ‘never’ for
sure, and ‘rarely’ doesn’t help much when you get caught by it. How
did I find out about it? Implementing a cache (the uncached stuff was
hanging around in memory, intermittently since unshift will re-use
the parts of the array before the start). I also found (and reported,
maybe even supplied a patch for) a problem in Mongrel’s thread
management code that was using shift. How did I debug it the first
time? Don’t ask.

I believe/hope that this will be fixed in some future version of Ruby.

This monkey patch fixes the problem, if this is how you want to solve
it…

class Array
alias :clingy_shift :shift

def shift
self[0] = nil
clingy_shift
end
end

Cheers,
Bob

Jesus.

Bob H. – tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. – weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ – works on http://www.raconteur.info/
cms-for-static-content/home/

simonsaid · October 23, 2007, 4:53pm

On 10/23/07, Bob H. [email protected] wrote:

the array).
In your scheme you are using unshift to remove from the front, and
push to add to the back. As I mentioned shift moves the start point
of the array. Every time you use shift you ‘loose’ a cell of your
array before the start of the array. Unshift will re-use those lost
cells (Ruby might be doing something clever with these but I wouldn’t
count on it). Push will never reuse them since it is adding to the
end of the array. Consequently the Array used for the queue will get
larger and larger.

I understand your explanation, but this sounds like a bug to me. I
understand the optimization part of not shifting everything in the
shift method, but if that’s a desired way of working I suppose it
should be warned for the users of Array. In light of this then, the
recommended approach for queue semantics would be to use unshift and
pop?

Thanks,

Jesus.

simonsaid · October 23, 2007, 4:58pm

On 10/23/07, Bob H. [email protected] wrote:

class << queue
alias dequeue shift

This is potentially a troublesome implementation. I believe that the
queue is going to grow and grow. See my other messages about the
behaviour of un/shift.

As I understand this is only a problem with shift, and not with pop, I
propose this:

module Queue
def self.extend_object(o)
class << o
alias enqueue unshift
alias dequeue pop
end
end
end

q = [].extend(Queue)

Jesus.