Concatenative Programming
The concatenation of two programs denotes the composition of the functions denoted by the two programs.
Concatenative programming is a point-free approach to writing code. Functions compose by means of simple juxstiposition. Additionally, any function can be replaced directly by it's definition and vice versa. Programs are thus built up by composing smaller primitives together.
Joy, The Canonical Catlang
In 2001, Manfred von Thun created Joy. It was the first language to call itself "concatenative" and formalized many of the ideas behind the paradigm. Code was written in a postfix style. Each function represented a transformation from state to state (the state being represented by a stack). The core of a Joy program consisted of two operations: concatenation and quotation (Mathematical Foundation of Joy, Manfred von Thun).
Concatenation is an infex operator. Since composition happens by default, it has no symbol. Instead it's denoted by the whitespace between functions. The result of one function is automatically chained to the next. All functions are free to produce and consume multiple values from the current stack.
- abs
Quotations allow for capturing a program as a value. A quotation is denoted by matching square brackets ([...]). They can be passed two and between functions like any other program. Furethermore, they can be manipuated like any other piece of data.
5 [1] [*] primrec
primrec combinator. (Mathematical Foundations of Joy, Manfred von Thun)
These two principles a woven deeply into the fabric of concatenative programmings. Many concatenative programmings languages feature some way to leavage these two principles (composition being required). However, there is a third feature promentent in concatenative programming languages.
Combinators
Combinators are what enable concatenative programming languages (catlangs for short) to be so powerful. They are higher-order functions — functions which operate on other functions — that serve as a means to change the dataflow of a program.
A language like Factor makes ample use of combinators. They serve as the means for writing loops, abstracting flow control, and improving readability by reducing the need for direct menipulation of the stack.
Stacks that Shuffle and Shuffles that Stack
While not a hard requirement, many implementations of catlangs are stack based. A stack is the simplist construct which allows functions to communicate between one and other. Data is allowed to persist between operations. Consummed in a first-in-last-out order.
With two stacks, you can have something turing complete.
This simplicity lead to Chuck Moore's discovery of Forth in the 1970s (as he would put it). Forth is a low-level stack based langauge. It's been used to write firmware and program microcontrollers. It's small enough to be easily bootstrapped from low-level primitives.
Unlike other "close-to-the-metal-languages", Forth is interactive. Code written in Forth within a live enviroment, providing a tight feedback loop.
: fib
dup 0 <= if drop 0 else
dup 1 = if drop 1 else
1 - recurse swap 2 - recurse +
then then
;
Despite being a low-level procedural language, it has many of the properties of a catlang. Most words (function) compose together in a point free fashion. Additionally, forth support has the same property of being easy to inline and factor code.
For this reason forth is retroactively consider a concatenative programming langauge. Furthermore, all stack-based languages can be view threw a concatenative.
A Triangle
: plot ( i j -- )
bitand zero? "* " " " ? write ;
: pad ( n -- )
1 - [ bl ] times ;
: plot-row ( n -- )
dup 1 + [ tuck - plot ] with each-integer ;
: sierpinski ( n -- )
dup '[ _ over - pad plot-row nl ] each-integer ;
16 sierpinski
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
References and Additional Reading