/Home /Archive /Syndicate /Blog /Support /About /Contact  
All Visual Basic Feeds in one place!





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.

© 2005 Serge Baranovsky. All rights reserved.
All feed content is property of original publisher. Designated trademarks and brands are the property of their respective owners.

This site is maintained by SubMain(), a division of vbCity.com, LLC