The joy of recursion, immutable data, & pure functions: Making mazes with JS

Appreciation for the Article and Website

Several users expressed general enjoyment and appreciation for the article and the associated website's design.

• "Nice read, and beautiful website btw." - jefecoon
• "Indeed to both. I enjoyed it greatly. It was well written and on something that I think about someone's but never implemented." - tisdadd
• "Really great writeup." - anarcat

Discussion on Immutable Data Structures and Memoization

A significant portion of the conversation revolved around the use of immutable data structures, particularly in JavaScript, and related concepts like memoization. Opinions varied on the practicalities and potential pitfalls.

• Challenges with Vanilla JS: One user recalled difficulties with Immutable.js in vanilla JavaScript, highlighting the verbosity of methods like thing.set('foo', 42) compared to direct assignment and the potential for confusion between plain objects and immutable Records.
  • "I remember trying to use Immutable.js back in the day. It's probably pretty great with Typescript these days, but I remember it was kinda hell with vanilla JS back then since I'd accidentally do things like assign thing.foo = 42 instead of thing.set('foo', 42) and I'd comb through the code to see why it wouldn't work, and I remember not knowing when I had a JS object or a Record. All things fixed by Typescript, of course." - hombre_fatal
• Success with Immutable.js in a Specific Stack: Another user shared a positive experience using Immutable.js within a React, Redux, and Reselect stack for managing time-series market data. They explained how immutability and reference changes effectively triggered recomputations in memoized selectors and rerenders in React.
  • "It was great working with Redux, Immutable.js which was recommended by Redux, React, and Reselect managing thousands of points of time series streaming market data. The state stayed immutable, and when I needed to break cache I returned a new object for the affected slice in the root state tree. That change, changing the object reference on a leaf of the state tree, triggered Reselect to recompute its memoized selectors, and React / Redux (with shallow equality checks) picked up the new references and rerendered only the impacted components." - dataviz1000 He also mentioned using Ramda for data transformations and being able to precisely track operations with this stack.
• Concerns about Memory Leaks and Garbage Collection: A prominent concern was raised regarding potential memory leaks introduced by memoization techniques, especially in larger-scale applications. The user emphasized the importance of cooperating with the garbage collector and mentioned JavaScript's WeakRef and FinalizationRegistry as potential tools, wondering why a WeakCache isn't more readily available.
  • "I'm slightly horrified by the memory leak that's casually introduced without even a remark as to the potential to cause a problem. I can't tell if I'm more horrified by the cavalier attitude or the fact that JavaScript makes having a global registry the only easy way to use an object of an arbitrary type as a key to Map."
  • "But at the very least, if you're going to memoize immutable values, please do it in a way that allows garbage collection. JavaScript has WeakRef and FinalizationRegistry. (Why it doesn't provide the obvious WeakCache built on those is a mystery, though.)"
  • "The issues won't be visible on a toy example like making mazes a few hundred elements across, but if you use these techniques on real problems, you absolutely need to cooperate with the garbage collector." - chowells
• LRU Cache vs. Weak Maps: A brief debate occurred about whether an LRU (Least Recently Used) cache would be a better alternative to weak maps for memoization. The counter-argument was that LRU caches could evict items still in use, breaking the assumption of referential equality equaling value equality.
  • "Probably better to use an LRU cache rather than weak maps." - b_e_n_t_o_n
  • "No because then you lose the ability to compare objects for equality." - sltkr
  • "Yes. It's using a global variable to canonicalize instances so that reference equality is value equality. An LRU cache will evict things that are still in use, so that the canonicalization process returns a different instance for the same value. (If it doesn't evict anything still in use, it's strictly inferior to just tying to the garbage collector anyway.) This will break the assumption that reference equality is the same as value equality that the rest of the code depends on." - chowells
  • "Oh yeah you're right, I wasn't thinking about the possibility of creating a new point that got evicted but is still hanging around for the comparison..." - b_e_n_t_o_n
  • "Personally I'd design it with Point.Equals(p1, p2) static method and forego using referential equality, then the LRU cache could prevent runaway memory usage but tbh this is all bikesheding for this use case anyways :). The original code is fine." - b_e_n_t_o_n (suggesting an alternative of using explicit equality methods)

The State of Tail Call Optimization (TCO) in JavaScript

The discussion touched upon the absence of Tail Call Optimization (TCO) in JavaScript, with users expressing disappointment and exploring the reasons behind its limited implementation.

• User Disappointment: One user expressed sadness over the lack of TCO in JavaScript and wondered about the implementation difficulties.
  • "I’m still sad that JS doesn’t have tail call optimization. I’ve always wondered why. Is it hard to implement?" - sillysaurusx
• Reasons for Limited TCO: Several reasons were cited for the lack of widespread TCO, including developer addiction to automatic stack traces, potential performance hits for all users, and disagreements among browser vendors regarding implicit versus explicit TCO.
  • "People are too addicted to automatic stack traces for mainstream languages to optimize away stack frames." - chowells
  • "If my memory serves right, the browser vendors couldn't agree on the implementation. On the one hand, allowing any function to be eligible for TCO means that the developer won't know if the code was optimized or not. A trivial change can easily convert a fast function to one that blows the stack. Additionally, every function created- or at least every named function- would need to be analyzed, causing a performance hit for everyone, even those who never write a recursive function in their lives. On the hand, some argued that TCO eligibility should be explicitly opt-in with some sort of keyword or annotation. If a function so annotated did not end up being a valid target for TCO, the script would not compile, similar to a syntax error. This is an even more harsh failure mode than the implicit version, but would have been easier to identify. I vaguely recall chrome devs generally being in favor of explicit annotations, and Safari implicit. I could be completely wrong on this, and I don't think anyone was particularly enthused about the trade-offs either way." - zdragnar
• Partial Implementation: It was noted that TCO is supported in JavaScriptCore (used by Safari and Bun), though not universally across all browsers.
  • "It does if you use JavaScriptCore (Safari, other Webkit browsers, Bun)." - Jtsummers
  • "TCO is actually in the ES6 spec but browser vendors (except Safari) haven't implemented it due to concerns about debugging (stack traces become less useful) and security implications with stack inspection." - ethan_smith

Functional Programming and Related Resources

The discussion briefly touched on functional programming concepts and shared resources for those interested.

• Juxtaposition of Functional and Imperative Styles: One user found it amusing that an article about a functional algorithm began with an imperative explanation.
  • "Kind of amusing and maybe telling that this article about implementing an algorithm functionally begins by explaining it in an iterative, mutational fashion." - wk_end
• Related Content: Users shared links to related content, including a blog post on generating mazes in Haskell using inductive graphs and a book on functional programming with JavaScript.
  • "If you enjoyed that, I have a blog post on generating mazes in Haskell (from over a decade ago!). The algorithm is very similar, but the code is written using "inductive graphs" and the post is really more of an intro to working with graphs in a purely functional style." - tikhonj
  • "A Skeptic’s Guide To Functional Programming With JavaScript" "I’d recommend it for functional-curious JS devs like myself." - joshfarrant