Qi Compiler Sync Dec 22 2023

Eleventh Hour Surprises

Qi Compiler Sync Dec 22 2023

Adjacent meetings: Previous | Up | Next

Summary

We got to the bottom of the "weird syntax pair bug" that had been discovered in the last few days which pushed back the release (we had originally planned to release the compiler work today). We considered some ways to fix it and implemented a reasonable short term option. We also discussed a few other things including code coverage and benchmarks.

Background

The compiler work is in final code review, and we addressed some points that came up during review. A few issues came to light during an attempt to bring the code coverage up to 100%, where, in particular, it emerged that compiler passes were in some cases terminating prematurely. This was happening in connection with the two techniques that we use in applying compiler optimizations comprehensively to the input syntax: (1) syntax tree traversal, to traverse the input syntax and apply given rewrite rules in every applicable position, and (2) fixed-point finding, which applies the given rules until the input reaches a fixed point, i.e. until rule application does not further optimize the code.

The problem was, the latter terminated upon receiving a false return value, while the former takes such a value as a sign to continue the traversal. As both are higher-order functions applying the same underlying rewrite rules, this incompatibility resulted in premature termination of optimization in some cases. This was fixed by having both functions treat a false return value as a sign to terminate.

But as a result of this, the passes were now continuing further and encountering a problem that had hitherto been hidden, where the compiler was inappropriately attempting to optimize a partial fragment of core language syntax, rather than a full and legitimate use of it.

Although this left the branch with a failing test, we merged this work to continue exploring it, as we agreed it was a blocker for release in any case:

Cover compile-time errors in tests

Getting to the Bottom of It

We put the failing source expression in an independent module for testing, and added debug logs in the syntax tree traversal utility, find-and-map, and that showed that in some cases, specifically for the somewhat pathological source expression:

(flow (thread tee collect))

... it was receiving (tee collect) as a syntax pair at some intermediate point in the traversal, and then attempting to rewrite this using normalization rules, of which, one:

(tee f) -> f

... was found to be applicable, which then caused the containing expression to become:

(thread . collect)

... which was invalid syntax.

A First Fix

