Lambda returning another lambda

Question

is there any way how to return lambda from another lambda recursively?

All I want to do is finite state machine, implemented as lambda, which returns lambda implementing another state (or null).

nesting Func<> won't work as I want.

C#, .NET 3.5

Example:

machine, 3 states, pseudolanguage

private Lambda State1()
{  
    if (SomeConditionIsMet)
        return State2;
    else
        return State1;
}

private Lambda State2()
{  
    while (SomeConditionIsMet)
        return State2;
    else
        return State3;
}

private Lambda State3()
{  
    LogEnd();
    return NULL;
}

public void FSM()
{
    Lambda _currentState = State1;

    while(_currentState != NULL)
    {
        _currentState = _currentState();
    }
}

I know, that I can workaround this using enum+switch, for example, but I'm just curious if I can do this.

Answer 1

Your question is already answered, but those reading this may be interested to note that you can use this technique to embed the Lambda calculus in C#.

First starting with:

    public delegate Lambda Lambda(Lambda x);

Using various function definitions found at http://en.wikipedia.org/wiki/Lambda_calculus I defined various primitives as follows:

    public static Lambda Id         = x => x;
    public static Lambda Zero       = f => x => x;
    public static Lambda True       = x => y => x;
    public static Lambda False      = x => y => y;
    public static Lambda One        = f => x => f(x);
    public static Lambda Two        = f => x => f(f(x));
    public static Lambda Succ       = n => f => x => f(n(f)(x));
    public static Lambda Three      = Succ(Two);
    public static Lambda Pred       = n => f => x => n(g => h => h(g(f)))(u => x)(Id);
    public static Lambda Plus       = m => n => f => x => m(f)(n(f)(x));
    public static Lambda Sub        = m => n => n (Pred) (m);
    public static Lambda And        = p => q => p(q)(p);
    public static Lambda Or         = p => q => p(p)(q);
    public static Lambda Not        = p => a => b => p(b)(a);
    public static Lambda IfThenElse = p => a => b => p(a)(b);
    public static Lambda IsZero     = n => n(x => False)(True);
    public static Lambda IsLtEqOne  = n => IsZero(Pred(n));
    public static Lambda Pair       = x => y => f => f(x)(y);
    public static Lambda First      = pair => pair(True);
    public static Lambda Second     = pair => pair(False);
    public static Lambda Nil        = x => True;
    public static Lambda Null       = p => p(x => y => False);
    public static Lambda LtEq       = x => y => IsZero(Sub(x)(y));
    public static Lambda Gt         = x => y => LtEq(y)(x);
    public static Lambda Eq         = x => y => And(LtEq(x)(y))(LtEq(y)(x));
    public static Lambda M          = x => x(x);

For various tests and the whole code see: http://code.google.com/p/jigsaw-library/source/browse/trunk/Theory/EmbeddedLambdaCalculus.cs

Answer 2

Sure, you can return a lambda from another lambda:

Func<int, Func<int, int>> makeAdder = x => y => x + y;
Func<int, int> addTen = makeAdder(10);
Console.WriteLine(addTen(20)); // 30

What aspect of the syntax are you having trouble with? I am interested to know how people get this sort of thing wrong because that helps us design the language and documentation better next time.

UPDATE:

well, but you cannot return lambda returning lambda

Sure you can.

Func<int, Func<int, int>> GetAdderMaker()
{
    return x => y => x + y;
}

Here we are returning a lambda that returns a lambda. Why do you believe this is impossible?

UPDATE:

Aha, I understand. You believe that the word "lambda" means "delegate". It does not. A lambda is a kind of expression that is convertible to a delegate.

If you want a delegate that returns a delegate then just declare that. That's perfectly legal. For example, here's a delegate called a "combinator" -- a combinator is a delegate which takes itself and returns itself:

delegate D D(D d);

That's a delegate named D which takes a D and returns a D.

You can make a lambda expression that is compatible with this delegate type. For example:

D I = x=>x;

is the Identity combinator. Or

D M = x=>x(x);

is the Mockingbird combinator in Raymond Smullyan's whimsical characterization of combinators.

As you correctly note, there's no way to make a generic Func that is this kind of combinator. I wrote an article about this fact back in 2006:

http://blogs.msdn.com/ericlippert/archive/2006/06/23/standard-generic-delegate-types-part-two.aspx

Answer 3

I believe you can declare a delegate type: public delegate Lambda Lambda() which returns a delegate of its own type. It does compile, anyway.