NUS CS1101S：SICP JavaScript 描述：五、使用寄存器机进行计算（2）-阿里云开发者社区

NUS CS1101S：SICP JavaScript 描述：五、使用寄存器机进行计算（1）https://developer.aliyun.com/article/1427742

作为这些函数如何使用的示例，我们可以定义gcd_machine为 5.1.1 节中 GCD 机器的模型，如下所示：

const gcd_machine =
    make_machine(
        list("a", "b", "t"),
        list(list("rem", (a, b) => a % b),
         list("=", (a, b) => a === b)),
        list(
          "test_b",
            test(list(op("="), reg("b"), constant(0))),
            branch(label("gcd_done")),
            assign("t", list(op("rem"), reg("a"), reg("b"))),
            assign("a", reg("b")),
            assign("b", reg("t")),
            go_to(label("test_b")),
      "gcd_done"));

make_machine的第一个参数是一个寄存器名称列表。下一个参数是一个表（包含两个元素列表的列表），将每个操作名称与实现该操作的 JavaScript 函数配对（即，给定相同的输入值产生相同的输出值）。最后一个参数指定控制器，格式为标签和机器指令的列表，就像 5.1 节中的格式。

要使用这台机器计算 GCD，我们设置输入寄存器，启动机器，并在模拟终止时检查结果：

set_register_contents(gcd_machine, "a", 206);
"done"
set_register_contents(gcd_machine, "b", 40);
"done"
start(gcd_machine);
"done"
get_register_contents(gcd_machine, "a");
`2`

这个计算将比用 JavaScript 编写的gcd函数运行得慢得多，因为我们将模拟低级机器指令，比如assign，通过更复杂的操作。

练习 5.7

使用模拟器测试您在练习 5.4 中设计的机器。

5.2.1 机器模型

make_machine生成的机器模型表示为使用消息传递技术在第 3 章中开发的本地状态的函数。为了构建这个模型，make_machine首先调用函数make_new_machine来构造所有寄存器机器共有的部分。由make_new_machine构建的基本机器模型本质上是一种包含一些寄存器和堆栈的容器，以及一个执行机制，逐个处理控制器指令。

然后函数make_machine扩展了这个基本模型（通过向其发送消息）以包括所定义的特定机器的寄存器、操作和控制器。首先，它为新机器中提供的每个寄存器名称分配一个寄存器，并在机器中安装指定的操作。然后，它使用一个汇编器（在第 5.2.2 节中描述）将控制器列表转换为新机器的指令，并将其安装为机器的指令序列。函数make_machine返回修改后的机器模型作为其值。

function make_machine(register_names, ops, controller) {
    const machine = make_new_machine();
    for_each(register_name =>
               machine("allocate_register")(register_name),
             register_names);
    machine("install_operations")(ops);
    machine("install_instruction_sequence")
           (assemble(controller, machine));
    return machine;
}

寄存器

我们将寄存器表示为具有局部状态的函数，就像第 3 章中一样。函数make_register创建一个可以访问或更改值的寄存器：

function make_register(name) {
    let contents = "unassigned";
    function dispatch(message) {
        return message === "get"
               ? contents
               : message === "set"
               ? value => { contents = value; }
               : error(message, "unknown request – make_register");
    }
    return dispatch;
}

以下函数用于访问寄存器：

function get_contents(register) {
    return register("get");
}
function set_contents(register, value) {
    return register("set")(value);
}

栈

我们也可以将栈表示为具有局部状态的函数。函数make_stack创建一个栈，其局部状态包括栈上项目的列表。栈接受请求将项目push到栈上，pop弹出栈顶项目并返回它，以及initialize将栈初始化为空。

function make_stack() {
    let stack = null;
    function push(x) {
        stack = pair(x, stack);
        return "done";
    }
    function pop() {
        if (is_null(stack)) {
            error("empty stack – pop");
        } else {
            const top = head(stack);
            stack = tail(stack);
            return top;
        }
    }
    function initialize() {
        stack = null;
        return "done";
    }
    function dispatch(message) {
        return message === "push"
               ? push
               : message === "pop"
               ? pop()
               : message === "initialize"
               ? initialize()
               : error(message, "unknown request – stack");
    }
    return dispatch;
}

以下函数用于访问栈：

function pop(stack) {
    return stack("pop");
}
function push(stack, value) {
    return stack("push")(value);
}

基本机器

make_new_machine函数，如图 5.13 所示，构造了一个对象，其局部状态包括一个栈、一个最初为空的指令序列、一个最初包含一个初始化栈操作的操作列表，以及一个寄存器表，最初包含两个寄存器，名为flag和pc（代表“程序计数器”）。内部函数allocate_register添加新条目到寄存器表中，内部函数lookup_register在表中查找寄存器。

