Recursive lambda expressions



This is a very geeky post. The tiny piece of useful information comes right at the bottom. The rest of it is all artifacts of the obscure art of doing lambda calculus in C#, which can also be characterized as doing very much with very little, sacrificing only readability.


People sometimes complain that you cannot write a lambda expression that is recursive. Good old factorial, for instance, how to write that as a lambda expression? Well the fathers of lambda calculus, who invented the lambda expressions in the 1930’s struggled with that, too, and as you might have guessed they came up with a solution.


In this post let us stand on the shoulders of those giants and see how you can get recursion into your own lambda expressions in C#. It may not be practical but it is fun!


How to write factorial


So what you really want is to be able to write the lambda expression:


x => x == 0 ? 1 : x * fac(x-1)


But that won’t work – we’re using fac to define fac, but we haven’t defined it yet! Usually when you want to use something you don’t know, you abstract over it at let someone pass it to you later. So we could abstract over the factorial function itself and write:


fac => x => x == 0 ? 1 : x * fac(x-1)


Now what we are saying is, if someone could please hand us the fac function, then we can tell them what the fac function should do, in terms of itself.


At the face of it that seems immediately useless; but in fact it is not; we just need to find a way to “wire the function back to itself”.


Fixed points


Some functions on a domain have one or more fixed points. A fixed point for a function f is a value x such that f(x) = x. For instance a fixed point of the function MultiplyByTwo is 0 because MultiplyByTwo(0) = 0.


Our lambda above is also a function on a domain; i.e., one that maps from a type to the same type. The type of it is


Func<Func<int,int>,Func<int,int>> F =


       fac => x => x == 0 ? 1 : x * fac(x-1)


In other words it maps from Func<int,int> to Func<int,int>. If we could find a fixed point for F, that would be the factorial function! Why? Because, by the definition of fixed points, that fixed point, let us optimistically call it Factorial would satisfy that F(Factorial) = Factorial. Which for any input x would mean that


Factorial(x)


= F(Factorial)(x)


= x == 0 ? 1 : x * Factorial(x-1).


This is the very definition of what it means to be the factorial function!


Finding fixed points for functions can be very hard. Finding fixed points for functions over functions however, is known territory, and in fact guys such as Church, Curry and Turing, who all dabbled in the lambda calculus back in the 1930’s and 40’s came up with nice ways of doing it automatically.


Self replication through self application


To see how we can get something recursive going using just lambda expression, let us look at the simplest form of self application. Imagine that we have a function that takes a function and applies it to itself, like this:


f => f(f)


First let us see how we can type this in C#. This is one of the few odd lambda expressions that you can’t really give a Func<…> type. Try it and see why. Instead let’s define a special delegate type for self-applicable functions:


delegate T SelfApplicable<T>(SelfApplicable<T> self);


 


We can now define the self application function above like this:


SelfApplicable<int> omega = f => f(f);


What happens if we apply omega to itself?


omega(omega);


well omega applies omega to itself, which will apply omega to itself, which will … infinite recursion. While not particularly useful in this setting, the example demonstrates that you can in fact have recursive application in a lambda expression. Now all we have to do is to make it do something useful as it goes, such as call functions recursively.


Y combinators


What both Curry and Turing came up with was ways to write a lambda expression that has the same self-replicating structure as omega, but which additionally replicates something else – the application of a given function.


For some reason the things they came up with are often called Y combinators. Just take that as a curious fact or look up the history yourself. The contract for a Y combinator is roughly this: “Give me myself and a higher order function f, and I’ll return to you a function that is a fixed point of f.” So:


SelfApplicable<Func<Func<Func<int,int>,Func<int,int>>,Func<int,int>>>


  Y = y => f => …;


If we can write the body of Y so that it fulfills the contract, that means that Y(Y) is actually a fixed point finder: Give it a higher order function and it returns a fixed point. For instance, use it on the factorial-related higher-order function F from above, Y(Y)(F), and you get – the factorial function!


