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)[reply]

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)[reply]

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)[reply]