图 5.13 make_new_machine函数实现了基本的机器模型。

flag寄存器用于控制模拟机器中的分支。我们的test指令将flag的内容设置为测试的结果（真或假）。我们的branch指令通过检查flag的内容来决定是否进行分支。

pc寄存器确定指令在机器运行时的顺序。这种顺序由内部函数execute实现。在模拟模型中，每条机器指令都是一个数据结构，其中包括一个没有参数的函数，称为指令执行函数，调用这个函数模拟执行指令。随着模拟的运行，pc指向指令序列中下一条要执行的指令的位置。函数execute获取该指令，通过调用指令执行函数来执行它，并重复这个循环，直到没有更多的指令需要执行（即，直到pc指向指令序列的末尾）。

作为其操作的一部分，每个指令执行函数修改pc以指示下一个要执行的指令。branch和go_to指令将pc更改为指向新的目的地。所有其他指令只是推进pc，使其指向序列中的下一条指令。请注意，每次调用execute都会再次调用execute，但这不会产生无限循环，因为运行指令执行函数会改变pc的内容。

函数make_new_machine返回一个分发函数，实现对内部状态的消息传递访问。请注意，启动机器是通过将pc设置为指令序列的开头并调用execute来完成的。

为了方便起见，我们提供了一个机器的start操作的替代接口，以及用于设置和检查寄存器内容的函数，如第 5.2 节开头所述：

function start(machine) {
    return machine("start");
}
function get_register_contents(machine, register_name) {
    return get_contents(get_register(machine, register_name));
}
function set_register_contents(machine, register_name, value) {
    set_contents(get_register(machine, register_name), value);
    return "done";
}

这些函数（以及第 5.2.2 和 5.2.3 节中的许多函数）使用以下内容来查找给定机器中具有给定名称的寄存器：

function get_register(machine, reg_name) {
    return machine("get_register")(reg_name);
}

5.2.2 汇编器

汇编器将机器的控制器指令序列转换为相应的机器指令列表，每个指令都有其执行函数。总的来说，汇编器很像我们在第 4 章中学习的求值器——它有一个输入语言（在本例中是寄存器机器语言），我们必须对语言中的每种组件执行适当的操作。

为每条指令生成一个执行函数的技术正是我们在 4.1.7 节中用来通过将分析与运行时执行分离来加速求值器的技术。正如我们在第 4 章中看到的，可以在不知道名称的实际值的情况下执行对 JavaScript 表达式的有用分析。在这里，类似地，可以在不知道机器寄存器的实际内容的情况下执行对寄存器机器语言表达式的有用分析。例如，我们可以用指向寄存器对象的指针来替换对寄存器的引用，并且可以用指向标签在指令序列中指定位置的指针来替换对标签的引用。

在生成指令执行函数之前，汇编器必须知道所有标签的引用，因此它首先通过扫描控制器序列来将标签与指令分离。在扫描控制器时，它同时构造了指令列表和一个将每个标签与指向该列表中的指针关联起来的表。然后汇编器通过为每条指令插入执行函数来增强指令列表。

assemble函数是汇编器的主要入口。它接受控制器序列和机器模型作为参数，并返回要存储在模型中的指令序列。assemble函数调用extract_labels来从提供的控制器构建初始指令列表和标签表。extract_labels的第二个参数是一个函数，用于处理这些结果：该函数使用update_insts生成指令执行函数并将其插入指令列表，然后返回修改后的列表。

function assemble(controller, machine) {
    return extract_labels(controller,
                          (insts, labels) => {
                              update_insts(insts, labels, machine);
                              return insts;
                          });
}

extract_labels函数接受一个名为controller的列表和一个名为receive的函数作为参数。函数receive将被调用并传入两个值：（1）一个名为insts的指令数据结构列表，其中包含来自controller的指令；和（2）一个名为labels的表，它将controller中的每个标签与其指定的insts列表中的位置关联起来。

function extract_labels(controller, receive) {
    return is_null(controller)
           ? receive(null, null)
           : extract_labels(
                 tail(controller),
                 (insts, labels) => {
                   const next_element = head(controller);
                   return is_string(next_element)
                          ? receive(insts,
                                    pair(make_label_entry(next_element,
                                                          insts),
                                         labels))
                          : receive(pair(make_inst(next_element),
                                         insts),
                                    labels);
                 });
}

extract_labels函数通过顺序扫描controller的元素并累积insts和labels来工作。如果一个元素是字符串（因此是标签），则将适当的条目添加到labels表中。否则，该元素将被累积到insts列表中。

update_insts函数修改了指令列表，该列表最初只包含控制器指令，以包括相应的执行函数：

