Anonymous Recursion

I was planning on writing about anonymous recursion relating to work in NStatic, but Wes Dyer beat me to the punch with his post Anonymous Recursion in C#. In addition to my name, Wes Dyer shares my desire to push a more functional style of programming in C# (and he's also a member of the C# team, so we may win).

 

Loops and recursive functions in NStatic are converted to recursive lambda expressions, and then through various techniques like unrolling, recurrence solving, inductive proofs, are simplified to a closed form. The expressions above are intentionally unsimplified for illustrative purposes. 

Each of the lambda expressions displayed above are recursive. Nonrecursive lambda expressions are applied over their arguments, so they aren't normally seen unless standalone without any arguments.

I am not currently sure how I will eventually display lambda expressions in C#; the current display is attractive to my eyes, personally, but may turn off users unfamiliar with lambda calculus. I probably will ultimately go with a more C#-like syntax. My previous attempt was quite unreadable or quite verbose because the lambda operator => looks like the inequality operator and the use of parenthesis was quite excessive. Another possibility is to use C# 2.0 syntax with delegate and return keywords.

For those with sharp eyes, I introduced a fix operator to concisely display recursive lambda expressions. The fix function takes as its argument any lambda expression that includes a first parameter, representing the name of the function itself. That parameter can be used inside the lambda expression to recursively call itself.

In a language that does not explicitly have recursion operators, lambda expressions can be used to introduce recursion. It's not very pretty, but one such operator to do this is called the Y fixed-point combinator.

    public delegate Func<X,T> YFunc<X,T>(YFunc<X,T> f);
    public static Func<X, T> YCombinator<X, T>(Func<Func<X,T>, Func<X,T>> f)
    {
        YFunc<X,T> lambda = delegate(YFunc<X,T> y)
        {
            // return f(y(y)); -- only works with call by name
            return f(delegate(X x) { return y(y)(x); });
        };
        return lambda(lambda);
    }

The combinator does not allowed to use recursion, only function application, in its definition, since it's purpose is to introduce a form of recursion in the first place.

The Y combinator is possible in a typed language like C# because C# allows us to recursively define types--that is, YFunc was defined in terms of itself. A slight modification, an additional lambda expression, was also needed to allow f(y(y)) to be called by name.

A more efficient function for anonymous recursion takes advantage of assignment in the C# to avoid the creation of more than one closure is the following function.

    public static Func<X, T> Fix<X, T>(Func<Func<X,T>, Func<X,T>> func)
    {
        Func<X,T> fixfunc = null;
        fixfunc = func(delegate(X x) { return fixfunc(x); });
        return fixfunc;
    }

An example of its use in C# is the following:

    Func<int,int> func = Fix<int,int>(
        delegate(Func<int,int> f)
        {
            return delegate(int n)
            {
                return n<=1 ? 1 : n + f(n-1);
            };
        });
    
    Console.WriteLine(func(6));

Comments

[Zane Tailor]

In your first code sample you use YFunc and Func. Is that a typo? If not, what is Func?

[Wesner Moise]

Func is a generic delegate type defined in Visual Studio Orcas/C# 3.0/VB 9.0.

delegate T Func(A a);
delegate T Func();
delegate T Func

[Wes]

Comments don't accept less-than and greater-than symbols.

delegate T Func{A,T}(A a);
delegate T Func{T}();
delegate T Func{A1,A2,T}(A1 a1, A2 a2);