結構化指令的底層塑造法

看板Programming作者tommy.時間14年前 (2010/12/12 02:01)推噓1(1推 0噓 2→)

留言3則, 2人參與討論串1/3 (看更多)

內容範圍: 程式編譯器. 內容程度: 高級, 進階. 內容抽象: 看似不同的高階結構, 卻有著相同的底層指令. 內容精度: 觀念模式. 【前言】本篇是我個人研究編譯器設計的一點中途心得. 希望有志與此的同好, 能一起分享. 本文內容不是編譯器的教學手冊, 因此不會描述所有必要的基礎, 只著重在我想表達的重點上. 所以如果看不懂的人, 請參考其它編譯器書籍或等候未來我發表相關文章. 【概要】程式語言中所具有的種種不同的結構化指令, 看似在表面上有所不同, 但是其底層的機械碼卻是相同的. 都可以使用GOTO指令塑造出來. 例如: BASIC: IF/ ELSE/ END IF FOR/ EXIT FOR/ NEXT DO/ EXIT DO/ LOOP SUB/ EXIT SUB/ END SUB ... (A) 語言指令底層GOTO結構功能說明 -------- ------------ -------- IF 計算邏輯式 if not TRUE goto .else_001 邏輯為假, 跳至ELSE段. ... ... 一般運算敘述. 邏輯為真, 繼續執行. ... ... goto .if_001.endif IF段結束跳至出口. ELSE label .else_001 ELSE段進入點註標. ... ... 一般運算敘述. END IF label .if_001.endif IF出口註標. (B) 語言指令底層GOTO結構功能說明 -------- ------------ -------- FOR I=y to z初始化 I=y 變數初始化. label .for_001 入口註標. 判斷邏輯式: I <= z if not TRUE goto .next_001 邏輯為假, 跳至出口註標. ... 一般運算敘述. 邏輯為真, 繼續執行. ... EXIT FOR goto .next_001 運算敘述, 跳至出口運算. ... 一般運算敘述. ... add I = I + step 累加器. 累加變數指定間距. goto .for_001 跳至入口註標. NEXT label .next_001 next出口註標. 【正文】 __緣由__ 在我研究機械碼執行的過程裡, 我很驚訝的發現: 一般常見的結構化敘述竟然可以只使用簡單的goto指令來建置完成. 實際上因為我也只有goto可以用... goto指令在程式語言的演進中被視為「攪亂」程式邏輯的「元凶」. 因為程式設計師在胡亂的goto之後, 根本不知道原來的流程是怎樣跑的, 以致於除錯追蹤變得很困難. 然而如果你只是程式設計界的後輩. 只學會前人慘痛的「結果」. 那你拋棄 goto的後果就會造成你寫不出語言編譯器! 因為你不懂得goto的基本意義. __機械執行__ 在「機械執行」的世界裡, 其實只有「位址轉移」這種基本的功能. 也就是 goto! 一段機械碼連續執行下來, 遇到goto, 就轉移到指定的機械段繼續執行. 如果沒有, 就繼續執行下去... 在機器的眼光中看不見人類所謂的高階結構--也就是像IF/END IF 這種「結構化指令」. __機械執行的單純性__ 很多人習慣高階程式設計之後, 並不瞭解所謂的「機械化」會到什麼程度. 因為高階語言是專為貼近人類思考所開發出來的. 機械化的定義是這樣: 原理解說 1. 執行命令的明確性. 也就是一個指令有一個固定的動作. 2. 執行順序的可預期性. 指令和指令間相互銜接的轉移. 3. 沒有任何執行是「未知的」. 「機械運轉」的基本法則. 也由於這樣的定義, 才使得由「物質」來實現「機械運算」成為可能. 其中, goto指令就是基本的第二法條. 指令間的轉移. 另外, 隱含的指令轉移就是下一個指令位址. 附帶說明. 「機械化執行」中, 不能有任何執行是「未知」的. 任何「無法決定」的運算, 也必須被明確「定義」出來, 叫做「意外」. 而執行「意外」的機械碼就是「直接當機」 (鎖住後續的其它執行, 避免災害擴大.) __機械碼的世界__ 如果你仔細設計一個虛擬機器, 用來執行你自己自定的機械碼, 那它看起來會像這樣: 「左轉, 右轉, 向前走 5 秒, 後退走 3 秒.」這個機器只有4 個指令, 左轉, 右轉、前進、後退. 並且每個指令都有條件參數. 轉向時, 包括角度. 前進後退時, 包括時間. 你把機械碼定義出來以後, 可以控制電腦鼠走迷宮, 或是工廠的無人化自動搬運車等. 由於每個指令都是可以實現的. 所以「機械」執行變得可能. __電腦的機械碼__ 現在大家所知道的電腦, 其實也是運用這種基本的思想造出來的. 只是底層的硬體運作是電流與類比轉換器. 電流能不能流經指定的通路 (開關) , 決定了其結果如何. 如果通路的另一端連上了另一個電磁開關的話. 當電流經過開開關關等數億個電路閥門, 如果有一個通路正好通向外界的燈泡或許你就會看到指令執行「亮」起來. 這個燈泡其實就是一種「類比轉換器」. 將電流轉換成「光」的能源形式. 而不再是「看不見」的東西. 電腦就是這樣由複雜的電流開關加上機械動作的類比轉換器所構成的. 不過, 由於人類為了方便自己瞭解與簡單描述起見, 才會用文字來定義「每個動作」. 這就造成所謂的二進制碼, 與更高階的組合語言碼了. 很多人並不知道, 其實你偶而由二進制碼編輯器看見的一堆亂碼 (或數字). 已經是經過高階化的東西. 它是以16進位的數字碼型式來表示電流各點的開關狀態. 如果你還不能想像的話, 想想盲人用的點字書就會曉得. 點字書上的點, 可以視為「開」的狀態. 無點即「關」. 但是數字碼卻是以號碼來表示功能. __回歸正傳的goto__ 我之所以簡單介紹前面的機械執行與機械碼, 是要告訴你. 我瞭解goto並不是膚淺的. 我是真的明白所謂的「機械控制」是什麼, 才會決定goto其實是機械執行的根本基礎. goto的用不用, 在早期引起了很大的紛爭! 設計師的習慣, 功能的實現, 與系統開發管理上的益處等. 這裡我需要你明白, 在「這」之下, 沒有goto, 你無法完成工作. 在「這」之上. 濫用goto, 只會使你頭痛, 如果頭痛的不是接你工作的那個人的話. __在goto之前__ 我在早期研究編譯器功能時, 首先做的就是「直線」運算. 也就是沒有分支轉移的運算. 最簡單的機械指令設計就是這樣: 指令編號: 1 機械碼: '1' 功能: 暫存器加一. (count) 指令長度: 1 參數: 無. (後面沒有了! 不要懷疑! 只有一個指令!) 虛擬機器像這樣: (在電腦中用軟體程式來模擬機器) '==BASIC 碼== '--機器啟動初始化-- Counter = 0 '暫存器歸零. CodeSize = Len(codeStr$) '取得機械碼的程式長度. pinSize = 1 '預設機械指令只有1 個字元長. if CodeSize > 0 then pi = 1 else pi = 0 '沒有機械碼時不運轉. '--運轉行程-- Do While pi '==機械運算核心== Select case Val(mid$(codeStr$,pi,1)) Case 1 'Count Counter = Counter + 1 '暫存器加1. pinSize = 1 '機械指令長度: 1 Case Else pi = 0: pinSize = 0 '無定義的機械碼, 當機. (脫離機器) end Select '==機械核心結束== pi = pi + pinSize '切換執行到下一個機械碼位址. if pi > CodeSize then pi = 0 '決定是否繼續執行: 超出機械碼範圍. if pi < 1 then pi = 0 '決定是否繼續執行: 不合理的範圍. Loop '--運轉結束-- 程式看起來像這樣: 1 1 1 (連續執行「加一」3 次) 或是 1 1 1 1 1 (連續執行「加一」5 次) 程式影像似這樣: codeStr$="111" 或 codeStr$="11111" 把codeStr$ 餵給前面的虛擬機器「吃」, 你就會得到暫存器是3 或5 的結果. 由於機器沒有輸出指令. 你必須自己在執行後加上「記憶體傾印」的功能. 例如: Print Counter __goto: 功能的分支執行__ 前面的機器是非常簡單的. 只有一個指令! 並且只能「加一」. 但是「千里之行始於足下」. 所有複雜功能都是後來加上的. 你可以想像再添加所有可能指令到機器核心上..像買菜、洗碗、拖地等.... 這裡我要加上功能分支指令goto. 指令編號: 2 機械碼: '2' 功能: 流程轉移. 絕對位移. (goto) 指令長度: 3 參數: 位址. 兩碼. 一個程式看起來像這樣: codeStr$ = "11208111" 指令分解成: "1, 1, 2:08, 1, 1, 1" 有6 個指令. 其中goto在第三個. goto的參數有兩碼. 00到99. 可位移99個位元組. 算是小跳躍. 機器核心加上此段: Case 2 'Goto pi = Val(mid$(codeStr$, pi+1, 2)) '新的執行點. pinSize = 0 '機械指令長度: 歸零. 因為pi已是新值. 程式執行起來像這樣: 影像: 1, 1, 2:08, 1, 1, 1 -> -> | > ->..........| 繼續..跳..........到這裡繼續其中, 後面的兩個 '1' 指令被跳過去了! 在2:08之後. goto 直接執行指令轉移到絕對位址8 上面. 所以 codeStr$ "11208111" 第8 個位址為 '1' 即: "1120811*"星號所在的指令. 最後, 執行的結果傾印暫存器會是3, 因為只加了3 次. 在"**20811*" 有星號的指令1 被執行. 從這裡你就知道分支執行是多簡單的事! 機器只是改變執行指標到新的位址. 其它都不必動. 真實的電腦原理完全一樣! 只是看起來電子電路, 電流控制會複雜很多. __goto: 跳躍的可能形式__ 一般應用上goto會有短跳躍與長跳躍兩種形式. 還有相對跳躍與絕對跳躍等模式. 短跳躍除了指令較短之外, 其內部機械運轉要動到的相關部位也較小. 你可以想像成: 走到廚房..及走到學校去..兩種跳躍形式. 當然「走到廚房」 (短跳躍) 成本比長跳躍 (到學校去) 低得多! 絕對跳躍是基本指令. 相對跳躍可以由絕對跳躍模擬出來. 差別在多一個可變的基底暫存器. 相對跳躍所做的, 除了指令後的參數值--相對位移量之外, 機器還會自動加上現在的狀態: 基底暫存器值. 說明一下, 這個「基底暫存器」是你自己的機器弄出來的. 它可以是另一個變數, 像前面的機器Counter 變數類似. 例如JumpBase等. 絕對跳躍的運算法如下: pi = 參數值. 直接指明絕對位址, 正值. 相對跳躍: pi = 參數值 + 基底暫存器. 相對於基底暫存器的前後位址. 可能正負. 從這裡你也可以知道. 要塑造goto有多簡單! 而且實際由機器實現 (有電流或物質運轉) 也是很基本的事. __goto的goto: 「進化」__ 這個雙關語標題其實就是本篇重點了: 「結構化指令的底層塑造」當你簡單的在機器實現goto功能之後. 你就可能實現所有的「高階」結構化指令. 像IF/END IF, FOR/NEXT 等. 回過頭去看前面的「概要」. 我不需要重複篇幅將內容打兩次. 你應該可以看得懂我在寫什麼. 到目前為止, 我的虛擬機器只差條件判斷式 (if) 而已! 如果你注意到的話. 你可能發現 label 這個定義字要怎麼「執行」. label 不是執行指令! 不會在機器核心運算! 它是寫程式的助憶碼. 其真正的結果應該是它所在的位址: 一個「數值」而已! 並且不會產生機械碼.(自己的機械碼) label 是由編譯器來識別的. 當程式編譯完成後, 你在機械碼中是看不到這些字樣 (功能) 的. 程式通常都是由人來寫. 所以程式原文的語法會很高階. 這也是程式語言為何要發展到接近人類思考與習慣的原因. 由於機械碼的位址很難用人工計算! 所以直接由編譯器來代算會比較簡單! 前面的例子, 我們手寫的機械碼 "11208111".由於是非常簡化的功能, 所以跳躍位址一眼就看得出來. 由: |...>* 指令2:08, 轉移到後面* 的位址. 然而複雜的大程式, 都是由編譯器來記住跳躍註標的位址, 反復計算才計算出來的! 這包括要計算前面指令的大小, 跳躍時考慮短跳躍或長跳躍. 往前跳或往後跳等. __goto如何造出結構化__ 我用IF/END IF當例子. 解釋goto如何能架構出「結構化語法」 ------------------------------------------------------- IF 計算邏輯式 if not TRUE goto .else_001 邏輯為假, 跳至ELSE段. ... ... 運算敘述. 邏輯為真, 繼續執行. ... ... 一般運算敘述. goto .if_001.endif IF段結束跳至出口. ELSE label .else_001 ELSE段進入點註標. ... ... 一般運算敘述. END IF label .if_001.endif IF出口註標. ------------------------------------------------------- 由於我手上的指令只有goto可以用.(在機械運算的底層) 因此我必須想辦法將高階語法用goto塑造出來! 經過基本原理的思考之後我發現: 所謂的「結構化執行」也不過就是「區段」的執行罷了! 用這眼光看其它的語法, Do/Loop, For/Next. 沒有不是區段執行的. 連副程式或副程序都是! 在早期高階語法的設計要點中, 很明確的任務是要解決執行流程不易追蹤的問題. 而流程追蹤不是在機器執行階段才要查, 而是必須要在原始碼書面階段就要能夠檢查才行! goto造成的指標亂跳, 使得人的腦筋也亂跳. 所以一個循序、有固定出入口的高階語法變成容易瞭解的解決方案. 結構化語法總是由上往下執行, 因功能需求, 有可能回復回到開頭再往返循環. 並且, 出口總是固定, 不是在語法結束, 就是後來加的中途出口敘述. 然而中途出口敘述在機械碼轉換之中也總是從語法結束後離開的. 這和正常離開並沒有兩樣. 我在理解語法的基本原理之後, 配合goto的能力. 我就將「結構化語法」使用 goto指令造出來了. 首先: 'IF' (開頭的指令) 是一個邏輯運算式. 這裡的機械碼轉換和表面語意是相反的! 很奇怪! 'IF'說明的是 '成立' 才做. 但是機械流程用goto來想後, 卻是 '不成立' 要跳離! 跳離到 'ELSE' 段落去做! 原因在goto只做'跳'的動作,'IF' 卻是留在原地, 所以要反過來 '不成立' 才可以跳. 另外, 你可以發現, 結構的幾個地方有 label標記. 即 else 區段開頭, 及 END IF結構結尾的部份. 這是很容易理解的. 因為 'IF' 的構造, 不是二選一, 可能跳到第二段做, 就是單選 (IF/END IF), 條件不成立直接結束 (跳至結尾). 如果 'IF' 段成立. 則ELSE段不能執行, 所以在 'IF' 區段編譯時, 會在段尾加入goto結尾的指令, 以便離開. 然而ELSE段已經是臨近結束, 執行完就會自然離開, 所以ELSE段沒有最後的goto. __goto的挑戰: 巢狀結構化__ 或許有人會問! 現行的程式語法中有巢狀表示法, 也就是IF中有IF等. 那goto 又要如何設計? 語法範例: ------------------------------------------------------- IF 計算邏輯式 if not TRUE goto .else_001 邏輯為假, 跳至ELSE段. ... ... 運算敘述. 邏輯為真, 繼續執行. '--巢狀內層--------------------- IF 計算邏輯式 if not TRUE goto .else_002 ... ... goto .if_002.endif ELSE label .else_002 ... ... END IF label .if_002.endif '------------------------------- ... ... goto .if_001.endif IF段結束跳至出口. ELSE label .else_001 ELSE段進入點註標. ... ... 一般運算敘述. END IF label .if_001.endif IF出口註標. ------------------------------------------------------- 眼尖的程式設計師一看到最前面的範例出現 "if_001.." 的註標就會自己懂了! 註標之所以有編號, 正是為了巢狀結構用的. 這樣編譯器才不會找錯人, 跳到不該執行的段落去! 最後, 說明一下. "goto .if_xxx.endif", "label .if_xxx.endif" 都是編譯器自己假造出來的. 在中間語法分析階段, 編譯器可以自己加入必要的系統碼. 因此goto/ label 都是編譯器添加的, 方便自己編譯出正確的語法來使用. 或者, 你可以說, 這樣的「底層GOTO結構」正是代表成品機械碼最直接的表示法. 因為它已經「明示」了原來「結構化語法」所沒有的東西. __goto的最後說明: 副程序__ 前面的範例並沒有列出所有的「結構化語法」轉換的形式. 這些都可以由您自己來做. 原則一樣. 但是值得一提的是副程序的轉換法. 很簡單, 可是卻可能在一開始就被忽略. (C) 語言指令底層GOTO結構功能說明 -------- ------------ -------- goto .SUBEND_0001 避免前面的敘述「不經同意」執行 SUB label .SUB_0001 副程序的進入點. END SUB label .SUBEND_0001 副程序的出口. 一開始的 goto 很重要! 因為副程序是區段保護的! 沒有正確呼叫不能任意進入副程序中. 這個「陷阱」讓我一開始就掉進去! 直到虛擬機器執行到不該執行的碼時我才發現! 原因在原始碼指令都是連續的. 連副程序定義在裡面也只是「一個指令段落」而已! 由於設計師有可能在原始碼中任意地方加上副程序. 因此有機會出現副程序段與主流程段交替出現的寫法.(這是使用一般文字編輯器寫程式所可能出現的結果.) 然而根據副程序的「意義」. 表明它是「獨立」的程式區段. 所以其存在「和前後的程式碼順序無關」. 一開始我只注意到副程序要有進入點, 否則不會執行. 卻忘掉要加「流程保護」碼. 即最開頭的goto指令. 結果初次的編譯結果就是被副程序定義之前的程式碼「無意中闖入」! 因為副程序就寫在它的後面而已! 【結語】本篇主要闡明. goto是編譯器轉換成機械執行碼的最基本功能. 也是建置「結構化指令」的最終實現指令. 實際上沒有電腦是直接提供「結構化指令」的機械碼的. 高階形式都有低階的化約. 另外, 本篇也簡單的描述了「機械化執行」的一些原則. 這大概可以加強你對 goto能力的印象. 最後. 要實現完整的編譯功能其實還有很長的路要走. 雖然本篇提出了一個簡單的虛擬機器來說明goto實作的方式. 但是高階語法的解譯, 位址運算, 及符號表等等, 本篇沒有另加說明. 因此你可以知道, 本篇的重點只在這個概念: 「結構化指令的底層其實只是goto而已」! Tommy 99/12/08 後註: 現代流行的事件驅動模型. 雖然改變了循序執行的表象. 但是底層執行, 甚至事件函式中的執行段等等, 無一不是以「結構化指令」作基礎的. 所以不要以為有了「事件驅動」就不要懂「結構化執行」, 任何高階抽象的背後都會有基礎的功能來支持的. -- ※ Origin: 楓橋驛站<bbs.cs.nthu.edu.tw> ◆ From: tommy @ 125-232-135-111.dynamic.hinet.net