擴充 For 和 Next

wiki

[!] 發布公告：以下程式碼適用於較舊版本的 Lua，Lua 4。在 Lua 5 中無法正常執行。

適用於 Lua 4.0 的實驗性修補程式

Lua API 可輕易整合「外部」物件，包括外部映射，但未提供用於反覆運算的工具程式。也就是說透過定義 gettable 和 settable 標籤方法，可行地將索引的外部物件完全整合到 Lua 環境中，但無法延伸用於 for k,v in foregin_map 或 k,v = next(foregin_map, k)。這兩種結構都相當實用。

我也對擴充 next 到「產生器」函式的可能性感到好奇。產生器函式的運作方式與 Lua 的 next 函式庫函式完全相同；給定反覆運算狀態，它會產生下一個反覆運算狀態和值。舉具體範例來說，我可能會定義產生器為字串的閉包，因此我可以說

keywords = words "do else elseif end for if in repeat unless while"
for i, v in keywords do
   dict[v] = (dict[v] or 0) + 1
end

我認為相當典雅。

修補程式的設計十分簡潔，所以我已將它發布在檔案區，給可能想要使用它的使用者。

檔案

• 檔案：wiki_insecure/users/rici/next.patch即為修補程式本身

• 檔案：wiki_insecure/users/rici/test.lua為一個簡單的時間測試

• 檔案：wiki_insecure/users/rici/results.test.lua.txt為對 vanilla Lua 的測試結果

• 檔案：wiki_insecure/users/rici/results.test.nlua.txt為對修補後 Lua 的測試結果

• 檔案：wiki_insecure/users/rici/test2.lua展示了使用修補程式以及時間測試的部分方法

• 檔案：wiki_insecure/users/rici/results.test2.nlua.txt為對修補後 Lua 的測試結果（對未修補的 Lua 無效）

用法

修補程式提供了一個新的標籤方法，「next」，由 for k,v in object do end 結構來呼叫；在 next 函式庫函式中；以及在 lua_next API 中。依據 Lua 的風格，提供了一個新的 rawnext 函式庫函式和 lua_rawnext API，避免使用標籤方法。這些函式的工作原理與表格相同，但與其傳回和使用「金鑰」，改用「反覆運算狀態」。如果物件也定義了 gettable 和 settable 標籤方法，可能會明智地安排金鑰和反覆運算狀態成為同一個東西；但對於純反覆運算物件，反覆運算狀態可為任何東西，前提是 nil 同時表示反覆運算的開頭和結尾。事實上，反覆運算時無需保持不同。

另外，修補後的結構可對函數進行反覆運算，而非使用「next」標籤方法的表格或物件；函數使用單一引數進行呼叫，也就是反覆運算狀態，且必須傳回兩個引數，其中一個是下一個反覆運算狀態，另一個則是關聯值。對於 next 和 lua_next 來說，這在表面上並無實際價值，但它可避免需要判斷被反覆運算的內容是函式還是物件。

範例

上面描述的 words 產生器定義如下

function words(str)
  return
    function(k)
      local _, k, v = strfind(%str, "([%w]+)", (k or 0) + 1)
      return k,v
    end
end

如你所見，它保留引數作為封閉，並使用每個字詞中最後一個字元的索引作為反覆運算狀態。

同樣，我可以定義

function wordsInFile(file)
  return
    function(k)
      k = read(%file, "*w")
      return k, k
    end
end

在此情況下，反覆運算狀態在反覆運算過程中基本上沒有意義；它只用於宣告終止。顯然，可執行更精密的實作。

篩選器和轉換器

篩選器和轉換器採用產生器，並傳回另一個產生器。一個轉換器的簡單範例是

function toupper(gen)
  return
    function(k)
      local v
      k, v = next(%gen, k)
      if k then return k, strupper(v) end
    end
end

這可以概括為

function gmap(fn, gen)
  return function(k)
    local v
    k, v = next(%gen, k)
    return k, k and %fn(v)
  end
end

現在，我可以撰寫類似下列內容

for i, v in toupper(words(str)) do
  -- something
end

篩選器有點像轉換器，但並非一對一。範例篩選器類似於 Perl grep 函數

-- given a predicate and a generator, generate only those
-- values for which the predicate returns true
function gfilter(fn, gen)
  return function(k)
    local v
    k, v = next(%gen, k)
    while k do
      if %fn(v) then return k, v end
      k, v = next(%gen, k)
    end
  end
end

我希望這些能讓你略知可行性。

實作筆記

修補程序的大部分在 lvm.c 中。這裡，我修改作業碼 LFORPREP 和 LFORLOOP 以使用新的 vm 函數 luaV_next，其中實作對 ttype 和標籤方法的切換。next 和 lua_next 也修改為使用此相同函數，以產生（我希望）一致的結果。

這會稍微降低 for 迴圈的速度，因為每次迴圈中都會執行測試。在裝有 128MB RAM、執行 FreeBSD 3.2 的 P3/866 上執行時序測試（我開發的機器），顯示一個非常基本的 for 迴圈在修補後速度慢了約 10%。（但另一方面，next 快了約 4%。）我有一個有點更複雜的修補程序，它會快取堆疊中的標籤方法，導致速度只降低 7%，但我目前對它還不滿意，不足以發布它。我相信 4.1alpha 架構更適合這個問題，而且我目前正在深入了解 4.1alpha VM，希望可以解決這個問題。

在 for 迴圈期間，解析器或堆疊配置並未進行任何變更，因此，修補後的 Lua 理應具有二進位相容性；它只提供新增的功能。不過，我無法針對這項宣告提供擔保。

未來方向

我認為所有這些都只是一次有趣的實驗。我認為修補程序提供的範例程式碼展現了新結構的表達能力，除了能夠定義可反覆運算的使用者資料之外。

然而，迭代表態與金鑰之間的混淆始終困擾著我。我注意到在 4.1 alpha 版本中，for 清單實作時同時包含迭代表態和一組金鑰，我認為這樣較為合理（理應會稍微快一些）；我對擴充 for 迴圈與 next 函數庫語意的可能性感興趣，希望可以允許如此。雖然金鑰通常可用作迭代表態，但並非總是這麼方便（如 words 範例所示）。

在 for 迴圈期間隱藏迭代表態具有誘惑力，但會降低彈性。使用 for 迴圈和產生器而非傳統 map 函數的主要優點，在於可以放棄或修改迭代表態。也就是說，至少應該可以在 for 迴圈內部使用 next 來略過元素。在某些狀況中，也可以透過指定迭代表態變數來重新啟動迭代表態。

顯然地，產生器有許多類別，需要適當地記載說明。它們可能是

• 可重新啟動，意即可以重複使用先前產生的迭代表態

• 在修改下仍維持穩定，意即可以在迭代表態期間修改所迭代的物件

• ...

同時，金鑰->值模型有點僵硬。如果向量的話，金鑰可能對我沒什麼用；如果是資料庫的話，我可能會用會傳回多個值的產生器。理論上，可以透過將 for 的語法擴充為類似 for name_list in exp1 [, exp1] ... 的內容來解決此問題（第二個 exp1 會是起點迭代表態，預設為 nil）。

歡迎提供任何想法；你可以透過 rlake(at)oxfam.org.pe 與我聯繫。或直接在此處或寄信至郵寄清單。

我建議使用選項「-urN」進行修補，並在修補程式中加入測試程式。--JohnBelmonte