Re: [stack] stackless fixed-arity concatenative languages

On May 20, 2008, at 9:42 AM, William Tanksley, Jr wrote:

> 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.

That makes sense. Agreed.

>> 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.

That's certainly possible. I already have that syntax for special  
forms anyway. It might be nice to not require the numbers to be given  
when the effect is inferable though. For example, I often do things  
like '[+] dip', and it would be rather annoying to have to do '[+]  
(dip 2 1)' instead.

Once you start inferring that sort of thing though, you have a  
situation (again) where you can't split definitions cleanly because  
there might not be enough information to infer stack effects. Perhaps  
instead, you could have a 'dip-with' form that takes a quotation  
directly. You could then do something like '(dip-with +)'. This way,  
it is at least clear that you can't split between '+' and 'dip-with'.

In any case, it should be possible to figure out some nice way of  
doing all this.

>> 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.

Aye. I've already decided against that as Joy's semantics are just too  
hard to compile efficiently. The one thing I really wanted Joy's stack- 
preservation for however was assertions and contracts. It's important  
to be able to remove assertions from a program without changing the  
program's meaning, and preserving the stack takes care of that.  
However, a fixed arity restriction does that as well, as it is known  
at compile time how many elements of the stack need to be saved and  
restored for the call to assert. Since we're not longer dealing with a  
stack though, you just call assertion with the arguments it needs and  
ignore the result. Very easy.

> 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.

Very good. Thank you William and Chris for giving me the go-ahead.

- John