def 陳述

December 19, 2021

在 Toy Lang 中要定義函式,是使用 def 來定義。

Toy 語法

例如,以下是個求最大公因數的函式定義:

def gcd(m, n) {
    if n == 0 {
        return m
    }
    return gcd(n, m % n)
}

println(gcd(20, 30)) # 顯示 10

在上例中,gcd 是函式名稱,mn 為參數名稱,如果要傳回值則使用 return,如果函式執行完畢但沒有使用 return 傳回值,不會傳回任何值。

在 Toy Lang 中,沒有 nullNoneundefined 之類的東西,因此想判斷有沒有傳回值,可以使用 hasValuenoValue 來測試有沒有值,例如:

def foo1() {
    return 1
}

def foo2() {
    println()
}

println(hasValue(foo1())) # 顯示 true
println(noValue(foo2()))  # 顯示 false

Toy Lang 是動態定型語言,因此基本上不支援函式重載,也就是在同一個範疇中,不能有相同的函式名稱。如果定義了兩個函式具有相同名稱但擁有不同的參數個數,後者定義會覆蓋前者定義。例如:

def sum(a, b, c) {
    return a + b + c
}

def sum(a, b) {
    return a + b
}

println(sum(1, 2))     # 顯示 3
println(sum(1, 2, 3))  # 顯示 3

在上面的範例中,第一個 sum 的定義被第二個覆蓋了,因此就算傳入了三個引數,還是只會計算前兩個,在這邊你也可以看到,呼叫函式時,參數與引數的個數可以不相同,如果引數個數少於參數,未被指定值的參數沒有值,可以使用 hasValuenoValue 來測試有沒有值,例如:

def sum(a, b, c) {
    if hasValue(c) {
        return a + b + c
    }
    return a + b
}

println(sum(1, 2))     # 顯示 3
println(sum(1, 2, 3))  # 顯示 6

如果引數個數多於參數,對應的參數可以取得引數之外,函式中都會有個 arguments 名稱,它會使用 List 自動收集全部的引數,因此,就算是沒有定義參數,也是可以接受引數的:

def sum() {
    return arguments.reduce((acc, n) -> acc + n, 0)
}

println(sum(1, 2))     # 顯示 3
println(sum(1, 2, 3))  # 顯示 6

先前提過,在 Toy Lang 中,變數會在指定值時自動建立,因此,在一個函式中,除非特別使用 nonlocal 指明,否則就是建立區域變數:

x = 10
y = 10
def some() {
    x = 20
    println(x) # 顯示 20
    println(y) # 顯示 10
}

some()
println(x) # 顯示 10

如以上的範例看到的,如果使用的變數名稱,在函式範圍內找不到,就會試著在函式外的環境中尋找,直到頂層範圍還是找不到,就會發生 ReferenceError

在指定變數時使用 nonlocal 時,一定是往外部環境中尋找,先在某個環境中找到的變數就加以設定:

x = 10
y = 10
def some() {
    nonlocal x = 20
    println(x) # 顯示 20
    println(y) # 顯示 10
}

some()
println(x) # 顯示 20

除非透過設計,否則函式中無法直接設定全域變數,在 Toy Lang 中的全域變數,實際是以模組為範圍的變數,之後文件還會討論模組。

Toy 實作

剖析時建立函式節點,基本上沒太大問題,在 Toy Lang 中,def 陳述被當成一種指定,函式名稱被當成變數,函式定義被當成是值,這在 line_parser.jscreateAssignFunc 中可以看到:

...
return new StmtSequence(
    new DefStmt(
        Variable.of(fNameTokenable.value), 
        new Func(
            paramTokenables.map(paramTokenable => Variable.of(paramTokenable.value)), 
            bodyStmt,
            fNameTokenable.value
        )
    ),
    LINE_PARSER.parse(tokenableLines.slice(bodyLineCount + 2)),
    tokenableLines[0].lineNumber
);    

代表函式定義的 Func 節點,就像是個陳述句容器,封裝了本體的陳述句,以及參數、函式名稱,談到這個,要來抱怨一下物件導向,如果沒打算將語言實作為支援物件導向,很多語法節點與執行都可以很簡單解決啊!例如,在還沒有支援物件與類別時,Func 節點就可以直接當一級函式值傳遞了,畢竟,如先前談到,def 陳述被當成一種指定。

為了要支援物件導向,必須定義實例、實現實例所屬的類別,最後還會有 ObjectClass 雞生蛋、蛋生雞的問題,腦袋差點就打結…XD

總之,在剖析完成後,Toy Lang 會執行頂層範圍內的程式碼,若有函式,這時就會生成函式物件,也就是 Function 實例,這才是在傳遞函式時真正的值。

其實是也可以選擇不實現為 Function,直接將 Func 節點傳遞,只不過,這會讓函式看來像是接近基本型態的原生值,此時沒有方法可以操作,就只能靠另一個原生函式來獲取函式名稱等資訊,不過,就使用 Toy Lang 語言來說,還是實現為 Function 實例會比較方便。

總之,執行時會呼叫 Funcevaluate,建立 Function 實例,這可以在 value.js 中的 Func 看到:

