寄存器機器
我們通過求值器解釋了編程語言運算的細節(jié)在扰，但由于之前講解的求值器都是基于 Lisp 語言開發(fā)涉枫，所以自然繼承 Lisp 的控制結(jié)構(gòu)，于是在求值器部分就沒有談到更加底層的控制結(jié)構(gòu)知識硕旗。
計算機中主要將 寄存器（register） 作為存儲單元士修，通過 指令（instruction） 維護其中的存儲內(nèi)容，這樣的計算機也稱為寄存器機器澈灼。這便是編程語言的底層基礎(chǔ)竞川。我們需要通過一門機器語言描述寄存器機器的構(gòu)造，主要是其中的 數(shù)據(jù)通路（data-path） 和 控制器（controller） 結(jié)構(gòu)叁熔，雖然可以使用如下類似電子原件電路圖的方式描述委乌，但我們希望將其轉(zhuǎn)換為文本形式，通過指令序列的方式描述該結(jié)構(gòu)荣回。
指令
(assign <register-name> (reg <register-name>))
(assign <register-name> (const <constant-value>))
(assign <register-name>
(op <operation-name>)
<input1> ... <inputn>)
(perform (op <operation-name>) <input1> ... <inputn>)
(test (op <operation-name>) <input1> ... <inputn>)
(branch (label <label-name>))
(goto (label <label-name>))
-
test為檢測指令遭贸，能夠執(zhí)行指定檢測 -
branch指令，也稱條件分支指令心软，由控制器標(biāo)識指定的路徑壕吹，主要基于檢測指令的檢測結(jié)果進行選擇。（檢測指令和條件指令在控制器圖示中以菱形組件的形式一同出現(xiàn)）删铃。如果檢測結(jié)果為false耳贬，控制器將繼續(xù)運行序列中的下一指令。否則猎唁，控制器應(yīng)該繼續(xù)運行branch標(biāo)識之后的指令咒劲。 -
goto指令，也稱非條件分支指令诫隅，根據(jù)標(biāo)識名稱跳轉(zhuǎn)至需要繼續(xù)執(zhí)行的控制節(jié)點腐魂。 -
assign指令，能夠?qū)碜云渌拇嫫骰虺Ａ康臄?shù)據(jù)存儲至指定寄存器中逐纬。 -
perform指令蛔屹，能夠執(zhí)行 action，action 指某些操作產(chǎn)生的結(jié)果只會呈現(xiàn)于寄存器機器外部风题，例如print操作就是 action判导。
goto 指令除了可以直接跳轉(zhuǎn)至指定標(biāo)識節(jié)點，也可以通過存儲于寄存器中的標(biāo)識節(jié)點跳轉(zhuǎn)沛硅，示例如下眼刃。
(assign <register-name> (label <label-name>))
(goto (reg <register-name>))
除此之外，還有操作堆的指令摇肌，如下擂红。
(save <register-name>)
(restore <register-name>)
通過 save 指令能夠?qū)?shù)據(jù)存入堆中，通過 restore 指令能夠從堆中取出數(shù)據(jù)。在堆中存入一組數(shù)據(jù)后昵骤，通過 restore 會將這組數(shù)據(jù)按與存入順序相反的順序取出树碱，也就是先入后出。
描述寄存器機器的語言
通過寄存器機器語言既能描述數(shù)據(jù)通路成榜，也能描述控制器樱溉，但由于這樣會導(dǎo)致閱讀機器描述時要反復(fù)查閱操作定義和寄存器命名完丽，所以我們選擇將數(shù)據(jù)通路描述融入控制器描述的方式體現(xiàn)寄存器機器描述你稚。忽略數(shù)據(jù)通路的部分主要是因為通過控制器理解寄存器機器的運轉(zhuǎn)對我們更加重要宇弛，示例如下。
(data-path
(registers
((name a)
(buttons ((name a<-b) (source (register b)))))
((name b)
(buttons ((name b<-t) (source (register t)))))
((name t)
(buttons ((name t<-r) (source (operation rem))))))
(operations
((name rem) (inputs (register a) (register b)))
((name =) (inputs (register b) (constant 0)))))
(controller
test-b
(test =)
(branch (label gcd-done))
(t<-r)
(a<-b)
(b<-t)
(goto (label test-b))
gcd-done)
整合數(shù)據(jù)通路描述和控制器描述后如下货徙。
(controller
test-b
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label test-b))
gcd-done)
雖然這樣也存在描述冗長、重復(fù)的問題，但基于我們關(guān)心的重點在后面的內(nèi)容中都將使用這種機器描述。
迭代過程與遞歸過程
通過上述介紹的寄存器機器描述語言我們可以描述實現(xiàn)迭代過程和遞歸過程的寄存器機器漩蟆。迭代過程比較簡單捺癞，下列示例就是一個描述輾除法計算 GCD 值的寄存器機器。
(controller
test-b
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label test-b))
gcd-done)
遞歸過程與迭代過程描述最大的不同在于驼鹅，遞歸過程需要在子問題調(diào)用的計算結(jié)果完成后再進行主問題的下一步計算豺型，所以在計算子問題時主問題的計算需要掛起，在子問題計算完成后恢復(fù)主問題的寄存器（因為子問題的計算過程可能修改寄存器的數(shù)據(jù)）數(shù)據(jù)繼續(xù)主問題的運算买乃。這時便需要堆這個數(shù)據(jù)結(jié)構(gòu)的幫助姻氨，利用堆可以存儲寄存器機器的數(shù)據(jù)，在需要時再從堆恢復(fù)數(shù)據(jù)剪验。下列示例是一個計算階乘的寄存器機器描述肴焊。
(controller
(assign continue (label fact-done))
fact-loop
(test (op =) (reg n) (const 1))
(branch (label base-case))
(save continue)
(save n)
(assign n (op -) (reg n) (const 1))
(assign continue (label after-fact))
(goto (label fact-loop))
after-fact
(restore n)
(restore continue)
(assign val (op *) (reg n) (reg val))
(goto (reg continue))
base-case
(assign val (const 1))
(goto (reg continue))
fact-done)
