Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Why are "push", "pop", "shift" and "unshift" so named?

by Cody Pendant (Prior)
on May 02, 2007 at 02:56 UTC ( #613124=perlquestion: print w/replies, xml ) Need Help??
Cody Pendant has asked for the wisdom of the Perl Monks concerning the following question:

I've always wondered this.

Just about every tutorial on this topic talks about spring-loaded cafeteria trays. There are three main things wrong with this analogy:

  • I have never eaten in a cafeteria with spring-loaded trays
  • You might just conceivably "push" some new trays onto the top, so that term sort of fits the mental picture, but you don't "shift", "unshift" or "pop" cafeteria trays
  • The tray stack can only be added to from the top, whereas perl functions allow us to add at either end.

So, how did they get those names?

I'm not sure what I would have called them, if Perl were just invented and Larry asked me to assign them names -- "append" and "prepend" maybe, are the best English equivalents for push and unshift? But the others don't really have obvious analogues.



($_='kkvvttuu bbooppuuiiffss qqffssmm iibbddllffss')
=~y~b-v~a-z~s; print
  • Comment on Why are "push", "pop", "shift" and "unshift" so named?

Replies are listed 'Best First'.
Re: Why are "push", "pop", "shift" and "unshift" so named?
by Moron (Curate) on May 02, 2007 at 05:48 UTC
    I think it's earlier than some people think. PUSH and POP are assembler (2GL) (stack) instructions dating back to the early 1950's but these are just tokens for actual hardware instructions (1GL). Shell argument shifting (from which Perl derives its shift) may be 1970's in origin, but that in turn is an analogy on bit shifting which goes back at least twenty years before that. i.e. all three are really 55+ years old. As for the cafeteria tray, although cafeteria the term came to English via American Spanish in the 19th Century, the electronic computer was invented in England in the 1940s. At that time anybody involved in the early computing wouldn't be eating in a "cafeteria" (though at the time, certainly in a mess), so it isn't likely that the term "stack" and its operators could have been inspired by cafeteria trays, though it could very possibly come from a spring-loaded plate stacking device which did exist in messes in the 1940s.

    Update; The first ever software programmable* electronic computer, built in 1943, in North London was Colossus which, in addition to being intended to support stacks, included also the first implementation of the shift register.

    (*The Bell Labs (1930) and ABC (1937) predecessors were not software programmable. The ABC inventors abandoned it (at Iowa State University) in 1939 to join in on the joint British-American wartime efforts - a chain of developments eventually leading to the crucial Colossus Mk. II. - a serious turning point in WWII intelligence history)

    More update: On the other side, the German's had an electro-mechanical programmable computer (Z3) since 1941, based on von Neumann's theories but a request to fund an electronic successor was rejected as being "strategically unimportant" - hmmm I suppose technically they were right, given that the work of Colossus, which clearly remained secret, was of immediate tactical importance rather than strategic ;)

    More more update: not to be confused with Enigma, which was decoded electromechanically, the decoding of "Geheimschreiber" by Colossus effectively blew the cover off high-ranking German military communications giving allied forces a free ride, bringing the war to a swift end. Colossus remained protected in Britain under the Official Secrets Act until the early 1970's, 25 years after IBM had got their hands on it from the CIA. This piece of crass bureaucracy cost the British economy an estimated $1x10E14 in lost opportunity over the years - erm can we have our money back please Mr. Blair?

    __________________________________________________________________________________

    ^M Free your mind!

