Condividi tramite

Anonymous Recursion in C#

  • Articolo

Recursion is beautiful and lambdas are the ultimate abstraction.  But how can they be used together?  Lambdas are anonymous functions and recursion requires names.  Let's try to define a lambda that computes the nth fibonacci number.

Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

But this doesn't work.  The compiler will complain about the use of fib in the lambda.

Use of unassigned local variable 'fib'

Eric Lippert has a great blog post on this issue.  The problem is that the right hand side is evaluated before fib is definitely assigned.  In this case, the compiler could potentially deduce (if the language spec allowed it) that fib is not used before it is definitely assigned, but in other cases it might need to be used before fib is assigned.

A quick workaround is to assign the value null to fib and then assign the lambda to fib.  This causes fib to be definitely assigned before it is used.

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Console.WriteLine(fib(6)); // displays 8

In fact, letrec in Scheme does something very similar.

But our C# workaround doesn't really use recursion.  Recursion requires that a function calls itself.  The fib function really just invokes the delegate that the local variable fib references.  It may seem that this is just nit picking about words, but there is a difference.  For example, consider the following code:

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Func<int, int> fibCopy = fib;
Console.WriteLine(fib(6)); // displays 8
Console.WriteLine(fibCopy(6)); // displays 8
fib = n => n * 2;
Console.WriteLine(fib(6)); // displays 12
Console.WriteLine(fibCopy(6)); // displays 18

Huh!?  Notice how the result of calling fib changes and that the result of calling fibCopy differs even from the result of calling fib!  (See if you can figure out why)

We can stop this kind of craziness by passing in the function that will be used for the recursive call.  So the lambda looks the same except that it takes an extra parameter f that is called instead of fib.  When a call to f is made, we need to pass f to itself as the first argument.

(f, n) => n > 1 ? f(f,n - 1) + f(f,n - 2) : n

Unfortunately, not all is done yet.  In order to convert the lambda to a delegate, we need a delegate type.  Although it is clear what type fib should be, it may not be apparent what should be the type of our new delegate.  So let's start with the type of fib, Func<int,int>.  We do know that the return type of the delegate should be the same, so it must be int.  We also know that the second argument's type should be the same which is also int.  As for the type of the first argument, we will be passing in a delegate which will then be called with the same arguments as the delegate we are defining.  But wait!  That is recursion.  We are defining the delegate type in terms of itself.  Therefore, the first parameter will be of the same type that the delegate we are defining is.

delegate int Recursive(Recursive r, int n);

The delegate can be generalized by parameterizing the type of the first argument and the return type.

delegate R Recursive<A,R>(Recursive<A,R> r, A a);

Now we can use the lambda that we defined.

Recursive<int, int> fib = (f, n) => n > 1 ? f(f,n - 1) + f(f,n - 2) : n;
Console.WriteLine(fib(fib,6)); // displays 8

While this is an improvement, neither the lambda nor its application look as nice as the original code.  The fact that the first argument should be the delegate itself seems a little strange.  The lambda can be curried in order to separate the passing of f to f from the mechanics of the fib function.  The innermost lambda will have the same signature as the original fib function.

f => n => n > 1 ? f(f)(n - 1) + f(f)(n - 2) : n

Now that the lambda has been curried, a new definition for the Recursive delegate is required.  It now only takes one argument which is the first argument of the previous definition, but the return type changes.  Recursive returns a function (the effect of currying it) which takes the second parameter of the original definition and returns the original return type.

delegate Func<A,R> Recursive<A,R>(Recursive<A,R> r);

Once the lambda is assigned to a Recursive delegate then we can apply the delegate to itself to get the underlying function.  Furthermore, if we made a copy of the delegate and then changed the original then none of the strange effects that happened early would occur.

Recursive<int, int> fibRec = f => n => n > 1 ? f(f)(n - 1) + f(f)(n - 2) : n;
Func<int, int> fib = fibRec(fibRec);
Console.WriteLine(fib(6)); // displays 8

It is now possible to clean-up the duplicated self-application of f.  We can get rid of it by creating a lambda inside of the fibRec lambda which contains the essential fibonacci definition but which takes an argument that references what function should be called for recursion.  Then, inside of fibRec, we can do the self-application of f.

Recursive<int, int> fibRec = f => n =>
{
Func<Func<int, int>, int, int> g = (h, m) => m > 1 ? h(m - 1) + h(m - 2) : m;
return g(f(f), n);
};
Func<int, int> fib = fibRec(fibRec);
Console.WriteLine(fib(6)); // displays 8

