date: 2025-1-4

关于我如何写一个自举解释器的事情

上回：https://github.com/taimoon/scheme-compiler

这回：https://github.com/taimoon/scheme-interpreter

书接上回，我已经实现一个可以自举的编译器。 说如果一开始没有scheme实现来运行我的scheme编译器源码？ 先驱们开头是怎么实现lisp？ 不妨假设当时已经有了计算机，基础操作系统以及汇编器， 那么必然是先驱们用汇编（机器码）实现lisp。 一上来就汇编，我表示把握不住，所以我用一个高级语言做一个原型先。 我选C语言因为比较接近汇编我不是很会C++, rust。

自动内存管理与垃圾回收

可是，用C语言实现scheme解释器非常困难因为C语言没有自动内存管理。 毕竟，我的scheme编译器运行时会产生很多垃圾，会挤爆内存，所以自动释放是必须的。

不是，in the first place, 为什么会有垃圾？什么是垃圾？

以下是一个scheme程序，每调用sum，里头的iota分配n长度的列表。 调用完后，这n长度的列表就不会影响后续的执行结果；等同于垃圾。

(define (sum n)
  (fold-left + 0 (iota n)))
; (sum 3)
; => (fold-left + 0 (iota 3))
; => (fold-left + 0 '(0 1 2))
; => 3 ; by some magic
(sum 3)
(sum 4)
(sum 5)

可能会有同学反驳说，可以手动释放啊，或者最好别写需要分配对象的实现，或者RAII云云。

(define (sum n)
  (let* ((ns (iota n))
         (res (fold-left + 0 ns)))
    (free ns)
    res))

(define (sum n)
  (if (<= n 0)
      0
      (+ n (sum (- n 1)))))

如果程序有一点点复杂，阁下又该如何应对？

(define (sum? e)
  (and (= (length e) 3) (eq? (car e) '+)))

(define (product? e)
  (and (= (length e) 3) (eq? (car e) '*)))

(define (make-sum left right)
  (list '+ left right))

(define (make-product left right)
  (list '* left right))

(define (left-operand e)
  (cadr e))

(define (right-operand e)
  (caddr e))

(define (variable? x) (symbol? x))

(define (variable=? x y) (and (variable? x) (variable? y) (eq? x y)))

(define (deriv exp var)
  (cond
    ((number? exp) 0)
    ((variable? exp)
     (if (variable=? exp var) 1 0))
    ((sum? exp)
     (make-sum (deriv (left-operand exp) var)
               (deriv (right-operand exp) var)))
    ((product? exp)
     (make-sum (make-product (left-operand exp)
                             (deriv (right-operand exp) var))
               (make-product (deriv (left-operand exp) var)
                             (right-operand exp))))
    (else (error 'deriv 'unknown exp))))

(define (simplify exp)
  (cond
    ((number? exp) exp)
    ((variable? exp) exp)
    ((sum? exp)
     (let ((left (simplify (left-operand exp)))
           (right (simplify (right-operand exp))))
      (cond 
        ((eq? 0 left) right)
        ((eq? 0 right) left)
        ((and (number? left) (number? right))
         (+ left right))
        ((equal? left right)
         (make-product 2 left))
        (else (make-sum left right)))))
    ((product? exp)
     (let ((left (simplify (left-operand exp)))
           (right (simplify (right-operand exp))))
      (cond 
        ((or (eq? 0 left) (eq? 0 right)) 0)
        ((and (number? left) (number? right))
         (* left right))
        ((eq? 1 left) right)
        ((eq? 1 right) left)
        (else (make-product left right)))))
    (else (error 'simplify 'unknown exp))))

(define (writeln x) (write x) (newline))

(writeln (simplify (deriv '(* (+ x 3) (+ x 5)) 'x)))
(writeln (simplify (deriv '(+ (* x x) (+ (* 8 x) 15)) 'x)))

哪怕办得到，到处free就很不优雅。当时John McCarthy先驱也是这么想的。

那么，有没有办法自动释放？

其中一个方案就是追踪式垃圾回收。

垃圾回收的核心是标记那些后续执行会访问的对象（包括其间接引用的对象），那些不是。 那些不会被访问的都是垃圾，可以被回收。这也是所谓的，可达对象（accessible object）。那么如何知道那些对象是会被后续执行继续使用？

答案是当前栈上的对象以及全部寄存器。这也是所谓的根节点的集合，即根集，root set。 准确地说，这要看运行时是如何管理上下文。一般比如C, python都是栈和寄存器。

垃圾回收涉及到栈,必须要有办法确定栈上面那些是对象，那些不是。 其次，这也涉及栈回溯。 对于我，这是垃圾回收实现最困难的部分：如何interface scheme解释器。 C语言默认运行时不包含类型信息，没办法确定栈上面的对象类型。

一个workaround是使用多一个栈，如果是带有类型信息的对象，运行时会压在这个栈。 这样这个栈上面全都是对象，而不会混杂其他运行时的数据。

声明：这涉及魔改C语言编译器，我嘴巴上说说而已，而且我也不知道行不行。

我scheme编译器更加极端，只是使用一个栈，在每次回收开始，栈上面只能是对象，返回地址以及栈针。

我的workaround是以continuation passing style的方式来写scheme解释器，即手动管理上下文。scheme的CPS实现会有固定的寄存器存储上下文，然后回收这些即可。

上下文

参考："Programming Languages and Lambda Calculi" at https://users.cs.utah.edu/~mflatt/past-courses/cs7520/public_html/s06/notes.pdf

假如我们有一个抽象机，只能给两个整数或寄存器做加法,乘法，减法。

num_or_reg_1 + num_or_reg_2
num_or_reg_1 - num_or_reg_2
num_or_reg_1 * num_or_reg_2
dest_reg = num_or_reg_1 + num_or_reg_2
dest_reg = num_or_reg_1 - num_or_reg_2
dest_reg = num_or_reg_1 * num_or_reg_2

然后比较复杂式子就不行了

(3 * 3) + (4 * 4)

因为(3 * 3)以及(4 * 4)仅仅是式子，不是整数，也不是寄存器，所以我们的抽象机计算不能。

我们可以理所当然认为抽象机可以先计算左边的式子，再计算右边的式子，然后才应用当前操作符，如下。

$$ \textbf{(3 * 3) + (4 * 4)} \\ \textbf{(3 * 3)} + (4 * 4) \\ 9 + \textbf{(4 * 4)} \\ \textbf{9 + 16} \\ 25 $$

或者可以如下面表示同样的计算过程，当中每一步的_对应着上面每一步运算粗体部分，可以称之为当前的evaluation context，上下文。

step (3 * 3) + (4 * 4)  , _
step 3 * 3              , ((_ + (4 * 4)), _)
step 9                  , ((_ + (4 * 4)), _)
step (4 * 4)            , ((9 + _), _)
step 16                 , ((9 + _), _)
step 9 + 16             , _
step 25                 , _
25

在以上两个例子当中，抽象机不可避免必须要保存evaluation context或者上下文。 形象地解释为可当抽象机计算左式子的时候，必须要记得过后还要计算右式子，这是所谓的上下文。

可能有同学反驳说，可以利用寄存器来存储当前中间结果，如编译器那样那样

tmp0 = 3 * 3
tmp1 = 4 * 4
out  = tmp0 + tmp1

一般处理器寄存器数量是有限， 而栈能存放的空间是远远多于寄存器， 所以这时很多编译器会选择压栈。 这压栈形同于存储上下文。

fn sum_recur(n: isize) -> isize {
    if n == 0 {
        0
    }
    else {
        n + sum_recur(n - 1)
    }
}
fn sum_iter(n: isize, init: isize) -> isize {
    if n == 0 {
        init
    }
    else {
        sum_iter(n - 1, init + n)
    }
}

fn main() {
    println!("{}", sum_iter(123456789, 0));
}

以上程序，rust编译执行会因sum_iter的调用会爆栈。难道可以不爆栈？

如果人肉执行sum_recur，我们能发现sum_recur的调用模式呈树状，需要额外保存上下文。

sum_recur(3)
3 + sum_recur(2)
3 + (2 + sum_recur(1))
3 + (2 + (1 + sum_recur(0)))
3 + (2 + (1 + 0))
3 + (2 + 1)
3 + 3
6

如果人肉执行sum_iter，我们能发现sum_iter的调用模式是线性，不需要额外保存上下文，直接返还结果。这是尾递归。

sum_iter(3, 0)
sum_iter(2, 3)
sum_iter(1, 5)
sum_iter(0, 6)
6

虽然开了优化rust，C编译器也可以尾递归优化， 但是scheme标准语义规定尾递归， 所以用C语言实现的scheme解释器也必须保证尾递归，但如果以CPS方式去编程，那么已经无形中做了尾递归优化。

CPS转换：爆改递归成循环的魔法

那么为什么sum_recur调用的上下文会增长，而sum_iter不会？

It is the evaluation of operands that makes the control context grow.

计算操作数才是导致上下文增长的罪魁祸首。

print(11 + 13)

11和13是operands，+是operator，然后print(11 + 13)是一个function call，其中print是operator，11 + 13是operand。让我在文中分别称它们为操作数和操作符。

在sum_recur当中，sum_recur(3)的值是等于3 + sum_recur(2),其中operator是加法，有两个operands分别为3和sum_recur(2)， 当前需要进一步计算sum_recur(2)的值，才可以计算当前的加法，必须要存储上下文记得回去做加法。 不是operator application需要上下文，而是operand的求值需要上下文。It is the evaluation of operands that makes the control context grow!

直到现在为止，文中出现上下文还是不够具体。 那么这里evaluation context(上下文)到底什么东西？

(2 + (3 * 5)) , _
3 * 5         , (2 + _)
15            , (2 + _)
2 + 15        , _
17

再回到之前抽象机的例子，上面的_对应着当前的evaluation context。 形象的说就是抽象机正在看着的地方，focus scope。 Evaluation context也是当抽象机已求值再次被放回去的地方，所以也可以被称为hole，洞。 再来，evaluation context也描述如果抽象机已求值，如何进行下一步计算，所以可以被称为continuation，续体。 Evaluation context也表示程序剩下的部分。

如果根据实现上述计算过程来实现抽象机

from dataclasses import dataclass
@dataclass
class Expr:...
@dataclass
class Add: ...
@dataclass
class Mul: ...
@dataclass
class Hole(Expr):...
@dataclass
class Prim(Expr):
  left: Expr
  op: Add|Mul
  right: Expr

def unparse(e: Expr|list[Expr]) -> str:
  match e:
    case int():
      return str(e)
    case Hole():
      return '_'
    case Prim(e1, Add(), e2):
      return f'({unparse(e1)} + {unparse(e2)})'
    case Prim(e1, Mul(), e2):
      return f'({unparse(e1)} * {unparse(e2)})'
    case [*es]:
      return '(' + ', '.join(unparse(e) for e in es) + ')'
    case _:
      raise NotImplementedError(e)

def calc(e: Expr, ctx: list[Expr]|Hole) -> int:
  print(unparse(e), unparse(ctx), sep=' , ')
  match e, ctx:
    case int(v), Hole():
      return v
    case int(v),[Prim(Hole(), op, e2), _ctx]:
      return calc(Prim(v, op, e2), _ctx)
    case int(v),[Prim(e1, op, Hole()), _ctx]:
      return calc(Prim(e1, op, v), _ctx)
    case Prim(int(v), Add(), int(w)), _ctx:
      return calc(v + w, _ctx)
    case Prim(int(v), Mul(), int(w)), _ctx:
      return calc(v * w, _ctx)
    case Prim(int(v), op, e2), _ctx:
      return calc(e2, [Prim(v, op, Hole()), _ctx])
    case Prim(e1, op, e2), _ctx:
      return calc(e1, [Prim(Hole(), op, e2), _ctx])
    case _:
      raise NotImplementedError(e)

print(calc(Prim(2, Add(), Prim(3, Mul(), 5)), Hole()))

运行时打印结果，完全符合预期。

(2 + (3 * 5)) , _
(3 * 5) , ((2 + _), _)
15 , ((2 + _), _)
(2 + 15) , _
17 , _
17

我们能发现到calc函数调用是线性的，全都是尾调用，并不会有上下文增长，可以很容易改写成循环。

def calc(e: Expr) -> int:
  ctx = Hole()
  while True:
    print(unparse(e), unparse(ctx), sep=' , ')
    match e, ctx:
      case int(v), Hole():
        return v
      case int(v),[Prim(Hole(), op, e2), _ctx]:
        e = Prim(v, op, e2)
        ctx = _ctx
      case int(v),[Prim(e1, op, Hole()), _ctx]:
        e = Prim(e1, op, v)
        ctx = _ctx
      case Prim(int(v), Add(), int(w)), _ctx:
        e = v + w
        ctx = _ctx
      case Prim(int(v), Mul(), int(w)), _ctx:
        e = v * w
        ctx = _ctx
      case Prim(int(v), op, e2), _ctx:
        e = e2
        ctx = [Prim(v, op, Hole()), _ctx]
      case Prim(e1, op, e2), _ctx:
        e = e1
        ctx = [Prim(Hole(), op, e2), _ctx]
      case _:
        raise NotImplementedError(e)

作为比较，以下是同样抽象机树遍历实现

def calc(e: Expr) -> int:
  match e:
    case int():
      return e
    case Prim(e1, Add(), e2):
      return calc(e1) + calc(e2)
    case Prim(e1, Mul(), e2):
      return calc(e1) * calc(e2)
    case _:
      raise NotImplementedError(e)

虽然可以改写成循环，不会爆栈， 然而仍然没有改变程序本质上需要保存上下文的事实， 只不过改写成以堆分配对象来保存上下文而已。

https://zhuanlan.zhihu.com/p/429531068

知乎上，游客账户0x0曾写过一篇标题为"（水文警告）什么是编程语言的语义"的科普，其中有那么一段

发现对于编程语言的语义是什么似乎有一个很普遍的误解：

高级编程语言必然是通过更低级的语言， 一层层向下并最终达到机器语言的。 所以越低级的语言越本质，高级语言的语义必须依赖于更低级的语言存在。

不能因为底层实现是循环，而忽视有些算法递归的本质。难道手动管理上下文就不是递归？ 比如解析程序过程本质上就是树遍历，必须上递归。

有些算法天然方案就是递归比如问一个整数有多少和拆分方式，可以重复，例子：

5 = 5
  = 4 + 1
  = 3 + 1 + 1
  = 2 + 3
  = 2 + 2 + 1
  = 2 + 1 + 1 + 1
  = 1 + 1 + 1 + 1 + 1

整数5总共有七个拆分。以下python程序实现

def sum_way(s: int, n: int) -> int:
  if s == 0:
    return 1
  elif s < 0 or n <= 0:
    return 0
  else:
    return sum_way(s - n, n) + sum_way(s, n - 1)

或者CPS方式去写同样程序，也是可以改写成循环

def sum_way_k(s: int, n: int) -> int:
  kont = ['sum_way_k', s, n, []]
  val = None
  while True:
    match kont:
      case []:
        return val
      case 'sum_way_k', 0, _, _kont:
        kont = _kont
        val = 1
      case 'sum_way_k', _, 0, _kont:
        kont = _kont
        val = 0
      case 'sum_way_k', s, _, _kont if s < 0:
        kont = _kont
        val = 0
      case 'sum_way_k', s, n, _kont:
        kont = ['sum_way_k', s - n, n, ['sum_way_k_right', s, n, _kont]]
      case 'sum_way_k_right', s, n, _kont:
        kont = ['sum_way_k', s, n - 1, ['add', val, _kont]]
      case 'add', prev, _kont:
        kont = _kont
        val = prev + val
      case _:
        raise NotImplementedError(kont)

虽然改写成循环，仍然需要手动管理上下文，没有改变该算法递归本质。是不会爆栈，但会爆堆。

蹦床

可能有聪明同学发现到，续体非得像上面用数据结构来表示，可以用函数来表示。

def calc(e: Expr, ctx = lambda x: x) -> int:
  match e:
    case int(v):
      return ctx(v)
    case Prim(e1, Mul(), e2):
      return calc(e1, lambda v: calc(e2, lambda w: ctx(v * w)))
    case Prim(e1, Add(), e2):
      return calc(e1, lambda v: calc(e2, lambda w: ctx(v + w)))
    case _:
      raise NotImplementedError(e)

然而python不一定会做尾递优化，还是会爆栈，比如

from functools import reduce
# 0 + 1 + ... + 1000
print(calc(reduce(lambda e, i: Prim(e, Add(), i), range(1000))))

其中一个workaround就是上蹦床

def trampolined_calc(e: Expr) -> int:
  bounce = calc(e)
  while not isinstance(bounce, int):
    bounce = bounce()
  return bounce

def calc(e: Expr, ctx = lambda x: x) -> int:
  match e:
    case int(v):
      return lambda: ctx(v)
    case Prim(e1, Mul(), e2):
      return lambda: calc(e1, lambda v: calc(e2, lambda w: ctx(v * w)))
    case Prim(e1, Add(), e2):
      return lambda: calc(e1, lambda v: calc(e2, lambda w: ctx(v + w)))
    case _:
      raise NotImplementedError(e)

from functools import reduce
e = reduce(lambda e, i: Prim(e, Add(), i), range(1000))

print(trampolined_calc(e))

解释器实现

总结，为什么当我用C语言scheme解释器要以CPS方式去写？

实际上，我最主要的动机是研究垃圾回收，而我想到CPS了。为此写一个原型 https://github.com/taimoon/CPS-CScheme。

从刚刚calc CPS实现，我们可以看到每一次循环，能影响下一步结果，只有val和ctx变量，所以垃圾回收这些就可以。 python过渡到C有一个困难，C不是函数式语言，没有闭包，也不是面向对象语言。当然可以如同sum_way_k，用switch,case，循环方式在C语言里面实现解释器，只不过全部实现都会挤在同个函数循环，导致会非常大。

我的方案是所有解释器相关helper函数实现都要遵循特定方式来调用，通过全局变量来传参，然后以NEXT全局变量来蹦床。 像我这种做法感觉大可不必纯纯装X。 实际上，我是根据我之前以CPS方式用scheme写的scheme解释器作为原型参考实现，再转写成C语言，才产生的workaround。

我的目标实现至少可以解释执行我scheme编译器，来得到一个scheme编译器，然后可以向C实现的解释器说拜拜。

我scheme解释器对语法糖支持是通过define-macro非卫生宏来支持。此举是避免用C语言层面来实现语法糖，毕竟用scheme编程就是比C容易，万不得以才动C。

不计入库以及编译器，保守估计最终实现代码行数在2000行上下，可以几分钟解释执行完我scheme编译器的自身编译。 相较于我scheme编译器可以几秒内编译自身，树遍历解释器都是这么慢。

可能有同学说，可以字节码虚拟机实现来提速啊。呃，我有那功夫不如我写编译器直接输出成机器码，其中很多步骤都是共同的。绝对不是因为我偷懒或者我不会

总结

我用C语言实现scheme解释器其中一个目的也是作为原型参考实现，以便在未来以此手写汇编。

另外，文中的抽象机实现也是CK抽象机的变种。有兴趣的同学可以阅读 Matthias Felleisen与Matthew Flatt写的"Programming Languages and Lambda Calculi"笔记补充。其中有明说垃圾回与续体的关系，以及垃圾回的形式化模型。

间幕：面向表达式

rust有些构造是面向表达式（expression oriented）比如if,loop，match。 让我误解以为rust鼓励面向表达式写法。 但是如果没有尾递归优化，sum_iter的写法就不行，被迫写成statement form，也可以理解为rust变相于官方不鼓励这么写。

我发现，没有尾递归保证，有损面向表达式的支持，没有尾递归保证，已经从设计上限制面向表达式的一些写法。 这可能也是rust原设计者，Graydon也希望rust支持尾递归优化(详见：https://graydon2.dreamwidth.org/307291.html)。 python, C的if表达式写法尴尬，直接表明官方不鼓励。

现代很多编程语言如python,C,C++,rust，尾递归仅仅局限于优化，不是作为语义约束。 为什么迟迟不能从语义上规定尾递归？ Guido写了一篇博客解释为什么python不支持尾递归。 Rust,C,C++也许是因为平台兼容限制，比如Sys V ABI调用规定压栈，如果有多余参数是先压参，后压返回地址，然而这调用规定不兼容尾递归实现，转而用其他workaround来实现尾调用规定。

后日谈

最近，为了满足我司KPI，我给我同事们科普类型系统的应用，时长两个小时的hand-on，用python写一个简单解释器，简单类型检查器和简单json类型推导。

<expr> :=
  <integer>
  | #t | #f
  | (let <identifier> = <expr> <expr>)
  | (if <expr> <expr> <expr>)
  | (<operator> <expr> ...)

<operator> := + | - | ... | <identifier>

结论，两个小时实在太短了，毕竟递归非常不普及。

Reference