Cool Monday - Functional compilers and atoms

I’ve seen this great talk by Daniel Spiewak on Functional Compilers. He talks about lexical and semantic analysis in particular. First, problems with traditional lexing with scanner. You can only have regular tokens or you have do do some dirty hacking and backtrace the scanner therefore losing linearity. And you can solve this with scannerless parsing

• putting regular expressions into your grammar. In fact this approach seems simpler to me, as the only proper parser I’ve done works this way. But this is not the interesting part.

Semantic analysis

This is where fun kicks in. After you parse the source code into an AST you need to do a bunch of operations on it. Naming, typing(even optimization in later phases). If I want to stay functional(which usually I do) my instinct tells me to do recursive traversal and rewrite the tree. And that’s exactly what my language does. But there is one huge problem. AST is not a tree. It’s huge misnomer. AST is just a spanning tree in the program graph. See, when you add stuff like let expressions, or types(what I’m doing currently) you get problems