[stack] stackless fixed-arity concatenative languages

In some languages, such as Haskell, all functions consume a fixed  
number of arguments and produce a fixed number of arguments.* For  
example, the 'foldr' function in Haskell always consumes three values  
and produces one. In fact, all functions in Haskell produce one value.

Concatenative languages like Joy expand on this; functions are not  
restricted to returning only one value.** For example, 'dup' consumes  
one value and produces two. We'll say 'dup' has a 1/2 arity; 'pop'  
would have a 1/0 arity, '+' would have a 2/1 arity, 'swap' would have  
a 2/2 arity, and so on.

However, some functions in Joy go beyond this. For example, 'i'  
essentially takes the entire state of the program as an argument and  
yields a new state. Because 'i' simply invokes the quotation on the  
top of the stack, there's no way to tell how many values 'i' will  
consume or produce without knowing what's on top of the stack. Other  
examples of such functions include 'dip' and 'while'.

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. In contrast, a concatenative language with only fixed- 
arity functions can be efficiently compiled to C without any need for  
a stack. An example of such a language is Forth without n-ary words  
like 'roll' and with the modest restriction that both branches of a  
conditional must have the same stack effect. [1][2]

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:

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

While this all likely seems to be overly burdensome at first, most  
functions that make use of quotations would not need so many versions.  
For example, 'fold' would only be valid for quotations of arity 2/1,  
and hence only one version would be needed.

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

- John

[1] http://www.complang.tuwien.ac.at/papers/ertl%26maierhofer95.ps.gz
[2] http://www.complang.tuwien.ac.at/papers/ertl96diss.ps.gz

* Yes, all functions in Haskell /really/ take one argument and are  
curried, and yes, there are tricky ways of implementing variadic  
functions, but we'll ignore that for now.

** Yes, all functions are /really/ unary functions of stacks to  
stacks, but we'll ignore that for now.