Qi Meeting October 31 2025

Adjacent meetings: Previous | Up | Next

We dressed up for Halloween and reviewed some challenges with expressing Qi's scoping rules in Redex, and discussed inlining challenges.

Since today's meeting was going to fall on Halloween, we decided to reveal our true selves that we keep hidden away on other days of the year.

We've made progress on inlining and formalizing semantics lately.

Sid revealed himself to be a vampire pirate. Dominik initially appeared as a glowing pumpkin, but then transformed before our very eyes into Riff Raff. Eutro appeared as the letter E.

Eutro hopes to use Qi as one concrete application of a general approach to ensuring hygiene through code transformations (based on Set of Scopes) that she's developing for her thesis.

By using set of scopes in the formalization of bindings, this approach could avoid the need for frequent renumbering when employing DeBruijn indices. This problem is comparatively mild in lambda calculus settings where the scoping structure is explicit, but may be more pronounced in languages with implicit scoping structures, such as Qi.

In the past, one approach to formalizing bindings we've considered is to translate bindings into flow values at a certain indices. Each new binding would introduce a new implicit flow value. We discussed today that, as we can determine the free variables at each point in the flow, and, knowing how many there are (say N), we could reserve the first N flow values (or the last N values) for these bindings, rewriting flows to marshall these accordingly.

We felt that this is a viable approach and analogous to DeBruijn indices, but it could be quite tedious, and marshalling these implicit values at every point in the flow does not sound easy. By virtue of this same analogy with DeBruijn indices, Eutro suspects that using a set-of-scopes based formalization would be more appropriate and tractable for a language like Qi.

Eutro took a stab at declaring Qi's scoping rules in Redex. (as) bindings now reduce to (gen) (as they are grounded, producing no values), while also declaring substitutions.

The substitutions are notated using the #:refers-to keyword argument on a reference. But this did not achieve the desired results. It may be that this form assumes that it is used within the textual scope of a Racket-style binding, whereas Qi's bindings, while lexical, are not textually contained in a binding form, so it may require special handling, or might require a different approach. It might be worth asking about this on Discord to get some leads on what it would take to encode these binding rules.

Eutro spoke to Michael recently and discussed hygiene, as she's currently planning how to approach her thesis. Inlining is one form of substitution that could employ this approach, and developing such applications feels like a useful focal point for her work.

We had recently run into a difficulty applying this to inlining, however, where Syntax Spec was dropping the scope that was added as part of inlining. It turns out that having Syntax Spec preserve this priori scope would be a somewhat fundamental change rather than only superficial, as Syntax Spec translates scopes in nontrivial ways. Still, it sounds like even without the extra scope, we expect hygiene to work properly (TODO: why?). As we discussed last time, we could write a lot of tests to check especially:

1. Both use site flow and inlined flow (defined using define-flow) use (different) bindings with the same name.

2. The same flow is inlined more than once.

Additionally, the other issue that remains to be addressed is coming up with a way to propagate syntax properties through compiler rewrites. Ideally, if this is a general way, it could also be used to propagate the nonterminal property that we currently do in an ad hoc way.

For now, Eutro rebased the inlining PR and pushed the latest changes. It isn't yet ready to merge as we still need to address the above issues.

Ferdy does a special trick around Halloween time, "Boo!" (which is secretly just a different name for the same trick that he does at other times of the year when it's called "Meerkat," but he knows that us silly humans don't use free-identifier=? to resolve the bindings and are easily fooled).

Ferdy didn't make an appearance during the Qi meeting as his costume wasn't ready yet. We are still working on it, and I'll post a picture here if we get around to finishing it.

(Some of these are carried over from last time)

• Add bindings and effects to the Redex semantics.
• Incorporate Chai into Qi.
• Implement a compile-time table of known arities and add an entry to it as part of define-flow.
• Ready the inlining PR to be merged and tag for code review.
• Write phase 1 unit tests for inlining.
• Define the define-producer, define-transformer, and define-consumer interface for extending deforestation (also encapsulating both naive and stream semantics in the definition), and re-implement existing operations using it.
• Implement the remaining producers and transformers in racket/list for qi/list.
• Attach a deforested syntax property in the deforestation pass, and use it in compiler rules tests (instead of string matching).
• Improve qi/list and deforestation testing by writing a macro to simultaneously test the expansion and the semantics.
• Investigate whether the deforested operations could be expressed using a small number of core forms like #%producer, #%transformer, #%consumer, and #%stream.
• Decide on whether there will be any deforested operations provided in (require qi) (without (require qi/list))
• Review which racket/list forms are actually needed in qi/list
• Come up with a good way to validate the syntactic arguments to range using contracts.
• Start organizing qi-lib into qi and qi/base collections
• Publish qi/class in some form.
• Implement DAG-like binding rules for branching forms [Syntax Spec parallel binding-spec PR]
• Formalize Qi's semantics using Redex.
• Incorporate effects and bindings into Qi's pen-and-paper semantic model.
• Return to developing Qi's theory of effects, including accounting for binding rules.
• Write a proof-of-concept for implementing code generation from abstractions of "flow" and "connective tissue" that are set by a context parameter.
• Why is range-map-car slower against Racket following the Qi 5 release?
• Decide on appropriate reference implementations to use for comparison in the new benchmarks report and add them.
• Add reader flow syntax in #lang qi
• Develop a backwards-incompatibility migration tool using Resyntax, to be used in the next Qi release.

Dominik, Eutro, Sid