**Arane设计笔记(第二版本)**
Shadee
2022-02-26
Last Update: 2022-03-01
得益于Matvey Soloviev所编写的[预编译器](https://github.com/blackhole89/macros),
第二个版本的Arane得以重新使用C语言完成.
相比与前一个版本的Arane, 此版本相对更加底层/复杂, 重大修改包括:
* 更小的内存占用, 更快的运行速度
* 底层支持的垃圾回收机制, 可选择引用计数或动态回收
* 编译友好的设计
* 破坏性的Hack设计
基本类型
================================================================================
Arane中的基本类型代表由引擎所提供的底层数据对象, 一个基本类型对象总是由以下几个部分组成:
1. 对象头部, 记录对象的类型, 元数据等等. 在翻译型的引擎中是必须的
2. 调试注解部分, 在调试模式下才存在, 见
Section [附加的调试元数据(Debug注解)]
3. 对象数据
对于引擎而言, 基本类型又分定长和变长两种, 这种分类和动态类型的对象可能会混淆,
比较典型的例子是: `ary`(Arane中的变长数组类型)被分类为定长类型,
因为`ary`类型的长度仅在运行期改变, 因此引擎并不需要额外的信息来编译;
而`id`(Arane中的字符串字面值)则被分类为变长类型, 因为对于每个的`id`,
引擎需要知道其长度才能编译.
## Number(数值类型)
有许多语言默认允许数值类型间的隐式转换, 然而, 由于Arane允许关闭核心指令集的类型检测功能,
因此无法**直接**实现数值的隐式转换(在预处理过程中添加转换过程是可以的),
只有`+`/`-`...等一部分数值运算指令支持自动检测, 但即使是这些指令也不支持不同类型间的互运算.
### nump(number-pointer)(平台特异数值类型)
该类型对应于C语言的`intptr_t`类型, 因此其长度是取决于各平台的.
在无说明的情况下, 引擎默认使用该类型作为各命令的传参类型, 这个类型是有符号的.
### numf(number-float)(双精度浮点类型)
对应C语言中的`double`类型, 长度为64位(在大多数平台下). 用于通常的数学运算.
### numi(number-int)(整数类型)
对应C语言中的`int32_t`类型, 长度为32位. 一般用于位运算, 字符串存储, 和通常的数学运算.
## Container(容器类型)
### cons(数据对类型)
和Lisp语言的Cons一致, 在其内部存储了两个指针.
### ary(array)(数组类型)
在内部存储任意数量的指针.
### dict(dictionary)(字典/哈希表类型)
提供键到值的唯一映射, 内部实现不透明, 在当前的CArane版本中,
由glib提供的`HashMap`类型实现.
## String(字符串类型)
### id(标识符类型)
类似于大多数语言中的定长`String`类型, 使用UTF-8编码, 无终结符,
使用一个动态编码的头部来指示长度.
## 其他类型
### nil(假值/空值类型)
无数据位, 表示逻辑假, 相当于C语言中的`NULL`值.
### link(强引用/弱引用/GC引用/外部引用类型)
TODO
垃圾回收策略
================================================================================
!!! warn
垃圾回收策略的实现方式是取决于各平台的, 以下所讲述的是当前版本的CArane中的实现.
## 回收策略之间的混合方式
和大多数现代的自动垃圾回收系统不同, Arane的垃圾回收系统是**混合**的,
允许不同回收策略的对象一并存在, 核心提供的回收策略包括自动/引用计数/手动几种,
同时, 也允许使用手动回收的方式来构建自定义的垃圾回收系统.
混合的垃圾回收系统中, 比较困难的是如何正确标记出需要保留的对象, 在当前的CArane中,
标记流程是从GC根对象开始, 递归扫描所有经过的对象, 遇到是GC类型的对象便进行标记,
因此, 虽然Arane支持不同策略的对象一起存在, 并不意味着各个策略的对象是独立存在的,
而是在同一个环境中互相作用的.
********************************************************************************
* .-. .-.n .-.
* | G |: GC Obj | R |: Reference Count Obj | S |: Manual Management Object
* '-' '-' n: Ref Count '-'
*-------------------------------------------------------------------------------
* :
* .-------. .-.1 .-. .-.1 :
* | GC Root +----->| R +--. | G +------->| R | :
* '-------' '+' | '-' '+' :
* | | | :
* v | v :
* .-. | .-. .-. : Before GC
* | S | '-->| G | | G | :
* '-' '+' '+' : Marking GC Obj
* | | :
* v v :
* .-. .-.2 .-. :
* | S | | R |<-------+ G | :
* '-' '-' '-' :
* :
*-------------------------------------------------------------------------------
* :
* .-------. .-.1 .-.0 :
* | GC Root +----->| R +--. | R | :
* '-------' '+' | '-' :
* | | :
* v | :
* .-. | .-. : During GC
* | S | '-->| G | :
* '-' '+' : GC Obj is cleaned
* | :
* v :
* .-. .-.1 :
* | S | | R | :
* '-' '-' :
* :
*-------------------------------------------------------------------------------
* :
* .-------. .-.1 :
* | GC Root +----->| R +--. :
* '-------' '+' | :
* | | :
* v | :
* .-. | .-. : After GC
* | S | '-->| G | :
* '-' '+' : Rc Obj is cleaned too
* | :
* v :
* .-. .-.1 :
* | S | | R | :
* '-' '-' :
* :
********************************************************************************
[一次GC的执行流程]
## 自动垃圾回收策略
### 处理/索引方式
当前的CArane假设用户代码对GC系统的依赖是相对较轻的(即不是所有对象都通过GC分配),
因此GC系统使用"标记/清理"方式进行垃圾回收,
1. GC事件开始
2. 从指定的域(默认是根域)开始迭代所有的存在对象, 将存活标记置0
3. 从指定的GC根(默认是全局GC根)开始递归索引所有可达对象, 将对应的存活标记置1
4. 从指定的域开始迭代所有的存在对象, 将不存活对象回收
5. 结束GC事件
因为只有部分对象通过GC分配, 在这种情况下, 为每一个GC对象分配索引并不会造成太大的开销,
因此在每次分配GC对象时, GC系统将首先用常规的分配器将对象分配到内存中, 然后,
在一个追踪表(即下面所讨论的域)中记录对应对象的指针以方便以后索引.
通过这种方式, CArane中的GC对象实际上是**非移动**的, 因此将GC对象传递到外部调用是安全的.
同时, 由于建立索引表的指针大小是固定的, 因此也不存在碎片化或重整理等问题.
### 基于域的索引模型/部分GC(Partial GC)
在大型程序中进行一次完全的垃圾回收是非常耗费时间,
因此各个基于自动垃圾回收的语言均采取了一些优化手段:
在Java/JavaScript中, 引擎(CMS,G1以及V8等)大都采用分代回收的机制,
将运行期对象分为新生代和老生代进行分级回收. 其中, 运行于新生代的回收基本上非常快速,
耗时基本上在微秒级别. 但一旦发生老生代的回收, 则会消耗相当长的时间, 一般在数到数十毫秒.
当然, 在设计优秀的Java程序中, 触发老生代回收的频率会相当低.
新老生代的核心思想就是将GC对象**分级**回收. 在Arane中, 虽然藉由混合管理模型减少了GC的必要,
但一旦发生GC, 从根部开始扫描所有对象依旧会耗费很多时间. 因此在当前的CArane中,
自动垃圾回收系统的索引是基于域的, 即将GC对象链接于一个个的表(即域)中, 而域之间也可以相互链接:
***********************************************************************
*
* .---------------------.
* Root Zone | A Zone | B Zone
* .-----------. | .-----------. | .-----------.
* | Zone Link +-' .-->| Obj Link +--. '-->| Obj Link +---.
* +-----------+ | +-----------+ | +-----------+ |
* | Zone Link +---' | ... | | | ... | |
* +-----------+ '-----------' | '-----------' |
* | Obj Link +-. | |
* +-----------+ | .-----. | |
* | Obj Link +-. '-->| Obj | v |
* +-----------+ | '-----' .-----. .-----. |
* | ... | | | Obj | | Obj |<--'
* '-----------' | .-----. '-----' '-----'
* '-->| Obj |
* '-----'
*
***********************************************************************
[CArane垃圾回收的域模型]
存在一个根域, 所有的域最终都将被直接/间接链接到根域. 因此, 对根域执行GC实际上就是进行全量GC.
执行部分GC时, 需要指定开始扫描的GC根(默认是全局的GC根), 这是手动指定的, 因此,
需要使用者了解对应GC根的可达范围.
对于GC域的可达范围小于GC根的情况, 称为"过扫描", 在这种情况下,
会多浪费一部分时间用于扫描父域的GC对象, 在某些情况下会造成悬空指针.
这种情况可以通过设置"弱引用"隔离父域对象来避免.
对于GC域的可达范围大于GC根的情况, 称为"遗漏", 在这种情况下, GC域的多余可达部分会被直接回收,
如果相应部分在某处仍可访问, 则形成悬空指针, 是绝对要避免的情况.
### 多线程下的自动垃圾回收
由于Arane的垃圾回收是"非移动"的, 因此在进行垃圾回收时并不会锁定所有线程, 所以,
Arane中可能会遭遇的多线程垃圾回收问题和多线程竞态访问是一样的,
只需要在对应被多个线程所访问的对象上加锁即可.
改进作用域策略
================================================================================
在A1中, 通过提供对作用域存储的访问和修改能力(`scope`和`eval`指令),
用户可以完全地自定义作用域的实现, 无论是动态作用域, 静态作用域, 还是其他什么类型.
这是非常灵活, 强大以及简单的设计(当然Store域是一个实在的败笔).
但是这样优秀的设计却最终招致铺天盖地的麻烦(和之后的惰性求值一起):
> "很难相信一个短短几十行的函数需要浪费我五天的时间,
> 而且即使写出来了也无法确定这几十行会如预期一般工作,
> 没有一丝的成就感, 只有满满的怀疑."
> -- Shadee
为了不让这种悲剧重演, A2必须在作用域策略上作出改变.
对于过于强大而无法使用的工具, 一般的解决办法无外乎两种: 限制能力和改变使用方法,
其实可以统一归纳为一种思路: 工具与实际问题的层次差距太大, 导致难以实用化, 因此要把工具特化.
## 从问题开始
让我们先观察一个例子:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ js linenumbers
let b = 1;
function a() {
let b = 0;
return function() {
return b;
}
}
let c = a();
console.log(c());
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ lisp linenumbers
(scope b 1)
(scope a
(raw
(block
(scope b 0)
(raw
(scope b)))))
(scope c (a))
(log (c))
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
第一段代码是一段简单的JS代码, 定义了一个函数闭包.
第二段代码是一段A1代码(在arane-rust环境下), "看上去"和JS版本的代码功能差不多.
但实际上有很大区别, 因为Arane是动态作用域的.
从更底层来讲, Arane的函数是无任何附加信息的, 在上面的例子中,
A1代码所定义的`c`函数实际上就是一个纯粹的`List`(`Cons`序列), 它的值为`(scope b)`.
因此当A1中的`c`被调用时, 它没有任何的其他信息, 直接将调用者的作用域归为己用, 返回`1`.
更极端的情况下, 因为它调用了环境中的`scope`函数,
所以如果它在一个没有`scope`函数的环境中被调用时, 会直接失败.
反观JS版本, 当`a`内部的匿名函数被定义时, 被建立的并不是一个形如`() -> {return b;}`的对象,
而是
~~~~~~~~~~~~~~~~ js
{
type: "Function",
source: () -> {return b;},
scope: [link to construct scope]
}
~~~~~~~~~~~~~~~~
这样的一个对象, 当这个对象(最终被赋值到`c`)被调用的时候, 是以形如
~~~~~~~~~~~~~~~~ js
call_with_scope(c.source, c.scope);
~~~~~~~~~~~~~~~~
这样调用的.
显而易见, A1版本的代码需要一些修改来实现相同的效果, 这是修改后的版本
(让我们假设`eval`指令不再需要可恶的`stack`和`store`参数):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ lisp linenumbers
(scope b 1)
(scope a
(raw
(block
(scope b 0)
(cons
(scope)
(raw
(scope b))))))
(scope c (a))
(log (eval (cdr (scope c)) (car (scope c))))
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这段代码会和JS产生相同的结果, 但还是有问题: 虽然我们封闭了`c`的定义作用域
(通过把作用域和代码封装进一个`Cons`的方式), 但当你调试的时候,
你会发现这个作用域和顶层作用域是同一个, 甚至产生了一个循环引用.
原因在于无论是`a`还是`c`函数都没有建立自己的新作用域.
实际上, 当一个JS函数建立的时候, JS引擎做的事情大概是:
1. 为这个函数建立一个新的作用域
2. 为这个新的作用域连接到建立时环境作用域
3. 将这个函数绑定到这个作用域并返回
参考上述流程, 最终, 一个逻辑上大致正确的版本如下
(虽然在使用引用计数进行回收的arane-rust环境中会因为循环引用而导致内存泄漏):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ lisp linenumbers
(scope b 1)
(scope a
(raw
(eval
(raw
(block
(scope b 0)
(cons
(cons (dict) (scope))
(raw
(scope b)))))
(cons (dict) (scope)))))
(scope c (a))
(log (eval (cdr (scope c)) (car (scope c))))
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
(注: 我没有进行检查, 我猜你大概也不想)
透过上面一段代码, 我想你已经大概清楚了其中的一部分烦恼. 因此大多数人都会这样想:
让我来写个自动处理这些环境问题的宏吧!
那么好吧, 以下就是这个想法付诸实践的样子(如果只是上面的问题的话大概会更加简单一点,
以下的代码还考虑了参数预求值/环形引用/命名参数等一系列问题):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ lisp linenumbers
(# func args(1) body(1))
(# Shadee-0型闭包函数定义指令)
(scope func
(list
packenv
(list
packenv
(raw (raw (store)))
(raw (list cons (link (scope)) (raw (scope))))
(raw
(list
cons
(list
dict
(list
maplist
(raw
(list
cons
(raw (car (args 0)))
(list eval (raw (car (cdr (args 0))))
(list raw (stack 1))
(raw (store))
(raw (cdr (scope))))))
(raw (raw (cons (args 0) (args 1))))
(list
list
(list raw (earg 0))
(raw (args))))))))
(raw (link (scope)))
(raw (cons block (earg 1)))))
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这个宏能正确工作吗? 很难确定, 因为光是理解它大概就是一个很艰苦的工作,
我也不建议你尝试去理解它, 因为我自己甚至不敢用它.
到这里, 你大概就会理解 **为什么** A1的作用域策略是有问题的.
## 解决问题的必胜法: 先理解问题
在尝试修改架构或是往里面添加指令之前, 让我们先搞清楚这个问题的本质.
首先假设一个
预处理流程
================================================================================
当前版本的Arane将一部分前一代的运行时逻辑分离了出来, 作为预处理流程来实现.
********************************************************************************
*
* |
* | Text Code
* |
* ................................|...............
* : v :
* : Read Process .-----------------. :
* : | Parse Macro Layer | :
* : '--------+--------' :
* : | :
* : | S-expr Code :
* : v :
* : .-----------------. :
* : | Token Macro Layer | :
* : '--------+--------' :
* : | :
* :...............................|..............:
* |
* | S-expr Code
* |
* ................................|...............
* : v :
* : Macro-processing .--------------------. :
* : | Semantic Parse Layer | :
* : Process '----------+---------' :
* : | :
* : | Runtime Objs :
* : v :
* : .-------------------. :
* : | Macro Explain Layer | :
* : '---------+---------' :
* : | :
* : | Runtime Objs :
* : v :
* : .---------------. :
* : | Obj Write Layer | :
* : '-------+-------' :
* : | :
* :...............................|..............:
* |
* | S-expr Code
* |
* .--------' '--------.
* ........................|...... ......|........................
* : | : : | :
* : Translate Runtime | : : | Bytecoding Process :
* : v : : v :
* : .--------------------. : : .--------------------. :
* : | Semantic Parse Layer | : : | Semantic Parse Layer | :
* : '----------+---------' : : '----------+---------' :
* : | : : | :
* : | Runtime Objs : : | Runtime Objs :
* : v : : v :
* : .--------------. : : .--------------. :
* : | Solidify Layer | : : | Solidify Layer | :
* : '-------+------' : : '-------+------' :
* : | : : | :
* : | Runtime Objs : : | Runtime Objs :
* : v : : v :
* : .-----. : : .--------------------. :
* : | Eval | : : | Obj Bytecoding Layer | :
* : '-----' : : '---------+----------' :
* : : : | :
* :.............................: :..............|..............:
* |
* .-----------------'
* |
* | Bytecode
* |
* .--------' '--------.
* ........................|...... ......|........................
* : | : : | :
* : Translate Runtime | : : | Compiling Process :
* : v : : v :
* : .-------------------. : : .-------------------. :
* : | Bytecode Load Layer | : : | Bytecode Load Layer | :
* : '---------+---------' : : '---------+---------' :
* : | : : | :
* : | Runtime Objs : : | Runtime Objs :
* : v : : v :
* : .-----. : : .-------. :
* : | Eval | : : | Compile | :
* : '-----' : : '---+---' :
* : : : | :
* :.............................: :..............|..............:
* |
* .-----------------'
* |
* | Executable Obj
* v
*
********************************************************************************
[Arane的代码处理流程(实际写出来之后, 发现其实还是很复杂的)]
TODO
## TODO
Hack式设计
================================================================================
和第一版本不一样, 在考量了运行速度, 内存占用, 便利性等因素后,
当前版本的Arane引入了一些不是那么"形而上"的设计. 这一定程度上破坏了理论模型的简洁性
(实际上原先的惰性求值特性几乎被完全抹去了), 但相应的带来了许多好处, 比如兼容性,
对汇编编译器的支持, 以及巨大的性能提升.
虽然好处多多, 但依旧是给新的架构模型引入了边角细节, 增加了理解的困难度.
实际如果你需要的是一个纯学术型的函数式计算架构, 则应该放弃使用该版本转而使用第一版,
该版本实际上是针对日常使用及生产环境优化的.
下面详细列出了各项Hack式修改以及进行修改的原因
(如果确定有更好的方案来解决这些问题的话将考虑修改对应的Hack).
## 所有类型的大小对齐到8字节
所有的基本类型的内存大小都将是8的整数倍.
这是为了防止未对齐时访问8字节长度的底层类型(如64位指针, 双精度浮点数)时产生性能问题.
引擎中所有定长类型(包括`numi`, `nil`, `cons`等等) 即使大小不足8字节也会被提升到8字节,
而大于8字节的则对齐到下一个整数倍.
不定长类型(包括`id`, `myst`等等)在运行时允许不对齐, 但其字节码表达必须对齐.
这是为了防止将来生成字节码编码的程序或数据对象时引发不对齐问题.
## 附加的类型头部元数据(头部注解)
在A1(第一代Arane)版本中, 对象是由一个指示类型和引用数的头部以及数据构成的,
因为A1是只使用引用计数回收对象的. 其他包括A1是"默认引用"的, 所以拷贝是手动的.
因此A1的对象结构得以设计得简单易懂.
在A2中, 由于各种原因导致类型的变得多样化, 但增加类型会导致嵌套关系变得复杂, 同时降低运行速度.
因此A2将类型头部拆解为多个部分加以复用, 以表达对象的一些特性. 这些Hack统称为"头部注解".
********************************************************************************
*
* .-------+-------+-------+-------. .-------.
* Bit Index | 0 ~ 5 | 6 ~ 7 | 8 | 9 ~11 | | 12~31 |
* +-------+-------+-------+-------+ +-------+
* Bit Size | 6 bit | 2 bit | 1 bit | 3 bit | | 20bit |
* +-------+-------+-------+-------+ +-------+
* Zone ID | TYPE | MEM | COPY | RESV | | REF_C |
* '-------+-------+-------+-------' '-------'
*
* .-------+-------+-------.
* | 12 | 13 | 14~31 |
* +-------+-------+-------+
* | 1 bit | 1 bit | 18bit |
* +-------+-------+-------+
* | GC_EN | GC_MK | RESV |
* '-------+-------+-------'
*
********************************************************************************
[标准的A2头部数据]
如表中所示, A2的对象头部占用`4byte`(`32bit`), 整个头部被划分为数个区域来使用:
### 任何情况下
* `RESV`:
保留位
* `TYPE`:
指示对象的类型, 占用`6bit`. 因此A2最大支持64种基本对象.
* `MEM`:
指示该对象的内存管理模型:
* `00`: 手动内存管理, 不进行任何形式的自动垃圾回收
* `01`: 保留位
* `10`: 引用计数管理, 计算被引用计数, 计数至0时回收
* `11`: 自动内存管理, 由GC系统管理该对象的回收
* `COPY`:
指示该对象的转移行为:
* `0`: 转移时只引用, 在对象被赋值时直接索引原对象
* `1`: 转移时复制, 在对象被赋值时拷贝一份再进行索引
!!! warn
该注解只是目前供引擎使用, 在框架进一步完善后将被去除, 因此开发者不应该使用该注解
### 当使用引用计数时
* `REF_C`:
指示该对象的被引用次数
### 当使用自动内存管理时
* `GC_EN`:
指示该对象是否参与此次垃圾回收流程, CArane引擎使用该位来识别"过扫描"的情况
* `GC_MK`:
指示该对象在此次垃圾回收中是否被标记
## 附加的调试元数据(Debug注解)
当CArane编译于调试模式下时, 对象的头部被拓展为`20byte`(`160bit`, 是不是有点大?),
与原先相比多出的`16byte`被分为3个区域使用, 以供调试器存储相关信息.
********************************************************************************
*
* .-----------. .-----------+-----------------------+-----------.
* | 4 byte | | 4 byte | 8 byte | 4 byte |
* +-----------+ +-----------+-----------------------+-----------+ ...
* | Head | | DB_HEAD | DB_DATA | RESV |
* '-----------' '-----------+-----------------------+-----------'
*
********************************************************************************
[Debug注解]
因为Debug注解的内容标准可能经常发生改变, 因此以下只解释每个区域大概的作用.
* `DB_HEAD`:
Debug注解的头部, 包含一些位数据/标记等等
* `DB_DATA`:
Debug注解的数据部分, 可能包含一个数字或指针
* `RESV`:
保留位, 为了对齐而添加
## 附加的Cons元数据(Cons注解)
TODO
## 附加的Link元数据(Link注解)
TODO
## 预处理(编译期处理)流程
和A1完全由运行期实现各种语言特性不同, A2将一部分语言特性从运行期提前了,
这些被提前处理的统称为"预处理", 详细参见 Section [预处理流程].
使用这个Hack的目的是为了让语言更易于理解, 减少运行时开销, 同时允许语言被编译为汇编形式.
## TODO