问题哈斯克尔的祖父悖论

我正在尝试为我在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 从...返回 Map.lookup 必须进行评估以查看要采用的路径。

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

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

9492

2018-04-02 20:11

起源

答案:

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

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

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

2018-04-02 21:10

非常好！这也解决了我在名称解析失败时如何重写AST的另一个问题。你只需要替换Def (error "lookup failed")。 - pat

答案:

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

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

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

2018-04-02 21:10

非常好！这也解决了我在名称解析失败时如何重写AST的另一个问题。你只需要替换Def (error "lookup failed")。 - pat

我没有经过深思熟虑的答案，但有一个想法。你在AST上的单次传递将获取所有Def并产生一个（Map Symbol _），我想知道相同的AST传递是否可以获取所有的使用并生成（设置符号）以及延迟查找。

之后，您可以非常安全地将Map键中的符号与Set中的符号进行比较。如果Set中没有任何内容，那么您可以报告所有这些符号都是错误。如果Set中没有任何Def'd符号，则可以警告未使用的符号。

2018-04-02 20:48

问题 哈斯克尔的祖父悖论

答案:

答案:

热门问题

问题哈斯克尔的祖父悖论