產生器與惰性求值

iThome 網站首載：產生器與惰性求值

多數傳統程式語言，特別是命令式（Imperative）語言的求值策略是立刻求值（Eager evaluation），也就是運算式（Expression）在被指定至變數時，就會立即運算出數值，習於使用這些傳統語言的開發者，對於惰性求值（Lazy evaluation）的概念與應用相對來說較不熟悉，若能認識惰性求值，在適當場合善用對應的語法或程式庫，對於效能的改進將會有極大幫助。

Python中的產生器語法

在Python中有個yield語法可運用在函式中，呼叫包括yield的函式時，實際上並非執行函式內容，而是傳回產生器（Generator），產生器的__next__被呼叫時，才會執行原本包括yield的流程，單看流程定義的話，yield很像是return可傳回值，不過傳回值後，流程會離開函式回到呼叫__next__的客戶端流程，客戶端再度呼叫產生器的__next__時，流程又會回到函式中yield處並承接先前狀態繼續執行，可是這語法有什麼好處呢？應用之一是產生無限長的自然數列：

def natural(x):

              while True:

                  yield x; x += 1

假設呼叫natural(1)後會傳回產生器並指定給gen變數，next(gen)就會呼叫gen的__next__方法，此時執行natural函式定義的流程並於yield時傳回1，客戶端再呼叫next(gen)就會繼續x += 1的流程並再度回到迴圈開頭執行yield傳回2，依此類推。建立無限長自然數的list在Python中是不可能的，然而使用yield建立產生器，就可在需要時產生下一個自然數。在Python中還可使用for表達式（Comprehension）建立產生器，例如(get_person_from_database(id) for id in ids)會建立產生器，而[get_person_from_database(id) for id in ids]會直接產生list，如果如前者建立產生器並指定給person_gen的話，那麼以下程式會比直接產生list有效率：

for person in person_gen:
if(person.luckyNumber == generatedLuckyNumber):
return person

上面的for in迴圈會呼叫產生器的__next__，此時get_person_from_database才會實際執行，查詢資料庫是個耗時工作，若原本的ids有1000個，假設首次迭代就找到幸運兒，那後面就節省了後續999次的查詢資料庫動作，提供了捷徑（Short-circuit）運算的可能性。

迭代器與產生器的不同

Python使用者可能會聯想到迭代器，正如我先前專欄〈從具體到抽象的迭代器〉中談過的，迭代器可尋訪一組資料，在Python中可實作物件的__iter__方法傳回迭代器，通常使用iter函式來呼叫物件的__iter__方法，迭代器與產生器使用相同的協定，也就是迭代器也具有__next__方法。事實上，可搭配for in迴圈的是具有__iter__方法的物件，迴圈會透過__iter__取得迭代器，再於迴圈中呼叫迭代器的__next__方法。前段介紹的產生器就實作了__iter__方法，因此可搭配for in迴圈進行迭代。

既然Python中的產生器與迭代器，都是具有__next__方法的物件，那為何要區分產生器與迭代器？直接以迭代器概念，也可實現無限長自然數列或是捷徑運算不是嗎？畢竟使用產生器搭配for in迴圈時，最後也是呼叫迭代器__next__方法時，將之委託給產生器的__next__方法罷了。就Python而言，主要程式碼在表述能力上的問題，Python提供了yield與for表達式來建立產生器，可使得程式碼在流程表述上更為清楚。

在沒有內建產生器語法的語言中，像是Java，確實可以實作迭代器模式，令迭代器具備產生器的行為；實際上，在JDK8設計與Lambda語法搭配的Collection API時，2012年4月的草案中就曾考慮過在Iterable上定義filter、map等方法，令他們傳回Iterable物件，而這些物件的iterator方法傳回的Iterator實作，將具有產生器的功能，只不過，相對於直接提供語法建立產生器來說，使用迭代器來實作產生器概念時，程式碼著實刁鑽了許多。

以產生器實現惰性求值

先前實現無限長自然數列或是捷徑運算的範例，實際上都是產生器於惰性求值的應用。惰性求值常見於函數式程式語言，運算式不會在被指定給變數時立即求值，而是真正要取用值的時候才進行運算。舉例來說，Java中若有個addOne方法，可將傳入的List中之元素都加1後傳回新List，那麼addOne(addOne(addOne(list)))時將會發生三次走訪List的動作，整個過程中最右邊的addOne會產生List傳給中間的addOne，而該addOne又產生新的List傳給最右邊的addOne，然後最右的addOne產生最後的List。

然而在Haskell中，執行addOne \$ addOne \$ addOne [1, 2, 3, 4, 5]時，最右邊的addOne並不會馬上求值，而是當最左邊的addOne需要在第一個元素上加1時，中間addOne才會要求最右邊的addOne提供第一個元素，因此整個過程完成只需產生一個數列，數列走訪只會發生一次，由此獲得效率上的改進。簡單來說，在Haskell這類支援惰性求值的語言中，每個運算式都是產生器，並不需要特別的語法。

Python的運算式不支援惰性求值，然而提供yield與for表達式來建立產生器，在實現惰性求值時甚至可以不影響原本流程表述方式。例如在Python中addOne(addOne(addOne(list)))時，想要有Haskell中類似的惰性求值效果，可以定義addOne函式如下：

def addOne(lt):

              return (ele + 1 for ele in lt)

基本上這個流程表述方式，Python開發者都很熟悉，只不過將[]改為()，不過addOne(addOne(addOne(list)))最後傳回的還是產生器，因此得搭配next函式，或者是for in語法來逐一取得元素，或者是使用list函式從產生器中建立list物件，用set函式建立set物件等。實際上，Python中有些函式的結果就是產生器，像是map、filter，它們傳回map與filter實例，而不是list。

區分職責與語義

在Python中由於有支援產生器的語法，因此產生器與迭代器在外觀與職責算是清楚，然而在沒有這類支援的Java中，雖可使用迭代器來實現產生器，然而職責上混淆不清。2012年12月的草案中提出新的Stream物件來擔負產生器職責。相對於Collection是以iterator產生Iterator物件，stream方法用來產生Stream物件，其本身是循序的概念，上頭定義的filter、map等方法，也都傳回Stream物件，就如同Python中map、filter函式會傳回map、filter物件，Stream在做filter、map等時是惰性求值。iterator傳回迭代器，stream傳回Stream產生器，語義明確，而對於平行處理的支援，則可以使用Collection的parallelStream方法傳回支援平行處理的Stream物件。

將產生器與迭代器的職責區隔開來後就可以明瞭，在stream方法呼叫之後，接下來的操作都是中介操作，若要取得最後成果必然得透過某個方法，就像Python中使用list、set等函式，從產生器中建立list、set物件等；然而與其在Stream上設計一堆toList、toSet、toCollection方法，JDK8定義collect方法接受Collector物件，透過Collector物件來告知collect方法，如何收集產生器中取得的物件並以指定型態傳回。

現在不少程式庫或語言都納入了產生器的實現概念，例如不支援產生器語法的JavaScript有個Lazy.js程式庫，就致力於JavaScript中實現惰性求值，JavaScript是動態語言，因而實現之後在應用上算是簡潔；實際上JavaScript 1.7定義了yield可建立產生器，可惜目前JavaScript的各執行環境在支援上程度不一。無論如何，產生器在現代開發中並非罕見，認識並理解產生器的實現概念，方有助於對相關程式庫或語法的善用。