This inner lambda looks very similar to our original lambda which took two parameters.  In fact, it appears that the whole process of construction and self-application that initially happened at the top level is now happening inside of the lambda.  The only difference is that the inner lambda does not pass a reference to itself around.  This has now be abstracted out in the call to g.

We can simplify the fibRec definition by currying the inner lambda.

Recursive<int, int> fibRec = f => n =>
{
Func<Func<int, int>, Func<int, int>> g = h => m => m > 1 ? h(m - 1) + h(m - 2) : m;
return g(f(f))(n);
};
Func<int, int> fib = fibRec(fibRec);
Console.WriteLine(fib(6)); // displays 8

Note that the definition of g does not depend on f or n at all.  Therefore, we can move it outside of the outer lambda.

Func<Func<int, int>, Func<int, int>> g = h => m => m > 1 ? h(m - 1) + h(m - 2) : m;
Recursive<int, int> fibRec = f => n => g(f(f))(n);
Func<int, int> fib = fibRec(fibRec);
Console.WriteLine(fib(6)); // displays 8

Notice in the above code that g now represents our original concept of the fibonacci function while fibRec does all of the handy work to enable anonymous recursion.  The whole process of building of fibRec and then applying it to itself only requires a reference to g.  So let's move the definition of fibRec and fib to a different function named CreateFib.

static Func<int, int> CreateFib(Func<Func<int, int>, Func<int, int>> g)
{
Recursive<A, R> fibRec = f => n => g(f(f))(n);
return fibRec(fibRec);
}

We can now call CreateFib instead of creating fibRec.

Func<Func<int, int>, Func<int, int>> g = h => m => m > 1 ? h(m - 1) + h(m - 2) : m;
Func<int, int> fib =CreateFib(g);
Console.WriteLine(fib(6)); // displays 8

But really our CreateFib function is useful for more than just creating fibonacci functions.  It can create any recursive function which takes one argument.  Parameterizing the types used by CreateFib leads to what is known as the Y fixed-point combinator.

static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
Recursive<A, R> rec = r => a => f(r(r))(a);
return rec(rec);
}

We can now create any recursive lambda of one parameter that we want.