But that is the case also inside the body of Y. Because the parameter (lower-case) y represents Y itself, y(y) is also a fixed point finder, which we can then apply inside the body. In particular, inside the body we can use it to take the fixed point of the second argument, f! Can we then just return y(y)(f) as the result?


SelfApplicable<Func<Func<Func<int,int>,Func<int,int>>,Func<int,int>>>


  Y = y => f => y(y)(f);// Not good


Not so fast. That would have us go around in circles forever, not making any progress. We’d never actually use f for anything. But we can recursively apply y(y)(f) to effect the next level of the recursion inside the body of Y. More specifically, remember that f is a higher order function that expects to be passed the fixed point. So let’s pass y(y)(f) – the fixed point – to f itself:


SelfApplicable<Func<Func<Func<int,int>,Func<int,int>>,Func<int,int>>>


  Y = y => f => f(y(y)(f));// Still not quite good


This would actually work if we were in a lazy language such as Haskell. However, in an eager call-by-value language like C#, it would go off and immediately try to compute an infinitely deep factorial function where the recursion is endlessly unfolded. So you never get to actually apply it because you have to wait forever first.


Instead, the right thing to do is to do the unfolding gradually as the arguments to the resulting function are passed. We can do it like this:


SelfApplicable<Func<Func<int,int>,Func<int,int>>, Func<int,int>> Y =


  y => f => x => f(y(y)(f))(x);// Quite good indeed


In this way we defer the recursive call of y(y)(f) until someone has actually called the resulting function – e.g., factorial – with a value. This turns out to work nicely.


Putting it together


We can now go ahead and define a fixed point finder (or rather builder) function Fix as simply:


Func<Func<Func<int,int>,Func<int,int>>,Func<int,int>> Fix = Y(Y);


And finally we can get our factorial function by writing


Func<int,int> factorial = Fix(F);


Or if you want to write it out:


Func<int,int> factorial = Fix(fac => x => x == 0 ? 1 : x * fac(x-1));


The whole code looks like this:


public class Program


{


  delegate T SelfApplicable<T>(SelfApplicable<T> self);


 


  static void Main(string[] args)


  {


     // The Y combinator


     SelfApplicable<


       Func<Func<Func<int,int>,Func<int,int>>,Func<int,int>>


     > Y = y => f => x => f(y(y)(f))(x);


 


     // The fixed point generator


     Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>> Fix =


       Y(Y);


 


     // The higher order function describing factorial


     Func<Func<int,int>,Func<int,int>> F =


       fac => x => x == 0 ? 1 : x * fac(x-1);


 


     // The factorial function itself


     Func<int,int> factorial = Fix(F);


 


     for (int i = 0; i < 12; i++) {


       Console.WriteLine(factorial(i));


     }


  }


}


So how does this work again?


It is instructive to look at function evaluation as a gradual in-place replacement of terms with what they evaluate to. In fact that is how the semantics of the lambda calculus are typically described. So let’s go ahead and “execute” the program ourselves, to observe how the recursion comes about.


First, Y is a lambda expression, so there’s nothing to execute (well in C# a delegate is generated and stored, but that’s it).


Y = y => f => x => f(y(y)(f))(x)


Next, what happens when we build the Fix function? Let’s evaluate:


Fix = Y(Y) = f => x => f(Y(Y)(f))(x)


The higher order function F is again a lambda so nothing to evaluate:


          F = fac => x => x == 0 ? 1 : x * fac(x-1)


In the following we will allow ourselves to use the local variable names above as abbreviations of the functions themselves. Now we are ready to build our factorial function:


          factorial = Fix(F) = x => F(Y(Y)(F))(x)


Now let’s apply factorial to a value:


          factorial(5)
                   =
F(Y(Y)(F))(5)
                   =
(x => x == 0 ? 1 : x * Y(Y)(F)(x-1))(5)
                   =
5 == 0 ? 1 : 5 * Y(Y)(F)(5 – 1)
                   = 5 * Y(Y)(F)(4)
                   = 5 * (y => f => x => f(y(y)(f))(x))(Y)(F)(4))
           
