Redesign Pijama's IRs

[pvdrz]

In this moment we have two IRs based on the lambda calculus which have been a great way to start because the typing rules are easy and you can express a lot of intricate programs with them without changing its structure.

However, there are some problems with those IRs:

• One is performance, as mentioned in https://github.com/christianpoveda/pijama/issues/50. Evaluation time grows fast with the number of arguments of a function.
• Other has to do with lazy evaluation. We are using a call-by-name evaluation strategy. Which means this code is evaluated as following:

  (fn(x:Int) do x + x end) (1 + 1)
  -> (1 + 1) + (1 + 1)
  -> 2 + (1 + 1)
  -> 2 + 2
  -> 4

  i.e., (1 + 1) is evaluated twice even though they are the same expression. We should be able to "cache" that evaluations like Haskell and its "call-by-need" does.

• The lower level representation uses de Bruijn indices to represent variables. Which takes care of scoping and shadowing nicely but is hard to debug.
• Recursive functions are represented using the fixed-point operator which introduces a significant overhead for recursion

I like to propose we move to more traditional IR based in one of the following:

• static single assignment form: Like rust's MIR, LLVM-IR, the cranelift IR.
• continuation passing style form: which is a superset of SSA and is better suited for functional languages.
• Something like the spineless tagless G machine language: This is one of Haskell's IR.

[DarkDrek]

For me the continuation passing style form is at least conceptional the easiest to understand and at the same time a bit interesting. As for the others the static single assignment form is also easy to understand and the spineless tagless G machine is something I can't comment on but it seems to advanced.

[pvdrz]

I've been checking how Haskell works as we share certain features such as currying with it. So the idea is that there are two IRs

• Core (equiv to our MIR): Which is a (explicitly-typed) lambda calculus, some optimizations such as inlining happen here.
• STG (equiv to our LIR): Which is the one that actually is executed / compiled to machine code. What I like about that model is that the two IRs are really different because they are suited for different purposes.

In our case LIR is like MIR but with less syntax. Which makes the lowering easy, but executing LIR is almost as slow as executing MIR. The only advantage is that there are no naming issues because LIR has no names at all.

I think we can try to do some fixes to our MIR but keep it almost untouched. And focus on changing LIR by something that we can execute easily. What do you think?

I haven't found enough info about CPS even though I like the model. If you happen to have any good sources to see how it works in a compiler I'd love to give it a look