How to use the Reader Monad when traversing an Abstract Syntax Tree

Question

I have an abstract syntax tree in haskell made from Parsec. I want to be able to query its structure while traversing it at the same time in order to translate it into intermediate code. For example, I need to know how many parameters any given function of my AST takes in order to make this translation. What I am currently doing is passing in the AST to every single function so I can call it whenever I need to do a lookup and I have helper functions in another file to do the lookups for me. This is polluting my type signatures. Especially when I begin to add more things like an accumulator.

Instead of passing in the AST to every function I've heard this would be a good job for the Reader Monad (for state that doesn't change, the AST) and the State Monad (for state that does change, the accumulator).

How can I take the ast out of the IO monad (gulp) and use it in a Reader Monad to do global lookups?

main = do
  putStrLn "Please enter the name of your jack file (i.e. Main)"
  fileName <- getLine
  file <- readFile (fileName++".jack")
  let ast = parseString file
  writeFile (fileName++".xml") (toClass ast) --I need to query this globally
  putStrLn $  "Completed Parsing, " ++ fileName ++ ".vm created..."

type VM = String

toClass :: Jack -> VM
toClass c = case c of
   (Class ident decs) ->
     toDecs decs 

toDecs ::[Declaration] -> VM -- I don't want to add the ast in every function arg...
toDecs [] = ""
toDecs (x:xs) = case x of
  (SubDec keyword typ subname params subbody) ->
    case keyword of
      "constructor" -> --use the above ast to query the # of local variables here...
    toSubBody subbody ++
    toDecs xs
  otherwise -> []

UPDATE on Reader Monad progress: I have transformed the above example into something like this: (see below). But now I'm wondering due to all this accumulation of string output, should I use a writer Monad as well? And if so, how should I go about composing the two? Should ReaderT encapsulate writer? or vice versa? Should I make a type that just accepts a Reader and a Writer without attempting to compose them as a Monad Transformer?

main = do
  putStrLn "Please enter the name of your jack file (i.e. Main)"
  fileName <- getLine
  file <- readFile (fileName++".jack")
  writeFile (fileName++".xml")  (runReader toClass $ parseString file)
  putStrLn $  "Completed Parsing, " ++ fileName ++ ".xml created..."

toClass = do   
  env <- ask
  case env of Class ident decs -> return $ toDecs decs env

toDecs [] = return ""
toDecs ((SubDec keyword typ subname params subbody):xs) = do
  env <- ask
  res <- (case keyword of
            "method" -> do return "push this 0\n"
            "constructor" -> do return "pop pointer 0\nMemory.alloc 1\n"
            otherwise -> do return "")
  return $ res ++ toSubBody subbody env ++ toDecs xs env
toDecs (_:xs) = do
  decs <- ask
  return $ toDecs xs decs

toSubBody (SubBodyStatement states) = do
    return $ toStatement states
toSubBody (SubBody _ states) = do
    return $ toStatement states

http://hpaste.org/83595 --for declarations

You have found a very appropriate opportunity to use the reader monad. Indeed, you don't want to pass around the AST all the time. However, in your sample code, I can't see any (and I expected multiple) functions taking in a AST. Maybe you can paste code with less details of your domain? — Tarrasch
Tarrasch, one example would be the "constructor" case. Its result needs to be: "push pointer " ++ (show $ getFieldCount subname ast) ++ "\n" I have it outlined in the code above. — The Internet
in toDecs you bind res, but never use it. I'm not sure if thats a mistake or a typo. Also, what is the type of toDecs? In the first 2 cases it takes 1 input, but in the 3rd it takes 2. It would be much easier to help if you provided a code fragment that compiles (ie. with the data definitions for Class, SubDec, SubBody etc...) — cdk
Chris, you are exactly right. I forgot to add res to the return expression. I've added an hpaste of all my declarations. hpaste.org/83595 — The Internet

J. Abrahamson J. Abrahamson · Accepted Answer · 2013-03-06T16:28:25

Without knowing a bit more about the Jack and Declaration types it's hard to see how to transform it into a Reader monad. If the idea is to perform a "map" or a "fold" over something while having the ast :: Jack object in scope, you might write

f :: [Declaration] -> Reader Jack [Something]
f decls = mapM go decls where 
  go :: Declaration -> Reader Jack Something
  go (SubDec keyword typ subname params subbody) =
    case keyword of
      "constructor" -> do
        ast <- ask
        return (doSomething subbody ast)

and then execute it in context with your ast as runReader (f decls) ast.

How to use the Reader Monad when traversing an Abstract Syntax Tree

1 Answers