Y-Combinator в FT EDSL

Question

Я пытаюсь выяснить, как выразить Y-Combitor в этом Наконец Tagless EDSL:

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 -Комбинатор должен быть возможен, используя «lam» и «app».

Кто-нибудь знает как? Мои первые попытки терпят неудачу из-за того, что «невозможно построить бесконечный тип».

Приветствия, Гюнтер

Answer 1

Если вы приведете ЛПЭ вы можете обеспечить реализацию по умолчанию. Но вы не можете сделать это с помощью lam и приложения в одиночку, по той же причине вы не можете написать его прямо в Haskell без разрешения. Ваша цель здесь - расширение просто типизированного лямбда-исчисления, и этот термин просто не будет вводить его.

Answer 2

Как указывает sclv, вам нужно ввести примитивную форму фиксированной точки в язык. Подумайте о том, как это определено в Haskell:

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

Подходящая форма связывания «давайте» доставит вас туда. Хорошей ссылкой для такого рода фундаментальных материалов являются главы 1 и 2 Barendregt, которые могут быть в вашей библиотеке, хотя я считаю, что это не печатает (может ли кто-нибудь подтвердить?). A close second is http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.9283