3

我试图弄清楚如何在这个最终无标签 EDSL 中表达 Y-Combitor：

class Symantics exp where
    lam :: (exp a -> exp b) -> exp (exp a -> exp b)
    app :: exp (exp a -> exp b) -> exp a -> exp b

    fix :: ...
    fix f = .....

我不确定，但我认为 Y-Combinator 的默认实现应该可以使用“lam”和“app”。

有人知道怎么做吗？我的第一次尝试失败是因为“无法构造无限类型”的东西。

干杯，Günther

4

2 回答 2

2

如果引入 let，则可以提供默认实现。但是你不能单独使用 lam 和 app 这样做，出于同样的原因，你不能在没有 let 的情况下直接在 Haskell 中编写它。您的目标是简单类型的 lambda 演算的扩展，而该术语不会输入。

于 2010-06-23T17:11:56.727 回答
2

正如 sclv 指出的那样，您需要在语言中引入原始不动点形式。想想它在 Haskell 中是如何定义的：

fix :: (a -> a) -> a
fix f = let x = f x in x

一个合适的“让”绑定表格将带您到达那里。Barendregt 的第 1 章和第 2 章是此类基础知识的一个很好的参考，它们可能在您的图书馆中——尽管我相信它已经绝版（有人可以确认吗？）。紧随其后的是http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.9283

于 2010-06-23T17:41:07.580 回答