Subject: Реализация рефала на haskell - структуры днных
From: Mike Potanin (potanin@mccme.ru)
Date: Mon Aug 20 2001 - 19:52:54 MSD
Я начал реализовывать интерпретатор рефала на haskell. Моя цель не только
изучить оба языка :-), но и проверить что получится, если сделать рефал
ленивым. Рефал поддерживает структуру данных, к которой можно подступится
с 2 сторон, в то время как к списку только с одной. Я пока реализовал
рефаловские структуры через список. В результате
Test1 {
s.a e.b = e.b;
}
Test2 {
= 'a' <Test3>;
}
выполняется лениво, а
Test1 {
e.b s.a = e.b;
}
Test2 {
= <Test3> 'a'>;
}
лениво выполнится не может.
Есть еще одна проблема, с ленивостью не связаная.
В рефале требуются ссылки на подструктуры и возможносто конкацинации этих
ссылок. Сейчас я каждый раз копирую часть списка, что не очень эффективно.
Впрчем тестов на призводительность я не проводил, может ленивость haskellа
эту неэфективносто компенсирует.
В связи с вышесказаным у меня возник вопрос, как можно реализовать
рефаловские структуры данных, что бы этих проблем не возникало?
Списки можно реализовать не выходя за рамки лямбда-исчисления
cons a b = \f->(f a b)
head l = l (\a -> (\b -> a))
tail l = l (\a -> (\b -> b))
Есть ли столь же элегантная запись рефаловских структур?
P.S.
Где-нибудь есть формально описаная граматика рефала? Я в формальных
граматиках не силен и сочинять ее самому мне не хочется.
P.S.S.
Здесь многие хорошо знают и рафал и haskell. Может у кого-нибудь
найдется временя посмотреть эту программу
(http://pm.kmost.express.ru/~pm/hrefal.tgz).
Ее конечно надо переписать "с нуля", но я еще не понял как правильно
писать на haskell с точки зрения стиля. Буду благодарен любым замечаниям.
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:59 MSD