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:

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

In Haskell:

(even)
(not . even)
(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 + ]

Compare with lisps applicative version; note the closure does not print readably:

* (let ((x 5)) (lambda (y) (+ x y)))
#<FUNCTION (LAMBDA (Y)) {11682335}>

or Haskell:

(5+)
Functions cannot be printed in Haskell

Examples of compose:

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

Applicative version:

* (let ((f (lambda (x) (= x 3)))) (lambda (y) (not (funcall f y))))
#<FUNCTION (LAMBDA (Y)) {11680B3D}>
(not . (3 ==))
Again, functions cannot be printed

As you can see, function composition and partial application feels a lot more natural in stack languages, because of the duality between composition and concatenation.

This revision created on Wed, 26 Oct 2011 19:56:28 by DanielSwe