=========================================== REDUCERON MEMO 8 Speculative evaluation of primitive redexes during instantiation of function bodies Colin R, 21 November (Revised: minor corrections and a note on deriving # annotations) =========================================== Consider a function such as this one, which performs the safety-checking inner loop in the Queens program: safe :: Int -> Int -> [Int] -> Bool safe x d [] = True safe x d (q:qs) = x /= q && x /= q+d && x /= q-d && safe x (d+1) qs Or in semi-compiled form: safe x d qs = qs True (safe' x d) safe' x d q qs = x /= q && x /= q+d && x /= q-d && safe x (d+1) qs Just look at the body of safe'. All those primitive operations! I haven't worked out the current compiled form of this body, but I imagine it leads to a rather fragmented and therefore slow computation. A Hand-Tracing Analogy ---------------------- Suppose I am tracing the program by hand. Quite early on I need the value of safe 1 1 [2] ==> safe' 1 1 2 [] If am feeling really keen and pedantic, I suppose I *might* just reduce this to the instance of the safe' body with x=1, d=1, q=2 and qs=[]. safe' 1 1 2 [] ==> 1 /= 2 && 1 /= 2+1 && 1 /= 2-1 && safe 1 (1+1) [] But if I am in a hurry to obtain the result, I shall instead take the opportunity to do a bit of speculative evaluation. I reduce the four primitive redexes as I go along, even though I may not yet be able to see which of their results will actually be needed. So this step in my trace becomes instead: safe' 1 1 2 [] ==> True && 1 /= 3 && 1 /= 1 && safe 1 2 [] Now, I could just appeal to the definition of && True && 1 /= 3 && 1 /= 1 && safe 1 2 [] ==> 1 /= 3 && 1 /= 1 && safe 1 2 [] but I might rather take the opportunity to do some more speculative reduction of the primitive redexes. True && 1 /= 3 && 1 /= 1 && safe 1 2 [] ==> True && True && False && safe 1 2 [] And so on. What Might Reduceron Do? ------------------------ The Reduceron compiler could work out, and make explicit, where there is opportunity for speculative primitive reduction. For example, revisiting the "semi-compiled" version of safe', and borrowing the # notation for unboxed values: safe' #x #d #q qs = _A && x /= _B && x /= _C && safe x _D qs where #_A = x /= q #_B = q + d #_C = q - d #_D = d + 1 A # attached to a binding occurrence of an argument means "this argument will be already evaluated to a primitive value". A # attached to a binding occurrence of a local variable means "this primitive value should be computed and substituted at the points of each applied occurrence during instantiation of the body". This kind of speculative reduction of primitive redexes would presumably require an extra clock-cycle or two during instantiation of function bodies to which it is applicable. But it would be worth it. As in the hand trace, a further wave of speculation may be possible using the results of the first wave. safe' #x #d #q qs = _A && _E && _F && safe x _D qs where #_A = x /= q #_B = q + d #_C = q - d #_D = d + 1 #_E = x /= _B #_F = x /= _C However, without specific values available, this is far more speculative. If _A turns out to be False, the second-wave evaluation of _E and _F is a waste of time. Boolean Speculation and Associative Transformation -------------------------------------------------- I am not sure what sort of speculation might be effective for the *semi-strict* Boolean primitives && and ||, when the strict argument (only) is available as a value . One problem is that the size of the result, which must form part of the instantiated body, cannot be determined at compile-time. The result of something like _B && expr is the primitive value False if _B is False, but it is expr (which might be of any size) if _B is True. Associative transformations could help here. For the reason just given, it is awkward to do speculative reduction of && in the safe' body safe' #x #d #q qs = _A && (_E && (_F && safe x _D qs)) because every && application involves a non-strict argument not yet evaluated. But as && is associative, the body could be transformed to maximise opportunities to combine primitive values. safe' #x #d #q qs = ((_A && _E) && _F) && safe x _D qs This kind of associative transformation would also be applicable in the numeric case for chains and combinations of addition and multiplication. Deriving # Annotations on Arguments ----------------------------------- The compiler needs some way of determining which arguments can be # annotated. I think this analysis should be fairly simple. Initially assume *all* integer and boolean arguments can be # annotated, and then do an iterative refinement until a fixed point is reached. Where recursive call sites can sustain # status, but some initial calls from other sites break it, we could user the worker-wrapper idea as in GHC.