function update_insts(insts, labels, machine) {
    const pc = get_register(machine, "pc");
    const flag = get_register(machine, "flag");
    const stack = machine("stack");
    const ops = machine("operations");
    return for_each(inst => set_inst_execution_fun(
                                inst,
                                make_execution_function(
                                    inst_controller_instruction(inst),
                                    labels, machine, pc,
                                    flag, stack, ops)),
                    insts);
}

机器指令数据结构简单地将控制器指令与相应的执行函数配对。当extract_labels构造指令时，执行函数尚不可用，而是稍后由update_insts插入。

function make_inst(inst_controller_instruction) {
    return pair(inst_controller_instruction, null);
}
function inst_controller_instruction(inst) {
    return head(inst);
}
function inst_execution_fun(inst) {
    return tail(inst);
}
function set_inst_execution_fun(inst, fun) {
    set_tail(inst, fun);
}

我们的模拟器不使用控制器指令，但保留它以便进行调试（参见练习 5.15）。

标签表的元素是成对出现的：

function make_label_entry(label_name, insts) {
    return pair(label_name, insts);
}

表中的条目将使用查找。

function lookup_label(labels, label_name) {
    const val = assoc(label_name, labels);
    return is_undefined(val)
           ? error(label_name, "undefined label – assemble")
           : tail(val);
}

练习 5.8

以下寄存器机器代码是模棱两可的，因为标签here被定义了多次：

"start",
  go_to(label("here")),
"here",
  assign("a", constant(3)),
  go_to(label("there")),
"here",
  assign("a", constant(4)),
  go_to(label("there")),
"there",

按照目前的模拟器，当控制到达there时，寄存器a的内容将是什么？修改extract_labels函数，使得汇编器在使用相同的标签名称指示两个不同位置时会发出错误信号。

5.2.3 指令及其执行函数

汇编器调用make_execution_function为控制器指令生成执行函数。就像第 4.1.7 节的求值器中的analyze函数一样，这根据指令类型分发以生成适当的执行函数。这些执行函数的细节决定了寄存器机器语言中各个指令的含义。

function make_execution_function(inst, labels, machine,
                                 pc, flag, stack, ops) {
    const inst_type = type(inst);
    return inst_type === "assign"
           ? make_assign_ef(inst, machine, labels, ops, pc)
           : inst_type === "test"
           ? make_test_ef(inst, machine, labels, ops, flag, pc)
           : inst_type === "branch"
           ? make_branch_ef(inst, machine, labels, flag, pc)
           : inst_type === "go_to"
           ? make_go_to_ef(inst, machine, labels, pc)
           : inst_type === "save"
           ? make_save_ef(inst, machine, stack, pc)
           : inst_type === "restore"
           ? make_restore_ef(inst, machine, stack, pc)
           : inst_type === "perform"
           ? make_perform_ef(inst, machine, labels, ops, pc)
           : error(inst, "unknown instruction type – assemble");
}

controller序列的元素由make_machine接收并传递给assemble，它们是字符串（用于标签）和带有标签的列表（用于指令）。指令中的标签是一个字符串，用于标识指令类型，比如"go_to"，列表的其余元素包含参数，比如go_to的目的地。make_execution_function中的分发使用

function type(instruction) { return head(instruction); }

当求值作为make_machine的第三个参数的list表达式时，带有标签的列表被构造。list的每个参数都是一个字符串（求值为其自身）或者是一个带有指令标签列表构造函数的调用。例如，assign("b", reg("t"))调用构造函数assign，参数为"b"和调用构造函数reg的结果，参数为"t"。构造函数及其参数确定了寄存器机器语言中各个指令的语法。指令构造函数和选择器如下所示，以及使用选择器的执行函数生成器。

指令`assign`

make_assign_ef函数为assign指令生成执行函数：

function make_assign_ef(inst, machine, labels, operations, pc) {
    const target = get_register(machine, assign_reg_name(inst));
    const value_exp = assign_value_exp(inst);
    const value_fun =
        is_operation_exp(value_exp)
        ? make_operation_exp_ef(value_exp, machine, labels, operations)
        : make_primitive_exp_ef(value_exp, machine, labels);
    return () => {
               set_contents(target, value_fun());
               advance_pc(pc);
           };
}

assign函数构造assign指令。选择器assign_reg_ name和assign_value_exp从assign指令中提取寄存器名称和值表达式。

function assign(register_name, source) {
    return list("assign", register_name, source);
}
function assign_reg_name(assign_instruction) {
    return head(tail(assign_instruction));
}
function assign_value_exp(assign_instruction) {
    return head(tail(tail(assign_instruction)));
}

