haskell - Haskell中的祖父悖论

Question

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

重命名器扫描 AST 以查找符号 DEF，将其输入符号表和符号 USE，通过查找符号表来解决这些问题。

在这种语言中，uses 可以出现在 defs 之前或之后，因此似乎需要 2 pass 策略；一次通过查找所有定义并构建符号表，第二次解决所有用途。

然而，由于 Haskell 是懒惰的(像我一样)，我想我可以在实际构建之前将重命名器传递给最终的符号表。只要我 promise 实际构建它就可以了。在命令式编程语言中，这就像及时发送消息一样。这在 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对于 Use s(2 被注释掉)。在第一种形式中，它工作正常。

如果您注释掉第一个 rename1M Use ，并取消注释第二个，程序不会终止。然而，在精神上，它与第一种形式没有什么不同。不同的是它有两个 return s 而不是一个，所以 Maybe从 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

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