Правильный тег AST

Question

Я уже давно пытаюсь создать тэги AST. Давайте представим вопрос:

data E a
  = V a
  | LitInt Int
  | LitBool Bool
  | FooIntBool (E a) (E a) -- er…
    deriving (Eq,Show)

Проблема с этим фрагментом кода, для меня, заключается в FooIntBool, Идея состоит в том, что он принимает выражение int и выражение bool и склеивает их вместе. Но E a может быть что угодно. Это будет действительно, учитывая приведенное выше определение E:

FooIntBool (LitInt 3) (LitInt 0)

Вы можете увидеть проблему. Тогда что мы хотим? Помеченное выражение. Это невозможно, учитывая текущее определение E, поэтому давайте представим несколько GADT:

data E :: * -> * -> * where
  V          :: a -> E l a
  LitInt     :: Int -> E Int a
  LitBool    :: Bool -> E Bool a
  FooIntBool :: E Int a -> E Bool a -> E (Int,Bool) a

Это довольно мило! Теперь я могу исправить такой код:

FooIntBool (V "x") (LitBool False)

Проблема в том, когда я хочу сделать это монадой или аппликативом. Это просто невозможно. Рассмотрим реализацию монады:

instance Monad (E l) where
  return = V

Это было очевидно и понятно. Давайте посмотрим реализацию связывания:

  V x >>= f = f x -- obvious as well
  LitInt a >>= _ = LitInt a -- obvious yeah
  LitBool a >>= _ = LitBool a -- …
  FooIntBool a b >>= f = FooIntBool (a >>= ?) (b >>= ?) -- AH?

Мы не можем написать a >>= f а также b >>= f поскольку f :: a -> E l b, Я еще не нашел решения этой проблемы, и мне действительно любопытно, как с этим справиться, и я все еще могу использовать индексы де Брюина (через связанное).

Answer 1

Я думаю, что ваш напечатанный AST вряд ли будет работать так, как вы хотите. Тот факт, что переменные нетипизированы, повредит. Попытайтесь представить, каково это было бы написать переводчика со средой; вам придется искать переменные в среде, а затем либо приводить результаты к правильным типам, либо с ошибкой. Итак, я собираюсь предложить немного другой AST с типизированными переменными и пока еще необъяснимое изменение порядка параметров типа.

data E v a where
  V          :: v a -> E v a
  LitInt     :: Int  -> E v Int
  LitBool    :: Bool -> E v Bool
  FooIntBool :: E v Int -> E v Bool -> E v (Int, Bool)

Теперь, насколько я знаю, невозможно определить законопослушного Monad экземпляр для этого. Обратите внимание, что вид E является (* -> *) -> * -> *; для наших целей может быть более интуитивным думать о нем как о (* -> *) -> (* -> *), Это внешне совместимо с тем, что Monad надеется, * -> *по крайней мере, если вы частично подать заявку E для некоторых v, но тогда типы становятся странными. Я полагаю, что вы уже знаете об этом, именно поэтому вы поместили свой параметр типа переменной последним; Предполагаемый эффект этого заключается в том, что (>>=) будет представлять замену. Однако, если мы сделали это с этим новым типом, который я предложил, он не совместим с Monad совсем.

Однако есть другой тип монады, который может работать. Мы можем обобщить его вид из * -> * в (k -> *) -> (k -> *) (где k в этом случае просто *). Обратите внимание, что я использовал скобки, чтобы подчеркнуть это, как и большинство случаев Monad, E должен рассматриваться как конструктор унарного типа. Мы будем работать с естественными преобразованиями вместо какой-либо старой функции Haskell:

type a ~> b = forall x. a x -> b x

(Кстати, вид (~>) является (k -> *) -> (k -> *) -> *.)

Чтобы построить наш новый HMonad Тип класса, мы можем просто скопировать Monad и заменить (->) с (~>), Есть одно осложнение, которое заключается в том, что мы должны изменить порядок аргументов (>>=), чтобы заставить типы работать:

class HMonad m where
  hreturn ::  a ~> m a
  hbind   :: (a ~> m b) -> (m a ~> m b)

Я просто покажу вам HMonad экземпляр для E а затем попытайтесь объяснить это:

instance HMonad E where
  hreturn = V
  hbind f e = case e of
    V v            -> f v
    LitInt x       -> LitInt x
    LitBool x      -> LitBool x
    FooIntBool a b -> FooIntBool (hbind f a) (hbind f b)

На самом деле, это выглядит именно так, как Monad экземпляр был бы для нетипизированной версии AST. Обратите внимание, что, как и ожидалось, hreturn просто вводит переменную, и hbind выполняет типобезопасную замену путем поиска переменных и применения к ним функции. Это работает из-за более высоких типов ранга.

Вы не можете сделать это с помощью связанного пакета, так как он использует Monad вместо этого любителя HMonad, Можно (и даже неоднократно) писать версию границы, которая работает для типизированных AST, как это, но неясно, стоит ли это на самом деле.

Answer 2

Если вы действительно хотите, можно написать хорошо напечатанный Monad пример. Я не проверял, следует ли он законам монады.

instance Monad (E l) where 
  return = V 

  V x >>= f = f x 
  LitInt a >>= _ = LitInt a 
  LitBool a >>= _ = LitBool a
  FooIntBool a b >>= f = FooIntBool (a >>= q.f) (b >>= r.f) where 

    q :: E (Int, Bool) t -> E Int t
    q (V x) = V x 
    q (FooIntBool x _) = x

    r :: E (Int, Bool) t -> E Bool t
    r (V x) = V x 
    r (FooIntBool _ x) = x