Re: Why are "push", "pop", "shift" and "unshift" so named?
by davido (Cardinal) on May 02, 2007 at 03:14 UTC

    I always thought that push and pop applied to a "cafeteria plates" metaphor, not trays. ;) Wikipedia seems to support this assertion.

    As the wikipedia article states, the cafeteria plates metaphor works because it conveys the notion of LIFO, as well as the notion that all but the top-most item are hidden from view in a traditional stack implementation as they are in a stack of cafeteria plates.

    If you don't like the plates metaphor; how about those vending machines with spiral dispenser? The last item loaded is the first one to pop off as the spiral turns to dispense the item. Or how about facial tissue; the top one is always the one that pops out next as you pull on it. Of course for that metaphor to really work you would have to assure that the box of tissue was loaded from the top. ;)

    Shift and unshift are perhaps a little more difficult. Since they occur at the zero end of a queue, the notion is that the entire queue has to shuffle up one for someone else to be placed in the zero position. And when one is taken from the zero position, everyone shifts down one spot. Think of a line of people. If the person at the front of the line passes through the threshold everyone else has to shift forward so that someone else can wait at the front of the line.


    Dave

      Maybe I've just eaten in too many caffeterias in my life (I was a military brat, so that's quite possible), but from what I remember of caffeterias, some of them had the spring-loaded stacks for trays, not the plates.

      IF you're not in a self-service buffet, but an old style caffeteria -- you'd collect the tray and utensils yourself, but as you went down the line, you'd request specific items from the caffeteria workers. They'd put it on a plate, and hand you the plate of food. So the general public only saw the use of stacks on the trays, not necessarily the plates.

      These days, it's much rarer for the general public to see a caffeteria, and when you do, they've typically forgone the spring-loaded stack in exchange just a pile of trays. We do occassionally see stacks in use at self-service buffets. (some hotel restaurants, all-you-can-eat type places, etc), but it's more common in older establishments. Newer places just have a few piles of plates rather than the elegant spring-loaded stacks).

      ...

      So, anyway ... I'd hardly qualify wikipedia as authoritative in these sorts of things ... and the spring-loadedness, or even what is in the stack is less important than the fact that you can only easily get to the items in the reverse order they were placed on the stack.

      update: bah ... immediately after posting this, I realized that the spring-loadedness is necessary so that 'push' and 'pop' make sense in a polysemous way -- I still don't think _what_ is in the stack is necessarily significant.

      update2: I was in an IHOP yesterday, and saw a spring loaded stack, but it was for bowls. (so neither plates or trays)

        It's true that you don't see the spring-loaded tray or plate stacks as much, but it's an analogy that has stuck with us. We have a similar situation with "radio buttons" in graphical interfaces. The name is losing its meaning relative to actual radios over time, but the name is still here in a particular input type.

        As far as the contents of the stack: all analogies break down sooner or later. The stack of plates is just a starting point. This is Perl, so that stack could contain plates, trays, scalars, turkeys, or small cars.

Re: Why are "push", "pop", "shift" and "unshift" so named?
by GrandFather (Sage) on May 02, 2007 at 03:15 UTC

    The "cafeteria with spring-loaded trays" model is exactly right for stacks (LIFOs - Last in, First out) which are what push and pop apply to. And yes, you absolutely would both push and "pop" trays - push to add em in the first place,and pop to get one to use.

    Perl extends the concept to include access to the "bottom" of the "stack" which allows a few more operational models. In particular the combination of push and shift (or unshift and pop) provide a queue (FIFO - First in, First out). Shift parallels an operation common in handling arguments in some OS batch/scripting languages. Unshift is a neat complement to shift for "putting back" an argument after taking a peek at it. At times there is an advantage to using a queue where you can add and remove elements to/from either end - can't think of an example right now in the software world, but it often happens in supermarket checkout queues!

    Nomenclature adjusted for northern hemisphere usage. In the southern hemisphere stacks are the other way up. Queues can be either way and may be affected by the Coriolis effect.


    DWIM is Perl's answer to Gödel
      Nomenclature adjusted for northern hemisphere usage.

      For sure. I mean... if the world were flat, all the Australians would fall off!

Re: Why are "push", "pop", "shift" and "unshift" so named?
by jbert (Priest) on May 02, 2007 at 05:14 UTC
    Only 'push' and 'pop' come from the stack terminology. You 'pop' plates off the top (the rest of the plates 'pop' up when you do it I guess).

    I would say 'shift' comes from shell scripting, where you 'shift' the arguments off of the list passed to the script. This is a fairly natural usage, and might also derive from assembly language, where a basic operation is to shift all the bits in a register one place left or right.

    'unshift' is probably originates with perl and would have been named by analogy with 'shift' I think.

      push and pop come from stack terminology, while shift comes from queues (to be combined with push).

      unshift is, like somebody else said, just the opposite of shift, like unget is the opposite of get. Not exactly proper English, but clear enough for the insiders — us.

      But technically, there's no reason why the array ends could not have been swapped. You get a just as fine stack if you just use unshift/shift as primitives instead of the usual push/pop, and, for queues, unshift/pop, instead of push/shift.

Re: Why are "push", "pop", "shift" and "unshift" so named?
by fenLisesi (Priest) on May 02, 2007 at 03:02 UTC
    They are probably so named with respect to existing computing literature. I think the names are pretty clear. For me, the only possibly interesting bit there is "unshift", which is a good name, too, assuming you know "shift". Cheers.
Re: Why are "push", "pop", "shift" and "unshift" so named?
by talexb (Canon) on May 02, 2007 at 11:29 UTC

    Since no one's mentioned the Pez dispenser here, I will. It's a toy that lets you 'push' candies into a stack, and then 'pop' them out.

    Amd, as has already been mentioned, 'shift' comes from the assembler operation of the same name, and 'unshift' follows from that.

    Alex / talexb / Toronto

    "Groklaw is the open-source mentality applied to legal research" ~ Linus Torvalds

      I just got an awful image in my head: a Larry Wall pez dispenser.
