c# - C# 中的无类型 lambda 演算

Question

我一直在尝试在 C# 上实现原始 lambda 演算，但在实现它时遇到了一些麻烦，因为最后，我总是被要求提供对象。

例如，我想要一些可以让我定义一些基本逻辑组合子的东西，例如

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

但是 C# 似乎是在假设它最终会得到一个对象的情况下运行的。我试图以各种方式定义它们，例如

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

依此类推，但要么不遵守语法，要么不兼容

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

我尝试使用委托(delegate)

public delegate object lambda(Object o);

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

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

但最后，这些函数的任何实际使用仍然需要在行尾有一个参数，以及一个像

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

只会在执行过程中导致转换错误。

有没有办法在本地实现无类型 lambda 演算，还是我必须回到字符串处理？

对于程序的执行示例，它看起来像这样。对于以下功能:

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

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

(m(m))(i) 的执行应该类似于 m(m) 被评估，在打印 "m"后返回 m(m)，这将返回原始的 (m(m))(i)，然后将打印无限量的“m”(这是最简单的带有逻辑组合符的无限循环，尽管稍后会涉及一些蹦床以避免破坏堆栈)。

Answer 1

而不是将 lambda 表达式编码为 Func<,> (这可能不适合 无类型 lambda 演算)，您应该将其编码为抽象语法树。像这样的东西:

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; }
}

例如， M将会

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

然后，在此数据结构上实现用于 alpha 重命名和 beta 缩减的递归方法非常简单。