尝试将CPS应用于口译员 [英] Trying to apply CPS to an interpreter

问题描述

我试图使用CPS来简化我的Python解释器中的控制流实现。具体来说，在执行 return / break / continue 时，I必须手动存储状态并放开，这很乏味。我读过以这种方式实现异常处理非常棘手。我想要的是每个 eval 函数都能够将控制流引导至下一条指令或完全指向其他指令。

有一些比我更有经验的人建议寻找CPS作为正确处理这种情况的一种方法。我真的很喜欢它是如何简化解释器中的控制流程的，但我不确定我为了实现这个目的需要多少实际操作。

1. 我需要在AST上运行CPS转换吗？我应该把这个AST降低到一个更小的IR，然后将其转换吗？

我需要更新评估者以接受无处不在的成功延续？ （我假设是这样）。

我想我通常会理解CPS变换：目标是线程化包括所有表达式。

我也有点困惑 Cont monad是否适合在这里，作为宿主语言是Haskell。

编辑：这里是AST的缩写版本。它是Python语句，表达式和内置值的1-1映射。

  data语句
 =赋值表达式表达式
 |表达式表达
 |打破
 |表达式[语句] 
 
数据表达式
 |属性表达式字符串
 |常量值
 
数据值
 =字符串字符串
 |整数
 |无
  

要评估语句，我使用 eval ：

  eval（Assignment（Variable var）expr）= do 
 value < -  evalExpr expr 
 updateSymbol var value 
 
 eval（Expression e）= do 
 _<  -  evalExpr e 
 return（）
  

为了评估表达式，我使用 evalExpr ：

  evalExpr（属性目标名称）= do 
接收者<  -  evalExpr目标
属性<  -  getAttr名称接收者
 
的属性属性v  - >返回v 
无 - >失败$无属性++名称
 
 evalExpr（常量c）=返回c 
  

整个事情的动机是执行休息所需的诡计。 break定义是合理的，但它对while定义的作用有点多：

pre $ e $ e $ eval（Break）= $
env< - 当（loopLevel env <= 0）时获得
（失败只能在循环中中断）
放env {flow = Breaking}

eval（while condition block）= do
setup
loop
cleanup

where
setup = do
env< - get
let level = loopLevel env
put env {loopLevel = level + 1}

loop = do
env< - get
result< - 当（isTruthy result&& flow env == Next）时，evalExpr条件
$ do
evalBlock block

- 非常丑陋！继续吃。
updatedEnv< - 当$（flow updatedEnv ==持续）$ put updatedEnv {flow = Next}

循环

cleanup = do $时获得
b $ b env< - get
let level = loopLevel env
put env {loopLevel = level - 1}

案例流程env of
Breaking - > put env {flow = Next}
继续 - > put env {flow = Next}
_ - > return（）

我相信在这里可以做更多简化，但核心问题是在某处填塞状态并手动退出。我希望CPS能够让我把账簿（比如循环退出点）写入状态，并在需要时使用它们。

我不喜欢语句和表达式，并担心它可能会使CPS转换更多的工作。

解决方案

这终于给了我一个很好的借口， code> ContT ！

以下是一种可能的方式：store（在 Reader 包装在 ContT ）继续退出当前（最内层）循环：



  newtype M ra = M {unM :: ContT r（ReaderT（M r（））（StateT（Map Id Value）IO））a} 
 derived（Functor，Applicative，Monad $ MonadReader（M r（）），MonadCont，MonadState（Map Id值）
，MonadIO 
）
 
 runM :: M aa  - > IO a 
 runM m = evalStateT（runReaderT（runContT（unM m）return）（errornot in a loop））M.empty 
 
 withBreakHere :: M r（） - > ; M r（）
 withBreakHere act = callCC $ \break  - > local（const $ break（））act 
 
 break :: M r（）
 break = join请求
  

（我还添加了 IO 以便在我的玩具解释器中打印，并且 State（Map Id值）为变量）。



使用此设置，您可以编写 Break 和 as：

  eval Break = break 
 eval条件块）= withBreakHere $ fix $ \loop  - >做
结果<  -  evalExpr条件
除非（isTruthy result）
 break 
 evalBlock block 
 loop 
  

以下是供参考的完整代码：



  { - ＃LANGUAGE GeneralizedNewDeriving＃ - } 
模块Interp其中
 
导入前导隐藏（断开）
导入Control.Applicative 
导入Control.Monad.Cont 
导入控制。 Monad.State 
导入Control.Monad.Reader 
导入Data.Function 
导入Data.Map（映射）
将限定的Data.Map导入为M 
导入数据。也许
 
类型Id =字符串
 
数据语句
 =打印表达式
 |分配ID表达
 |打破
 |表达式[声明] 
 |如果表达式[语句] 
导出显示
 
数据表达式
 = Var Id 
 |常量值
 |添加表达式表达
 |不表达
导出显示
 
数据值
 =字符串字符串
 |整数
 |无
导出显示
 
数据Env = Env {loopLevel :: Int 
，flow :: Flow 
} 
 
数据流
 =打破
 |继续
 |下一个