make_assign_ef函数使用get_register查找寄存器名称以生成目标寄存器对象。如果值是操作的结果，则将值表达式传递给make_ operation_exp_ef，否则将其传递给make_primitive_exp_ef。这些函数（如下所示）分析值表达式并为该值生成执行函数。这是一个没有参数的函数，称为value_fun，在模拟期间将被求值以产生要分配给寄存器的实际值。请注意，查找寄存器名称和分析值表达式的工作只在汇编时执行一次，而不是每次模拟指令时执行。这种工作的节省是我们使用执行函数的原因，并直接对应于我们在第 4.1.7 节的求值器中将程序分析与执行分开获得的工作节省。

make_assign_ef返回的结果是assign指令的执行函数。当这个函数被调用（由机器模型的execute函数调用），它将目标寄存器的内容设置为执行value_fun得到的结果。然后通过运行函数将pc前进到下一条指令

function advance_pc(pc) {
    set_contents(pc, tail(get_contents(pc)));
}

advance_pc函数是除branch和go_to之外的所有指令的正常终止。

指令`test`，`branch`和`go_to`

make_test_ef函数以类似的方式处理test指令。它提取指定要测试的条件的表达式，并为其生成执行函数。在模拟时，调用条件的函数，将结果赋给flag寄存器，并将pc前进：

function make_test_ef(inst, machine, labels, operations, flag, pc) {
    const condition = test_condition(inst);
    if (is_operation_exp(condition)) {
        const condition_fun = make_operation_exp_ef(
                                  condition, machine,
                                  labels, operations);
        return () => {
                   set_contents(flag, condition_fun());
                   advance_pc(pc);
               };
    } else {
        error(inst, "bad test instruction – assemble");
    }
}

test函数构造test指令。选择器test_condition从测试中提取条件。

function test(condition) { return list("test", condition); }
function test_condition(test_instruction) {
    return head(tail(test_instruction));
}

branch指令的执行函数检查flag寄存器的内容，然后将pc的内容设置为分支目的地（如果分支被执行），或者只是推进pc（如果分支未被执行）。请注意，branch指令中指定的目的地必须是一个标签，make_branch_ef函数强制执行此条件。还要注意，标签是在汇编时查找的，而不是每次模拟branch指令时查找。

function make_branch_ef(inst, machine, labels, flag, pc) {
    const dest = branch_dest(inst);
    if (is_label_exp(dest)) {
        const insts = lookup_label(labels, label_exp_label(dest));
        return () => {
                   if (get_contents(flag)) {
                       set_contents(pc, insts);
                   } else {
                       advance_pc(pc);
                   }
               };
    } else {
        error(inst, "bad branch instruction – assemble");
    }
}

branch函数构造branch指令。选择器branch_dest从分支中提取目的地。

function branch(label) { return list("branch", label); }
function branch_dest(branch_instruction) {
    return head(tail(branch_instruction));
}

go_to指令类似于分支，不同之处在于目的地可以指定为标签或寄存器，并且没有条件需要检查——pc总是设置为新的目的地。

function make_go_to_ef(inst, machine, labels, pc) {
    const dest = go_to_dest(inst);
    if (is_label_exp(dest)) {
        const insts = lookup_label(labels, label_exp_label(dest));
        return () => set_contents(pc, insts);
    } else if (is_register_exp(dest)) {
        const reg = get_register(machine, register_exp_reg(dest));
        return () => set_contents(pc, get_contents(reg));
    } else {
        error(inst, "bad go_to instruction – assemble");
    }
}

go_to函数构造go_to指令。选择器go_to_dest从go_to指令中提取目的地。

function go_to(label) { return list("go_to", label); }
function go_to_dest(go_to_instruction) {
    return head(tail(go_to_instruction));
}

其他指令

堆栈指令save和restore只是使用指定寄存器的堆栈并推进pc：

function make_save_ef(inst, machine, stack, pc) {
    const reg = get_register(machine, stack_inst_reg_name(inst));
    return () => {
               push(stack, get_contents(reg));
               advance_pc(pc);
           };
}
function make_restore_ef(inst, machine, stack, pc) {
    const reg = get_register(machine, stack_inst_reg_name(inst));
    return () => {
               set_contents(reg, pop(stack));
               advance_pc(pc);
           };
}

save和restore函数构造save和restore指令。选择器stack_inst_reg_name从这些指令中提取寄存器名称。

function save(reg) { return list("save", reg); }
function restore(reg) { return list("restore", reg); }
function stack_inst_reg_name(stack_instruction) {
    return head(tail(stack_instruction));
}

由make_perform_ef处理的最终指令类型生成要执行的动作的执行函数。在模拟时，执行动作函数并推进pc。

function make_perform_ef(inst, machine, labels, operations, pc) {
    const action = perform_action(inst);
    if (is_operation_exp(action)) {
        const action_fun = make_operation_exp_ef(action, machine,
                                                 labels, operations);
        return () => {
                   action_fun();
                   advance_pc(pc);
               };
    } else {
        error(inst, "bad perform instruction – assemble");
    }
}

