Y-Combinator в FT EDSL - PullRequest
Новая
       4

Y-Combinator в FT EDSL

3 голосов
/ 23 июня 2010

Я пытаюсь понять, как выразить 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-Combinator по умолчанию должна быть возможна с использованием "lam" и "app".

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

Ура, Гюнтер

Ответы [ 2 ]

2 голосов
/ 23 июня 2010

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

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

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

2 голосов
/ 23 июня 2010

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

...