## June 2006 - Posts

I wasn’t sure I was going to report a version of Y using Object rather than explicit recursive types, but it turned out to be so easy and pretty that I couldn’t resist. It’s rather a dead-end, evolutionarily speaking, since future development will use the template of the explicit Universal type presented last time, but it’s amusing enough for a blog entry:

REM (λ a -> z z a)

Class** OfA**

** **Private** Z **As** **Object

** **Sub** **New**(**ByVal** Z **As** **Object**)**

** **Me**.Z = Z**

** **End** **Sub

** **Function** [Of](**ByVal** a **As** **Object**) **As** **Object

** **Return** Z.[Of](Z).[Of](a)**

** **End** **Function

End** **Class

REM [λ z -> h(λ a -> z z a)]

Class** OfZ**

** **Private** H **As** **Object

** **Sub** **New**(**ByVal** H **As** **Object**)**

** **Me**.H = H**

** **End** **Sub

** **Function** [Of](**ByVal** z **As** **Object**) **As** **Object

** **Return** H.[Of](**New** OfA(z))**

** **End** **Function

End** **Class

REM y h = [λ z -> h(λ a -> z z a)] [λ z -> h(λ a -> z z a)]

Class** Y**

** **Function** [Of](**ByVal** h **As** **Object**) **As** **Object

** **Dim** z **As** **New** OfZ(h)**

** **Return** z.[Of](z)**

** **End** **Function

End** **Class

REM λ n -> if n=0 return 1 else return n * fact(n - 1)

Class** OfN**

** **Private** fact **As** **Object

** **Sub** **New**(**ByVal** h **As** **Object**) **REM inflate the closure

** **Me**.fact = h**

** **End** **Sub

** **Function** [Of](**ByVal** N **As** **Object**) **As** **Object

** **If** N < 0 **Then

** **Return** N**

** **End** **If

** **If** N = 0 **Then

** **Return** 1**

** **Else

** **Return** N * fact.[Of](N - 1)**

** **End** **If

** **End** **Function

End** **Class

REM Currying: λ g -> (λ n -> ...). This is our target for y.

Class** f**

** **Function** [Of](**ByVal** fact **As** **Object**) **As** **Object

** **Return** **New** OfN(fact)**

** **End** **Function

End** **Class

Module** Module1**

** **Sub** Main()**

** **Dim** y = **New** Y()**

** **Dim** fact = y.[Of](**New** f)**

** **Dim** result **As** **Object** = 1**

** **While** result > 0**

** Console.Write(**"Enter an Integer Number (negative to stop): "**)**

** result = fact.[Of](Console.ReadLine())**

** Console.WriteLine(**"{0}"**, result)**

** **End** **While

** **End** **Sub

End** **Module

Ok, we have almost everything on hand to write a clean and honest recursion-free factorial in VB, albeit with recursive types. I actually struggled with this for some time, the problem being that we have functions of *Long* to *Long*—call those of type *df*, then functions from *df* to *df*—call those of type *dh*, then functions from *dh* to *df*, and functions from *dh* to *dh*—mmm, ok this situation isn’t converging. If we needed two flashes and one rolling thunderstorm of genius to get this far, it was looking like we might need a cat-3 hurricane of genius to get past it. Fortunately, my colleague, Mark Shields, showed me the way out. I’m not sure I would ever have thought of this myself, but it’s a lovely technique and it’s now added permanently to my bag of tricks. The technique is to model the type system itself—in miniature, of course—with a Universal type *U* that can model either a *Long* or a function from *U* to *U*. Now, all the variety of function types are swept up under one, large, inclusive rug. To model a *Long*, we’ll have a *MustOverride ReadOnly Property* that returns the *Long* value, and to model a function we’ll model function application itself through a *MustOverride* function named *[Of]* that takes a U and returns a U (square brackets let us reuse a keyword for our own purposes, and *Of* is the keyword for generic types, which we’re not using here for simplicity. We could have called the function *appliedTo*, but *[Of]* turns out to be definitely prettier, as we shall see):

MustInherit** **Class** U**

** **MustOverride** **ReadOnly** **Property** V() **As** **Long

** **MustOverride** **Function** [Of](**ByVal** u **As** U) **As** U**

