Окончательный DSL без тегов с проблемами RValue LValue

Question

Типизированные финальные переводчики без тегов являются интересной альтернативой подходу свободной монады.

Но даже с довольно простым ToyLang Например, в последнем стиле без тегов всплывающие переменные.

ToyLang это EDSL, который должен читать что-то вроде этого:

toy :: ToyLang m => m (Maybe Int)
toy = do
    a <- int "a"       -- declare a variable and return a reference
    a .= num 1         -- set a to 1
    a .= a .+ num 1    -- add 1 to a
    ret a              -- returns a

Общая цель, конечно, состоит в том, чтобы максимально использовать систему типов Haskell в этом EDSL и использовать полиморфизм для создания различных интерпретаторов.

Все было бы хорошо, если бы не (.+) операция, которая приводит к понятию lvalue и rvalue: оператор присваивания (.=) имеет lvalue слева и либо lvalue, либо rvalue справа. Основная идея взята из двух комментариев в Impredicative Polymorphisms, вариант использования:

{-# LANGUAGE GADTs #-}

data L -- dummies for Expr (see the comments for a better way)
data R

-- An Expr is either a lvalue or a rvalue
data Expr lr where
    Var :: String -> Maybe Int -> Expr L
    Num :: Maybe Int -> Expr R

-- tagless final style
class Monad m => ToyLang m where
    int :: String -> m (Expr L)             -- declare a variable with name
    (.=) :: Expr L -> Expr lr -> m (Expr L) -- assignment
    (.+) :: Expr lr -> Expr lr' -> Expr R   -- addition operation - TROUBLE!
    ret :: Expr lr -> m (Maybe Int)         -- return anything
    end :: m ()                             -- can also just end

"Интерпретатор" с красивым шрифтом начинался бы так:

import Control.Monad.Writer.Lazy

-- A ToyLang instance that just dumps the program into a String
instance ToyLang (Writer String) where
    int n = do
        tell $ "var " <> n <> "\n"
        return (Var n Nothing)
    (.=) (Var n _) e = do
        tell $ n <> " = " <> toString e <> "\n"
        return $ Var n (toVal e)
    ...

где маленький помощник toString должен выкопать значения из слагаемых ГАДТ:

toString :: Expr lr -> String
toString (Var n mi) = n
toString (Num i)    = show i

Умный конструктор num это просто

num :: Int -> Expr R
num = Num . Just

(.+) хлопотно по двум причинам:

1. (.+) не в монаде m потому что иначе мы не можем написать a .= a + num 1, но для Writer String Например, монада нужна для того, чтобы tell,

2. Проверка типов лает на неоднозначные типы, созданные (.+) :: Expr lr -> Expr lr' -> Expr R, Понятно, что без дальнейших аннотаций он не может решить, какой экземпляр имеется в виду. Но комментируя такой пункт, как a .= a .+ num 1, если это вообще возможно, сделает DSL очень неуклюжим.

Один из способов заставить типы работать, двигая (.+) в какой-то степени в монаду, и (.=), слишком:

 class Monad m => ToyLang m where
    ...
    (.=) :: Expr L -> m (Expr lr) -> m (Expr L)
    (.+) :: Expr lr -> m (Expr lr') -> m (Expr R)
    ...

Все это странно, хотя

• (.=) а также (.+) асимметричны там, где им нужна монада m и где они не делают.

• Даже в Writer String Монада, я вынужден делать целочисленную арифметику, чтобы создать m (Expr R) тип возврата, хотя на самом деле нет необходимости в результате

• Инстанцирование ToyLang как Writer String выглядит аккуратно, но на самом деле не делает работу. a .= a .+ num 1 не может быть красиво напечатано как таковое, потому что a .+ num 1 оценивается (следовательно, печатается) до .=,

Это как-то все неправильно, я чувствую. Есть лучший способ сделать это?

Исходный код для этого ToyLang пример на github.

Рекомендации:

• Напечатаны финальные переводчики Tagless Олега Киселева
• Предиктивный полиморфизм, вариант использования by augustss
• Почему Free Monads Matter от Габриэля Гонсалеса
• Финальное кодирование без тегов в Haskell от JP Royo Sales