perform函数构造perform指令。选择器perform_action从perform指令中提取动作。

function perform(action) { return list("perform", action); }
function perform_action(perform_instruction) {
    return head(tail(perform_instruction));
}

子表达式的执行函数

可能需要对reg、label或constant表达式的值进行赋值给寄存器（如上面的make_assign_ef）或输入到操作中（如下面的make_operation_exp_ef）。以下函数生成执行函数，以在模拟期间为这些表达式生成值：

function make_primitive_exp_ef(exp, machine, labels) {
    if (is_constant_exp(exp)) {
        const c = constant_exp_value(exp);
        return () => c;
    } else if (is_label_exp(exp)) {
        const insts = lookup_label(labels, label_exp_label(exp));
        return () => insts;
    } else if (is_register_exp(exp)) {
        const r = get_register(machine, register_exp_reg(exp));
        return () => get_contents(r);
    } else {
        error(exp, "unknown expression type – assemble");
    }
}

reg、label和constant表达式的语法由以下构造函数确定，以及相应的谓词和选择器。

function reg(name) { return list("reg", name); }
function is_register_exp(exp) { return is_tagged_list(exp, "reg"); }
function register_exp_reg(exp) { return head(tail(exp)); }
function constant(value) { return list("constant", value); }
function is_constant_exp(exp) {
    return is_tagged_list(exp, "constant");
}
function constant_exp_value(exp) { return head(tail(exp)); }
function label(name) { return list("label", name); }
function is_label_exp(exp) { return is_tagged_list(exp, "label"); }
function label_exp_label(exp) { return head(tail(exp)); }

assign、perform和test指令可能包括对机器操作（由op表达式指定）对一些操作数（由reg和constant表达式指定）的应用。以下函数为“操作表达式”（包含指令中的操作和操作数表达式的列表）生成执行函数：

function make_operation_exp_ef(exp, machine, labels, operations) {
    const op = lookup_prim(operation_exp_op(exp), operations);
    const afuns = map(e => make_primitive_exp_ef(e, machine, labels),
                      operation_exp_operands(exp));
    return () => apply_in_underlying_javascript(
                     op, map(f => f(), afuns));
}

操作表达式的语法由

function op(name) { return list("op", name); }
function is_operation_exp(exp) {
    return is_pair(exp) && is_tagged_list(head(exp), "op");
}
function operation_exp_op(op_exp) { return head(tail(head(op_exp))); }
function operation_exp_operands(op_exp) { return tail(op_exp); }

注意，操作表达式的处理非常类似于求值器中analyze_application函数对函数应用的处理，我们为每个操作数生成一个执行函数。在模拟时，我们调用操作数函数并将模拟操作的 JavaScript 函数应用于生成的值。我们使用apply_in_underlying_javascript函数，就像在 4.1.4 节中的apply_primitive_function中所做的那样。这是为了将op应用于第一个map生成的参数列表afuns的所有元素，就好像它们是op的单独参数一样。如果没有这样做，op将被限制为一元函数。

通过在机器的操作表中查找操作名称来找到模拟函数：

function lookup_prim(symbol, operations) {
    const val = assoc(symbol, operations);
    return is_undefined(val)
           ? error(symbol, "unknown operation – assemble")
           : head(tail(val));
}

练习 5.9

上面对机器操作的处理允许它们对标签以及寄存器的内容和常量进行操作。修改表达式处理函数以强制执行操作只能与寄存器和常量一起使用的条件。

练习 5.10

当我们在 5.1.4 节中介绍save和restore时，我们没有指定如果尝试恢复不是最后一个保存的寄存器会发生什么，例如在以下序列中

save(y);
save(x);
restore(y);

对于restore的含义有几种合理的可能性：

a. restore(y)将最后一个保存在堆栈上的值放入y中，无论该值来自哪个寄存器。这是我们模拟器的行为方式。展示如何利用这种行为来消除 5.1.4 节（图 5.12）中 Fibonacci 机器的一条指令。
b. restore(y)将最后一个保存在堆栈上的值放入y中，但前提是该值是从y保存的；否则，它会发出错误信号。修改模拟器以使其行为如此。您将不得不更改save以将寄存器名称与值一起放入堆栈。
c. restore(y)将最后一个保存在y中的值放入y中，而不管在y之后保存的其他寄存器是什么。修改模拟器以使其行为如此。您将不得不为每个寄存器关联一个单独的堆栈。您应该使initialize_stack操作初始化所有寄存器堆栈。

练习 5.11

模拟器可用于帮助确定实现具有给定控制器的机器所需的数据路径。扩展汇编程序以在机器模型中存储以下信息：

