-
Notifications
You must be signed in to change notification settings - Fork 12
Qi Meeting Jun 21 2024
Qi Meeting Jun 21 2024
Adjacent meetings: Previous | Up | Next [None]
We discussed plans for deforestation, the design of qi/list, and the architecture of compiler optimizations.
Dominik recently submitted a PR including improvements to deforestation in qi/list.
With the release of Qi 4, we started to provide deforestation of standard list-oriented functional transformations such as map, filter and foldl. As part of recent reassessments of how we apply such optimizations, it was deemed necessary to include such bindings in the Qi library instead of matching Racket bindings for this purpose.
Now that we are providing Qi bindings, we wondered whether it would be more appropriate to support Qi syntax in relevant function positions instead of Racket syntax. For instance, (~> (filter odd?) (map (~> sqr add1))) instead of (~>> (filter odd?) (map (λ (v) (add1 (sqr v)))).
The clear benefit to doing this is that it allows us to use Qi syntax to express the kinds of functional operations that it is designed for, instead of using the more generic and verbose Racket syntax.
We considered a few potential drawbacks as well:
Benchmarking deforested vs naive functional pipelines would require syntactic changes in the benchmarked modules. That is, formerly, deforestation could just be turned on and off by requiring (or not requiring) qi/list.
We felt that this makes writing the benchmarks less trivial, but that it wasn't a factor to consider in language design. Additionally, it's possible we could still automate derivation of deforested code from an undeforested source module if it would be useful, perhaps by use of macros.
(require qi) changes semantics in ways that may be unexpected.
For example, in:
(require qi)
(~>> (filter odd?) (map (λ (v) (add1 (sqr v)))))
filter and map are treated as partial applications of Racket functions. But in:
(require qi
qi/list)
(~>> (filter odd?) (map (λ (v) (add1 (sqr v)))))
they are (as we discuss in more detail below) Qi macros expecting Qi syntax, and (λ (v) ...) is now a syntax error as it is treated as a partial application of a Racket function named λ, rather than as Racket syntax for defining an anonymous function.
One resolution here is to say that we're OK with this, since even in plain Racket, importing libraries can lead to shadowing of identifiers, so that any ordinary Racket library could provide a different meaning to identifiers such as map, filter, and even λ, and thus, requiring it could lead to the same issue.
But we also felt that it could be confusing as it deviates from the current behavior of requiring qi/list, where Racket syntax is honored and merely deforested behind the scenes. That is, it feels odd that (require qi/list) was formerly causing a difference in the semantics of certain source expressions, and would now also cause a similar difference in the same source expressions, but for these two differences to not be the same! Typically, this would be a sign of backwards incompatibility.
In fact, this can be seen as another sign that we are on the right track in moving away from optimizing host language expressions, as this kind of "incompatibility" would not occur if we were only operating on bindings we introduce ourselves, leaving host language semantics unmodified.
We concluded that our new bindings do not override any prior bindings provided by Qi, but only bindings provided by Racket through the standard mechanism of shadowing, but in an unusual, perhaps unexpected way, because the current implementation optimizes host language expressions.
We considered a possible remedy: support Racket's lambda syntax in Qi as a shorthand for (esc (lambda ...)) which, in any case, is the most common way to use esc.
That is, we could simply introduce the following Syntax Spec rewrite productions in the expander:
(~> (lambda e ...) (esc (lambda e ...)))
(~> (λ e ...) (lambda e ...))
This would simultaneously:
- minimize possible confusion by avoiding the need to escape lambdas
- provide a more economical entry point to this common use of Racket in Qi
- enable a gradual transition to using more convenient Qi syntax in place of lambdas
We agreed that as far as we could see, this was the best option.
Supporting Qi syntax in the new list bindings means exhibiting Qi's floe nonterminal in the syntax of the form rather than Racket's expr.
One option we mentioned and immediately ruled out was to define the bindings in terms of appropriate use of the flow macro.
Besides being "inelegant" in introducing a re-entrant Qi expansion and compilation via Racket instead of immediately fulfilling the translation to Racket, it also would mean that our compiler optimizations would straddle two languages once again, a state of affairs we have been trying to move away from.
We converged on implementing these bindings as ordinary Qi macros that expand to a use of a new core form introduced for the purposes of deforestation. Something like:
(#%deforestable-expression name:id (proc:floe) (arg:expr ...))
(define-qi-syntax-rule (filter proc)
(#%deforestable-expression filter (proc)))
One issue to resolve is that if after compilation we still have #%deforestable-expression islands left, at that point, we need to call host functions directly, or otherwise specify the runtime for this new core form. In order to do this, we need to know which positions are floe as we can't always assume it's the first position [TODO: clarify].
We could resolve that by including the appropriate host language expression in the expansion!
(define-qi-syntax-rule (filter proc)
(%deforestable-expression filter (proc) (a b c) (filter proc a b c)))
But that would mean encoding host language syntax in the DSL core language, which feels wrong.
Another option could be to embed a kind of "mini language" in the compiler in the code generation step which conditions on the name of the deforestable expression (via syntax-parse clauses) and compiles to a full use of the appropriate host language expression. This is another way in which the host language syntax could be encoded in the DSL implementation, but it seems acceptable here as it would be at the code generation step (in the compiler) where the host language is to be used at any rate, rather than in the DSL syntax (i.e. in the expander).
Ultimately, qi/list is going to be not just deforestation for racket/list APIs but also a more convenient way to express functional list operations.
As the new bindings in qi/list are going to be macros in the proposed implementation, they could simply be documented as forms employing floe and expr positions, and link to the existing docs for these. They need not include anything more substantial as the existing docs already go into detail on the syntax and semantics of such expressions.
With these improvements in the interfaces and architecture of optimizations, it becomes more feasible to organize a community event around writing Qi compiler optimizations, which we've talked about a few times before.
(Some of these are carried over from last time)
- 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.
Dominik, Michael, Sid
Home | Developer's Guide | Calendar | Events | Projects | Meeting Notes