Lambda the Ultimate

inactiveTopic Theory of Concatenative Combinators
started 10/8/2002; 6:25:49 AM - last post 10/17/2002; 8:42:30 AM
Shae Erisson - Theory of Concatenative Combinators  blueArrow
10/8/2002; 6:25:49 AM (reads: 301, responses: 4) Joy is a postfix concatenative stack-based functional language. The concatenative aspect allows the code to be extremely concise, and the stack based aspect allows for easy understanding. It claims some distant relationship to Forth and PostScript.

Kerby's paper comes from a brute force "minimal base" program he wrote in Joy. He uses this program to find different minimum sets of combinators for Joy.

If you'd like to learn more about Joy, here's a quick hack to give you a feel for the syntax:

(* x y percent approxEqual *) DEFINE approxEqual == 100.0 / rotate [0 =] [pop] [dup rolldown - swap /] ifte > .

Joy's homepage is at

Ehud Lamm - Re: Theory of Concatenative Combinators  blueArrow
10/8/2002; 7:03:48 AM (reads: 305, responses: 0)
the stack based aspect allows for easy understanding

And I always thought stack based languages are the worst when it comes to readability.

Shae Erisson - Re: Theory of Concatenative Combinators  blueArrow
10/9/2002; 5:10:53 AM (reads: 286, responses: 1)
The easy part (for me) about stack-based languages is that everything happens where and when the arguments hit the stack. You don't need to worry about values changing names, they only have positions. I find that easy to track through.

Ehud Lamm - Re: Theory of Concatenative Combinators  blueArrow
10/9/2002; 11:14:26 AM (reads: 304, responses: 0)
So use (pure) functional languages...

I see your point about the code being easy to understand. I was thinking about it being easy to read -- which is not the case with stack based languages.

Frank Atanassow - Re: Theory of Concatenative Combinators  blueArrow
10/17/2002; 8:42:30 AM (reads: 282, responses: 0)
I think the "simplicity" here is largely illusory; it seems simple only because it focuses on simple problems, namely how to manipulate a stack and how to re-express yourself in postfix syntax. Like crossword puzzles, this can be a fun game to play, but it isn't usually the problem you want to be solving when you write a program.

  • Suppose I want to use a function argument which is n elements below the top of the stack. Then I have to figure out a way to pop, dup, roll, etc. to get at it without destroying the stuff above it. This is the sort of task which an optimizer is better at than a human.
  • In the same situation, I have to remember an implementation detail, where on the stack it is, rather than "simply" what its name is.
  • If you really love concatenativity, you could easily program these combinators up in a functional language anyway, so what's the point of restricting yourself to a language which only allows that means of expression?

Deja vu... I think I've written this post once before.