导出Eq 
 
 newtype M ra = M {unM :: ContT r（ReaderT（M r（））（StateT（Map Id Value）IO））a} 
派生（Functor，Applicative，Monad 
，MonadReader（M r（）），MonadCont，MonadState（Map Id值）
，MonadIO 
）
 
 runM :: M aa  - > IO a 
 runM m = evalStateT（runReaderT（runContT（unM m）return）（errornot in a loop））M.empty 
 
 withBreakHere :: M r（） - > ; M r（）
 withBreakHere act = callCC $ \break  - > local（const $ break（））act 
 
 break :: M r（）
 break = join请求
 
 evalExpr ::表达式 - >价值
 evalExpr（常量val）=返回值
 evalExpr（Var v）=从$可能会得到$ err错误。 M.lookup v 
其中
 err =错误$ unwords [变量不在范围内：，show v] 
 evalExpr（Add e1 e2）= do 
 Int val1< -  evalExpr e1 
 Int val2<  -  evalExpr e2 
 return $ Int $ val1 + val2 
 evalExpr（Not e）= do 
 val<  -  evalExpr e 
返回$ if isTruthy val then None其他Int 1 
 
 isTruthy（String s）= not $ null s 
 isTruthy（Int n）= n / = 0 
 isTruthy None = False 
 
 evalBlock = mapM_ eval 
 
 eval :: Statement  - > M r（）
 eval（Assign ve）= do 
 val < -  evalExpr e 
修改$ M.insert v val 
 eval（Print e）= do 
 val<  -  evalExpr e 
 liftIO $ print val 
 eval（如果cond block）= do 
 val<  -  evalExpr cond 
当（isTruthy val）$ 
 evalBlock block 
 eval Break = break 
 eval（while condition block）= withBreakHere $ fix $ \loop  - >做
结果<  -  evalExpr条件
除非（isTruthy result）
 break 
 evalBlock block 
 loop 
  

以下是一个简洁的测试示例：



  prog = [Assign i$ Constant $ Int 10 
，While（Vari）[Print（Vari）
，Assigni（Add（Vari）（Constant $ Int -1）））
，赋值j$常数$ Int 10 
，While（Varj）[Print（Varj）
，赋值j（Add （Varj）（常量$ Int（-1）））
，If（不加（Varj）（常量$ Int（-4））））[Break] 
 ] 
] 
，打印$常量$字符串完成
] 
  







  i = 10 
而我：
 print i 
i =我 -  1 
j = 10 
 while j：
 print j 
j = j  -  1 
 if j == 4：
 break 
  

因此它会打印

  10 10 9 8 7 6 5 
 9 10 9 8 7 6 5 
 8 10 9 8 7 6 5 
 ... 
 1 10 9 8 7 6 5 
  




I'm trying to use CPS to simplify control-flow implementation in my Python interpreter. Specifically, when implementing return/break/continue, I have to store state and unwind manually, which is tedious. I've read that it's extraordinarily tricky to implement exception handling in this way. What I want is for each eval function to be able to direct control flow to either the next instruction, or to a different instruction entirely.

Some people with more experience than me suggested looking into CPS as a way to deal with this properly. I really like how it simplifies control flow in the interpreter, but I'm not sure how much I need to actually do in order to accomplish this.

1. Do I need to run a CPS transform on the AST? Should I lower this AST into a lower-level IR that is smaller and then transform that?

