Qi Meeting July 30 2025

Adjacent meetings: Previous | Up | Next

We returned to discussing deforestation and came up with some next steps. We continued with formalizing Qi semantics using Redex, sans bindings.

We haven't worked on deforestation in some time, but we knew that there weren't any blockers there.

We've recently felt that it would be valuable to have a reference semantics for Qi, independent of any implementation.

There were several old conversations around deforestation that we attempted to recall, including:

• how can we specify both naive and deforested semantics in the defining form for deforestable streams, i.e. define-deforestable?
• should we broaden our core language to explicitly model such streams using #%producer, #%transformer, #%consumer as well as fused #%stream forms?
• can we simplify parsing of deforestable forms and avoid the use of complicated syntax classes?

Many of these were summarized some time ago when we identified small steps for continuing on deforestation.

In today's discussion, we felt that deferring discussion of core forms would be wise and that we should continue to use #%deforestable on its own, for now. Although our development so far leads us to suspect that producers, transformers, and consumers are a natural taxonomy of stream operations, we have implemented relatively few such operations in the grand scheme of things, and it's possible that more implementations would reveal patterns that don't fit into these ideas. It would be better to allow these future implementations to suggest the right organizing ideas in retrospect than to constrain ourselves prematurely with organizing ideas discerned from what may not be a representative sample.

We agreed that the next steps are:

1. Modify define-deforestable to include a specification of both naive as well as stream semantics.
2. Implement remaining stream operations analogous to racket/list that we identified some time back.
3. At the end, review whether there is a small set of core forms that could be introduced that would express all of the stream operations.

For the first, we felt that it would make the most sense to reuse the existing compile-time deforestable-info struct that was introduced to carry the naive runtime through compilation.

Although our recent attempt to formalize Qi semantics using Redex was thwarted by the apparent absence of a convenient way to notate Qi's binding rules, we discussed that it would still be valuable to formalize the rest of the semantics --- that is, the semantics, sans bindings.

To do this, to the basic syntax we had notated last time, we added the on interface macro. Even though it isn't part of the Qi language, as it entails the operation of Qi flows on actual values, it's essential to allow us to express the meaning of flows.

Towards this, we also defined some basic reduction rules on the thread form, similar to normalization rules in the compiler. We used Redex's testing utilities to verify that actual Qi expressions did reduce to values as encoded in our fledgling semantics.

#lang racket

(require redex)

(define-language qi
  (floe (~> floe ...)
        (-< floe ...)
        (== floe ...)
        (>< floe)
        f)
  (expr (on (value ...) floe)
        (values value ...))
  (value number)
  (f variable-not-otherwise-mentioned))

(define-metafunction qi
  Σ : number ... -> number
  [(Σ number ...)
   ,(apply + (term (number ...)))])

;; need to express conditional recursive rules like this:
;; (if (--> (on (value ...) floe)
;;           (values value ...))
;;         (--> (on (value ...) (~> floe floe_2 ...))
;;              (on (value ...) (~> floe_2 ...))))

(define thread-step
  (reduction-relation qi
    (--> (on (value ...) (~>))
         (values value ...))
    (--> (on (value ...) (~> floe))
         (on (value ...) floe))
    (--> (on (value ...) +)
         (values (Σ value ...)))))

(redex-match?
 qi
 floe
 (term (~> f g h)))

(redex-match?
 qi
 expr
 (term (on (1) (~> + -))))

(redex-match?
 qi
 floe
 (term (-< f g h)))

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

(test-->> thread-step
          (term (on (2 1) (~>)))
          (term (values 2 1)))

(test-->> thread-step
          (term (on (2 1) +))
          (term (values 3)))

(test-->> thread-step
          (term (on (2 1) (~> +)))
          (term (values 3)))

This was just a start, and there's a lot more that we would need to do to have a full semantics. Eutro suggested that writing out the small step semantics using pen and paper could be a good step to get an idea of what we'd like to achieve with Redex here.

(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