所有指令的列表，去除重复项，按指令类型（assign，go_to等）排序；
一个（无重复）的寄存器列表，用于保存入口点（这些是由go_to指令引用的寄存器）；
一个（无重复）的寄存器列表，这些寄存器被“保存”或“恢复”；
对于每个寄存器，列出（无重复）分配给它的源（例如，图 5.11 中的阶乘机器中val寄存器的源是constant(1)和list(op("*"), reg("n"), reg("val"))）。

扩展与机器的消息传递接口，以提供对这些新信息的访问。为了测试您的分析器，定义来自图 5.12 的 Fibonacci 机器，并检查您构建的列表。

练习 5.12

修改模拟器，使其使用控制器序列来确定机器具有哪些寄存器，而不是要求在make_machine的参数中预分配寄存器的列表。不要在make_machine中预分配寄存器，而是在汇编指令装配时首次看到它们时逐个分配它们。

5.2.4 监控机器性能

模拟不仅用于验证提议的机器设计的正确性，还用于测量机器的性能。例如，我们可以在模拟程序中安装一个“计量器”，用于测量计算中使用的堆栈操作次数。为此，我们修改我们的模拟堆栈以跟踪寄存器保存在堆栈上的次数和堆栈达到的最大深度，并在堆栈的接口中添加一个打印统计信息的消息，如下所示。我们还在基本机器模型中添加一个操作来打印堆栈统计信息，通过在make_new_machine中初始化the_ops来实现

list(list("initialize_stack",
          () => stack("initialize")),
     list("print_stack_statistics",
          () => stack("print_statistics")));

这是make_stack的新版本：

function make_stack() {
    let stack = null;
    let number_pushes = 0;
    let max_depth = 0;
    let current_depth = 0;
    function push(x) {
        stack = pair(x, stack);
        number_pushes = number_pushes + 1;
        current_depth = current_depth + 1;
        max_depth = math_max(current_depth, max_depth);
        return "done";
    }
    function pop() {
        if (is_null(stack)) {
            error("empty stack – pop");
        } else {
            const top = head(stack);
            stack = tail(stack);
            current_depth = current_depth - 1;
            return top;
        }
    }
    function initialize() {
        stack = null;
        number_pushes = 0;
        max_depth = 0;
        current_depth = 0;
        return "done";
    }
    function print_statistics() {
        display("total pushes = " + stringify(number_pushes));
        display("maximum depth = " + stringify(max_depth));
    }
    function dispatch(message) {
        return message === "push"
               ? push
               : message === "pop"
               ? pop()
               : message === "initialize"
               ? initialize()
               : message === "print_statistics"
               ? print_statistics()
               : error(message, "unknown request – stack");
    }
    return dispatch;
}

练习 5.14 到 5.18 描述了可以添加到寄存器机模拟器的其他有用的监控和调试功能。

练习 5.13

测量计算n！所需的推送次数和最大堆栈深度，对于各个小值的n，使用图 5.11 中显示的阶乘机器。从您的数据中确定关于n的总推送操作次数和计算n！所需的最大堆栈深度的公式。请注意，这两者都是n的线性函数，因此由两个常数确定。为了打印统计信息，您将需要增加阶乘机器的指令来初始化堆栈并打印统计信息。您可能还希望修改机器，使其重复读取n的值，计算阶乘，并打印结果（就像我们在图 5.4 中对 GCD 机器所做的那样），这样您就不必反复调用get_register_contents，set_register_contents和start。

练习 5.14

将指令计数添加到寄存器机器模拟中。也就是说，让机器模型跟踪执行的指令数量。扩展机器模型的接口，接受一个新的消息，打印指令计数的值并将计数重置为零。

练习 5.15

增强模拟器以提供指令跟踪。也就是说，在执行每条指令之前，模拟器应该打印该指令。使机器模型接受trace_on和trace_off消息以打开和关闭跟踪。

练习 5.16

扩展练习 5.15 的指令跟踪，以便在打印指令之前，模拟器打印出控制器序列中紧接着该指令的任何标签。要小心以不干扰指令计数（练习 5.14）的方式进行此操作。您将需要使模拟器保留必要的标签信息。

练习 5.17

修改 5.2.1 节的make_register函数，以便可以跟踪寄存器。寄存器应该接受打开和关闭跟踪的消息。当寄存器被跟踪时，将值分配给寄存器应该打印寄存器的名称，寄存器的旧内容以及正在分配的新内容。扩展机器模型的接口，允许您为指定的机器寄存器打开和关闭跟踪。

练习 5.18

Alyssa P. Hacker 希望模拟器中有一个断点功能，以帮助她调试她的机器设计。您已被聘请为她安装此功能。她希望能够指定控制器序列中的一个位置，模拟器将在那里停止，并允许她检查机器的状态。您要实现一个函数

set_breakpoint(machine, label, n)

