Pop/push, shift/unshift

ruby-talk
21

Thanks! (I did notice those later.)

Randy Kramer

···

On Tuesday 23 October 2007 08:37 am, David A. Black wrote:

Have a look at #shift and #unshift.

22

It was my understanding that unshift was the leaky method. There was a
monkey patch but I have lost the reference to that thread.

···

On Oct 23, 10:32 am, Bob Hutchison <hu...@recursive.ca> wrote:

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

Hi,

> On 10/23/07, richard.j.d...@gmail.com <richard.j.d...@gmail.com> > > 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).

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 Hutchison -- tumblelog at http://www.recursive.ca/so/
Recursive Design Inc. -- weblog athttp://www.recursive.ca/
hutchhttp://www.recursive.ca/ -- works onhttp://www.raconteur.info/
cms-for-static-content/home/- Hide quoted text -

- Show quoted text -

23

Could this lead to a security problem down the road?

-Thufir

···

On Tue, 23 Oct 2007 23:32:01 +0900, Bob Hutchison wrote:

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.

24

Not only that, but enqueue and dequeue return different objects.
Enqueue returns an array, and dequeue returns the object that was
shifted from the stack.

Todd

···

On 10/23/07, David A. Black <dblack@rubypal.com> wrote:

Hi --

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

> On 10/23/07, richard.j.dale@gmail.com <richard.j.dale@gmail.com> 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).

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.

25

Or, in a similar vein perhaps Disney.

Repugnant or not?:

···

On 10/25/07, Giles Bowkett <gilesb@gmail.com> wrote:

> Other people, however, believe that you enter a queue at
> the head and leave at the tail, in the manner of food passing through a
> snake. Queues written in that way appear in places that might be
> considered authoritiative, such as the GNU/Linux operating system, making
> the point of view hard to dismiss however repugnant you find the idea of
> getting your data from a snake's rear-end."
>
> <http://en.wikipedia.org/wiki/FIFO&gt;

Repugnant is definitely the word. I don't like the idea of getting my
information from a snake's asshole. If I wanted to do that, I'd talk
to Steven Ballmer.

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

26

Hi --

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

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

Now you're talking :slight_smile: 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

···

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

On 10/23/07, David A. Black <dblack@rubypal.com> wrote:

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

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

27

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.

···

On 10/23/07, Bob Hutchison <hutch@recursive.ca> wrote:

On 23-Oct-07, at 10:32 AM, Bob Hutchison wrote:
> On 23-Oct-07, at 10:02 AM, Jesús Gabriel y Galán wrote:
>> 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.

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.

28

Hmm. I guess shift/unshift are like that too. Sorry for the noise.

I'm surprised, though, that this thread has received so much
attention. I don't really have a problem with the terminology, or the
behavior of the methods pop/push/shift/unshift. In fact, the
shift/unshift methods were two of many things that attracted me to
Ruby. I know they exist in other languages, but I haven't experienced
the others in depth yet.

Todd

···

On 10/24/07, Todd Benson <caduceass@gmail.com> wrote:

Not only that, but enqueue and dequeue return different objects.
Enqueue returns an array, and dequeue returns the object that was
shifted from the stack.

Todd

29

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.

Could this lead to a security problem down the road?

I don't think so in the cases I mentioned. The objects in front of the array are not accessible using Ruby. I suppose you could write some C code easily enough to get at them.

Cheers,
Bob

···

On 24-Oct-07, at 5:03 AM, Thufir wrote:

On Tue, 23 Oct 2007 23:32:01 +0900, Bob Hutchison wrote:

-Thufir

----
Bob Hutchison -- 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/

30

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.

Cheers,
Bob

···

On 23-Oct-07, at 10:37 AM, David A. Black wrote:

On Tue, 23 Oct 2007, Jes˙s Gabriel y Gal·n wrote:

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

Now you're talking :slight_smile: 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

----
Bob Hutchison -- 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/

31

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?

