Stack-oriented programming

2 3 multiply instead of multiply 2 3</code>"}},"i":0}}]}'>multiply 2 3 (prefix or Polish notation), or 2 multiply 3</code>"}},"i":0}}]}'>2 multiply 3 (infix notation). The programming languages Forth, Factor, RPL, PostScript, BibTeX style design language and many assembly languages fit this paradigm.

Stack-based algorithms manipulate data by popping data from and pushing data to the stack. Operators govern how the stack manipulates data. To emphasize the effect of a statement, a comment is often used showing the top of the stack before and after the statement; this is known as the stack effect diagram. Some stack-oriented languages may use multiple stacks for different purposes; for example, PostScript uses separate stacks for variables, dictionaries, procedures, some typical procedures, and control flow statements. Analysis of the language model allows expressions and programs to be interpreted simply.

(2 + 3) × 11 + 1? If it is first written in postfix form, that is, 2 3 add 11 mul 1 add</code>"}},"i":0}}]}'>2 3 add 11 mul 1 add, the calculation can be performed in exactly the same manner and achieve the correct result. The steps of the calculation are shown in the table below. Each column shows an input element (the plate at the end of the conveyor), and the contents of the stack after processing that input.

Input	2	11	add
Stack	5	5"}},"i":0}}]}'/>11 5	56

After processing all the input, the stack contains 56, which is the answer.

From this, the following can be concluded: a stack-based programming language has only one way to handle data, by taking one piece of data from atop the stack, termed popping, and putting data back atop the stack, termed pushing. Any expression that can be written conventionally, or in another programming language, can be written in postfix (or prefix) form and thus be amenable to being interpreted by a stack-oriented language.

Since the stack is the key means to manipulate data in a stack-oriented language, such languages often provide some sort of stack manipulation operators. Commonly provided are dup, to duplicate the element atop the stack, exch (or swap), to exchange elements atop the stack (the first becomes second and the second becomes first), roll, to cyclically permute elements in the stack or on part of the stack, pop (or drop), to discard the element atop the stack (push is implicit), and others. These become key in studying procedures.

As an aid to understanding the effect of the statement, a short comment is used showing the top of the stack before and after the statement. The top of the stack is rightmost if there are multiple items. This notation is commonly used in the Forth language, where comments are enclosed in parentheses.

It is equivalent to preconditions and postconditions in Hoare logic. Both comments may also be referenced as assertions, though not necessarily in the context of Stack-based languages.

PostScript and some other stack languages have other separate stacks for other purposes.

The evaluation of different expressions has already been analysed. The implementation of variables is important for any programming language, but for stack-oriented languages, it is of special concern, as there is only one way to interact with data.

The way variables are implemented in stack-oriented languages such as PostScript usually involves a separate, specialized stack which holds dictionaries of key-value pairs. To create a variable, a key (the variable name) must be created first, with which a value is then associated. In PostScript, a name data object is prefixed with a /, so /x is a name data object which can be associated with, for example, the number 42. The define command is def, so

/x 42 def

associates with the name x with the number 42 in the dictionary atop the stack. A difference exists between /x and x – the former is a data object representing a name, and x stands for what is defined under /x.

A procedure in a stack-based programming language is treated as a data object in its own right. In PostScript, procedures are denoted between { and }.

For example, in PostScript syntax,

{ dup mul }

represents an anonymous procedure to duplicate what is on the top of the stack and then multiply the result – a squaring procedure.

Since procedures are treated as simple data objects, names with procedures can be defined. When they are retrieved, they are executed directly.

Dictionaries provide a means of controlling scoping, as well as storing definitions.

Since data objects are stored in the top-most dictionary, an unexpected ability arises naturally: when looking up a definition from a dictionary, the topmost dictionary is checked, then the next, and so on. If a procedure is defined that has the same name as another already defined in a different dictionary, the local one will be called.

Procedures often take arguments. They are handled by the procedure in a very specific way, different from that of other programming languages.

To examine a Fibonacci number program in PostScript:

Looping and other constructs are similar.

The simple model provided in a stack-oriented language allows expressions and programs to be interpreted simply and theoretically evaluated much faster, since no syntax analysis needs to be done but lexical analysis. The way such programs are written facilitates being interpreted by machines, which is why PostScript suits printers well for its use. However, the slightly artificial way of writing PostScript programs can form an initial barrier to understanding stack-oriented languages such as PostScript.

While the ability to shadow by overriding inbuilt and other definitions can make programs hard to debug, and irresponsible use of this feature can cause unpredictable behaviour, it can simplify some functions greatly. For example, in PostScript use, the showpage operator can be overridden with a custom one that applies a certain style to the page, instead of having to define a custom operator or repeat code to generate the style.

• List of stack-based programming languages
• Reverse Polish notation
• Return-oriented programming

---

View original on Wikipedia | Back | FazBrowse Home