We realized that syntax-e sometimes produces a "syntax pair" in unwrapping input syntax, even if the input appears to be a syntax list. As find-and-map traversal destructures lists but attempts to apply the transforming function (i.e. given set of rules) to any syntax (including a "syntax pair"), this was resulting in an inappropriate attempt to optimize (tee collect). An initial fix that seemed to work was to attempt syntax->list first before trying syntax-e, as this reliably produces a list when possible. This ensured that the traversal appropriately handled both sublists (like '(#'tee #'collect)) via syntax->list as well as atoms (like tee) via syntax-e.

Although the tests were now passing, we realized that this was still not a robust way to do it, since this example:

(flow (partition [tee collect]))

... would consider [tee collect] to be syntax rather than a list-of-syntax, and thus would attempt to optimize it and would run into a similar problem as before.

What we needed here was for the traversal algorithm to be aware of the core language grammar so that it could properly disregard subexpressions that may happen to resemble uses of the core syntax but which aren't actually.

We considered a few options:

1. Implement such a core language aware syntax traversal algorithm.
2. Offer such a generic utility in Syntax Spec that could be inferred from the specified core language grammar.
3. Change the design of the Qi core language so that all of the core forms may only be used in parenthesized form (rather than as identifiers) -- this would allow Syntax Spec to expand things in a way that would work with the existing assumptions.

A Better Fix

All of these options seemed relatively time-consuming or cumbersome, so we went with another, short term option: for Syntax Spec to simply tag expansions to indicate which syntax objects are full and legitimate uses of core language syntax. Then, in the Qi compiler, we would look for this property and only attempt to apply optimizations if it is present.

Syntax Spec differentiates three types of syntax productions that are fulfilled as part of expansion:

1. Rewrite productions
2. Form productions
3. Syntax productions

The first resemble macro tranformation rules, which simply match an input syntax pattern and rewrite it to a new pattern, typically one that is in the core language grammar. For instance, Qi's rules to rewrite the use of infix templates like _ and __ and implicit partial application employ such productions to "rewrite" such syntax into an explicit use of a core language form like #%blanket-template and #%fine-template.

The second type is productions of core language forms. For instance, expansion of a use of tee or thread in Qi would represent such a production.

The third type, syntax productions, refer to productions from source forms that aren't the usual parenthesized expressions with the first form indicating the form name, but something else where perhaps the pattern is not determined by a simple name or the presence of a single identifier.

In order to implement the chosen solution, Michael tagged the produced syntax with the new syntax property (called nonterminal) in all form productions. This ensured that all expansions directly stemming from use of a core form would have this property attached. This is a straightforward and quick solution, but it doesn't necessarily provide the right long term interface; for instance, it doesn't expose a predicate to users, and doesn't use a helper to implement the feature, and is just a syntax property that doesn't come with any knobs.

A New Release!

Michael quickly added the feature to Syntax Spec and made a new release in short order, so we technically did release something today after all! It just wasn't a Qi release 😝

Verifying the Fix

We waited for the Package Server to pick up the changes and then validated both that they fixed the specific test that was failing before, as well as a new test to validate that subforms of partition aren't inappropriately optimized.

Most of the existing low-level compiler tests were failing though, since the syntax objects they used in testing did not have the new syntax property (called nonterminal) that the compiler was expecting. We started to add this in tests and verified that that would fix the tests, but left the manual work of doing it for every test for after the meeting.

One More Case to Handle

Although we optimize every node in the input syntax tree, we still don't optimize the same syntax node at multiple levels, so that this possible normalization isn't performed:

(~> (>< (~> f))) → f

Instead, as we traverse "top down" and stop traversing a node when an optimization is applied, it only does:

(>< f)

This is nice to have, but not a blocker for release.

Coverage

We reviewed test coverage and found that it's close to 100%, but a few lines are still not covered. We concluded that some of these lines aren't hit because, although they implement valid error handling for stream producers, they are never hit because our current stream producers (i.e. specifically range) doesn't ever encounter that particular case. There were a few other lines that weren't covered that were more mystifying, since it appeared that the function definition was marked as not covered, even while the body of the function was marked as covered. Although not directly related to coverage, we did upon review seem to agree that some of the stream implementations (especially car) could be further simplified.

Elusive Linear Speedup?

With deforestation, we expect to see a linear speedup with increasing length of the functional pipeline. But although we do see this in sequences of length two (3x speedup) or three (4-5x speedup), our current long-functional-pipeline benchmark that is intended to show a clear gain on a longer functional sequence does not appear to show this speedup (it's typically about the same or a little faster than Racket). We noted this and felt that it was odd and worth investigating.

Actor Basic Updates

We saw some updates in Actor Basic, including the recent addition of a "monitor" that allows execution to be interrupted at any point and provides visibility into the "state" of every actor, allowing the user to manipulate the dynamic evaluation context. We could play around with this concept as we continue designing debugging facilities for Qi.

Release Readiness

We reviewed outstanding items for release. Aside from further testing and review, we agreed that the items remaining are:

1. Updating tests for the "syntax pair" bug fix
2. Generating a final performance report
3. Updating the user and developer documentation

And of course, there will surely be lots of other little things, but hopefully, no more surprises!

Next Steps

(Some of these are carried over from last time)

• Update the main documentation to reflect the compiler work
• Update the developer documentation with details of the compiler implementation
• Investigate why we don't see a linear speedup in the long-functional-pipeline benchmark
• Review whether we can continue optimizing a single syntax node at many levels (this is not a blocker)
• Comprehensively review error messages in Qi
• Add test cases for the backwards incompatibility on datum vs literal matching.
• Investigate ways to extend the compiler (e.g. language composition or compiler macros) and use that to implement qi/list (deforesting racket/list) as a proof of concept.
• Prototype and then propose map1 for addition to Racket.
• Preserve the stack of source expressions through expansion in Syntax Spec.
• Review the use of contracts in deforestation.
• Improve expander tests to compare expressions literally, using a test for alpha-equivalence.
• Try unpublished expansion event APIs to implement hierarchical reporting of expansion in the compiler.
• Implement streams for the other list operations described in St-Amour's writeup (i.e. unfoldr zip average). 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, "logging" style (like Typed Racket) tests to validate expected compilation sequences, 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)) ...)
• 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, Michael, Sid