Re: Why are "push", "pop", "shift" and "unshift" so named?
by jkva (Chaplain) on May 02, 2007 at 03:19 UTC
    I recall teaching myself ASM with an old 8080/8086 ASM book, and it also had the same analogy, so I guess it goes way back.
Re: Why are "push", "pop", "shift" and "unshift" so named?
by ambrus (Abbot) on May 02, 2007 at 10:06 UTC

    Shift is from the builtin command of same name in unix shells. It shifted a command-line argument from the beginning, so that if you used it in a loop, you could loop through command-line arguments in normal order. Even the DOS command.com has copied that command with the same name.

    Update: I see jbert has already said this in his reply.

Re: Why are "push", "pop", "shift" and "unshift" so named?
by scorpio17 (Canon) on May 02, 2007 at 11:13 UTC
    I think "shift" comes from digital electronics, i.e., the 'shift register'. In textbooks, these are drawn as a group of little boxes, 1 box per bit, and data is shifted in from left to right (low order bit first). I've never seen the term "unshift" outside of perl, but I think it's a good term for "the opposite of shift".
Re: Why are "push", "pop", "shift" and "unshift" so named?
by herby1620 (Monk) on May 02, 2007 at 16:13 UTC
    While it seems that "push" and "pop" are already in the dictionary of computer terms, my preference is to use "push" and "pull". One computer I worked on had these terms and it was easy to understand (besides they were both 4 letter words). The current terms appear to have been popularized from pdp-10 (-6) usage, as that is how DEC documented them. The "dish stack" in a cafeteria that was spring loaded, usually had two stacks of dishes (the device was about 12 inches by 24 inches and had rollers). In addition the stacker could have been plugged in to heat the plates to a reasonable (non-burning) temperature (why they had two stacks). Nowdays some pharmacy's have spring loaded displays for box packaged things. Unfortunately these don't rotate the stock too well, so if the stock becomes close to depleted, you might get stale product. The whole analogy is to appear to have only ONE item visible to the "consumer".

    Stacks as implemented in computer hardware work in various ways. I've seen them grow by increasing addresses, and by decreasing addresses (big-endian/little-endian). Since they rarely diverge from the host hardware, it makes little difference. As far as things go, devices like "stacks", "queues", and "lists" are pretty general, and typically the subject of a first course in programming. What to call the "operators" on these devices is what one might call a "local option". They do vary, but there are a few common names.

Use shaft for shift
by mattr (Curate) on May 02, 2007 at 18:26 UTC
    Push onto a stack, pop off the top of the stack.

    I think pop was an assembly language instruction in 6502 and someone else said earlier it seems. Data is stored on the stack and you pop the last one off the top.

    Shift/unshift I admit has always been confusing to me if I think about it long enough, since I mix it up with binary powers (i.e. the "shift" operator << in perl). There is an assembler command to bitwise shift everything one digit up, etc.. The only useful thing I can say is that you get the first argument provided by the user from the command line with shift, you are shifting it off the ARGV array. In a subroutine you can get the first argument off the @_ with which it got called with shift. Basically if you think of shift as shifting something off the bottom then unshift is the (confusing) reverse.

    I miss peek() which looked at a memory location without touching it and poke() which touched the location, i.e. to drive the speaker (in the reverse direction I discovered)

    However you are entirely right. You cannot "shift" trays off the bottom of a stack easily, they are going to be held down by the weight of the trays on top. Maybe think of shift as "shaft". You are going to take a long steel pole and thrust it at the bottom-most tray to shoot it out from the bottom of the stack. It gets shafted! (beat up / betrayed / knocked out / messed with) Let's use this one without telling anybody.. :)

    Actually this is eminently useful. Unshafting is then making something not shafted, i.e. making things clean and proper. Which would obviously mean picking the knocked out tray off the floor and wedging it carefully back in under the bottom of the stack of trays. At least I can convince myself about it.
Re: Why are "push", "pop", "shift" and "unshift" so named?
by appleb (Novice) on May 03, 2007 at 18:47 UTC
    You started me on an interesting trail of discovery, and I can share a little of it with you.

    I dug out an article by Frederick L Bauer who invented the stack, and even tried to read his original paper, written in 1950. He talked there about 'pushdown' data storage and it was known as the Kellerprinzip or cellar principle. So I reckon that's where 'push' comes from.

    I was not surprised to find that Bauer's work was based on original papers by a certain Alan Turing, written in 1934. He is most famous for his work with breaking the Enigma code in the second world war. But go look him up in your resource of choice, and you will find his ideas in many other areas, including AI and neural networks.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://613124]
Approved by Corion
Front-paged by Old_Gray_Bear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (3)
As of 2018-12-14 02:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    How many stories does it take before you've heard them all?







    Results (63 votes). Check out past polls.

    Notices?