while 陳述

December 19, 2021

while 陳述根據指定的條件式,判斷是否執行 while 本體,用以進行重複性的演算。

Toy 語法

例如以下是個求最大公因數的程式:

m = Number.parseInt(input('輸入數字 1'))
n = Number.parseInt(input('輸入數字 2'))

while n != 0 {
   r = m % n
   m = n
   n = r
}

println('GCD: ' + m)

Toy Lang 沒有其他語言中有的 do while 語句,必須使用判斷式及 break 來達成。例如判斷輸入為奇數或偶數,直到使用者回答 No 為止:

while true {
    number = Number.parseInt(input('輸入數字:'))
    println('輸入數為' + ('奇數' if number % 2 else '偶數'))
    if input('繼續?(Yes/No)') == 'No' {
        break
    }
}

底下是個很無聊的遊戲,看誰可以最久不撞到這個數字 5:

import '/lib/math'

while true {
    number = Number.parseInt(math.random() * 10)
    println(number)
    if number == 5 {
        break
    }
}

println('I hit 5....Orz')

Toy Lang 有模組管理機制,math 模組是標準模組之一,其中包含了 random 函式,會隨機產生 0.0 到小於 1.0 的值,乘上 10 再裁掉小數部份,表示產生 0 到 9 的數。

Toy 實作

如果會建立 if 陳述相對應的語法節點,while 相對應的語法節點,基本上不成問題:

class While {
    constructor(cond, stmt) {
        this.cond = cond;
        this.stmt = stmt;
    }

    evaluate(context) {
        let ctx = context;
        while(true) {
            if(this.cond.evaluate(context).value) {
                ctx = this.stmt.evaluate(context);
            }
            else {
                break;
            }
        }
        return ctx;
    }   
}

也就是每次對 while 的條件式節點求值,結果會是 true,就一直執行 while 本體的陳述句節點,不過,還得考慮 break,它會有一個相對應的 Break 節點:

const Break = {
    lineCount : 1,
    evaluate(context) {
        return context.broken();
    }
};

也就是執行 break,相對應的 Break 會在環境物件中做個註記,表示執行了 break,只要環境物件中這個註記還存在,while 本體中的之後每個陳述節點都不會執行,而 While 節點:

class While {
    constructor(cond, stmt) {
        this.cond = cond;
        this.stmt = stmt;
    }

    evaluate(context) {
        let ctx = context;
        while(true) {
            if(this.cond.evaluate(context).value) {
                ctx = this.stmt.evaluate(context);
                if(ctx.isBroken()) {
                    return ctx.fixBroken();
                }
            }
            else {
                break;
            }
        }
        return ctx;
    }   
}

break 會中斷目前的 while 陳述,因此本體的陳述節點執行過後,檢查 ctx.isBroken() 看看環境物件有無註記,有的話就 return,然而在 return 之前,必須先清楚環境物件中關於 break 的註記,這就是 ctx.fixBroken() 做的事情,否則在 while 陳述後若還有其他陳述,也會無法執行。

檢查每個陳述句執行過後,環境物件是否有被註記,實際上應該實作在 StmtSequence 之中,不過,程式中的 StmtSequence 何其多,每執行一次陳述句,就得檢查一次環境物件,著實沒有效率,因而實際上,我並沒有真的做檢查的動作,而是使用回呼函式。

每個環境物件都有個 notBroken 函式,上一個陳述句若傳回 ctx,要執行下個陳述句 stmt 的話,程式碼上會是:

ctx.notBroken(c => stmt.evaluate(c));

notBroken 平常參考的函式會是:

function call(f) {
    return f(this);
} 

也就是方才的 c 在正常執行流程下,就是 ctx,萬一有個 break 執行了,對應的節點會執行環境物件的 broken 方法,這時環境物件的 notBroken 會被代換為:

function self(f) {
    return this;
} 

也就是此時,會忽略掉傳入的 f,因此等同於略過回呼中指定的 stmt 之估值,這樣就不用每次都檢查有沒有被註解 break 了;如果呼叫了環境物件的 fixBroken 方法,就會將 notBroken 參考的函式,恢復為方才的 call 函式。

為什麼取名為 notBroken,因為可讀性,也就是 ctx.notBroken(c => stmt.evaluate(c)) 代表的是,在沒有 break 下執行回呼函式。

