Unique id/counter in Haskell

Question

I am trying to generate some assembly instructions in Haskell and need to generate some unique ids to label sections for jmp instructions. I believe I could do this using a state monad but I am still new to Haskell and not super comfortable with State monad and need some help using it in this context.

Here is one of the examples where I'd need a unique id

generateExpression :: AST.Expr -> String
generateExpression (AST.BinOpExpr AST.Or e1 e2) =
            (generateExpression e1) ++
            "    cmpl    $0, %eax\n" ++
            "    je      _or_clause2\n" ++
            "    movl    $1, %eax\n" ++
            "    jmp     _or_end\n" ++
            "_or_clause2:\n" ++           -- need to use a unique id here instead of clause 2
            (generateExpression e2) ++
            "    cmpl    $0, %eax\n" ++
            "    movl    $0, %eax\n" ++
            "    setne   %al\n" ++
            "_or_end:\n"                  -- need to use a unique id here to label the end

Edit: I have read some tutorials on State Monad and can implement a simple counter such as

import Control.Monad.State

counter :: State Int Int
counter = do
    x <- get
    put (x+1)
    return x

runState counter 1 -- outputs (1,2) where the state has been incremented

which would keep track of a counter as the state. But I am not sure how to use this in my function where I need to keep a state around in recursive calls.

Answer 1

So the return type needs to have a State Int in it, it can't be String. The key thing is that you need to thread the State through. Here, I've used do notation as you seem comfortable with it.

counter :: State Int Int
counter = do
    n <- get
    put (n + 1)
    pure n

generateASM :: AST.Expr -> State Int String
generateASM (AST.BinOpExpr AST.Or e1 e2) = do
    e1ASM <- generateASM e1
    n <- counter
    e2ASM <- generateASM e2
    pure $
        e1ASM ++
        "    cmpl    $0, %eax\n" ++
        "    je      _or_clause" ++ show n ++ "\n" ++
        "    movl    $1, %eax\n" ++
        "    jmp     _or_end" ++ show n ++ "\n" ++
        "_or_clause" ++ show n ++ ":\n" ++ show n ++
        e2ASM ++
        "    cmpl    $0, %eax\n" ++
        "    movl    $0, %eax\n" ++
        "    setne   %al\n" ++
        "_or_end" ++ show n ++ ":\n"
generateASM (..) = .. -- other branches defined similarly...

generateASMFull :: AST.Expr -> String
generateASMFull e = evalState (generateASM e) 0

P.S. I haven't checked if your assembly logic is correct.