## Contents

Front Page

Main:

Concatenative languages:

Interesting languages:

Computer science:

External:

Meta:

# 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))```

```((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}>```

```(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:55:21 by DanielSwe