June 2006 - Posts

Late-Bound Fixed Point

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

Posted Tuesday, June 6, 2006 7:38 AM by brianbec | 1 comment(s)

Filed under: , ,

Finally Factorial Fixed Point

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

 

Posted Monday, June 5, 2006 7:55 AM by brianbec | 1 comment(s)

Filed under: , ,

Rebirth of the Y

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 λxf(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.

 

Posted Sunday, June 4, 2006 9:08 PM by brianbec | 1 comment(s)

Filed under: , ,

Closures without Closures; Currying without Currying

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.

Posted Friday, June 2, 2006 11:12 PM by brianbec | with no comments

Filed under: , ,

Lambdas, Closures, Currying, and All That

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.

Posted Thursday, June 1, 2006 5:04 PM by brianbec | 4 comment(s)

Filed under: , ,

More Posts