List 與迭代 API

December 19, 2021

List 是有序的物件集合,具有索引特性,長度可以變動。

Toy 語法

要建立 List,可以使用內建的 List 類別,每個元素,使用逗號 , 區隔,例如:

lt = new List(1, 2)

# 逐行顯示元素
i = 0
while i < lt.length() {
    println(lt.get(i))
    i += 1
}

lt.add(3).add(4)
println(lt)      # 顯示 [1,2,3,4]

除了使用 List 之外,也可以使用 [] 實字,這是建立 List 的便捷方式,例如:

lt = [1, 2, 3, 4]
println(lt)    # [1,2,3,4]

lt.remove(1)
println(lt)    # [2,3,4]

lt2 = lt.concat([10, 20])
println(lt2)   # [2,3,4,10,20]

List 是 List 類別的實例,List 類別上定義了一些迭代處理元素的便捷方法,例如:

([1, 2, 3, 4, 5].filter(elem -> elem >= 2) 
                .map(elem -> elem * 100)   
                .forEach(println)) # 顯示 200、300、400、500

在 Toy Lang 中,如果運算式需要跨越多行,必須使用 () 將之含括,另一個方式是使用 \

[1, 2, 3, 4, 5].filter(elem -> elem >= 2) \
               .map(elem -> elem * 100)   \
               .forEach(println)   # 顯示 200、300、400、500

如上所示,filtermapforEach 等方法,可以接受函式,也就是說在 Toy Lang 中,函式是一級值,而這邊指定的是 lambda 運算式,它會產生函式實例,對於可以在一行內完成的小函式,使用 lambda 運算式是比較方便的。

如果要建立的 List 數值是某個範圍,可以使用 range 函式,例如:

(range(2, 6).filter(elem -> elem >= 2) 
            .map(elem -> elem * 100)   
            .forEach(println)) # 顯示 200、300、400、500

range 可根據指定的數值範圍,產生 List 實例,預設的步進值是 1,可以用第三個引數來指定步進值,步進值可以是負數:

println(range(1, 30, 5))    # 顯示 [1,6,11,16,21,26]
println(range(100, 90, -2)) # 顯示 [100,98,96,94,92]

甚至可以使用 lambda 運算式來指定範圍的終點以及步進方式:

println(range(1, n -> n < 30, n -> n + 5))    # 顯示 [1,6,11,16,21,26]
println(range(100, n -> n > 90, n -> n - 2))  # 顯示 [100,98,96,94,92]

如果只是需要迭代,不需要實際產生 List,可以使用 iterate 函式:

iterate(1, 5).forEach(println) # 顯示 1 到 4

range 不同的是,iterate 產生的並不是 List 實例,而是個迭代器,這個迭代器具有 hasNextnextforEachselect 以及 collect 方法,舉例而言,range(1, 100) 會產生 List,內含元素值 1 到 99,然而 iterate(1, 100) 並沒有馬上產生 1 到 99 的數值,只有在 next 等方法呼叫之時,才會進一步產生出值來。

也就是說,如果只是要迭代,而不是真的要有個 List,那麼 iterate 會比較有效率,若需要將數值收集起來,可以使用 collect 方法,若需要先做個條件過濾再收集起來,可以使用 select,這兩個方法是會產生 List 實例,用以銜接 List 的 API。

(iterate(2, 6).select(elem -> elem >= 2) 
              .forEach(println)) # 顯示 2、3、4、5

Toy 實作

在實作 Toy Lang 的過程中,List 是放在很後期才實作出來的 API,因為它是個類別,顯然地,就必須在有函式與類別的語法,以及相對應的語法節點之後,才能夠進一步實作。

為了儘早讓 Toy Lang 可以做些比較實際的運算,List 底層實際銜接了 JavaScript 原生的 Array API,這沒有什麼好意外地,許多語言為了效率,有些函式在底層也都會銜接至 C 語言的程式庫。

對於 Toy Lang 來說,銜接至 JavaScript 程式庫的實作,都放在 builtin 之中,現在要解釋裏頭的實作原理還太早,這部份會等到談到函式與類別之後,再來逐步說明。

