Implement a pass to compile Core terms to A-Normal Form

[brendanzab]

So, it seems that the first stage of compilation that we might want to do is to compile to A-Normal Form (ANF). I'm guessing we could start a new module called pikelet::compiler::anf for this. We'll probably want a new set of IR types for this.

A-Normal Form syntactically sequentializes computations, and it partitions expressions into two classes: atomic expressions and complex expressions.

Because it (implicitly) simplifies the internal structure of continuations, it is easier to construct an interpreter for A-Normal Form.

For the same reason, it is easier to generate machine code or construct a static analyzer.

– A-Normalization: Why and How

Type Preservation

I ultimately want each of our passes to be type preserving, so we'll want a new type system and type checker, but it's fine if the initial version leaves this out. The paper Compiling Dependent Types Without Continuations outlines how this can be done for dependent types.

Resources

Don't feel that you need to read and understand all of these in their entirety to tackle this issue, but I've included them with the hope that they might be helpful or interesting! Let me know if there are any more I should add!

• A-Normal Form on Wikipedia
• A-Normalization: Why and How
• The Essence of Compiling with Continuations
• Compiling Dependent Types Without Continuations