Re: [stack] improved parallel combinator

On Jan 7, 2009, at 3:51 PM, William Tanksley, Jr wrote:

> John Nowak <[email protected]> wrote:
>
>> I actually really like this one. No more weird pseudo-vector stuff.
>> Here are the semantics:
>>
>
> Very nice; I like it too, more than spread and its associated
> functions. I presume that it's easier to typecheck?

Spread, cleave, and this are all easy to type check. The combinator I  
proposed before this isn't; it might be doable, but I don't think it's  
worth doing.

> \But it also occurs to me that a general-purpose word is possible: let
> me call it "multistack". The idea is that both (- -) and (| |) split
> data and control flow into multiple stacks, run arbitrary code on
> those stacks, and then combine the results onto the main stack;

Cleave doesn't quite do that:

    (- F , G -)  ==  [ F ] [ G ] bi  ==  [ F ] keep G

In other words, 'G' has access to the result of '[ F ] keep'. This  
might seem like something you could prevent with types, but as I  
posted earlier, it unfortunately isn't unless you restrict 'G' to  
returning a single element or some other exact number (or extend the  
type system just for this purpose). As a result of this, you cannot  
implement 'cleave' with your multistack combinator.

> It therefore seems that the multistack combinator would take three
> arguments: one gatherer quotation, one combiner quotation, and one
> sequence of quotations to be run on the split stack. This seems both
> general and statically determinable.
> ...
> Is it?

Not generally given higher order functions. The type system would need  
the addition of concatenation ('++').  Here are the types involved for  
'multistack' with two quotations in the list:

    Gatherer: R -> (R++S)  -- ensures it returns 0 or more values
    Quote1:   S -> T
    Quote2:   S -> U
    Combiner: (T -> V) /\ (U -> W)
    Final:    R -> (V++W)

It may be possible to add concatenation. My guess is that the  
combination of concatenation and intersection is probably undecidable  
though. Concatenation alone may be undecidable. In either case, I've  
no idea how to do it. I'd have to go back and look at some of the  
things done along these lines with record systems that support record  
concatenation.

Now, if we rule out higher order functions, it's all trivial provided  
the functions are known. There is one exception to this: You couldn't  
support Joy's "unstack" ('R {S} -> S') or any other function that does  
not have the same row variable on both sides. Doing so would again  
require concatenation. You'd also need concatenation if you allowed  
the definition of second order combinators where a function passed in  
is used in multistack.

- John