Re: [stack] stackless fixed-arity concatenative languages

John Nowak <[email protected]> wrote:
> One downside of such functions is that it becomes impossible to
> efficiently compile a language like Joy to C; you have no choice but
> to make use of a stack (or some equivalent mechanism) in the
> implementation.

"Impossible" is an overly strong word (especially in conjunction with
a shades-of-grey word like "efficiently"). It's quite possible to use
the stack in the same way that C itself does; but it's very hard to
work together with your C compiler's optimizer, and I'd say that is
the major difficulty, not anything having to do with stacks.

Even in the presence of statically indeterminate stack effects, MOST
of the program can be efficiently compiled.

BUT, I do agree that it's simple to statically determine stack
effects, so your point is otherwise well-taken. I think that would be
a good variant of Joy.

> It seems the way to do this for a language like Joy would be to find
> alternatives for functions like 'i' and add a type system to ensure
> conditional branches are balanced. Ignoring the type system for now,
> it seems one possibility would be to restrict 'i' to simply dequoting
> the quotation on the top of the stack without allowing it access to
> the stack itself. If one wanted the quotation to have access to
> arguments on the stack, they could be partially applied to the
> quotation first. Several versions of 'i' would need to be available to
> indicate how many values will be returned from its use. For example:

Indeed, Joy does this in many places, with all its functions that
contain a numeral in their name.

>    # 'p' is partial application
>    # 'i1' indicates that the quotation produces 1 value
>    # the result is '7'
>    2 [5 +] p i1
>
> Rather than dealing with partial application, a convenient and
> efficient implementation would simply offer a suite of 'i' combinators
> from 0i0 up until 4i4 or so, where the numbers indicate the number of
> values to be consumed and produced.

At this point, it would seem convenient to add some syntax for
staticly-known (and required) parameters. Perhaps (i 4 4) would be an
example of such syntax. strongForth does something like this with its
EXECUTE function (equivalent to 'i'), which is always followed by a
parenthetical type declaration.

> Does anyone think such a language would be feasible? What might the
> benefits be? What useful features would be lost?

Well, you'd also need to remove Joy's stack-preservation semantics. As
long as that's present, you simply have to implement a stack, no way
around it.

But yes, I see no reason why it'd be hard at all. You'd lose the
ability to create code with dynamic stack effects, but such code is
generally frowned upon anyhow -- it's very hard to read.

> - John

-Wm