Re: [stack] map fusion

On Fri, Aug 1, 2008 at 4:52 AM, John Nowak <[email protected]> wrote:
> In a functional language, the following optimization is valid
> (assuming F and G are pure functions that terminate):
>
> map G (map F xs) -> map (G . F) xs
>
> This is not only an optimization: It is a law that can be used for
> understanding and proving program properties.
>
> For a concatenative language, we might assume the following rule
> (using Joy's syntax):
>
> [F] map [G] map -> [F G] map
>
> Unfortunately, this is not valid because 'F' and 'G' can access more
> than one value on the stack. Here is a counterexample to the above rule:
>
> 9 [1 2 3] [drop dup] map [[1 -] dip] map -- yields 6 [9 9 9]
> 9 [1 2 3] [drop dup [1 -] dip] map -- yields 6 [9 8 7]
>
> This seems to be yet another argument against n-ary combinators where
> the quotation is not called a fixed number of times. (Combinators that
> call their quotation a fixed number of times like 'dip', 'twice', or
> '@bi' are fine.) The fact that 'map' in a concatenative language is
> still "purely functional" doesn't change the fact that the
> unrestricted stack access complicates things the same way mutable
> local variables do.
>
> It seems the solution is to offer two versions of certain combinators.
> The restricted versions ('map, 'each', etc) will be easier to reason
> about and optimize, while the unrestricted versions ('map*', 'each*',
> etc) will remain useful in a way only possible in stack-based
> languages. I think this would be worthwhile to adopt in both typed and
> untyped languages.

I think I understand. To summarize with Cat type notation:

map : (list ('a -> 'a) -> list)
map* : (list ('A 'b -> 'A 'b) -> list)

In other words, "map" accepts only 1->1 functions, while map* accepts
n->n functions where n >= 1.

FWIW I think this is a very good idea, and I like the notation.

In Cat I simply disallowed "map" and similar combinators from
modifying the stack. It made type analysis easier, it preserved the
fusion properties, and it didn't really cause any huge loss of
expressiveness AFAICT. However: there was definitely some scenarios,
where Joy would be more succinct.

- Christopher

- Christopher