ROSES ARE #FF0000
VIOLETS ARE #0000FF
ALL MY BASE
ARE BELONG TO YOU

#easter #geek

Some notes on recursive lambda expressions in case I ever want to try this myself (spoilers: a lot of study time ahead; many of these links are not live any more)

A sidestep of the series around Writing a tool that restarts the Google Chat desktop app Window (and hopefully the Google Duo desktop app Window too):

Enumerating Windows and especially Child Windows is a recursive endeavour, so I wondered if it was possible to write a self referencing delegate, anonymous method or lambda in C#.

That turns out to be way more complicated than I hoped for.

Some notes below, as:

• one day I might want to rewrite the core to use this technique just for learning purposes
• finding these links was quite a bit harder than expected due to link rot often caused by missing redirects (especially on the Microsoft blog sites: for one as not all their blog members are still with them which means content got ditched, and also because they moved through a couple of blog platforms so the really old links to not redirect, not even while tracking them through the Wayback Machine, or the content is incomplete which is why all below links are both in the Wayback Machine and Archive.is)

Here we go:

Let’s start with the recursive series that most of the below links use:

Factorial numbers grow way faster than Fibonacci numbers, but there are more series that can grow even faster as explained in Recurrence relation – Wikipedia, but I digress.

Then the blog posts:

• [Wayback/Archive] Mads Torgersen has a great explanation, though it is still not easy to grasp. It is from 2007 and at [Wayback/Archive] Recursive lambda expressions – The Mellow Musings of Dr. T – Site Home – MSDN Blogs (the live link is long gone that was why it was tough to find at all):
  

  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.

  so basically: it can be done, it is ugly, do not use it if you can avoid it.

  He continues:

  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!

  and the final part of the post is showing how ugly:

  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)

  • [Wayback/Archive] Mads Torgersen | InformIT
    

    Mads Torgersen is a senior program manager at Microsoft. As the program manager for the C# language, he runs the C# language design meetings and maintains the C# language specification. Prior to joining Microsoft in 2005, Mads was an associate professor at the University of Aarhus, teaching and researching object-oriented programming languages. There, he led the group that designed and implemented generic wildcards for the Java Programming Language.

• [Wayback/Archive] Stupid Lambda Tricks – Visual C++ Team Blog – Site Home – MSDN Blogs (live link is dead, but archived links have the complete blog post content including comments)[Wayback/Archive] Stupid Lambda Tricks – C++ Team Blog (incomplete! – it only contains the first half of the post)
  describes the crux:

  Note that we had to actually name the lambda in order to implement the recursion.  Without a name, how would you make the recursive call?  This self-referencing places some restrictions on how a recursive lambda can be used; the lambda doesn’t refer to itself, it refers to fib1, which happens to be itself.

  [Wayback/Archive] Stupid Lambda Tricks – Visual C++ Team Blog – Site Home – MSDN Blogs – page 2 has the rest of the comments.

  This blog post also links to a great article below from Bart de Smet.

