3

このFinally Tagless 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 のデフォルトの実装が可能になるはずです。

誰でも方法を知っていますか？「無限型を構築できない」という理由で、最初の試みは失敗します。

乾杯、ギュンター

4

2 に答える 2

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です。

于 2010-06-23T17:41:07.580 に答える
2

let を導入すると、デフォルトの実装を提供できます。しかし、let なしでは Haskell で直接書くことができないのと同じ理由で、lam と app だけではそうすることができません。ここでのターゲットは、単純に型付けされたラムダ計算の拡張であり、その用語は入力されません。

于 2010-06-23T17:11:56.727 に答える