============================
REDUCERON MEMO 1
Widening function bodies
Matthew N, 13 November 2008
============================

Take the standard definition of list-reversal using an accumulator.

  data List a = Nil | Cons a (List a)

  rev xs acc =
    case xs of
      Nil -> acc
      Cons x xs -> rev xs (Cons x acc)

The Reduceron compiler turns this definition into the following set of
combinator definitions.

  Nil n c       = n                        (1)
  Cons x xs n c = c x xs                   (2)
  rev  v acc    = v acc (rev' acc)         (3)
  rev' acc x xs = rev xs (Cons x acc)      (4)

The Reduceron can apply any one of these rewrite rules in

  3 + (n `div` 8)

clock-cycles, where n is the number of nodes in the right-hand-side.
One can see that the Reduceron is fast at instantiating large function
bodies --- the bigger the better!

However, function bodies often contain case expressions and, in
general, case expressions cause function bodies to be split up into
small pieces when compiled to combinator expressions.  To be precise,
a new combinator definition is created for each case-alternative whose
pattern is a non-zero-arity constructor.  For example, equation (4)
above captures the second case alternative in the original definition
of rev.

Can we avoid this splitting up, allowing larger functions bodies to
remain?  One way would be to support lambda expressions and to redefine
equation (3) as follows.

  rev v acc  = v acc (\x xs -> rev xs (Cons x acc))

The right-hand-size is definitly bigger, but now there is a new
problem.  How do we instantiate a function-body containing
lambda-bound variables?  When we apply rev, we don't know what to
substitute for x and xs.  We have to build a closure for the lambda
expression, but that corresponds to introducing a new combinator
definition and creating a partial application of that combinator to
the "environment" (in this case "acc").

My tentative conclusion is that inlining case alternatives does not
seem feasible.  But there is an alternative way to widen combinator
bodies.

Widening constructors
---------------------

Let us consider the possibility of a non-empty list containing four
heads (say) as well as just a single head.

  data List a = Nil | Cons a (List a) | Cons4 a a a a (List a)

The rev function must now be adjusted to handle Cons4 constructors.

  rev xs acc =
    case xs of
      Nil -> acc
      Cons x xs -> rev xs (Cons x acc)
      Cons4 x0 x1 x2 x3 xs -> rev xs (Cons4 x3 x2 x1 x0 acc)

Now take a look at the resulting combinators.

  Nil   n c c4                = n
  Cons  x xs n c c4           = c x xs
  Cons4 x0 x1 x2 x3 xs n c c4 = c4 x0 x1 x2 x3 xs
  rev   v acc                 = v acc (rev' acc) (rev'' acc)
  rev'  acc x xs              = rev xs (Cons x acc)
  rev'' acc x0 x1 x2 x3 xs    = rev xs (Cons4 x2 x3 x1 x0 acc)

They are quite a bit larger.  What's more they contain wider
application nodes which the Reduceron can fetch very quickly.

Of course, many questions remain.  Can constructors such as Cons4 be
introduced automatically *and* without breaking laziness?  If not, we
could define a library for "chunked" lists where the chunks are
considered spine-strict --- how well would this work?  Can other
functions, besides reverse, benifit from wider constructors too?
Widening constructors opens the possibility for vector arithmetic ---
can this be usefully exploited?