Lambda returning another lambda

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()
{开发者_JAVA技巧  
    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.

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

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

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

You can have a method which builds and returns an expression tree:

public Expression GetExpression()
{

}

Also building expression trees in .NET 4.0 has been greatly enhanced.