哈斯克尔的祖父悖论

Question

我正在尝试为我正在Haskell中编写的编译器编写一个重命名器.

重命名器扫描AST以查找符号DEF,它将其输入符号表,以及符号USE,它通过查看符号表来解析.

在这种语言中,使用可以在defs之前或之后使用,因此看起来需要2遍策略; 一次通过查找所有defs并构建符号表,第二次用于解决所有用途.

但是,由于Haskell是懒惰的(像我一样),我认为我可以打结,并在实际构建之前将重命名符号表传递给最终符号表.只要我保证实际构建它,这很好.在命令式编程语言中,这就像回传邮件一样.这在Haskell中有效,但必须注意不要引入时间悖论.

这是一个简洁的例子:

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
         ]

这是打结的线:

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

运行符号表存储在其中MonadState,RWS最终符号表存储在MonadReader.

在上述例子中,我有3个版本rename1M为UseS(2注释).在第一种形式,它工作正常.

如果您注释掉第一个rename1M Use,并取消注释第二个,则程序不会终止.然而,在精神上,它与第一种形式没有区别.区别在于它有两个return而不是一个,因此必须对Maybe返回的from Map.lookup进行求值以查看要采用的路径.

第三种形式是我真正想要的形式.如果我找不到符号,我想抛出一个错误.但是这个版本也没有终止.在这里,时间悖论是显而易见的; 关于符号是否会在表格中的决定会影响它是否会在表格中...

所以,我的问题是,是否有一种优雅的方式来做第三个版本所做的事情(抛出错误)而不会遇到悖论？发送错误MonadWriter而不允许查找更改路径？两次通过？

Answer 1

发生错误时你真的必须中断执行吗？另一种方法是记录错误.绑定结后,您可以检查错误列表是否为空.我过去采用过这种方法.

-- 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

这不会产生与惰性相关的非终止问题,因为符号表的内容不受查找是否成功的影响.