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

Show and Tell
#1

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
#2

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

1 Like
#3

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!)

#4

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
#5

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.