Hw4 開發紀錄(B)

基礎知識

JIT (Just In Time) compilation
與執行前編譯好執行檔不一樣,JIT 是一邊執行程式一邊編譯,可以直接將程式碼轉成機械碼或是其他形式執行。常常使用在 dynamic programming language。
 
BrainF*ck
  • 圖靈實現語言:可以用來模擬單磁帶圖靈機的程式語言,而且只要懂一種圖靈實驗語言,就可以理解其他同一類型的語言。「磁帶」的每一個符號都有對應的動作,透過有限的 table 查表運作。而 brainf*ck 只有八個指令:
  • >:移動 data pointer 到下一個 cell
  • <:移動 data pointer 到上一個 cell
  • +:加一 data pointer 指向的 byte
  • -:減一 data pointer 指向的 byte
  • .:輸出 data pointer 所指向的 byte
  • ,:輸入 1 byte 的資料到 data pointer 所指向的 cell
  • [:如果 data pointer 所指向的資料為 0,就跳到 ]之後繼續執行,否則往下執行
  • ]:跳回對應的]繼續執行
  • 需要一個磁帶的空間,另一個是存資料的空間 (cell),例如給變數的空間。
  • [P11]:遇到迴圈起點時,先找尋對應的迴圈終點。可以偵測巢狀迴圈:
  • 因為是先遇到[ ,所以將 b初始化為 1,如果遇到 ]就減一,遇到[就加一。當b為 0 時,就代表找到成對的中括號。
  • 找到之後,先將對應的],改成0,為了就是讓 data pointer 偵測迴圈終點。recursive call,進入迴圈執行。等迴圈結束後,再將0改回]
  • [P16]:x=y,假設 x 存在 cell 0,y 存在 cell 1,data pointer 目前指向 x:那就會是 >[-<+>]
  • 將 y 減 1,再將 x 加 1,直到 y 為 0。
  • 另一個方法是將 y 的值存到  t 中,然後減掉 t,同時將 x y 加回來。假設 t 在 cell 2,data pointer 目前指向 x:>[->+<]>[-<<+>+>] 
  • [P17]:if statement:
Move x to t;
if ( t != 0 ) recharge x; foobar;
  • [P18]:clean,用一個 while loop 把那個 cell 減到 0。
  • [P19]:cat,先將目前的 cell 加一,確保他非 0,然後用一個 while loop,一直讀輸入,再輸出,直到遇到\0
  • [P22]:Multiply,就是連續加法,用一個 cell 存要加幾次,在重複加另一個 cell
  • [P23]:Divide,連續減法,用一個 cell 存被除數,一個 cell 存商,每次 loop 減被除數除數
// a / b = c;
cell 0 store the value of a.
while ( a > 0 ) {
    ++c;
    a -= b;
}
  • [P26]:bubble sort
>>>>>,.[>>>,.]        // 從第六個 cell 開始,讀取輸入,每隔兩個存一個值
<<<                   // 當輸入結束 (讀到0時),移回最後一個資料
[<<<                  // 迴圈A:移到上一個資料
[>>>                  // 迴圈B:移到下一個資料
    [-<<<-<+>[>]>>]   // 迴圈C1:每次將這個資料與上一個資料減一,每減一次就在上個資料的前一個 cell 加一,然後移回上一個資料。如果上一個資料還沒歸零的話,就會重複移回這個資料,持續上述動作。所以說,較小的值會被存到上一個資料的前面的 cell。如果上一個比這個大,data pointer 最終會指向這個資料(此時這個為0)。否則,會指向這個資料的前面一個 cell(此時上一個為0)
    <<<[<]>>          // 找到上一個資料的位置
    [>>>+<<<-]<       // 迴圈C2:如果上一個值比較大,就會先把剩下的值搬到"這個"去,然後指回暫時存起來的最小值
    [>+>>>+<<<<-]     // 迴圈C3:然後把暫存的最小值都搬到兩個資料中。搬移完成後,data pointer 會在這個暫存 cell 中。這樣比較大的值,就會跑到後面去了。
<<]                   // 迴圈B:往上一個值移動,這樣比較小的值就會一直往前,直到遇到0
>>>[.[-]]             // 往後移動到最近的資料,印出這個值後,把他 clear 掉(所以最小值會先被印出來)
>>>[>>>]<<<]          // 迴圈A:往下一個資料移動,直到遇到0後,將指標轉回最後一個,直到所有資料都被印出來(all 0)
  • 優化:對於重複執行的動作,可以進行優化
  • 連續加法,或連續減法,連續移動:都可以被一條指令給取代,而非一個一個重複執行