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
