Untyped lambda calculus in C#

user_3564549 0
Viewed 440

I've been trying to implement raw lambda calculus on C# but I am having some troubles implementing it, as in the end, I am always asked for objects.

I would like something that would allow me, for instance, to define a few basic logical combinators, such as 

I = Lambda x. x
M = Lambda x. x(x)

but C# seems to run on the assumption that it will get an object in the end. I've tried to define them in various ways, such as 

using lambda = Func<Object, Object>;
using lambda = Func<Func<Object, Object>, Func<Object, Object>>;
using lambda = Func<Func, Func>;

and so on, but either those do not obey the syntax or are incompatible with

lambda I = x => x;
lambda M = x => x(x);

I tried using the delegate 

public delegate object lambda(Object o);

static object i(object o)
{
    return o;
}

static object m(object o)
{
    return ((lambda)o)(o);
}

But in the end, any actual use of those functions will still require an argument at the end of the line, and a dummy argument like

m(m(i('')));

will simply lead to a cast error during execution.

Is there a way to implement typeless lambda calculus natively, or do I have to go back to string processing?

For an example of execution of the program, it would look something like this. For the following functions : 

lambda i(lambda x)
{
    print("i");
    return x;
}

lambda m(lambda x)
{
    print("m");
    return x(x);
}

The execution of (m(m))(i) should be something like m(m) is evaluated, returning m(m) after printing "m", which gives us back the original (m(m))(i), which will then print an infinite amount of "m" (this is the simplest infinite loop with logical combinators, although this will involve some trampolining later on to avoid blowing the stack).

lambda-calculus lambda c#
1 Answers

Rather than encoding a lambda expression as Func<,> (which is probably not a good match for untyped lambda calculus), you should encode it as an abstract syntax tree. Something like this:

public class LambdaAbstraction: ILambdaExpression {
    public LambdaVariable Variable { get; set; }
    public ILambdaExpression Body { get; set; }
}

public class LambdaApplication: ILambdaExpression {
    public ILambdaExpression Function { get; set; }
    public ILambdaExpression Argument { get; set; }
}

public class LambdaVariable: ILambdaExpression {
    public string Name { get; set; }
}

For example, M would be

ILambdaExpression M = new LambdaAbstraction {
   Variable = new LambdaVariable { Name = "x" },
   Body = new LambdaApplication {
       Function = new LambdaVariable { Name = "x" },
       Argument = new LambdaVariable { Name = "x" }
   }
}

Then it's quite straightforward to implement recursive methods for alpha renaming and beta reductions on this data structure.

user_6899230
Related