2

我正在使用 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));;
val it : Expr = Const 10
示例 3：
> eval (If(Const 0,Const 3,Const 4));;
val it : Expr = Const 4

但正如我所提到的，我很难在我的 lambda 演算中实现定点运算符。这里定义为：
Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

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

感谢所有帮助。

编辑：修正了代码中的错字......以前我有Mult而不是Minus在受歧视的工会中。有趣的是我才注意到这一点！

4

2 回答 2

4

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

Y = lambda G. (lambda g. G(lambda x. g g x)) (lambda g. G(lambda x. g g x))
于 2010-11-03T10:49:18.783 回答
1

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

Y-Combinator 实际示例

于 2010-11-03T11:53:13.190 回答