• From [Wayback/Archive] Wes Dyer is [Wayback/Archive] Anonymous Recursion in C# – Yet Another Language Geek – Site Home – MSDN Blogs (yup, this live link is also dead, but the archived content have the full blog post)
  [Wayback/Archive] Anonymous Recursion in C# | Microsoft Learn does have a live link, but has all the <code> tags removed which might have influenced the code itself too (on my content management systems occasionally does), so here are quotes from the content with those [Wayback/Archive] <code> : The Inline Code element – HTML: HyperText Markup Language | MDN in it as it shows how to create the Y-combinator:

  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’

  … The problem is that the right hand side is evaluated before fib is definitely assigned.

  …

  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);

  …

  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.

  In the comments, he then shows the same Action<T> Y-combinator that Eric Lippert shows below on Stack Overflow:

  delegate Action RecursiveAction(RecursiveAction r);static Action Y(Func<Action, Action> f){  RecursiveAction 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.

  delegate Action RecursiveAction(RecursiveAction r);static Action Y(Func<Action, Action> f){  RecursiveAction 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.

  Be sure to read the other comments there as well as they also describe the memoisation optimisation that Bart de Smet writes about below.

  • [Wayback/Archive] 5.3 Definite assignment (C#) (2003)
    

    At a given location in the executable code of a function member, a variable is said to be definitely assigned if the compiler can prove, by static flow analysis, that the variable has been automatically initialized or has been the target of at least one assignment.

  • Fixed-point combinator: Y combinator – Wikipedia
    

    In functional programming, the Y combinator can be used to formally define recursive functions in a programming language that does not support recursion.

     

  • The bog post about currying from Wes Dyer further below.
• [Wayback/Archive] Why does a recursive lambda cause a definite assignment error? – Fabulous Adventures In Coding – Site Home – MSDN Blogs (yup, the live content of that post got lost as well; the archived versions work and have code markup and show all the comments, including an interesting one from Wes Dyer – yes about the Y combinator, and a comment referring to the blog post from Mads Torgersen)
  [Wayback/Archive] Why does a recursive lambda cause a definite assignment error? | Microsoft Learn is live, but omits the both the valuable comments and the code markup.

  What if we wanted that last one to use lambdas?

  static void PrintTree(Tree t){ Traversal df = (t, a)=>{ if(t==null) return; a(t.Value); df(t.Left, a); df(t.Right, a); }; Traverse(t, df, Print);}

  That doesn’t work because it’s a definite assignment error. The compiler says that local variable df is being used before it is assigned. You’d have to say

  Traversal<T> df = null;df = (t, a)=>{

  And suddenly it would start working.

  The reason this is an error is because though there is actually no definite assignment problem here, it is not too hard to find a similar situation which does create a problem. Here’s a silly example that nevertheless demonstrates a real problem:

  delegate D D(D d);//...D d = ((D)(c=>c(d))(e=>e); If you trace out the logic of that thing you’ll find that in fact the local variable delegate d is potentially used before it is initialized, and therefore this must be an error. We could immensely complicate the definite assignment rules by adding rules to discover which lambda and anonymous method bodies are guaranteed to be never called during the initialization, and therefore suppress definite assignment errors on some locals in their bodies. But one of the goals of the standardization process is to make rules that are clear and unambiguous and comprehensible by mortals; enabling recursive anonymous methods isn’t a big enough win for the amount of complexity, particularly when you consider that there is the simple workaround of assigning to null and then reassigning.

  Note that in practice though, assigning null will not capture that value, but still capture the variable (including the new assignment) and use the captured variable in the lambda.

• Linked from the C++ team blog above is a C# blog post by [Wayback/Archive] bartdesmet (Bart J.F. De Smet) at [Wayback/Archive] Memoization for dummies – B# .NET Blog (which too is only available on the archived places: the live link died shortly after the 2020 archival at [Wayback/Archive] Memoization for dummies – B# .NET Blog).Bart explains the error most people get while trying in an easier way than all above posts:
  

  Func<uint, uint> fib = null;
  fib = n => n <= 2 ? 1 : fib(n – 1) + fib(n – 2);

  The reason we need to spread this across two lines is interesting by itself. If we don’t do this, the following error appears:

  memoize.cs(17,48): error CS0165: Use of unassigned local variable ‘fib’

  referring to the highlighted position in the code:

  Func<uint, uint> fib = n => n <= 2 ? 1 : fib(n – 1) + fib(n – 2);

  The reason this error pops up is because we’re defining a function in terms of itself, something that’s invalid in a variable declaration/assignment in C#, just like the following is invalid:

  int a = a + b;

  Then he gets to the point about explaining what happens when the statement is spread across two lines: the variable fib (and not its initial null value) is captured in the n => n <= 2 ? 1 : fib(n - 1) + fib(n - 2)lambda expression:

  But what are we doing really when declaring the following?

  Func<uint, uint> fib = null;
  fib = n => n <= 2 ? 1 : fib(n – 1) + fib(n – 2);

  When assigning the lambda on the second line to fib, we’re capturing the fib variable itself as it appears in the lambda’s body.

  Then he goes on measuring performance of this function, and then injects a memoisation which is plugin compatible with fib and caches intermediate fib results (as fib(n-1) depends on the result of fib(n-2), which results of an order of magnitude performance increasing!)

• [Wayback/Archive] Currying and Partial Function Application – Yet Another Language Geek – Site Home – MSDN BlogsI have not yet wrapped my head around this, especially about practical use, so I will likely need to read Currying – Wikipedia first.

Big thank you

I got most of the above links via two sources:

How I found all this

This was my start: [Wayback/Archive] recursive c# self referencing Action – Recherche Google.

It got me to both the Stack Overflow question above and the 2011 comment.

--jeroen

#000080 #0000ff #008080 #ff0000

Even front-end devs are romantic, you know ❤️

.rose {
color: #FF0000;
}
.violet {
color: #0000FF;
}
.honey, #you {
sweet: true;
}

Get our latest design here =>
https://shirtforce.org/tee/roses-are-ff0000/

100% profits go to our sponsorship program.
#valentines #SaaS #CSS #frontend #swag