Stack-oriented programming language

From Wikipedia, the free encyclopedia

A stack-oriented programming language is one that relies on a stack machine model for passing parameters. Several programming languages fit this description, notably Forth and PostScript, and also many Assembly languages (but on a much lower level).

Stack oriented programming languages operate upon one or more stacks, each of which may serve different purposes. Because of this, programming constructs in other programming languages may need to be modified for use in a stack-oriented programming language. Adding to this, some stack-oriented programming languages operate in Reverse Polish or postfix notation - that is, the arguments or parameters for some command are stated before the actual command itself. For example, in RPN, one would say "2, 3, multiply" instead of "multiply, 2, 3" (prefix or Polish notation) or "2 multiply 3" (infix notation).

Contents

[edit] Operations of the stack

Assume we have a postfix stack based programming language. PostScript is one such real language. To understand how a stack-oriented programming language works, in calculating an expression such as 2 3 mul, we can use a simple thought experiment.

Say you are standing at the end of a conveyor belt (the input), onto which someone has placed (in sequence) plates marked 2, 3, and mul. You can take the plate at the end of the conveyor (2), but you can't see or take further plates from the conveyor until you do something with the plate you've just taken. The only way you can store plates is in a stack, and you can only add or remove a plate on top of the stack, not in the middle. You also have a supply of blank plates (and a marker), and you can discard plates (but this is permanent). Can you perform the calculation?

Yes, you take plate 2 and put it on the stack, then take plate 3 and put it on the stack. Next, you take the mul plate. This is an instruction to you. You will take the top two plates off the stack, multiply their labels (2 and 3), and write the result (6) on a new plate. The two old plates (2 and 3) and the mul plate are then discarded, and the new plate gets put on the stack. With no more plates remaining on the conveyor, the result of the calculation (6) is shown on the plate at the top of the stack.

This is of course a very simple calculation. What if we wanted to calculate something like (2 + 3) × 11 + 1 ? If we first write it into postfix form, that is, 2 3 add 11 mul 1 add, we can perform the calculation 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 3 add 11 mul 1 add
Stack 2 3
2		 5 11
5		 55 1
55		 56

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

We can conclude from this the following: a stack based programming language has only one way of handling data, by taking one piece of data from the top of the stack, known as popping, and putting data back on the top of the stack, known as 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 be interpreted by a stack-oriented programming language.

[edit] Stack manipulation

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

[edit] Stack effect diagrams

As an aid to understanding the effect of 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.

( before -- after )

For example, the basic Forth stack operators are described:

dup  ( a -- a a )
drop ( a -- )
swap ( a b -- b a )
over ( a b -- a b a )
rot  ( a b c -- b c a )

And the fib function below is described:

fib  ( n -- fib )

[edit] PostScript stacks

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

[edit] Variables and dictionaries

We have examined how we can evaluate differing expressions. The implementation of variables is important for any programming language, but for stack-oriented languages it is of special concern, as we only have one way of interacting with data.

The way variables are implemented in stack-oriented programming languages such as PostScript usually involves a separate, specialized stack which holds dictionaries, which hold key-value pairs. To create a variable, we create a key (the variable name), to which we associate a value. In PostScript, a name data object is prefixed with a "/", so "/x" is a name data object which we can associate, for example, with the number "42". The "define" command is def, so

/x 42 def

associates with the name "x" with the number 42 in the dictionary on the top of the stack. Note that there is a difference between "/x" and "x" - the former is a data object representing a name, "x" itself stands for what is defined under "/x".

[edit] Procedures

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, we can define names with procedures, and when they are retrieved, they are executed directly.

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

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

[edit] Anatomy of some typical procedures

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

Let us examine a Fibonacci number program in PostScript:

 /fib
 {
    dup dup 1 eq exch 0 eq or not
    {
       dup 1 sub fib
       exch 2 sub fib
       add
    } if
 } def

We use a recursive definition, and do so on the stack. The Fibonacci number function takes one argument. We first test whether it is 1 or 0.

Let us decompose each of the program's key steps, reflecting the stack. Assume we calculate F(4).

                stack: 4
   dup 
                stack: 4 4
   dup 
                stack: 4 4 4
   1 eq 
                stack: false 4 4
   exch 
                stack: 4 false 4
   0 eq
                stack: false false 4 
   or
                stack: false 4
   not
                stack: true 4

Since the expression evaluates to true, the inner procedure is evaluated.

                stack: 4
   dup 
                stack: 4 4
   1 sub
                stack: 3 4
   fib
(we recurse here)
                stack: F(3) 4
   exch 
                stack: 4 F(3)
   2 sub 
                stack: 2 F(3)
   fib
(we recurse here)
                stack: F(2) F(3)
   add
                stack: F(2)+F(3)

which is the result we wanted.

This procedure does not use named variables, purely the stack. We can create named variables by using the

/a exch def

construct. For example,

{/n exch def n n mul}

is a square procedure with a named variable n. Assume that

/sq {/n exch def n n mul} def

and

3 sq

is called. Let us analyse this procedure.

               stack: 3 /n 
   exch 
               stack: /n 3
   def 
               stack: empty (it has been defined)
   n 
               stack: 3
   n 
               stack: 3 3 
   mul
               stack: 9

which is the result we wanted.

[edit] Control and flow

Since we have anonymous procedures, flow control can arise naturally. We need three pieces of data for an if-then-else statement, a condition, a procedure to be done if true, and one to be done if false. In PostScript for example,

2 3 gt { (2 is greater than three) = } { (2 is not greater than three) = } ifelse

performs the near equivalent in C:

if(2 >= 3) { printf("2 is greater than three\n"); } else { printf("2 is not greater than three\n"); }

Looping and other constructs are similar.

[edit] Analysis of the language model

The simple model provided in a stack-oriented programming language allows expressions and programs to be interpreted simply and theoretically evaluated much more quickly, since no syntax analysis needs to be done, only lexical analysis. The way programs are written lends itself well to be interpreted by machines, which is why PostScript suits printers well for its use. However, the slightly artificial way of writing PostScript programs can result in an initial barrier to understanding the PostScript language and other stack-oriented programming languages.

Whilst the capability of shadowing by overriding inbuilt and other definitions can make things difficult to debug - and irresponsible usage of this feature can result in unpredictable behaviour - it can make certain functionality much simpler. For example, in PostScript usage, 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 to repeat code to generate the style.

[edit] See also

Languages