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.