Re: [stack] Re: Concatenative Research

On Feb 3, 2011, at 5:52 AM, Justin wrote:

> But couldn't one also view the concatenative calculus as an alternative to the lambda calculus which may in some circumstances prove more elegant? After all, there's no variables (and the accompanying alpha-renaming), no function application (and the accompanying order-of-evaluation questions), and even no function abstraction if you don't want it.

I think most people would agree that the machinery, if you will, is simpler. The SK calculus is also simpler.

That said, I'm not sure it matters. What matters is how simply these things can be applied to particular problems. In that respect, it does seem that the power of substitution is hard to pass up.

> That certainly works. Do you know which is more powerful, equirecursive or intersection types?

Neither is more powerful than the other. The "power" of a system really depends on what you're trying to do with it.

> Wait, are you saying that typing a typical concatenative language (which allows functions to recursively grow the data stack) is undecidable?

No, type checking for such a language can be decidable. It's only type inference in the presence of polymorphic recursion that is not decidable. This is not at all unique to concatenative languages.

- jn