Dec

2008

In part one of this series, I introduced the concept of a stack-based language and in particular the syntax and rough ideas behind Cat. However, to anyone coming into concatenative land for the first time, my examples likely seemed both odd and unconvincing. After all, why would you ever use point-free programming when everyone else seems to be sold on the idea of name binding? More importantly, where do these languages fit in with our established menagerie of language paradigms?

The answer to the first question really depends on the situation. I personally think that the best motivation for concatenative languages is their syntax. If you want to create an internal DSL, there will be no language better suited to it than one which is concatenative, Cat, Factor or otherwise. This is because stack-oriented languages can get away with almost no syntax whatsoever. They say that Lisp is a syntax-free language, but this holds even more strongly for languages like Cat. Well, that and you don’t have to deal with all the parentheses…

The second question is (I think) the more interesting one: how do we classify these languages and what sort of methodologies should we apply? At first glance, Cat (and other languages like it) seem to be quite imperative in nature. After all, you have a single mutable stack that any function can modify. However, if you turn your head sideways and blink twice, you begin to realize that concatenative languages are really much closer to the functional side of the oyster.

Consider the following Cat program:

define plus { + } define minus { - } 7 2 3 plus minus |

Trivial, but to the point. This program first adds the numbers `2`

and `3`

, then subtracts the result from `7`

. Thus, the final result is a value of `2`

on the stack. The only twist is that we have defined functions `plus`

and `minus`

to do the dirty work for us. This wasn’t strictly necessary, but I wanted to emphasize that `+`

and `-`

really are functions. We could express the exact same program in Scala:

def plus(a: Int, b: Int) = a + b def minus(a: Int, b: Int) = a - b minus(7, plus(2, 3)) |

Do you see how the consecutive invocations of `plus`

and `minus`

in Cat became composed invocations in Scala? This is where the term “concatenative language” derives from: the whole program is just a series of function compositions. Wikipedia’s article on Cat has a very nice, mathematical description:

Two adjacent terms in Cat imply the composition of functions that generate stacks, so the Cat program

`f g`

is equivalent to the mathematical expressions and , wherexis the stack input to the expression.

Strictly speaking, a concatenative language could be implemented without a stack, but such an implementation would likely be a bit harder to use than the average stack-based language.

Coming back to my original premise: concatenative languages are functional in nature. Absolutely *everything* in Cat is a function. Operators, words, even numeric literals like “`3`

” are actually functions at the conceptual level. Additionally, Cat, Joy and Factor all offer a mechanism for treating functions as first-class values:

2 3 [ + ] apply |

The square-bracket (`[]`

) syntax is representative of a quotation. Literally this mean “create a function of the enclosed words and place it as a value on the stack”. We can pop this function off the stack and invoke it by using the `apply`

word. Incidentally, you may have noticed that this syntax is remarkably close to that which is used in `if`

conditionals:

5 0 < [ "strange math" ] [ "all is well" ] if |

This syntax works because `if`

isn’t *conceptually* a language primitive: it’s just another function which happens to take a boolean and two quotations off the stack. For the sake of efficiency, Cat does indeed implement `if`

as a primitive, but this was a deliberate optimization rather than an implementation forced by the language design. Untyped Cat (see Part 3) is equivalent in power to the pure-untyped lambda calculus, and as our friend Alonzo Church showed us, `if`

-style conditionals are easily accomplished:

FALSE = λa . λb . b

IF = λp . λt . λe . p t e

Yeah, maybe we’re drifting a bit off-point here…

### Higher-Order Programming

So if Cat is just another functional programming language, then we should be able to implement all of those higher-order design patterns that we’ve come to know and love in languages like Scala and ML. To see how, let’s look at implementing some simple list manipulation functions in Cat. The easiest would be to start with `append`

, which pops two lists off of the stack and pushes a new list which is the end-to-end concatenation of the two originals:

define append { empty [ pop ] [ uncons [append] dip cons ] if } |

This function first starts by checking to see if the top list is empty. If so, then just pop it off the stack and leave the other right where it is. Appending an empty list should always yield the original list. However, if the head list is *not* empty, then we need to work a bit. First, we decompose it into its tail and head, which are pushed onto the stack in order by the `uncons`

function. Next, we need to recursively append the tail with our second list on the stack. However, the head of the list from `uncons`

is in the way on top of the stack. We could use stack manipulation to move things around and get our lists up to the head of the stack, but `dip`

provides us with a handy, higher-order shortcut. We temporarily remove the top of the stack, invoke the quotation “`[append]`

” against the remainder and then push the old top back on top of the result.

The `dip`

operation is surprisingly powerful, making it possible to completely live without either variables or multiple stacks. Any non-trivial Cat program will need to make use of this handy function at some level.

Once we have the old head and the new appended-list on the stack, all we need to do is put them back together using `cons`

. This function leaves a new list on the stack in place of the old list and head element. This Cat program is almost precisely analogous to the following ML:

fun append ls nil = ls | append ls (hd :: tail) = hd :: (append ls tail) |

Personally, I find the ML a lot easier to read, but that’s just me. Obviously it’s a lot shorter, but as it turns out, our Cat implementation, while intuitive, was sub-optimal. Cat already implements `append`

in the guise of the `cat`

function, and it is far more concise than what I showed:

define cat { swap [cons] rfold } |

It’s almost frightening how short this is: only three words. It’s not as if `rfold`

