pop/push, shift/unshift

[Simon Schuster]

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?

 

[Konrad Meyer]

--nextPart1470437.F2NYfBXcZq
Content-Type: text/plain;
charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Quoth Simon Schuster:

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.)
=20
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.
=20
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=20
common "visualisation" is to imagine a dinner-plate-stack-holder at a buffe=
t.=20
You push plates down into the spring-loaded stack to add more. When you wan=
t=20
to remove a plate, you pop it out of the top of the stack. That's probably=
=20
not the best description of the idea, but you can always google for push/po=
p.

HTH,
=2D-=20
Konrad Meyer <[email protected]> http://konrad.sobertillnoon.com/

--nextPart1470437.F2NYfBXcZq
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)

iD8DBQBHHXylCHB0oCiR2cwRAhawAJ90jg5XQk3DgyKBQUKWoFQtUpcXvgCcDYNg
sA2ycsG6tcFWifLSreYRL+o=
=J4z4
-----END PGP SIGNATURE-----

--nextPart1470437.F2NYfBXcZq--

 

[Robert Klemme]

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?

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

 

[Thufir]

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

 

[Simon Schuster]

*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.

 

[richard.j.dale]

*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

 

[Randy Kramer]

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 Kramer

 

[Robert Klemme]

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.

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

 

[Randy Kramer]

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 Kramer

 

[David A. Black]

Hi --

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.)

Have a look at #shift and #unshift.


David

--
Upcoming training by David A. Black/Ruby Power and Light, LLC:
* Advancing With Rails, Edison, NJ, November 6-9
* Advancing With Rails, Berlin, Germany, November 19-22
* Intro to Rails, London, UK, December 3-6 (by Skills Matter)
See http://www.rubypal.com for details!

 

[Trans]

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?

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.

 

[Robert Klemme]

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.

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

Kind regards

robert

 

[Jesús Gabriel y Galán]

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 ush
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.

 

[David A. Black]

--1926193751-840406803-1193148362=:30404
Content-Type: MULTIPART/MIXED; BOUNDARY="1926193751-840406803-1193148362=:30404"

This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.

--1926193751-840406803-1193148362=:30404
Content-Type: TEXT/PLAIN; charset=X-UNKNOWN; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

Hi --

I like this:

class Array
alias :enqueue ush
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

--=20
Upcoming training by David A. Black/Ruby Power and Light, LLC:
* Advancing With Rails, Edison, NJ, November 6-9
* Advancing With Rails, Berlin, Germany, November 19-22
* Intro to Rails, London, UK, December 3-6 (by Skills Matter)
See http://www.rubypal.com for details!
--1926193751-840406803-1193148362=:30404--
--1926193751-840406803-1193148362=:30404--

 

[Jesús Gabriel y Galán]

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 =3D []
class << queue
alias :enqueue ush
alias :dequeue :shift
end


Jesus.

 

[Bob Hutchison]

On 23-Oct-07, at 10:02 AM, Jes=FAs Gabriel y Gal=E1n wrote:

Hi,

I like this:

class Array
alias :enqueue ush
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 =20
not the same functions working on opposite ends of the array, no =20
matter what it sounds like from the documentation.

There is an issue with shift that I think amounts to a bug. Shift/=20
unshift work at the beginning of the array, so shift conceptually =20
requires moving array elements around. Ruby (and other programming =20
languages too, specifically some implementations of Common Lisp) =20
optimise shift so as to not have to actually move anything in memory. =20=

What it does is, more or less, to move the start of the array 'right' =20=

-- so no movement but there is now some part of the array before the =20
start of the array. The bug is that Ruby doesn't stomp on the cell of =20=

the array that is being shifted before the start, and so that cell =20
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 =20=

sure, and 'rarely' doesn't help much when you get caught by it. How =20
did I find out about it? Implementing a cache (the uncached stuff was =20=

hanging around in memory, intermittently since unshift will re-use =20
the parts of the array before the start). I also found (and reported, =20=

maybe even supplied a patch for) a problem in Mongrel's thread =20
management code that was using shift. How did I debug it the first =20
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 =20=

it...

class Array
alias :clingy_shift :shift

def shift
self[0] =3D nil
clingy_shift
end
end


Cheers,
Bob

Jesus.

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

 

[David A. Black]

--1926193751-842377821-1193150265=:30997
Content-Type: MULTIPART/MIXED; BOUNDARY="1926193751-842377821-1193150265=:30997"

This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.

--1926193751-842377821-1193150265=:30997
Content-Type: TEXT/PLAIN; charset=X-UNKNOWN; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

Hi --

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 =3D []
class << queue
alias :enqueue ush
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 =3D [].extend(Queue)

(I'm a big #extend fan.)


David

--=20
Upcoming training by David A. Black/Ruby Power and Light, LLC:
* Advancing With Rails, Edison, NJ, November 6-9
* Advancing With Rails, Berlin, Germany, November 19-22
* Intro to Rails, London, UK, December 3-6 (by Skills Matter)
See http://www.rubypal.com for details!
--1926193751-842377821-1193150265=:30997--
--1926193751-842377821-1193150265=:30997--

 

[Bob Hutchison]

On 23-Oct-07, at 10:02 AM, Jes=FAs Gabriel y Gal=E1n wrote:

Hi,


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

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

In your scheme you are using unshift to remove from the front, and =20
push to add to the back. As I mentioned shift moves the start point =20
of the array. Every time you use shift you 'loose' a cell of your =20
array before the start of the array. Unshift will re-use those lost =20
cells (Ruby might be doing something clever with these but I wouldn't =20=

count on it). Push will never reuse them since it is adding to the =20
end of the array. Consequently the Array used for the queue will get =20
larger and larger.

I guess this is just reinforcing David's comment.

Cheers,
Bob

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

You say this will never happen? or rarely? Well, it's not 'never' =20
for sure, and 'rarely' doesn't help much when you get caught by it. =20=

How did I find out about it? Implementing a cache (the uncached =20
stuff was hanging around in memory, intermittently since unshift =20
will re-use the parts of the array before the start). I also found =20
(and reported, maybe even supplied a patch for) a problem in =20
Mongrel's thread management code that was using shift. How did I =20
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 =20
solve it...

class Array
alias :clingy_shift :shift

def shift
self[0] =3D nil
clingy_shift
end
end


Cheers,
Bob

Jesus.

hutch
http://www.recursive.ca/ -- works on http://=20
www.raconteur.info/cms-for-static-content/home/

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

 

[Bob Hutchison]

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 =3D []
class << queue
alias :enqueue ush
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 =3D [].extend(Queue)

(I'm a big #extend fan.)


David

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

Cheers,
Bob

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

 

[Jesús Gabriel y Galán]

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 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.