Closure

December 20, 2021

在 Toy Lang 中,函式中還可以定義函式,稱為區域函式(Local function),可以使用區域函式將某函式中的演算組織為更小的單元。

Toy 語法

例如,在〈選擇排序〉實作時,每次會從未排序部份,選擇最小值放到已排序部份之後,在底下的範例中,尋找最小值的演算,就實作為區域函式的方式:

def selection(number) {
    # 找出未排序中最小值
    def min(m, j) {
        if j == number.length() {
            return m
        }
        if number.get(j) < number.get(m) {
            return min(j, j + 1)
        }
        
        return min(m, j + 1)
    }
    
    i = 0
    while i < number.length() {
        m = min(i, i + 1)
        number.swap(i, m)
        i += 1
    }
}

number = [1, 5, 2, 3, 9, 7]
selection(number)
println(number)     # 顯示 [1, 2, 3, 5, 7, 9]

區域函式的好處之一,就是可以直接存取包裹它的外部函式之參數(或宣告在區域函式之前的區域變數),如此可減少呼叫函式時引數的傳遞。

如〈def 陳述〉中談到的,Toy Lang 執行到 def 時,會產生一個函式物件,為 Function 的實例,既然函式是個物件,它可以指定給其他的變數,例如:

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

println(gcd(20, 30))         # 顯示 10
println(gcd.class())         # 顯示 <Class Function>

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

既然函式是個物件,可以指定給其他變數,當然也可以傳入函式:

def printFoo() {
    println('Foo')
}

iterate(0, 5).forEach(printFoo) # 顯示 5 行 Foo

或者是從函式中傳回:

def doSome() {
    x = 10
    def f(y) {
        return x + y
    }
    return f
}

foo = doSome()
println(foo(20))  # 顯示 30
println(foo(30))  # 顯示 40

上面的函式 doSome 中,區域函式 f 建立了一個 Closure,如果單看:

def f(y) {
    return x + y
}

看來起變數 x 似乎沒有定義,因而外部函式的環境物件,必須有個 x,呼叫 f 時才有意義,若是在 doSome 中呼叫 f(2),由於外部函式有個 x 參考了 10,因此結果會是 12,這部份沒有問題。

Toy Lang 中每個函式,都會記錄外部函式的環境物件,當 fdoSome 傳回,f 會記得 doSome 的環境物件,而在查找 x 時,由於 f 本身沒有該名稱,這時會看看本身記錄的環境物件,也就是 doSome 的環境物件,這時仍然可以找到,因此才可以順利執行傳回的函式。

函式從函式傳回後,被傳回的函式仍然存取當時外部函式中的變數,或者另一種說法,外部函式中的變數,生命週期被傳回的延續了,具有這個能力的函式,在現代程式語言中,被稱為 Closure。

如果在 Closure 上,使用 nonlocal 指定外部函式的環境物件中之變數會如何呢?

def doSome() {
    x = 10
    def f(y) {
        nonlocal x = x + y
        return x
    }
    return f
}

foo = doSome()
println(foo(20))  # 顯示 30
println(foo(30))  # 顯示 60

由於 Toy Lang 的函式會攜帶外部函式的環境物件,因此使用 nonlocal 時的行為,當然也是對外部函式的環境物件之名稱設值,以 Closure 的術語概念來說的話,Closure 綁定的是變數,而不是值。

你可能會有疑問的是,如果 Closure 關閉了某個變數,使得該變數的生命週期得以延長,那麼這個會怎麼樣?

def doSome() {
    x = 10
    def f(y) {
        nonlocal x = x + y
        return x
    }
    return f
}

foo1 = doSome()
foo2 = doSome()
println(foo1(20))  # 顯示 30
println(foo2(20))  # 顯示 30

在這個範例中,doSome 被呼叫了兩次,每次呼叫時其實都建立了個別的區域變數 x,而個別建立的 Closure 綁定了個別的 x(傳回的函式攜帶了當時外部函式各自的環境物件)。foo1foo2 中的 x 彼此並不影響。

Toy 實作

在〈def 陳述〉中談過,def 陳述被當成一種指定,函式名稱被當成變數,函式定義被當成是值,執行時期這個值會是 Function 的實例,既然如此,函式可以被任意傳遞,是再自然也不過的事情了,沒有需要多做任何的實作。

然而,單只有這樣,沒辦法構造 Closure 的功能,想當然爾,每次呼叫函式之後,呼叫函式時的 Child 環境物件就沒有用了,如果你不想辦法保留這個環境物件,也就無法查找環境物件中的變數。

因此,必須要有個方式,可以讓傳回的函式與當時外部函式物件產生對應,不同的語言實作應該各有其方式,比方說 JavaScript 的 Scope chain,Toy Lang 的方式則是,直接封裝在 Func 節點上,也就是〈def 陳述〉中看過的 parentContext

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

    ...

    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()
        );
    }

    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)
        );
    }
}

就就是在執行時期,外部函式的 context 環境物件,會先封裝在 Func 節點之中,然後才建立 Function 實例傳回,而在呼叫函式時,也就是 call 方法中,可以看到是用 parentContext 產生 Child 環境物件,因此查找的環境物件鏈上,才可以找到變數。

想當年,由於 JavaScript 流行起來,連帶著 Closure 被廣泛的討論,然而對多數未接觸過一級函式概念的開發者而言,總覺得 Closure 很神秘,實際上,從語言實作層面的概念來看,Closure 一點也不複雜,差別在於不同的實作中是如何保存環境物件。