End** **Class

Of course, we COULD use generics, replacing *Long* with a type variable *T*, but that’s a tweak at best. Let’s move on. For the subtype of *U* representing *Long*, we just need *[Of]* to throw:

Class** I**

** **Inherits** U**

** **Private** i0 **As** **Long

** **Sub** **New**(**ByVal** i **As** **Long**)**

** i0 = i**

** **End** **Sub

** **Overrides** **ReadOnly** **Property** V() **As** **Long

** **Get

** **Return** i0**

** **End** **Get

** **End** **Property

** **Overrides** **Function** [Of](**ByVal** x **As** U) **As** U**

** **Throw** **New** ApplicationException( _**

** **"Sorry, can't apply a Long to an argument"**)**

** **End** **Function

End** **Class

The subtype of *U* that represents functions should be *MustInherit* itself, and, of course, should throw on attempted access of the *Long* property, which just doesn’t obtain for functions:

MustInherit** **Class** λ**

** **Inherits** U**

** **Overrides** **ReadOnly** **Property** V() **As** **Long

** **Get

** **Throw** **New** ApplicationException( _**

** **"Sorry, can't get the value of a function"**)**

** **End** **Get

** **End** **Property

End** **Class

Let’s start with the ultimate target for application of the y combinator. We called this *f* in the previous blogs on this theme. This is a function of two arguments, the first of which is the factorial function itself, the second of which is a *Long* number to which to apply *factorial*. Since we’re currying, we represent this as a function of a function that returns a function of a *Long*, represented in-turn by two subclasses of λ, remembering to make closures over free variables:

REM Currying: λ g -> (λ n -> ...). This is our target for y.

Class** f**

** **Inherits** λ**

** **Overrides** **Function** [Of](**ByVal** fact **As** U) **As** U**

** **Return** **New** OfN(fact)**

** **End** **Function

End** **Class

REM λ n -> if n=0 return 1 else return n * fact(n - 1)

Class** OfN**

** **Inherits** λ**

** **Private** fact **As** λ**

** **Sub** **New**(**ByVal** h **As** λ)** REM inflate the closure

** **Me**.fact = h**

** **End** **Sub

** **Overrides** **Function** [Of](**ByVal** N **As** U) **As** U**

** **Dim** i = N.V**

** **If** i = 0 **Then

** **Return** **New** I(1)**

** **Else

** **Return** **New** I(i * fact.[Of](**New** I(i - 1)).V)**

** **End** **If

** **End** **Function

End** **Class

The money line is highlighted. Even though there is lots of machinery laying around, this is almost readable. Ok, now y itself, which we derived last time, with two auxiliary classes with closures, one for each of the lambda forms it uses internally:

REM y h = [λ z -> h(λ a -> z z a)] [λ z -> h(λ a -> z z a)]

Class** Y**

** **Inherits** λ**

** **Overrides** **Function** [Of](**ByVal** h **As** U) **As** U**

** **Dim** z **As** **New** OfZ_hFree(h)**

** **Return** z.[Of](z)**

** **End** **Function

End** **Class

REM [λ z -> h(λ a -> z z a)]

Class** OfZ_hFree**

** **Inherits** λ**

** **Private** H **As** U**

** **Sub** **New**(**ByVal** H **As** U)**

** **Me**.H = H**

** **End** **Sub

** **Overrides** **Function** [Of](**ByVal** z **As** U) **As** U**

** **Return** H.[Of](**New** OfA_zFree(z))**

** **End** **Function

End** **Class

REM (λ a -> z z a)

Class** OfA_zFree**

** **Inherits** λ**

** **Private** Z **As** U**

** **Sub** **New**(**ByVal** Z **As** U)**

** **Me**.Z = Z**

** **End** **Sub

** **Overrides** **Function** [Of](**ByVal** a **As** U) **As** U**

** **Return** Z.[Of](Z).[Of](a)**

** **End** **Function

End** **Class

That’s it! We’re done, and we really just had to read off the mathematics. Wasn’t too hard once Mark showed me the road. By the way, if you change y so that it uses the following, divergent form, you can generate stack-overflows and check that we really do need the one with delayed application:

REM [λ z -> h(z z)] : Loops forever