unshift/pop seems to me to be a possibility. I think it'll have to be tested though. One can easily imagine that ruby does not release allocated space in an array, as an optimisation. If this is the case then the queue will continue to grow unbound but after the end of the array instead before the start.

Maybe a linked list?

Cheers,
Bob

···

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

Thanks,

Jesus.

----
Bob Hutchison -- 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/

32

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.

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?

I just did a quick test. It looks as though Ruby is now handling both the unshift/pop and push/shift properly. I know when I reported it in Ruby 1.8.4 there was a discussion about how to deal with this, and it looks as though 1.8.5 has it working (or I've patched my version of Ruby and have forgotten about it).

So maybe not a problem, or too big of a problem. Just don't forget about the cells holding references, that is definitely there in 1.8.5.

Cheers,
Bob

···

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

On 10/23/07, Bob Hutchison <hutch@recursive.ca> wrote:

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

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

Thanks,

Jesus.

----
Bob Hutchison -- 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/

33

Well, I answered to this thread not because I had any problem with the
terminology, but to comment on the fact that pop/push is stack
semantics, and I would like also queue semantics. After thinking about
what David and I were discussing about how to make this happen, I'm
settled on the following if I ever want queue/stack semantics :

class Queue
   def initialize
      @buffer =
   end

   def enqueue(element)
      @buffer.unshift(element)
   end

   def dequeue
      @buffer.pop
   end

   def empty?
      @buffer.empty?
   end
end

But, there's already a Queue implementation in ruby core, so I would
use that, although that class is aimed at synchronizing threads so I
might implement a simple queue like the above at some point if I need
simple queue semantics.
I would corresponding class for Stack, with push/pop being delegated
to array's push and pop :-). Or just use an array if the fact of
having more methods than a stack is not a problem :-).

Jesus.

···

On 10/24/07, Todd Benson <caduceass@gmail.com> wrote:

On 10/24/07, Todd Benson <caduceass@gmail.com> wrote:
I'm surprised, though, that this thread has received so much
attention. I don't really have a problem with the terminology, or the
behavior of the methods pop/push/shift/unshift. In fact, the
shift/unshift methods were two of many things that attracted me to
Ruby. I know they exist in other languages, but I haven't experienced
the others in depth yet.

34

Not only that, but enqueue and dequeue return different objects.
Enqueue returns an array, and dequeue returns the object that was
shifted from the stack.

Todd

Hmm. I guess shift/unshift are like that too. Sorry for the noise.

I'm surprised, though, that this thread has received so much
attention. I don't really have a problem with the terminology, or the
behavior of the methods pop/push/shift/unshift. In fact, the
shift/unshift methods were two of many things that attracted me to
Ruby. I know they exist in other languages, but I haven't experienced
the others in depth yet.

I agree with you. I don't have any problem with the terminology, and I certainly appreciate the implementation. The only problem I have is the two specific deficiencies in the optimisation of un/shift. With some release after 1.8.5 this should be completely resolved, it is much better in 1.8.5 than in 1.8.4 I think.

Cheers,
Bob

···

On 24-Oct-07, at 6:30 AM, Todd Benson wrote:

On 10/24/07, Todd Benson <caduceass@gmail.com> wrote:

Todd

----
Bob Hutchison -- 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/

35

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)

:slight_smile:

Jesus.

···

On 10/23/07, Bob Hutchison <hutch@recursive.ca> wrote:

On 23-Oct-07, at 10:37 AM, David A. Black wrote:
> On Tue, 23 Oct 2007, Jes¨Bs Gabriel y Gal¡¤n wrote:
>
>> 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
>
> Now you're talking :slight_smile: 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
>
>

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.

36

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?

