Qi Meeting July 23 2025

Adjacent meetings: Previous | Up | Next

We upgraded Qi from using Syntax Spec v2 to v3 (in a PR), and submitted three PRs on the Syntax Spec repo in connection with this and also in connection with DAG-structured bindings. We started to formalize Qi using Redex but ran into problems right away with encoding scoping structure.

We've been discussing the need for DAG-structured scoping rules in Qi in order to easily support alternative backends, like futures. Eutro recently added a new parallel binding spec to Syntax Spec to support this, in the v2 rather than main branch of Syntax Spec, as that is the version currently used by Qi.

We've also been discussing the need to formalize Qi's semantics, as the implementation in some cases deviates from the design, and we plan to explore alternative backends that may introduce their own idiosyncracies.

Sid took a first stab at formalizing Qi this week using Redex. The docs for Redex are excellent, and it was pretty straightforward to get started.

Redex allows you to specify the semantics of a language, including a grammar and scoping rules, and offers predicates to reason about and check those semantics. A basic version of Qi could be formalized as:

#lang racket

(require redex)

(define-language qi
  (floe (~> floe ...)
        (-< floe ...)
        (== floe ...)
        (>< floe)
        f)
  (f variable-not-otherwise-mentioned))

Now we can check whether some syntax matches the grammar:

(redex-match?
 qi
 floe
 (term (~> f (-< g h) (>< l)))) ;=> #true

term here is analogous to quote, so we are simply providing some syntax here to see if it matches the grammar for the floe nonterminal in the qi language, which, we learn, it does.

Next, we wanted to encode Qi's scoping rules, i.e., the as form. But that immediately presented a challenge. The documentation on binding forms gives this example for Scheme's usual lambda as a binding nonterminal:

