Qi Compiler Sync Jan 12 2024
Qi Compiler Sync Jan 12 2024
Adjacent meetings: Previous | Up | Next
We released Qi 4! Ferdinand the cat performed tricks for everyone. We discussed lots of future directions and avenues for exploration, Qi project governance, ABE, and more.
The compiler work has been over a year in the making and is finally ready.
Sid was secretly feeling quite smug that the process of making a new release was already documented in the wiki. "This is the great thing about documentation-driven development," he was saying to himself, amidst discussions about the release and connected activities like the latest benchmarking results, "We can pretty much just go through the motions as the steps are all written down pretty clearly by someone quite smart and cool." We had gotten complacent enough that most of the release activities were done in the background to other ongoing discussions, since we assumed there would be long cycles of waiting as things got deployed and CI jobs got executed and so we might as well continue other discussions in parallel to save time.
But even good documentation isn't foolproof, and step-by-step instructions can still be bungled if not followed with care. We ended up accidentally tagging a wrong commit as v4.0 and pushed it upstream. This tag was deleted and it was only a couple of minutes that it was publicly visible, so hopefully that won't cause any problems 😅
It later turned out that we also neglected to go through the "pre-merge checklist" in the pull request description (which has now been promoted into the wiki so we don't miss it!). In particular, we forgot to add version exceptions, and a maintenance branch, for older versions of Racket.
One lesson here is that there should be a single source of truth on steps to follow. In this case, we followed the steps in Making a New Release, but the pre-merge checklist was in the PR description. Another lesson is that doing a release may involve long cycles of waiting, but it is still worth taking it slowly to ensure there are no mistakes, which are all too easy to make.
The good news is, we learn from our mistakes and now we have even better documentation for next time!
Well, it'd be boring if we didn't have at least a few hiccups during release. And when all was said and done, we'd officially merged more than a year of work on the Qi compiler! Yet, this is only the beginning, since this has only opened the door to exploration of all kinds of optimizations for which there is literature stretching back decades, and it's going to be very interesting to see how these time-tested and well-studied optimizations manifest in Qi's flow-oriented paradigm. Who knows, there may even be novel optimizations that this paradigm enables that are tricky to do in general. For instance, it is perhaps a unique aspect of Qi that entire programs have a simple and tractable semantic structure, since flows are acyclic graphs. There may be graph-oriented flow optimizations that are natural in Qi but which may be inapplicable or which would not suggest themselves in other paradigms. Similarly, there may be other unique attributes to flows that would lend themselves to interesting and unusual optimizations.
The Qi repo now has over 1000 commits. We reviewed the tracked local benchmarks and found that the (require qi) latency is about the same as before (at about 150ms), despite the fact that we added a dependency (on Syntax Spec). We also noticed that the tracked benchmarks now included many nonlocal benchmarks, such as filter-map. We had planned to add this some time ago but had forgotten (or perhaps didn't know) that we had in fact done so already!
Of course, these tracked benchmarks aren't very rigorous and must be taken with a huge grain of salt. The main purpose they serve is to signal obvious regressions or improvements, and for forensic purposes in case we expect to see a historical difference due to some commit, and we would then be able to verify if such a change was present in this historical data.
Ferdinand the cat had been through a very rough patch in the last week. Under the pretext that Qi 4 is like "chi chi chi chi," a way of calling cats in Prague and other parts of Europe, we had invited him to perform some tricks for us and had announced this to the community. But in the preceding days, Ferdy had had a hypertension-induced stroke and had been in a coma in the hospital, and the vets were unsure if he would awaken from his deep, deep slumber. During that harrowing time, Sid told Ferdy that "we told everyone" he was going to do tricks for them, and that he had to come back and couldn't miss the show. Miraculously, that's just what he did the next day. Not only did he come back (to the amazement of veterinary staff at the hospital), but he made great strides in the following days, and was unstoppable!
Though he was still recovering, he eagerly performed some tricks for us, including:
- sit
- shake hands
- stay
- high five!
- head butt
- flying head butt
- which hand?
- meerkat
- figure 8s
- cherchez la femme / the shell game
Everyone was thrilled and we gave Ferdy lots of treats (but cut into small pieces since he is still on a low-carb diet!) for being a very good boy. We called the cat and the cat came to the show!
Now that release activities were concluded and the guest of honor had performed for us, we discussed other follow-on matters like how to get reliable benchmark data to accompany the release announcement.
One of the difficulties is that running on a laptop concurrently with other activities can lead to spikes in the data.
One option was to use GitHub's CI infrastructure to run the benchmarks, using a similar workflow to our existing backup docs workflow, and tracked benchmarks workflow. Sid had created a PR as a starting point for this, but we felt there were still some unknowns regarding setting triggers for the workflow, having the benchmarks suite in "package" form so that it could be reliably installed, conflicts with the docs workflow which deploys files to the root path on the Qi GitHub site, and possible constraints on workers that may prevent running jobs long enough to get the level of confidence we need.
To sidestep these unknowns and have maximum control, Dominik rigged up a dedicated machine to run the benchmarks on, which we will be using to get less noisy data.
These are the latest benchmarks we have at the moment from this mean machine.
Last time we'd observed that Qi forms were still unlinked in the documentation. After further investigation, and asking on Discord, Matthew confirmed that this is due to Qi's use of binding spaces (as we'd suspected), and the need to support a #:space argument in Scribble documentation forms like @defform and @racket. Rhombus is a prominent emerging language in the Racket ecosystem that makes heavy use of binding spaces, and its documentation is correctly linked as it uses lower-level Scribble APIs to implement its documentation forms. We could look into doing something similar now, but we agreed that it would be better to wait until this support is added in a released version of Racket so that we can use the high level Scribble API with the #:space argument at that stage.
This logo was sketched by Racket's very own Sam Tobin-Hochstadt at RacketCon this year. Sid asked one of his friends, Alan, who is a designer, if he would be kind enough to make the logo for us, and he did! Behold!
The Qi project eschews traditional licensing as it only works for a tiny fraction of people who need the benefits it supposedly provides, and even for these people, it's often stressful, challenging and time-consuming to get their rightful share of whatever value may have been created by their work. For the vast majority of people, declaring licenses is a pointless exercise, and in the aggregate over the entire system, costly and an enormous waste of time.
ABE's approach to the problem is to say that "authorship" and contributions are not something to be determined by decree ("I own this"), but rather, it is something that is fundamentally defined collectively (in the parlance of the research at drym.org, it is dialectical). After all, when creative contributions are available in the world, their tangible public impact is apparent for everyone to see. It remains to define fair social processes to appraise this value that is generated, while also identifying the extent to which each contribution contributes to the whole. Appraising value is of course subjective and one of the oldest philosophical problems. ABE addresses this by differentiating two forms of value (1) dialectical value and (2) transcendent value. This division accepts that philosophically, some component of value cannot be determined by any social process. By accepting this limitation, ABE frees us to recognize the true extent to which we can recognize value collectively, that is, ABE's contention is that economic value should be identified with dialectical value, and this gives us a conceptual framework to understand how to go about recognizing it.
Once this is done, "claiming" ownership is simply unnecessary (and in fact an obstruction) to fair -- financial -- recognition of contributors. The process that recognizes dialectical value is called Dialectical Inheritance Attribution, and it is designed to recognize any type of value, including labor, capital, and ideas, and thereby exhibit the right economic properties and give rise to the right economic incentives that are aligned with the common good. DIA is a formalized, structured, and anonymized social process that anyone may participate in, and by an application of the Golden Rule to the origin of economic incentives, it ensures that project contributors are fairly recognized even if these contributors do not participate in the process at all! The beauty of the process is that its results aren't determined by specific people but by processes that anyone may follow (it is inspired by the Gayanashagowa -- the origin of modern process-oriented governance).
Qi already has a dedicated repo, dia-qi, that tracks contributions to the Qi project for this purpose. Now, with the compiler work completed, it will need to go through a fresh round of DIA to identify the value created and the sources of that value. DIA is still in its early stages of development, but as a proof of concept, we have already demonstrated that it works. The next step is to scale it, and Sid has been teasing for some time that he has an idea for how to do this, and he hopes to work on a proof of concept soon.
Looking back at copyright and other traditional ways of recognizing creators, we see that by allowing people to claim ownership over such works, we disproportionately empower those who are in a position to enforce their ownership claims, rather than those who really contributed the value. Indeed, we exclude the majority of people from participating in the creation of value (just think of all the cool AI tech now being developed behind closed doors), minimizing the global creation of value in the pursuit of fair recognition for a few that copyright ultimately fails to deliver. It is a very simplistic system that ignores the immense complexities and richness of the real ways in which value is created in the world, and the wonderful ways in which it can be created, when we set it free.
The purpose of identifying sources of value is to empower the appropriate contributors to make further valuable contributions.
One aspect of this is of course financial. ABE's contention is that if you contribute value, you should get paid. Not for your sake, but for everyone's sake. Because if you don't get paid, someone else is getting paid for value you created, and they are therefore gaining an influence over the world's progress that is disproportionate with the value they themselves contributed, eroding our collective capacity to recognize and achieve good outcomes. Today, ABE facilitates payments using the accounting prototype Old Abe, which is governed by a novel financial model.
The other aspect of empowerment is in the sense of governance. Looking at Qi's current attributions (it doesn't yet account for the compiler work, of course), we would like the members in that contributors file to have a say in the direction of the Qi project that is proportionate to their attributive share, that is, to their proportion of value contributed.
We discussed that in Qi, there are no bosses, employees, managers, VPs and CEOs with fiat authority -- there are only roles and needs that anyone may fulfill, value that is identified in advance and recognized in retrospect, and influence that members have that is proportionate to their contributions.
Of course, this is all very well "in theory," but we don't actually have any governance processes defined that achieve this in practice. We discussed that such processes will need to be defined, and mentioned, yet again, the Gayanashagowa as one possible source of inspiration.
Now that we've completed the initial work on the compiler, there are many, many avenues of future work. We talked about some of these possibilities.
Currently, we fuse (deforest) a handful of standard higher-order functional utilities like map, filter, foldl and foldr. But we also fuse some list utilities like range. Recently, Sam had suggested deforesting car, and then Dominik identified a whole host of list utilities that could be amenable to the technique. We've talked about implementing this a number of times, but a balancing concern was doing it in such a way that it keeps the Qi core library lean. That is, we'd like this functionality, but we'd like to require it on demand, instead of bundling it with Qi for all users though only a few of them may conduct such elaborate list transformations.
Last time, Dominik showed a proof of concept of a simple "internal" compiler extension mechanism that we agreed could be used to prototype this, and we felt that this would be one logical next step for Qi compiler development.
We also discussed that there does not seem to be a case study in the literature of having deforested a full existing reference API such as racket/list, and such a case study might be a useful outcome of such an endeavor.
On the other hand, we also considered that work on the subject of deforestation would be mainly of interest from a research perspective if it was in terms of an industry standard implementation such as Haskell's GHC rather than a comparatively obscure one like Qi.
On the other hand, an implementation of deforestation that could be extended by libraries to custom types could be compelling and may be a unique advantage for the Racket ecosystem, with tools like syntax-spec and syntax-parse, the module system, and distinct compilation phases.
This would be especially compelling if we could achieve it in an elegant and composable way. One possible approach we recently talked about is "the bottom level is hopeless." It's unclear whether that is a viable approach, but we talked about how there is a lot of literature on the subject of language composition, and enumerated some papers and approaches for reference, including:
- Work by Eelco Visser
- Stratego
- Spoofax
- JetBrains NPS
- Lightweight Modular Staging
- Delite
- Hermit
- MLIR
- Ziggurat
... and many more.
It would be useful to understand some of these options to see if they are applicable, and to put any of our efforts in context. Additionally, it would also be useful to have at least two distinct data types ("we need to do it for N = 2") and corresponding APIs to deforest, as that would serve as a trial of candidate approaches and allow us to converge on a specification that works for any data type. It may also reveal useful generic functionality that could be implemented in platform technologies like Syntax Spec.
We felt that Racket lists were clearly one such data type, and possibly another one would be the functional dataframe type that Sam was working on recently.
One intriguing possibility that Qi presents has been the ability to transform values without regard to collections. This could mean that it could be used to implement such transformations in a collection-agnostic way, much like Clojure's transducers. Of course, our current implementation of deforestation is specific to lists. But we've talked about applying this core implementation to the deforestation of pure values in expressions like (~> (pass f) (>< g)). If we could do this, then that would open the door to deforesting any collection.
One obstacle here is that functions in Qi typically accept any number of inputs and produce any number of outputs. Our current implementation of deforestation assumes that the functions used in map return a single value. We would need to generalize this to "0 or more" outputs, which, it's at present unknown whether this can be done in a performant way.
We could also provide generic operators more generally. For instance, we could accept an expression like (~> ("a" "b" "c") +) and perform string concatenation here. But it's unclear whether there would be any particular benefits to implementing such generic operators in Qi as opposed to just using Racket's generic interfaces to create such operators as Racket functions (as the relation library does). Most likely, such generic operators would be more compelling in something like Typed Qi.
Earlier when we discussed making the new benchmarking suite available as a library, Dominik had mentioned that it wasn't quite ready and that he often finds he writes many different versions of a library before he settles on the right interface, and Hendrik sagely observed that, indeed, "Good writing is rewriting." In any event, the library is currently specialized to the existing benchmarks we've been using with Qi, i.e. functional pipelines like filter-map. We agreed that generalizing it to be usable by other libraries in the Racket ecosystem for general purpose benchmarking would be valuable. There is already a benchmarking library for Racket, so it would be worth evaluating what features it provides and whether it would make sense to complement that feature set or provide a completely distinct offering. In the spirit of "N = 2," it could be useful to try extending this suite to benchmarking some variants of Minikanren that Michael is working on, on the road to defining a generic and useful interface.
Qi now has one proven effective optimization (stream fusion / deforestation), which was the goal of the initial compiler work. One optimization that might be a good next step is to use functions accepting a statically known number of values wherever possible, vs functions that are variadic in their inputs.
In getting this release ready, we took a number of shortcuts to get the job done. Now that the release is out, it may be worth reviewing some of these choices and investing some effort into doing them in more robust ways, to better support our continuing efforts along the many paths we've identified for future exploration. Some of these items that may be worth prioritizing in the near term include:
- Incorporating the new benchmarking suite into development and CI workflows
- Developing a core grammar aware tree traversal utility in Syntax Spec, to avoid the need for the
nonterminalsyntax property - Preserving source code and locations through expansion in Syntax Spec, for use in error reporting in the compiler, to avoid the need for the "de-expander"
... along with triaging the numerous "Next Steps" we've been carrying forward below!
(Some of these are carried over from last time)
- Incorporate the new benchmark suite into the SDK (including Makefile targets) and CI workflows
- Review whether we can continue optimizing a single syntax node at many levels (this is not a blocker)
- Comprehensively review error messages in Qi
- 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. - Preserve the source syntax through expansion in Syntax Spec.
- Review the use of contracts in deforestation.
- Improve expander tests to compare expressions literally, using a test for alpha-equivalence.
- Try unpublished expansion event APIs to implement hierarchical reporting of expansion in the compiler.
- 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. - 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).
Ariana, Dominik, Ferdinand, Hendrik, Michael, Sid