在给定标签后的第n条指令之前设置一个断点。例如，

set_breakpoint(gcd_machine, "test_b", 4)

在gcd_machine中的寄存器a分配之前设置断点。当模拟器到达断点时，它应该打印标签和断点的偏移量，并停止执行指令。然后 Alyssa 可以使用get_register_contents和set_register_contents来操纵模拟机的状态。然后她应该能够通过说

proceed_machine(machine)

她还应该能够通过以下方式删除特定的断点

cancel_breakpoint(machine, label, n)

或通过以下方式删除所有断点

cancel_all_breakpoints(machine)

5.3 存储分配和垃圾收集

在第 5.4 节中，我们将展示如何将 JavaScript 求值器实现为寄存器机器。为了简化讨论，我们将假设我们的寄存器机器可以配备列表结构内存，其中用于操作列表结构数据的基本操作是原始的。假设这样的内存存在是一个有用的抽象，当一个解释器专注于控制机制时，但这并不反映当代计算机的实际原始数据操作的真实视图。为了更全面地了解系统如何有效支持列表结构内存，我们必须调查如何表示列表结构，以使其与传统计算机内存兼容。

在实现列表结构时有两个考虑因素。第一个纯粹是一个表示问题：如何仅使用典型计算机内存的存储和寻址能力来表示对，使用“盒子和指针”结构。第二个问题涉及内存管理随着计算的进行。JavaScript 系统的操作至关重要的依赖于不断创建新的数据对象的能力。这些包括由 JavaScript 函数明确创建的对象，以及由解释器本身创建的结构，例如环境和参数列表。尽管在具有无限量快速可寻址内存的计算机上不断创建新的数据对象不会造成问题，但计算机内存只有有限的大小（更可惜）。因此，JavaScript 提供了自动存储分配设施，以支持无限内存的幻觉。当不再需要数据对象时，分配给它的内存会自动回收并用于构造新的数据对象。提供这种自动存储分配的各种技术。我们将在本节中讨论的方法称为垃圾收集。

5.3.1 记忆作为向量

传统计算机内存可以被认为是一个包含信息的小隔间数组。每个小隔间都有一个唯一的名称，称为其地址或位置。典型的内存系统提供两种原始操作：一种是获取存储在指定位置的数据，另一种是将新数据分配给指定位置。内存地址可以递增以支持对一些小隔间的顺序访问。更一般地，许多重要的数据操作要求将内存地址视为数据，可以存储在内存位置中，并在机器寄存器中进行操作。列表结构的表示是这种地址算术的一个应用。

为了模拟计算机内存，我们使用一种称为向量的新数据结构。抽象地说，向量是一个复合数据对象，其各个元素可以通过整数索引来访问，而访问的时间与索引无关。为了描述内存操作，我们使用两个用于操作向量的函数。

vector_ref(vector, n)返回向量的第n个元素。
vector_set(vector, n, value)将向量的第n个元素设置为指定的值。

例如，如果v是一个向量，那么vector_ref(v, 5)会得到向量v中的第五个条目，vector_set(v, 5, 7)会将向量v的第五个条目的值更改为 7。对于计算机内存，这种访问可以通过地址算术来实现，将指定向量在内存中的基地址与指定向量特定元素的索引相结合。

表示数据

我们可以使用向量来实现列表结构内存所需的基本对结构。让我们想象计算机内存被分成两个向量：the_heads和the_tails。我们将表示列表结构如下：对于一对的指针是两个向量中的索引。一对的head是指定索引的the_heads中的条目，一对的tail是指定索引的the_tails中的条目。我们还需要一种表示除对之外的对象（如数字和字符串）的方法，以及一种区分一种数据类型与另一种的方法。有许多方法可以实现这一点，但它们都可以归结为使用类型化指针，即将“指针”的概念扩展到包括有关数据类型的信息。数据类型使系统能够区分指向一对的指针（它由“对”数据类型和内存向量中的索引组成）和指向其他类型数据的指针（它由其他数据类型和用于表示该类型数据的任何内容组成）。如果它们的指针相同，两个数据对象被认为是相同的（===）。图 5.14 说明了使用这种方法表示list(list(1, 2), 3, 4)，其盒式图也显示在图中。我们使用字母前缀来表示数据类型信息。因此，指向索引 5 的对的指针表示为p5，空列表由指针e0表示，指向数字 4 的指针表示为n4。在盒式图中，我们在每对的左下方指示了指定head和tail存储位置的向量索引。the_heads和the_tails中的空白位置可能包含其他列表结构的部分（这里不感兴趣）。

图 5.14 列表list(list(1, 2), 3, 4)的盒式图和内存向量表示。

