在Clojure中模拟机器

我的联合创始人乔和我最近完成了SiCp。这是一次令人费解的经历：您只需从3个概念开始，然后递归地构建代数方程解算器、电路仿真器、4个解释器和一个编译器。

在某种程度上，你会体验到一种发自内心的感觉：如果你被丢在森林里，…。您可以创建自己的计算机。对这种感觉贡献最大的项目是创造一个机器模拟器。

我们偏离了本书，用Clojure而不是Scheme编写模拟器。我们可以在Clojure中使用不可变的数据结构和更高级别的概念来压缩解决方案，以至于我认为您可以在几天的时间内构建自己的解决方案。

本文将指导您完成这项工作：让我们构建一个机器模拟器，历经几天的黑客攻击！我希望这能激励您尝试Clojure，并更深入地了解SiCp。

在我们模拟普通机器之前，让我们先考虑一下混凝土机器。我们怎样才能创造出一台能计算阶乘的机器呢？

(Defn阶乘[n](循环[res 1计数器1](if(>；Counter n)res(Recur(*Counter res)(Inc Counter)。

嗯，我们需要一种方法来跟踪计数器、res和n。要做到这一点，我们需要一个存储信息的设备。

我们可以说，如果灯泡亮着，那就代表数字1，如果灯泡熄灭了，那就代表数字0。

如果我们在设备中有一串灯泡，我们可以将这些灯泡的状态解释为越来越大的二进制数。例如，我刚才向您展示的设备中的灯泡将代表“10101”，这是“21”的二进制表示。

现在，想象一下，任何时候都有一串其他导线连接到这个设备。这些电线为灯泡带来了“新的”电荷，但有一点不同：传入的电荷目前还不会影响灯泡内部。

注意“a”灯泡的来电是如何“关闭”的，但里面的灯泡仍然亮着。相反，传入费用是亮的，但灯泡是关的。如果设备可以做到这一点，这意味着无论设备内部的灯泡的费用是什么，都是一个存储值。非常酷！

现在，我们需要这些传入的电线在某个时刻做一些事情。如果这台设备有一个“保存”按钮会怎么样。

一旦我们按下“保存”，输入的电流就会转移到盒子里：

这里，灯泡“a”从“开”变为“关”，灯泡"；b"；从"；开"；变为"；关。

我们还需要一种方式将内部内容的状态共享给其他设备。要做到这一点，我们所需要做的就是让一束电线离开我们的设备，这些电线带有与灯泡相同的电荷：

现在，如果我们把这些传出的电荷连接到其他设备上，那个设备就会收到存储在这个设备上的“号码”。

我们刚才描述的内容类似于计算机的寄存器(1)。寄存器使我们能够存储和共享信息。

现在，我们可以使用三个寄存器来存储res count和n的值。

接下来，我们需要一个可以“添加”两个寄存器的设备。想象一下这样一个设备，它有两个寄存器的传入线路和一个寄存器的传出线路：

如果设备能够以这样的方式连接那些传入的线路，即传出的线路代表这些寄存器的“相加”，我们就有了一个“加法器”设备！

在上面的示例中，左边的寄存器表示“10101”(21)，右边的寄存器表示“00001”(1)。输出线充电为“10110”…。代表22个人！

类似地，我们可以有一个器件，它有两条寄存器值的输入线和一条寄存器值的输出线：

如果我们能以这样一种方式连接输入导线，使输出导线代表乘法的结果，那么我们就会有一个乘法装置！

上面左边的寄存器表示“00101”(5)，右边的寄存器表示“00010”(2)，出线的电荷是“01010”(10)。好的!。这就给了我们一个乘法器。

我们还需要一个装置。假设一个设备需要两条相当于寄存器的输入线，但只有一条输出线：

如果我们可以这样组合输入线，即当左侧寄存器较大时，输出线为“ON”，否则为OFF，我们可以将其用作比较器机器！

如果我们有所有这些机器，我们可以用这样的方式连接它们，这样我们就可以计算阶乘：

在这里，我们将res和Counter的输出线连接到*机器。我们将*机器的输出线连接起来，作为RES的输入线。

这样，如果我们按“A”，我们将“存储”计数器与res相乘的结果！

类似地，我们将COUNTER和一个保持值1的寄存器的输出线连接到+机器。

如果我们按“B”，计数器将与加1的结果一起存储！

接下来，我们将COUNTER和n连接起来。例如，如果我们将一个灯泡连接到>；机器的输出线上，那么每当它打开时，我们就会知道COUNTER大于n。

(循环[资源1计数器1](IF(>；计数器n)资源(RECUR(*计数器资源)(INC计数器)。

想象一下，如果我们有“数据路径”机器。如果我们遵循下面的食谱会发生什么：

"；按A"；。这将使用*计算机在RES和计数器上的结果更新RES。

“按B键”。这将使用1上的+机器和计数器的结果更新计数器。

如果我们反复这样做，一旦连接到>；机器输出的灯泡打开，RES将包含阶乘的结果！

很酷，但是这种体力劳动会很烦人。不过，如果你看了这些说明，就会有一个相当重要的见解：所有这些说明都很简单：看一下给灯泡充电，按下按钮..."；。

事实上，它们是如此简单，以至于我们可以连接一台机器来通过那个食谱！想象一下，如果我们创建了一台机器，它可以根据>；机器的输出线是否打开来为我们“按”按钮：

现在，在这个阶段，您可能在想：究竟如何产生表示乘法的输出线？+是怎么工作的，控制器又是怎么走的呢？

如果你仔细想想，这些都可以简化为非常简单的机器。它们甚至不一定是电子的：

想象一下，你有一个球从山上滚下来。您可以通过将RES和计数器放在天平上来构建类似于>；机器的东西：根据哪个更大，球将走不同的路径。

有了足够的精力、空间、时间和独创性，你真的可以在山上用一个球建造这一切。现在，你不一定会这么做(2)，但是你可以想象组成我们机器的电子部件是如何类似的简单的逻辑机器：如果关闭就打开，如果打开就关闭，等等。这些逻辑机器被称为“逻辑门”。你可以查一下，但希望我很快就能给你写一篇关于这些机器的文章🙂。

现在，我们拿出我们的机器，看看如何用简单的设备来建造它们。我们怎么能模拟这些机器呢？

为了模拟这些机器，我们需要将我们的图片描述转换成计算机可以操作的东西。计算机可以更好地处理文本：让我们创建一种语言来描述这些机器。

(def阶乘指令'；(START(TEST(OP&>；)(REG COUNTER)(Reg N))(BRANCH(LABEL DONE))(分配RES(OP*)(REG COUNTER)(REG RES))(ASSIGN COUNTER(OP+)(REG COUNTER)(Const 1))(GOTO(LABEL START))DONE))。

我们的分支指令检查测试指令是否说是。如果是，它将移动到Done。否则它就不工作了，机器就向前移动一步。

之后，我们的(ASSIGN RES)表达式类似于“按A”。(分配计数器类似于“按下B”，而(GOTO(标签开始)类似于将我们带回到起点的箭头。

有了这个文本表示，我们可以构建一个解释器并模拟我们的机器。我们开始吧！

我们的机器在Clojure中的状态是什么？那么，我们如何用Clojure来表示大多数东西呢？用地图！让我们将机器的状态表示为地图：

注册表映射可以保持寄存器到值的映射。Label→idx可以在指令列表中保持标签到其idx的映射。

这样，我们就可以使用我们语言中最基本的部分：我们使用(const…。(REG..。AND(标签…。到处都是。

如果我们的机器看到(Reg Foo)，它应该查找foo寄存器中的任何内容，并返回。

如果我们的机器看到(标签为foo)，它应该在我们的指令表中返回正确的索引。

(Def Tag First)；(tag'；(Const 1))=>；const(Defn tag-of？[sym s](=sym(Tag S)；(tag-of？'；const'；(Const 1))=>；true(定义解析原语[{：项[注册表映射标签->；idx]：AS机器状态}prim-exp](condp tag-of？Prim-exp&39；const(Second prim-exp)'；reg(获取注册表映射(Second prim-exp))'；Label(Label-&>；IDX(Second prim-exp)。

我们的解析原语函数获取机器状态，并根据表达式的标记执行正确的操作。

(解析基元出机器状态-V0'；(Const 1))；=>；1(解析基元出机器状态-V0'；(Reg N))；=>；10(解析基元出机器状态-V0'；(标签完成))；=>；5。

好的，我们有基本体在工作，让我们更上一层楼。我们的模拟器允许我们访问其他一些机器，如*+和>；

'；(...(OP>；)(REG计数器)(REG N))'；(...(OP*)(REG COUNTER)(REG RES))'；(...(OP+)(REG COUNTER)(Const 1))。

当我们的模拟器看到这些指令时，它需要查找与OP相对应的机器，并使用提供的原始参数运行它。

(def ex-Machine-state-v1{：注册表映射{'；n 10'；分辨率1'；计数器1}：标签->；idx{'；开始0'；完成5}：操作映射{'；**'；++'；>；>；}})。

(def operation-sym(Comp Second First))；((op>；)...)=>；>；(def operation-args rest)；((op>；)(Reg Count)(Reg N))=>；((注册表计数器)(Reg N))(defn parse-operation[{：keys[op-map]：as data}op-exp](let[op-fn(get op-map(operation-sym op-exp)valed-args(map(部分解析原始数据)(operation-args op-exp))](Apply op-fn valed-args))。

(parse-operation ex-Machine-state-v1'；((op>；)(Reg Count)(Reg N))；=>；false(parse-operation ex-Machine-state-v1'；((op*)(Reg Count)(Reg Res)；=>；1(parse-operation ex-Machine-state-v1'；((op+)(Reg Count)(Const 1)；=>；2。

现在是时候更上一层楼，开始实现我们的实际指令表达式了。

让我们从赋值开始。分配有两种形式。我们可以指定一个原始值：

一旦赋值完成，我们的机器状态需要“前进”到下一条指令。

(def ex-Machine-state-v2{：注册表映射{'；n 10'；分辨率1'；计数器1}：Label->；idx{'；start 0'；Done 5}：op-map{'；**'；++'；>；>；}：idx 0})。

我们现在有一个IDX状态，它跟踪指令列表中机器的当前索引。这将允许我们通过简单地递增索引来“向前移动”。

(def Assign-reg-name Second)；(Assign Foo...)=>；Foo(def Assign-Operator#(nth%2))；(Assign Foo(Const 1)=>；(def operation-exp？(comp(part tag-of？'；op)Assign-Operator))；(Assign Foo(op...=>；true(def assign-operation-exp(Part Drop 2)；(Assign Foo(op*)...)=>；((op*)...)(Defn exec-Assign&34；Assign有两种形式：(Assign reg-name<；primitive-op>；)i.E(Assign Foo(Const 1))(Assign reg-name<；operation<；args...>；)i.E(Assign Foo(op*)(Const 2)(Reg Foo))"；[DATA INS](让[注册表名(ASSIGN-REG-NAME INS)VAL(IF(OPERATION-EXP？INS)(解析操作数据(ASSIGN-OPERATION-EXP INS))(解析原语数据(ASSIGN-OPERATOR INS))](->；DATA(ASSOC-IN[：REGISTRY-MAP REG-NAME]VAL)(UPDATE：IDX INC))。

(SELECT-KEYS(EXEC-ASSIGN EX-MACHINE-STATE-v2'；(ASSIGN COUNTER(CONST 0)[：注册表映射：IDX])；=>；{：注册表映射{n 10，RES 1，Counter 0}，：IDX 1}(SELECT-KEYS(EXEC-ASSIGN EX-MACHINE-STATE-v2'；(ASSIGN COUNTER(CONST 10)[：REGISTRY-MAP：IDX])；=&gT；{：注册表映射{n 10，分辨率1，计数器10}，：idx 1}。

(goto<；primitive-exp>；)应该将我们机器中的idx设置为基元表达式的结果值：

(def GOTO-DEST秒)；(GOTO(标签完成))=>；(标签完成)(DEFN EXEC-GOTO[DATA INS](ASSOC DATA：IDX(Parse-Primitive Data(GOTO-DEST INS)

(SELECT-KEYS(EXEC-GOTO EX-MACHINE-STATE-v2'；(GOTO(标签完成)[：Label->；idx：idx])=>；{：Label->；idx{Start 0，Done 5}，：idx 5}。

我们就快到了！接下来，让我们考虑一下测试和分支指令：

请记住，当测试运行时，我们需要确定OP是否返回是或否，然后我们将机器向前移动。当分支运行时，我们需要检查最后一条测试指令是否说是。如果是，我们就跳到分支目的地。否则，我们不执行操作，并将指令表向前移动一位。

(def ex Machine-state-v3{：Registry-map{'；n 10'；res 1'；Counter 1}：Label->；idx{'；start 0'；Done 5}：op-map{'；**'；++'；>；>；}：idx 0：测试通过？False})。

(def drop-tag rest)；(test(op>；)...)=>；((op>；)...)。(Defn EXEC-TEST[DATA INS](->；DATA(ASSOC：测试通过？(解析操作数据(Drop-Tag INS)(UPDATE：IDX Inc))。

)：考试通过了吗？(exec-test ex-Machine-state-v3'；(test(op>；)(reg计数器)(Reg N)；=>；false(：test-pass？(EXEC-TEST EXM-MACHINE-STATE-v3'；(test(op>；)(Reg N)(Reg Count)；=>；true。

机器测试通过了吗？状态IS设置为操作值。

(def BRANCH-DEST秒)；(BRANCH(标签完成))=>；(标签完成)(DEFN EXEC-BRANCH[DATA INS](LET[DEST(解析基元数据(BRANCH-DEST INS)](IF(：测试通过？数据)(ASSOC数据：IDX DEST)(更新数据：IDX Inc))

(EXEC-BRANCH{：LABEL->；IDX{'；Done 5}：测试通过？FALSE：idx 0}'；(分支(标签完成))；=>；{：标签->；idx{完成5}，：测试通过？FALSE，：IDX 1}(EXEC-BRANCH{：LABEL->；IDX{'；Done 5}：测试通过？True：idx 0}'；(分支(标签完成))；=>；{：标签->；idx{完成5}，：测试通过？TRUE，：IDX 5}。

我们现在已经实现了使阶乘机器工作所需的所有指令。让我们创建一个将它们放在一起的函数：

(定义EXEC-INS[数据INS](让[type->；f{##39；ASSIGN EXEC-ASSIGN'；TEST EXEC-ASSIGN'；BRANCH EXEC-BRANCH'；GOTO EXEC-GOTO}f(或(TYPE->；f(TAG INS)(抛出(异常。"；意外指令"；)](f数据输入))。

'；(START(TEST(OP&>；)(REG COUNTER)(Reg N))(BRANCH(LABEL DONE))(ASSIGN(LABEL DONE))(赋值RES(OP*)(REG COUNTER)(REG RES))(ASSIGN COUNTER(OP+)(REG COUNTER)(Const 1))(GOTO(Label Start))DONE)。

但是我们需要Label→idx映射。为了使这些索引有意义，我们还需要仅表示可执行指令。让我们写下这些：

(Defn Extract-Instructions[RAW-Instructions](vec(Remove Symbol？RAW-Instructions)(Defn Extract-Label->；idx[RAW-Instructions](Second(Reduce(Fn[[IDX Label->；IDX]Part])(IF(Symbol？Part)[IDX(Assoc Label->；IDX Part IDX)][(Inc IDX)Label->；IDX])[0{}]RAW-Instructions))。

(Extract-Label->；IDX阶乘指令)；=>；{Start 0，Done 5}(Extract-Instructions阶乘指令)；=>；[(test(op>；)(Reg Counter)(Reg N))(分支(Label Done))(Assign RES(OP*)(Reg Counter)(Reg Res))(Assign Counter(OP+)(Reg Counter)(Const 1))(GOTO(LABEL START))]。

好的，exec可以接受一个机器状态和一条指令，然后返回一个全新的机器状态。Extract-Label→idx可以创建我们的标签→idx映射，而Extract-Instructions只能为我们提供可执行表达式。

(Defn运行[注册表映射操作映射原始指令](让[标签-&>；idx(提取-标签-&>；idx原始指令)指令(提取-指令原始指令)初始机器状态{：注册表映射注册表映射：操作映射操作映射：idx 0：测试通过？Nil：标签->；idx标签->；idx}](loop[机器状态初始机器状态](if-let[ins(第n条指令(：idx机器状态)nil)](recur(exec-ins机器状态ins))机器状态))。

我们接收一个注册表、一个操作映射和一些原始指令。之后，我们在循环中运行，根据idx执行指令，并在idx不再返回可执行指令时返回。

(Get-in(运行{'；n5'；计数器1'；分辨率1}{'；**'；>；>；'；++}阶乘说明)[：注册表映射'；分辨率])；=>；120。

哇，那真是一次旅行。希望你玩得开心！🙂。如果您想了解整个过程，请查看GitHub回购。

准备接受挑战？尝试实现其他一些机器：Fibonacci序列、求幂等。尝试编写这些算法的递归版本，要做到这一点，您需要机器状态中的堆栈结构和(save<；reg-name>；)(restore<；reg-name>；)指令。在那之后，见鬼，你可以实现一个LISP求值器！

如果你对这类东西感兴趣，可以在推特或电子邮件上联系一下-我总是很乐意与志同道合的黑客🙂聊天。

感谢Joe Averbukh，David Magaltadze，Ian Sinnot，Raghavan Lakshmana审阅了这篇文章的草稿。

(1)计算机寄存器也有一个启动子，但我决定不把它包括在论文中。我认为没有必要抓住本质。我计划再写一篇更深入的文章：)

(2)你在球上可能达到的最高速度是200公里/小时，而光的传播速度是30万公里/小时(…)。马上就到。你可以想象这种速度会如何改变游戏规则：从让计算器变得不切实际到生产iPhone。