=================================== REDUCERON MEMO 39 The Force-and-Rebind transformation Matthew N, 20 October 2009 =================================== Consider reduction of the fromTo function with primitive redex speculation (PRS) enabled. fromTo m n = case (<=) m n of { False -> Nil; True -> Cons m (fromTo ((+) m 1) n); }; If fromTo is passed literal integers as arguments, e.g. "fromTo 1 10", then both the comparison and the addition in the body of fromTo will be detected as primitive redexes and reduced on-the-fly. Consequently, the arguments to the recursive call will also be literal integers, and so the comparison and addition will be primitive redexes on every iteration. Now suppose that fromTo is passed unevaluated expressions, e.g. "fromTo (length xs) (length ys)". The first time the comparison is encountered, it will not be detected as a primitive redex, and "length xs" and "length ys" will be forced via the default machinery for dealing with strict primitives. One might hope that by the time the second case alternative is taken, since the values of m and n are then known, the addition will be detected as a primitive redex. However, this is not the case: although m and n are fully evaluated, they are represented as pointers to literal integers on the heap - they are not themselves literal integers. Sadly, on every iteration, no primitive redexes will be detected. It is easy to make fromTo more robust by defining it in a worker-wrapper fashion. fromTo m n = n (m fromToWork); fromToWork m n = case (<=) m n of { False -> Nil; True -> Cons m (fromToWork ((+) m 1) n); }; The wrapper forces evaluation of m and n and then calls the worker. In doing so, m and n are rebound to literal, unboxed values. This can be done because fromToWork is clearly strict in both arguments. Below I outline a transformation - called Force-and-Rebind - for automatically introducing these worker-wrapper style functions. The transformation ------------------ STEP 1. Look for functions of the form f ... = ... case p e1 e2 of { False -> alt1 ; True -> alt2 } ... where p is a primitive function strict in both arguments returning a boolean, and alt1 or alt2 can lead to another call of f. STEP 2. Take all the strictly-needed variables of type integer referred to in e1 or e2 that also referred to in alt1 or alt2. Call them v1..vn. Proceed only if v1..vn is non-empty. STEP 3. Abstract the expression of interest into a function h: f ... = ... h v1..vn w1..wn ... h v1..vn w1..wn = case p e1 e2 of { False -> alt1 ; True -> alt2 }; where w1..wn are the free variables, other than v1..vn, in the case expression. STEP 4. Create function f' like f but which forces evaluation of v1..vn before applying h: f' ... = ... vn (..(v1 h)) w1..wn ... STEP 5. Now calls to f can be replaced by calls to f'. However, as primed functions are meant to be wrappers, only calls to f which occur in a function that is NOT call-reachable from f should be replaced. Results ------- Saving due to Force-and-Rebind transformation: +-------------+------------+ | PROGRAM | % SAVING | +-------------+------------+ | Adjoxo | -1.5 | | Fib | 0 | | OrdList | 0 | | Queens | -7.9 | | Queens2 | 0 | | Cichelli | 12.8 | | KnuthBendix | -2.1 | | Parts | 0 | | SumPuz | 28.6 | | Clausify | -4.1 | | MSS | 0 | | PermSort | -4.7 | | Taut | -5.8 | | CountDown | 22.3 | | Mate | 0.3 | | While | -5.0 | +-------------+------------+ | AVERAGE | 2 | +-------------+------------+