Макросы как fexpr: expand-macro и раскрытие до упора

Макрос это программа, которая пишет программу. В lishp макрос это fexpr: получает невычисленные аргументы, строит из них новый код, и этот код вычисляет вызывающий. Разбираем тип Macro, проверку “это макрос” до eval аргументов, expandMacro (связывание невычисленных аргументов, прогон тела, восстановление окружения), expand-macro и expandAll (раскрытие формы до упора). Портируем macro_integration_test из эталона. И разбираем, чем fexpr отличается от Template Haskell и от гигиеничных макросов.

Идея

Собери в голове три способа, которыми наш вычислитель обрабатывает вызов. Функция вычисляет аргументы, потом своё тело. Спец-форма встроена в eval и сама решает, что вычислять. Макрос делает третье: получает аргументы невычисленными, строит из них новый код, и этот код вычисляет уже вызывающий.

Ключевое слово тут “новый код”. Макрос работает на этапе раскрытия, до исполнения: он берёт форму (when c body), превращает её в форму (if c (do body) nil), и дальше eval исполняет уже результат. Программа, которая пишет программу. Из этого растёт почти вся выразительность Lisp: cond, when, and, or в нашей стандартной библиотеке (урок 24) это макросы, а не встроенные конструкции. И всё это возможно ровно потому, что код это LishpVal, обычные данные, которые макрос строит теми же cons и list, что и любой список.

Тип Macro и проверка до eval

Macro несёт параметры, варьируемый хвост и тело, как лямбда, но без захваченного окружения (он работает в окружении вызова). Создаётся он веткой evalSpecial, как и lambda:

  SfMacro -> with2 $ \argsList body -> do
    (ps, var) <- parseParams "macro" argsList
    pure (Macro ps var body)

А вот где макрос особенный: проверка на него стоит в самом начале eval, до того как аргументы вообще тронуты. Если голова вызова это символ, связанный с Macro, мы не идём обычным путём (который вычислил бы аргументы), а раскрываем макрос и вычисляем то, что он построил:

eval :: Env -> LishpVal -> Eval LishpVal
eval env val = do
  macroInfo <- case val of
    Pair (Sym name) _ -> do
      bound <- liftIO (getVar env name)
      pure $ case bound of
        Just (Macro ps var body) -> Just (ps, var, body)
        _                        -> Nothing
    _ -> pure Nothing
  case macroInfo of
    Just (ps, var, body) -> expandMacro env ps var body (cdrOf val) >>= eval env
    Nothing              -> evalExpanded env val      -- обычный путь из уроков 18-22
  where
    cdrOf (Pair _ t) = t
    cdrOf _          = Nil

Прочитай последнюю развилку вслух: если голова это макрос, сперва expandMacro (получим код), потом eval env этого кода. Вот почему аргументы макроса не вычисляются: до evalExpanded, где живёт обычное правило вызова, дело просто не доходит.

expandMacro и expandAll

Раскрытие это сердце механизма. expandMacro связывает параметры с невычисленными аргументами прямо в текущем окружении, прогоняет тело (оно и строит новый код), а потом восстанавливает окружение, чтобы временные связки параметров не протекли наружу:

expandMacro :: Env -> [String] -> Maybe String -> LishpVal -> LishpVal -> Eval LishpVal
expandMacro env params variadic body argsList = do
  let argVals = properElems argsList            -- аргументы как есть, НЕ вычислены
  -- (проверка арности опущена для краткости)
  savedParams <- liftIO $ forM (zip params argVals) $ \(p, a) -> do
    old <- getVar env p                          -- запомнить прежнее значение имени
    defineVar env p a                            -- связать параметр с сырым аргументом
    pure (p, old)
  result <- liftIO (runExceptT (eval env body))  -- прогнать тело: оно строит код
  liftIO $ mapM_ (restore env) savedParams       -- вернуть окружение как было
  either throwError pure result
  where
    restore e (name, Just old) = defineVar e name old   -- было значение, вернуть
    restore e (name, Nothing)  = removeVar e name        -- не было, удалить

Узор “сохранить, подменить, восстановить” гарантирует гигиену по параметрам: после раскрытия имена cond, then, body исчезают, как будто их не было. Тут и пригодился removeVar из урока 21.

Спец-форма expand-macro показывает раскрытие, не исполняя результат, удобно для отладки. Она раскрывает форму до упора, пока голова остаётся макросом:

  ExpandMacro -> with1 (expandAll env)

expandAll :: Env -> LishpVal -> Eval LishpVal
expandAll env current = case current of
  Pair (Sym name) tl -> do
    bound <- liftIO (getVar env name)
    case bound of
      Just (Macro ps var body) -> expandMacro env ps var body tl >>= expandAll env  -- ещё раз
      _                        -> pure current
  _ -> pure current