Aura 一个嵌入式小语言

上周看到了 Redis 作者的新玩具语言 Aocla ，感觉很有启发。它是 FORTH 和 Lisp 的杂合体，又增加了一些内嵌局部变量的支持。非常像我前两年给我们数学库做的一个小东西。最初的想法是为数学库设计一个 DSL 潜入 Lua ，在做复杂的数学计算过程时，可以把计算过程停留在 C Side ，减少 Lua 和 C 之间的边界成本。最初的版本是我模仿 FORTH 设计的基于栈的小语言。希望牺牲一些表达能力，换取一点性能。但实用起来过于别扭，后来又增加了一些特性却没有本质改进。最后终于决定把这个 DSL 彻底从数学库中剥离了 。

看过 Aocla 后，我又有了一些新的想法。Aocla 只有一千多行代码，我判断实现这么一个小玩具应该在 2 天之内，所以实验成本并不高。那么，不如直接动手试试重新实现一个看看。

我并没有看 Aocla 的具体实现。我设想的 DSL 只是提供完整的控制结构，数据类型基于 list 就够了。这方面我已有一些经验 写起来应该很顺手。参与运算的数值类型应该是根据需求从外部注入的，类似 Lua 的 userdata ，但提供更高的效率以及类型支持。毕竟，在 Lua 中实现自定义数据类型最大的问题是它们是二等公民，Lua 和 C 之间的边界成本颇高。

如果是嵌入 Lua 使用，那么原生的 string 类型是不必要的。所有数值都可以是类型加 ID ，它们就有了固定的大小。我们的用 DSL 编写的代码规模并不会太大，代码本身也是 list ，赋予它们 64K 的代码空间是可以合理的限制。

这个 DSL 是一个函数式语言，所有的值都是不变量，包括 list 。这样可以保证执行过程是不修改已有状态的。我们把每个执行过程都看成是栈上的若干输入，经过处理，产生若干输出。运行过程需要的空间，处理栈，还需要有一个存放临时生成 list 的堆，可以采取只分配不释放的原则，我们并不需要实现复杂的 GC 。在每个执行过程完毕后，堆栈都可以直接复位。由于不需要 GC ，所以那些原本需要为回收保留的元信息：引用计数器或垃圾标记都可以省略，数据也会更紧凑，或许 64K 的空间就够完成绝大部分任务了。

上面多次强调 64K 的上限，也是为了让内部索引可以在 2 字节内表示，这能进一步的让数据更紧凑。

在我的版本中，基本采用了 Aocla 的设计。但也有一些不同点：

我把 list 分成了两种不同的子类型，一是由代码注入的不变量，由 parser 从 string 构建出来。它更为紧凑，所有的 word （从 FORTH 中借来的概念）都在 parser 过程翻译成 16bit 的 id 。所以每个 list 就是一个 id 数组。我认为像 42 这样的数字、true false 这样的布尔常量，eval def 这样的内置方法，都应该是同一种东西，它们都对应着一个 C Side 的函数，用来改变运行栈。

比如 “42” 其实是一个把整数 42 压入运行栈的 word ，true 则会在栈上产生一个布尔真。parser 在做翻译的时候，只需要切割 word ，用紧凑的方式组成嵌套 list 的形式就可以了。其中内置数据类型的值以常量表的形式也放在代码块中。

运行时，程序可以动态产生一些 list （称之为 dlist ），它们会把“值” 直接放在 list 内。相比 parser 产生的 word list （称之为 slist），它体积更大一些。dlist 中可以包含 slist 的引用、而 slist 中不会包含 dlist 的引用。最重要的 eval ，同时支持 dlist 和 slist 两种 list 并不是难事。

前面提到了，我并不打算实现 GC ，每段程序运行完都直接用 O(1) 的方法重置堆栈。那么，是否还允许在运行期构建新 word 呢？我觉得这是一个可选的特性，如果有会更方便。

对于构建 word 的 def ，如果它定义的是一个 slist ，那么只需要在单词表中记录一下索引就好了。如果是一个 dlist ，为了阻止数据在运行完后被回收，我把运行堆设计为两端向中间使用的。运行过程中产生的 dlist 顺着堆底部向顶部堆叠，等运行完毕后重置。而如果对 dlist 调用 def 的话，则把该 dlist deepcopy 到堆的顶部，永久保存下来。

对于局部变量，我认为是 Aocla 的设计亮点，自然也继承了下来。我把局部变量的数量上限提高到了 255 个，并使用更长的单词（而不是单字母）。它们会在 parser 过程就翻译成单字节的 ID 。

注意，局部变量的名字和 word 的名字一样，在 VM 中其实是保留了单词表的字面串的，这些信息可以用于输出调试信息。不过为了避免变成的字符串结构，VM 中保存的字符串都是字符串的开头有限字节（16 字节）加上 32bit 的 hash 值。也就是说，如果两个字符串的前 15 字节（添加了 0 结束符）相同，且完整字符串的 hash 值也相同，就认为它们是同一个词。我相信这个限制是合理的，够用了。

