Re: [stack] improved parallel combinator

John Nowak <[email protected]> wrote:
> William Tanksley, Jr 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.

Are you saying that (| |) is hard to typecheck? And I thought that
spread and cleave were hard.

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

Oh, I know -- cleave doesn't split into multiple stacks, which to me
makes it harder to think about. I admit that what cleave does with
multiple stacks IS useful, but I don't have a conceptual model yet for
it.

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

>    Gatherer: R -> (R++S)  -- ensures it returns 0 or more values

The gatherer was intended to be a lot simpler than that. The type should be:

  Sn-1 -> Sn qn

...where q1 is a typed staticly-sized list or tuple, and the index /n/
varies according to which quotation accepts it. And S0 = R (the
starting stack).

The idea is that the gatherer uses the main stack to build the
starting stack for its quotation, and it returns that starting stack
in the form of a list. It's run once for each quotation.

The quotation, when it runs, will see ONLY the items the gatherer put
onto that list.

Let 'Q' be the type of the stack after the last gatherer has run (in
this case Q = Q2).

>    Quote1:   S -> T
>    Quote2:   S -> U

Hmm.

QuoteN:  Qn -> Tn

...where 'Qn' is the type of the contents of the gatherer's list,
viewed as a stack. (I'm not a typing expert; probably a list is the
wrong structure; if you type tuples, use those instead. The size must
be static.)

>    Combiner: (T -> V) /\ (U -> W)

Yes, this one's a problem. I can hide the problem by keeping the
contents of T and U in tuples when passing them to the combiner, but
I'm not sure if that really solves the problem. It seems consistent...
So here's that:

Combiner:

  Un tn -> Wn

The last combiner, when run, produces W as its result stack (in this
case, W=W2).

>    Final:    R -> (V++W)

Final: R -> W

I think I've eliminated all type concatenation, at the cost of
requiring statically typed n-tuples. (Actually, the sequence of
quotations would be a typed n-tuple -- it certainly couldn't be
dynamically computed.)

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

If tuples were statically internally typed "unstack" would be possible... Right?

Higher orders ... Whew. I need to think about that, but even with what
I said I'm sure you're right.

Keep in mind that I'm very new to static type inference...

> - John

-Wm