Qi Compiler Sync Aug 12 2022

Compiler Goals and Approaches

Qi Compiler Sync Aug 12 2022

Adjacent meetings: Previous [None] | Up | Next

Goals for the compiler

How much does performance matter for the usecases Qi is concerned with? Probably the important thing is just to have all the pieces in place so that optimizations could be written over time, i.e. the scaffolding should be there. Initially, these may just restore performance to pre-core-language / pre-compiler levels.

Core language

The compiler will be engaged in generating optimized Racket code from a minimal core (Qi) language. The kinds of optimizations we are interested in doing will inform the choice of core language. For instance, if a compiler is going to do function inlining, the core language needs to properly distinguish functions from other forms so that the compiler can reliably identify them. We ideally want to have a small core language to make writing optimizations easier.

Approaches to the Compiler

1. Few intermediate representations (IRs)
2. Many IRs - e.g. one IR for each class of optimization ("Nanopass")

"Theory of optimization"

• Qi is a general purpose language, so arguably, there is not a lot of specialized "domain specific" information we could leverage to write optimizations.
• On the other hand, some patterns are idiomatic in Qi while others aren't (e.g. mutation is unidiomatic and even highly awkward). We could potentially take advantage of these by doubling down on supporting / optimizing idiomatic patterns, while being willing to downgrade unidiomatic patterns to second-class handling.

Optimizations

Qi doesn't distinguish variable argument flows from known-arity flows. That is, there are cases where analysis could infer the arity, but flows don't encode it. This is fine from a language standpoint, but from the compiler standpoint, it is likely that we will want to handle these two cases distinctly. For instance, there could be an IR that focuses on arity-related optimization.

• In general for the arity optimizations, we could build a table of arities of built-in Racket functions which could help in inferring arity of flows.
• "Avoiding intermediate collections" -- we could avoid intermediate constructions in map-filter-fold functional pipelines (like Clojure transducers). But, things to keep in mind:
  • These are fundamentally not algorithmic complexity optimizations (e.g. they may go from 3N passes to N passes) but instead memory-efficiency optimizations. In some cases avoiding intermediate collections may end up being less memory efficient due to the use of recently cached data in a particular stage of the pipeline, which might end up becoming uncached if a subsequent stage is also memory-intensive. That is, for memory-intensive pipeline stages, eliminating them could end up being worse.
  • Racket's compiler doesn't do "effect analysis" -- that is, there's no information available on whether certain functions entail side effects or not. It may therefore be challenging to reliably eliminate pipeline stages. One (not especially great) option is to introduce a safe~> form that advertises that it will eliminate pipeline stages, leaving it to the user to ensure there are no side effects.
  • In cases where the individual operations on the data are expensive (e.g. database lookups, or computationally intensive tasks like chemical reaction modeling or simulations), there will not be a perceivable benefit to eliminating pipeline stages.

Binding Spec DSL

This will generate an expander taking care of hygiene, good error messages, etc. when you give it a grammar for your language in terms of core forms. At the moment it doesn't support optional cases in the core forms, but that is a planned improvement. We could integrate this and then iterate on it over time as bugs / needed features become apparent.

Other things that may be worth looking into

• Esterel is a synchronous reactive language -- reputedly hard to compile -- but loops in Qi might be related to it and could be worth seeing how they're handled in that language
• "Geometry of interaction" is a way of understanding lambda calculus computations in terms of graph rewriting. Since Qi flows are DAGs, maybe thinking about compilation as a graph-rewriting process in this sense would be worthwhile

Next Steps

• Have a better idea of a theory of optimization
• Try out a compiler approach - e.g. write one optimization as a start.
• Necessary changes to be able to incorporate binding spec

Participants

Michael, Nia, Sid