lisp 宏展开实现中遇到的两个问题

2019-06-24

我在设计的一个 lisp 方言,实现宏的时候遇到的两个问题。这两问题其实都是影响到语言设计的,记录一下。

pattern match 宏展开,以及尾递归

pattern match 是我想默认带进语言里面的 feature,在这个语言中默认使用 pattern match 定义函数:

(func acc
    n => (acc (- n 1))
    0 => 0)

很明显,这是一个尾递归的函数。所以我们调用 (args 66666666) 不应该爆栈。

func 是一个宏,展开后是用的 match 宏:

(defun acc (args)
    (match args
        n => (acc (- n 1))
        0 => 0))

所以这里对 match 宏有一个要求:不能把原本尾递归的代码,展开之后变成非尾递归了

这个要求实现起来,可比听起来要复杂很多。

match 宏展开会有一个膨胀问题,假设我们的 match 条件是

(or
  (and A B C)
  (and D E F)
  (and G H))

用最朴素的方式展开,会变成

(if A
    (if B
        (if C
            ;; match condition (and A B C)
            (if D
                (if E
                    (if F
                        ;; match condition (and D E F)
                        (if G
                            (if H
                                ;; match condition (and G H)
                                (error "no match")))))))
        (if ;; handle (or (and D E H) (and G H)) cases))
    (if D
        (if E
            (if F
                ;; match condition (and D E F)
                (if G
                    (if H
                        ;; match condition (and G H)
                        (error "no match")))))))
  • 假设 match 到 (and A B C) 中的 A 失败了,接下来要把 (and D E F)(and G H) 代码生成一遍
  • 假设 match 到 (and A B C) 中的 B 失败了,接下来要把 (and D E F)(and G H) 代码生成一遍
  • 假设 match 到 (and A B C) 中的 C 失败了,接下来要把 (and D E F)(and G H) 代码生成一遍

这种代码膨胀的是非常夸张的,会有很多很多的重复代码生成... 宏展开之后的代码完全没法读了。

避免重重代码的方式,就是把结果存到变量里面。一种写法是引入特殊的 fail 值,另一种是用 CPS 风格写代码。比如说使用 fail 值的方式

(lambda ()
    (if A
        (if B
            (if C
                ;; match condition (and A B C)
                (fail))
            (fail))
        (fail)))
    
(lambda ()
    (if D
        (if E
            (if F
                ;; match condition (and D E F)
                (fail))
            (fail))
        (fail)))

独立处理各个 pattern match 的 case,如果失败,直接返回特殊 fail 标记。然后在一个循环里面依次判断各个 match 的 case

(func loop
    [] -> (error "no match")
    [p1 | p2] -> (if (= (p1) (fail))
                     ;; match case p1
                     (loop p2)))

代码膨胀的问题就解决了,以前每个 (fail) 都是对应了大量的重复代码的。

CPS 方案也是类似的,不过是把 (fail) 变成直接调用 cc 跳转到接下来要处理的 case 的逻辑中:

(if A
        (if B
            (if C
                ;; match condition (and A B C)
                (cc 1))
            (cc 1))
        (cc 1))
        
cc 1 = 
(if D
      (if E
          (if F
              ;; match condition (and D E F)
              (cc 2))
          (cc 2))
      (cc 2))

无论是引用 fail 标记,还是用 cps 风格写法,它们都带来一个问题,就是结果不再是最终结果,需要保存下来。这可能会导致原本尾递归的代码,展开后变成不是尾递归的!

这个影响还是很大的。我原本准备在 clojure 上面实现我的 lisp 方言,但是由于 clojure 不是支持尾递归的,导致这种 pattern match 实现展开以后会爆栈。 原本的

(func acc
    n => (recur (- n 1))
    0 => 0)

在展开后 recur 会移动到其它位置,不再是尾调用的位置。

小结一个就是说,想要 match 宏代码展开不膨胀,必定会保存中间结果,保存中间结果可能会使原本尾递归的地方变得不再尾递归。像 clojure 里面的 recur 这种"伪"递归是不行的。

如果想比较好的支持 match,至少要求语言层面支持严格尾递归了。

宏展开,以及对特殊表处理

在设计这个语言的时候,另一个我纠结了很久的事情是,宏是否应该理解语义。

如果宏是要理解语义的,那么就要像 scheme 那样做样卫生宏,要考虑宏定义环境,和宏展开环境。这会带来非常高的实现复杂度。最后我决定做成非卫生宏。让宏是完全工作在符号层的,也就是 sexp 上面,不理解语义。

我发现实现宏的时候有两种写法。第一种是:

(func macroexpand
      x => (let y (compose *macros* x)
                (if (equal? x y)
                 x
                 (walk macroexpand y))))

walk 是一个对 sexp 每个元素进行访问的函数,compose 就是 clojure 里面的 --> 宏。这个函数意思是,对展开后的结果,跟展开之前对比,直到不会变化了,就是完全展开了。像是一个不动点。

另外一种写法是这样的:

(func macroexpand
    (list 'lambda ...) => (expand-lambda ...)
    (list 'let ...) => (expand-let ...)
    (list 'if a b c) => (expand-if ...)
    (list 'set ... => (expand-set ...)))

第二种写法中,对 lambda, let 等等特殊表都进行特殊处理了。我开始不理解要什么要这么做,直到后来自己实现时,才明白 特殊表的语法,对宏展开会有影响

比如 lambda 在 scheme 里面是一个特殊表 (lambda (max a b) body),假设在我设计的语言里面,宏是不理解语义的,也就是说,它并不知道 lambda 是特殊表,它会对 (max a b) 继续调用宏展开,而不是把它当作参数!

参数 max 正好是一个宏的名字,展开之后就有问题了,最后变成 (lambda (if (> a b) a b) body)

我才理解,为什么 shen 语言设计的时候 lambda, let 这些都是不带括号的,它是 (let a 3 b 5 (+ a b)) 这种语法,不像 scheme 的 (let ((a 3) (b 5)) (+ a b)),在 shen 里面 let 就不是特殊表了,只是一个普通的宏。

如果特殊表里面有 (),就需要特殊处理。这会让宏的实现复杂化。所以这里也算是对语言设计有影响的。我希望自己设计时,让宏完全不理解语义,甚至连特殊表都不需要理解,更接近 lisp 原旨教义。

lispcoramacro