==========================
REDUCERON MEMO 44
An objective look at PRS
Matthew N, 2 December 2009
==========================

In the Reduceron, an integer can be represented as a literal value
(unboxed) or as pointer to a literal value (boxed).  As discussed in
Memo 39, the boxed form prevents sucessfull PRS.  A possible
workaround is to introduce recursive function wrappers which force
strict integer arguments to their unboxed forms, allowing worker
functions to enjoy successfull PRS.  This memo looks objectively at
PRS, and considers the possibility of using the results of strictness
analysis in a machine *without* PRS.

CPS-based primitives
--------------------

For every primitive function (+) which takes two integers and produces
an integer, we introduce a CPS version (+') which additionally takes a
continuation that is passed the result of the function.  For example,

  (+') 1 2 k

would be reduced to

  k 3.

Example 1
---------

One of the programs on which PRS has a large impact is MSS.  MSS
contains the following function.

  sum xs = sumAcc 0 xs;

  sumAcc acc Nil = acc;
  sumAcc acc (Cons x xs) = sumAcc ((+) x acc) xs;

By observing that sumAcc is strict in acc, we can avoid instantiating
"(+) x acc" on the heap by transforming sumAcc to:

  sumAcc acc Nil = acc;
  sumAcc acc (Cons x xs) = (+') x acc sumAcc xs;

The end result appears to be a version of sum that performs as well
without PRS as it does with PRS.  However, the recursive call to
sumAcc can no longer be inlined, making it more costly than the PRS
version.

Example 2
---------

Another function used in the MSS program is:

  fromTo n m = case (<=) n m of {
                 True -> Cons n (fromTo ((+) n 1) m);
                 False -> Nil;
               };

A strictness analyser can easily spot that fromTo is strict in both
arguments.  We could therefore avoid instantiation of "(+) n 1" on the
heap by evaluating it before the recursive call to fromTo.  This could
be achieved by transforming fromTo to

  fromTo n m = case (<=) n m of {
                 True -> Cons n ((+') n 1 fromTo m);
                 False -> Nil;
               };

The end result is a version of fromTo that seems to perform as well
without PRS as it does with PRS.  However, once again the recursive
call to fromTo cannot be inlined.  Furthermore, notice that the 2nd
argument to Cons is a 5-node application which may have to be split in
two.

Closing thought
---------------

A robust PRS implementation seems to require strictness information.
Such information is useful in a Reduceron implementation without PRS,
however the PRS mechanism still brings some benifits.