= 5 * F(Y(Y)(F))(4)


See how the recursion occurs? The third-to-last line is equivalent to 5 * Fix(F)(4). So we take the fixed point of F once again, so that the last line is equivalent to 5 * factorial(4)! The factorial function has completed its self replication and is ready to party on the next argument. Of course it will go around and around from here, and all we need to see is how it ends. At some point we’ll get to:


          5 * 4 * 3 * 2 * 1 * F(Y(Y)(F))(0)
                   = 5 * 4 * 3 * 2 * 1 * (x => x == 0 ? 1 : x * Y(Y)(F)(x-1))(0)
                   = 5 * 4 * 3 * 2 * 1 * 0 == 0 ? 1 : 0 * Y(Y)(F)(0 – 1)
                   = 5 * 4 * 3 * 2 * 1 * 1
                   = 120


Magic! We’re done.


Recursive lambdas


Now you may argue that the definition above of factorial isn’t actually a lambda expression, and besides it was created using all sorts of helper functions. But look at the step above where we compute what factorial really “is”. This step is interesting because it shows how a recursive function such as factorial can be written directly as a pure lambda expression without any other predefined scaffolding than a few predefined types: Substitute the actual lambdas designated by Y and F directly in there (surrounded by a few explicit delegate creation expressions when the compiler can’t figure them out, and a renaming of x to i to avoid name collisions) and you have a fully self-contained recursive function directly described as a lambda. Admitted it ain’t pretty:


i => new Func<Func<int,int>,Func<int,int>>(fac => x => x == 0 ? 1 : x * fac(x – 1))(new SelfApplicable<Func<Func<Func<int,int>,Func<int,int>>,Func<int,int>>>(y => f => x => f(y(y)(f))(x))(y => f => x => f(y(y)(f))(x))(fac => x => x == 0 ? 1 : x * fac(x – 1)))(i)


Neat, huh? I can’t even figure out how to line break it so that it approaches readable, so I haven’t. But! It is proof of concept that you can write real recursive lambda expressions if you really really want to! This means you can do it in expression trees, too, although I wouldn’t really recommend it.


So the next time you hear someone complain that you can’t write a recursive lambda expression, just throw them a fixed point generator!


Enough already


Of course you would like to generalize so Y and Fix don’t only work on functions over int. You can’t have generic lambdas, so what do you do? A trick is to put Y and Fix as static members of a generic class:


public class Fun<T> {


  public static … Y = … ;


  public static … Fix = Y(Y);


}


Then you can access the fixed point operator for int functions as Fun<int>.Fix.


For practical purposes, you can also choose to write your fixed point generator as an ordinary named generic recursive method, which is much easier and works just as well:


Func<T, T> Fix<T>(Func<Func<T,T>, Func<T,T>> F) {


  return t => F(Fix(F))(t);


}


Then you also don’t need the intermediate Y combinator and the freak SelfApplicable delegate type.


Regardless of how you write your fixed point generator, it is a useful thing whenever you want to pass a recursive function that you cook up on the fly.


If you want to play some more with this stuff, I recommend the following two exercises:


1)    Make a fixed point generator for functions of two arguments


2)    Figure out how to make two mutually recursive functions in this way


Anyway, enough lambda calculus for one day. Now get back to work!

kick it on DotNetKicks.com


