前言

这是填上三年前的坑 只有咸鱼看不懂的解释器科普 第一步:解析 实际上我觉得我成了咸鱼了,看不懂自己之前写的解释器。

三年前我写的是科普,但现在因为精力有限完全算不上科普了,再说那么多年过去了也不需要科普了吧,这东西也没什么技术含量。

这里我就简略的讲一下,iKa 最核心的执行逻辑。会引入大量外部概念,专有名词我就用斜体表示了。

作为早期作品模块划分有点问题,命名更是不专业,而且没有注释和类型信息。以前的自己得意地觉得这些代码能自我注释,所以根本没去注释,现在看实在太难读了。

主逻辑

作为一个执行着的程序来说 iKa 是一个 REPL

def main():
    import readline
    print(';; ika 1*10^-42')
    evaluator = evaluator_maker()
    while True:
        for expr in parser(input('; >> ')):
            evaluator(expr)

可以看到被解析以后的表达式,塞进 evaluator 就执行了,evaluator_maker 用于创建 evaluator

evaluator 排除编译表达式的那行调用,基本上能看作一个虚拟机。实际上应该把编译和执行分开的,不知为何我把逻辑写在同一个模块里。

我发现自己竟然把主逻辑藏到了 __init__.py 里面。

执行器

def evaluator_maker(cont=output):
    ir = []
    env_ = Env()

    def evaluator(expr):
        pc = len(ir)
        env = env_
        values = ()

        if expr is not None:
            compiler(expr, ir)
        ir.append((rtn, ()))
        while True:
            function, arguments = ir[pc]
            # print(pc, values, function)
            if function is rtn and env.parent is None:
                break
            elif function is instruction.self_evaluator:
                pc += 1
                values = (arguments[0], values)
            else:
                env, pc, values = function(env, pc, values, *arguments)
        return cont(values[0])
    return evaluator

ir 指的是 Intermediate language,但实际里面就是 Target code,表达式从 AST 编译后就被放到 ir 里。可以理解成放代码的内存段。

ir 内部是 [(function, arguments)]

function 实际上是 instruction( 类似汇编的 mov),都是一些别处定义的运行时执行所必需的基础控制逻辑,编译的过程其实就是把复杂的表达式(包括函数定义)编译成这些基础指令组成的序列,而且编译后的序列是 CPS 的。

而 arguments 是一个 Python 意义上的 tuple,负责给 instruction 传递编译时被确定的控制数据,这些参数并非是运行时求值得到的,而是编译时就确定下来的,补全指令用的控制参数。

比如说 (set! a 1) 就会产生 (instruction.assign, (Symbol(a), )) 这样的指令压入到 ir 中。

而 1 呢?因为 CPS 变换,所以会是这样的:

[
  # ...
  (self_evaluate, (        1, )),
  (assign       , (Symbol(a), )),
]

self_evaluate 指令代表什么都不做,因为 1 已经是一个立即数了。

运行时,前面的指令的求值结果累计在 values 中,传递给后一条指令。这就是 CPS 变换的实现方式。

values 作为值的累积可以看作一个栈,新的表达式的求值结果就压到这个栈中,而后面的指令依赖于前面的表达式求值结果的话,比如说过程调用需要若干参数,就会弹出栈内的值。

env 代表作用域,可以看作一个用于装局部变量的键值对,以及指向上层作用域的指针,作用域嵌套形成了一个偏序。

pcProgram Counter,指向下一条需要执行的指令,一般的操作只会让 pc + 1 但是函数调用、条件分支等就会重设 pc

而真正在执行指令的语句就是:

env, pc, values = function(env, pc, values, *arguments)

将当前的各种 context 和编译时就确定的 arguments 传递给指令,按照指令内部逻辑更新这些 context,作为返回值返回。

比如说修改 env 以进入子作用域或者跳到外层,修改 pc 以过程调用。

这就是这个机器执行时的主要工作了,但是过程调用具体怎么进行的呢,call/cc 具体怎么运作…我自己都还没看懂,慢慢填坑吧。

编译

evaluator 里面有一句 compiler(expr, ir),将 expr 编译成前文说到的指令序列,放到 ir 中。

compiler 函数的代码里并没有逻辑,只是去模式匹配表达式,派送到对应的处理单元(handler)而已:

def compiler(expr, ir):
    for cond, handler in line:
        if cond(expr):
            return handler(expr, ir)

line 里面放着这些处理单元,也是一个二元组,[(cond, handler)],显然 cond 用来测试表达式是否匹配,如果匹配就用 handler 处理。

这里就来看看 assign 编译处理单元吧,就是专门处理赋值语句的。

@sign(car_is('set!'))
@register
def assign(expr, ir):
    key = expr[1][0]  # .cdr.car
    value = expr[1][1][0]  # .cdr.cdr.car
    compiler(value, ir)
    return instruction.set_value, (key,)

先看参数和返回值,和 compiler 函数中的调用对应,参数就是表达式本身,以及存放已编译指令序列的 ir

assign 内部的逻辑很简单,取出表达式中被赋值的符号 key 以及右值表达式 value

先递归编译 value,对这个表达式的求值会先被压入指令序列,然后才返回自身的指令—— key 就作为 arguments

但这里没有显式把产生的指令加入 ir,这个工作因为几乎是每个 handler 的结尾,所以用了一个修饰器 register 代劳了。

另一个 sign 修饰器的意思已经很明显了,就略过了。

(sign 实际上才应该叫 register,而 register 叫 save_ir 比较好。)

编译部分的逻辑都比较简单,只是代码的简单变换而已,那就以其中最麻烦的 lambda 函数编译作为结尾吧。

@sign(car_is('lambda'))
def lambda_(expr, ir):
    pc = len(ir)
    ir.append(None)  # 占位,最后一行会回来填充

    args, body = expr[1]  # 获得参数列表和函数体
    func = Function(args, pc+1)  # Function 可以看作函数上下文结构。

    compiler(Pair(('begin', body)), ir)  # 编译函数体并加入 ir 中
    # 因为函数体内默认可以多行语句,所以手动给函数体加入 begin。
    # 现在编译后, ir 内部 None 后就跟着函数体指令码。
    ir.append((rtn, ()))  # rtn 就是 return 负责弹出当前调用。
    i = len(ir)  # i 代表执行到 lambda 的时候,pc 更新逻辑,这里就用于跳过函数体,因为还没有被调用。

    # 之前写着 None 的占位符,这里填充了真正的 lambda 指令。
    ir[pc] = (instruction.lambda_, (i, body, func))

可以看到,对于其他大多数表达式,因为 CPS 变换的缘故,表达式内的子表达式,是先于表达式本身加入 ir 的,但是定义函数的 lambda_ 就并非如此。

编译后的结果是这样的:

[
  # ...
  [lambda_, (next_pc, function_body_expr, func_context)],
  # 已编译的 body
  [...],
  [rtn, ()],
]

next_pc 就是 i,用于跳过函数体,至于其他的部分,那就下一篇文章讲真正运行时的执行逻辑再说吧,其实我也还没搞懂。