There's quite neat lexer and parser generators for Python that can ease the barrier to entry. For example, I've used PLY now and then for very small things. On the non-generated side, lexer creation is largely…
I agree. I've found that, for the languages I'm interesting in compiling (strict functional languages), a custom backend is desirable simply because LLVM isn't well suited for various things you might like to do when…
> Meanwhile, a compiler is an enormously complicated story. I don't intend to downplay the effort involved in creating a large project, but it's evident to me that there's a class of "better C" languages for which LLVM…
There's a neat paper where they implement basic blocks (in a control flow graph) as zippers (https://www.cs.tufts.edu/~nr/pubs/zipcfg.pdf). The neat part is that - due to how the host language works (mutation having the…
I sometimes write C recreationally. The real problem I have with it is that it's overly laborious for the boring parts (e.g. spelling out inductive datatypes). If you imagine that a large amount of writing a compiler…
Nice. I'm always happy to see more accessible resources for compiler writers. --- As an aside: for displaying CFGs on the page, it would be very interesting to emit something somewhat dynamic. SVGs are always a good…
I think it will introduce too many redundant phis, but I've never used it in practice - so I can only speculate. I'm not convinced DCE will clean maximal SSA up substantially. Even the classic Cytron et al algorithm…
On the topic of QBE, I've always felt that someone aiming to do the same scope of project ought to make their IR a syntactic subset of LLVM IR. If you do that, your test suite can involve invoking LLVM for a comparison.…
Typical implementations of Lengauer-Tarjan are often taken verbatim from Andrew Appel's book and involve higher constant factors than alternative algorithms - such as Cooper et al's "engineered" version of the usual…
I have a rather niche theory that many Hindley-Milner type inference tutorials written by Haskellers insist on teaching the error-prone, slow, details of algorithm W because otherwise the authors would need to commit to…
My reading of the article is that the author has chosen to use "ANF" to describe a specific property of their IR that is not unique to ANF, whilst ignoring the fact that ANF (and variants of it) is strongly tied to the…
The author has mentioned ANF a few times but, from what I can tell, the likeness that they emphasise is really just the usual property of operands being atomic. This is a property used in many IRs, but I don't feel it's…
Ah, I thought your username was familiar: you recommended Wadler's approach on a previous HN thread concerning my blog post about Pettersson/Maranget's algorithm (https://news.ycombinator.com/item?id=39241776). Yeah, I…
If we are talking about the context of a compiler, I agree: you should compile pattern matching to decision trees (DAGs), by way of something like Pettersson's algorithm. In my comment, I specified "in an interpreter",…
It is worth noting that lots of applications of unification do not reify explicit substitutions in their implementations. You often see introductory type inference articles (usually focused on Hindley-Milner) use…
Thank you very much! Your website's landing page is very clean.
This is my blog, thanks for posting - never expected to see such engagement.
Agreed, union-find is great. My favourite usage of it in practice is for solving first-order (syntactic) unification problems. Destructive unification by means of rewriting unbound variables to be links to other…
I think the languages you selected in your final remark sum it up for me. If one is truly taken by functional programming, much of their mental model starts to revolve around algebraic (inductively defined) data types…
There's quite neat lexer and parser generators for Python that can ease the barrier to entry. For example, I've used PLY now and then for very small things. On the non-generated side, lexer creation is largely…
I agree. I've found that, for the languages I'm interesting in compiling (strict functional languages), a custom backend is desirable simply because LLVM isn't well suited for various things you might like to do when…
> Meanwhile, a compiler is an enormously complicated story. I don't intend to downplay the effort involved in creating a large project, but it's evident to me that there's a class of "better C" languages for which LLVM…
There's a neat paper where they implement basic blocks (in a control flow graph) as zippers (https://www.cs.tufts.edu/~nr/pubs/zipcfg.pdf). The neat part is that - due to how the host language works (mutation having the…
I sometimes write C recreationally. The real problem I have with it is that it's overly laborious for the boring parts (e.g. spelling out inductive datatypes). If you imagine that a large amount of writing a compiler…
Nice. I'm always happy to see more accessible resources for compiler writers. --- As an aside: for displaying CFGs on the page, it would be very interesting to emit something somewhat dynamic. SVGs are always a good…
I think it will introduce too many redundant phis, but I've never used it in practice - so I can only speculate. I'm not convinced DCE will clean maximal SSA up substantially. Even the classic Cytron et al algorithm…
On the topic of QBE, I've always felt that someone aiming to do the same scope of project ought to make their IR a syntactic subset of LLVM IR. If you do that, your test suite can involve invoking LLVM for a comparison.…
Typical implementations of Lengauer-Tarjan are often taken verbatim from Andrew Appel's book and involve higher constant factors than alternative algorithms - such as Cooper et al's "engineered" version of the usual…
I have a rather niche theory that many Hindley-Milner type inference tutorials written by Haskellers insist on teaching the error-prone, slow, details of algorithm W because otherwise the authors would need to commit to…
My reading of the article is that the author has chosen to use "ANF" to describe a specific property of their IR that is not unique to ANF, whilst ignoring the fact that ANF (and variants of it) is strongly tied to the…
The author has mentioned ANF a few times but, from what I can tell, the likeness that they emphasise is really just the usual property of operands being atomic. This is a property used in many IRs, but I don't feel it's…
Ah, I thought your username was familiar: you recommended Wadler's approach on a previous HN thread concerning my blog post about Pettersson/Maranget's algorithm (https://news.ycombinator.com/item?id=39241776). Yeah, I…
If we are talking about the context of a compiler, I agree: you should compile pattern matching to decision trees (DAGs), by way of something like Pettersson's algorithm. In my comment, I specified "in an interpreter",…
It is worth noting that lots of applications of unification do not reify explicit substitutions in their implementations. You often see introductory type inference articles (usually focused on Hindley-Milner) use…
Thank you very much! Your website's landing page is very clean.
This is my blog, thanks for posting - never expected to see such engagement.
Agreed, union-find is great. My favourite usage of it in practice is for solving first-order (syntactic) unification problems. Destructive unification by means of rewriting unbound variables to be links to other…
I think the languages you selected in your final remark sum it up for me. If one is truly taken by functional programming, much of their mental model starts to revolve around algebraic (inductively defined) data types…