Re: [stack] function "adjoinment"?

On Mon, 1 Feb 2010 13:39:26 -0600, Matt Hellige <[email protected]> wrote:

> Yes, this is what I'm suggesting. But I only just thought of it as I
> was reading the original email in this thread, so I'm not really sure
> whether it would be possible and haven't really thought it through,
> let alone tried it. The stack effect system of languages like Cat,
> though, always reminded me of a kind of row polymorphism, so I've had
> the inkling before.

If you make use of the fact that almost all first-order functions have
a fixed arity (e.g. 3 -> 2) except for bizarre functions like 'clear',
you can type things similar to Factor's smart combinators that handle
things like stack concatenation. You just need a tiered approach where
your combinators are not themselves first-class values and only have
first-order functions provided to them. This lets you have types like
the following for function "concatenation":

   fn-cat : (A -> B, C -> D) -> A C -> B D

The only requirement for this to work is that rows are introduced before
(i.e. "to the left of") the point they are used in a concatenation. For
example, instantiating the above function with a function of type
'R int -> R int' and a function of type 'R string int -> R char' would
yield a function of type 'R int string int -> R int char'.

Another example is concatenating first-class stacks; the only requirement
is that two first-order functions need to be supplied -- once for each
stack -- and then you can assemble the appropriate function "magically":

   stack-cat : (A -> B, C -> D) -> R {A} {C} -> R {B++D}

This is all a bit cleaner if first order functions are not lifted to
operate on stacks of >= N size (where N is their input arity), but rather
on stacks of *exactly* N size, aka N-tuples. Doing this eliminates the
need to magically "unlift" functions and make them no longer row
polymorphic. This is the system I briefly describe in that "vis.txt"
document I linked to: http://johnnowak.com/heap/vis.txt

I should note that the flatness of concatenating inputs and outputs, as
opposed to the pairing done in the Arrow for -> in Haskell, lends itself
much better to a visual representation.

- jn

P.S. Emailing very quickly from work. Apologies if the above is unclear
(or worse).