Парадокс Деда в Хаскелле

Я пытаюсь написать renamer для компилятора, который я пишу в 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 для Use (2 закомментированы). В этой первой форме он отлично работает.

Если вы закомментируете первый rename1M Use и раскомментируете второй, программа не завершится. Однако он по духу не отличается от первой формы. Разница в том, что он имеет два return вместо одного, поэтому Maybe, возвращаемый из Map.lookup, должен быть оценен, чтобы увидеть, какой путь принять.

Третья форма - та, которую я действительно хочу. Я хочу выбросить ошибку, если не могу найти символ. Но эта версия также не заканчивается. Здесь временный парадокс очевиден; решение о том, будет ли символ находиться в таблице, может повлиять на то, будет ли он в таблице...

Итак, мой вопрос в том, есть ли элегантный способ сделать то, что делает третья версия (выбросить ошибку), не запуская парадокса? Отправить ошибки на MonadWriter, не позволяя поиску изменить путь? Два прохода?

Ответ 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

Это не приводит к проблемам, связанным с нетерпением, связанными с лени, потому что содержимое таблицы символов не зависит от того, удалось ли выполнить поиск.

Ответ 2

У меня нет хорошо продуманного ответа, но одна мысль. Ваш единственный проход по AST принимает всю Def и создает (Символ карты _), и мне интересно, может ли тот же самый проход AST принять все Использование и произвести (Установить Символ), а также ленивый поиск.

Впоследствии вы можете совершенно спокойно сравнить символы в ключах карты с символами в наборе. Если в Set ничего нет на карте, вы можете сообщить обо всех этих Символах, это ошибки. Если какие-либо символы Def'd не включены в Set, вы можете предупредить об неиспользованных символах.