例如，指向数字的指针，比如n4，可能由一个指示数字数据的类型和数字 4 的实际表示组成。为了处理无法在单个指针分配的固定空间中表示的太大的数字，我们可以使用一个不同的bignum数据类型，其中指针指定一个列表，其中存储了数字的各个部分。

一个字符串可以被表示为一个类型化的指针，该指针指定了形成字符串打印表示的字符序列。当解析器遇到字符串文字时，它构造这样一个序列，字符串连接运算符+和诸如stringify之类的字符串生成原始函数也构造这样一个序列。由于我们希望两个字符串实例被===识别为“相同”的字符串，并且我们希望===是指针相等的简单测试，我们必须确保如果系统两次看到相同的字符串，它将使用相同的指针（指向相同的字符序列）来表示这两个实例。为了实现这一点，系统维护一个称为字符串池的表，其中包含它曾经遇到的所有字符串。当系统即将构造一个字符串时，它会检查字符串池，看看它以前是否见过相同的字符串。如果没有，它会构造一个新的字符串（指向新的字符序列的类型化指针）并将这个指针输入字符串池。如果系统以前见过这个字符串，它会返回字符串池中存储的字符串指针。这个用唯一指针替换字符串的过程称为字符串国际化。

实现原始列表操作

根据上述表示方案，我们可以用一个或多个原始向量操作替换寄存器机器的每个“原始”列表操作。我们将使用两个寄存器the_heads和the_tails来标识内存向量，并假设vector_ref和vector_set可用作原始操作。我们还假设指针的数值操作（例如递增指针，使用对指针索引向量，或者将两个数字相加）仅使用类型指针的索引部分。

例如，我们可以使一个寄存器机器支持以下指令

assign(reg[1], list(op("head"), reg(reg[2])))
assign(reg[1], list(op("tail"), reg(reg[2])))

如果我们分别实现这些，作为

assign(reg[1], list(op("vector_ref"), reg("the_heads"), reg(reg[2])))
assign(reg[1], list(op("vector_ref"), reg("the_tails"), reg(reg[2])))

指令

perform(list(op("set_head"), reg(reg[1]), reg(reg[2])))
perform(list(op("set_tail"), reg(reg[1]), reg(reg[2])))

被实现为

perform(list(op("vector_set"), reg("the_heads"), reg(reg[1]), reg(reg[2])))
perform(list(op("vector_set"), reg("the_tails"), reg(reg[1]), reg(reg[2])))

pair操作通过分配一个未使用的索引并将pair的参数存储在该索引向量位置的the_heads和the_tails中来执行。我们假设有一个特殊的寄存器free，它始终保存一个包含下一个可用索引的对指针，并且我们可以递增该指针的索引部分以找到下一个空闲位置。¹² 例如，指令

assign(reg[1], list(op("pair"), reg(reg[2]), reg(reg[3])))

被实现为以下向量操作的序列：¹³

perform(list(op("vector_set"),
             reg("the_heads"), reg("free"), reg(reg[2]))),
perform(list(op("vector_set"),
             reg("the_tails"), reg("free"), reg(reg[3]))),
assign(reg[1], reg("free")),
assign("free", list(op("+"), reg("free"), constant(1)))

NUS CS1101S：SICP JavaScript 描述：五、使用寄存器机进行计算（3）https://developer.aliyun.com/article/1427744

NUS CS1101S：SICP JavaScript 描述：五、使用寄存器机进行计算（2）

练习 5.7

5.2.1 机器模型

寄存器

栈

基本机器

5.2.2 汇编器

练习 5.8

5.2.3 指令及其执行函数

指令`assign`

指令`test`，`branch`和`go_to`

其他指令

子表达式的执行函数

练习 5.9

练习 5.10

练习 5.11

练习 5.12

5.2.4 监控机器性能

练习 5.13

练习 5.14

练习 5.15

练习 5.16

练习 5.17

练习 5.18

5.3 存储分配和垃圾收集

5.3.1 记忆作为向量

表示数据

实现原始列表操作

热门文章

最新文章

相关课程

相关电子书

相关实验场景

NUS CS1101S：SICP JavaScript 描述：五、使用寄存器机进行计算（2）

练习 5.7

5.2.1 机器模型

寄存器

栈

基本机器

5.2.2 汇编器

练习 5.8

5.2.3 指令及其执行函数

指令assign

指令test，branch和go_to

其他指令

子表达式的执行函数

练习 5.9

练习 5.10

练习 5.11

练习 5.12

5.2.4 监控机器性能

练习 5.13

练习 5.14

练习 5.15

练习 5.16

练习 5.17

练习 5.18

5.3 存储分配和垃圾收集

5.3.1 记忆作为向量

表示数据

实现原始列表操作

热门文章

最新文章

相关课程

相关电子书

相关实验场景

指令`assign`

指令`test`，`branch`和`go_to`