Re: [stack] stackless fixed-arity concatenative languages

This is a reasonable idea for some cases, but there's some generality
that's lost. Look at how reduce is defined in Factor:

: reduce ( seq identity quot -- result )
    swapd each ;

When each runs, it has the stack underneath as an implicit
accumulator. That means that we can just use the code of each when
writing reduce, but only because the quotation can be not just 1/0 but
also 2/1. The genericness here allows a reduction in code duplication
in certain cases which are completely impossible in Haskell (unless
you start by implementing reduce, then base a each off of it
(pretending Haskell has side effects), and this is more complicated),
though arguably unnecessary.

Anyway, can't a type signature for each of something like ( A ( A x --
A ) [x] -- A ) handle this adequately? Is it difficult to infer or
deal with such a type?

Dan

On Tue, May 20, 2008 at 1:15 AM, John Nowak <[email protected]> wrote:
> 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.
>
>