Re: [stack] stackless fixed-arity concatenative languages

On May 21, 2008, at 1:39 PM, William Tanksley, Jr wrote:

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

It's a fundamental property, at least for any type system resembling  
the one in Fifth as it stands now. This comes about because we're not  
"hiding" the result of the first 'dip' from the second. One way around  
this would be to have 'bi@' bundle the two values into their own sub- 
stacks before applying the quotation. The implementation and type  
would then be something like this:

   -- assume this:
   stack :: A b -> A (Stack b)
   infra :: A (Stack B) (B -> C) -> A (Stack C)

   -- so we can define this:
   bi@ :: A b b (b -> C) -> A (Stack C) (Stack C)
   bi = [stack [stack] dip] dip dup [infra] dip [infra] dip

The above code already type checks and works in Fifth as expected. As  
you can see though, it's a huge pain in the ass; 'dup dip dip' is much  
nicer. It's also difficult to compile to efficient code.

The version of 'bi@' with type 'a a (a -> b) -> b b' is certainly  
better. This type is quite similar to the type 'bi@' in Haskell:

    bi@ :: (a -> b) -> a -> a -> (b, b)
    bi f x y = (f x, f y)

It may seem limiting to require the quotation be of arity 1->1, but  
the quotation can always create its own sub-stacks or tuples if it  
wants to return multiple values for each use. I think encouraging  
separate computations to be returned in their own bundles rather than  
in one pile on the stack is a good idea anyway. If you do this, you  
can get away with far fewer n-ary combinators.

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

Indeed. See the end of the email I sent in response to Chris right  
before this one talking about the possibility for using something like  
FP's combining forms.

- John