Refactor the compiler to use visitors

[brendanzab]

I poke fun at expression parser/evaluator written in OO style, because really the visitor pattern is just asking for it. But I have a weird, almost morbid fondness for such things written in plain old ANSI C. It’s complicated between me and C don’t ask me about it I’m not ready

— Drn’t Tran Ma 🦖

At the moment we create lots of intermediate data structures between the stages in the compiler, and it would be nice to cut that down!

Using the visitor pattern might make things more efficient by allowing us to fuse various traversals into single passes. Ultimately it might even be a good idea (or even necessary) to push the visitor abstraction back to the nameless library as well. The challenge would be to continue to maintain a nice, readable codebase in the process.

Resources

• Zero-Overhead Tree Processing with the Visitor Pattern
  • Reddit thread featuring yours-truly getting mistaken
  • Rust playground version of the blog post
  • Repository with further implementations of visitors in Rust
• libsyntax/visit.rs (visitor module in Rustc) - uses 'walkers' to allow for default methods to simplify visitor implementations.
• ratel-visitor - has an interesting build! macro
• Serde's Serializer anf Deserializer traits follow this pattern.
• Visitors Unchained - auto-generating visitors for use in variable binding (uses OCaml)
• Miniphases: Compilation using Modular and Efficient Tree Transformations - slightly different approach, applied to compilation in Dotty (the next version of the Scala compiler)

[brendanzab]

Just made a repo with some visitor stuff from the Zero-Overhead blog post: brendanzab/rust-visitors.

[brendanzab]

I also have a (currently broken) branch with some experiments at https://github.com/pikelet-lang/pikelet/tree/visitors

[brendanzab]

One concern is that Moniker (the name-binding library we use) is currently designed in a way that might make this hard to get much value out of. It would be neat to see if we could move Moniker to a model that more looks like what is described in Visitors Unchained and implemented in alphaLib.