haskell - 如何在我的 LISP 中实现宏系统

Question

我正在根据在 48 小时内为自己编写一个方案编写自己的 LISP。 (代码是 here。)作为最后一个练习，我想实现宏。考虑到我将表达式表示为不可变数据类型的列表，如何做到这一点。这可以简单地在 LISP 本身中完成，还是我必须在 Haskell 中实现一些功能？

我目前的实现是用 Haskell 编写的，几乎是这样工作的:

• 解析输入并将其转换为表达式列表
• 评估表达式并替换它直到它是一个表达式
• 返回那个表达式并打印出来

表达式在 Haskell 中是这样表示的:

data Expr
  = Sym String
  | List [Expr]
  | Num Int
  | Str String
  | Bool Bool
  | Func Env [String] Expr
  | Prim ([Expr] -> ErrorOr Expr)
  | Action ([Expr] -> IOErrorOr Expr)

好的，现在进入真正的问题。宏不会评估其参数，而是通过将参数“放置”在表单中来转换为表达式。返回可以作为引用列表评估或返回的有效表达式。我正在考虑通过一个特殊的评估函数来实现这一点，该函数只评估宏形式的符号。虽然这是如何实现的，但我很难理解。正确的解决方案感觉我应该通过用参数替换其中的符号来“简单地”修改表单，但由于 Haskell 的不变性，这是不可能的。

所以，Clojure似乎已经在 Lisp 本身中实现了宏。我无法解释 Clojure 的解决方案，但如果可以做到，感觉比在 Haskell 中做要容易一些。我不知道 macroexpand1(which macroexpand call) 做了什么，它是否从 Clojure 的实现中调用了一些函数？如果是这样，那么我仍然必须在 Haskell 中实现它。

如果我们看看函数是如何求值的:

eval env (List (op:args)) = do
  func <- eval env op
  args <- mapM (eval env) args
  apply func args

apply :: Expr -> [Expr] -> IOErrorOr Expr
apply (Prim func) args = liftToIO $ func args
apply (Action func) args = func args
apply (Func env params form) args =
  case length params == length args of
    True -> (liftIO $ bind env $ zip params args)
        >>= flip eval form
    False -> throwError . NumArgs . toInteger $ length params
apply _ _ = error "apply"

所以，如果我想实现一个宏系统，那么我可能会删除参数的评估部分，然后将宏参数绑定(bind)到它的参数，并有一个特殊的评估，它只评估表单中的每个符号，返回一个将参数放入其中的新形式。这是我无法实现的，我什至不确定逻辑是否正确。

我知道这个问题很广泛，可以更简单地问“我如何在用 Haskell 编写的 LISP 实现中实现宏系统”

Answer 1

您可以尝试阅读 Structure and Implementation of Computer Programs 中的解释器实现。您清楚地显示的 eval 函数仅适用于默认 评估规则，而不适用于本书所称的特殊形式。

一个普通的 Lisp eval 函数看起来更像这样:

eval env expr@(List _)
    | isSpecialForm env expr = evalSpecial env expr
    | otherwise = evalApplication env expr

evalApplication env (op:args) = do
  func <- eval env op
  args <- mapM (eval env) args
  apply func args

evalSpecial env expr@(List (op:args))
    | isMacro env op = eval env (macroExpand env expr)
    | otherwise = case op of
                    "lambda" -> ...
                    "if" -> ...
                    -- etc.