javascript - 如何在JavaScript中的自定义LISP中编写宏扩展

Question

我有一个一般性的问题，我应该如何去创造适当的宏扩展函数或宏。
这是我的宏在嘴唇解释器中的定义（您可以在这里测试它https://jcubic.github.io/lips/）

function macro_expand(single) {
    return async function(code, args) {
        var env = args['env'] = this;
        async function traverse(node) {
            if (node instanceof Pair && node.car instanceof Symbol) {
                try {
                    var value = env.get(node.car);
                    if (value instanceof Macro && value.defmacro) {
                        var result = await value.invoke(node.cdr, args, true);
                        if (result instanceof Pair) {
                            return result;
                        }
                    }
                } catch (e) {
                    // ignore variables
                }
            }
            var car = node.car;
            if (car instanceof Pair) {
                car = await traverse(car);
            }
            var cdr = node.cdr;
            if (cdr instanceof Pair) {
                cdr = await traverse(cdr);
            }
            var pair = new Pair(car, cdr);
            return pair;
        }
        var new_code = code;
        if (single) {
            return quote((await traverse(code)).car);
        } else {
            while (true) {
                new_code = await traverse(code);
                if (code.toString() === new_code.toString()) {
                    break;
                }
                code = new_code;
            }
            return quote(new_code.car);
        }
    };
}

问题是，这是一个伪宏扩展，忽略了变量的错误，所以它不能计算宏拟量，因为它抛出了找不到变量的异常所以我最终在扩展列表中使用了quasique（注意：最新版本的代码甚至不尝试扩展quasique，因为它被标记为不可扩展）。
编写宏扩展的方法是什么在使用宏扩展函数时，我是否应该扩展evaluate函数以使其工作方式不同？
我在测试biwascheme是如何创建这个函数的， https://www.biwascheme.org/但是它也没有像我期望的那样工作：
它扩展了：

biwascheme> (define-macro (foo name . body) `(let ((x ,(symbol->string name))) `(print ,x)))
biwascheme> (macroexpand '(foo bar))
=> ((lambda (x) (cons (quote print) (cons x (quote ())))) "bar")
biwascheme> 

我希望它能扩展到：

(let ((x "bar")) (quasiquote (print (unquote x))))

我的口齿不清：

lips> (define-macro (foo name . body)
          `(let ((x ,(symbol->string name))) `(print ,x)))
;; macroexpand is a macro
lips> (macroexpand (foo bar))
(quasiquote (let ((x (unquote (symbol->string name))))
              (quasiquote (print (unquote x)))))

即使我将 quasiquote设置为expandable，它也不会展开quasique，因为它找不到名称，所以抛出异常，而macroexpand会忽略该异常。
任何代码，甚至是伪代码，都将有助于在我的LISP中编写此函数或宏。
编辑：
我已经开始更新代码，将宏扩展合并到evaluate函数中，并在define宏宏中做了一个更改。当调用宏扩展时，它不是第一次调用代码，这就是问题所在。
之前：

var rest = __doc__ ? macro.cdr.cdr : macro.cdr;
if (macro_expand) {
    return rest.car;
}
var pair = rest.reduce(function(result, node) {
    return evaluate(node, { env, dynamic_scope, error });
});

之后：

var rest = __doc__ ? macro.cdr.cdr : macro.cdr;
var pair = rest.reduce(function(result, node) {
    return evaluate(node, eval_args);
});
if (macro_expand) {
    return quote(pair);
}

它现在工作正常，所以我的expand_宏工作正常，这就是你应该如何编写macro_expand。
EDIT2：我进一步重构了代码，结果发现，我不需要在define macro宏中执行macro-exapnd代码，只需取消对它们的引用（delete data flag）。

Answer 1

这是一个用球拍写的玩具宏扩展器，它处理CL风格的宏我在编写这篇文章的过程中使用了Racket宏和其他工具，因此它本身并不是自举的显然，这样的事情是可以做到的，但这样做会显得毛茸茸的。
这样做的目的仅仅是为了演示一个简单的宏扩展器是如何工作的：它在任何意义上都不是适合实际使用的东西。
特殊形式
首先我们需要处理特殊的表格特殊形式是具有神奇语义的事物这个扩展器对它们的工作原理有一个非常简单的概念：
特殊形式是其第一元素是特殊运算符的复合形式；
形式其余部分的每一个元素要么是某种未展开的特殊事物，要么是正常展开的，这是通过在定义中说expr来实现的；
这样做的方式是由一个相当愚蠢的模式匹配器来完成的，这可能仅仅是因为扩展器知道一些特殊的表单。
下面是特殊形式的定义，以及其中三种形式的定义：

