Stack-oriented programming language

Stack-oriented programming language

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

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.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 "pop"ping, and putting data back on the top of the stack, known as "push"ing. 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.

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.

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 )

PostScript stacks

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

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 defassociates 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".

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.

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} defand 3 sqis 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: 9which is the result we wanted.

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) = } ifelseperforms the near equivalent in C: if(2 >= 3) { printf("2 is greater than three "); } else { printf("2 is not greater than three "); }

Looping and other constructs are similar.

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.

See also

* Stack (data structure)
* Java virtual machine
* Call stack
* Reverse Polish notation


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Concatenative programming language — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurr …   Wikipedia

  • Esoteric programming language — An esoteric programming language (sometimes shortened to esolang) is a programming language designed as a test of the boundaries of computer programming language design, as a proof of concept, or as a joke. There is usually no intention of the… …   Wikipedia

  • Cat (programming language) — Infobox programming language name = Cat paradigm = multi paradigm: functional, stack oriented year = 2006 designer = [http://www.cat language.com Christopher Diggins] latest release version = 0.10.3 latest release date = April 3, 2007 typing =… …   Wikipedia

  • Onyx (programming language) — Onyx is a stack oriented programming language. External links Onyx Home Page Categories: Stack oriented programming languagesConcatenative programming languagesProgramming language topic stubs …   Wikipedia

  • C Sharp (programming language) — The correct title of this article is C# (programming language). The substitution or omission of the # sign is because of technical restrictions. C# Paradigm(s) multi paradigm: structured, imperative …   Wikipedia

  • Java (programming language) — infobox programming language name = Java paradigm = Object oriented, structured, imperative year = 1995 designer = Sun Microsystems latest release version = Java Standard Edition 6 (1.6.0) latest release date = latest test version = latest test… …   Wikipedia

  • Joy (programming language) — Joy Paradigm(s) multi paradigm: functional, concatenative, stack oriented Appeared in 2001 Designed by Manfred von Thun Developer Manfred von Thun, John Cowan St …   Wikipedia

  • Mouse (programming language) — The Mouse programming language is a small computer programming language developed by Dr. Peter Grogono in the late 1970s and early 1980s.[1][2] It was developed as an extension of an earlier language called MUSYS, which was used to control… …   Wikipedia

  • Claire (programming language) — Claire Paradigm(s) multi paradigm: functional, object oriented (class based), rule processing, reflective Appeared in 1994 (1994) Designed by Yves Caseau Stable release …   Wikipedia

  • LPC (programming language) — Infobox programming language name = LPC paradigm = prototype based year = designer = Lars Pensjö developer = Lars Pensjö and others latest release version = latest release date = typing = implementations = LPC dialects = Amylaar, MudOS, LDMud,… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”