Grandfather Paradox in Haskell

Question

I'm trying to write a renamer for a compiler that I'm writing in Haskell.

The renamer scans an AST looking for symbol DEFs, which it enters into a symbol table, and symbol USEs, which it resolves by looking in the symbol table.

In this language, uses can come before or after defs, so it would seem that a 2 pass strategy is required; one pass to find all the defs and build the symbol table, and a second to resolve all the uses.

However, since Haskell is lazy (like me), I figure I can tie-the-knot and pass the renamer the final symbol table before it is actually built. This is fine as long as I promise to actually build it. In an imperative programming language, this would be like sending a message back in time. This does work in Haskell, but care must be taken to not introduce a temporal paradox.

Here's a terse example:

module Main where

import Control.Monad.Error
import Control.Monad.RWS
import Data.Maybe ( catMaybes )
import qualified Data.Map as Map
import Data.Map ( Map )

type Symtab = Map String Int

type RenameM = ErrorT String (RWS Symtab String Symtab)

data Cmd = Def String Int
         | Use String

renameM :: [Cmd] -> RenameM [(String, Int)]
renameM = liftM catMaybes . mapM rename1M

rename1M :: Cmd -> RenameM (Maybe (String, Int))
rename1M (Def name value) = do
  modify $ \symtab -> Map.insert name value symtab
  return Nothing
rename1M (Use name) = return . liftM ((,) name) . Map.lookup name =<< ask
--rename1M (Use name) =
--  maybe (return Nothing) (return . Just . (,) name) . Map.lookup name =<< ask
--rename1M (Use name) =
--  maybe (throwError $ "Cannot locate " ++ name) (return . Just . (,) name) . Map.lookup name =<< ask

rename :: [Cmd] -> IO ()
rename cmds = do
  let (result, symtab, log) = runRWS (runErrorT $ renameM cmds) symtab Map.empty
  print result

main :: IO ()
main = do
  rename [ Use "foo"
         , Def "bar" 2
         , Use "bar"
         , Def "foo" 1
         ]

This is the line where the knot is tied:

  let (result, symtab, log) = runRWS (runErrorT $ renameM cmds) symtab Map.empty

The running symbol table is stored in the MonadState of the RWS, and the final symbol table is stored in the MonadReader.

In the above example, I have 3 versions of rename1M for Uses (2 are commented out). In this first form, it works fine.

If you comment out the first rename1M Use, and uncomment the second, the program does not terminate. However, it is, in spirit, no different than the first form. The difference is that it has two returns instead of one, so the Maybe returned from Map.lookup must be evaluated to see which path to take.

The third form is the one that I really want. I want to throw an error if I can't find a symbol. But this version also does not terminate. Here, the temporal paradox is obvious; the decision about whether the the symbol will be in the table can affect whether it will be in the table...

So, my question is, is there an elegant way to do what the third version does (throw an error) without running into the paradox? Send the errors on the MonadWriter without allowing the lookup to change the path? Two passes?

Answer 1

Do you really have to interrupt execution when an error occurs? An alternative approach would be to log errors. After tying the knot, you can check whether the list of errors is empty. I've taken this approach in the past.

-- I've wrapped a writer in a writer transformer.  You'll probably want to implement it differently to avoid ambiguity
-- related to writer methods.
type RenameM = WriterT [RenameError] (RWS Symtab String Symtab)

rename1M (Use name) = do
  symtab_entry <- asks (Map.lookup name)
  -- Write a list of zero or more errors.  Evaluation of the list is not forced until all processing is done.
  tell $ if isJust symtab_entry then [] else missingSymbol name
  return $ Just (name, fromMaybe (error "lookup failed") symtab_entry)

rename cmds = do
  let ((result, errors), symtab, log) = runRWS (runWriterT $ renameM cmds) symtab Map.empty
  -- After tying the knot, check for errors
  if null errors then print result else print errors

This does not produce laziness-related nontermination problems because the contents of the symbol table are not affected by whether or not a lookup succeeded.

Answer 2

I don't have a well thought out answer, but one quick thought. Your single pass over the AST takes all the Def and produces a (Map Symbol _), and I wonder if the same AST pass can take all the Use and produce a (Set Symbol) as well as the lazy lookup.

Afterwards you can quite safely compare the Symbols in the keys of the Map with the Symbols in the Set. If the Set has anything not in the Map then you can report all of those Symbols are errors. If any Def'd Symbols are not in in the Set then you can warn about unused Symbols.