关于尾调用的观察

主要观点: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 日的澄清等。
阅读 9
0 条评论