FT EDSL中的Y-组合器

Question

我正在尝试如何在这个最终无标签的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 = .....

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

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

干杯，金瑟

Answer 1

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

Answer 2

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

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

一个合适的“let”绑定形式会让你做到这一点。这类基础资料的一个很好的参考资料是Barendregt第1章和第2章，它可能在您的图书馆中--尽管我认为它已经绝版(有人能证实吗？)。紧随其后的是http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.9283