stack-based.mdwn (1896B)
1 **Stack machines** are arguably the simplest kind of computer architecture. Their LIFO structure is quite suitable for block-oriented languages. The code size for a stack machine can be very compact because most instructions have no operand field. 2 3 [[Forth]] (from around 1970) is perhaps the most succesful stack-based programming language, based on a machine model consisting of a data stack and a return stack. Stack-oriented languages are a large subset of concatenative programming language (with the Om language being a rare example of a non-stack-oriented concatenative programming language). 4 5 Many [[virtual machine]]s used as compilation targets of higher-level programming languages ([[Java]], [[Lua]], etc.) are stack-based. 6 7 History 8 ------- 9 10 Reverse Polish notation was separately invented since the 1950s by several matematicians and computer scientists. GEORGE (1957) was the first practical programming language based on RPN. 11 12 Stack-based instruction sets were used by many mainframe computers of the early 1960s (notably, the Burroughs B5000 and the English Electric KDF9), but the idea was later marginalized by register-based architectures such as the IBM S/360. Still, some later stack-based computers (such as [[Niklaus Wirth]]'s Lilith) proved to be quite competitive in terms of speed, particularly thanks to the high code density that reduced their need for memory bandwidth. 13 14 Example 15 ------- 16 17 Primitives: 18 19 * POP Remove an item at index, closing the hole left in the stack. 20 * ROLL Remove an item at index, push it on top of the stack. 21 * PICK Copy an item at index, push it on top of the stack. 22 23 From these primitives, the basic stack operations can be created: 24 25 * DROP(a b) Discard top item. 26 * NIP(a c) Discard second item. 27 * SWAP(a c b) Bring second item to top. 28 * ROT(b c a) Bring third item to top. 29 * DUP(a b c c) Copy top item. 30 * OVER(a b c b) Copy second item to top.