========================================================
REDUCERON MEMO 3
Head reduction, arity raising and shared subexpressions
Colin R, 17 November
(Minor revision: mainly the part about non-linear args.)
========================================================

In the simple compiler of the Reduceron prototype case alternatives are
split off as separate functions.  Memo 2, after discussion, concluded
that a useful way to achieve recombination (hence widening) in many
cases is to in-line the case distinguishing function in the recursive
alternatives.  So we have identified originally recursive call sites in
case alternatives as prime candidates for inlining.

Basic Observation and First Example
-----------------------------------

This memo looks at another class of in-lining sites.  Consider the head
applications (ie. the leftmost outermost applications) in each function
body.  Wherever a *named function*, as distinct from an argument variable,
occurs in this position, the application can be reduced. Sometimes,
arity raising must be performed first to make this reduction possible.

For example, consider the list-append function.  After simple compilation
we obtain:

  Cons x xs n c = c x xs

  app xs ys = xs ys (app' ys)
  app' ys x xs' = Cons x (app xs' ys)

Now we in-line app in the recursive alternative:

  app' ys x xs' = Cons x (xs ys (app' ys))

With this definition, once recursion "gets going" computation is mainly
by the directly recursive and not-too-thin app' combinator.  Apart,
that is, from the Cons in the head position.  In order to reduce the
Cons at compile time, we first raise the arity of app'

  app' ys x xs' n c = Cons x (xs ys (app' ys)) n c

then apply the Cons rule:

  app' ys x xs' n c = c x (xs ys (app' ys))

Shared Subexpressions
---------------------

The app function may itself occur in the head position of another
function body.  For example, consider the concat function:

  concat xss = xss Nil concat'
  concat' xs xss' = app xs (concat xss')

In-lining in the recursive alternative:

  concat' xs xss' = app xs (xss' Nil concat')

As app occurs in the head position, and its application is already
saturated, it can be reduced:

  concat' xs xss' = xs (xss' Nil concat') (app' (xss' Nil concat'))

But look what has happened: because the app body is non-linear the
second argument expression has been duplicated.  We know that in any
one application of concat' only one occurrence will be evaluated,
because xs is a projective function.  Even so a repeated subexpression
is undesirable: it makes the body not merely wide but obese.  In addition
to the possible extra cost of instantiation, an obese body takes up more
space in the combinator store and increases pressure on the heap.

In general, when reducing at compile-time an application of a function
with a non-linear body, a local variable definition may need to be
introduced to avoid repeated subexpressions.  The only purpose of such
local definitions is to express a term-graph rather than a term-tree as
the body:

  concat' xs xss' = xs c (app' c)
                    where
                    c = xss' Nil concat'

Another Example
---------------

This time, consider the power-list function.  We shall need as auxiliary
the map function:

  map f xs = xs Nil (map' f)
  map' f x xs' = Cons (f x) (map f xs')

In-lining in the recursive alternative:

  map' f x xs' = Cons (f x) (xs' Nil (map' f))

Arity raising and reducing the head application:

  map' f x xs' n c = c (f x) (xs' Nil (map' f))
          
Now to the power-list function itself:

  pow xs = xs (Cons Nil Nil) pow'
  pow' x xs' = app p (map (Cons x) p)
               where
               p = pow xs'

In-lining in the recursive alternative:

  pow' x xs' = app p (map (Cons x) p)
               where
               p = xs' (Cons Nil Nil) pow'
               
And reducing the head application:

  pow' x xs' = p ys (app' ys)
               where
               p = xs' (Cons Nil Nil) pow'
               ys = map (Cons x) p
               

Other Observations
------------------

If *all* applications of a function are either in the head position or
in recursive calls in alternatives, then all these applications can be
reduced at compile-time and the function definition can be discarded,
saving space in the combinator store.

