为 Scheme 实现准备的 IL（中间语言） 和执行模式 原文档
BiwaScheme 是一个基于虚拟机的字节码解释型语言，Scheme 代码通过 BiwaScheme.Compiler 翻译为中间语言，并随后在 BiwaScheme.Interpreter 中解释执行
实现的大部分字节码设计基于 R. Kent Dybvig 1987 年发布的论文 《三种 Scheme 实现模型》
显然地，这里描述的 不是 BiwaScheme VM，但与之类似
typedef struct SchemeVMSt {
Value *stack; // SchemeVM 栈
unsigned freeIndex; // 指示栈上空闲位置起始（空栈模式）
unsigned stackSize; // 指示栈大小
Value value; // 临时变量
OpCode *operations; // 接下来执行的字节码数组
Closure func; // 当前正在执行的闭包对象
} SchemeVM;执行栈的实现非常简单，在 Java 等应用层高级程序设计语言中，你可以使用 ArrayList、LinkedList 等实现它
空栈是指堆栈将栈顶指针指向下一个为空的位置，压入栈帧时递增栈指针，相对的满栈则将栈顶指针指向当前位置
typedef struct StackStruct {
Value *items;
unsigned freeIndex;
unsigned stackSize;
unsigned maxSize;
} Stack;
Value Stack_push(Stack &stack, Value value);
Value Stack_pop(Stack &stack, Value value);
Value Stack_peek(Stack &stack); // 只取栈顶的值，不移除它
bool Stack_empty(Stack &stack);闭包对象包含关于 自由变量（外部变量） 的信息
当我们需要一个外部变量的值的时候，就会用到 func 寄存器了
字节码 refer-free 和 assign-free 需要这个寄存器
将 val 置入 value 寄存器
vm.value = op1(display 'Hello)frame
constant "Hello"
# value = "Hello"
argument
# stack = ["Hello"]
constant 1
# value = 1
argument
# stack = [1, "Hello"]
refer-global "display"
apply
halt将 value 压入执行者栈，一般作为函数参数
这意味着它要读取旧的栈大小并写入新栈大小（维护栈指针）
vm.stack << vm.value(print "Hi")constant "Hi"
# value = "Hi"
argument
# stack = ["Hi"]测试 value 寄存器的值，如果为真，跳转到 then 分支执行，否则跳转到 else
if vm.value then
vm.ip = op1
else
vm.ip = op2
end(define val (if 1 2 3))constant 1
test 2 3 # branch_then, brance_else
constant 2 # if 1 then value = 2
constant 3 # else 3
argument # [2 or 3]
constant "val"
argument # ["val", 2 or 3]
constant 2
argument # [2, "val", 2 or 3]
refer-global "define"
apply # apply global "define" argsize=2 "val", 2 or 3创建可以用数组表示的 Scheme 闭包对象到 value 寄存器
close freevar_num, dotpos, body, body_size, nextfreevar_num: 自由变量，也即引用的外部变量个数
自由变量应该使用 box 封装
dotpos: 可变参数起始索引
(lambda vararg ...) : 0 ; vararg
(lambda (a . rest) ...) : 1
(lambda (a b . rest) ...) : 2
(lambda (a b c) ...) : -1 ; no vararg
(lambda () ...) : 0 ; no argumentvm.value = make_closure(op1, op2, op3, op4)
vm.ip = op5 # next(lambda () 1)
(define (f a b)
(lambda () a b))
(f 11 22)
(define (f a b)
(set! a 99)
(lambda () a b))
(f 11 22)close 0, -1, 1, 2, 3
constant 1
return
halt
;; insns omitted ;;
; (lambda () a b))
refer-free 0
refer-free 1
return
; (lambda () a b))
refer-free 0
indirect
refer-free 1
return捕获当前程序执行状态，这将会创建一个 Closure，其中包含执行栈的复制和还原程序上下文使用的 nuate 指令
conti n next
n 是要移除的外部 lambda 参数个数
nuate saved_stack next
当执行这条指令时，解释器栈会被保存栈 saved_stack 替换
这条指令只会在运行时由字节码解释器创建，因为编译器不知道关于运行时栈的信息
(define cc (call/cc identity))
(cc)refer-local 0
nuate <saved stack> 2
return终止虚拟机指令循环。告诉虚拟机程序已经结束执行
apply 函数前必须调用 frame，除非是在尾递归优化中
frame next, after
一般，栈帧包含这些信息：
- 返回地址，即
after的位置 freeIndex，即上层栈帧地址closure，即当前执行的闭包对象
return 一般用于提前从调用中返回
(print 11)frame 1, 7 ; halt
constant 11
argument
constant 1
argument
refer-global "print"
apply
haltframe 自己一般不更新上层栈指针，而由 apply 来更新，因为函数参数必须在这一层执行
apply 没有参数，可以用来执行原生函数和 Closure
执行时，它先 get value 出需要 apply 的 applicable 对象，再 pop 出参数个数，最后是参数 arg1, arg2...
(+ 11 12)constant 12
argument ; arg2: 12
constant 11
argument ; arg1: 11
constant 2
argument ; argn: 2
refer-global "+" ; fun: +
apply ; +(11, 12)类似 apply，不过在允许基本调用栈调试的情况下进行尾递归优化
我们使用这些变量来保存调用调试信息：
var lastRefer: String
val callStack: Stack<String>
val tcoCounter: Stack<Integer>return 会将栈顶的栈帧弹出，一般用于从函数返回
shift n_args
shift 把栈帧顶的 n 个参数移除，以便使用这层栈帧尾调用函数
- local
refer-local pos
- free
refer-free pos
用于索引闭包的自由变量
- global
refer-global name-symbol
格式皆为 assign-* id
将 value 寄存器的值赋予 id
为一个本地变量创建一重指针 box local-slot
indirect 可以从 value 寄存器里解包（unwrap）出包装的值
#include <stdint.h>
#include <stddef.h>
// nil, boolean, reference, number
// integer, C function, string, mapping
// closure, vm state
#define TNIL 0
#define TBOL 1
#define TREF 2
#define TNUM 3
#define TINT 4
#define TFUN 5
#define TSTR 6
#define TMAP 7
#define TLBA 8
#define TSVM 9
#define ttype(o) (o.info.type)
#define trefc(o) (o.info.refc)
// 字节码为 64 位整形
typedef int64_t OpCode;
// 元类型
struct ValueBase {
unsigned short type; // 值类型
unsigned short refc; // 引用计数
};
// 字符串
struct StringStruct {
struct ValueBase info;
unsigned long hash;
size_t length;
char buffer[1];
};
// 浮点数值
struct NumberStruct {
struct ValueBase info;
double number;
};
// 整形数值
struct IntegerStruct {
struct ValueBase info;
long integer;
};
// 引用、C 函数
struct ReferenceStruct {
struct ValueBase info;
void *pointer;
};
// 实际上都是 Value 类型，但我太菜就算了
typedef struct KvPairStruct {
void *key;
void *value;
} KvPair;
// 映射
struct MapStruct {
struct ValueBase info;
size_t kvlength;
KvPair *pairarray;
};
// 闭包
struct ClosureStruct {
struct ValueBase info;
OpCode *insns;
KvPair *binding;
unsigned dotpos;
// rest args num, -1 means not vararg, 0 means no argument
};
typedef struct ClosureStruct Closure;
// 执行状态
struct StateStruct {
struct ValueBase info;
void *vm; // 不会互相引用，就无类型了
};
// 值引用
struct ValueStruct {
unsigned short type, refc;
union {
struct StringStruct str;
struct NumberStruct num;
struct IntegerStruct integer;
struct ReferenceStruct ref;
struct MapStruct map;
struct ClosureStruct lba;
struct StateStruct vm;
};
};
typedef struct ValueStruct Value;
typedef struct VMStackFrameStruct {
Value *stack; // SchemeVM 栈
unsigned freeIndex; // 指示栈上空闲位置起始（空栈模式）
unsigned stackSize; // 指示栈大小
} VMStackFrame;
// 虚拟机
typedef struct SchemeVMStruct {
VMStackFrame *stack; // SchemeVM 栈帧数组
unsigned freeIndex; // 指示栈上空闲位置起始（空栈模式）
unsigned stackSize; // 指示栈大小
Value value; // 临时变量
OpCode *operations; // 接下来执行的字节码数组
Closure func; // 当前正在执行的闭包对象
} SchemeVM;