Состояние и окружения: IORef, фреймы, def и set!

Чтобы def запоминал переменную между формами, интерпретатору нужна память. В этом уроке: IORef на отвлечённых примерах (изменяемая ячейка в чистом языке) и почему здесь не State, тип Env как фрейм плюс ссылка на родителя, def пишет в текущий фрейм, set! идёт по цепочке наружу до первого определения, removeVar, и REPL, который наконец помнит, что ты ввёл раньше.

Идея

До сих пор eval получал Env, но мы ни разу не сказали, что это. Пора: без окружения def не может запомнить переменную между формами, а (def x 5) потом x обязано вернуть 5.

Окружение это таблица “имя в значение” плюс ссылка на внешнее окружение. Резолв символа простой: ищем имя в своём фрейме, не нашли, идём к родителю, и так до самого верха. Цепочка фреймов и есть область видимости, это классическая модель окружений из третьей главы SICP. Когда функция (урок 22) создаёт для вызова новый фрейм поверх своего, получается вложенность, и переменные снаружи остаются видны, а локальные их перекрывают.

Отвлечённо: IORef

Окружение должно меняться: def добавляет имя, set! правит значение. В чистом Haskell мутации нет, но в IO есть изменяемая ячейка, IORef:

import Data.IORef

demo :: IO ()
demo = do
  ref <- newIORef (0 :: Int)   -- создать ячейку со значением 0
  writeIORef ref 10            -- перезаписать
  modifyIORef' ref (+ 5)        -- изменить функцией: теперь 15
  v <- readIORef ref           -- прочитать: 15
  print v

Почему IORef, а не State? Окружения образуют дерево с общими ссылками: дочерний фрейм держит ссылку на родителя, замыкание (урок 22) уносит ссылку на фрейм определения, и все они должны видеть одни и те же изменения. Прокинуть такое через State, где состояние это одно значение на весь поток, мучительно: пришлось бы вручную сшивать версии дерева. С IORef каждый фрейм это самостоятельная изменяемая ячейка, ссылки на неё разделяются естественно, а eval и так уже живёт в IO (из-за print и read), так что новой цены тут нет.

Тип Env

Фрейм это IORef от обычной Map, плюс необязательный родитель:

import Data.IORef (IORef)
import Data.Map.Strict (Map)

data Env = Env (IORef (Map String LishpVal)) (Maybe Env)

Создание фреймов: пустой верхний и пустой дочерний от заданного.

import Data.IORef (modifyIORef', newIORef, readIORef)
import qualified Data.Map.Strict as Map

-- свежее верхнее окружение, без родителя
newEnv :: IO Env
newEnv = (`Env` Nothing) <$> newIORef Map.empty

-- пустой дочерний фрейм поверх данного (так делается фрейм вызова функции)
childEnv :: Env -> IO Env
childEnv parent = (`Env` Just parent) <$> newIORef Map.empty

Резолв имени, тот самый проход вверх по цепочке:

-- найти имя, поднимаясь к родителям
getVar :: Env -> String -> IO (Maybe LishpVal)
getVar (Env frame parent) name = do
  m <- readIORef frame
  case Map.lookup name m of
    Just v  -> pure (Just v)
    Nothing -> maybe (pure Nothing) (`getVar` name) parent

Этот проход вверх по цепочке проще увидеть в движении, чем прочитать. Прогони резолв по фреймам: глобальный внизу, дочерний фрейм вызова сверху. Поиск стартует во внутреннем фрейме и идёт наружу, пока не найдёт имя, и тут же видно, как локальная переменная перекрывает внешнюю (shadowing).

def, set!, removeVar

Три операции записи, и разница между первыми двумя принципиальная. def всегда пишет в текущий фрейм (создаёт или перекрывает имя здесь). set! ищет существующее имя вверх по цепочке и меняет его там, где нашёл, а если нигде не нашёл, это ошибка.

-- определить имя в ТЕКУЩЕМ фрейме (перекрывая внешнее, если было)
defineVar :: Env -> String -> LishpVal -> IO ()
defineVar (Env frame _) name value = modifyIORef' frame (Map.insert name value)

-- присвоить СУЩЕСТВУЮЩЕМУ имени, ища вверх; False, если имя нигде не связано
setVar :: Env -> String -> LishpVal -> IO Bool
setVar (Env frame parent) name value = do
  m <- readIORef frame
  if Map.member name m
    then modifyIORef' frame (Map.insert name value) >> pure True
    else maybe (pure False) (\p -> setVar p name value) parent

-- удалить имя из текущего фрейма (пригодится для уборки после макроса, урок 23)
removeVar :: Env -> String -> IO ()
removeVar (Env frame _) name = modifyIORef' frame (Map.delete name)

containsVar :: Env -> String -> IO Bool
containsVar env name = maybe False (const True) <$> getVar env name

Теперь спец-формы def и set! из урока 20 дополняют evalSpecial. def вычисляет значение и кладёт его в текущий фрейм; set! сначала проверяет, что имя вообще связано, иначе ошибка:

  Define -> with2 $ \nameE valE -> case nameE of
    Sym name -> do
      v <- eval env valE
      liftIO (defineVar env name v)
      pure Nil                                  -- def возвращает nil
    _ -> throwError CannotDefineNonSymbol
  Set -> with2 $ \nameE valE -> case nameE of
    Sym name -> do
      bound <- liftIO (containsVar env name)
      if not bound
        then throwError (UndefinedVariable name)   -- set! на несвязанном это ошибка
        else do
          v <- eval env valE
          _ <- liftIO (setVar env name v)
          pure Nil
    _ -> throwError CannotSetNonSymbol

(В уроке 22 ветка Define обрастёт одной добавкой, чтобы заработала рекурсия. Пока хватает и этого.) И наконец ветка Sym в самом eval, которая раньше была заглушкой, теперь резолвит имя:

  Sym name ->
    liftIO (getVar env name) >>= maybe (throwError (UndefinedVariable name)) pure