A concatenative programming library in 5 lines of Clojure

http://blog.fogus.me/2013/01/06/pesto5-a-concatenative-programming-library-in-5-lines-of-clojure/

by cpleppert • 14 years ago

44 17 14 years ago

blog.fogus.me

This isn’t concatenative except in the trivial sense of “stack-based”. Concatenative languages are functional languages with compositional semantics, which often happen to be most efficiently implemented as stack machines. Concatenative languages are interesting because they’re a combinator calculus like SKI[1] but with simpler semantics and useful algebraic properties.

Only allowing two-argument functions doesn’t cut it, and you need some means of returning multiple values as well. You also need a means of abstraction (e.g., Clojure fns) and combinators for application, abstraction, and stack manipulation. A full implementation of an interpreter for a concatenative DSL would be rather longer than this—though still probably in the realm of 100 lines.

[1] http://en.wikipedia.org/wiki/SKI_combinator_calculus

fogus• 14 years ago

I'm not sure that the presense of a stack is required for a concatenative language, but your point is well taken. Pesto5 is not enterprise ready.

evincarofautumn5• 14 years ago

Right, that’s what I said. Just because it’s efficient to implement one language that way doesn’t mean it’s efficient to do that for every language in the same family. :)

With non-variadic arithmetic functions:

    (defn add [x]
      (cons (+ (first x) (second x)) (rest (rest x))))

Your “postfix” function can remain a simple “reduce”, but can be totally agnostic of function arity. That frees you up to write the basic combinators:

    (defn dup [x]
      (cons (first x) x))

    (defn zap [x]
      (rest x))

    (defn swap [x]
      (cons (second x) (cons (first x) (rest (rest x)))))

    (defn ap [x]
      (apply (first x) (rest x)))

    ...

sparist• 14 years ago

A data stack is indeed not required -- see Om (experimental):

http://concatenative.org/wiki/view/Om

It uses prefix notation: instead of a data stack, each function takes the remainder of the program for rewriting.

dkersten• 14 years ago

Enchilada is a concatenative language which is not stack based but instead works through term rewriting.

snprbob862• 14 years ago

I whether or not there is a stack is similar to the complementary nature of foldL vs parallel fold (ie Clojure's core/reduce vs reducers). Left-to-right concatenative languages make use of a stack and are appropriate for side effects and stream processing. However, there are pure concatenative languages that operate in parallel via term rewriting, which has a computational model akin to that of a DNA computer.

groovy2shoes• 14 years ago

> Concatenative languages are interesting because they’re a combinator calculus like SKI but with simpler semantics and useful algebraic properties.

It's difficult to have simpler semantics than SK calculus. Perhaps a more appropriate modifier in this instance would be "more convenient".

evincarofautumn5• 14 years ago

Yes, that’s fair. The example I had in mind was to do with GC: I’m not sure you can implement an SK interpreter without it.

gruseom• 14 years ago

You seem to have missed the point of this fun little exercise. Search for "in no way indicative" and "debatable" in the OP.

evincarofautumn5• 14 years ago

No no, I only said this for the benefit of others who might not be familiar with concatenative programming. The OP clearly knows what they’re doing.

snprbob862• 14 years ago

Fogus linked to my project, Factjor:

https://github.com/brandonbloom/factjor

Factjor supports quotations, currying, composition, and has most of the primary combinators: dip, keep, cleave, spread, application, etc. It's only about 100 lines.

tikhonj• 14 years ago

Amusingly, just like whoever wrote the Haskell example linked in the blog, the very first thing I did with free monads was also write a trivial stack-based language. All I supported was pushing numbers to the stack and addition. Not a very complicated language! Programs look something like:

    prog = do {1; 2; add; 3; 4; add; add}

The cool thing is that I get "subroutines" (or, as Forth calls them, "words") for free:

    incr = do {1; add}
    prog = do {1; incr; incr; incr}

The interesting thing is that incr and prog are actually ASTs: I can run them, with a function called runProgram, but I can just as easily pretty print them. This is a wonderful property of free monads that's very useful for real DSLs. And, in fact, I'm using them for a current project--they're great.

With a bit of cleverness, it's probably possible to encode some of the stack semantics into the type system, making running a program with too few or too many elements left on the stack a type error. Also, with GADTs, I can probably add support for something like strings and have a mini string/int type system just for my little language, without much effort.

evincarofautumn5• 14 years ago

I’m working on a statically typed concatenative language and would be happy to chat about typing in your stack language. My username at Gmail.

thejsjunky2• 14 years ago

> it's probably possible to encode some of the stack semantics into the type system, making running a program with too few or too many elements left on the stack a type error

Indeed, Factor does this. In addition to checking for stack (over/under)-flows it's what allows really powerful behavior like the ability to say "run both these words with the current stack" without having to explicitly state how much of the stack to duplicate.

thejsjunky2• 14 years ago

Stack based and concatenative programming languages are something I find really interesting. It's really easy to implement a simple one, so one of my go-to benchmarks for trying out a new language is to implement a little stack based language in it.

They're a lot of fun, and some simple ideas can lead to really interesting results. Since all code is just a sequence of tokens it becomes trivial to treat words, quotations, and entire programs as lists and manipulate them a la Lisp. Another nice thing is many such languages give you access to the parser. One I wrote recently is (almost) interpreted directly from text and let's you hook into the parsing process. It doesn't have comments, but it's trivial to add them:

    IMMEDIATE: /* BEGIN NEXT-TOKEN STRING */ EQ? UNTIL ;

This turns "/*" into a function that will drop tokens until it comes to a terminating marker. Such functionality can be used for macros or to add to DSLs.

Also interesting is how the stack changes the way you write code. What you end up with is program that's entirely made of something like pipes in ML-like languages or chaining constructs in JavaScript. They're very easy to compose together (and generally there's less overhead) so it encourages "factoring" out into lots of little pieces; something you can do in almost any language but doesn't feel as natural IMO.

dherz• 14 years ago

You might have a look at Consize, a concatenative language I implemented in Clojure in 140 LOC. Consize is very much inspired by Factor, however Consize is a functional language like Joy or Cat is.

http://code.google.com/p/consize/

It is extensively documented in German — I plan to add some documentation in English as well. But you might enjoy reading the source code anyhow ;-) After reading consize.clj, I recommend to continue with prelude-plain.txt.

BTW: Adding object-orientation (i.e. polymorphism via generic words & multiple inheritance much like Clojure does) is possible in about 30 LOC.

Dominikus

A concatenative programming library in 5 lines of Clojure

Related Stories