===================================================
REDUCERON MEMO 40
Forcing arguments to primitive functions, revisited
Matthew N, 21 October 2009
===================================================

This is an alternative proposal to Memo 38.

Quick recap
-----------

Currently the Reduceron compiler translates primitive applications
by the rule

  p n m     -->     m (n p)                (1)

which forces evaluation of integer arguments n and m before applying
primitive function p.  This is assuming the reduction rule

  i e       -->     e i                    (2)

for any fully evaluated integer i and arbitrary expression e.

Mild generalisation
-------------------

For every binary primitive function p, let us introduce a new
primitive swap:p, a version of p that expects its arguments flipped.

Now translate binary primitive applications by the rule

  p n m          -->     n p m             (3)

and introduce the reduction rules

  i p e          -->     e swap:p i        (4)

  i p j          -->     p i j             (5)

for any fully evaluated integers i and j, unevaluated expression e,
and primitive function p.

Note that the evaluator can actually perform the primitive application
in (5) rather than merely instantiating it.

Symmetry
--------

For symmetry, we can add the rule:

  i swap:p e     -->     e p i             (6)

for evaluated integer i, and unevaluated expression e.

Now transformation rule (3) could just as sensibly be:

  p n m          -->     m swap:p n        (8)

In the interest of efficiency, choice of (3) and (8) could be informed
by compile-time knowledge of whether n or m is expected to be already
evaluated.

Performance
-----------

Consider the number of clock cycles to compute "(+) a b" using the
swap-based approach to force arguments:

  * "(+) a b" is translated to "b (a (+))"
  * Application of rule (2) is required after "b" is evaluated.
  * One unwind is required to fetch argument "a (+)" from heap.
  * Application of rule (2) is required after "a" is evaluated.
  * A primitive reduction is required.
  * That's 4 cycles in total.

Using the approach described in Memo 38:

  * "(+) a b" is translated to "b a (+)"
  * After "b" is evaluated, it must be pushed onto the PV stack.
  * After "a" is evaluated, it must be pushed onto the PV stack.
  * A primitive reduction is required.
  * That's 3 cycles in total.

Using the approach described in this memo:

  * "(+) a b" is translated to "a (+) b"
  * Application of rule (4) is required after "a" is evaluated.
  * Application of rule (5) is required after "b" is evaluated.
  * That's 2 cycles in total.

Also note that "a (+) b" comprises one application whereas "b (a (+))"
comprises two, so the former is cheaper to instantiate.
