Qi Compiler Sync Dec 8 2023
Qi Compiler Sync Dec 8 2023
Adjacent meetings: Previous | Up | Next
We began with a demo by Dominik of the latest developments in the Racket RogueLike Library. We discussed the compiler extension mechanisms we've talked about recently and seemed to converge on the necessity of "compiler macros" due to a "diamond problem" in composing languages, which may yet have a satisfactory resolution. We discussed known backwards incompatibilities in this release and the need to notify the community of them. We reviewed the intentional use of side effects in Qi. We discussed having more rigorous benchmarks in the future, the need for more developer documentation to cover the compiler work, and some apparent false negatives in the current test coverage report. Finally, we agreed that the compiler work was ready for code review.
Last week, we covered a lot of ground taking stock of everything in flight and all the things remaining to be done for release, which we're targeting for Dec 22.
In the interim, some work was merged:
The last time we saw the Racket RogueLike Library, Dominik had shown how flow-oriented actors (implemented in Actor Basic) could model a dynamic maze with many distinct (e.g. 2D, 3D) representations without any use of mutable state. He noted this time that the use of continuations in Actor Basic is "sound but sometimes unintuitive." It's something we will need to reckon with when we consider the design of continuations as they might appear in Qi. But in general, Actor Basic is able to make use of them to provide "the simplicity of imperative programming" while retaining the benefits of functional programming. Dominik showed some new additions to RRLL, including monsters (what we had seen long ago as "walkers" in a 2D maze) and fireballs!
A frequent topic of discussion in recent times has been ways to extend the compiler ("compiler macros" and "towers of languages"), and why we might want to do that (to keep the core Qi library lean). We seemed to conclude previously that the tower of languages approach was cleaner and more robust, but upon further discussion this time, we realized that it implies that we would need to use a custom interface macro for each such high level language and it may not be easy to mix them. For instance, there would be one interface macro for the language that would include deforestation of interfaces in racket/list. And then there would be a different one for, say, a dataframe library, a database library, and so on. Presumably, each of these macros would themselves be named flow, overriding (and delegating to) the lower level Qi interface macro. But what if we wanted to use both list as well as dataframe optimizations? Mixing the use of these interface macros could get cumbersome.
We could imagine constructing a composed macro that includes both languages. The question is, how does one construct such a macro? Could it be done purely on the client side, without deconstructing the respective sublanguages being composed? That would mean that the composed macro would need to duplicate some of the pattern matching already found in the sublanguages, to decide the cases in which to delegate to either. But in this case, we run into a kind of "diamond inheritance" problem. If two sublanguages provide optimizations for the same expression, how to decide which one to use?
A further issue with this approach is that each of the "higher level" languages is expected to produce Racket code which is a use of the macro of the lower-level language, and does not retain any "context" of composition. In other words, the lower-level language is hardcoded and cannot be varied, and it does not get any information that the expansion is happening within the context of composition with this higher level language, information which might be useful or necessary.
So we once again returned to the idea that some form of "compiler macros" are needed, which allow the Qi language itself to be extended (rather than add another language on top), including being able to insert custom compiler passes, and to write such passes in isolation without needing to cooperate with authors of other such extensions. Still, this option (assuming it is possible of course), while offering the benefits we seek (keeping the Qi core lean, while allowing compiler extension), does appear to have some drawbacks that were noted before.
Another option could be to devise a new language composition scheme in terms of a shared intermediate representation within a context of composition (i.e. not the "bottom level," Racket) for use across Qi dialects, where languages (represented by interface macros) may be composed in whatever order we indicate. It needn't be commutative, the same way that (~> sqr add1) isn't the same as (~> add1 sqr), and thus avoids the "diamond" problem by leaving it to users / macro authors to decide how they want to compose the languages. So it could be something like:
flow* := (lang-compose~> list:flow dataframe:flow db:flow)
This would first compile a source expression using the qi/list language (assuming list:flow refers to the flow macro exported by qi/list), not to Racket, but instead, to the Core Qi representation just prior to the code generation step. That is, this compiled representation would include optimized Qi expressions and escaped Racket -- it would resemble the expansion output except that optimizations have already been applied. If any further language-specific tags have been added (e.g. in order to create a language-specific intermediate representation that is not Core Qi, including arity annotations or whatever else), they should have been removed by this point to restore the presumptive output code to Core Qi (including esc).
Then, this output would be passed to the qi/dataframe language, which would repeat the same process, followed by the qi/db language. Finally, the composed language macro would perform the code generation step (just once, at the end).
One nuance is, if the qi/df language includes a project form, while qi/list does not, then in the above composition, an expression like this:
(~> ... (project f) ...)
... would get compiled by qi/list to
(... (esc (project f)) ...)
So when the dataframe language gets this as input, it would need to unwrap the esc in some cases to "promote" these forms back into the domain of the language, instead of being an escaped expression that would not be subject to optimization. This would likely need to happen at the very beginning, either right before or after normalization, or maybe even as a preceding step to compilation, or even prior to expansion. In fact this last alternative might be best, so that it can be aesthetically part of composition rather than part of the language.
So effectively, these languages could compose by virtue of:
- The code generation step being decoupled from the compiler(s).
- The "compilation" (sans code generation) of each language producing the Qi Core language (including
esc), which is a subset of each language's domain, rather than producing the "bottom level" of Racket (where we lose the context of composition), or another custom intermediate representation. - A way to "promote"
escaped expressions back into the domain of each language. - Expansion being idempotent (so that when languages receive already-expanded core forms as input, it is valid and they leave them unchanged).
It could be worthwhile to explore to what extent the expanders and compilers of each language could be cleanly decomposed to avoid any overlap. For instance, could it be structured more like this:
flow* := (lang-compose~> list:flow dataframe:flow db:flow qi:flow)
... where the last macro is the standard Qi flow macro, which would expand and compile the standard forms (still to Core Qi, not Racket, as that is done at the level of the entire composition)? Or does Core Qi need to be part of the expanders of each of the languages being composed, so that it is not necessary to have qi:flow at the end, as we had it initially? It's likely that the core expander does need to be duplicated here in each of the higher level languages in order to be able to properly "mix" them, but it would be ideal to be able to avoid that somehow.
If we feel this approach is viable, we would need to define precisely how languages could be defined so that they are composable in this way and how for instance syntax-spec can enable this kind of composition. The languages would need to usable in standalone form (i.e. performing code generation on their own), as well as in composition (where they should not perform code generation and instead leave it to the composing macro).
Qi does not provide guarantees in the presence of accidental side effects, that is, flows that are effectful but where the effect isn't explicitly indicated using the effect form.
But we wanted to review whether we provide sufficiently useful ways to escape this "pure" behavior in a convenient way. We had talked about a do form a long time ago -- a form that would cause the compiler to suspend optimizations. After discussing, we felt that this form would not be very useful to users and would be somewhat unnatural, as "not applying optimizations" is essentially saying "providing different semantics," which accords some arbitrary meaning to Qi expressions within the do form that happens to correspond to the meaning of certain corresponding Racket expressions. It doesn't seem very well-defined. But we did think that such a "hidden" form might be useful for Qi developers, for testing purposes.
We already do have the gen and esc forms which in principle mark the boundary between Qi and Racket. It would be ideal if we did not cross this boundary to perform optimizations. But in practice, for optimizations like deforestation, that's exactly what we do since there are racket/list functions that we look for in our patterns, which are all wrapped by esc as they are trivially host language expressions. One way that we might resolve this contradiction is the "promoting" pass we talked about above for composing languages. Someday, when a qi/list language exists, we could promote uses of (esc map) to something like (forest map), which would be a core expression of the language, so that the rest of the compiler could safely ignore esc as desired. Alternatively, as the expander for qi/list would already have forest as a core form, it could translate uses of map directly into (forest map) during expansion, the same way we translate function identifiers like f into (esc f).
In any case, we generally want to ensure that effects within effect, esc and gen forms are honored.
We noted that while our current benchmarks give a rough idea of performance and are a good place to start, they aren't very rigorous. For one thing, the results vary fairly widely from one run to the next, by up to 20% or even more. It would be good to report not just the measured performance but also statistics like the standard deviation. It would be great to have charts and visualizations, as well.
Now that the compiler work is close to release, we observed that it would be a good time to start documenting the new codebase architecture and development practices for Qi developers, including an overview of the approach we've taken, the big ideas and organizing patterns, and workhorse functions and macros in the code (like generate-fused-operation) and how they work.
As we noted last time, a lot of code that we know to be tested isn't showing up as "covered" in coverage report (e.g. viewable by running make cover).
We agreed that, now that the first-optimizations branch has been merged so that we officially have an optimizing compiler, and that this compiler is "beating Racket" on a few benchmarks, which we had set as goals for the compiler work, that it was now at last ready for code review!
(Some of these are carried over from last time)
- Tag people for code review
- Rebase the
lets-write-a-qi-compilerbranch tomainand resolve conflicts - Ask the community for help with testing and validating / migrating existing codebases due to backwards incompatibilities
- Investigate the coverage false negatives issue
- Fix the "bind and switch" issue, and identify whether there are any other forms that bindings do not escape.
- Update the main documentation to reflect the compiler work
- Update the developer documentation with details of the compiler implementation
- Comprehensively review error messages in Qi
- Review compiler normalization pass for correctness
- Review the use of explicit side effects in Qi wrt optimizations.
- Add test cases for the backwards incompatibility on datum vs literal matching.
- Investigate ways to extend the compiler (e.g. language composition or compiler macros) and use that to implement
qi/list(deforestingracket/list) as a proof of concept. - Prototype and then propose
map1for addition to Racket. - Validate that optimization passes can prematurely terminate if they don't return false when they don't transform the input (and then fix it).
- Implement streams for the other list operations described in St-Amour's writeup (i.e.
unfoldrzipaverage). Note: implementingaveragemight benefit from having "multi-valued CPS" for deforestation. - Write unit tests for more compiler rewrite rules, as well as end-to-end tests for pairs of input expressions, "logging" style (like Typed Racket) tests to validate expected compilation sequences, and sanity tests for the expander.
- Find a way to reliably detect list-like operations on values.
- Rewrite these list-like operations to list-based functional pipelines, e.g.
(~> (-< (>< f) (>< g)) ...) - Generalize the stream implementation to support multiple values at each step (in addition to zero or one) and recheck the performance.
- Review other core Qi combinators besides
~>(e.g.-<,==and><, maybeifandpass) and see whether it would make sense to extend fusion to them. - Should Qi provide a
maputility (overriding the default one) that supports "0 or more" values (as was discussed in the RacketCon talk)? - Design a core continuation form(s?) for Qi, and show how
trycan be implemented in terms of it. - Describe the sequence of compilation for input expressions with the optimizing compiler against the reference compiler, showing cases in which these do not terminate.
- Come up with a methodology to formalize and theoretically validate compiler behavior.
- Review other bindings cases that we could support next (e.g. selective binding, packing values, and binding exceptions in
try).
Dominik, Sid