2. Do I need to update the evaluator to accept the success continuation everywhere? (I'm assuming so).

I think I generally understand the CPS transform: the goal is to thread the continuation through the entire AST, including all expressions.

I'm also a bit confused where the Cont monad fits in here, as the host language is Haskell.

Edit: here's a condensed version of the AST in question. It is a 1-1 mapping of Python statements, expressions, and built-in values.

data Statement
    = Assignment Expression Expression
    | Expression Expression
    | Break
    | While Expression [Statement]

data Expression
    | Attribute Expression String
    | Constant Value

data Value
    = String String
    | Int Integer
    | None

To evaluate statements, I use eval:

eval (Assignment (Variable var) expr) = do
    value <- evalExpr expr
    updateSymbol var value

eval (Expression e) = do
    _ <- evalExpr e
    return ()

To evaluate expressions, I use evalExpr:

evalExpr (Attribute target name) = do
    receiver <- evalExpr target
    attribute <- getAttr name receiver
    case attribute of
        Just v  -> return v
        Nothing -> fail $ "No attribute " ++ name

evalExpr (Constant c) = return c

What motivated the whole thing was the shenanigans required for implementing break. The break definition is reasonable, but what it does to the while definition is a bit much:

eval (Break) = do
    env <- get
    when (loopLevel env <= 0) (fail "Can only break in a loop!")
    put env { flow = Breaking }

eval (While condition block) = do
    setup
    loop
    cleanup

    where
        setup = do
            env <- get
            let level = loopLevel env
            put env { loopLevel = level + 1 }

        loop = do
            env <- get
            result <- evalExpr condition
            when (isTruthy result && flow env == Next) $ do
                evalBlock block

                -- Pretty ugly! Eat continue.
                updatedEnv <- get
                when (flow updatedEnv == Continuing) $ put updatedEnv { flow = Next }

                loop

        cleanup = do
            env <- get
            let level = loopLevel env
            put env { loopLevel = level - 1 }

            case flow env of
                Breaking    -> put env { flow = Next }
                Continuing  -> put env { flow = Next }
                _           -> return ()

I am sure there are more simplifications that can be done here, but the core problem is one of stuffing state somewhere and manually winding out. I'm hoping that CPS will let me stuff book-keeping (like loop exit points) into state and just use those when I need them.

I dislike the split between statements and expressions and worry it might make the CPS transform more work.

解决方案

This finally gave me a good excuse to try using ContT!

Here's one possible way of doing this: store (in a Reader wrapped in ContT) the continuation of exiting the current (innermost) loop:

newtype M r a = M{ unM :: ContT r (ReaderT (M r ()) (StateT (Map Id Value) IO)) a }
              deriving ( Functor, Applicative, Monad
                       , MonadReader (M r ()), MonadCont, MonadState (Map Id Value)
                       , MonadIO
                       )

runM :: M a a -> IO a
runM m = evalStateT (runReaderT (runContT (unM m) return) (error "not in a loop")) M.empty

withBreakHere :: M r () -> M r ()
withBreakHere act = callCC $ \break -> local (const $ break ()) act

break :: M r ()
break = join ask

(I've also added IO for easy printing in my toy interpreter, and State (Map Id Value) for variables).

Using this setup, you can write Break and While as:

eval Break = break
eval (While condition block) = withBreakHere $ fix $ \loop -> do
    result <- evalExpr condition
    unless (isTruthy result)
      break
    evalBlock block
    loop

Here's the full code for reference:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
module Interp where

import Prelude hiding (break)
import Control.Applicative
import Control.Monad.Cont
import Control.Monad.State
import Control.Monad.Reader
import Data.Function
import Data.Map (Map)
import qualified Data.Map as M
import Data.Maybe

type Id = String

data Statement
    = Print Expression
    | Assign Id Expression
    | Break
    | While Expression [Statement]
    | If Expression [Statement]
    deriving Show

data Expression
    = Var Id
    | Constant Value
    | Add Expression Expression
    | Not Expression
    deriving Show

data Value
    = String String
    | Int Integer
    | None
    deriving Show

data Env = Env{ loopLevel :: Int
              , flow :: Flow
              }

data Flow
    = Breaking
    | Continuing
    | Next
    deriving Eq

newtype M r a = M{ unM :: ContT r (ReaderT (M r ()) (StateT (Map Id Value) IO)) a }
              deriving ( Functor, Applicative, Monad
                       , MonadReader (M r ()), MonadCont, MonadState (Map Id Value)
                       , MonadIO
                       )

runM :: M a a -> IO a
runM m = evalStateT (runReaderT (runContT (unM m) return) (error "not in a loop")) M.empty

withBreakHere :: M r () -> M r ()
withBreakHere act = callCC $ \break -> local (const $ break ()) act

break :: M r ()
break = join ask

evalExpr :: Expression -> M r Value
evalExpr (Constant val) = return val
evalExpr (Var v) = gets $ fromMaybe err . M.lookup v
  where
    err = error $ unwords ["Variable not in scope:", show v]
evalExpr (Add e1 e2) = do
    Int val1 <- evalExpr e1
    Int val2 <- evalExpr e2
    return $ Int $ val1 + val2
evalExpr (Not e) = do
    val <- evalExpr e
    return $ if isTruthy val then None else Int 1

isTruthy (String s) = not $ null s
isTruthy (Int n) = n /= 0
isTruthy None = False

evalBlock = mapM_ eval

eval :: Statement -> M r ()
eval (Assign v e) = do
    val <- evalExpr e
    modify $ M.insert v val
eval (Print e) = do
    val <- evalExpr e
    liftIO $ print val
eval (If cond block) = do
    val <- evalExpr cond
    when (isTruthy val) $
      evalBlock block
eval Break = break
eval (While condition block) = withBreakHere $ fix $ \loop -> do
    result <- evalExpr condition
    unless (isTruthy result)
      break
    evalBlock block
    loop

and here's a neat test example:

prog = [ Assign "i" $ Constant $ Int 10
       , While (Var "i") [ Print (Var "i")
                         , Assign "i" (Add (Var "i") (Constant $ Int (-1)))
                         , Assign "j" $ Constant $ Int 10
                         , While (Var "j") [ Print (Var "j")
                                           , Assign "j" (Add (Var "j") (Constant $ Int (-1)))
                                           , If (Not (Add (Var "j") (Constant $ Int (-4)))) [ Break ]
                                           ]
                         ]
       , Print $ Constant $ String "Done"
       ]

which is

i = 10
while i:
  print i
  i = i - 1
  j = 10
  while j:
    print j
    j = j - 1
    if j == 4:
      break

so it will print

10 10 9 8 7 6 5
 9 10 9 8 7 6 5
 8 10 9 8 7 6 5
...
 1 10 9 8 7 6 5

这篇关于尝试将CPS应用于口译员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！