is doing anything mysterious either; it’s just a simple right-fold function that takes a list, an initial value and a quotation, producing a result by traversing the entire list. We can use something similar back in ML-land, achieving an implementation which is arguably equivalent in subjective elegance:

val append = foldr (op::) |

Moving on, we can also implement a `length`

function in Cat, this time using `fold`

to tighten things up:

define length { 0 [ pop 1 + ] fold } |

You’ll notice that we have to mess around a bit in the quotation in order to avoid the first “parameter”, the current element of the list (which we do not need). Expressing this in ML yields a very similar degree of cruft:

val length = foldl (fn (n, _) => n + 1) 0 |

### Conclusion

The important take-away from this tangled morass of an article is the fact that Cat is a highly functional language, capable of easily keeping up with some of the stalwart champions of the paradigm. More significantly, this is a trait which is shared by *all* concatenative languages. Rather than throwing away all of the old wisdom learned in language design, stack-based languages build on it by providing an alternative view into the world of functions.

In the next (and final) article of the series, we will take a brief look at the challenges of applying a type system to a concatenative language and the fascinating techniques used by Cat to achieve just that.

## Comments

Hello,

I have a brief question about the ‘dip’ operator. Where is the element that is popped off placed? It seems to me that this is a secondary stack, in fact, the ‘usual’ stack which one might find in functional programs, while the actual ’stack’ used by Cat is more like a big input argument that is threaded along. (Sort of like the ‘World’ in the IO monad of Haskell, or a list in a state-monad).

Wow! About eight years ago, I invented a concatenative stack-based language when I was playing with genetic programming. It worked really well. It’s easy to cross over two streams of symbols. I just didn’t know there were real languages out there like mine.

Nice articles. Looking forward to part 3.

How is Cat conceptually different than Forth?

First thanks for these great articles, I’m looking forward for part 3.

>>If you want to create an internal DSL, there will be no language better suited to it

>>than one which is concatenative, Cat, Factor or otherwise.

I think you forgot to mention Rebol : creating a DSL with it is really straightforward.

Christophe Poucet: usually the dip operator is implemented by placing the element on a hidden extra stack. So [ ... ] dip in Cat/Joy/Factor is analogous to >r … r> in Forth, except there’s no way to mess up and write code with unbalanced >r/r>’s.

codist: Cat has a type system, first-class functions and automatic memory management. Forth does not.

kib2, Rebol is a cool language; it’s not a coincidence that its author has a lot of experience with Forth. Its DSL capabilities lie in two main areas: first, its syntax is simple enough to be generally useful for many domains; and second, it comes with a simple LL parser that’s well-integrated. Factor excels over Rebol in both of these ways — it has a PEG parser (which is far more powerful than Rebol’s LL parser), and its syntax is strictly left-to-right (as opposed to Rebol’s left to right reading with right-to-left execution).

Still, Rebol is a good language. I hope its new version does well; I’ve been watching it hoping for some results for quite some time.

Hello Slava,

I admit that I find the concept of the ’stack’ in stack languages then rather ambiguously phrased. To me it just seems -a- datastructure that is threaded along that just happens to be a stack. But it appears that the true call stack is that hidden stack you refer to. Is this correct?

Christophe, the “stack” in stack languages is the means for communicating between function invocations. Some stack languages, like Forth, actually have two stacks, with the second one serving as the return stack and a temporary data storage space; but only one is absolutely needed. There’s an experimental concatenative language named “xy” which uses a queue, and it’s possible to code a “stackless” call structure so that a call stack isn’t used (although I don’t know whether anyone’s done that yet for a concatenative language).

I tought Rebol’s parse was using a parsing expression grammar algo too, but maybe I was wrong.

I already tried Factor wich seems a very interesting language, but the main problem is actually the total lack of documentation. Sure, there’s a “Your first program” section and then the “index”, but how can learn a programming language from an index (particularly when it is a stack based one)? Not me. I already told Slava about this fact on IRC, and I can understand he’s busy developping Factor; but one must admit that a language without docs is just useless. Some efforts have been done by Aaron Schaefer recently by writting some blog posts about Factor, and they’re really great. Here too, I’m looking forward for his third part.

kib2, there is a lot of documentation in Factor. Look at http://docs.factorcode.org or use the browser in the Factor UI, you will find that the entire core language and most of the libraries are extensively documented. For introductory material, there is a tutorial as well as a cookbook.

The concatenative language’s concept of a “stack” actually is a very precise, mathematically defined construct: a last in, first out stack.

The dip operator is 100% compatible with this definition. It pops the top of the stack, applies the quotation to the resulting stack, then pushes the original item back onto the stack. At NO TIME does the dip operator violate the semantics of the mathematical concept of a stack.

In the real-world, of course, our computers do not run on stack architectures; therefore, it might store the top of stack in another CPU register. Or, it might be pushed onto the hardware call stack, as in Forth with >R and R>. Or, who knows, it might be stored in a well-known, reserved memory location (a la 6502’s zero-page locations). This is an implementation detail that you needn’t concern yourself with.

You proposed the following Scala as equivalent:

minus(7, plus(2, 3))

To be the equivalent you seek, wouldn’t the code actually need to be as follows?

minus(plus(7, 2, 3))

(Here let’s assume the definitions of plus and minus have been changed so that they apply only to the last two items in the list.)

@Tracy,

No. His equivalence is correct. Your equivalence would be 7 2 3 + + – which would produce a stack underflow.

## Post a Comment