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).

A stack oriented programming language behaves by operations upon one or many stacks, 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 such an expression as "2 3 multiply", we can use a simple thought experiment.

Say you are standing at the start of a line and along the line someone has placed "2", "3", and "multiply" along it. The problem is, you can only see the first thing in front of you in the line, the 2, and nothing else. You are only allowed to perform any calculation, take what you can see off the line (the first thing), and put something back on the line in front of you. Can you perform the calculation?

Yes you can, you take the 2 off the line, then the 3, then the command to multiply, in which you multiply what you have, 2 and 3, and then put the result, 6, back on the line.

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 multiply 1 add

we can perform the calculation in exactly the same manner and achieve exactly the same result. After each operation, one puts the result of that operation back on the line (the stack), and continues as before. The stack would then be transformed as follows

5 11 multiply 1 add
55 1 add
56

which is the result.

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. Forth variables and procedures reside in a global dictionary, and Forth control flow is handled by data stack processing at compile-time vs. execution time.

[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 to that of other programming languages.

Let us examine the 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"); }

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

Retrieved from "http://en.wikipedia.org../../../s/t/a/Stack-oriented_programming_language.html"
In other languages