前言
这是填上三年前的坑 只有咸鱼看不懂的解释器科普 第一步:解析 实际上我觉得我成了咸鱼了,看不懂自己之前写的解释器。
三年前我写的是科普,但现在因为精力有限完全算不上科普了,再说那么多年过去了也不需要科普了吧,这东西也没什么技术含量。
这里我就简略的讲一下,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
代表作用域,可以看作一个用于装局部变量的键值对,以及指向上层作用域的指针,作用域嵌套形成了一个偏序。
pc
是 Program 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
,用于跳过函数体,至于其他的部分,那就下一篇文章讲真正运行时的执行逻辑再说吧,其实我也还没搞懂。