CODEWITHSUNDEEP
haskellmonadsabstract-syntax-tree
The Internet
The Internet

Reputation: 8123

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

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

Upvotes: 7

Views: 683

Answers (1)

J. Abrahamson
J. Abrahamson

Reputation: 74374

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.

Upvotes: 0

Related Questions