Inlining Recursive Definitions and Other Tricky Cases

Qi Meeting October 24 2025

Adjacent meetings: Previous | Up | Next

Summary

We returned to discussing inlining and Eutro's in-progress PR to implement this for Qi.

Background

A little while ago, Eutro started a PR to inline Qi definitions. Unfortunately, we hit the doldrums after encountering several challenges with inlining across the separate compilation boundary.

Some Challenges with Inlining

We had discovered a number of challenges with inlining separately defined flows, some time ago. Eutro returned to working on it this week and identified the following comprehensive issues to be resolved (along with some proposed solutions):

1. Mutually recursive definitions encounter an infinite loop.

Racket employs a two-pass expansion which first discovers definitions and then resolves references. This is how it is able to resolve forward and recursive references. Preemptively inlining a definition therefore doesn't work if the referenced binding doesn't exist yet. This especially breaks in the case of mutually recursive definitions, where the request to expand the other definition on-demand in the "first pass" doesn't work because that definition hasn't been resolved yet (TODO: clarify).

Eutro proposed to address this by the use of promises. The on-demand expansion would be wrapped in a promise, i.e. Racket's delay. Then, it will be forced and evaluated at some point before it is actually needed (TODO: where?).

2. Referenced identifiers that are inlined do not draw binding arrows in DrRacket / Emacs.

This is because these identifiers are actually inlined at compile time and no longer exist as identifiers. Racket provides a standard mechanism by which we can track that this has happened, which is to add a disappeared-uses syntax property to the syntax replacing the identifier.

This approach worked, and the binding arrows were now being drawn, but in certain cases we found that it was again no longer happening. We realized that this happened if any Qi compiler pass performed an optimization, as the syntax property was not being propagated as part of rewriting the syntax.

We used syntax-track-origin in the qi0->racket codegen pass to preserve the property, and that handled a few cases, but we realized that others were still failing because some other pass was failing to propagate the syntax property.

We noted the close analogy with the problems we've encountered with propagating the nonterminal syntax property (which conveys to the Qi compiler's traversal strategy aka find-and-map/qi which syntax is valid to traverse), and how rewrites always need to preserve this property.

A General Solution for Preserving Syntax Properties?

We felt that instead of manually propagating each syntax property, it would be preferable to have a general solution that ensures that syntax properties are always preserve through rewrites, both in the Qi compiler as well as in the Qi expander (implemented in Syntax Spec).

3. Hygiene guarantees are unclear if introduced bindings have the same name as use-site bindings

In the case where the syntax being inlined contains bindings or references, it is essential to ensure that when it is inlined in a separately defined flow, that the bindings are appropriately scoped and do not interfere with those in the inlining context.

Eutro proposed a simple solution: add a fresh scope before inlining the flow! This is a tried and true approach that underlies the implemenation of hygiene in macro expansion, where expansion introduces a macro definition scope that is absent at the use site. Eutro is in fact hoping to develop this approach, in the abstract, as an alternative formal model for bindings in lambda calculus (e.g., alternative to DeBruijn indices), which could allow proofs to become simpler and for bindings to be used without too much ceremony.

Yet, this elegant solution unfortunately didn't work in the inlining implementation, as, internally within Syntax Spec, the freshly added scope was being dropped.

We do not know why this happens, and wondered whether this should be considered a bug, and that Syntax Spec expansion should not affect any a priori scopes.

But we also didn't know exactly what the behavior is right now if we don't add the scope. Could it be that it already works correctly, by some unknown accident or intent?

We felt that a simple way to proceed, without requiring upstream changes in Syntax Spec, is simply to write a comprehensive set of tests for different scoping scenarios that we can think of, and if the tests all pass, we will consider that hygiene is working as intended. Of course, this isn't as good as a conceptual argument for soundness based on an actual model of how things work, but it may be practical.

Release Practices

If the tests pass, ship it! That's Qi's current release policy. We discussed that the implications of this need to be thoroughly understood and described in user documentation to cover every possible use case and guide users and library authors alike as to the best ways to use Qi with the versioning guarantees that they need. Sid had started to work on this a while back and, in trying to understand the ideal versioning and distribution schemes and any compromises that may be necessary for Racket's specific ecosystem, there were some very interesting directions brought up by Sage and Greg that we haven't had a chance to follow up on and explore further.

qi-redex Released!

We noted that Eutro's PR has a dependency on redex-gui-lib even though we don't use any GUI functionality. We investigated and managed to avoid that dependency, and then, now that the tests were all passing and everything looked good, merged the PR!

Modern Times

The recent AWS outage apparently caused some beds (actual beds) to spontaneously turn their heating up to the max, so that people weren't able to sleep in them! We were frightened to imagine if "smart" cars or other less passive devices threw a fit because they couldn't access the cloud!

We also discussed pokemons and getting more sleep, whether it's just dozing, snoozing, or even slumbering.

Next Steps

(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.

Attendees

Dominik, Eutro, Sid, Stephen