Calcit IR 梳理

[tiye]

概览

Calcit 目前有两种运行方式:

• compact.cirru 源码, 经过 preprocessing(符号处理, 宏展开), 经过 runner 解释执行.
• compact.cirru 源码, 经过 preprocessing, 调用的 emit_js 生成 JavaScript, 由 js 引擎执行.

preprocessing 步骤中, 源码很多偏语法性质的抽象, 被 macro 展开, 语法糖就去掉了,
最终剩下:

• fn, 动态函数, 用户生成, 存储的是 Calcit 数据, 执行时需要绑定参数, 访问 scope, 解释 body 中的代码,
• proc, 内置函数, 只存储函数名称, 通过 Rust 函数执行,
• syntax 核心语法, 活动参数执行之前的 Cirru 节点, 然后 Rust 函数处理. 跟 proc 的区别在于符号先不执行, 由 Rust 处理看是否要何时要执行.

核心语法是非常少的, 其中 eval macro* 是跟元编程相关,
if let try 控制逻辑相关,
defatom reset! 是处理状态,
另外 foldl foldl-shortcut sort 出于高阶函数调用和性能的原因, 在 Rust 环境目前只好通过语法实现,

https://github.com/calcit-lang/calcit_runner.rs/blob/9a0ac7bbae4812e5c0e1852dcf179fda76254d14/src/builtins.rs#L288-L309

而函数, 目前实现的就比较多了. 随着后续迭代应该还会增加的.
另外由于 #44 当中的计划, 会将通用函数做一定的拆分,
比如原来的 count 函数, 后续会拆出 &map:count &list:count &str:count &set:count 多个, 再分别通过 .count 调用.
预期 proc 部分的函数定义会逐渐臃肿.

https://github.com/calcit-lang/calcit_runner.rs/blob/9a0ac7bbae4812e5c0e1852dcf179fda76254d14/src/builtins.rs#L18-L150

IR 的结构

不难看出, preprocessing 步骤是代码本身的简化, 而后续基于其结果可以分别用不同的执行方式.
目前 Calcit IR 指的就是 preprocessing 的结果, 以及导出的一份数据. 或者可以认为是简化后的程序的信息.
所以现在 cr --emit-ir -1 命令, 可以生成一个 js-out/program-ir.json 的文件, 其中就是状态.

IR 结构是简化的代码, 大体结构还是比较简单的(麻烦的地方是内部函数包含的一些语义),
然后因为 Calcit 从 Clojure 继承了 namespace 的方案, 所以数据的顶层是 namespaces, 表示成 HashMap:

https://github.com/calcit-lang/calcit_runner.rs/blob/9a0ac7bbae4812e5c0e1852dcf179fda76254d14/src/codegen/gen_ir.rs#L10-L33

顶层结构 IrData:

https://github.com/calcit-lang/calcit_runner.rs/blob/9a0ac7bbae4812e5c0e1852dcf179fda76254d14/src/codegen/gen_ir.rs#L29-L33

每个 namespace 对应一个 IrDataFile, 主要用到 defs 部分.
imports 部分在 preprocessing 过程有把信息标记到 symbol 当中, 以后可能用不到了.

https://github.com/calcit-lang/calcit_runner.rs/blob/9a0ac7bbae4812e5c0e1852dcf179fda76254d14/src/codegen/gen_ir.rs#L17-L20

代码部分, 由于带着语义, 所以显得还是臃肿的, 这里是直接把信息转成了 JSON,
literal 类型如果能用 JSON 表示, 就直接标出出来. 以及 Calcit 的 syntax, proc, 都比较容易表示.
比较麻烦的 symbol 部分, preprocessing 时候做过一些识别, 指向局部作用域, 还是某个定义,
这个对于解释执行来说大致足够了, 但是要做进一步优化, 不清楚怎么做...

https://github.com/calcit-lang/calcit_runner.rs/blob/9a0ac7bbae4812e5c0e1852dcf179fda76254d14/src/codegen/gen_ir.rs#L78-L157

其中, macro 预期是在 preprocessing 当中完成的, 即便调用 eval, 也会有 preprocessing 的过程,
所以在 IR 当中预期不会存在 macro, 除非是特殊的用法, 但是应该不涉及到计算了.

另外 symbol 当中主要是符号字符串, 以及对应的 namespace, 另外就是查找到的引用信息了,
这部分信息就是前面说的从"作用域引用", 从定义引用, 还有就是语法符号比如 &.
这些信息是包含语义的, 所以转向更底层的指令时需要再编译掉.

https://github.com/calcit-lang/calcit_runner.rs/blob/9a0ac7bbae4812e5c0e1852dcf179fda76254d14/src/primes.rs#L16-L21

关于 VM

最初 Calcit 设计现在的 HashMap 结构, 主要是为了热替换的方便,
但是从性能出发, 这个方案是不充分的. 提高性能要求更低层的代码抽象.
至少对于动态语言而言, VM 比起生成机器码是更合适的方案.

我之前考虑 calx-vm(还没启动) 打算用的是动态的方案,
定义数据类型的时候按照 Calcit 的一些基础类型定义,
这样保持一个动态特性的语义, 跟 Calcit 本身大致能对应上,
不过除了 List 就不提供更加复杂的数据结构了, 影响性能.
另一方面, 参考 WASM 的控制流语法, 通过 block br loop 进行控制.
目前 Calcit 消耗在控制流和函数调用性能挺多的, 这部分特别需要优化掉.

不可变数据问题. 我看了看网上的 bytecode VM 教程, 看上去讲的都是基于 int, float 做的,
具体堆上的数据结构怎么去交互还没懂, 但是那些例子用的也是 mutable data.
而现在 Calcit 当中是 immutable data 语义, 那么这块怎么转化过来? 没想明白.

主要的目标是性能, 现在 Calcit 的问题就是基于 Lisp 思路, 抽象过多, 无法实现高性能.
不过话说回来究竟底层应该怎样设计, 我也还不清楚,
janet 是个可以参考的例子, 有 Lisp, 有 VM. 不过 Calcit 不同还是在于不可变数据.

错误定位, 调用 ABI 之类暂不考虑...

影响因素

• 内置函数

内置函数随着功能增多而增加, 如果设计 VM, 是需要在底层同步增加, 还是其他方式保证 VM 底层稳定?

• 语法符号

目前主要是 & 符号, 跟 JavaScript 中的 ... 相似, 用于处理函数的展开等等.
对于生成低级代码来说, 这部分要怎么处理? 低级代码是应该去掉这部分语义的.

• methods 设计

从 Lisp 角度出发时, 所有的调用, 不是 syntax, 就是 proc 或者 fn, 而 macro 被预处理掉了.
按照 #44 增加了 method, 也就出现额外的 method 调用.
按照设计, method 可以对应到一个 Record 表示的函数调用上, 但这个关系绕了一圈.
具体怎么表现在低级代码, 要再看.