Haskell在递归函数中标记项目 [英] Haskell labelling items in recursive function

问题描述

我对Haskell和函数式编程通常都很陌生，所以如果问题看起来很简单或者很愚蠢，那么请原谅我。

我有一个简单语言的解析器，产生一个抽象语法树。为了扁平化AST（将while和if语句变成跳转），我需要在树中放置标签。问题是我不知道下一个标签应该是什么（我仍然认为是必要的，因为如果我有状态，这些都不会成为问题）。

到目前为止，我的功能如下：

  transform :: Stmt  - > FStmt 
 transform（Seq stmt）= FSeq（map transform stmt）
 transform（Assign var val）= FAssign var val 
 transform（While cond stmt）= FWhilelabel1（Jumpf cond （转换stmt1）label2）（转换stmt）（转换标签1）label2
转换（如果cond stmt1 stmt2）= FIf（跳转condlabel）（转换stmt1） b  

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

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

解决方案

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

  transform :: Stmt  - > FStmt 
 transform = snd。 transform'0 
 
 transform':: Int  - > Stmt  - > （Int，FStmt）
转换'freeIdx（seq stmt）=（freeIdx'，FSeq stmt'）
其中
（freeIdx'，stmt'）= mapAccumL转换'freeIdx stmt 
转换'freeIdx（Assign var val）=（freeIdx，FAssign var val）
 transform'freeIdx（While cond stmt）= 
（freeIdx'，FWhile label1（Jumpf cond label2）stmt'（Jump label1 ）label2）
其中
 label1 =label++显示freeIdx 
 label2 =label++ show（freeIdx + 1）
（freeIdx'，stmt'）=转换'（freeIdx + 2）stmt 
转换'freeIdx（如果cond stmt1 stmt2）= 
（freeIdx''，FIf（Jumpf cond label）stmt1'label stmt2'）
其中
 label =label++ show freeIdx 
（freeIdx'，stmt1'）= transform'（freeIdx + 1）stmt1 
（freeIdx''，stmt2'）= transform'freeIdx'stmt2 
  

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

  transform :: Stmt  - > FStmt 
 transform = flip evalState 0。变换'
 
变换':: 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 
标签<  -  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 
  

I am quite new to Haskell and functional programming in general, so excuse me if the question seems straightforward or silly.

I have a parser for a simple language that produces an abstract syntax tree. In order to flatten the AST (turn while and if statements into jumps) I need to put labels in the tree. The problem is that I do not know what the next label should be (I am still thinking imperatively, because if I had state, none of this would be a problem).

The function that I have so far is the following:

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)

In its current state, the function "flattens" the AST, but does not attempt to put the correct labels (it uses the same string for every construct).

Basically the problem is that in the case of a sequential statement (and every program is a sequential statement) I cannot think of a way to pass the next value that should be used in the labels.

Thank you in advance.

解决方案

If I understand correctly your problem, you can add to the function an extra parameter free-index like this:

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

But if you known State monad, you can design like this:

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在递归函数中标记项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！