Lambda the Ultimate

Stumbling across Anonymous Recursion in C#, I see one solution is as follows:

Func<int, int> Factorial = null;
Factorial = (n) => n <= 1 ? 1 : n * Factorial(n - 1);

Func can be used in lieu of explicitly declaring the delegate. And splitting the declaration away from assignment gets around the instance declaration (though the link above takes issue whether this qualifies as true recursion).

Well, it's a bit difficult to have anonymous recursive function, sure the language can provide a 'this/self' keyword, but it's a little weird.

So no difference is a bit too strong IMHO.

[Edit Note: Meant as reply to renox]

Once you introduce the ability to name functions, it should not make a difference whether the function being called is one defined elsewhere or the one currently being defined. The only special consideration that recursion introduces is that the function being called has not been completely defined yet - a forward reference of sorts.

In languages that don't allow forward references, you have to introduce a special form to work around this limit. In ML, the 'rec' keyword can be used for this purpose. The function form of:

fun fact n =
   if (n <= 1)
      then 1
      else n * fact (n-1)

Is just syntactic sugar for:

val rec fact = fn n =>
   if (n <= 1)
      then 1
      else n * fact (n-1)

In PLs that don't allow reassignment of names, there is not a similar need for a special form. In Haskell, the function syntax of:

factorial n =
   if n <= 1
      then 1
      else n * factorial (n - 1)

Is just a special form for:

factorial = \n ->
   if n <= 1
      then 1
      else n * factorial (n - 1)

Since I'm discussing this in terms of C# lambdas, and I just went through the motions of translating SICP chapter 1 to C#, the example of calculating square roots with block scoping gives us:

double Sqrt(double x)
{
    Func<double, bool> Good_Enough = (guess) => 
        Math.Abs(Square(guess) - x) < 0.001;
    Func<double, double> Improve = (guess) =>
        Average(guess, x / guess);
    Func<double, double> Iter = null;
    Iter = (guess) =>
        {
            if (Good_Enough(guess))
                return guess;
            else
                return Sqrt(Improve(guess));
        };
    return Iter(1.0);
}

Looking beyond the problem of recursive functions that manifests itself in the Iter function, what I'm trying to say is that the above should be equivalent to the following code that the compiler won't accept:

double Sqrt(double x)
{
    bool Good_Enough(double guess)
    {
        return Math.Abs(Square(guess) - x) < 0.001;
    }
    double Improve(double guess)
    {
        return Average(guess, x / guess);
    }
    double Iter(double guess)
    {
        if (Good_Enough(guess))
            return guess;
        else 
            return Iter(Improve(guessx));
    }
    return Iter(1.0);
}

In other words, the problem works both ways. Sometimes I want to use lambdas where the language requires the use of named functions. And at other times, I want to use named functions where the language requires me to use lambdas. I prefer a PL that allows the user to select the most readable and maintainable form.

As long as I'm doing lambdas in mainstream languages, I was wanting to also take a look at Java Closures. Sticking with factorials, my guess would be that the equivalent for Java 1.7 would be:

{int=>int} factorial = 
   {int n => (n <= 1) ? 1 : n * factorial(n - 1)};

However, I downloaded the nigtly build for beta jdk 1.7 and it doesn't seem to be implemented just yet. Anyone know when java closures are going to be available for consumption?

In Virgil, I have a slightly more elegant way of expressing delegates, but currently do not have lambda. Virgil generalizes the common expr.method(...) syntax for method calls to expr(...) and generalize the member access operator to create a delegate by simply writing expr.method, which represents a first-class value that is the delegate bound to the function method and the object expr. Then the expr.method() invocation syntax just becomes a special case of the more general invocation syntax. Delegates in Virgil are typed by their argument and return types only, and there is a special type constructor called function that can be used to refer to function types.

Example from my paper:

class List {
    field head: Link;
    method add(i: Item) { . . . }
    method apply(f: function(Item)) {
        local pos = head;
        while ( pos != null ) {
            f(pos.item);
            pos = pos.next;
        }
    }
}
component K {
    method printAll(l: List) {
        l.apply(print);
    }
    method append(src: List, dst: List) {
        src.apply(dst.add);
    }
    method print(i: Item) { . . . }
}

The implementation represents delegate values as a two-word tuple of a pointer to a method and a pointer to an object, and so does not require memory allocation.

The drawback is that you sacrifice method overloading, because a delegate expression becomes ambiguous. Since there aren't any parameters in a delegate expression, there is no way to infer which of the overloaded methods is being called.

At any rate, retrofitting C# and Java with lambda seems like it's going to be ugly!