Talk:Stack Machine

Proposed merger

I have tagged this article to merge with pushdown automaton. The two are formally the same. I am creating a similar article called queue machine which would list both theoretical and practical concerns, as I believe that is the main difference between the two articles. SamuelRiv 03:33, 6 November 2007 (UTC)

Make sure you also state the word Stack Machine somewhere. When you know as little as I do, you don't expect to find stack machines at pushdown automation. :)

Merging is probably -not- a good idea. A Stack Machine is a computer architecture in which almost all instructions operate implicitly on values at the top of a stack (a high-level view). A Pushdown automaton is a -State Machine- (not Stack Machine) in which the transition from one state to another may depend on one or multiple values on a stack, which may be modified by the state transition (a low-level view). There should perhaps be a link, and an explanation about their relation, but no more than that. To a theorist, these are the same, but to anyone else, one is a class of implemented CPUs (F21, 387, etc.), while the other is pure computer theory.

I don't think the merge is appropriate. I wouldn't have expected to find stack machines in the pushdown automation article (as one commenter mentioned), and as the second commenter mentioned, pushdown automation is the theory, and stack machines are the implementation. —Preceding unsigned comment added by Gracana (talk • contribs) 01:33, 4 July 2008 (UTC)

I agree it would be a mistake. One of the standard textbooks I saw on formal language theory, I believe Hopcroft and Ullman 1969, defines stack automata as different from pushdown automata, and more powerful. Formal language theory also defines two-stack machines, which are a trivial variant of Turing machines. The present article seems to be about the use of stacks in general and hence would cover all such automata. Rp (talk) 15:20, 9 July 2008 (UTC)

The two are usually considered different since an finite state automata augmented with two stacks (or one stack and a register, ram, etc.) is equivelent to a Turing Machine and thus in a different class of computational power from a finite state automata augmented with only a single stack. If you include multi-stack autmata in pushdown automata, then many theorems no longer apply. For instance, Pumping lemma for context-free languages would no longer apply to all languages accepted by all pushdown automata.

The equivalence to a turing machine can be seen if you think about the two stacks as being the tape of the turing machine. In order to move left, a value is popped off the left-stack and pushed onto the right stack and likewise to move right. Writing to the tape accomplished by popping a value off one stack and pushing a different value onto the same stack. Finding references for this is trivial (Kozen's purple book and The Dragon Book come to mind) but I'm away from my bookshelf for the week. This weekend I'll clean up the entries to make the distinction clear and put some references to it after I return. I've personally can't recall ever having heard the term Queue Machine, though that doesn't mean the term is invalid. It just means that I hope to see some good references on your page. Perhaps that is the proper term for a fsm augmented with more than one stack. Nutmegmagi (talk) 20:43, 24 December 2008 (UTC)

I agree they should not be mixed. The origional stack machines were designed and promoted as ALGOL machines. At that time there were engineering and data processing computers. Engineering computers were register machines. Data processing were memory to memory. The IBM 70xx were the mathematical orianted engineering machines. Data processing were memory memory to memory. There was no hardware stack on these early machines.

Having first learned programming in the late 1960 I studied these different architectures.

I think we should organize this into interlinked topics.

In fact can we not have the wikipedia software provide a feature that provides a list of articles linking to a subject. A list that could placed on the talk page.

It is obvious that this article falls short on the details of actual hardware imementation.

One thing not said is that because stack machines are designed for function orianted programming their direct local variable addressing were short not needing to address all of memory.