Skip to content
Print

The Joy of Concatenative Languages Part 2: Innately Functional

15
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 , where x is 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:

TRUE = λa . λb . a
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

  1. 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).

    Christophe Poucet Monday, December 15, 2008 at 5:53 am
  2. 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.

    300baud Monday, December 15, 2008 at 6:49 am
  3. Nice articles. Looking forward to part 3.

    Slava Pestov Monday, December 15, 2008 at 7:31 am
  4. How is Cat conceptually different than Forth?

    codist Monday, December 15, 2008 at 11:44 am
  5. 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.

    kib2 Monday, December 15, 2008 at 1:53 pm
  6. 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.

    Slava Pestov Monday, December 15, 2008 at 5:47 pm
  7. 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.

    Wm Tanksley Monday, December 15, 2008 at 6:19 pm
  8. 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 Poucet Tuesday, December 16, 2008 at 8:11 am
  9. 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).

    Wm Tanksley Tuesday, December 16, 2008 at 8:50 am
  10. 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 Tuesday, December 16, 2008 at 2:44 pm
  11. 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.

    Slava Pestov Wednesday, December 17, 2008 at 8:16 pm
  12. 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.

    Samuel A. Falvo II Friday, December 19, 2008 at 1:48 pm
  13. 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 Harms Thursday, June 18, 2009 at 3:50 pm
  14. @Tracy,

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

    Samuel A. Falvo II Friday, June 19, 2009 at 9:38 am

Post a Comment

Comments are automatically formatted. Markup are either stripped or will cause large blocks of text to be eaten, depending on the phase of the moon. Code snippets should be wrapped in <pre>...</pre> tags. Indentation within pre tags will be preserved, and most instances of "<" and ">" will work without a problem.

Please note that first-time commenters are moderated, so don't panic if your comment doesn't appear immediately.

*
*