4、 表
table是lua的主要——實際上，也是唯一的——資料結構。table不僅在語言中，同時也在語言的實作中扮演着重要角色。effort spent on a good implementation of tables is rewarded in the language,because tables are used for several internal tasks, with no qualms about performance。這有助于保持實作的小巧。相反的，任何其他資料結構的機制的缺乏也為table的高效實作帶來了很大壓力
lua中的table是關聯數組，也就是可以用任何值做索引（除了nil），也可以持有任何值。另外，table是動态的，也就是說當加進資料的時候它們将增長（給迄今不存在的域指派）而移除資料的時候将萎縮（給域賦nil值）。
不像大多數其他腳本語言，lua沒有數組類型。數組被表示為以整數做鍵的table。用table作為數組對于語言是有益的。主要的（益處）顯而易見：lua并不需要操縱表和數組的兩套不同的運算符。另外，程式員不用對兩種實作做出艱難選擇。在lua中實作稀疏數組是輕而易舉的。例如，在perl裡面，如果你嘗試去跑$a[1000000000]=1 這樣的程式，你能跑出個記憶體溢出！（you can run out of memory），因為它觸發了一個10億個元素的數組的建立（譯注，perl的哲學是：去除不必要的限制）。而等價的lua程式 a={[1000000000]=1},（隻是）建立了有一個單獨的項的表（而已）。
直到lua 4.0，table都是作為hash表嚴格地實作：所有的pair都被顯式地儲存。lua5.0引入了一個新算法來優化作為數組的table：它将以整數為鍵的pair不再是存儲鍵而是優化成存儲值在真正的數組中。更精确地說，在lua 5.0中，table被實作為一個混合資料結構：它們包括一個hash部分和一個數組部分。圖2展示了一個有"x"→ 9.3, 1 → 100,2 → 200, 3 → 300對子的表的一種可能結構。注意到數組部分在右邊，并沒有存儲整數的key。這個劃分僅僅是在一個低的實作層次進行的，通路table仍然是透明的，甚至在虛拟機内部（通路table）也是如此。table根據内容自動并且動态地對兩個部分進行适配：數組部分試圖從1到n的相應地存儲值，關聯非整數鍵或者整數鍵超過數組範圍的值被存儲在hash部分。
當一個table需要增長時，lua重新計算hash部分和數組部分的大小。任一部分都可能是空的。重新計算後的數組大小是至少是目前使用的數組部分從1到n的一半情況下的最大n值（原文：the computed size of the array part is the largest n such that at least half the slots between 1 and n are in use）（稀疏數組時避免浪費空間），并至少有一個（元素）處在n/2+1到n的槽中（當n被2整除時，避免n的這樣的數組大小）。計算完大小後，lua建立了“新”的部分并将“舊”的部分的元素重新插入到的“新”的部分。作為一個例子，假設a是一個空表；它的數組部分和hash部分的大小都是0。當我們執行a[1]=v時，這個表需要增長到足夠容納新的鍵。lua将為新的數組部分的大小選擇n=1（帶有一個項1→v）。hash部分仍然保持為空。
這個混合的方案有兩個優點。首先，通路以整數為鍵的值加快了，因為不再需要任何的散列行為。其次，也是最重要的，數組部分占用的記憶體大概是将數組部分存儲在hash部分時的一半，因為key在數組中是隐式的（譯注：也就是數組的下标）而在hash部分卻是顯式的。因而，當一個table被用作數組的時，它表現的就像一個數組，隻要整數鍵是密集。另外，不用為hash部分付出任何記憶體和時間上的懲罰，因為它（譯注：hash部分）甚至都不存在。相反的控制：如果table被用作關聯數組而非一個數組，數組部分可能就是空的。這些記憶體上的節省是比較重要的，因為lua程式經常建立一些小的table，例如table被用來實作對象（object）（譯注，也就是用table來模仿對象，有點類似javascript中的json）。
hash部分采用brent's variation[3]的組合的鍊狀發散表。這些table的主要不變式是如果一個元素沒有在它的主要位置上（也就是hash值的原始位置），則沖突的元素在它自己的主要位置上。換句話說，僅當兩個元素有相同的主要位置（也就是在當時table大小情況下的hash值）時才有沖突的。沒有二級沖突。正因為那樣，這些table的加載因子可以是100%而沒有性能上的損失。這部分不是很明白，附上原文：
the hash part uses a mix of chained scatter table with brent's variation [3].
a main invariant of these tables is that if an element is not in its main position
(i.e., the original position given by its hash value), then the colliding element
is in its own main position. in other words, there are collisions only when two
elements have the same main position (i.e., the same hash values for that table
size). there are no secondary collisions. because of that, the load factor of these
tables can be 100% without performance penalties.
5、函數和閉包
當lua編譯一個函數的時候，它産生一個模型（prototype），包括了函數的虛拟機指令、常量值（數字，字元串字面量等）和一些調試資訊。運作的時候，無論何時lua執行一個function…end表達式，它都建立一個新的閉包。每個閉包都有一個引用指向相應的模型，一個引用指向環境（environment）（一張查找全局變量的表，譯注：指所謂環境就是這樣一張表），和一組用來通路外部local變量的指向upvalue的引用。
詞法範圍以及first-class函數的組合導緻一個關于（如何）通路外部local變量的著名難題。考慮圖3中的例子。當add2被調用的時候，它的函數體（body）部分引用了外部local變量x (函數參數在lua裡是local變量，譯注：x就是所謂的自由變量，這裡形成了閉包)。盡管如此，當add2被調用時，生成add2的函數add已經傳回。如果在棧中生成變量x，（x在棧的）其棧槽将不複存在。（譯注，此處的意思應該是說如果在棧儲存變量x，那麼在調用add2的時候，add函數早已經傳回，x也在add2調用前就不在棧裡頭了，這就是那個著名難題）。
大多數過程語言通過限制詞法範圍（例如python），不提供first-class函數（例如pascal），或者都兩者都采用（例如c,譯注：也就是說c既不把函數當一等公民，也限制詞法範圍）來回避這個問題。函數式語言就沒有那些限制。圍繞着非純粹函數語言比如scheme和ml的研究已經産生了大量的關于閉包的編譯技術的知識（參見[19, 1, 21]）。盡管如此，這些工作并沒有盡力去限制編譯器的複雜性。以優化的scheme編譯器bigloo的控制流分
析階段為例，（它的實作）比lua實作的10倍還大：bigloo 2.6f的cfa子產品源碼有106,350行 vs. 10,155行的lua5.0核心。正如第2部分已經解釋過的（原因），lua需要簡單。
lua使用了一個稱為upvalue的結構來實作閉包。任何外部local變量的通路都是通過一個upvalue間接進行的。upvalue初始指向的是變量存活位置的棧槽（參見圖4的左半部分）。當變量（x）已經離開作用域（譯注，也就是這裡的add函數傳回時），它就遷移到upvalue結構本身一個槽中（參見圖4的右半部分）。因為（對變量的）通路是間接地通過upvalue結構中的一個指針進行的，是以這個遷移對于任何寫或者讀該變量的代碼都是透明的。不像它的内嵌函數（譯注：例子的add2，它是指外部函數add），聲明變量的函數通路該變量就像通路它的local變量一樣：直接到棧。
通過每個變量最多建立一個upvalue結構并且在必要的時候複用它們，可變狀态得以在閉包之間正确地共享。為了保證這一限制，lua維持一個連結清單，裡面是一個棧裡（圖4中的pending vars清單）的所有open upvalue（所謂open upvalue，是指仍然指向棧的upvalue結構）。當lua建立一個新的閉包的時候，它周遊所有的外部local變量。對于每個（外部local）變量，如果它在清單中找到一個open upvalue，那麼它就複用這個upvalue結構。否則，lua就建立一個新的upvalue并将它放傳入連結表。注意到清單搜尋隻是探測了少數幾個節點，因為清單最多包含一個被内嵌函數使用的local變量的項。當一個closed upvalue不再被任何閉包引用的時候，它最後将被當作垃圾并回收。
一個函數允許通路一個不是它的直接外圍函數的外部local變量，隻要（這個local變量）是外部函數的（outer function）。在那種情況下，甚至在閉包被建立的時候，（外部local）變量可能就不在棧裡了。lua使用扁平閉包（flat closures）解決這種情況[5]。通過扁平閉包，一個函數無論何時去通路一個不屬于它的外圍函數的外部變量，這個變量都将進入外圍函數的閉包。進而當一個函數被執行個體化
文章轉自莊周夢蝶 ，原文釋出時間2008-04-07