Why does a recursive lambda cause a definite assignment error?

  • Article

Hey fabulous readers, sorry for not much blogging lately. Between implementing LINQ and making plans to attend my first Burning Man, there's been no time for anything. We've had lots of new ideas generated here for the type inferencing algorithm which I will discuss in detail when I get back.

For now, here's a question I got recently about definite assignment analysis and recursive functions. Clearly this is legal:

delegate void Action<A>(A a);
delegate void Traversal<T>(Tree<T> t, Action<T> a);

static void DepthFirstTraversal<T>(Tree<T> t, Action<T> a){
if (t == null) return;
a(t.Value);
  DepthFirstTraversal(t.Left, a);
DepthFirstTraversal(t.Right, a);
}
static void Traverse<T>(Tree<T> t, Traversal<T> f, Action<T> a){
f(t, a);
}
static void Print<T>(T t){
System.Console.WriteLine(t.ToString());
}
static void PrintTree<T>(Tree<T> t){
Traverse(t, DepthFirstTraversal, Print);
}

What if we wanted that last one to use lambdas?

static void PrintTree<T>(Tree<T> t){
Traversal<T> 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.

What the heck? I mean, the original code is a syntactic sugar for:

privateclass Locals{
public Traversal<T> df;
public void M<T>(Tree<T> t, Action<T> a){
if(t==null) return;
a(t.Value);
this.df(t.Left, a);
this.df(t.Right, a);
}
}
static void PrintTree<T>(Tree<T> t){
Locals locals = new Locals();
locals.df = new Traversal<T>(locals.M<T>);
Traverse(t, locals.df, Print);
}

And clearly there is no use-before-initialization problem there.

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.

Comments

  • Anonymous
    August 18, 2006
    Isn't this something that's been solved in Scheme & co. by having letrec?

  • Anonymous
    August 18, 2006
    You can recurse without definite assignment problems but you need to do it with a fixed point combinator.  Here is the change.

    using System;

    class Program
    {
     static void Main()
     {
       var tree = new Tree<int>(3, new Tree<int>(4, new Tree<int>(1), null), new Tree<int>(5));
       PrintTree(tree);
     }

     delegate void Action<A>(A a);
     delegate void Traversal<T>(Tree<T> t, Action<T> a);

     static void Traverse<T>(Tree<T> t, Traversal<T> f, Action<T> a)
     {
       f(t, a);
     }

     static void Print<T>(T t)
     {
       System.Console.WriteLine(t.ToString());
     }

     static void Foo<T>(Tree<T> t, Action<T> a)
     {
       a(t.Value);
     }

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

     delegate Traversal<T> TraversalFunctor<T>(Traversal<T> t);
     delegate Traversal<T> Recursive<T>(Recursive<T> r);

     static Traversal<T> Fix<T>(TraversalFunctor<T> f)
     {
       Recursive<T> rec = r => new Traversal<T>((t, a) => f(r(r))(t, a));

       return rec(rec);
     }
    }

    class Tree<T>
    {
     public Tree<T> Left;
     public Tree<T> Right;
     public T Value;

     public Tree(T value) { Value = value; }
     public Tree(T value, Tree<T> left, Tree<T> right) { Value = value; Left = left; Right = right; }
    }

  • Anonymous
    August 24, 2006
    For what it's worth, your workaround is more or less what a letrec expands to in Scheme or Common Lisp.

    e.g. this form:

    (letrec ((len (lambda (ls) (if (null? ls) 0 (+ 1 (len (cdr ls))))))) (len '(1 2 3)))

    generates more or less the same code as:

    (let ((len 'unassigned)) (begin (set! len (lambda (ls) ...)) (len '(1 2 3))))

    (where 'unassigned is some special internal value).

  • Anonymous
    September 04, 2006
    The C# team is happy to welcome you to the new look of the C# Developer Center. This is the home page...

  • Anonymous
    February 02, 2007
    Recursion is beautiful and lambdas are the ultimate abstraction. But how can they be used together? Lambdas

  • Anonymous
    April 04, 2011
    I would have thought that a lambda body was actually a nested scope therefore the declaration and assignment should be split by the compiler anyway? This has made a piece of elegant code look ugly: Func<Node, bool> isInPath = null; isInPath = n => n.Key == selector ? true : n.Children.Any(s => isInPath(s));

  • Anonymous
    April 14, 2011
    This article may be interesting. Keep a nice cool ice-pack nearby when you read it in order to stop your brain overheating... blogs.msdn.com/.../recursive-lambda-expressions.aspx