Augie Doggie, Dodgy DAGy

Qi Meeting July 16 2025

Adjacent meetings: Previous | Up | Next

Summary

We resumed our discussion of ways to close the box on Cassandra's binding, and came up with a few more options. We also merged a recent PR improving some binding rules.

Background

Recently, we've been discussing some options for implementing DAG-like binding structures for branching Qi forms like -< (tee) and == (relay), in order to avoid undesirable dependencies across branches (or tines) of such otherwise "parallel" flows.

Dodgy DAGy Binding Structures

As the desired tee junction scoping rules are "DAG structured" rather than tree-structured, Syntax Spec on its own cannot ensure them during expansion.

We'd already come up with a few options to get around this:

Runtime Binding Checks

With hybrid compile-time / runtime checking, we could check weaker rules at compile time, and assert remaining checks at runtime. We felt this was undesirable as it would mean that different runtimes (e.g., functions vs futures) for Qi would need to implement their own, independent checks.

A Compiler Pass to Enforce Binding Constraints

A second option (discussed last week) was to introduce a new compiler pass that would traverse the syntax and assert the DAG-like constraints in the form of:

1. Excluding peer references in branching forms.
2. Excluding shadowing of peers to avoid ambiguous binding downstream.

… raising a compile-time error in each of these cases.

We felt that this option was feasible, and Michael had suggested that we could use compiled-identifier=? and get-racket-referenced-identifiers from Syntax Spec to do it in a sound way. At the same time, he did point out that while this approach would achieve our minimum requirement of precluding peer dependencies, it would not truly achieve DAG binding structure.

However, note that this does not yield quite the same thing as the DAG structure, because it rules out the following program:

(~> () 1 (as x) 2 (-< (as x) (gen x)))

With DAG-structured scope this program would be legal and would return 1, because the reference in the second tine [...] would refer to the binding from before the tee [...] ignoring the binding in the first tine [...].

"There and Back" Bindings

One remaining unknown was that we were unsure of whether get-racket-referenced-identifiers would gracefully handle the presence of bindings in a nested Qi flow within an escaped Racket expression:

(~> (3) (esc (☯ (as x))) (gen x))

One expectation here could be that it should work and produce 3.

But another expectation could be that, as the nested, re-entrant flow is a Racket (rather than Qi) expression, bindings would not escape the esc, and would be unavailable downstream according to Racket's binding rules for ordinary expressions.

Finally, the nested expression in this case returns to Qi, but it could also enter a different DSL with different scoping rules that may contradict Qi's, for example, a "Nemesis Qi" that unbinds downstream as Qi binds downstream, making downstream binding ambiguous even if we ignore the Racket intermediary between the two languages.

On this basis, Sid felt that "there and back" binding isn't well defined in general without a specification of the boundary behavior between each pair of languages being available to Syntax Spec. In any case, we felt it would be OK to disregard such bindings, as long as we do so gracefully without error. We felt we would need to experiment and see what happens when we try this.

In the meeting, we discussed a few more options:

Manually Add and Remove Scopes

Expansion of Qi syntax occurs in a "nested" way, that is, even in branching forms like ==, each succeeding branch is nested inside the preceding branch, with the downstream syntax ultimately being nested inside the last tine. This order of expansion is effectively a tree, and it is due to this order of control flow that bindings must also follow a similar structure --- that is, only tree-structured binding rules are expressible in Syntax Spec (TODO: is this accurate?).

Update, July 17th: Dominik wrote a blog post concisely explaining the difficulty to a lay audience.

Since succeeding tines are nested in this way and would have scopes from preceding tines, we could introduce a new compiler pass that would reflect on the scope sets on the syntax and manually remove scopes introduced by bindings in each tine of branching flows from subsequent tines, finally reintroducing them downstream (since the tines should bind downstream).

This compiler pass would occur right after expansion, before normalization (and before the in-development inlining pass). The pass needs to be done early so that we can treat it as being conceptually part of expansion. This is useful as we may, for instance, desire to write optimizations that perform some analysis of bound and free identifiers, eliminating unused or superfluous bindings, and so on. Eutro pointed out that Racket doesn't currently provide a utility to check whether one identifier binds another, that is, there's bound-identifier=? which is too strict for our purposes, and free-identifier=? which is too lax, but there isn't currently a bound-identifier<=? which would be what we would need here. She said she would consider submitting a PR to add one to Racket. That would help us write bindings-related optimizations.

