Outlining Inlining

Qi Meeting Apr 25 2025

Adjacent meetings: Previous | Up | Next

Summary

We discussed what inlining independently defined flows would look like, and some potential challenges with inlining higher-order flows. We got buy-in from C-levels on Qi Enterprise Edition™ (QiEE™).

Background

Last week we discussed the problem of compiling independently defined flows, which might miss optimizations that would have been possible if they had been defined inline. We felt that using compile-time metadata — specifically the use of persistent symbol tables — could facilitate inlining of such flows so that they can be compiled together.

General Approach to Inlining

We felt that we could modify define-flow (but consider Racket's define to be out of scope) to store the surface syntax of the flow definition in a persistent symbol table (available from Syntax Spec) keyed by the name of the defined flow. Then, at the very first stage of compilation, prior to normalization (i.e., right after expansion), we could introduce an inlining pass which would inspect any flows used as identifiers to see whether they have an entry in the persistent symbol table. If an entry is found, we replace the occurrence of the flow identifier with its definition.

"0th Order" Flows

For flows that do not name their arguments (regardless of how many they accept — so not only "0th order" in the sense of accepting no arguments), we noted that it would be trivial to inline them, as it would be a simple context-free transformation of the flow reference to its definition. This may in fact capture a majority of cases.

1st Order Flows

For flows that are not parametrized by other flows and which operate directly on the input arguments, we didn't see any issues with being able to inline definitions. But as define-flow also supports being able to bind arguments, we might need to handle those in a special way.

In addition to the transformation of the reference to the definition, it may be necessary to preface the flow with (~> (-< (as arg-spec) _) flow-definition) [note: I thought of this while writing these meeting notes — to be discussed next time].

One thing that might present some nuance is that as bindings are scoped to the outermost threading form. So if an argument to the flow being referenced happens to be named x, then inlining it using the as preface could potentially spoil the scope of any variable in the containing flow that may also be named x. So it would be necessary to apply some form of "hygiene" here, perhaps just the old school use of gensym would suffice.

Higher Order Flows

There are a few different ways we might use higher-order flows within a flow definition.

A Macro

If the flow is written as a macro:

(define-qi-syntax-rule (my-filter f)
  (filter f))

(define-flow my-pipeline
  (~> (my-filter f) (map g))

… then there are no issues as the expansion happens prior to compilation, in any case, and it wouldn't even need to be inlined.

A Function

(require qi)

(define-flow my-filter
  filter)

(define-flow af
  (~> (my-filter odd? _) (map sqr _)))

(af '(1 2 3 4 5)) ;=> '(1 4 9)

In a case like this with a higher-order flow, we felt there might be challenges in inlining it. However, in this particular example, we are not using qi/list, so map and filter here are Racket functions, and as such, they are outside the scope of the Qi compiler and likely do not need to be inlined.

But it could be this, instead:

(require qi qi/list)

(define-flow my-filter
  (~> (relay (as f)
             (filter f))))

(define-flow af (~> (my-filter odd? _) (map sqr)))
(af '(1 2 3 4 5)) ;=> '(1 4 9)

Here, my-filter indeed expands to, effectively, a simple (filter f). But there are some fiddly aspects, including binding inputs to names, and the fact that at the use site, this is used with template application syntax as a Racket function.

We noted that even if it were inlined:

(define-flow af
  (~> (~> (relay (as f)
                 (filter f))) (map sqr)))

… it's likely that this would not get deforested today since it does not match any of the standard patterns for fusable sequences. Now, the as binding would in fact get lifted out of this expression into a containing let at the stage when we translate Qi bindings into Racket bindings, and at that stage, filter and map here would in principle be sequential without any messy binding forms being involved. Unfortunately, this happens after the operation of the Qi compiler, as the final stage after code generation to Racket. So during the operation of the Qi compiler, we would still be seeing the as form, and that would not match any current patterns we have for deforestation.

But at least, there is a chance that future cleverness in the compiler would manage to deciper such patterns as being deforestable.

Additionally, with this example, although we bind the variable f within the flow here, we could have also defined my-filter as:

(define-flow (my-filter f vs)
  (~> (== ⏚ _) (filter f)))

So there are such permutations to consider.

We could use the same "hygienic as trick" as before to handle the binding of inputs in case there are any done at the Racket level as in this second version, so that could be OK.

(define-flow af
  (~> (~> (-< (as f-1 vs-1) _) (== ⏚ _) (filter f-1)) (map sqr)))

On the other hand, the flow is used as:

(my-filter odd? _)

… which is syntax for template application of a Racket function. In attempting to inline the flow, it might be necessary to handle all the permutations of partial and template application at the use site, in order to determine how to inline the definition.

This might be especially fiddly.

Takeaways

We concluded that it's valuable to do this kind of inlining, as we want to do whatever we can to encourage structured programming, and such good practices should not come at a performance cost.

We should be able to inline flows that do not name any arguments, and for flows that name their arguments at the Racket level, we could probably use gensyms together with as to facilitate inlining. Although in the latter case we do not currently have any optimizations that would benefit from inlining, it at least opens the door to the possibility. Finally, at the use site, we will only handle inlining of flows used as identifiers, i.e., which do not use partial and template application syntax that is intended for general use with Racket functions. We could consider supporting those permutations in the future.

OKRs for Qi Enterprise Edition™

In related news, the newly formed Qi Enterprise Edition™ (QiEE™) Business Unit (QiEEBU) convened, and there was broad agreement that it's high time to commence work on Qi Enterprise Edition™ in earnest. In the initial discussions, we agreed that we will next:

• set milestones
• do market analysis to determine appropriate licensing fees
• likewise for consulting fees
• define a suite of value-added services we could provide, after studying the Red Hat model

We felt that it would be wise to also define OKRs and KPIs as we embark on this initiative under tight development timelines, including especially Lines of Code shipped / day, among other quality indicators.

Next Steps

(Some of these are carried over from last time)

• Write a proof-of-concept for using a persistent symbol table.
• 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, Sid