includedlibrary
@includedlibrary

Существует ли простой и элегантный способ добавить информацию о позиции в синтаксическое дерево с взаимно-рекурсивными типами?

Есть синтаксическое дерево с взаимно-рекурсивными типами LVal и Expr:
data Expr = IntLit Int
          | StrLit String
          | LVal LVal
          | Binop Expr Binop Expr
          | Assign LVal Expr

data Binop = Add | Sub | Mul | Div

data LVal = Var String
          | Dot LVal String
          | Index LVal Expr

Необходимо добавить в него информацию о позиции выражений в файле. Есть несколько вариантов. Первый - добавить позицию в каждый конструктор каждого типа:
data Expr = IntLit Int Position
          | StrLit String Position
          | LVal LVal Position
          | Binop Expr Binop Expr Position
          | Assign LVal Expr Position

data Binop = Add | Sub | Mul | Div

data LVal = Var String Position
          | Dot LVal String Position
          | Index LVal Expr Position

Но работать с такими деревьями уже не так удобно, как с обычными. Второй вариант - представление типов данных через Fix, но, так как они взаимно-рекурсивные, данный подход реализовать не получится. Можно, конечно, использовать Fix2:
newtype Fix2 f g = Fix2 { unFix2 :: f (Fix2 f g) (Fix2 g f) }

Но назвать подход с его использованием простым язык не поворачивается. Последним из вариантов является добавление отдельного конструктора с позицией в каждый из типов:
data Expr = IntLit Int
          | StrLit String
          | LVal LVal
          | Binop Expr Binop Expr
          | Assign LVal Expr
          | EAnn Expr Position

data Binop = Add | Sub | Mul | Div

data LVal = Var String
          | Dot LVal String
          | Index LVal Expr
          | LAnn LVal Position

Тогда с типами работать получается также удобно, как и без информации о позиционировании. Но в таком случае нельзя гарантировать, что каждый узел дерева снабжён информацией о позиции выражения.

Вопрос - существует ли простой и элегантный способ добавить информацию о позиции в синтаксическое дерево?
  • Вопрос задан
  • 80 просмотров
Решения вопроса 1
wiz
@wiz
Ортодоксальный хаскелит
Для работы с AST функторные кодировки более предпочтительны как раз за счёт возможности единообразно всем подсовывать новые фичи (а затем разом их скидывать). Да и с готовыми схемами рекурсии приятней работать, чем открывать фабрику велосипедов.

Набросал пример с добавлением аннотаций на эти выражения: https://repl.it/@ICRainbow/RoundHuskyExabyte
Fix2 не нужен, но надо чётко понимать чем будет являться функтор и неподвижная точка в каких выражениях. Это не сложно, но нужна практика.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Вроде такого способа нет.

А почему второй вариант неудобен?
См, например, haskell-src-exts, там у каждого типа есть доп. элемент типа l, в котором может быть позиция или что-то ещё.
В ghc сделано аналогично, но чуть иначе - некоторые конструкторы обёрнуты в Located
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы