Bringing Clojure's Persistent Data Structures to Fennel

In 2019, I embarked on a journey to infuse Lua's Fennel with Clojure's charm through a project called fennel-cljlib. This library aimed to replicate a subset of Clojure's core functions and macros, driven by my fondness for Clojure's functional programming style. Over time, I expanded it to include lazy sequences, immutability, and even a testing library inspired by clojure.test and kaocha. Despite its growth, fennel-cljlib remained an experimental passion project, rarely used in serious applications except for fenneldoc, a documentation tool for Fennel libraries.

Recently, I initiated ClojureFnl, a Clojure-to-Fennel compiler built on fennel-cljlib. Though still in its infancy, it can compile most .cljc files, albeit with limited standard library support. A significant hurdle was my initial implementation of immutable data structures, which relied on a slow copy-on-write approach. To advance ClojureFnl, I needed to replace this with more efficient structures.

Clojure's persistent data structures, like Persistent HAMT for hash maps and bit-partitioned tries for vectors, inspired my new library, immutable.fnl. I crafted a Persistent HAMT with native Lua hashing, achieving O(Log16 N) operations, effectively O(1) for practical key counts. While slower than Lua's C-implemented tables, this approach balances performance and immutability.

Benchmarks reveal that operations with Persistent HashMap are slower than Lua tables, but still usable. Transients offer slight performance improvements. On LuaJIT, the performance gap narrows, yet native table operations remain faster. I chose the djb2 algorithm for hashing due to its simplicity and compatibility across Lua versions, despite its collision-prone nature.

Persistent Vectors followed, utilizing direct index-based navigation with a branching factor of 32. This structure offers efficient lookup, update, and pop operations, though still slower than Lua's sequential tables. Transient operations improve performance slightly.

For sorted maps and sets, I implemented a persistent red-black tree using Okasaki's and Germane & Might's algorithms. While slower than Lua tables, the performance is satisfactory given the structural sharing properties.

I also revamped my lazy persistent list implementation, simplifying it to a {:head :tail} structure with three metatables. This change enhances integration with other data structures and supports lazy construction from iterators.

Finally, I introduced a persistent queue, combining a linked list for the front and a persistent vector for the rear. This design ensures efficient append and remove operations, maintaining O(1) complexity.

With these improved data structures, I'm poised to focus on the ClojureFnl compiler itself. The next phase promises to delve deeper into the compiler's development, unless, of course, I get sidetracked by another intriguing idea.