===================================
REDUCERON MEMO 38
Benefits of a primitive-value stack
Matthew N, 14 October 2009
===================================
Currently the Reduceron compiler translates primitive applications
according to 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.
No extra stack is needed to store the evaluated arguments to a
primitive. However, it would be cheap to introduce such a
primitive-value stack into the Reduceron. Then primitive applications
could be translated by the rule
p n m --> m n p (3)
and the reduction rule would now be
i e --> e (4)
with the *side-effect* of pushing i onto the primitive-value stack.
By the time p reaches the top of the evaluation stack, its
fully-evaluated arguments will be avilable on the primitive-value
stack.
The main consequence of this new approach is: expressions are smaller
and shallower. The RHS of rule (1) contains 2 applications and has
depth 2; the RHS of rule (3) contains 1 application and has depth 1.
Smaller and shallower expressions are faster to instantiate and result
in less unwinding during evaluation.
EXAMPLE 1. Consider the following case where a primitive application
itself contains a primitive application.
(+) ((-) a b) ((-) c d)
This could be compiled to reverse polish notation:
d c (-) b a (-) (+)
EXAMPLE 2. More generally, the expression
(+) (f x) (f y)
could be compiled to:
f y f x (+)