Witam
Implementuję interpreter prostego języka funkcyjnego i napotkałem na problem z ewaluacją funkcji rekurencyjnych.
Chciałbym mieć dla f. rek specjalną składnię np. \f . x -> if x <= 1 then 1 else x * f (x - 1) albo
LETREC f = \x -> if x <=1 then 1 else x * f (x - 1) IN f (w zależności co jest prostsze).
Resztę wyrażeń ewaluuję poprzez redukcję do Weak Head Normal Form z tym, że argumenty funkcji i operatorów są
redukowane jeszcze przed ewaluacją ciała funkcji.
Teraz chciałem zaimplementować ewaluację fun. rek. poprzez zastąpienie wszystkich wystąpień \f . x -> exp przez
Y (\f . x -> exp), gdzie Y jest kombinatorem punktu stałego. Niestety proram się zapętla.
Kombinator Y implementowałem na dwa sposoby: Y dla strategii leniwej i Z gorliwej, ale w obu przypadkach się zapętla.
(Zapętla się przy ewaluacji a nie sprawdzaniu typów).
Czy macie pomysł co może być nie tak?
Czy może znacie jakiś inny sposób jak zaimplementować taką rekurencję tak, aby pasowała do ewaluacji reszty konstrukcji?
Pozdrawiam
Adam
P.S. Nie wiem czy to może być ważne, ale w ksiąąkach traktujących o implementacji języków funkcyjnych ostrzegali przed
"name-capture problem" i podawali, że jednym z wyjść jest przemianowanie zmiennych związanych w ewaluaowanym wyrażeniu.
Ku mojemu zdziwieniu zaimplementowałem to jakoś tak, że nie potrzebuję tego robić a wszystko działa dobrze.