[Final Project Idea] Implement a New Language Backend for Co-dfns

[arcfide]

• Project: Co-dfns
• Size: long-350h
• Difficulty Level: Hard
• Project URL: https://github.com/Co-dfns/Co-dfns
• Potential Mentors: Aaron Hsu (@arcfide), Max Sun (@MaxCan-Code)
• Discussions: [Final Project Idea] Implement a New Language Backend for Co-dfns #12

Description:

Co-dfns is an APL compiler with a novel architecture that is designed to support compiling APL to multiple different backend languages.
The goal of this project is to add a new backend to Co-dfns. The choice of backend target language is open to the implementor. The current backend is implemented in C.

Possible languages include any language of the mentee's choice, but a non-exhaustive list could be: JS, Java, Python, WASM, X86-64 Assembly, SML, OCaml, Zig, Rust, Go, Lua, CUDA, or any language of your choice

Expected outcomes:

New backend language support for Co-dfns. 

Technologies involved:

APL, C, Co-dfns, and the language and tooling of the mentee's choice.

[sloorush]

Thank you @arcfide. Can you also write what all languages the backends are already worked on or completed and what would you like to see as examples? (obviously all languages of mentee's choices will be considered)

[arcfide]

I've updated the description, but I find listing the possible language choices somewhat unnecessary.

[GlowingScrewdriver]

I have some experience with compilers, and I'm comfortable programming in C, but I haven't used APL or any of its variants. Is this project a far shot for me?

"Some experience with compilers" is vague, yes, but I'm mainly wondering about whether not knowing APL is a concern.

EDIT: Of course, I'm open to learning the language over the next few weeks.

[arcfide]

APL is quite easy to learn how to read at a "novice" level, and you'll have support for learning how the Co-dfns architecture and code is laid out, so lack of APL knowledge is unlikely to be a severe hinderance, but you should expect to "learn on the job" as it were. However, the more things you have to learn on the job, the harder it will be. Fortunately, making a backend only means you can be mostly "isolated" from much of the details of the other elements of the compiler system, so this also gives you a bit of an advantage in terms of not needing to know too much.

The major ideas that will help you get a handle on things as a whole are:

• The Nanopass style of compiler construction to understand how all the compiler pieces fit together and how new components are designed
• APL's semantics to both read Co-dfns and understand the compilation targets
• C programming to understand the semantic mapping between APL concepts and their reification in the C runtime
• Understanding the target language you're writing a runtime for so that you can understand the performance and usability ramifications of your runtime design decisions
• The Co-dfns data structure philosophy and how to work with this data so that you can understand the correct way to interact with the AST when generating the target code

Overall, a background in functional compiler design will be a big help, but monolithic compiler construction less so (but not useless by a long shot). The more of the above concepts you come to this with a deep understanding, the easier it will be, but at least in theory you could learn all of this on the job. Depending on the language, you'll be able to get the least support with your target language, so a good understanding of the target language you want to support is probably the most important thing to know ahead of time and the hardest thing to learn on the job (since we won't be able to help as much with this part).

[GlowingScrewdriver]

Understood. Thank you for the detailed explanation! I'll give it some serious thought and exploration.

[arcfide]

Thanks for your interest, and I hope you'll have some fun either way!

[arcfide]

If you'd like, you can explore the publications on Co-dfns to get some idea of how we approach things: https://github.com/Co-dfns/Co-dfns#publications . This might help you decide.

[namgyaaal]

I have been fascinated by Co-dfns for a bit. While I doubt this is something I could contribute to anytime soon, I do have some questions pertaining to it, adding onto previous post.
(1) How much background knowledge would be required in compilers to be able to tackle this for someone who wrote a basic OCaml interpreter in OCaml. Is it worth giving "Compilers: Principles, Techniques, and Tools" a read through before going through your thesis?
(2) I am unsure what it means fully for it to be self-hosted in the GPU. Is the subset of APL that Co-dfns targets viable to produce SPIR-V bytecode from APL?

Thank you.

[arcfide]

Implementing a new backend will not likely benefit from reading a traditional compiler manual. You'll get far more value out of reading the existing backend and understanding how it works and what the output IR from the Co-dfns compiler looks like.

The self-hosting goal for Co-dfns is that the entire APL language that is needed to write Co-dfns can be compiled for an executed in a GPU-first fashion. In the thesis, this was done by demonstrating that there exists a translation from the compiler passes in the thesis to a GPU version of those same passes. In the thesis, this was done by "hand compilation" of the passes. At this point, those original passes likely already "work" on the GPU with Co-dfns able to compile them, but we have not done this because our focus is on self-hosting the current version of the compiler.

To self-host the current version of the compiler on the GPU, we want to be able to compile Co-dfns using Co-dfns with the GPU backend and have the resulting code execute with reasonable efficiency on the GPU. We are very close to this goal for the parser and core compiler, but further out on this with the code generator, because the code generator either needs to be redesigned a little bit to flatten out the generation passes, or the compiler itself needs to better implement an optimization for the core nested data parallelism in the code generator.

At the moment, our emphasis is on enhancing the parser for static analysis and improving the existing backend performance to get parity or exceed the performance that we were able to achieve with v4 of the compiler. Once we achieve these goals, we intend to rapidly expand the set of backends available for the compiler, and that may provide some aid to those who wish to add new backends. Unfortunately, we do not currently have a timeline or estimate for when this work on new backends will start, and nothing prevents a motivated individual from beginning work on a new backend themselves before we have added a second backend to the official releases.

I hope this helps!