(define special-patterns (make-hasheqv))

(define (special-pattern? op)
  (and (symbol? op)
       (hash-has-key? special-patterns op)))

(define (special-pattern op)
  (hash-ref special-patterns op))

(define-syntax-rule (define-special-pattern (op spec ...))
  (hash-set! special-patterns 'op '(op spec ...)))

(define-special-pattern (quote thing))
(define-special-pattern (lambda args expr ...))
(define-special-pattern (define thing expr ...))
(define-special-pattern (set! thing expr))

现在我们可以询问某个东西是否是特殊形式（代码中的特殊模式）并检索其模式：

> (special-pattern? 'lambda)
#t
> (special-pattern 'lambda)
'(lambda args expr ...)

请注意， if之类的东西对宏扩展器不是特殊的运算符，即使它们实际上是特殊的：在类似于 (if test then else)的形式中，所有的子窗体都应该展开，因此宏扩展器没有理由知道它们只有像 lambda这样的子窗体不应该被扩展的情况宏扩展器才需要知道。
宏定义
宏是复合形式，其第一个元素被识别为命名宏对于每个这样的宏，都有一个宏扩展函数负责扩展窗体：该函数传递给整个窗体有一点语法是 define-macro，它以类似于 defmacro在CL中的方式包装此函数（但不支持 &whole或arglist解构或其他任何支持）。

(define macros (make-hasheqv))

(define (macro? op)
  (and (symbol? op)
       (hash-has-key? macros op)))

(define (macro op)
  (hash-ref macros op))

(define-syntax-rule (define-macro (m arg ... . tail) form ...)
  (hash-set! macros 'm (lambda (whole)
                         (apply (lambda (arg ... . tail) form ...)
                                (rest whole)))))

通过这个，我们可以定义一个简单的宏：这里有四个 let的定义。
首先，这里是最基本的一个：它甚至不使用 define-macro而是它变成了什么：外部函数获取整个形式，然后在它的位上调用内部函数，这不是宏名然后，内部函数费力地将 (let ((x y) ...) ...)变成 ((lambda (x ...) ...) y ...)，这是 let的正确扩展（注意，这些都不涉及CL (let (x) ...)）。

(hash-set! macros 'let
           ;; this is what define-macro turns into
           (lambda (whole)
             (apply (lambda (bindings . body)
                      (cons (cons 'lambda
                                  (cons (map first bindings) body))
                            (map second bindings)))
                    (rest whole))))

现在是这样，但是使用 define-macro来减轻疼痛：

(define-macro (let bindings . body)
  ;; Really primitive version
  (cons (cons 'lambda (cons (map first bindings) body))
        (map second bindings)))

另一个版本使用 list*来让事情变得不那么可怕：

(define-macro (let bindings . body)
  ;; without backquote, but usung list* to make it a bit
  ;; less painful
  (list* (list* 'lambda (map first bindings) body)
         (map second bindings)))

最后是一个使用反引号的版本（又名拟序）。

(define-macro (let bindings . body)
  ;; with backquote
  `((lambda ,(map first bindings) ,@body)
    ,@(map second bindings)))

以下是 prog1的宏定义的版本，该宏定义因卫生故障而损坏：

(define-macro (prog1 form . forms)
  ;; Broken
  `(let ([r ,form])
     ,@forms
     r))

以下是你需要如何写的，以使它更卫生（尽管按照Scheme的一些极端标准，它仍然是不卫生的）：

(define-macro (prog1 form . forms)
  ;; Working
  (let ([rn (string->uninterned-symbol "r")])
    `(let ([,rn ,form])
       ,@forms
       ,rn)))

注意，这个宏会变成另一个宏：它会扩展到 let：扩展器需要处理这个问题（确实如此）。
宏扩展器
宏扩展器由两个函数组成： expand-macros是实际执行扩展的对象，它为特殊表单分派到 expand-special。
这里是 expand-macros：

(define (expand-macros form)
  ;; expanding a form
  (if (cons? form)
      ;; only compound forms are even considered
      (let ([op (first form)])
        (cond [(macro? op)
               ;; it's a macro: call the macro function & recurse on the result
               (expand-macros ((macro op) form))]
              [(special-pattern? op)
               ;; it's special: use the special expander
               (expand-special form)]
              [else
               ;; just expand every element.
               (map expand-macros form)]))
      form))

注意事项：
只有复合形式可以是宏形式；
这是一个lisp-1，所以复合形式的cars是完全正常的，可以是宏形式： ((let (...) ...) ...)很好；
宏将递归展开，直到无事可做为止。
这里是 expand-special：这比 expand-macro要烦躁得多，而且可能有缺陷：它试图做的是将特殊表单的定义与给定的表单相匹配。

(define (expand-special form)
  ;; expand a special thing based on a pattern.
  (match-let* ([(cons op body) form]
               [(cons pop pbody) (special-pattern op)])
    (unless (eqv? op pop)
      (error 'expand-special "~s is not ~s" pop op))
    (let pattern-loop ([accum (list op)]
                       [tail body]
                       [ptail pbody]
                       [context 'expr])
      (cond [(null? tail)
             (unless (or (null? ptail)
                         (eqv? (first ptail) '...))
               (error 'expand-special "~s is not enough forms for ~s"
                      body op))
             (reverse accum)]
            [(null? ptail)
             (error 'expand-special "~s is too many forms for ~s"
                    body op)]
            [else
             (match-let* ([(cons btf btr) tail]
                          [(cons ptf ptr) ptail]
                          [ellipsis? (eqv? ptf '...)]
                          [ctx (if ellipsis? context ptf)]
                          [ptt (if ellipsis? ptail ptr)])
               (pattern-loop (cons (if (eqv? ctx 'expr)
                                       (expand-macros btf)
                                       btf)
                                   accum)
                             btr ptt ctx))]))))

这里的关键是省略（ ...）的处理，在匹配器中使用它来表示“这里有更多的东西”：我不记得它是否可以处理不是模式中最后一件事情的省略，但我强烈怀疑它不能请注意，尽管底层宏系统也使用省略号，但这些都是不相关的：这只是依赖于 ...是合法的符号名这一事实。
当然，还要注意，这会在需要的地方递归到 expand-macros中。
给定这些定义，我们现在可以展开一些宏：

> (expand-macros '(let ((x y)) x))
'((lambda (x) x) y)
> (expand-macros '(prog1 a b))
'((lambda (r) b r) a)

请注意，Racket的打印机不是专门打印非联网的，但上面的 r是非联网的。
使用一个简单的跟踪实用程序，您可以定义macroexpander的跟踪版本：

> (expand-macros '(let ([x 1]) (prog1 x (display "1"))))
[expand-macros (let ((x 1)) (prog1 x (display "1")))
 [expand-macros ((lambda (x) (prog1 x (display "1"))) 1)
  [expand-macros (lambda (x) (prog1 x (display "1")))
   [expand-special (lambda (x) (prog1 x (display "1")))
    [expand-macros (prog1 x (display "1"))
     [expand-macros (let ((r x)) (display "1") r)
      [expand-macros ((lambda (r) (display "1") r) x)
       [expand-macros (lambda (r) (display "1") r)
        [expand-special (lambda (r) (display "1") r)
         [expand-macros (display "1")
          [expand-macros display
           -> display]
          [expand-macros "1"
           -> "1"]
          -> (display "1")]
         [expand-macros r
          -> r]
         -> (lambda (r) (display "1") r)]
        -> (lambda (r) (display "1") r)]
       [expand-macros x
        -> x]
       -> ((lambda (r) (display "1") r) x)]
      -> ((lambda (r) (display "1") r) x)]
     -> ((lambda (r) (display "1") r) x)]
    -> (lambda (x) ((lambda (r) (display "1") r) x))]
   -> (lambda (x) ((lambda (r) (display "1") r) x))]
  [expand-macros 1
   -> 1]
  -> ((lambda (x) ((lambda (r) (display "1") r) x)) 1)]
 -> ((lambda (x) ((lambda (r) (display "1") r) x)) 1)]
'((lambda (x) ((lambda (r) (display "1") r) x)) 1)

此代码的版本可用 here。