Comments (38)

  1. Senior .NET Developer says:

    My head hurts. I think I’ll go become a manager.

  2. I love this stuff. More of the same please!

  3. j marlowe says:

    awesome.

    and all this included in language that can actually pay the mortgage.

    3.5 cannot be released fast enough!

    how do you plan to deal with the inevitable problem of unifying the existing bcl apis with the more functional-style possible in 3.5 and beyond?  extension methods only go so far in this regard.  how will you avoid a "split" into apis that prefer a functional-style and those that do not?

  4. I’ve met both the author (Mads T), and Luca in person. This post is not an impersonal, anonymous attack.

  5. David Travis says:

    Hmmm… It is good know we can do it. But why not stick with the good old methods we know to implement recursions? The readability trade-off here is huge.

    Either way, thank you for the thorough explanation.

  6. You’ve been kicked (a good thing) – Trackback from DotNetKicks.com

  7. Welcome to the 27th Community Convergence. I use this column to keep you informed of events in the C#

  8. Why don’t you do this?

    Func<int, int> fac  = null;

    fac = x => x– * (x == 0 ? 1 : fac(x));

  9. Sorry, I had bad read your post :-(

  10. I feel it very neccessary at this point to warn you that this is most certainly not for the faint hearted

  11. Beyond words …. but thx for the entertaining read! 😀

  12. Fduch says:

    How about this?

    I’ve never siin so complicated brain****ing stuff so I may be wrong:

    delegate int SelfApplicableInt<Tvoid>(SelfApplicableInt<Tvoid> self, int x);

    SelfApplicableInt<int> F = (fac, x) => x == 0 ? 1 : x * fac(fac, x – 1);

    Func<int, int> factorial = (x) => F1(F1, x);

    var z = factorial2(8);

  13. Fduch says:

    spelling errors…

    delegate int SelfApplicableInt<Tvoid>(SelfApplicableInt<Tvoid> self, int x);

    SelfApplicableInt<int> F = (fac, x) => x == 0 ? 1 : x * fac(fac, x – 1);

    Func<int, int> factorial = (x) => F(F, x);

    var z = factorial(8);

  14. Jeff Lebowski says:

    This is worse than regular expressions… but almost as entertaining.  Thanks!

  15. Not too long ago I blogged about a C# raytracer which took advantage of a lot of C#3.0 language constructs.

  16. Fan Shi says:

    Actually, VB can define a pure lambda founded Y combinator, no neeed to define any helper types.

    Dim Y1 = Function(f) _

    (Function(h) Function(x) f.Invoke(h.Invoke(h)).Invoke(x)) _

    (Function(h) Function(x) f.Invoke(h.Invoke(h)).Invoke(x))

    It is a late binding version. Typed version is also be able to created.

  17. Reading Mads Torgersen old blog post on Recursive Lambda Expressions , I decided it was time for me to

  18. .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New",

  19. WikiPedia:��ư�� sumii������ – ��ư���黻�Ҥդ����� �٥���ӥ͡����äƲ��˻Ȥ��Ρ� – sumii������ ���͸��� Lazy ���롣�ֳ��ԡ�Y����ӥ͡����� – ���쥲���� SICP 1.3.3 Procedures as General Methods:Finding fixed points of functions Fixed point combinato…

  20. GrabBag says:

    This post was originally published here . I saw a couple of posts on recursive lambda expressions , and

  21. gugoxx (giuseppe.ugo@integres.it) says:

    I can’t really understand why the following wouldn’t be considered enough for the solution.

    Func<int, int> fac = null;

    fac = x => (x == 0) ? 1 : x * fac(x – 1);

    Isn’t enough for declaring that it’s recursive?

  22. MattManela says:

    Yes, but then you are no longer dealing with lambda expression in the mathamtical sense.  In lambda calculus there is no concept of storing the expression in a ‘variable’.  Thus a function has no way to refer to itself.  This fact leads to the need for a fixpoint combinator to create recursion in a more round-a-bout way.

  23. PeteS says:

    Aside from LINQ is there any use for lambda expressions in C#? I mean it seems great academic fun, but if that’s the idea why not use LISP or ML and such? Since C# is supposed to be a real world language one wonders what’s this stuff doing there.

    Other than that it IS fun! :)

  24. David Conrad says:

    I know this is a very old post, but I hope you’ll see this. I tried to "put Y and Fix as static members of a generic class", as you said, but got errors I couldn’t understand. I assume I still need the SelfApplicable delegate, and I need to put it inside the Fun<T> class? This is what I tried, but it’s wrong:

    public class Fun<T> {

       public delegate Q SelfApplicable<Q>(SelfApplicable<Q> self);

       // The Y combinator

       public static SelfApplicable<Func<Func<T,T>,T>> Y =

           y => f => x => f(y(y)(f))(x);

       // The fixed point generator

       public static Func<Func<T, T>, T> Fix = Y(Y);

    }

    Can you expand on the ellipses that you used at that point in your post?

  25. You have to love a hotel where you have the amazing Lavazza coffee in your hotel room. CLR/Silverlight/Orcas/C# One of the things that has been a bit fustrating over the years with the CLR is the limitation of one CLR per process. Specifically, where

  26. Note : This entry was originally posted on 11/28/2008 11:58:09 AM. I present at a lot of the local Florida

  27. Paul Batum says:

    This post inspired me to do my own series on how the y combinator can be derived. I used C# and tried to go about it using very small steps. The series starts here:

    http://www.paulbatum.com/2009/01/refactoring-towards-y-combinator-part-1.html

  28. At PDC several years ago, I attended the first talk on C# 3.0 by Anders Hejlsberg wherein he demonstrated

  29. serge says:

    Just for completeness. Here’s what the Y combinator factorial looks like in Erlang.  Simple and clear:

    fun(0, _) -> 1; (X, F) -> X * F(X-1, F) end.

  30. Glenn Slayden says:

    Great post.

    I understand the geeky theory, and the fact that the compiler gives "error CS0165: Use of unassigned local variable" proves that it, too, is a geek.

    But in the real world, assigning null first, as others have pointed out, works.

    Func<int, int> f = null;

    f = x => (x == 0) ? 1 : x * f(x – 1);

  31. Harro says:

    Well, this seems to work also:

    public static Func<int, int> fac = f => f == 0 ? 1 : f * fac(f – 1);

  32. Dzugaru says:

    One more point – return value type of a recursive function is not related to it's argument type in any way. So it can be written like this:

    class Fun<T, TResult>

    {

    delegate T1 SelfApplicable<T1>(SelfApplicable<T1> warp);

    static SelfApplicable<Func<Func<Func<T,TResult>,Func<T,TResult>>,Func<T,TResult>>> Y = y => f => x => f(y(y)(f))(x);

    public static Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>> Fix = Y(Y);

    }

    and allows more fun stuff like, say, traversing a tree recursively and sum it's leaves values:

    int sum = Fun<TreeNode, int>.Fix(tree =>

    node =>  node.Value + (node.Nodes.Count == 0 ? 0 : node.Nodes.Sum(a => tree(a))))(firstNode);

  33. Doug says:

    Love the posts. Please keep them coming.

  34. Timwi says:

    Such a grave error you are perpetuating here in this post:

    “x => x == 0 ? 1 : x * fac(x-1)

    But that won’t work – we’re using fac to define fac, but we haven’t defined it yet!”

    That’ll work just fine, you just have to write the definition separately from the declaration:

    Func<int, int> fac = null;

    fac = x => x == 0 ? 1 : x * fac(x-1);

    No need for the head-spinning fix-point operator, no need for all that brain-crashing lambda calculus stuff. It’s all interesting and fascinating and geeky, but it’s *not necessary in production code*. I’m disappointed that you make it sound as if it were.

  35. Sanity of readers ... says:

    I love Obfuscated C…..  Or is this C#?… Or is it C? I can't tell.  , I used to love -> of C and my heart was shattered when someone told me that C# gonna chop it off.

    Now it has got a buddy …. I hope someone doesn't write "lambda functions considered harmful to sanity of readers" for at least 10 years to come…