class Func extends Value {
    constructor(params, stmt, name = '', parentContext = null) {
        super();
        this.params = params;
        this.stmt = stmt;
        this.name = name;
        this.parentContext = parentContext;
    }

    ...

    withParentContext(context) {
        return new Func(this.params, this.stmt, this.name, context);
    }

    clzOfLang(context) {
        return context.lookUpVariable('Function');;
    }

    evaluate(context) {
        return new Instance(
            this.clzOfLang(context), new Map(), this.withParentContext(context)
        );
    }
}

Func 封裝的 parentContext,與實現 Closure 有關,這邊暫不解釋。到這邊為止,僅僅是函式定義的部份,未涉及函式呼叫,函式呼叫在剖析時也是建立一個節點,這定義在 callable.js 之中:

class FunCall {
    constructor(func, argsList) {
        this.func = func;
        this.argsList = argsList;
    } 

    evaluate(context) {
        return callChain(context, this.func.evaluate(context).internalNode, this.argsList);
    }    

    ...
}

function callChain(context, f, argsList) {
    const args = argsList[0];
    return f.call(context, args).notThrown(c => {
        const returnedValue = c.returnedValue;
        if(argsList.length > 1) {
            return callChain(context, returnedValue.internalNode, argsList.slice(1));
        }
        return returnedValue === null ? Void : returnedValue;
    });
}

可以看到,FunCall 建立時,必須封裝剖析時取得的函式名稱,以及呼叫函式時指定的引數。

執行時期 FunCallevaluate 中,callChain 可以處理 foo()()() 這樣的連續呼叫風格,最主要的是看到,在根據函式名稱查找到 Function 實例之後,internalNode 用來取得 Func 語法節點,並透過 f.call 實際呼叫函式:

function assigns(variables, values) {
    if(variables.length === 0) {
        return StmtSequence.EMPTY;
    }
    return new StmtSequence(
        new VariableAssign(variables[0], values[0]), 
        assigns(variables.slice(1), values.slice(1))
    );
}  

class Func extends Value {
    ...

    assignToParams(context, args) {
        const argumentsListInstance = newInstance(context, 'List', Native, args); 
        return assigns(
            this.params.concat([Variable.of('arguments')]), 
            this.params.map((_, idx) => args[idx] ? args[idx] : Null).concat([argumentsListInstance])
        );
    }

    bodyStmt(context, args) {
        return new StmtSequence(this.assignToParams(context, args), this.stmt, this.stmt.lineNumber);
    }

    call(context, args) {
        const ctxValues = evaluateArgs(context, args);
        if(ctxValues.length !== 0) {
            const ctxValue = ctxValues.slice(-1)[0];
            if(ctxValue.thrownNode) {
                return ctxValue;
            }
        }

        const bodyStmt = this.bodyStmt(context, ctxValues);
        return bodyStmt.evaluate(
            this.parentContext ? 
                this.parentContext.childContext() : // closure context
                context.childContext()
        );
    }

    ...
}

call 方法中,會先對每個引數估值,因為每個引數實際上也是語法節點,除了數值等之外,也有可能是變數、函式呼叫或運算式等,接著將估值完成的引數用來呼叫 bodyStmt 方法。

執行本體之前,必須指定參數的每個引數,這跟指定值給變數是相同的,assignToParams 就是在做這件事,實際上也是建立 VariableAssign 罷了。

assignToParams 中,你看到了…嗯?Null?這是個內部節點,它什麼事也沒做:

class Value {
    evaluate(context) {
        return this;
    }      

    notThrown(f) {
        return f(this);
    }

    box(context) {
        return this;
    }

    toString() {
        return '';
    }
}

// internal null value
const Null = new Value();
// internal void value
const Void = Null;

沒有引數可指定的參數,都會被指定 Null,雖然有內部節點 Null,然而,你不能拿它來做什麼,因為沒有 null 之類的字面表示法,可以取得這個 Null,只能使用 hasValuenoValue 原生函式來測試,在這邊你也看到了 Void,其實它與 Null 參考相同物件,因此想測試函式是否有傳回值,也是使用 hasValuenoValue

在這種情況下,其實真想做,你是可以製作出一個 null 的:

null = println()
println(hasValue(null)) # 顯示 false

當然,真想要有 null 的話,不管語法上再怎麼處理,開發者總有辦法,重點是你為什麼要使用 null 這種東西?想胡搞的話,沒人能阻止你!

可不可以連內部的 Null 都不需要呢?基本上可以,或許像 Python 那樣,嚴格比對參數與引數個數必須相符,不過,因為我想要能模擬函式重載,若嚴格比對參數與引數個數必須相符,那函式必須要有預設引數、不定長度引數等語法。

這不是做不到,只不過會增加剖析器的負擔,實作語言,理解剖析器原理是一個重點,然而不是全部,在剖析完成、建立語法樹之後,後續要處理的細節還有非常多,因而,我儘量善用先前已經建立起來的剖析過程,在可以不增加語法上,儘量增強語言的能力。

因此,我採用了 JavaScript 的做法,允許引數與參數在個數上不相同,並使用 arguments 來收集全部的引數,在 assignToParams 中可以看到,arguments 會在呼叫函式時自動建立。

