Behind the scenes, I’m working on the lambda-execution mode for the IQ97. I’m hoping for a few tweaks to VB and LINQ before I can do this satisfactorily, but I can take the opportunity now—with the current CTP—to illustrate the general technique of defining functions with lambda and what I hope it might look like in VB some time down the road. This exercise raises a number of interesting technical issues: in particular, closures—environments for free variables, and currying—values of functions when only some of their arguments are supplied. We explore these rather fully in this installment.
Suppose you had a function, call it
Function fact(ByVal n As Long) As Long
that would compute the factorial of any integer, n, at least up to the limits of the Long data type. This would be fairly easy to define as follows:
Function fact(ByVal n As Long) As Long
If n = 0 Then
Return 1
Else
Return n * fact(n - 1)
End If
End Function
This would be fine for many purposes, but it only works because the function has a name, namely fact. Suppose fact didn’t have a name, or had another name, or your language didn’t allow recursive calls, or you simply refused to call fact inside the body of fact. The scenario where fact doesn’t have a name at all is the lambda-expression scenario, which LINQ uses internally. The other scenarios are easier to understand, so let’s start with them. Just refuse to call fact recursively, now what do we do? Let fact take another argument, which is a delegate function that (refers to a function that) computes the factorial, and write
Delegate Function dg(ByVal n As Long) As Long
Function fact(g As dg, ByVal n As Long) As Long
If n = 0 Then
Return 1
Else
Return n * g(n - 1)
End If
End Function
But fact was supposed to be our function that computes the factorial, so try to call it as follows:
Dim x = fact(AddressOf fact, 6L)
and get a type error: the first argument of fact must be a function of one argument, and we are trying to pass fact itself in that argument slot, and fact is a function of two arguments. How can we escape this problem? Well, there is an easy answer, and that is to make the first argument of fact be a function of two arguments, exactly of the signature of fact itself, as follows (after juggling names a little bit):
Delegate Function dg(ByVal adg As dg, ByVal n As Long) As Long
Function f(ByVal g As dg, ByVal n As Long) As Long
If n = 0 Then
Return 1
Else
Return n * g(g, n - 1)
End If
End Function
Function fact(ByVal n As Long) As Long
Return f(AddressOf f, n)
End Function
If you like this answer, then we’re done and have a nice day. But, really, this is just the beginning and there are some lovely treats ahead.
There is something ugly about carrying around g just so it can be applied to itself over and over again in the pseudo-recursive call. Since it’s always g in that slot, except for the very first call, where it’s f, isn’t it a bit excessive to pass it around as an argument? We could lift g out and make it a top-level (module-level) variable:
Dim g As dg = AddressOf f
but I would hope that you would recoil in horror at such a solution. First of all, we would like it to be a constant—it never varies—and VB won’t allow that:
Const g As dg = AddressOf f REM XXXX Not Allowed !!!!
For the same reason, we can’t reverse the argument list and make g an optional argument, because a constant is required:
Function f(ByVal n As Long, Optional ByVal g As dg = AddressOf f)
REM XXXX Not Allowed !!!!
No function but f needs to access g, and it’s programming-style anathema to lift arguments far out of the scope where they’re needed. You should be ashamed of yourself for even thinking it.
Let’s change fonts as we go into magical wishful-thinking land. First, let’s imagine that our programming language allowed us to apply f to its first argument once and for all, but NOT apply it to its second long integer argument, getting a delegate to a NEW function that takes the integer:
Delegate Function dg(ByVal adg As dg, ByVal n As Long) As Long
Delegate Function df(ByVal n As Long) As Long
Function f(ByVal g As dg, ByVal n As Long) As Long
...
Dim fact As df = f(f)
This is called currying. To be a bit more precise about it, currying is a language feature (or just a theoretical construct) that allows you to call a function one argument at a time, left-to-right down the argument list. Each call returns a new function that takes the remainder of the arguments until you’re left with a function of one argument. Its utility is not just to pretty up scenarios like this, but also to support a simple theoretical calculus of programming, in which every function is, at heart, just a function of one argument, albeit one that may return other functions. In this calculus, a function of many variables—a multiary function—is modeled as a chain of unary functions. Of course, the calculus is the lambda calculus.
So, by currying, f(f) returns a new function of n As Long, which matches the delegate type df. We don’t say AddressOf in our fantasy code, because this new function is not represented in the source code. We just assume that our imaginary currying support will produce a delegate instance for us. From this point on, we can call the fantasy fact with a single argument, the number whose factorial we desire. Let’s try to write out what f(f) ought to be, still in our fantasy language:
Function (ByVal n As Long) As Long
If n = 0 Then
Return 1
Else
Return n * g(g, n - 1)
End If
End Function
We have two problems here: one easy and one hard. The easy one, first: the function has no name. It’s not f, because that function takes two arguments. It’s not even an overload of f, because we didn’t actually write it down: we calculated this function by calling f on f. The compiler might create a name for it internally, but we can’t access that name. The syntax above is perfectly reasonable for defining a function with no name. Alternatives might be:
Lambda (ByVal n As Long) As Long
...
(ByVal n As Long) As Long
...
Now the hard problem: g is not visibly defined anywhere—it’s not a local variable, and it’s not a function argument—but we know what it is: it’s f itself, or, more precisely, an instance of delegate type matching the signature of f. Such things—variables whose definitions are not locally obvious—are called free variables. We talked about them before, heaping shame upon anathema for thinking about putting them in some visible scope.
So, the lambda expression above actually includes an invisible environment in which the location of g is stored when the function is defined and from which the value of g can be looked up when the function is called. This pair of a lambda and an environment for free variables is called a closure. It’s important to store the location of g when the lambda function is defined, this is called static binding or lexical scoping. The alternative, in which the location of g is stored at call time, is called dynamic binding or dynamic scoping. While a completely legitimate style, it is no longer favored because it leads to potentially surprising behavior when the particular g depends on what function actually called the lambda containing the free variables. Call f from one place, get one g; call f from another place, get a potentially different g.
Amazingly enough, we can leave the realm of fantasy and actually model currying, closures, and lambdas in the current VB, but it’s non trivial. Let’s leave that for the next installment.