Functions to Delay Binding

In the previous article, the discussion of lambda calculus is a bit misleading. We're not using lambda calculus terms as the intermediate representation. We're being inspired by the lambda calculus and aping it as a mechanism for propagating information around in the intermediate representation.

In Python, using the SQLAlchemy, you can construct conditions by using expressions like == 'bob'. The object in is some kind of column type, and it overloads __eq__ in such a way that when you evaluate it against 'bob', rather than returning a boolean truth value, it returns some kind of filter expression object. This is a way of delaying binding: nothing is really computed at this moment, it's just all bound together in preparation for a later evaluation step. In the case of SQLAlchemy, that evaluation is actually going to generate part of an SQL query. This gives the appearance of a bridge between Python and SQL.

What's really happening in a DCG statement like sentence(VP) --> np(NP), vp(NP^VP) is a beautiful confluence of Prolog ideas. Prolog's unification is used not just as pattern matching against the structure of the subterm result from the verb phrase, but also to propagate the value from the noun phrase into the verb phrase. Because unification is more like forming a link than procedurally assigning variables, we can unify things in any order. This is how we get a noun from before the verb and a noun from after the verb to live nicely side-by-side inside a term build by the verb.

We didn't really wind up having to build anything like the lambda calculus, because binding in LC is just like binding in Prolog. In fact, we got a "rename" step "for free" because Prolog variable names are not global.

So where was the lambda calculus? It wasn't in the AST we built, and it wasn't really there in the building of it. The idea of variable abstraction from terms is all we used, and we only used it during the formation of the AST.