# I would like to share a compiler I am building for fun that uses ANF/monadic form as an intermediate language

I’m building a compiler to pass the time and it uses ANF/monadic normal form as an intermediate language. So far it can compile `if True then print(2); else print(3);;` to correct assembly that gets run with gcc. Thats the only one I have tested.

heres the code

But the instruction selection module generates code for expressions such as:
`let x = 0;; while x < 4;: if x < 3; then print(x);; let x = x + 1;; else print(3);;` and it can generate ast for tuples such as `(4 ; 5 ; 6)`.

I know the syntax is ugly but i wanted to skip the parsing phase as fast i could.

It uses the happy parser generator.

If you take a look at the code and if you want and have time, I will appreciate some feedback. This is my second main project in haskell so I am not sure if I wrote Haskell in a good style. I had some compiler experience with common lisp but i think haskell is better for writing compilers. thanks. have a nice day

7 Likes

Nice! I happen to be doing a very similar thing at the moment.
Enjoy the journey!

1 Like

Not a term I’m familiar with - can you provide a link or description? (I worked on a compiler to a “monadic intermediate language”, so this piqued my interest!)

The reason it is also called monadic normal form is due to the similarity of do-notation, e.g.:

``````do
y <- do
x <- m
f x
g y

==

do
x <- m
y <- f x
g y
``````

(taken from Monad laws in terms of do notation : haskell, thanks @tomjaguarpaw)

That is one of the transformations which you also need to do when converting expressions to A-normal form.

Or one of the examples on that wiki page:

``````f(g(x),h(y))
``````

is written in ANF as:

``````let v0 = g(x) in
let v1 = h(y) in
f(v0,v1)
``````

And in do-notation:

``````do
v0 <- g x
v1 <- h y
f v0 v1
``````

You can take a look at this article by Dr. Might, a computer science professor: A-Normalization: Why and How (with code) and here is the original paper https://dl.acm.org/doi/pdf/10.1145/155090.155113. for an introduction to monadic normal form which is essentially ANF you can take a look at this book GitHub - IUCompilerCourse/Essentials-of-Compilation: A book about compiling Racket and Python to x86-64 assembly. Once in the github account you need to navigate to the releases and either download a pdf of the racket version or the python version.