Haskell 在递归函数中标记项目

Question

我对 Haskell 和一般的函数式编程还很陌生，所以如果问题看起来简单或愚蠢，请原谅。

我有一个用于生成抽象语法树的简单语言的解析器。为了扁平化 AST（将 while 和 if 语句转换为跳转），我需要将标签放在树中。问题是我不知道下一个标签应该是什么（我还在命令式地思考，因为如果我有状态，none这将是一个问题）。

我目前拥有的功能如下：

transform :: Stmt -> FStmt
transform (Seq stmt) = FSeq (map transform stmt)
transform (Assign var val) = FAssign var val
transform (While cond stmt) = FWhile "label1" (Jumpf cond "label2") (transform stmt) (Jump "label1") "label2"
transform (If cond stmt1 stmt2) = FIf (Jumpf cond "label") (transform stmt1) "label" (transform stmt2)

在其当前状态下，函数 "flattens" AST，但不会尝试放置正确的标签（它为每个构造使用相同的字符串）。

基本上问题是在顺序语句的情况下（每个程序都是顺序语句）我想不出一种方法来传递应该在标签中使用的下一个值。

提前致谢。

Answer 1

如果我对你的问题的理解正确，你可以向函数添加一个额外的参数 free-index，如下所示：

transform :: Stmt -> FStmt
transform = snd . transform' 0

transform' :: Int -> Stmt -> (Int, FStmt)
transform' freeIdx (Seq stmt) = (freeIdx', FSeq stmt')
  where
    (freeIdx', stmt') = mapAccumL transform' freeIdx stmt
transform' freeIdx (Assign var val) = (freeIdx, FAssign var val)
transform' freeIdx (While cond stmt) =
    (freeIdx', FWhile label1 (Jumpf cond label2) stmt' (Jump label1) label2)
  where
    label1 = "label" ++ show freeIdx
    label2 = "label" ++ show (freeIdx + 1)
    (freeIdx', stmt') = transform' (freeIdx + 2) stmt
transform' freeIdx (If cond stmt1 stmt2) =
    (freeIdx'', FIf (Jumpf cond label) stmt1' label stmt2')
  where
    label = "label" ++ show freeIdx
    (freeIdx', stmt1') = transform' (freeIdx + 1) stmt1
    (freeIdx'', stmt2') = transform' freeIdx' stmt2

但是如果你知道State monad，你可以这样设计：

transform :: Stmt -> FStmt
transform = flip evalState 0 . transform'

transform' :: Stmt -> State Int FStmt
transform' (Seq stmt) = FSeq <$> mapM transform stmt
transform' (Assign var val) = return $ FAssign var val
transform' (While cond stmt) = do
    label1 <- freeLabel
    label2 <- freeLabel
    stmt' <- transform' stmt
    return $ FWhile label1 (Jumpf cond label2) stmt' (Jump label1) label2
transform' (If cond stmt1 stmt2) = do
    label <- freeLabel
    stmt1' <- transform' stmt1
    stmt2' <- transform' stmt2
    return $ FIf (Jumpf cond label) stmt1' label stmt2'

freeLabel :: State Int String
freeLabel = do
    i <- get
    put $ i + 1
    return $ "label" ++ show i

Haskell 在递归函数中标记项目

Haskell labelling items in recursive function

haskell

abstract-syntax-tree