Stack-oriented programming, is a
programming paradigm
Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms.
Some paradigms are concerned mainly with implications for the execution model of the language, suc ...
which relies on a
stack machine
In computer science, computer engineering and programming language implementations, a stack machine is a computer processor or a virtual machine in which the primary interaction is moving short-lived temporary values to and from a push down st ...
model for passing
parameters
A parameter (), generally, is any characteristic that can help in defining or classifying a particular system (meaning an event, project, object, situation, etc.). That is, a parameter is an element of a system that is useful, or critical, when ...
. Stack-oriented languages operate on one or more
stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
s, each of which may serve a different purpose. Programming constructs in other programming languages need to be modified for use in a stack-oriented system. Some stack-oriented languages operate in ''postfix'' or
Reverse Polish notation
Reverse Polish notation (RPN), also known as reverse Łukasiewicz notation, Polish postfix notation or simply postfix notation, is a mathematical notation in which operators ''follow'' their operands, in contrast to Polish notation (PN), in whi ...
. Any arguments or parameters for a command are stated ''before'' that command. For example, postfix notation would be written instead of (''prefix'' or
Polish notation
Polish notation (PN), also known as normal Polish notation (NPN), Łukasiewicz notation, Warsaw notation, Polish prefix notation or simply prefix notation, is a mathematical notation in which operators ''precede'' their operands, in contrast t ...
), or (
''infix'' notation). The programming languages
Forth
Forth or FORTH may refer to:
Arts and entertainment
* ''forth'' magazine, an Internet magazine
* ''Forth'' (album), by The Verve, 2008
* ''Forth'', a 2011 album by Proto-Kaw
* Radio Forth, a group of independent local radio stations in Scotla ...
,
Factor
Factor, a Latin word meaning "who/which acts", may refer to:
Commerce
* Factor (agent), a person who acts for, notably a mercantile and colonial agent
* Factor (Scotland), a person or firm managing a Scottish estate
* Factors of production, suc ...
,
RPL,
PostScript
PostScript (PS) is a page description language in the electronic publishing and desktop publishing realm. It is a dynamically typed, concatenative programming language. It was created at Adobe Systems by John Warnock, Charles Geschke, Doug Br ...
,
BibTeX
BibTeX is reference management software for formatting lists of references. The BibTeX tool is typically used together with the LaTeX document preparation system. Within the typesetting system, its name is styled as . The name is a portmanteau ...
style design language
and many
assembly language
In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be ...
s fit this paradigm.
Stack-based algorithms consider data, by utilising one piece of data from atop the stack, and returning data back atop the stack. The need for stack manipulation operators, allow for the stack to manipulate
data
In the pursuit of knowledge, data (; ) is a collection of discrete values that convey information, describing quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpreted ...
. To emphasise the effect of a statement, a comment is used showing the top of the stack before and after the statement. This is known as the stack effect diagram.
Postscript
stacks consider separate stacks for additional purposes. This considers variables, dictionaries, procedures, anatomy of some typical procedures, control and flow. The analysis of the
language model
A language model is a probability distribution over sequences of words. Given any sequence of words of length , a language model assigns a probability P(w_1,\ldots,w_m) to the whole sequence. Language models generate probabilities by training on ...
allows expressions and programs to be interpreted simply and theoretically.
Stack-based algorithms
PostScript is an example of a postfix stack-based language. An expression example in this language is . Calculating the expression involves understanding how stack-orientation works.
Stack-orientation can be presented as the following conveyor belt analogy. at the end of a conveyor belt (the ''input''), plates marked
2
,
3
, and
mul
are placed in sequence. The plate at the end of the conveyor (
2
) can be taken, however other plates cannot be accessed until the plate at the end is removed. The plates can only be stored in a stack, and can only be added or removed from atop the stack, not from the middle or bottom. Blank plates (and a marker) can be supplied and plates can be permanently discarded.
![Human stack](https://upload.wikimedia.org/wikipedia/commons/5/50/Human_stack.svg)
Take plate
2
and put it on the stack, then take plate
3
and put it on the stack. Next, take the
mul
plate. This is an instruction to perform. Then, take the top two plates off the stack, multiply their labels (
2
and
3
), and write the result (
6
) on a new plate. Discard the two old plates (
2
and
3
) and the plate
mul
, and put the new plate on the stack. With no more plates remaining on the conveyor, the result of the calculation (
6
) is shown on the plate atop the stack.
This is a very simple calculation. What if a more complex calculation is needed, such as ? If it is first written in postfix form, that is, ,
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.
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 ''pop''ping, and putting data back atop the stack, termed ''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 being interpreted by a stack-oriented language.
Stack manipulation
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.
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 -- n' )
It is equivalent to
precondition
In computer programming, a precondition is a condition or predicate that must always be true just prior to the execution of some section of code or before an operation in a formal specification.
If a precondition is violated, the effect of the s ...
s and
postcondition In computer programming, a postcondition is a condition or predicate that must always be true just after the execution of some section of code or after an operation in a formal specification. Postconditions are sometimes tested using assertions wit ...
s in
Hoare logic
Hoare logic (also known as Floyd–Hoare logic or Hoare rules) is a formal system with a set of logical rules for reasoning rigorously about the correctness of computer programs. It was proposed in 1969 by the British computer scientist and log ...
. Both comments may also be referenced as
assertions, thought not necessarily in context of Stack-based languages.
PostScript stacks
PostScript and some other stack languages have other separate stacks for other purposes.
Variables and dictionaries
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,
x
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
.
For example, in PostScript syntax,
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 of 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.
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.
To examine a
Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
program in PostScript:
/fib
def
A recursive definition is used on the stack. The Fibonacci number function takes one argument. First, it is tested for being 1 or 0.
Decomposing each of the program's key steps, reflecting the stack, assuming calculation of
fib(4)
:
stack: 4
dup
stack: 4 4
dup
stack: 4 4 4
1 eq
stack: 4 4 false
exch
stack: 4 false 4
0 eq
stack: 4 false false
or
stack: 4 false
not
stack: 4 true
Since the expression evaluates to true, the inner procedure is evaluated.
stack: 4
dup
stack: 4 4
1 sub
stack: 4 3
fib
: ''(recursive call here)''
stack: 4 F(3)
exch
stack: F(3) 4
2 sub
stack: F(3) 2
fib
: ''(recursive call here)''
stack: F(3) F(2)
add
stack: F(3)+F(2)
which is the expected result.
This procedure does not use named variables, purely the stack. Named variables can be created by using the
/a exch def
construct. For example,
is a squaring procedure with a named variable
n
. Assuming that
/sq def
and
3 sq
is called, the procedure
sq
is analysed in the following way:
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 expected result.
Control and flow
As there exist anonymous procedures, flow control can arise naturally. Three pieces of data are required for an
if-then-else
In computer science, conditionals (that is, conditional statements, conditional expressions and conditional constructs,) are programming language commands for handling decisions. Specifically, conditionals perform different computations or actio ...
statement: a condition, a procedure to be done if the condition is true, and one to be done if the condition is false. In PostScript for example,
2 3 gt ifelse
performs the near equivalent in C:
if (2 > 3) else
Looping and other constructs are similar.
Analysis of the language model
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
In linguistics, syntax () is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure (constituency), ...
need be done, only
lexical analysis
In computer science, lexical analysis, lexing or tokenization is the process of converting a sequence of characters (such as in a computer program or web page) into a sequence of ''lexical tokens'' (strings with an assigned and thus identified m ...
. 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 to repeat code to generate the style.
See also
*
List of stack-based programming languages
This is a list of notable programming languages, grouped by type.
There is no overarching classification scheme for programming languages. Thus, in many cases, a language is listed under multiple headings (in this regard, see " Multiparadigm la ...
*
Reverse Polish notation
Reverse Polish notation (RPN), also known as reverse Łukasiewicz notation, Polish postfix notation or simply postfix notation, is a mathematical notation in which operators ''follow'' their operands, in contrast to Polish notation (PN), in whi ...
*
Return-oriented programming
Return-oriented programming (ROP) is a computer security exploit technique that allows an attacker to execute code in the presence of security defenses such as executable space protection and code signing.
In this technique, an attacker gains cont ...
References
{{Types of programming languages
Programming paradigms