Concatenative language/Concatenation is composition

A fundamental property of stack languages is that the concatenation of two programs X and Y -- X Y -- is the program that applies Y to the result of X, that is, the composition of X and Y. This means that certain common quotation patterns can be written very concisely.

For example, in Factor we can filter a sequence by a predicate using the filter combinator:

( scratchpad ) { 1 2 3 4 5 6 7 8 } [ even? ] filter .
{ 2 4 6 8 }

If we want to remove elements matching the predicate instead, we can compose the predicate with the not word:

( scratchpad ) { 1 2 3 4 5 6 7 8 } [ even? not ] filter .
{ 1 3 5 7 }

Partial application works out very nicely too: write a quotation which pushes some of the parameters before calling a word:

( scratchpad ) { 1 2 3 4 5 6 7 8 } [ 4 > ] filter .
{ 5 6 7 8 }

Compare these three quotations,

[ even? ]
[ even? not ]
[ 4 > ]

This is shorter than the equivalent in an applicative language, because we have to name the input argument, that is only used once. In Common Lisp for instance,

(function evenp)
(lambda (x) (not (evenp x)))
(lambda (x) (> x 4))

Since concatenative languages do not have named parameters (let's ignore Factor's locals vocabulary for now), talking about free variables does not make sense. The nearest equivalent in a concatenative language is constructing new quotations from existing quotations.

In Factor, quotations look like a sequence of objects; for example, [ 2 2 + ] has three elements, the integer 2, the integer 2 again, and the word +; the latter is itself an object which can be introspected and executed. This means that we can use sequence operations to construct quotations.

Suppose we have the quotation [ + ]. When executed, it takes two numbers from the stack, adds them, and leaves the result on the stack. If we prefix the quotation with the integer 5, we get a new quotation, [ 5 + ], which adds 5 to the top of the stack. This is similar to currying in applicative languages, so Factor calls this operation curry.

Another fundamental operation on quotations is composition: suppose we take the quotation [ 2 + ] and the quotation [ 0 > ]; their composition is [2 + 0 > ]. Of course, this is just the concatenation of the two quotations.

These two fundamental operations -- curry and compose -- have very simple and intuitive semantics. Note that quotations are printable objects, whereas in applicative languages, closures are typically opaque.

Examples of curry:

( scratchpad ) 5 [ + ] curry .
[ 5 + ]
* (let ((x 5)) (lambda (y) (+ x y)))
#<FUNCTION (LAMBDA (Y)) {11682335}>

Examples of compose:

( scratchpad ) [ 3 = ] [ not ] compose .
[ 3 = not ]

This revision created on Mon, 29 Dec 2008 23:59:53 by slava