Func<int,int> fib = Y<int,int>(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
Func<int, int> fact = Y<int, int>(f => n => n > 1 ? n * f(n - 1) : 1);
Console.WriteLine(fib(6)); // displays 8
Console.WriteLine(fact(6)); // displays 720

Finally, the goal of anonymous recursion has been reached.

Comments

  • Anonymous
    February 02, 2007
    Awesome Wes.  This is one of the most clear explanations of the y combinator I've seen yet.

  • Anonymous
    February 02, 2007
    I really hope we don't have to deal with this kind of stuff in our day to day coding. It seems rather messy.

  • Anonymous
    February 02, 2007
    I don't think that you will have to deal with this stuff in your day to day coding.  If you wanted to write a recursive lambda then you could just put the Y combinator into your code somewhere and let the recursive lambdas flow.

  • Anonymous
    February 02, 2007
    I was thinking about your comment and although it may seem like some of the intermediate steps were messy, the final product is not messy.  I even feel that it is beautiful. Furthermore, I personally don't even think that the intermediate steps are messy.  Sometimes when we look at code and say this is messy, we really are feeling ill at ease.  Becoming familiar with the lambda calculus and the transformations that are possible will help with that feeling. If you prefer different syntax try the link to the "The Why of Y" which uses Scheme to derive Y. If you still feel it is messy then just don't use it.  Sure it closes some possibilities but like I said previously, it probably won't matter for most people.

  • Anonymous
    February 04, 2007
    Are you doing functional programming tutorial to c# people? :) anyway, i absolutely enjoy it ! thats a lot of fun !!! i hope c# 3.0 will be releases soon ... BTW any plans for including some spec# features, like my favourite "requires" in the contract of the method?

  • Anonymous
    February 05, 2007
    We don't have any plans for including spec# features in C# 3.0.  I do agree that many of spec#'s features are very nice.

  • Anonymous
    February 05, 2007
    Keith Farmer brought it to my attention that there is at least a little confusion about how closures

  • Anonymous
    February 10, 2007
    O Y fixed point combinator είναι ένα από τα ποιο περίεργα και γοητευτικά "αντικείμενα" που έχω συναντήσει

  • Anonymous
    February 11, 2007
    I have to admit that this is intelligent! i become an addict to your blog! the implementation is quite tricky, the usage is quite simple! bravo.

  • Anonymous
    February 14, 2007
    Brilliant ! May I suggest the following alternative for the Y<A,R> function body: Func<A, R> g = null; g = a => f(g)(a); return g; This is twice as fast and doesn't use the Recursive<A,R> delegate which is difficult to grasp for us mere mortal. Are there any drawbacks with this solution ?

  • Anonymous
    February 14, 2007
    TFavier: That is a great question and I'm very glad that you asked it. Your definition of Y is good.  In fact, your definition for the body of Y is very like the definition that I used for the memoized version.  Here is your definition. public static Fun<A,R>Y<A,R>(Fun<Fun<A,R>, Fun<A,R>> f) {  Fun<A,R> g = null;  g = a => f(g)(a);  return g; } Now take a look at MemoizeFix. static Func<A, R> MemoizeFix<A, R>(this Func<Func<A, R>, Func<A, R>> f) {  Func<A, R> g = null;  Func<A, R> h = null;  g = a => f(h)(a);  h = g.Memoize();  return h; } But if I remove the memoization part and extension methods then it becomes... static Func<A, R> Fix<A, R>(Func<Func<A, R>, Func<A, R>> f) {  Func<A, R> h = null;  Func<A, R> g = a => f(h)(a);  h = g;  return h; } But then note that h is really just an alias of sorts for g. static Func<A, R> Fix<A, R>(Func<Func<A, R>, Func<A, R>> f) {  Func<A, R> g = null;  g = a => f(g)(a);  return g; } Voila, it’s the same!  In some sense the original Y definition is more intriguing. static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f) {  Recursive<A, R> rec = r => a => f(r(r))(a);  return rec(rec); } Because it doesn't use the g = null combined with lazy evaluation to reference itself.  Note that g is defined in terms of g whereas in Y rec is not defined in terms of rec.  There is no recursion in the definition of rec, yet when used it allows for recursion.  Wild eh?  To do this the recursion has been moved to the type system.  Recursive is a delegate type is that defined in terms of itself. I hope this answers your question.

  • Anonymous
    February 15, 2007
    The comment has been removed

  • Anonymous
    February 16, 2007
    Yet Another Y Function ! static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f) { Func<A, R> g = null; g = f(a=>g(a)); return g; } This variant is the most efficient I have found without using memoization. The figures are the following to compute fib(36) on my laptop:

  • your original Y definition: 12640 ms
  • definition in my February 14 comment: 6406 ms
  • this definition: 1187 ms The last one is approaching the named recursion example in the beginning of your post (796 ms). Do you have any explanations for such variations ?

  • Anonymous
    February 16, 2007
    TFavier: I like it.  I do have an explanation for the variations. The original Y definition that I gave reapplies f each time the function is invoked (original invocation and recursive invocations) and it also reapplies r to itself. Your first fixed point combinator reapplies f each time the function is invoked (original and recursive). Your second fixed point combinator applies f only once and then just applies g again. So in short, it is and should be much faster.  Good job on finding it. Again, the importance of the original Y definition is that it is possible to use that definition to have recursion in a language or environment that does not have recursion built into it.  So it is of theoretical importance. Using the same techniques that you used to make a more performant Y, we can also make a faster MemoizeFix.    static Func<A, R> MemoizeFix<A, R>(this Func<Func<A, R>, Func<A, R>> f)    {        Func<A, R> g = null;        g = f(a => g(a));        g = g.Memoize();        return g;    }

  • Anonymous
    February 19, 2007
    Welcome to the twenty-first Community Convergence. I'm Charlie Calvert, the C# Community PM, and this

  • Anonymous
    February 20, 2007
    Great post. When I got to the "We can stop this kind of craziness by passing in the function that will be used for the recursive call", I was wondering if you were going to take us to the Y combinator at the end. :-)

  • Anonymous
    February 26, 2007
    Tonight I did some more browsing through the January 2007 CTP version of Visual Studio "Orcas" and stumbled

  • Anonymous
    March 07, 2007
    "Again, the importance of the original Y definition is that it is possible to use that definition to have recursion in a language or environment that does not have recursion built into it." One problem with this assertion is that languages and environments that don't support recursion typically use statically allocated locations for local variables, parameters and return address, meaning that even with the Y combinator, recursion still won't work. A stack of function frames is only needed if recursion is to be supported, and if it isn't, the environment typically wouldn't implement it. I think the Y combinator is useful only as a formalism within lambda calculus to model recursion without requiring binding functions to names. Beyond that, it's just a mathematical artefact.

  • Anonymous
    March 08, 2007
    Barry: Thanks for the comments.  You are right that it isn't a very practical way to include recursion in a language that does not have recursion (just use the stack!). I still stand by my original assertion because it is important as a definition of recursion.  Y defines what and how recursion works without using recursion and for that reason it is important.

  • Anonymous
    March 20, 2007
    As someone unfamiliar with the calculus, currying and such the step by step was very nice. The final result does make my eyes hurt. I understand that learning about Y combinator is important, but I ouwld have liked to start with the more domain-specific naming to keep me following what was really happening. e.g. from my view the end result is as follows DOESN'T WORK: // Nth Fibonacci number function // (gives compile error about reusing fib) Func<int, int> fib =    n => n > 1 ? fib(n - 1) + fib(n - 2) : n; DOES WORK: // Nth Fibanacci number function Func<int,int> fib = MakeRecursive<int,int>(    f =>    n => n > 1 ? f(n - 1) + f(n - 2) : n); And the elaboration is great about how MakeRecursive is really a Y combinator and how adding that f indirection really helps. [from what I gather, the MakeRecursive call can pass the function into itself as a kind of argument] I recognize the 'n =>' part as defining the fibonacci step lambda. The 'f' is presumably going to be the step lambda passed into itself. I consider the whole 'f =>' lambda to be a kind of factory lambda that is passed into MakeRecursive. static Func<Arg, Ret> MakeRecursive<Arg, Ret>(    Func<Func<Arg, Ret>, Func<Arg, Ret>> f) {  Recursive<Arg, Ret> rec =      r =>      a => f(r(r))(a);  return rec(rec); } Now that method implementation still warps my brain but at least I can re-read and hope to understand the steps.  Here I am glad for TFavier's implementation:   Func<Arg, Ret> rec = null;   rec = factory(a => rec(a));   return rec; Is easier to read as the body. I can see how it's returning the recursive form of the stepwise algorithm I wanted to pass in. If the factory I passed in was the 'f => n => ...' then 'a => rec(a)' is the lambda that gets passed in as 'f'. The factory returns the 'n =>' stepwise lambda. Since rec is the recursive fibonacci function itself, 'a => rec(a)' is just saying the int argument to f() gets passed to the fibonacci function itself recursively. Does someone have a friendlier name for 'a'? I'm not arguing with the denoument, your article is very well written. I just stumbled across this page with just a bit of knowledge about C# 3.0 and got lost in the stepwise theory. Guess I need a 'Lambda For Dummies' book.

  • Anonymous
    March 21, 2007
    Good points.  You make a very good argument about naming.  I choose to follow naming closer to what the theorists use than what a practitioner would use and perhaps that was a mistake. The 'a' could be renamed 'argument' or 'parameter'. You are right that the 'f =>' is kind of like a lambda factory but the reason that it is that way is because it is a higher order function.  x => y => ... Lambdas that look like this are always lambda factories at the outer level.  They are a lambda which returns a lambda. The stepwise transformations can be a bit difficult to grok.  If you have trouble following them after reading and playing around with it then it may help to study the three main lambda calculus translations.  alpha conversion  beta reduction  eta conversion http://en.wikipedia.org/wiki/Lambda_calculus#.CE.B7-conversion Thanks and hope that helps.

  • Anonymous
    March 21, 2007
    Those trying to implement Fibonacci or Factorial in lambdas will probably want to read this: http://blogs.msdn.com/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx

  • Anonymous
    March 23, 2007
    I use the CTP of May 2006 and I cannot compile this : Func<int, int> maa = Y<int,int>(f => n => {    if(n<10)        return f(n + 1);    return n; }); However, this works fine : Func<int, int> maa = Y<int,int>(f => n => n<10 ? f(n+1) : n); Is it a bug of the 2006 CTP ? I was also wondering how to to make a void recursive lambda expression. Is it possible ?

  • Anonymous
    March 23, 2007
    maa: You are absolutely right.  That is why we are not shipping the May CTP.  This issue and many many more have been addressed in the actual production code.  Try using the March CTP or Beta 1 (when it comes out).

  • Anonymous
    March 25, 2007
    Thank you. And what about void recursive lambda expressions ? For example, how can I build, with a linq query, an XDocument that have a structure like this : <item>  <item></item>  <item>    <item>      <item></item>      <item>        ...      </item>    </item>  </item> </item> i.e a structure with multiple descendant nodes. I think I should use a void recursive lambda expressions but I don't know how... Could you help me ?

  • Anonymous
    March 26, 2007
    delegate Action<A> RecursiveAction<A>(RecursiveAction<A> r); static Action<A> Y<A>(Func<Action<A>, Action<A>> f) {  RecursiveAction<A> rec = r => a => f(r(r))(a);  return rec(rec); } Of course, you can use the function Fix instead of Y to do this which is more performant.

  • Anonymous
    April 11, 2007
    What about this:        public static Func<TParam, TReturn> Y<TParam, TReturn>(YDelegate<TParam, TReturn> le)        {            var me = default(Func<TParam, TReturn>);            return me = p => le(me)(p);        }

  • Anonymous
    April 12, 2007
    That is the same as:       public static Func<TParam, TReturn> Y<TParam, TReturn>(YDelegate<TParam, TReturn> le)       {           Func<TParam, TReturn> me = null;           return me = p => le(me)(p);       } And so all the same comments apply as the other solutions that use the assignment to null in order to achieve recursion without violating definite assignment.

  • Anonymous
    August 06, 2007
    le(me)(p)... did you miss the point that was made about naming :)

  • Anonymous
    August 09, 2007
    Wes Could you use this to elegantly implement the "Memento" pattern for n-level undo? To clarify, could functional programming like this replace the need to write a struct to track all the fields of your business object? Cheers - Rob

  • Anonymous
    December 26, 2007
    @ Ro LINQ is getting to something like that, with this: var businessObject = from p in Business where p.CompanyName = "Widgets Inc" select new {p.Owner, p.CompanyName, p.Address}; businessObject would now have a collection of anonymous objects containing a Owner, CompanyName, and Address property. I would still say it is better for something like the above example to have the typed out struct or class. Especially with the new syntax allowing for properties to be assigned to on creation. Neat nonetheless, and useful in its place. NOTE: I just wrote that code out, there could be a syntax error somewhere in there but the jist should be right.

  • Anonymous
    April 27, 2008
    can you shoot some tips if there is a way to extend this to much complex situation like quick sort. which takes 3 arguments instead of 1.

  • Anonymous
    May 04, 2008
    I just stumbled into this blog trying to learn more about Lambda and anonymous delegates, it took my attention because it talked about doing recursion which requires a NAME with something which has NO NAME. First I think is wrong to try to do something with something which is not equipped with functionality to do the thing in the first place, but I must agree is rather mind twisting. Anyway I think the first solution with the Y operator is kind of BULKY I think the second or third definition was much cleaner and simpler to grasp. The original problem as I understood was that if you self reference f() you ended up with possible bogus code the FibCopy which I ran did indeed return 18,I stopped and debugged and saw what was happening like you guys said the FibCopy was still pointing to the Anno_0000() method which itself reference the Fib which was no longer Anno_0000() but instead Anno_0001() therefore it was calculating partially using one Method and then using the result and calculating the rest using the new method. This was Very disturbing a lot of people would have gone that way. Anyway what I got from the whole blog was this, the problem was to remove the SELF reference of f() using some g() Created dynamically in the Y() Fixed Point function. So If I understand correctly is something like this            f => n=> {the logic of your one parameter recursive function} by calling Y(f) and creating a g() using f() we wind up with something like          g => n { the logic of your one parameter recursive function }  when you called the            g = a => f(g)(a) you return this new anonymous function which is based on the logic of  f() and recourses back to itself to g() so we have    g => n {same logic using g() instead of f()} and we can call g(6) or whatever. is this behavious why you call it FIXED because you FIXED the Logic in f() using g()? The solution was to replace f() with some dynamically created g() which references itself? So that the g() would not change like the f() was when you reassign it? DO I got this correct or still haven’t understood? I guess I have to find a good book on lambda and lamda-calulus, if anyone knows of a Good one please drop me an email at arapallodaily@bellsouth.net I know must of the time as a commercial programmer I have been for 15 years I would never have to do something like that, would do it the same way I have been doing it for the past 15 years That is using normal recursion with NAMED methods but I am just curious. I guess this has lots to do with Language Theory but I honestly took LISP back in the 1980s and don’t remember much. I mainly program in c# and t-sql. I guess the original Y() was done like that for the sake of explaining the PATH to it. Also what is Currier the Lambda? I mean I know you splitted the (x,y) into two Lambda x => y=> but what is it mean? What is the rule? thanks