Qi Meeting Aug 23 2024

One Track Minds

Qi Meeting Aug 23 2024

Adjacent meetings: Previous | Up | Next

Summary

We discussed deforestation architecture and next steps.

Background

There's been some drama this summer, with Sid getting into a bike accident by getting his wheels stuck in Muni (streetcar) tracks on the hills of San Francisco, and Dominik going on holiday to the coast of France (riding a moped but thankfully staying safe), and Michael going on a camping trip (he seems to have avoided encounters with notorious North American bears) and preparing for ICFP. In short, there hasn't been much to report on Qi, recently. Now we're all back from real forests (and the forests of the US medical system) for the moment, and returning to Qi deforestation architecture.

Deforesting in the Core Language

We recently discussed that it would be wise to make the core language rich enough to express deforestation rather than optimize host language (Racket) expressions.

This meant that:

• There would be a clear separation between Qi and Racket
• Higher-order function positions in such forms could now use Qi syntax

As this change implied moving away from optimizing host language function applications (e.g. map and filter) and towards optimizing Qi syntactic forms (i.e. macros that happen to be named map and filter), it also brought up some other considerations that we have been in the orbit of, and which Ben also touched upon in code review:

• What should the syntax of these new list-oriented forms be?
• Should they be drop-in replacements for racket/list forms?
• Fine and blanket templates are useful to capture computed values at runtime as arguments. How do we do this for these new forms?

Any Resemblance to Functions Living or Dead is Purely Coincidental

One answer is that as these are new forms and are not functions (even though they resemble known and standard functions), they can have any syntax we like. By selecting a simple syntax that is sufficient in practice, we can avoid complexity in the implementation that we had to introduce (like "vindaloo" curries) in the existing implementation in order to support Racket's syntax for these forms. When we need to, we can use bindings as an isomorphic replacement for templates, like this:

(~> (3) (as v) (range v 10))

But we felt that this isn't ideal. Templates are more natural here to capture intermediate values computed at runtime. Although the point about them being entirely distinct from racket/list functions is valid, we also felt that in terms of actual practical utility, the ability to supply arguments in any position is useful with racket/list APIs when used within Qi.

At the same time, supporting templates for these forms would seem to require a custom implementation as they would not be able to leverage the existing "fine template" and "blanket template" machinery we have in place for function applications. It would be nice if we could find a way to "promote" any form to one that supports templates, without duplicating the template logic and permutations across all of these definitions.

And all this is setting aside the fact that there seems to be a bug in using bindings for this purpose at the moment:

> (require qi qi/list)
> (~> (odd?) (as p) (range 100) (filter p))
string:1:15: let: duplicate identifier
  at: p
  in: (let ((p undefined) (p undefined) (p undefined) (p undefined)) (qi0->racket (thread (thread (esc (λ (p4) (set! p p4))) ground) (esc ((lambda (proc) (lambda () (proc 0 100 1))) (contract (->* (real?) (real? real?) any) (range->cstream-prepare (lambda (st...
 [,bt for context]

It might be related to how we are treating the processing of bindings after compilation in the generated Racket code as another compilation pass, and are invoking all of the compilation passes during the deforestation step. But in any case, we should be able to resolve this issue and it's a bug!

A Generic Scheme for Promotion

We agreed that not all Qi forms suggest the need for supporting positional behavior. For instance, forms like switch and ~> do not call for it. So for those forms that do entail positional "arguments," it would be useful to be able to treat them specially and offer natural support for positional behavior in the existing ways we've already developed for this, viz. templates.

We sketched a possible scheme to allow defining some Qi forms (like the list-oriented forms in qi/list) using a "meta-language" that would allow us to support templates while avoiding duplication, and also allow us to encode the runtime for the form in case it does not get deforested.

• First, make the #%deforestable syntax richer so we can encode a two-way mapping in it instead of just one-way as it currently is. That is, currently we cannot reconstruct the implementation of something like map just from its representation in #%deforestable, requiring us to hardcode the runtimes in the code generation step (see #%deforestable-parser in the qi0 module in the current PR). We would need something richer and more generic to indicate which positions in the implementation (specified inline as part of defining the macro, maybe?) are floe positions and which aren't.
• In order to define these macros that expand to #%deforestable and achieve the "two-way mapping," we can define a kind of meta-language that operates at a lower level than forms like define-qi-syntax-rule and use this meta-language macro to define forms like map. This macro would itself use define-qi-syntax directly. Typically, such transformer bindings have syntax transformer functions as their value, but with Syntax Spec, bindings for Qi macros and other forms of the language instead use a special struct type instance as a value here. The metalanguage we are talking about here would somehow place all the interesting compile-time information, captured from the definition, in the appropriate place in the struct type instance, which could then be consulted during compilation to reconstruct the code generation / runtime for these forms.
• This metalanguage would implicitly add support for _ and __ for any form that is defined this way, so that it doesn't need to be duplicated across the pattern-matching rules for each form that desires to support it.
• By being able to encode floe vs expr positions, as well as, perhaps, the expected argument positions, at the metalanguage / definition stage, it might reduce the complexity of matching (e.g. vindaloo curries) within the compiler.

Moving Forward on Deforestation

We felt that it would be good to merge the present PR before venturing down these directions though, and then continue against the integration branch. There seem to be three broad categories within the planned deforestation work:

• syntax of deforestable forms (e.g. supporting templates)
• deforested runtime for the different list-oriented APIs (e.g. modeled after those in racket/list)
• means of extending deforestation to custom list APIs (e.g. define-qi-stream-producer, ...)

While the means of extension will be informed by the former two, the syntax and runtime seem to be mostly decoupled from one another and could be done in parallel.

Another aspect we haven't talked about lately is whether deforestation can be extended to bespoke data types and not just lists. That will probably become more apparent once we complete the above three.

Qi 5?

We agreed that it looked like we will be on the integration branch for some time while we work out the many details discussed above, regarding syntax, implementation, testing, and upgrading the benchmarking suite to use the new implementation. As the higher-order positions employ Qi syntax, this also introduces "re-entrant" compilation and that, along with other things discussed here, would warrant proper testing.

So all in all, we felt it's looking like a new major release, and that we just might get it out "before Christmas." Solstice releases seem to be our thing!

Next Steps

(Some of these are carried over from last time)

• Review and merge the PR introducing the #%deforestable core form
• Fix the bug in using bindings in deforestable forms like range
• Implement the generic scheme for promoting position-oriented Qi macro definitions to handle templates
• Finalize and document guiding principles for Git commits in the developer wiki
• 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/list APIs via qi/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.

Attendees

Dominik, Michael, Sid