Qi Meeting Nov 22 2024

No More Unknowns!

Qi Meeting Nov 22 2024

Adjacent meetings: Previous | Up | Next

Summary

We discussed the in-progress PR integrating the deforestation extension POC into Qi, got the remaining compiler tests to pass, and discussed some interesting implementation choices facing us.

Background

Last week, we completed the POC for extending deforestation to custom list operations, and in the interim, Sid started a PR to integrate it into Qi. So far, only the map function has been translated to use the new way, and the user-level tests are passing though some compiler-level tests are not. In general, things are looking on track for a smooth integration.

In the actual PR, Sid is using a temporary #%deforestable2 core form to introduce the desired implementation in parallel with the existing implementation (that uses the #%deforestable form), so that we can preserve the existing functionality while we introduce the new stuff and test things incrementally as we go. But since that's just incidental, we'll just pretend it's already called #%deforestable when we talk about it here, as that is what it will eventually be renamed to when the old implementation is fully translated.

Are We Compiling Subexpressions Correctly?

As we reviewed the current state of things, we wondered whether our implementation would correctly handle a nested case of deforestation, for instance something like:

(~> ('((1 2 3) (4 5 6) (7 8 9))) (map (foldl + 0)))

Would the inner expression be correctly expanded and compiled?

Given that the inner expression here is declared as a floe in the core language grammar for the #%deforestable form that map expands to, we concluded that it would at least be expanded correctly.

As for whether it would be compiled correctly, we discussed this recently and felt that each compiler pass would be responsible for fully traversing the syntax and doing any optimizations within its purview. In this case, the expansion would be something like:

(map (foldl + 0))

→

(#%deforestable map info (f (foldl + 0)))

→

(#%deforestable map info₁ (f (#%deforestable foldl info₂ (f +) (e 0))))

… where the + and 0 would likely end up being wrapped in (esc (#%host-expression ...)), as usual, for expressions that are designated to be handled as Racket expressions after Qi expansion -- but we needn't worry about this for the purposes of discussion here.

This expression would then be passed through the various stages of compilation, where, for instance, the deforestation pass would need to traverse into it, including the inner foldl component, and apply optimizations to any floe positions that match an expected pattern for the optimization (which there wouldn't be any in this example).

We weren't sure whether the deforestation pass already does this today or not, but if not, we will need to add it in order to ensure that the floe positions are already fully compiled when we reach the code generation stage.

Failing Compiler Tests

As mentioned earlier, the user-level tests are currently all passing, but there are some failing compiler tests. This suggested that although the new map form was functioning correctly in terms of inputs and outputs, it wasn't actually being deforested. More specifically, the end-to-end behavior was correct, and it was falling through compilation to use the codegen we provided in the new define-deforestable definition (adapted from define-optimizable-op in the POC), without employing the optimized runtime provided by stream fusion.

Upon review, it looked like the problem was just that the match patterns in the deforestation pass needed to be updated to use the new syntax. But even after we made the change, the tests were still failing. It turned out that this was because our syntax for the new form was something like:

(#%deforestable name [tag e] ...)

But in our expansion machinery the name here was being replaced with the info "compile time metadata" struct instance that carries the codegen.

(define-syntax info
  (deforestable-info codegen-f))

(define-dsl-syntax name qi-macro
  (op-transformer #'info #'(spec ...)))

… where op-transformer writes the final expansion as something like:

#`(#%deforestable #,info [tag e] ...)

So the fact that it was working at all was a coincidence since the #%deforestable form expects an identifier as the first argument, and that's what it was seeing, even though it wasn't the actual name of the deforestable interface.

As we need to preserve the name of the original form for the purposes of pattern matching in the compiler, we modified the extension macros to add a distinct name argument, and use that here as:

(define-dsl-syntax name qi-macro
  (op-transformer #'name #'info #'(spec ...)))

… where op-transformer simply retains it as the first argument in the expansion.

#`(#%deforestable #,name #,info [tag e] ...)

This now caused the compiler tests to pass!

Out of Range

Our POC didn't include support for a case version of the deep macro, that is, where there might be multiple valid syntax patterns that may produce variant expansions.

We discussed and agreed that by the time the deforestation pass gets the syntax, it should already be normalized so that that form should not be responsible for, for instance, understanding that (range 10) is equivalent to (range 0 10 1) any the various permutations here.

We felt there were a few options to achieve this normalization. Either:

1. We could extend the macro to allow defining optimization rules for each individual compiler pass, so that normalization rules could be specified that rewrite the variant syntax patterns to a canonical form. Something like:

(define-deforestable
  (range [e low] [e high] [e step])
  (normalize
   [(range high) #'(range 0 high 1)]
   [(range low high) #'(range low high 1)])
  (deforest
    [pat tmpl]
    ...)
  #'(λ ()
      (r:range low high step)))

This seemed cool, but perhaps too cool, as it could allow gratuitous modification of the compiler to achieve goals that would have better solutions.

2. We could add rules to the normalization pass to rewrite the variant forms of range to a canonical form.

This seemed inadvisable since range is not a core language form, and writing normalization rules for #%deforestable that are specific to particular extensions like range seemed like a bad idea. We could consider including range in the Qi core, but as range isn't in racket/base but only in racket/list, that precedent seems to make an argument to keep range out of the Qi core as well.

3. The macro itself should be extended to support cases (like syntax-case vs define-syntax-rule), and the macro author should rewrite each case to the canonical form in the templates.

This third option seemed best, but in case that presents any challenges in implementation, we also came up with a clever hack to sidestep this issue.

A Clever Hack

For now, we could just write a single, canonical form of range that accepts three arguments, and call this ... range2. Then, we can write an ordinary Qi macro called range that rewrites the variant syntaxes of range to the canonical form of range2. It is range2 that would be the actual form being deforested under the hood, but this would be abstracted from the user behind the ordinary range macro, and they would not know the difference.

Freaking brilliant, man.

Of course it would be annoying to remember about range 2 in the codebase if it were there to stay, but it would be a quick way to get this POC integrated and the functionality where we want it for the purposes of unblocking further work on deforestation, so we just might do it, depending on how things go with trying to add a case version of define-deforestable. The difficulty on the surface is, we'd like to provide a single codegen, but multiple surface variants expanding to a canonical form. Is there an unambigious way to indicate this?

No More Unknowns!

At this point, Sid proclaimed that there were no further unknowns and it should be straightforward to translate the remaining interfaces to use the New and Improved Way! Dominik was more cautious and said that it's good that at least one of us is optimistic.

Spoiler alert: there were still a few surprises and Sid spent a few more hours debugging things after the meeting 😅

Cool Things to Look Forward to with Deforestation

Our current implementation of deforestation has already abstracted a lot of things so that a few attributes are used to control which implementation is used and how things are composed and so on. That is, the actual fusion implementation largely relies on a comparatively small number of attributes that are set based on whether the surface form is a producer, transformer, or consumer. These three categories entail their own sets of attributes which configure the actual stream components to behave the right way.

One of the things that Dominik has been planning is to use this abstracted infrastructure as the basis for a simple extensible interface presented to those who may be interested in writing custom deforestable (for now at least, list-oriented) operations. This interface could comprise macros like define-producer, define-transformer and define-consumer, which accept minimal specifications from the user that are necessary to set the attributes for these respective classes.

Revealing the Right Interface in a Bottom-Up Way

One of the reasons we haven't already added such macros is that we've deforested a relatively small number of list operations at this time. The syntax classes that provide the abstraction boundary for mapping these surface operations to the underlying stream fusion implementation have been generalized to the point that they adequately serve the needs of these already-deforested operations. But it's possible that as we deforest additional operations, those operations will present new challenges that will require generalizing or otherwise modifying these syntax classes to economically represent the new set of deforestable operations.

So we don't yet know what the right set of attributes is, or whether the abstractions we've defined are quite right yet.

So one line of thinking is, let's continue to deforest more operations and then define the macro interface once we are confident we've seen enough data and have a good feeling about the abstractions, and maybe have already found that we are able to support more interfaces without any further changes to them.

Defining the Interface Up Front

But just to see what this interface might look like, we started to sketch it from Dominik's best guess based on current data.

We came up with something like, basically all of the supporting syntax classes like fst-filter and fst-filter-map would go away, and we'd just need a single one for a fusable stream transformer:

(define-syntax-class fst2
  #:attributes (f next state)
  #:datum-literals (#%deforestable transformer)
  (pattern (#%deforestable _ _info (transformer f next state) _)
    (run-passes #'f-uncompiled)))

This would have the three attributes that have already been discerned for transformers, f, next, and state, and these attributes would be set early on at the macro-defining stage, via the planned define-transformer macro.

(define-transformer
  (filter [f f])
  #'(λ (vs)
      (r:filter f vs))
  ; provide f, next, and state:
  #'(f filter-cstream-next ()))

This would expand to something like:

(#%deforestable name info (transformer f filter-cstream-next ())

… which would be matched by the syntax class pattern in the compiler (i.e. fst2 above).

In this example, the macro author would need to provide an implementation of the stream component, in this case, filter-cstream-next, the continuation-passing-based implementation we currently use. It's possible that, due to the commonalities in the various stream components in the stream fusion implementation, we could even abstract it further and allow the user to indicate just a few parameters that expand to a full implementation of a stream component. But even without that, this interface is narrowly scoped and provides a simple contract for extending deforestation.

After looking at this, we second-guessed our initial thinking regarding only adding this interface at the end, as adding it up front could greatly reduce the amount of boilerplate in the compiler, even in its present form, and could simplify the work of adding support for each new operation in racket/list. It just might be worth it to add this interface up front and then implement the existing operations using these wrapping macros instead of using what would then be seen as the lower level interface, define-deforestable (which the former would expand to, in addition to doing other things). As this interface is being considered private for the forseeable future, we can safely iterate on it and make changes as we add new deforested implementations, so at least, we don't need to worry about things like backwards compatibility yet.

What's going on with raco setup?

These days, make build (a Makefile target that just runs raco setup --no-docs --pkgs qi-lib) is taking forever. On Sid's laptop, it ends up compiling qi-lib, qi-test, qi-cat, qi-sdk, qi-doc, qi-probe and even qi-wiki, an attempt to migrate the Qi wiki to Scribble from a few months ago.

Why does raco build all of these packages when we've only indicated to build qi-lib?

We don't know. It would be great to understand what's going on and fix it so that we can build individual packages and have a tighter feedback loop during development.

Next Steps

(Some of these are carried over from last time)

• Finish incorporating the extension scheme into the Qi codebase and submit a PR for review.
• Implement more fusable stream components like drop, append, and member.
• Define the define-producer, define-transformer, and define-consumer interface for extending deforestation, and re-implement existing operations using it.
• Investigate why make build is compiling a lot of packages instead of just qi-lib
• Update the benchmarking infrastructure (vlibench and also the basic ones in qi-sdk)
• Resolve the issue with bindings being prematurely evaluated.
• Fix the bug in using bindings in deforestable forms like range
• Finalize and document guiding principles for Git commits in the developer wiki
• Revisit extending deforestation to multi-valued settings.
• Write a proof-of-concept compiling Qi to another backend (such as threads or futures), and document the recipe for doing this.
• Ask Ben to review tests from the perspective of Frosthaven Manager.
• Review Cover's methodology for checking coverage.
• Document the release model in the user docs and announce the performance regression (and the remedy) to users.
• Improve unit testing infrastructure for deforestation.
• Discuss and work out Qi's theory of effects and merge the corresponding PR.
• 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))
• Continue investigating options to preserve or synthesize the appropriate source syntax through expansion for blame purposes.

Attendees

Dominik, Sid