主要观点:Go 缺乏适当的尾调用,标准实现中尾部位置的调用会增长栈,这阻止了将状态机直接实现为递归调用的函数集合,但通常的变通方法——迷你解释器,可以轻松地增量执行状态机,而无需依赖协程等额外语言特性。
关键信息:
- Go 中 lexer 在
template
包中通过在指令指针中编码部分状态来解决尾调用缺乏问题,使用类似stateFn func(*lexer) stateFn
的类型和循环来模拟尾调用。 - 标准 ML 中无法表达
stateFn
类型,这是对“无法在标准 ML 中类型化的东西就不值得类型化”这一普遍观念的反例。 - 手动消除尾调用效率低下,因为间接调用可能被错误预测,原调用是直接调用,所以希望有直接的语言支持尾调用。
- 代码中的
lexer.emit(itemLeftDelim)
是协程 yield,使 lexer 增量式工作,将结果传递给调用者,但在 Go 中因为 goroutine 提供并行性且在包初始化时被禁止,所以需要避免在template
包中使用 goroutine,可通过扩展迷你解释器来避免使用 goroutine。 - 除了
stateFn
类型,整个构造不需要特殊语言特性,关键是如果使用直接尾调用而不是迷你解释器,这种方法是不可能的。
重要细节:
- 如
for state!= nil { state = state(l) }
是在缺乏尾调用的系统上模拟尾调用的标准方式,GHC 与 C 后端以及 JVM 上的各种函数式语言实现都使用了该方式。 - 从尾调用改为当前 Go 源代码中的形式,如
func lexLeftDelim(l *lexer) { if... }
。 - 迷你解释器扩展为
for { select { case item := <-l.items: return item default: l.state = l.state(l) } }
,lexer 动作无需改变,可继续使用lexer.emit()
函数。 - 用通道和条件接收不是必需的,只是方便,可参考 Nigel Tao 的相关内容。
- 有在标准 ML 中编码
stateFn
类型和原始run
函数的方式。 - 修订记录包括 2011 年 10 月 9 日发布、10 月 11 日包含附录、2012 年 9 月 1 日的澄清等。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。