為了感受身為人類的感覺,我會在週末手寫程式碼。
我最新的挑戰?用 512 或 1024 位元組的純 C 程式碼打造一個 Python 直譯器。哦,而且不能使用巨集技巧或函式庫的胡鬧。
我大概無法將整個 Python 語言塞進一個只有 1024 位元組程式碼的直譯器裡。那麼,我能塞進什麼看起來像 Python 的東西呢?
這個 fizzbuzz 程式看起來明顯是 Python。它有 `def`、冒號、縮排,以及 if 語句沒有括號。在我看來,這就是 Python!當然,我還必須加入一些額外的限制,而不僅僅是語法子集。
我寫過許多遞迴下降解析器,這個能有多大不同?Python 的子集應該和我實作過的其他語言相似。
我從我能想到的最基本程式碼開始:`1 + 2`
然後我讓它更複雜:`x = 1 + 2 * 3`
接著我甚至加入了語句:`if x > y: z = 3`
太好了,我做了一個計算機……這不是我這個挑戰的本意!我已經超出限制了。那時我退一步,列出了看起來像 Python 的元素,同時也意識到我的程式碼高爾夫技巧不足以讓它塞進 512 位元組。
也許我能在 1024 位元組內做到?首先,讓它能運作,然後再讓它變小。
實際的 CPython 實作會將 Python 原始碼分詞,解析成抽象語法樹,進行一些分析和最佳化,產生位元組碼,然後解釋位元組碼。
狀態保存在少數全域變數中。它使用一個固定長度的陣列(目前是 999 個)來存放原始 Python 程式碼。變數和函式名稱都包含在單一陣列中。
運算式像其他遞迴下降解析器一樣處理,並在過程中執行。例如:
沒有任何形式的錯誤處理!它基於程式碼的正確性做了很多假設。例如,它假設關鍵字都拼寫正確。
它還假設了語彙單元的邊界是正確的,並移除了大部分空白字元。它保留了縮排和字串字面值中的空格。
它僅限於單一小寫字母的變數名稱,這允許我們直接進行符號表查找:
執行程式碼區塊的函式會一直執行到縮排減少為止。當縮排減少時,它會返回,由呼叫者處理下一行。因此,它利用 C 程式的呼叫堆疊來處理遞迴。
由於沒有編譯任何東西,迴圈是透過向後跳轉並在每次迭代時重新解析原始碼來運作的。`while` 和 `for` 迴圈都會追蹤條件運算式的位置。在執行完迴體後,它會跳回到該位置並繼續解析。
函式也以相同的方式運作。在解析定義時,符號表會記住函式在原始碼中的位置。然後在解析函式呼叫時,會儲存呼叫者的位置,解析器會跳到函式體,執行函式體,並在到達結尾時恢復呼叫者的位置。
即使沒有中間表示法,我們所能做到的事情也相當優美!直譯器維護的狀態也非常少。
我沒有怎麼做程式碼高爾夫。修剪變數名稱和空白字元是很明顯的,但我該如何節省那些大位元組呢?
存在一個古老、被遺忘的網站叫做 Stack Overflow,過去的程式碼魔法師們在那裡分享他們的知識。我從「Tips for golfing in C」學到了很多想法。
由於規則只存在於你的想像中,我確實必須有創意。其中一些技巧依賴於 GNU C89 的特定「特性」。這不是胡鬧!這是慣用的技巧。
例如,我之前展示的 `parse_sum(void)` 函式被高爾夫化為 `e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}`。它使用了 ASCII 值來節省幾個位元組。
在完成所有工作後,高爾夫化後的版本是 1024 位元組!
最終可讀的版本超過 4800 位元組。我原本還有更多功能,但為了讓它能塞進去,我一直刪減。比較運算式是下一個被刪減的對象,因為它們佔用了大量位元組,而且沒有它們,真值判斷仍然有效:`if n%15:`。
如果我只關心讓 fizzbuzz 能運作,我認為我可以做到低於 800 位元組!可能還有其他高爾夫技巧。
這是所有輝煌的高爾夫化原始碼:
最終,我能夠實作這些功能:
我認為我短期內不會再參加任何程式碼高爾夫挑戰了。這個過程非常繁瑣,需要在高爾夫化進行中的版本和原始版本之間來回切換,試圖理解我兩分鐘前才做了什麼更改。兩個版本都在 GitHub 上。
現在輪到你了。你的 1024 位元組 Python 是什麼樣子的?