实现 Haskell 求值语义(系列三)
本期文章为在MoonBit中实现惰性求值的第三篇。在上一篇中,我们了解了let表达式的编译方法以及如何实现基本的算术比较操作。这一篇文章中,我们将实现一种基于上下文的优化方法,并添加对数据结构的支持。
追踪上下文
回顾一下我们之前实现primitive的方法:
let compiledPrimitives : List[(String, Int, List[Instruction])] = List::[
// 算术
("add", 2, List::[Push(1), Eval, Push(1), Eval, Add, Update(2), Pop(2), Unwind]),
("sub", 2, List::[Push(1), Eval, Push(1), Eval, Sub, Update(2), Pop(2), Unwind]),
("mul", 2, List::[Push(1), Eval, Push(1), Eval, Mul, Update(2), Pop(2), Unwind]),
("div", 2, List::[Push(1), Eval, Push(1), Eval, Div, Update(2), Pop(2), Unwind]),
// 比较
("eq", 2, List::[Push(1), Eval, Push(1), Eval, Eq, Update(2), Pop(2), Unwind]),
("neq", 2, List::[Push(1), Eval, Push(1), Eval, Ne, Update(2), Pop(2), Unwind]),
("ge", 2, List::[Push(1), Eval, Push(1), Eval, Ge, Update(2), Pop(2), Unwind]),
("gt", 2, List::[Push(1), Eval, Push(1), Eval, Gt, Update(2), Pop(2), Unwind]),
("le", 2, List::[Push(1), Eval, Push(1), Eval, Le, Update(2), Pop(2), Unwind]),
("lt", 2, List::[Push(1), Eval, Push(1), Eval, Lt, Update(2), Pop(2), Unwind]),
// 杂项
("negate", 1, List::[Push(0), Eval, Neg, Update(1), Pop(1), Unwind]),
("if", 3, List::[Push(0), Eval, Cond(List::[Push(1)], List::[Push(2)]), Update(3), Pop(3), Unwind])
]
这样的实现引入了很多Eval
指令,但它们未必总是用得上。例如:
(add 3 (mul 4 5))
add
的两个参数在执行Eval
之前就已经是WHNF, 这里的Eval
指令是多余的。
一种可行的优化方法是在编译表达式时注意其上下文。例如,add需要它的参数被求值成WHNF,那么它的参数在编译时就处于严格(Strict)上下文中。通过这种方式,我们可以识别出一部分可以安全地按照严格求值进行编译的表达式(仅有一部分)
-
一个超组合子定义中的表达式处于严格上下文中
-
如果
(op e1 e2)
处于严格上下文中(此处op
是一个primitive),那么e1
和e2
也处于严格上下文中 -
如果
(let (.....) e)
处于严格上下文中,那么e
也处于严格上下文中(但是前面的局部变量对应的表达式就不是,因为e不一定需要它们的结果)
我们用函数compileE
实现这种严格求值上下文下的编译,它所生成的指令可以保证栈顶地址指向的值一定是一个WHNF。
首先对于默认分支,我们仅仅在compileC
的结果 后面加一条Eval
指令
append(compileC(self, env), List::[Eval])
常数则直接push
Num(n) => List::[PushInt(n)]