In any event, to modulate the scopes in the aforementioned way, we would need some way to reflect on and determine the scope sets at play, but there wasn't an obvious approach we could use here. Eutro mentioned one hacky possibility, of artificially introducing a binding, then introspecting it to discover the set of scopes present there, and then doing the same for subsequent branches and downstream, and finally using syntax-delta-introducer to obtain the scopes introduced by each branch (if any), which we could then use to make the necessary scope set changes! This would be quite fiddly, and would involve a lot of changes to the implementations of the branching flows themselves.

Expose Binding Primitives

The above solutions assume we cannot solve the problem at the expansion stage. We discussed a few more options that revisit this assumption.

Syntax Spec currently provides a mini-DSL for expressing tree-structured scoping rules or "binding specs," e.g., nest, nest-one, and so on. It could potentially provide an "escape hatch" into underlying Racket primitives expressing scope, which would allow us to manipulate them directly to attach and remove the scopes we need. This could be done in the expander via a special escape syntax offered by Syntax Spec, or, perhaps, a compile-time utility could be provided that would formally support the previous solution discussed (e.g., a way to introspect scopes), so that it's less hacky.

The advantage of doing this in the expander would be that instead of having to remove and reattach scopes attached during expansion, we could attach the intended scopes, to begin with.

Eutro did a quick survey of the Syntax Spec code and concluded that it may be hard to do this.

Add a New parallel Binding Spec

Last week, we discussed that the current tree-structured scoping rules are analogous to Racket's let*. Syntax Spec doesn't currently provide a way to encode rules that are more like let, where the binding clauses don't bind one another, and only bind "downstream" in the body.

A final option we considered was to introduce a new parallel binding spec in Syntax Spec, in addition to nest and nest-one. This binding spec wouldn't nest at all, but instead, would attach scopes on the different branches independently.

Eutro set to work on this to see if there would be any challenges, as we feared there would be given Michael's initial hesitation to support DAG rules of this kind.

Yet, if it's feasible, it would be the ideal solution since it would allow Syntax Spec to formally support such otherwise "dodgy" (as Eutro put it) DAG binding structures, and it could be formally and cleanly checked during expansion, without requiring patches at the DSL level.

Many Creeping Things

Things seemed to be going suspiciously well for a while, and Eutro was happily adding parallel support in various parts of the Syntax Spec code while Dominik and Sid discussed the finer points of benchmarking.

That is, until Eutro ran into some odd code that appeared to be recursive, but we couldn't find the recursive call. Tracing through it, it seemed to defy our assumptions of what it would do next. We gradually had the sense it was using some form of continuation-passing style, or perhaps "recursion-passing style," a complex "recursion spaghetti." We soon realized that we were looking at none other than the famous "expansion continuations" that Michael had spoken of a long time ago. It did seem that incorporating parallel into this scheme would prove to be a bit mind bending, so we left off there for the moment, at least with a clearer understanding of the challenges. Perhaps we'll pick up on this next week and see if we can make any progress.

Update, July 17th: Eutro has a working proof-of-concept! She reports:

I added one (1) extra field to nest-call which tracks the initial scopes of a (parallel f inner) binding spec. I add only those when expanding each f, but add all the accumulated scopes when expanding inner.

Merging the Bindings PR

In the meantime, we merged the recent PR improving some binding rules, and which fixes a bug that Jair had reported with ==* not binding as expected. We waited and saw that all the CI jobs passed. And with that merge, Eutro is officially a Qi committer! 🎉

Although, of course, Qi's commits (and indeed, commits in any project) are just one clue to the underlying contributions, and DIA (the process applied to Qi to track attribution, as part of prototyping Attribution Based Economics) does not rely on it as the source of truth. For instance, a lot of commits made during Qi meetings are made using Sid's account just because his super Emacs setup 😎 (he likes to believe) makes it convenient to do it that way.

Emacs Configuration Management

Eutro is working on a configuration management tool, an alternative to use-package that groups elementary units of configuration in ways that aren't coupled to packages, and which are reusable across similar customization domains (such as having certain keybindings across different programming languages). The configuration primitives also wrap underlying Emacs customization facilities in such a way as to make them invertible, in many cases. Dominik has a minimal Emacs config and he uses built-in ELisp primitives to manage it, but Sid does use use-package and has run into some of the problems that Eutro's approach might ameliorate. So he was quite excited and volunteered to be a beta tester.

Next Steps

(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.
• Consider defining a formal semantics for Qi 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))

Attendees

Dominik, Eutro, Sid