Func 是個陳述句容器,每一次的函式呼叫,會根據這個容器中的函式定義,指定引數後產生一串陳述句,接著執行陳述句,這就是函式呼叫的原理了,注意到 Funccall 中,在執行傳回的函式本體時,會有個 context.childContext()

也就是說,執行函式本體時,會產生一個新的環境物件,函式中的參數、變數,實際上都是在儲存在這個環境物件中,每個環境物件都會記得自己的 Parent 環境物件,在取得某個變數值時,若當時的環境物件找不到,就會往 Parent 環境物件查找。

嗯?不是常聽到,呼叫函式時會有呼叫堆疊(Call stack)嗎?堆疊呢?這概念應該是源自於基於堆疊的虛擬機實作,因為 Toy Lang 實作並沒有涉及虛擬機,使用的是 JavaScript,以鏈狀的方式將環境物件串接起來,當然,如果將 Parent 環境物件放在下頭,Child 環境物件放在上頭,看來也像是一層一層堆疊起來啦!(謎之音:這樣解釋也行啊…XD)

由於每個函式都會擁有自己的環境物件,按照〈變數與指定陳述〉中的說明,x = 10 這樣的指定陳述,自然也就是在函式自身的環境物件上註冊名稱與值了,至於 nonlocal 的話:

class NonlocalAssign extends Stmt {
    constructor(variable, value, operator) {
        super(1);
        this.variable = variable;
        this.value = value;
        this.operator = operator;
    }

    evaluate(context) {
        const maybeContext = this.value.evaluate(context);
        return maybeContext.notThrown(value => {
            if(this.operator) {
                return setParentVariable(
                    context, 
                    this.variable.name, 
                    ARITHMETIC_OPERATORS.get(this.operator)(this.variable.evaluate(context), value)
                );
                }
                return setParentVariable(context, this.variable.name, value);
        });
    }
}

這在 assignment.js 中可以找到,簡單來說,執行時,setParentVariable 會直接從 Parent 環境物件開始尋找變數名稱,看在哪個環境物件中找到,值就設定在那個環境物件中。

當然,最後別忘了 return,它的處理方式與 break 類似,會在環境物件中註記有傳回值,也就是底下 context.returned(value) 做的事情:

class Return extends Stmt {
    constructor(value) {
        super(1);
        this.value = value;
    }

    evaluate(context) {
        const maybeCtx = this.value.evaluate(context);
        return maybeCtx.notThrown(value => context.returned(value));
    }    
}

Return 定義在 statement.js 之中,與使用語言撰寫程式碼的感覺不一樣,使用語言時 return 像是從函式中「傳」回值,實際上,值是用環境物件「帶」出來的。

原因在〈while 陳述〉中其實解釋過,語言實作中大致上可以分為陳述句與運算式,而陳述句必須不斷地傳遞整個環境的狀態,因此舉一反三的話,如果不在環境物件上註記,直接傳回一個代表執行過 return 的物件,那麼上一個陳述句節點執行過後的環境物件狀態,就勢必被中斷,程式的狀態就無法不斷地傳遞下去了。

類似地,若是每次都得檢查每個陳述句執行過後,環境物件是否有被註記,著實沒有效率,因而實際上,並沒有真的做檢查的動作,而是使用回呼函式,原理上與 break 相同,這就是 StmtSequence 中會看到 notReturn 的原因:

class StmtSequence extends Stmt {
    constructor(firstStmt, secondStmt, lineNumber) {
        super(firstStmt.lineCount + secondStmt.lineCount);
        this.firstStmt = firstStmt;
        this.secondStmt = secondStmt;
        this.lineNumber = lineNumber;
    }
    
    evaluate(context) {
        try {
            const fstStmtContext = this.firstStmt.evaluate(context);
            return addTraceOrStmt(context, fstStmtContext, this.lineNumber, this.secondStmt);
        } catch(e) {
            if(this.lineNumber) {
                addStackTrace(context, e, {
                    fileName : context.fileName,
                    lineNumber : this.lineNumber,
                    statement : context.lines.get(this.lineNumber)
                });
            }
            throw e;
        }
    }      
}

function addTraceOrStmt(context, preStmtContext, lineNumber, stmt) {
    return preStmtContext.either(
        leftContext => {
            if(leftContext.thrownNode.stackTraceElements.length === 0 || 
                context !== leftContext.thrownContext) {
                leftContext.thrownNode.addStackTraceElement({
                    fileName : context.fileName,
                    lineNumber : lineNumber,
                    statement : context.lines.get(lineNumber)
                });
            }
            return leftContext;
        },
        rightContext => rightContext.notReturn(
            ctx => ctx.notBroken(c => stmt.evaluate(c))  
        )
    );
}

因為要一次談完函式中比較完整的概念,這一篇文件顯得冗長的多,實際上還沒完呢!後面還有 Closure、lambda 運算式要討論,實際上,函式的實作,或許是語言實現中最值得書寫的地方,很多後續的特性實現,像是方法、類別定義等,都是建立在函式的基礎上,在函式上花較多的心力,其實是相當值得的。