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.

Did you read any tutorials such as [this one](https://wiki.haskell.org/State_Monad) or [this one](https://mmhaskell.com/monads-5)? What point did you get stuck at? Did you look at the [haddock](https://www.stackage.org/haddock/lts-13.23/transformers-0.5.6.2/Control-Monad-Trans-State-Strict.html) documentation? Related: [Stuck in the State Monad](https://stackoverflow.com/q/14516835/2682729) — typesanitizer, May 25 '19 at 22:52
I did read some tutorials and various references. I think I understand how to implement a simple counter but not sure how to use it in my function. (edited the post with a little more clarification) — Bilentor, May 25 '19 at 23:02

typesanitizer · Accepted Answer · 2019-05-25T23:59:07.783

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.

Unique id/counter in Haskell

1 Answers1