Qi Compiler Sync Nov 4 2023

Literally Causing Problems

Qi Compiler Sync Nov 4 2023

Adjacent meetings: Previous | Up | Next

Summary

We reviewed a problem discovered when trying the development version of Qi with Frosthaven Manager, discussed some aspects of the stream fusion implementation, and started to implement the range stream producer.

Background

Recently, Dominik had posted the following polite message in the #Qi Discord channel:

@Ben Knoble Is it to be expected that when I try to raco pkg install frosthaven-manager, nothing works [...]?

... to which Ben responded:

What do you mean by nothing works 😅

They did some testing and verified that building FM worked with the release version of Qi but not the compiler branch. Dominik did some further testing with the Macro Stepper and discovered the underlying problem.

Literal vs Datum

The problem is that formerly we were using datum literal matching in Qi forms. That is, forms like ~> were not considered actual bindings but merely patterns to match verbatim in the input syntax, without there being any meaning attached to the pattern. So something like:

(flow (~> f g))

... would always be treated as valid Qi code and compiled as a sequential ("threading") composition of functions, irrespective of what bindings existed in the calling scope. But in the compiler branch, with the transition to syntax-spec and the desire to have the language be macro-extensible, the matching was changed to be literal matching, meaning that the form corresponds to an actual binding defined by the language, which may be overridden by macros or even other forms in the calling scope.

In the present case of Frosthaven Manager, it imports ~> from Qi and another form with the same name from Gui Easy. As bindings, these were now conflicting in usage like the above example. Yet, since ~> is defined in the qi binding space whereas the one from Gui Easy isn't, we could perhaps safely favor the Qi binding here without raising an error. This may be related to the "quirk" of binding spaces we've talked about before [correction: More accurately, in this case, the binding from Gui Easy was in scope but the one from Qi wasn't: (require racket/gui/easy (only-in qi flow)). The binding spaces quirk pertains to resolving the ambiguity when both are in scope].

We will need to review further the full consequences of this change, including developing testcases that reproduce these consequences, in order to evaluate the scope of backwards incompatibility, and define a set of migration steps to advertise to all users of Qi as part of releasing the compiler work.

Single vs Multiple Value Deforestation and map1

Just as compose1 is a known single-valued and more performant version of compose, we discussed a possible map1 as a known single valued version of map, as an addition to the main Racket distribution. This would allow us to apply the single valued deforestation optimization to a use of map1 while applying a potentially less-performant multi-valued version for uses of map. In fact, we can focus on the former optimization for the initial release of the Qi compiler, assuming we are able to get map1 into Racket in time for release, since, at the present time, we have yet to discover a more performant version of deforestation for multiple values.

A stream producer

So far in our stream fusion implementation, we've got some stream transformers and stream consumers, but we don't have any stream producers except the implicit one that converts a list to a stream. We took a first stab at implementing the range stream producer but didn't get it working yet:

(define (range->cstream-next done skip yield)
  (case-lambda
    [(h) (cond
           [(and h (>= l h)) (done)]
           [else (yield l (add1 l))])]
    [(l h) (cond
             [(and h (>= l h)) (done)]
             [else (yield l (add1 l))])]))

Moving complexity to the pattern matching layer

We also discussed that it might make sense to move part of the complexity of the stream fusion implementation to the pattern matching layer, instead of having a single general purpose stream fusion implementation, as the former is likely to be more performant while also keeping the implementation(s) simpler, while, of course, increasing the complexity of patterns to be matched. This is desirable, however, since matching patterns happens at compile time whereas a general purpose stream fusion implementation would need to make determinations about the input at runtime.

Next Steps

(Some of these are carried over from last time)

• Add test cases for the backwards incompatibility on datum vs literal matching, and review whether there is a way to avoid errors here by favoring the Qi binding space in the expander.
• Prototype and then propose map1 for addition to Racket.
• Add a "long functional pipeline" benchmark.
• Continue to integrate macroexpansion events into compiler rewrite rules to afford visibility in e.g. the Macro Stepper.
• Provide good error messages in optimized (e.g. deforested) expressions in terms of source expressions.
• Validate that optimization passes can prematurely terminate if they don't return false when they don't transform the input (and then fix it).
• Implement streams for the other list operations described in St-Amour's writeup (i.e. unfoldr zip average upto). Note: implementing average might benefit from having "multi-valued CPS" for deforestation.
• Write unit tests for more compiler rewrite rules, as well as end-to-end tests for pairs of input expressions, and sanity tests for the expander.
• Find a way to reliably detect list-like operations on values.
• Rewrite these list-like operations to list-based functional pipelines, e.g. (~> (-< (>< f) (>< g)) ...)
• Add additional nonlocal benchmarks to validate all cases optimized by stream fusion.
• Generalize the stream implementation to support multiple values at each step (in addition to zero or one) and recheck the performance.
• Review other core Qi combinators besides ~> (e.g. -<, == and ><, maybe if and pass) and see whether it would make sense to extend fusion to them.
• Should Qi provide a map utility (overriding the default one) that supports "0 or more" values (as was discussed in the RacketCon talk)?
• Design a core continuation form(s?) for Qi, and show how try can be implemented in terms of it.
• Describe the sequence of compilation for input expressions with the optimizing compiler against the reference compiler, showing cases in which these do not terminate.
• Come up with a methodology to formalize and theoretically validate compiler behavior.
• Review other bindings cases that we could support next (e.g. selective binding, packing values, and binding exceptions in try).

Attendees

Dominik, Sid