Untyped lambda calculus in C#

Question

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).

Can you specify an example of lambda or expression you want to get in the end? — CodingNagger
Currently the expression I am trying to evaluate is M(M(I)), for instance (I need to test for it because it is very much the main cause of stack overflows in such things) — Slereah
So you want something like Func<Object, Function<Object, Object>>? — Sumner Evans
I need a lambda expression that would be able to take a lambda expression as its input and give a lambda expression as its output. Ideally no other object should be involved in it. — Slereah

Mo B. Mo B. · Accepted Answer · 2020-11-19T12:00:18

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.

Untyped lambda calculus in C#

1 Answers