Hacker News
We built a regex engine in F# that outperforms industrial standards by supporting full boolean operators and context-aware lookarounds while maintaining linear-time complexity. The project, published at POPL 2025, leverages Brzozowski derivatives and minterm compression to achieve unprecedented performance and security against ReDoS.
AI 生成摘要
我們用 F# 打造了一個正規表達式引擎，不僅效能超越工業標準，還在維持線性時間複雜度的同時，支援了完整的布林運算子與上下文感知環視功能。這項研究已發表於 POPL 2025，我們利用 Brzozowski 導數與最小項壓縮技術，實現了前所未有的效能並解決了 ReDoS 安全威脅。
RE# 是一款由 F# 開發的新型正規表達式（Regex）引擎，其研究成果已發表於 POPL 2025 國際會議。該引擎的核心基於 Brzozowski 導數理論，不僅在效能上超越了現有的 .NET 內建引擎與多款工業級工具，更完整支援了交集與補數等布林運算子，並在維持線性時間複雜度的前提下實現了上下文感知的環視功能。
在 Hacker News 的討論中，社群對於 RE# 展現出的技術突破感到驚艷，特別是針對長期以來被視為理論挑戰的布林運算子支援。參與者指出，雖然正規語言在理論上對補數運算具有封閉性，但在缺乏顯式運算子的情況下，手寫這類邏輯極其困難且容易出錯。RE# 成功將這些「被遺忘的理論」轉化為高效能的實作，讓開發者能以更具模組化的方式撰寫正規表達式，避免產生難以維護的複雜語法。
然而，效能數據的優異表現也引發了部分資深開發者的謹慎懷疑。有評論認為這些數據「好到令人難以置信」，並期待看到更多獨立的基準測試。此外，由於該引擎目前主要以 F# 實作並透過 NuGet 發布，非 .NET 生態系的開發者表達了對跨平台支援的渴望，雖然作者提到有 Rust 版本的原生庫，但社群成員反映目前尚難以找到相關的公開連結。
討論的另一個焦點集中在開發語言 F# 本身。許多留言者對 F# 在高效能系統開發中的表現給予高度評價，認為其繼承自 ML 家族的強大類型系統，讓開發者在享受垃圾回收（GC）便利性的同時，能寫出不遜於 Rust 的高效程式碼。不過，這也引發了關於微軟對 F# 支援力度的爭論。部分觀點認為 F# 若非隸屬於 .NET 生態系，或許能像 Haskell 或 OCaml 一樣獲得更純粹的學術與社群關注；但也有反對意見指出，正是因為微軟研究院長期的投入與 .NET 的整合，才讓 F# 得以在工業界佔有一席之地。
此外，專業領域的討論也延伸到了程式語言理論。有評論者分享了正規表達式導數與延續傳遞風格（CPS）之間的概念聯繫，認為導數本質上就是處理完一個字元後的「後續動作」。這種理論與實務的結合，被社群視為計算機科學領域中將古老論文重新賦予現代價值的典範。
在討論串中，社群成員分享了其他相關的技術資源供參考。針對正規表達式導數的實作，有開發者提供了基於 Haskell 的 lregex 專案連結。此外，作者也提供了一個互動式 Web 應用程式，讓使用者能直接在瀏覽器中測試 RE# 的功能並觀察其如何處理複雜的布林運算與環視邏輯。對於對函數式編程歷史感興趣的讀者，留言中也提到了關於 Haskell 研究者與工業界應用之間關係的經典討論文章。