4

我正在 48 小时内根据为自己编写一个计划编写自己的 LISP。（代码在这里。）作为最后一个练习，我想实现宏。考虑到我将表达式表示为不可变数据类型的列表，如何做到这一点。这可以简单地在 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"

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

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

4

3 回答 3

3

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

一个普通的 Lispeval函数看起来更像这样：

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.
于 2013-05-11T23:31:13.820 回答
2

不，宏不能在 Lisp 本身中实现，这就是它们的全部意义所在。作为加载/编译/处理给定表达式的一部分，您必须根据其定义对每个宏调用进行宏扩展。

您将不得不更改您的eval实现以在未评估的参数上调用宏，并将结果反馈给eval（apply不像处理普通函数应用程序那样）。正如sepp2k评论中所建议的那样，您将宏表示为Func...表达式，但将它们保存在单独的环境中，其中仅存储宏。

另请参阅：惰性评估与宏

于 2013-05-11T17:13:33.850 回答
1

您不需要特殊版本的apply. 只需调用正则而不apply评估参数，然后调用.evalapply

于 2013-05-11T17:12:29.897 回答