I just did a quick test. It looks as though Ruby is now handling both the unshift/pop and push/shift properly. I know when I reported it in Ruby 1.8.4 there was a discussion about how to deal with this, and it looks as though 1.8.5 has it working (or I've patched my version of Ruby and have forgotten about it).

So maybe not a problem, or too big of a problem. Just don't forget about the cells holding references, that is definitely there in 1.8.5.

I just wrote a little test script. It looks as though push will cleanup the empty space left by shift. So your queue should be okay on *average* either way you implement it. Though you'll be growing the array until push is called (and at the same time there will be invisible references to objects)... generally working but with potentially subtle bugginess.

Cheers,
Bob

···

On 23-Oct-07, at 11:17 AM, Bob Hutchison wrote:

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

Cheers,
Bob

Thanks,

Jesus.

----
Bob Hutchison -- 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/

----
Bob Hutchison -- 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/

37

You want to -- as mentioned elsewhere in this thread -- push it in the
front and take it out the back. Interesting. I guess it all comes
down to what direction you want to go. I like to see the procession
moving towards the zeroth position and not to some indexth position.

If I was going to queue, it would be more like...

class Queue
  def initialize enum
    @list = enum if enum.is_a? Enumerable
  end
  def enqueue object
    @list << object
#haven't looked at C code, but
#I think this is the same as #push
  end
  def dequeue
    @list.shift
  end
  def cut_in_line object
    @list.unshift object
  end
  def bouncer_removes_last_guy
    @list.pop
  end

end

Todd

···

On 10/24/07, Jesús Gabriel y Galán <jgabrielygalan@gmail.com> wrote:

class Queue
   def initialize
      @buffer =
   end

   def enqueue(element)
      @buffer.unshift(element)
   end

   def dequeue
      @buffer.pop
   end

   def empty?
      @buffer.empty?
   end
end

But, there's already a Queue implementation in ruby core, so I would
use that, although that class is aimed at synchronizing threads so I
might implement a simple queue like the above at some point if I need
simple queue semantics.
I would corresponding class for Stack, with push/pop being delegated
to array's push and pop :-). Or just use an array if the fact of
having more methods than a stack is not a problem :-).

Jesus.

38

Thanks, it's good to know.

Kind regards,

Jesus.

···

On 10/23/07, Bob Hutchison <hutch@recursive.ca> wrote:

I just wrote a little test script. It looks as though push will
cleanup the empty space left by shift. So your queue should be okay
on *average* either way you implement it. Though you'll be growing
the array until push is called (and at the same time there will be
invisible references to objects)... generally working but with
potentially subtle bugginess.

39

Save yourself some grief, do it this way:

def dequeue
   tmp = @list[0]
   @list[0] = nil
   @list.shift
   tmp
end

Cheers,
Bob

···

On 24-Oct-07, at 9:03 AM, Todd Benson wrote:

  def dequeue
    @list.shift
  end

----
Bob Hutchison -- 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/

40

The truth is that I don't mind in which direction to go, because I
only want queue semantics, and that would be part of an implementation
detail. I changed in my example to unshift/pop because of the
recommendations made above in this thread about not using shift, but
other than that I wouldn't mind.

Jesus.

···

On 10/24/07, Todd Benson <caduceass@gmail.com> wrote:

On 10/24/07, Jesús Gabriel y Galán <jgabrielygalan@gmail.com> wrote:
> class Queue
> def initialize
> @buffer =
> end
>
> def enqueue(element)
> @buffer.unshift(element)
> end
>
> def dequeue
> @buffer.pop
> end
>
> def empty?
> @buffer.empty?
> end
> end
>
> But, there's already a Queue implementation in ruby core, so I would
> use that, although that class is aimed at synchronizing threads so I
> might implement a simple queue like the above at some point if I need
> simple queue semantics.
> I would corresponding class for Stack, with push/pop being delegated
> to array's push and pop :-). Or just use an array if the fact of
> having more methods than a stack is not a problem :-).
>
> Jesus.

You want to -- as mentioned elsewhere in this thread -- push it in the
front and take it out the back. Interesting. I guess it all comes
down to what direction you want to go. I like to see the procession
moving towards the zeroth position and not to some indexth position.