-
Notifications
You must be signed in to change notification settings - Fork 12
Qi Meeting May 31 2024
Qi Meeting May 31 2024
Adjacent meetings: Previous | Up | Next
We discussed various long term goals for Qi, especially regarding the architecture of the language and the development interface provided for extending the compiler. We developed the language composition proposal further before identifying modifications to our existing approach that would achieve all of the goals we've identified, to everyone's satisfaction.
There comes a time in any project when it must decide where it wants to go. Contributors must look to that distant horizon, though it may be only faintly discerned, in order to ensure that today's projects keep us on that long term path. In recent times, there have been some concerns regarding the current approach to compiler extension in light of such ambitions, and language composition seemed promising as a possible long term alternative.
From the earliest days of Qi, it had been apparent that there is something intuitive and simple about the language that makes some things that are possible in other languages in principle easy in Qi, a sentiment expressed by many members of the community.
One such idea is how the simple composability of flows is analogous to such composability in settings other than ordinary functions. For instance, we could imagine that flows could be threads or processes or streams, or even Big Data computing primitives like AWS Lambdas. All of these have some essential similarity that we have felt could be encapsulated by Qi's abstraction of "flow," so that the same surface language could perhaps compile to these distinct underlying semantics.
In recent times, thanks to Noah and Nia, this idea has become more concrete -- the "essential sameness" can be understood using category theory. The different implementations of flows correspond to different categories where, perhaps, an isomorphism could be defined to some suitable canonical category where the objects are (say) ordinary values and the morphisms are ordinary (e.g. Scheme) functions.
These goals are also consonant with broader ambitions expressed by Noah and also Sergiu, to characterize and understand Qi's connection with category theory more broadly, theoretical groundwork which could yield many practical constraints on Qi's design (some of which we'll talk about below), and may reveal possibilities we have not yet imagined.
Another idea, brought up by Sam P, is for Qi to be able to optimize bespoke datatypes not bundled by the core language, that is, for the language semantics to be extensible.
Michael is interested in Qi to the extent that it helps to reveal Syntax Spec's ideal interface and provisions for DSLs in general.
Dominik is interested in literally everything, and is currently (luckily for us) obsessed with thoroughly exploring deforestation.
Ben has always kept us grounded by insisting that Qi remain simple, transparent and sound.
Sid has been excited about all of these goals and is also concerned about the maintainability of the code and keeping it well-lit so that Qi community members today and in the future will always be able to contribute and so that it will always be fun.
Given these diverse goals, it was essential to review our short term efforts so that we do them in such a way that they are consistent with these longer term goals and do not hamper them.
Recently, we merged the compiler registry architecture to decouple deforestation work from the Qi core. This gave us a way to extend the compiler in a very simple way, but some concerns were raised that it was effectively a means not of extending the semantics of the language but instead of mutating them, giving rise to many possible problems if we try to use it as a general way to extend the compiler or choose a different backend.
Formally composing languages seemed promising as a way to achieve compiler extensibility in a sound way, so we looked at it in detail this time.
We reviewed a draft proposal that allows languages to be composed in relation to a common base language. Compiler passes could be written as distinct languages that are composed to form the current Qi language, but they could also be composed directly with other passes (languages) to form Qi variants that users may find more tailored to their needs.
We posed many challenges in order to develop and evaluate the proposal.
One of the reasons the Racket BC → CS work was possible was because the compiler was closed to extension. Had it been possible for anyone to write extensions for the compiler, then there would have been too many moving parts to keep compatible through the transition.
The proposal addresses this by using a sufficiently rich core language (let's call it Qi₀) as the common interface across all compiler passes, so that Qi₀ is the input and output to each pass. This seemingly constrains the information available to each pass as well as the diversity of intermediate representations, but this is addressed by a "dockerized" compiler architecture, where each pass is responsible to perform all pre-processing that may be needed for the pass to do its main job. This ensures that the core language is rich enough to express the optimized code, but that it only includes what is relevant to the output of each pass rather than its operation.
For instance, in typical architectures, an early pass may annotate the IR with arity information which is then leveraged in subsequent passes until it is fully taken advantage of, at which point it may be dropped from the IR for subsequent passes as they may not need it anymore. In the proposed approach, every pass that needs arity information is itself responsible for annotating the core language IR with this information. This could lead to duplicating the work of inferring arity across multiple passes (while sharing the code), but it ensures that the IR contract between representations remains the common, publicly-advertised core language, Qi₀, and keeps each pass uncoupled from other passes (indeed, it ensures that they are commutative). It is analogous to how CI systems favor Docker images that construct environments for each CI job (e.g. "run tests" vs "build docs") from scratch, instead of augmenting an existing persistent environment.
This would also simplify the actual work of each pass, as they would each operate on the specific representation that's needed for their purposes, rather than one that might encode additional information that's required in subsequent passes. By keeping each pass decoupled from every other, it also makes development easier by enabling us to turn passes on and off at will, without causing any errors.
Finally, as the input and output to each pass is the shared and well-specified core language (though it may be arbitrarily augmented within each pass), reasoning about the compiler should be more theoretically tractable, with all the benefits that brings.
As the Racket core language is unchanged across the BC → CS transition, with the proposed architecture, it would still have been equally possible without worrying about maintaining compatibility with third party extensions.
We considered this example:
(~> () (map sqr) △ (>< sqr) ▽ (map add1) △ (pass odd?) ▽ (filter (< 10)))
Would it be possible for an optimization to simultaneously deforest both the list- as well as values-oriented functional operations here?
As >< etc. are part of the core language, and as the proposal requires each language in the composition to be a superset of the core language, in this case, the qi-list language could include the necessary values→list translations so that its list-based deforestation would suffice here.
We considered this example:
(~> ((list 1 2 3) (list 4 5 6)) (>< (~>> (filter odd?) (map sqr))))
If we assume that the values-oriented forms like >< aren't part of the core language but are instead in a language called qi-std, then in the proposed approach, if qi-list went first in compiling the input, it would miss optimizing the relevant part as it wouldn't traverse into the >< expression. This wouldn't just mean that the code isn't as optimized as possible, but that it would cause a compilation error, as the core language would not recognize the uncompiled overlying syntax.
This issue also affects the previous example if we assume that the values-oriented forms are not part of the core language, and if we further assume that they are limited to only produce a single value (like traditional list-based map).
The resolution we came to was for each pass to do a generic traversal over the input syntax rather than one specific to the grammar of the particular language. We wondered if this might cause problems by virtue of traversing into syntax that containing forms in another language might treat differently than as usual flows, but we concluded that this would not be a problem if the optimized positions are always floe nonterminal positions. If a language intends to imbue special meaning to what appears to be flow syntax, then it would define a new nonterminal for the purpose rather than use floe.
We considered forms employing continuations to implement nonlocal exits. For instance, what if probe and readout were implemented as flows in a Qi language called qi-debug?
Then in this example:
(~> (pass odd?) (>< readout))
If we compose the language as (qi-list, qi-debug), then the sequence would be deforested, and the behavior of the readout would be different than if the language were uncomposed as qi-debug.
The same may be true of forms introducing bindings, where those bindings might be mutated in contained flows.
We compared this to the existing behavior of effects in Qi in the wake of deforestation that's already being performed on lists, and concluded that the changes in behavior are of the same kind as those that are already known and which we have discussed as being consistent with Qi's theory of effects which discourages "nonlocal" effects.
It also seems likely that what a "flow" is allowed to be in different languages and different backends should be constrained by category theory. Only those semantics that are isomorphic (or some weaker form of equivalence) to the usual flow category (however we construct that), perhaps, should be valid as flows. This may also rule out such nonlocal behavior.
If we had a qi-dataframe language and a qi-list language that both perform deforestation, then if there happen to be ways to deforest both at the same time, neither language would be able to do it. On the other hand, in a monolithic compiler architecture (even if split into passes), each pass would be able to do arbitrary transformations in terms of the full language. The drawback is that such optimizations would need to live in the core compiler and thus bloat the language to include custom datatypes.
It's worth observing that constraints in one area sometimes lead to advantages in other areas. For instance, disallowing mutation in functions makes them less powerful, but enables seamless composition which brings benefits at a higher level. In a similar way, constraining optimizations to overlying + core language syntax brings composability at the cost of such cross-language optimizations, and that may bring benefits we haven't thought of. Perhaps it would reveal what the right scope of each language truly should be.
It would be helpful to identify concrete examples where such cross-language compilation would be needed so that we might understand this case further.
Finally, this problem can be alleviated by suitable extensions to the core language of the kind considered below, so that it appears that we can have arbitrary compilation of composable languages if the core language is sufficiently rich (for instance, if it includes a deforestation primitive).
With the change to use generic traversal in compiler passes, we concluded that the composition approach should be able to handle all the cases we could think of. But it is likely to be a significant undertaking, requiring big changes in Syntax Spec, and there may be other, easier, ways to modify our existing approach to achieve what we want.
Additionally, the most common, indeed only, case of compiler extension that we've talked about is deforestation for custom types. In order to deforest a custom type with the language composition approach, a user would need to require both qi as well as the deforesting language, say qi-dataframe, and then use Syntax Spec to explicitly compose the language and re-provide it as a distinct language that they then use. Of course, in practice this may be done in libraries such as qi-datascience so that it would be library authors rather than users who perform this composition. But we wondered whether this was a relatively heavyweight way to gain deforestation for custom types. Are we "composing" here when we seek only to "extend"?
To orient the discussion, we identified three broad topics that we are talking about:
- Composition
- Extension
- Multiple backends
We felt that so far, the only kind of compiler extension we have identified a need for is to extend deforestation to bespoke datatypes. So we narrowed the discussion to how we might support extension for deforestation specifically, rather than be able to specify arbitrary compiler passes. We felt this could be accomplished by macros resembling:
(define-qi-deforestable-transformer dataframe-map
...)
This macro would define a binding that the module would provide, and we could then match and optimize this binding in the generic deforestation pass.
In order to avoid matching and optimizing a #%host-expression (even though it is "our" binding, it is still naively a host language expression), we could add a core form to the Qi syntax spec resembling:
(#%deforestable-call f arg ...)
and then a rewrite production:
(f:deforestable-operation arg ...) → (#%deforestable-call f arg ...)
… where deforestable-operation detects a compile-time value in a similar way to how Syntax Spec recognizes DSL macros (which we formerly mimicked in the Qi implementation before transitioning to Syntax Spec).
And this would now allow us to match and optimize this core language form in optimizations rather than any host language syntax!
Since allowing deforestation to be extended fulfills the only actual case of compiler extension we've talked about, that now means that we no longer need the compiler registry to serve as a means to extend the compiler. We can therefore consider it purely an internal implementation detail that allows us to turn on and off certain passes during testing and benchmarking, but not otherwise expose it as a means to extend the compiler outside of qi-lib. That way, generic deforestation semantics of producers, transformers and consumers could be part of the core language, but the myriad specific implementations of racket/list APIs could live in qi-list as extensions of core deforestation, which itself would be a prototype for extensions to custom datatypes like dataframes.
In order to compile to different backends, we can separate the compilation and code generation steps (as we do in the proposal) and use them in Syntax Spec's existing interface as:
(require qi/expander
qi/compiler
my-codegen)
(syntax-spec
(host-interface/expression
(flow f:floe ...)
(syntax-parse #'(f ...)
[(f) (qi0->my-backend
(compile-floe #'f)]
…))))
Thus, it should be possible to reuse the expander and compiler. It may be necessary to change the compiler from a macro to a function, and there are some Syntax Spec utilities that will help us preserve hygiene if we do this. It may also be necessary to write a distinct bindings pass for each backend as that happens after code generation.
It does not appear that there would be a way for these languages to introduce core forms of their own.
For instance, in an Erlang-like Qi dialect where we might send messages to named nodes on a network:
(~> (send node-A (~> sqr add1)) (send node-A (~> (* 2) (+ 5))))
Since node-A is the recipient of two communications in sequence, we would prefer to compile that to:
(~> (send node-A (~> sqr add1 (* 2) (+ 5))))
But if send isn't in the core language, then we wouldn't be able to do such an optimization.
In any case, we will need to write an actual proof of concept of at least one Qi dialect compiling to a different backend, in order to get a better sense of practical needs and whether considerations like the above would manifest as concrete limitations.
These changes address all of the concerns we'd identified with the existing means to extend the compiler. Specifically:
- We no longer match and optimize host language syntax, and thus do not violate host language invariants.
- We optimize syntax that Syntax Spec has validated, so we don't need literal matching in the compiler.
- There is no need to expose the compiler registry and thus the semantics of the language are not mutated outside
qi-lib. - The core language only adds a single (or perhaps a few) deforestation-related form and corresponding semantics, allowing the majority of list-related deforestation to exist as extensions in
qi-listrather than in the coreqi-lib. - Most other concerns (such as relying on internal IRs, placement of passes, encoding nonlocal information in passes, social overhead, broad backwards compatibility contract with downstream passes, etc.) disappear when the compiler registry is not exposed as the means of extension.
Finally, this extensibility of deforestation is orthogonal to, and compatible with, many of the ideas in the proposal, including composition, the "dockerized" compiler architecture, and more.
- As
map,filterandfoldlare going to effectively be Qi syntactic forms rather than partial application of host language functions, should they be invariant to threading direction, so that(~> (filter odd?) (map sqr))would be valid? - Can we extend deforestation to
floewhich could produce zero or more values, so that we could deforest values sequences like(~> (pass odd?) (>< sqr))? (Though performance here would be worse than single-valued deforestation, it is still likely to be much faster than current performance which involves values→list→values conversions.) - Should the function arguments to Qi's
filterandmapbefloepositions rather than escaped host functions (even if the implementation is constrained to expect single values)?
On the way here, we followed two philosophies. One approach is to study the data, work with it, model it, and allow implied generalizations from this data to suggest the right implementation. Another approach is to follow our instinct and search for solutions that feel right and achieve our high level purpose. The former is more scientific, the latter more artistic. The former risks finding locally optimal solutions, while the latter risks overengineered solutions.
Both are needed to find the best answers that are globally optimal and economical. Like the A* algorithm, we must be grounded, yet optimistic!
(Some of these are carried over from last time)
- Decide on the syntax of Qi's
map,filter, etc. - Revisit extending deforestation to multi-valued settings.
- Write a proof-of-concept compiling Qi to another backend (such as threads or futures), and document the recipe for doing this.
- Ask Ben to review tests from the perspective of Frosthaven Manager.
- Review Cover's methodology for checking coverage.
- Document the release model in the user docs and announce the performance regression (and the remedy) to users.
- Improve unit testing infrastructure for deforestation.
- Discuss and work out Qi's theory of effects and merge the corresponding PR.
- Decide on appropriate reference implementations to use for comparison in the new benchmarks report and add them.
- Deforest other
racket/listAPIs viaqi/list - Decide on whether there will be any deforestation in the Qi core, upon
(require qi)(without(require qi/list)) - Continue investigating options to preserve or synthesize the appropriate source syntax through expansion for blame purposes.
(Including input via email and Discord)
Ben, Dominik, Michael, Sid
Home | Developer's Guide | Calendar | Events | Projects | Meeting Notes