如何在 F# 中实现定点运算符（Y 组合器）？

Question

我正在使用 F# 创建 lambda 演算。我目前正试图弄清楚如何实现定点运算符（也称为 Y 组合器）。

我认为其他一切都井然有序。表达式由以下可区分联合表示：

type Expr =
 | Const of int
 | Plus  of Expr * Expr
 | Times of Expr * Expr
 | Minus of Expr * Expr
 | Div   of Expr * Expr
 | Neg   of Expr
 | Var   of string
 | Fun   of string * Expr
 | App   of Expr * Expr
 | If    of Expr * Expr * Expr

我的 eval 函数似乎可以工作。以下示例均产生预期结果。
示例1：
<代码>> eval (Fun("x",Plus(Const 7,Var("x"))));
val it : Expr = Fun ("x",Plus (Const 7,Var "x"))
示例2：
<代码>> eval (App(Fun("x",Plus(Const 7,Var("x"))),Const 3));;
验证它：Expr = Const 10
示例3：
<代码>> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

但正如我所提到的，我在 lambda 演算中实现定点运算符时遇到了困难。它在此处定义为：
Y = lambda G.(lambda g.G(gg)) (lambda g.G(gg))

有人有什么建议吗？我查看了有关 Y 组合器的其他问题，但找不到任何我能够成功采用的内容。

感谢所有帮助。

编辑：修正了代码中的一个拼写错误...之前我在可区分联合中使用了Mult而不是Minus。有趣的是我刚刚注意到这一点！

Answer 1

您所指的版本仅适用于惰性语言，如果您的语言不使用惰性求值策略，您将陷入无限循环。尝试翻译一下这个：

Y = lambda G. (lambda g. G(lambda x. g g x)) (lambda g. G(lambda x. g g x))

Answer 2

据我记得，无类型 lambda 演算中有一整类 Y 组合器，但如果您的语言是严格类型的，那么即使是一个 Y 组合器也很难实现，尽管人们已经尝试在 ML 和 F# 中执行特殊情况。如果您的语言支持递归（lambda 演算不支持），那么它似乎不是很有用。看看 Stackoverflow 上标记为通用“函数式编程”或 ML 的有关该主题的讨论，我认为有一些见解：

Y-Combinator 实际示例