Late Binding of Execution Order (August 1, 2007)

In a statically typed language, you can get by-name parameter passing on a parameter-by-parameter basis. Each parameter is marked as by name or as by value, and the compiler knows what to do with each method invocation because it looks at the static type information. Scala's by name parameters are one example in practice, and LazyJ's lazy types work essentially the same way, only with lazy-binding instead of by-name parameter passing.

Surprisingly, static typing is not necessary to get this selective, parameter-by-parameter behavior! To see this, consider an implementation approach where you always thunk-ize the arguments to method invocations, just in case. Then, when a method invocation actually runs, it does the following:

  1. Evaluate the receiver.
  2. Determine exactly which method that respond.
  3. Look at that method's parameters, and evaluate the parameters that are marked "by value".
  4. Invoke the method, passing values for the by-value parameters and thunks or the by-name parameters.

To see how it works, here is how you would modify lambda calculus. Lambda calculus has functions instead of methods, but the idea works out the same. Recall the standard evaluation rules for lambda calculus: 

(\x.e) v  -->  e[x\v]   
e1 e2  -->  e1 e2'      (assuming e2 --> e2')
e v  -->  e' v          (assuming e --> e')

On top of these, you can add a "by name" lambda expression, \BN x.e, which has the following evaluation rule: 

(\BN x.e1) e2  -->  e1[x\e2]

That is all. Note two differences between this rule and the ones for normal, by-value lambdas. First, you can pass an arbitrary expression into the lambda's body, not just a value -- that's by-name evaluation. Second, there is no recurrence for evaluating the argument. Once it is clear that the callee is a by-name lambda, it can go ahead and be invoked.

The net result is that an application (e1 e2) is evaluated as follows. First, e1 is fully evaluated into either a lambda or a by-name lambda (if it is something else, computation stops). Then, one of two things happens. If e1 is a normal by-value lambda, then e2 is evaluated and then the result is passed into the lambda. If e1 is a by-name lambda, then e2 is immediately passed into the body of that lambda.

The decision is made at run time, and so the same expression might even use a different evaluation order each time it runs. It is late binding of evaluation order.

After thinking about all of this, I am left with two questions:

  1. Is there a fast implementation? Thunking every single parameter looks expensive, but there might be better implementations.
  2. Is there any language feature where you need static typing other than for checking and for speed? I used to say parameter-specific execution order was an example, but now I see that it is not. What is left?

Lex Spoon