Re: [stack] stackless fixed-arity concatenative languages

John Nowak <[email protected]> wrote:
> Factor's 'bi@' combinator. The 'bi@' combinator takes some x, some y,
> and a quotation which it applies to both. As an example, '4 5 [ dup
> * ] bi@' yields '16 25'.
> Here's one way we might think to implement 'bi@' in Factor:
>    : bi@ ( x y quot -- x' y' ) dup dip dip ;

Great point. Here we seem to actually *need* type annotations on the
function types... I wonder whether it might be a fundamental property
and not just an accident of our lack of understanding.

> This is rather damning, and it may mean that n-ary combinators have to
> be completely eliminated unless a more expressive system can be found.

Or such combinators may have to be accommodated via specialized syntax.

> One way to do this would be fixed arity versions of 'dip' and 'i',
> along with built-in mechanisms for pattern matching and deconstruction
> (a la Haskell, et al) rather than simply using normal functions like
> 'unlist' as I've talked about previously.

Seems like a smart idea.

> There would still need to be
> some way to address the need to allow the user to write new
> combinators like '2dip' that apply a quotation below the top two
> elements of the stack rather than just one. Introducing something like
> lambda expressions would be one way to do this (similar to how
> Backus's Formal FP allowed lambda expressions for creating new
> combinators).



> Unfortunately, this type system is undecidable, expensive, and yields
> ugly types. What fun!

Undecidable isn't always bad. In general, types are undecidable. The
question is whether we're drawing the line at the right location, or
whether we're throwing away too much info.

> Hey, I thought concatenative languages were supposed to be simpler!

They appear to be, but the fundamental research for them hasn't been
done yet. You're doing the research at the same time as you're
generating a practical application. This is a recipe for high risk.
Hope you don't have any large amounts of money invested in this!

> - John

-Wm