Saturday, March 23, 2013

Three Layers of Laziness

In the last post I walked through the CIL disassembly for a simple function.  I discovered that one of my mechanisms intended to implement laziness was really causing more work than was necessary.

As a brief recap, the problem is this:  In a standard programming language, expressions that are parameters to functions are evaluated before being passed to the function, regardless of whether they are ultimately needed within the function.

I was hoping to get around this by passing in a reference to the expression, and only evaluate it if necessary.  However, in my sample function I used one of my parameters three times, and the C# compiler ended up evaluating the expression three times.

This makes perfect sense in the standard programming world, because the function might not return the same value each time.  However, if the function is pure, the expression only needs to be evaluated once.

In the end, I hope I can implement three layers of laziness: 1) Within a function, let each expression be evaluated only if it is needed;  2) If an expression is evaluated, let is only be evaluated once, and let its value be stored in a local variable if it is needed more than once; 3) Let a thunk remember its last evaluated value, and return it directly rather than reevaluating.

Having said that, here is a rough sketch of what the CIL for the AddAndMultiply function should have looked like.  (I'm not 100% certain how to calculate the maxstack value yet...working on that).

.maxstack 7
.locals init (
  int32 V_0,
  int32 V_1)
// Get the value of x
IL_0000:  ldarg.1
IL_0001:  callvirt instance !0 class ToylModel20130322.ISignature`1<int32>::Value()
// Store x in a local variable
IL_0006:  stloc.0
// If x >= 0 then goto IL_0019
IL_0007:  ldloc.0
IL_0008:  ldc.i4.0
IL_0009:  bge IL_0019
// Throw exception
IL_000e:  ldstr "x must not be less than zero"
IL_0013:  newobj instance void class [mscorlib]System.Exception::'.ctor'(string)
IL_0018:  throw
// Get the value of y
IL_0019:  ldarg.2
IL_001a:  callvirt instance !0 class ToylModel20130322.ISignature`1<int32>::Value()
// y is still on the stack, push x back on and add the two together
IL_0021:  ldloc.0
IL_0022:  add
// Push x on the stack again and multiply
IL_0023:  ldloc.0
IL_0024:  mul
// Return the result
IL_0025:  ret

Fig. 12.1: Ideal CIL code
One geeky observation that not many people would make:  The syntax of assembly language is very much like the syntax of Altaic languages--the verb always comes last.

No comments:

Post a Comment