Aocla 的 tuple 类型就是为了给局部变量赋值。例如 1 2 3 4 (x y z w) 就相当于 x = 1 , y = 2 , z = 3, w = 4 。这让基于栈的语言写起来更自然。我限制了 tuple 的元素个数不超过 4 个，这样可以把 (x y z w）看作是一个 word ，它由 4 个局部变量 ID 构成，可以放在 32bit 的字段中。如果 tuple 的元素个数不足 4 个，就用 255 填充。

上周四和上周五，我花了两个半天时间把上面的基础功能搭建好。这周一又用了一整天的时间完善以及修理明显的 Bug 。完成了一个粗糙的版本 。它没有完全实现 Aocla 的功能（主要是 list 的运行期构建），但加上并不复杂，因为不再涉及 VM 的细节。

这个版本最大的特色应该是其内部数据结构都用相当简单的基础结构构成的。没有指针，没有动态数组。这让程序运行时没有任何动态内存分配。一旦内存耗尽，能体面的结束计算过程。

Parser 的错误报告很简陋，而且没有实现像注释这样的必要特性。这倒不是我偷懒，而是我觉得它的语法足够简单，所以应该用最简单的代码实现最必要的功能：只解析 list 嵌套和分词即可。如果未来想实用，可以用同样简单的代码以 Lua 的形式（使用模式匹配）重新实现一版。在 Lua 版本中，可以更方便的加入过滤注释、提供解析错误后的完整错误报告等。

我还没有设计注入自定义数据类型的 C API ，想来不复杂。Lua binding 没开始动手。因为我注意到，其实它比 Lua 并没有明显的性能优势（这是我一开始的需求）。这并不意外，因为单从内置的控制结构、内置数据类型的处理流程看，同样是解释语言，Lua 已经优化到了极致。我不可能随手写个玩具就能超过它。

而潜在的优势仅在于它和 C 打交道的部分可以比 Lua 更轻量。代价是我们注入 C 代码时要更小心。不过目前看起来，虽然新的 DSL 比我之前的那版要稍微好用一些，但离好用还远远不够。暂时还只是个玩具吧。

最重要的一点：我的收获和 Antirez 一样，我有两个月没怎么写代码了。精力都放在游戏项目（的非代码工作）上。做这么一个千行级别的玩具项目让我恢复了写代码的感觉，非常的开心。

上周看到了 Redis 作者的新玩具语言 Aocla ，感觉很有启发。它是 FORTH 和 Lisp 的杂合体，又增加了一些内嵌局部变量的支持。非常像我前两年给我们数学库做的一个小东西。最初的想法是为数学库设计一个 DSL 潜入 Lua ，在做复杂的数学计算过程时，可以把计算过程停留在 C Side ，减少 Lua 和 C 之间的边界成本。最初的版本是我模仿 FORTH 设计的基于栈的小语言。希望牺牲一些表达能力，换取一点性能。但实用起来过于别扭，后来又增加了一些特性却没有本质改进。最后终于决定把这个 DSL 彻底从数学库中剥离了 。

看过 Aocla 后，我又有了一些新的想法。Aocla 只有一千多行代码，我判断实现这么一个小玩具应该在 2 天之内，所以实验成本并不高。那么，不如直接动手试试重新实现一个看看。

我并没有看 Aocla 的具体实现。我设想的 DSL 只是提供完整的控制结构，数据类型基于 list 就够了。这方面我已有一些经验 写起来应该很顺手。参与运算的数值类型应该是根据需求从外部注入的，类似 Lua 的 userdata ，但提供更高的效率以及类型支持。毕竟，在 Lua 中实现自定义数据类型最大的问题是它们是二等公民，Lua 和 C 之间的边界成本颇高。

如果是嵌入 Lua 使用，那么原生的 string 类型是不必要的。所有数值都可以是类型加 ID ，它们就有了固定的大小。我们的用 DSL 编写的代码规模并不会太大，代码本身也是 list ，赋予它们 64K 的代码空间是可以合理的限制。

这个 DSL 是一个函数式语言，所有的值都是不变量，包括 list 。这样可以保证执行过程是不修改已有状态的。我们把每个执行过程都看成是栈上的若干输入，经过处理，产生若干输出。运行过程需要的空间，处理栈，还需要有一个存放临时生成 list 的堆，可以采取只分配不释放的原则，我们并不需要实现复杂的 GC 。在每个执行过程完毕后，堆栈都可以直接复位。由于不需要 GC ，所以那些原本需要为回收保留的元信息：引用计数器或垃圾标记都可以省略，数据也会更紧凑，或许 64K 的空间就够完成绝大部分任务了。

上面多次强调 64K 的上限，也是为了让内部索引可以在 2 字节内表示，这能进一步的让数据更紧凑。

在我的版本中，基本采用了 Aocla 的设计。但也有一些不同点：

我把 list 分成了两种不同的子类型，一是由代码注入的不变量，由 parser 从 string 构建出来。它更为紧凑，所有的 word （从 FORTH 中借来的概念）都在 parser 过程翻译成 16bit 的 id 。所以每个 list 就是一个 id 数组。我认为像 42 这样的数字、true false 这样的布尔常量，eval def 这样的内置方法，都应该是同一种东西，它们都对应着一个 C Side 的函数，用来改变运行栈。

比如 “42” 其实是一个把整数 42 压入运行栈的 word ，true 则会在栈上产生一个布尔真。parser 在做翻译的时候，只需要切割 word ，用紧凑的方式组成嵌套 list 的形式就可以了。其中内置数据类型的值以常量表的形式也放在代码块中。

运行时，程序可以动态产生一些 list （称之为 dlist ），它们会把“值” 直接放在 list 内。相比 parser 产生的 word list （称之为 slist），它体积更大一些。dlist 中可以包含 slist 的引用、而 slist 中不会包含 dlist 的引用。最重要的 eval ，同时支持 dlist 和 slist 两种 list 并不是难事。

前面提到了，我并不打算实现 GC ，每段程序运行完都直接用 O(1) 的方法重置堆栈。那么，是否还允许在运行期构建新 word 呢？我觉得这是一个可选的特性，如果有会更方便。

对于构建 word 的 def ，如果它定义的是一个 slist ，那么只需要在单词表中记录一下索引就好了。如果是一个 dlist ，为了阻止数据在运行完后被回收，我把运行堆设计为两端向中间使用的。运行过程中产生的 dlist 顺着堆底部向顶部堆叠，等运行完毕后重置。而如果对 dlist 调用 def 的话，则把该 dlist deepcopy 到堆的顶部，永久保存下来。

对于局部变量，我认为是 Aocla 的设计亮点，自然也继承了下来。我把局部变量的数量上限提高到了 255 个，并使用更长的单词（而不是单字母）。它们会在 parser 过程就翻译成单字节的 ID 。

注意，局部变量的名字和 word 的名字一样，在 VM 中其实是保留了单词表的字面串的，这些信息可以用于输出调试信息。不过为了避免变成的字符串结构，VM 中保存的字符串都是字符串的开头有限字节（16 字节）加上 32bit 的 hash 值。也就是说，如果两个字符串的前 15 字节（添加了 0 结束符）相同，且完整字符串的 hash 值也相同，就认为它们是同一个词。我相信这个限制是合理的，够用了。

Aocla 的 tuple 类型就是为了给局部变量赋值。例如 1 2 3 4 (x y z w) 就相当于 x = 1 , y = 2 , z = 3, w = 4 。这让基于栈的语言写起来更自然。我限制了 tuple 的元素个数不超过 4 个，这样可以把 (x y z w）看作是一个 word ，它由 4 个局部变量 ID 构成，可以放在 32bit 的字段中。如果 tuple 的元素个数不足 4 个，就用 255 填充。

上周四和上周五，我花了两个半天时间把上面的基础功能搭建好。这周一又用了一整天的时间完善以及修理明显的 Bug 。完成了一个粗糙的版本 。它没有完全实现 Aocla 的功能（主要是 list 的运行期构建），但加上并不复杂，因为不再涉及 VM 的细节。

这个版本最大的特色应该是其内部数据结构都用相当简单的基础结构构成的。没有指针，没有动态数组。这让程序运行时没有任何动态内存分配。一旦内存耗尽，能体面的结束计算过程。

Parser 的错误报告很简陋，而且没有实现像注释这样的必要特性。这倒不是我偷懒，而是我觉得它的语法足够简单，所以应该用最简单的代码实现最必要的功能：只解析 list 嵌套和分词即可。如果未来想实用，可以用同样简单的代码以 Lua 的形式（使用模式匹配）重新实现一版。在 Lua 版本中，可以更方便的加入过滤注释、提供解析错误后的完整错误报告等。

我还没有设计注入自定义数据类型的 C API ，想来不复杂。Lua binding 没开始动手。因为我注意到，其实它比 Lua 并没有明显的性能优势（这是我一开始的需求）。这并不意外，因为单从内置的控制结构、内置数据类型的处理流程看，同样是解释语言，Lua 已经优化到了极致。我不可能随手写个玩具就能超过它。

而潜在的优势仅在于它和 C 打交道的部分可以比 Lua 更轻量。代价是我们注入 C 代码时要更小心。不过目前看起来，虽然新的 DSL 比我之前的那版要稍微好用一些，但离好用还远远不够。暂时还只是个玩具吧。

最重要的一点：我的收获和 Antirez 一样，我有两个月没怎么写代码了。精力都放在游戏项目（的非代码工作）上。做这么一个千行级别的玩具项目让我恢复了写代码的感觉，非常的开心。