然而如同〈字串與註解〉裏說過的,老是將函式或方法,直接對應至底層 JavaScript 的 API 沒有意思,因而後來,除了真的必須得用到 JavaScript 環境的一些 API 之外,我就直接用 Toy Lang 來寫函式或方法了,例如 rangeiterate,就是實作在 builtin.toy 之中:

def stopLambda(stop, step) {
    if typeof(stop) == 'number' {
        if noValue(step) or ((typeof(step) == 'number') and step > 0) {
            return i -> i < stop
        }
        else {
            return i -> i > stop 
        }
    }
    return stop
}

def stepLambda(step) {
    if noValue(step) {
        return i -> i + 1
    }

    if typeof(step) == 'number' {
        return i -> i + step
    }
    return step
}

def iterate(start, stop, step) {
    n = start
    p = stopLambda(stop, step)
    s = stepLambda(step)

    class Iter {
        def hasNext() {
            return p(n)
        }

        def next() {
            v = n
            nonlocal n = s(n)
            return v
        }

        def forEach(action) {
            while this.hasNext() {
                action(this.next())
            }
        }          

        def select(predicate) {
            lt = []
            while this.hasNext() {
                nx = this.next()
                if predicate(nx) {
                    lt.add(nx)
                }
            }
            return lt
        }  

        def collect(mapper) {
            lt = []
            this.forEach(elem -> lt.add(mapper(elem)))
            return lt  
        }
    }

    return new Iter()
}

def range(start, stop, step) {
    lt = []
    iterate(start, stop, step).forEach(n -> lt.add(n))
    return lt
}

你也可以從這個程式碼中,先預覽一下 Toy Lang 的函式與類別語法風格,這某些程度也是在測試 Toy Lang 的文法是否足以勝任一般性的任務,另一方面,現代開發者,應該很少有機會自行實作標準程式庫吧!偶而地,想要搞點小實驗,像是自行實現個亂數函式,就可以 Toy Lang 裏試試,別有一番樂趣。

方才談到,Toy Lang 中若運算式要跨越多行,必須使用 () 或者是 \,這是因為先前提過的,為了簡化 Parser 的設計,Toy Lang 採逐行剖析,強硬地運用了 Regular expression 來處理了大半的事情,然而,若不能跨行,上面範例那種流暢 API 風格,撰寫時就會受到一定的限制。

Toy Lang 在預處理原始碼時,會將 ()\ 標示的多行合併為一行,然後再進行剖析,tokenizer.js 裏的 concatExpr 函式做的,就是這件事。

然而,多行合併為一行,也就會造成顯示除錯訊息時的小問題,例如:

([1, 2, 3, 4, 5].filter(elem -> elem >= 2) 
	            .map(elem -> elem * 100)   
	            .foreach(println))

顯示的錯誤訊息會是:

ReferenceError: foreach is not defined
	at [1, 2, 3, 4, 5].filter(elem -> elem >= 2) .map(elem -> elem * 100) .foreach(println) (/main.toy:1)

也就是原本換行排版好的原始碼,在錯誤訊息中也被合併為一行了,這個嘛,必須從一開始的 Parser 設計就解決,就當成日後有機會實現下門語言的課題吧!

回到 List 本身,[] 的寫法,在建立語法樹時,實際上等同於 new List(),這在 expr_parser.js 中可以看到:

['list', {
	burst(elemTokenables) {
		const NewOperator = UNARY_OPERATORS.get('new');
		const args = elemTokenables.length === 1 && elemTokenables[0].value === '' ? [[]] :
							[elemTokenables.map(elem => EXPR_PARSER.parse(elem))]
				
		return new NewOperator(
			new FunCall(
				Variable.of('List'), 
				args
			)
		);
	}        
}]

如果編譯器會產生中介的位元碼(byte code)之類,最後寫出的位元碼會是相同的,這就是所謂的語法糖吧!雖然 List 可以使用 [] 建立,不過以索引取值或設值,還是透過 Listgetset 方法,理由之一是,後期我把心力都放在語法樹上,lt[0]、或 lt[1] = 10 這類的語法,必須在語法剖析器實作,有點懶得去做,另一個原因,等到後面談到函式時,再來說吧!