Friday, May 19, 2006

Late and early binding

It's taken me a long time to figure out what people mean when they talk about "late binding" and "early binding." Little by little, I was beginning to get a handle on it, when Brendan showed me this Python spec which used the terms to refer to order of expression evaluation in a syntactic form! According to the spec's terminology, evaluating an expression earlier is ostensibly "early binding." This freaked me out, but Brendan reassured me that this was probably just a misuse of terminology on the part of the Pythonistas.

At any rate, as I understand them, late and early binding describe the point in the lifetime of a computer program (usually, compile-time versus runtime) at which a particular variable reference becomes dereferenced, i.e., at what point its binding is discovered. Lisp, which is dynamically scoped, doesn't dereference function arguments until runtime, based on the dynamic context. Scheme variables, by contrast, can be early bound, since all variables' bindings are based on their lexical scope. Dynamic dispatch is another instance of late binding, where method names are resolved at runtime.

Dynamic scope is generally regarded as a liability, because it completely violates abstractions, exposing programmers' choice of variable names and making them vulnerable to accidental capture. Dynamic dispatch is a somewhat more restricted form of late binding, where the programmer has finer control over what names can be overridden by unknown external parties.

Compiler writers like early binding because it's an opportunity for optimization--variable references can be compiled into direct pointer dereferences rather than map lookups. From the perspective of program design, early binding is good because it results in clearer programs that are easier to reason about. However, in certain restricted forms, late-bound variables can be useful as a way of leaving a program open to subsequent extension. This is the purpose behind dynamic dispatch, as well as implicit parameters such as in MzScheme or Haskell.


Anonymous said...

Kent Pitman's paper on Condition Handling in the Lisp Language Family is quite enlightening.

Oh, not sure whether you meant that but at least in Common Lisp dynamically scoped variables need to be declared as special, and the naming convention *foo* reduces risk of accidental capture more or less completely. ISLISP has a better solution: it has a separate name space for special variables, so it's actually a Lisp-3.

Anonymous said...

I've also found the definition of late-vs-early binding hard to pin down. Is Haskell late bound?

Anonymous said...

Early binding is the same thing as compiler type safety. Late binding is exection time resolution of references, and open to errors.

for instance, in psuedo C# or Java

string s = "hello"

compiles because it's early bound and the compiler can verify it's ok.


int i = 0;

will fail because the reference to i is early bound to Int32. but

int i = 0;
i.GetType().Invoke( "ToUpper", new object[0] );

will comile but fail at run time because the method call is late bound.

I'm so glad I understand something you're talking about enough to actually respond!!

Cale Gibbard said...

In some sense, Haskell is earlier-bound than even most imperative languages are. You can write mutually-recursive value definitions:

evens = 0 : map (+1) odds
odds = map (+1) evens

odds and evens are available in each other's scope.