#:binding-forms
(λ (x) e #:refers-to x)

… indicating that the syntax e is bound by the syntax (an identifier) x.

But with Qi's as form, the bound expressions, although lexically scoped, are not textually contained within the binding form, as we discussed recently.

#:binding-forms
(as v) ; nowhere to put #:refers-to

We didn't find an obvious way to notate such binding rules, but there was some other syntax for bindings such as the #:exports keyword that could potentially be used. But if not, we discussed that we would probably need to formalize these rules simply as global scope with some rules on set!. This seems complicated, and if it were necessary we felt we should probably leave off on this for now.

The current implementation of Qi's binding rules resembles a let* in that preceding tines of parallel forms bind succeeding ones, and shadow them. We've recently discussed that we need something more like let, which doesn't bind across binding clauses (analogous to tines).

Dominik shared let++ and let+++ macros which implement something even more exactly analogous to what we need, where the binding clauses can also bind locally within those clauses if there is a body there, similar to nested flows within relays or tee junctions.

 #lang racket/base

(define-syntax let++
  (syntax-rules ()
    ((_ (((id expr) ...) ...) body ...)
     (let-values (((id ...) (let* ((id expr) ...)
                              (values id ...))) ...)
       body ...))))

(let++ (((a 5)
         (b (+ a 1)))
        ((c 7)))
       (displayln (list a b c)))

Here, the toplevel binding clauses do not bind one another, nor do they shadow one another, and a duplicate binding identifier is simply flagged as an error by the underlying let-values.

This brought up how bindings shadow across tines today. Is this actually desirable? Dominik pointed out that it would complicate implementing a futures backend for flows.

We felt that shadowing is in fact a form of coupling across tines, the very kind that we have been moving away from in recent discussions, so we felt that tines should not shadow one another (wrt downstream).

The let+++ macro was similar to let++ except that it actually leveraged futures for the different binding clauses.

Eutro explained that the parallel binding-spec that she has proposed for Syntax Spec handles this by allowing distinct bindings in the different tines, having them all bind downstream, while signaling an ambiguous binding error if the same name is used in different tines. We agreed that this was the ideal behavior, and the absence of shadowing here, too, would support a simple futures backend.

She submitted a PR against the v2 branch of Syntax Spec, which is the version used by Qi. This proved to be a good move as it helped us start the discussion with Michael and Syntax Spec maintainers, but we also felt that we should port the implementation to the main branch (currently v3) so that it would be easier for them to integrate on the main line of development.

We decided to migrate Qi to Syntax Spec v3 so that we could use it to test the proposed binding spec once it too has been migrated to v3.

This mainly involved syntax changes and went smoothly for the most part, except that we discovered that the tests were failing. Further investigation revealed that they were passing on the latest version of Racket but failing on the oldest Racket version supported by Qi, 8.5 (which are the two versions --- that is, oldest supported and latest --- used in the CI workflows).

Bisecting revealed that versions Racket 8.9 and earlier had the error, while 8.10 and newer were OK.

We tentatively documented the new implied version compatiblity in the Qi docs and also submitted a PR to add this information to the release notes in Syntax Spec (though we later learned this introduced version incompatibility was likely not intentional).

Eutro started porting the parallel implementation from v2 to v3, but we soon learned that although the changes in Qi to migrate to v3 were only syntactic changes, in fact, the underlying machinery had undergone significant changes as part of the move to v3. This complicated the migration for parallel and it didn't look like it was going to be a simple port, after all.

Eutro observed that the current operation of Syntax Spec carries out expansion, at phase 2 (the DSL's "phase 1"), essentially as a fold operation over a list of syntax. This supports scopes being reduced in a nested, tree-structured way. But parallel can no longer expand in that way, and we now needed to employ a tree fold, instead. She shared an amusing paper on the subject and started to implement the advocated approach in the Syntax Spec expansion pipeline, which of course involves the formidable expansion continuations.

Although she made a lot of progress, it looked like it was going to be a longer undertaking than we at first assumed. In retrospect, it's good that we submitted the Syntax Spec PR with the v2 version, as it starts the conversation on what is proving to be a longer-term undertaking. There have been some interesting discussions there since it was posted.

As it would be necessary to ensure that tests continue to pass after such changes as we were hoping to make, Dominik tried to run the Syntax Spec tests, and found that some of them would not run. He made the necessary changes to get them to run and submitted a PR to Syntax Spec.

So in the end, we had each submitted one PR to Syntax Spec! Won't d'Artagnan (aka Michael) be glad 😝. Of course, he is hard at work on his dissertation, at the moment, and plans to defend it in the coming weeks, so we knew that these discussions may not resolve in the near future.

A lot of our recent explorations (e.g., inlining, bindings) have been around Syntax Spec, and those are likely to be grounded for the time being. So we felt it might be a good time to return to other endeavors like deforestation.

Dominik is headed to Germany and plans to join the Qi meeting from there next week. We realized that, over the years, people have joined from all manner of places: a beach tent in France, a family living room in Mexico, a camper van in the Alps, from Brussels, Italy, California, Boston, Prague, Taiwan, Cambridge, London, Seattle, Virginia, and a lot more places! We wondered if we should make a leaderboard of people and the places they've joined from, as a friendly competition among Qiwis (although Dominik is surely far in the lead, and it seems that it would be difficult for others to catch up!).

(Some of these are carried over from last time)

• Implement DAG-like binding rules for branching forms
• Implement try exception binding and start a PR for review.
• Return to developing Qi's theory of effects, including accounting for binding rules.
• Write phase 1 unit tests for inlining.
• Create an issue for the general bindings syntax to get feedback on it.
• Formalize Qi's semantics using Redex.
• Start organizing qi-lib into qi and qi/base collections
• Invite Sam to tell us about data sharing approaches used in the uke library
• Fix linking of bindings issue in Qi docs.
• Ready the inlining PR to be merged and tag for code review.
• Publish qi/class in some form.
• Verify whether the call-with-values performance discrepancy exists on ARM machines, too.
• Take the next small steps on deforestation architecture.
• Define the define-producer, define-transformer, and define-consumer interface for extending deforestation, and re-implement existing operations using it.
• Write more reliable nonlocal benchmarks (in vlibench)
• Undertake a "fantastic voyage" to get to the bottom of the performance puzzle in using compose-with-values. [see also: PR #191]
• Implement more fusable stream components like drop, append, and member. [issue #118]
• Why is range-map-car slower against Racket following the Qi 5 release?
• Ensure (eventually) that both codegen and deforested runtimes are included in the info struct and not in the IR.
• Resolve the issue with bindings being prematurely evaluated. [issue syntax-spec#61]
• Fix the bug in using bindings in deforestable forms like range [issue #195]
• Write a proof-of-concept compiling Qi to another backend (such as threads or futures), and document the recipe for doing this.
• Review Cover's methodology for checking coverage (e.g. wrt. phases) [related issue: #189]
• Improve unit testing infrastructure for deforestation.
• Decide on appropriate reference implementations to use for comparison in the new benchmarks report and add them.
• Decide on whether there will be any deforestation in the Qi core, upon (require qi) (without (require qi/list))

Dominik, Eutro, Sid