Class** OfZ_hFree_diverges**

** **Inherits** λ**

** **Private** H **As** U**

** **Sub** **New**(**ByVal** H **As** U)**

** **Me**.H = H**

** **End** **Sub

** **Overrides** **Function** [Of](**ByVal** z **As** U) **As** U**

** **Return** H.[Of](z.[Of](z))**

** **End** **Function

End** **Class

Ok, let’s call it and call it a day:

Module** Module1**

** **Sub** Main()**

** **Dim** y = **New** Y()**

** **Dim** fact = y.[Of](**New** f)**

** **Dim** result = fact.[Of](**New** I(20))**

** Console.WriteLine(**"{0}"**, result.V)**

** Console.Write(**"Press any key to end the program..."**)**

** Console.ReadKey()**

** **End** **Sub

End** **Module

Let’s review the bookends of our so-far successful foray into recursion elimination. The general theme has been *replacement of recursive calls by self-application of functions adhering to recursive types*. (Now, I think we can even eliminate the recursive types, but we still have a way to go before that.) The first, successful recursive type was

** **Delegate** **Function** dg(**ByVal** g **As** dg, **ByVal** n **As** **Long**) **As** **Long

But we didn’t have closures and currying, so we had to keep an ugly argument slot open for the self-applied function. ‘Inventing’ closures and currying led us to invent a pair of function types:

** **Delegate** **Function** df(**ByVal** n **As** **Long**) **As** **Long

** **Delegate** **Function** dh(**ByVal** h **As** dh) **As** df**

Along the way, we gained something, but hardly noticed it, and then we lost it, again hardly noticing it. In this installment, we are going to get it back permanently. But what was it? Remember, at the very beginning, we wanted to write

** **Function** fact(f **As** df, **ByVal** n **As** **Long**) **As** **Long

** **If** n = 0 **Then : Return** 1**

** **Else **: **Return** n * f(n - 1)**

** **End** **If

** **End** **Function

but we were forced to write the following because we couldn’t get the declarations and the types uncoiled:

** **Function** preFac(**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

So, we channeled closures and currying to get rid of the open argument slot for **g**, but lost track of a primary wish: to have the function call in the final position NOT exhibit self application so blatantly. Brings to mind gagging on lukewarm bouillabaisse. While building up closures, we drove right by this little roadside poissonnerie:

** **Function** lambdaF(**ByVal** n **As** **Long**) **As** **Long

** **If** n = 0 **Then** : **Return** 1**

** **Else** : **Return** n * f(n - 1)**

** **End** **If

** **End** **Function

because this was only half of a real closure, of course. While it got the location of **f** right, its value didn’t come from the ambient environment. Instead, it was illicitly loaded at creation time, using secret knowledge, the **AddressOf lambdaF** itself. So, we got the *hiding-of-recursion-through-one-level-of-indirection* we wanted, but at the cost of defining **lambdaF** with reference to its own definition. We were trying to escape exactly that with the whole exercise! So we moved down the road to

** **Delegate** **Function** dh(**ByVal** h **As** dh) **As** df**

** **Private** h **As** dh**

** **Private** **Function** lambdaF(**ByVal** n **As** **Long**) **As** **Long

** **If** n = 0 **Then** : **Return** 1**

** **Else** : **Return** n * h(h)(n - 1)**

** **End** **If

** **End** **Function

** **Public** **Function** lambdaH(**ByVal** adh **As** dh) **As** df**

** **Me**.h = adh**

** **Return** **AddressOf** lambdaF**

** **End** **Function

Now, this new **lambdaF** doesn’t refer to itself in any way. One more level of indirection fixed it: the creator is responsible for loading the value of **h** from the ambient environment, where it can OPTIONALLY refer to **h** itself. The restoration of that option legitimizes the self-application:

** **Function** fact3(**ByVal** n **As** **Long**) **As** **Long

** **Dim** acf3 = **New** cf3**

** **Return** acf3.lambdaH(**AddressOf** acf3.lambdaH)(n)**

** **End** **Function

We made it! A place that fixes bouillabaisse, but, alas, it’s lukewarm again. **LambdaF** is ugly because it must blatantly repeat the self-application trick again, via **h(h)**. At least there is enough curry in the soup to prevent gagging. Or is there?

Notching up the abstraction of the discourse a tiny bit, we keep trying to write something like this

fact = f(f)

and getting our knickers in a twist because **f** has to do something unnatural for **fact. fact** wants to talk about numbers and **f** has to keep talking about *functions*, sometimes functions that take functions as arguments, and sometimes functions that take numbers as arguments. Let’s just back off and suppose we could pass **fact** itself to **f**:

fact = f(fact)

Well, this would do the trick, wouldn’t it? Now, **fact** could just call itself in the final position, legitimately divorced from self-definition, without carrying around the ugly divorce decree in plain sight as blatant self-application of a free variable.

This is a *fixed-point equation*: it says that the **fact** we really want is a fixed point of **f**, meaning, a ‘point’ in the domain of **f** that maps to itself. If we were dealing with ordinary function graphs from school math, like y = f(x), such an idea wouldn’t scare us at all. In fact, for many functions, it’s easy to solve such fixed-point problems. Consider the linear function

y = m x + b

which has the fixed-point solution

y = f(y) = b / (1 – m)

In other words, there is a unique fixed point unless m = 1, in which case either no points are fixed points, if b ≠ 0; or all points are fixed points, if b = 0.

But in our world of functions, we’re definitely feeling queasy. We’ve left the secure, dry land of functions on numbers and are pitching along the rolling seas of functions of functions. But there is much adventure and treasure ahead, even if only a properly cooked bouillabaisse.

We have only **f** to work with. Think, think, think. Ok (flash of genius), we’re already on the high seas of higher-order functions, so, maybe we can imagineer yet-an0ther-function, call it **y**, that can convert **f** into **fact**. We would get the mind-twisting equation:

fact = y(f) = f(y(f)) = f(fact)

Does this have a solution for **y** (we already know what **f** is)? Think, think, think. Ok (flash of genius), maybe self-application could help. Think, think, think. Maybe y(f) equals some other function applied to itself. Ok (rolling thunderstorm of genius), how about:

let g(x) = f(x(x)) *for any x (notice the free variable, *f*)*

let y(f) = g(g)*, which equals* f(g(g)) = f(y(f))

By gum, we’ve got it! A **y** that converts any function **f** into its fixed point, assuming that the fixed point exists. The condition for existence seems to be just that **f** take a function as its first argument, and we can curry off the rest of the arguments. Of course, this is the famous Y combinator and all that genius is borrowed from Haskell Curry himself.

There is one more little thing we must do before we boil this down into concrete realization in VB. If you actually called **y(f)** above, it would call **g(g)**, which would call **f(g(g))**, which would call **g(g)**, and the whole thing would diverge till we get a stack overflow. We must make sure that the **g(g)** in **f(g(g))** is not called *yet*, so we replace the argument of **f** with a function of one variable that applies **g(g)** to that variable. Mathematically, a function of one variable, say **j(a)**, that applies another function to that variable, as in **k(a)**, is just plain equal to that function. In other words **j = k**, so the equations above hold: a function of **a** that applies **g(g)** to **a** is just **g(g)**, so is mathematically equal to **f(g(g))**, just as before (this is η conversion). It just delays the evaluation one step: in the argument-position of **f**, it evaluates to a function that will apply **g(g)** to its argument *later*. So we don’t get a runaway loop unless the underlying function, **f**, has one in it. Here are a bunch of articles on this technique.

The current notation for discussing the mathematical meaning of all this function hacking is very clumsy, however, and gets in the way of understanding, and it will make it REALLY difficult to understand the upcoming VB code. It forces us to name every function, and the whole point of the project-at-large is to avoid naming functions by writing lambdas instead. We’ve got to graduate to the real thing. So here goes:

λ x → Q

Read this as “lambda of x returning Q.” It means *the function of **x** that does (or returns) **Q*, where Q stands for anything that may depend on x and upon other variables. This is *abstraction of **x*. If x were a free variable in Q, then it is bound in λ x → Q (reminder, a free variable is any variable that is not a function argument at any level of nesting in an expression) We can give this function a name as follows:

P = λ x → Q

This associates to the right, so that

Q → R → S = (Q → (R → S))

(if we think about it, it really only can be read that way). Abstraction relates back to the traditional notation as follows:

P(x) = Q

In the lambda notation, we do NOT need to write the parentheses around the function arguments and this is very helpful in more involved expressions. So, the above is the same as this:

P x = Q

This is *function application*, and it associates to the left, so

f g h = ((f g) h) *function **f** applied to **g**, and the result applied to **h*

To evaluate a function (called β reduction), we substitute an actual argument for a variable,

(λ x → Q) R ~> Q[x ← R] *if all free variables in *R* remain free*

Read this as “lambda of x returning Q applied to R becomes Q with R replacing x everywhere.” We can avoid ‘capturing’ free variables in R by just renaming any bound variables in Q that collide with them. See the wiki entry for more.

In the new notation, write the first version of y as

y f = [λ x → f (x x)] [λ x → f (x x)]

Read this as “y of f equals the function of x that returns f applied to x of x, applied to (a copy of) that same function.” Notice that we explicitly overrode the left-associativity in f(x x); we don’t want (f x) x— “f of x applied to x” —which would be the interpretation of just f x x. To evaluate y f, just follow β reduction, replacing x in f(x x) with λx→f(x x), resulting in

f ( [λ x → f (x x)] [λ x → f (x x)] ) = f (y f)

just as required. Doing the η conversion to delay evaluation changes nothing:

y f = [λ x → f (λ a → x x a)] [λ x → f (λ a → x x a)]

because (λ a → x x a) = x x, mathematically.

I’m just warming you up with this notation, because I’m going to put it in the comments when I write the VB version of this, next installment.

Last installment, we found we could write a factorial function with a function call in the recursive branch, but not a recursive call. This ‘nearly recursive’ style allows us to write factorial without using its name. We just *assume* we have a free-variable delegate to some function that performs the rest of the computation. At initialization time, set the delegate to refer to the function itself. Thus, replace recursion with a call through a free variable. Just another level of indirection, as the cliché goes.

We need exactly this technique when we need recursive functions where explicit recursion isn’t allowed, as in lambda expressions.

Well, how about getting rid of the recursive definitions? Why bother with all these gymnastics just to write supposedly elegant functions, when loops and tests will do, eh? Two reasons: many algorithms are very hard to write correctly without recursion, and two, much more importantly, because we **can**. Part of my job is to explore all the implications of our technology. If something is possible, I have to try it. And I get to have fun doing it, too.

There is endless discussion of recursion versus iteration. It’s always possible to transform recursion into tail-recursion, and most compilers automatically convert tail-recursion into iteration. But many algorithms are very difficult, even for experts, to write straight-up correctly in iterative form. Quicksort and merge sort are famous, and binary search is infamous. Just about any graph or tree algorithm is best written recursively. Finally, when coding, it’s usually best to transcribe recursive specifications as recursive programs, notwithstanding notorious counterexamples like Fibonacci.

So, let’s take it as given that programmers need recursion as an intellectual tool for writing correct programs faster, secure in the knowledge that there are many ways to attack problems that might arise. That’s the real justification for studying toy problems like factorial: they represent much larger challenges, but in a small form that promotes full understanding of the principles at play.

Last time, we indulged in imaginary extensions to VB, allowing us to curry a function applied to itself, to create a closure containing the delegate to call in place of the recursion. The closure part is very easy to model in non-imaginary VB. Consider

** **Delegate** **Function** df(**ByVal** n **As** **Long**) **As** **Long

That’s the type needed for a factorial function. Next, define one as something that creates a new instance of **Class cf**, short for **closure of f**, which loads a private instance variable (closure environments are externally invisible) then calls a pseudo-lambda of type **df** in that closure. This is our somewhat clumsy transcription of the imaginary Dim fact = f(f), which presupposes currying. Don’t worry, it will get less clumsy as we go along.

** **

** **Function** fact1(**ByVal** n **As** **Long**) **As** **Long

** **Return** (**New** cf1).lambdaF(n)**

** **End** **Function

** **

** **Class** cf1**

** **REM This is a free variable in lambdaF:

** **Private** adf **As** df**

** **REM The following is our simulation of self-application:

** **Sub** **New**()**

** **Me**.adf = **AddressOf** **Me**.lambdaF**

** **End** **Sub

** **REM Here is the non-recursive version, that calls itself

** **REM indirectly through the delegate stored in the closure:

** **Public** **Function** lambdaF(**ByVal** n **As** **Long**) **As** **Long

** **If** n = 0 **Then** : **Return** 1**

** **Else** : **Return** n * adf(n - 1)**

** **End** **If

** **End** **Function

** **End** **Class

This is pretty easy, and accounts for the idea of a closure, modeling it as an instance of a class that contains bindings for free variables. Of course, the closure here is statically special-cased, but a generalized technique is all-but-obvious:

** **Function** fact2(**ByVal** n **As** **Long**) **As** **Long

** **Return** (**New** cf2).****lambdaF(n)**

** **End** **Function

** **

** **Class** cf2**

** **Private** env **As** **New** Dictionary(**Of** **String**, df)**

** **Sub** **New**()**

** **Me**.env(**"adf"**)**** = **AddressOf** **Me**.lambdaF**

** **End** **Sub

** **Public** **Function** lambdaF(**ByVal** n **As** **Long**) **As** **Long

** **If** n = 0 **Then** : **Return** 1**

** **Else** : **Return** n * **Me**.env.Item(**"adf"**)****(n - 1)**

** **End** **If

** **End** **Function

** **End** **Class

or, even more generally

** **Class** dfFreeVars**

** **Protected **env **As** **New** Dictionary(**Of** **String**, df)**

** **End** **Class

** **Class** cf2**

** **Inherits** dfFreeVars**

** ...**

Let’s say the point is made: we can easily implement environments for free variables, thus we have that part of closures licked. Henceforth, since environments will be very small, let’s not bother with the full generality of dictionary types in superclasses, remembering that we can easily do this when we need the generality.

We still have the vexing problem that we don’t really have lambda, self-application, and currying, just a rather lame simulation for them. Lambda will take us far into high orbit in another installment, but currying and self-application we can fake up right now:

** **Function** fact3(**ByVal** n **As** **Long**) **As** **Long

** **Dim** acf3 = **New** cf3 **REM Make a var so we can self-apply:

** **REM chained calls represent currying

** **Return** acf3.lambdaH(**AddressOf** acf3.lambdaH)(n)**

** **End** **Function

** **Class** cf3**

** **REM This type represents functions that take (delegate)

** **REM functions as their first argument and return (delegate)

** **REM functions of a different type:

** **Delegate** **Function** dh(**ByVal** adh **As** dh) **As** df**

** **REM Here's the free variable we've closed over:

** **Private** adh **As** dh**

** **Private** **Function** lambdaF(**ByVal** n **As** **Long**) **As** **Long

** **If** n = 0 **Then** : **Return** 1**

** **REM Self-application and currying, call-on-call:

** **Else** : **Return** n * adh(adh)(n - 1)**

** **End** **If

** **End** **Function

** **REM The factorial MUST self apply to inflate the closure:

** **Public** **Function** lambdaH(**ByVal** adh **As** dh) **As** df**

** **Me**.adh = adh**

** **REM Ooh, look, mom: a way to break access control!

** **Return** **AddressOf** lambdaF**

** **End** **Function

** **End** **Class

See what’s happened? **Fact3** gins up a closure by self-application of the one public method of **cf3**. That closure returns a (delegate to a) function of a numerical argument, so it’s curried. **Fact3** then just calls the curried function. There is just a tiny bit of excess generality here, as **lambdaH** could be applied to any function of (delegate) type **dh**; it just so happens we always self-apply it, both when **cf3** is instantiated in **fact3**, and internally to **lambdaF**, where external self-application is mimicked internally.

There is much, much more to do over the next few installments. First of all, we don’t really have a full lambda yet. Sure, we can make functions that don’t refer to their names internally, but we still refer to them externally. Second, this is all specialized to factorial, so far: we need to make this recursion-elimination technique work for any recursive function whatever. Third, we’ve just replaced call recursion with type recursion. The stuff above only works because type **dh** can refer to itself. That’s so self-application will work in a static-typing ambience. We could get rid of that through late-binding, and I might show something like that: I haven’t decided yet. But there is another technique.

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.

More Posts