方才談到的實作,都可以在 context.jsstatement.js 中看到,實際的流程會再複雜一些,因為還處理了 returnthrow 的情況。

至於為什麼要採用在環境物件上註記的方式呢?記得之前談過陳述句與運算式的差別嗎?

若是陳述句,通常會對環境物件造成狀態變更,因此陳述句節點,必須傳回環境物件,如此下個陳述節點,才能在最新狀態的環境物件基礎下,繼續執行程式;如果是運算式節點,通常傳回自身,如此下個運算節點,才可以從傳回的物件上取得內含值,像是 xxx.value 這樣的動作。

運算式通常被包含在一個陳述句中,或者之後會看到,被包裝為在一個陳述節點之中,簡而言之,無論是哪個,最新的環境物件都必須被不斷傳遞下去;如果不在環境物件上註記,直接傳回一個代表執行過 break 的物件,那麼上一個陳述句節點執行過後的環境物件狀態,就勢必被中斷,程式的狀態就無法不斷地傳遞下去了。

既然談到了 While 節點,可以看一下 statement.jsWhile 的實作:

class While extends Stmt {
    constructor(boolean, stmt) {
        super(stmt.lineCount + 2);
        this.boolean = boolean;
        this.stmt = stmt;
    }

    evaluate(context) {
        let ctx = context;
        while(true) {
            const maybeContext = this.boolean.evaluate(ctx);
            if(maybeContext.thrownNode) {
                return maybeContext;
            }

            if(maybeContext.value) {
                ctx = this.stmt.evaluate(ctx);
                if(ctx.thrownNode || ctx.returnedValue) {
                    return ctx;
                }
                if(ctx.isBroken()) {
                    return ctx.fixBroken();
                }
            } else { break; }
        }
        return ctx;

        /*
            To avoid 'Maximum call stack size exceeded', the above code is the only place which uses 'while'.
            The corresponding code with the functional style is shown below.
            */

        // const maybeContext = this.boolean.evaluate(context);
        // return maybeContext.notThrown(v => {
        //     if(v.value) {
        //         const ctx = this.stmt.evaluate(context);
        //         return ctx.either(
        //             leftContext => leftContext, 
        //             rightContext => rightContext.notReturn(
        //                 c => c.isBroken() ? c.fixBroken() : this.evaluate(c)        
        //             )
        //         );
        //     }    
        //     return context;
        // });
    }   
}

嗯?那段註解是什麼?你可以試著找找看 Toy Lang 的 .js 實作原始碼,看看其他地方有沒有出現 while,實際上,這是唯一使用到 while 的地方喔!另外,在 .js 實作原始碼中,絕大多數的地方在宣告變數時是使用 const,只有在少數地方使用到 let

在實作 Toy Lang 時,我特意在大多數的地方採用函數式典範,這有很大的好處,特別是對函式流程的抽取、模組與類別職責的分配,以及模組與物件之間的獨立性等,我一直都有談到,對於語言實作來說,元件的獨立性很重要,若以函數式典範作為出發點,你就得一開始就考慮這些要素。

也就因此,具有重複性的邏輯,很多都被 filtermapreduce 這種基本模式的實作品給解決掉了,filtermapreduce 做不到的,就採用遞迴解決,結果就是每個函式流程都很精簡,每個模組也不巨大。

然而,這在實作 while 就會有問題,因為 JavaScript 並不支援遞迴的展開,也就因此,會受到遞迴深度的限制,上面程式碼註解的部份,就是實作 while 時對應的遞迴版本,實作它是有價值的,然而,因為受到遞迴深度的限制,while 本體變成差不多只能執行 2000 次左右了。

雖然是 Toy Lang,然而,如果 while 只能執行 2000 次左右,那就連 Toy 都稱不上了,對吧!?這也就令此處,成了唯一有使用到 while 實作的地方了!

話說,一下子又是 Toy Lang 的 while,一下子又是 JavaScript 的 while,你知道我正在談哪個 while 嗎?沒辦法!選的關鍵字雷同,經常會搞不清楚嘞!

之後在實作類別與實例時,我也是常得保持腦袋清楚,不然,很容易搞不清楚,我現在是想要 JavaScript 的某個實例,還是 Toy Lang 的某個實例啊…XD