Реализовать императивный оператор возврата в интерпретаторе

Я пытаюсь реализовать простой императивный язык в haskell.

Вообще говоря, моя программа представляет собой список операторов (таких как арифметическое выражение, если/тогда, блочный оператор). У моего оценщика простое состояние: стек лексических областей видимости. Лексическая область видимости — это просто сопоставление имени переменной со значением. Я нажимаю лексическую область видимости каждый раз, когда поток управления входит в функцию или блок, и всплываю, когда поток управления покидает функцию или блок.

Но я столкнулся с проблемой при попытке реализовать оценку оператора return. Что я пытаюсь сделать, так это создать специальный случай для оператора return в основной функции оценки (исходники здесь):

evalStatements :: [Statement] -> Eval MaybeValue

-- nothing to evaluate
evalStatements [] = return Nothing

-- current statement is 'return expr', 
-- evaluate expr and skip the rest of statements
evalStatements (ret@(ReturnStatement _expr):_stmts) =
    leaveLexEnv -- leave current lexical scope
    evalStatement ret >>= return

-- this is last statement in function, eval it and leave lexical scope
evalStatements [stmt] = do
    res <- evalStatement stmt
    leaveLexEnv -- leave current lexical scope
    return res

evalStatements (st:stmts) =
    evalStatement st >> evalStatements stmts >>= return

evalStatement :: Statement -> MaybeValue
evalStatement (ExprStatemet expr) = ...
evalStatement (IfThenStatement expr stmt) = ...

Но частный случай в функции evalStatements выглядит некрасиво для меня. И этот подход не работает с BlockStatement, потому что оператор return может находиться внутри этого блочного оператора. Другая проблема — восстановление стека лексических областей видимости, когда оператор return находится внутри нескольких вложенных блочных операторов.

Я думаю, что могу решить эту проблему, сохраняя какое-то дополнительное состояние в моем оценщике, но такой подход выглядит не очень хорошо. Что-то мне подсказывает, что здесь мне могут помочь продолжения. Но я пока не очень хорошо понимаю продолжения.

Каков наилучший способ решить эту проблему? Мне нужна только идея, общая концепция.

Спасибо.


person sergeyz    schedule 09.05.2014    source источник
comment
Согласно законам монады, (>>= return) всегда не работает. Вы должны удалить их, чтобы упростить код. И если это не неработоспособность, ваш экземпляр Monad для Eval неисправен.   -  person Carl    schedule 09.05.2014


Ответы (1)


Продолжения здесь могут работать, но это слишком. На самом деле продолжения почти всегда излишни для решения какой-либо конкретной проблемы.

Самое простое решение — поместить необходимую логику в ваш тип Eval. Если вы сделаете Eval содержащим конструктор для "это вычисление ранее возвращалось с этим значением", а затем сделаете ваши определения (>>) и (>>=) учитывающими это, все будет работать автоматически.

person Carl    schedule 09.05.2014
comment
Я использую трансформатор StateT для своего типа Eval. Похоже на type Eval a = StateT Environment Identity a. Должен ли я реализовать монаду Eval без преобразователей монад? - person sergeyz; 10.05.2014
comment
@sergeyz Это на самом деле не просто. Есть много вариантов, как это реализовать, и все они имеют разные компромиссы. Какой из них лучше, зависит от мелких деталей, которые трудно извлечь из краткого описания проблемы. Мой подход состоял бы в том, чтобы создать резервную копию и точно определить, какие операции Eval необходимо поддерживать, преобразовать их в DSL с рабочая библиотека, а затем выяснить, как написать интерпретатор для этого DSL. - person Carl; 10.05.2014
comment
спасибо за ссылку на статью, она мне очень пригодилась. - person sergeyz; 11.05.2014