Concatenative programming language
From Wikipedia, the free encyclopedia
In concatenative programming languages, the concatenation of appropriate programs denotes the composition of the functions which the programs denote. In other words, one can directly copy the source of one program onto the end of another, and the result is always a well-formed program whose meaning is the output of one program being treated as the input to the other. To achieve this, operations typically map an input stack into a results stack, and so it is possible to repeatedly concatenate a sequence of operations to create a program.
Formally speaking, a programming language is concatenative (and not applicative) when:
- The elementary well-formed expressions of the language are monadic functions of one argument and one return value.
- If X and Y are well-formed expressions, then the concatenation of X and Y is well-formed.
- If Z is the concatenation of X and Y, then the value of Z is the composition of the values of X and Y.
In this definition, there is no mention of the stack, and it is theoretically possible to have a concatenative language without a stack, but in practice, no such language exists. This precise definition of concatenative languages is controversial, and the actual meaning of "concatenative" is frequently debated.
Arguably, Forth was the first concatenative language, but Joy was the first language to call itself concatenative. The creator of Joy, Manfred von Thun, has written much about concatenative theory.
Many people, particularly people on the more practical side of programming in languages like Factor and Forth, consider the term "concatenative programming language" mostly useless. There is still a lot of confusion about what "concatenative" means exactly, and the above definition isn't what everyone accepts. Opponents of the term suggest using words like "stack-based" instead, which is usually more meaningful.
[edit] Examples
In Joy, the program fragment (call it A):
2 7 +
pushes "2" then "7" onto the stack. The "+" operator then replaces the stack with a new stack that contains the resulting sum "9". This notation is also known as reverse Polish notation.
In this language, the following fragment B takes the stack and adds 9 onto it:
9 +
According to the definition of a concatenative language, the concatenation of the two, A B:
2 7 + 9 +
must be a well formed program. Moreover, its meaning must be the composition of the two fragments B(A). That is, the composition of "7 plus 2" with "plus 9", or in other words, "7 plus 2 plus 9", leaving 18 on the stack.
