-
Notifications
You must be signed in to change notification settings - Fork 12
Qi Compiler Sync Sept 29 2023
Qi Compiler Sync Sept 29 2023
Adjacent meetings: Previous | Up | Next
We saw a demo of Dominik's experiments with continuations in Actor Basic and discussed adding continuations as first class citizens of Qi. We discussed the precise nature of the guarantees Qi will provide regarding side effects. We implemented deforestation for foldl, and while debugging that, we discovered that Qi's expansion and compilation are opaque to IDE tools including DrRacket's Macro Stepper. Finally, we noted that supporting multiple input values in deforestation is an immediate priority as we can't merge the compiler work as long as we regress on Racket's existing support for multiple input lists in functional transformations like map.
Last time, we resolved properly taking chirality of forms into account in applying the deforestation optimization to list transformations, applying it only for right chiral forms. We wanted to review some other aspects of chirality handling before continuing to the implementation of deforestation for foldl.
But first, Dominik showed a demo of using continuations in Actor Basic. In this language, continuations are used to allow looping flows representing "actors" to be interrupted with messages that may modulate some state, after which the original operation of the actor should be resumed as before. For instance, an actor moving in a square could receive a message to change color, which once done, should return control to the movement loop. Dominik likened continuations in a flow-oriented language to something between "prototype-based OOP" and "hardware interrupt handling."
Currently, there is limited support for continuations in Qi. Of course, continuations, as functions, are implicitly flows (as Ben observed on Discord), but their mechanics are naively inherited from the host language (Racket) and not natively modeled in Qi. The try form for exception handling is the only dynamic control flow mechanism in Qi and it is quite rudimentary.
We felt that it might make sense to introduce continuations as a new form in Qi so that we could do something resembling this:
(~> (5)
(continue out
(switch
[positive? (~> sqr add1)]
[else out])))
... which would do an arithmetic transformation on the input if it is positive, and otherwise produce it unchanged. Of course, this isn't a very useful example since we could easily do this without continuations, but it serves to illustrate the basic usage that we might expect with continuations in Qi. In essence, continue would be a new binding form in Qi, i.e. a form that introduces a binding like as.
In Racket, exception handling is part of the extended language and is implemented using continuations which are part of the core language. We felt that it would make sense for Qi to adopt a similar approach, reimplementing try (currently a core form) as a Qi macro expanding to a use of a core continuation form like continue in the example above. We could start anywhere that would allow us to achieve this stratification of try, but in the long term, we will need to carefully consider escape continuations (uni-directional) vs full delimited continuations (bidirectional), and how these should manifest in Qi.
Adding continuations may have implications for the layout and interactions between compiler passes, so it might make sense to add it sooner rather than later. On the other hand, as long as we don't expect the addition to regress on any aspect of the semantics provided by the language, it may be more expedient to introduce continuations later, even if it may cause more refactoring of compiler passes at that stage, as this would minimize the complexity of the initial compiler implementation.
We didn't talk about this live, but it's also worth thinking about whether the introduction of continuations might encourage a more imperative style (e.g. returning values from arbitrary points in the flow), and what we can do to discourage gratuitous use of this power. It is likely that having this power would be worthwhile and could allow nontrivial and elegant flow-oriented features that we haven't thought of yet, but it will be necessary to spend time both on the design as well as any language conventions that would be warranted in order to encourage "good" uses and discourage "bad" uses on the user-facing side.
While we were now handling chirality correctly in the deforestation pass, we were not doing anything special to handle it in the normalization pass. We felt that we might need to conditionally apply the threading identities only in cases where chiralities of the flows matched. But after discussing, we realized that we'd already discussed this last week and concluded that this would not be a problem because, due to the way syntax-parse works, the chirality property (and any other syntax properties) would implicitly be preserved on components when the expression is normalized. Since there is only one thread core form, and placement of arguments is determined by the chirality of individual components rather than globally by the thread form, it would automatically "just work" without any special handling here. The right threading ~>> macro sets the chirality, the deforestation pass conditions on it, and the #%partial-application and clos core forms implement supplying arguments on the appropriate side based on it. So, normalization does not need to care about chirality, aside from preserving it, which it implicitly does.
We agreed that this subtle operation of chirality should be internally documented (it is not a user-facing concept but relevant to the implementation) when the compiler work is being merged.
We chose to implement foldl directly within the Qi compiler instead of in a standalone module, since at this stage we already had the infrastructure to test it in place and the new stream presented the same interface as an existing stream (foldr) but with a different implementation.
We added some tests for foldl and foldr that used non-commutative operations (otherwise we wouldn't be able to distinguish left folds from right folds with something like +):
(check-equal? ((☯ (~>> (map string-upcase) (foldr string-append "I")))
(list "a" "b" "c"))
"ABCI")
(check-equal? ((☯ (~>> (map string-upcase) (foldl string-append "I")))
(list "a" "b" "c"))
"CBAI")
We copy-pasted the implementation of matching the foldr pattern, changing it to match foldl, and implemented the foldl stream this way:
(define-inline (foldl-cstream op init next)
(λ (state)
(let loop ([acc init] [state state])
((next (λ () acc)
(λ (state) (loop acc state))
(λ (value state)
(loop (op value acc) state)))
state))))
... comparing it with St-Amour's implementation. We realized that St-Amour's implementation assumes Haskell's order of arguments (bab) instead of Racket's (abb). We made the necessary changes to attempt to get it to work.
Initially, this wasn't being matched at all, and the tests were passing even when the implementation was wrong (since it would just fall through to being handled as Racket's built-in foldl). For some reason, the syntax pattern wasn't matching foldl even though we simply changed foldr to foldl and it had been working correctly for foldr.
In attempting to debug what was going on, we fired up DrRacket's Macro Stepper to expand an expression like ((☯ (~>> (map string-upcase) (foldl string-append "I"))) (list "a" "b" "c")). But this simply showed the output of both expansion and compilation in a single step, without showing the intermediate transformations.
(#%app
(☯ (~>> (map string-upcase) (foldl string-append "I")))
(list "a" "b" "c"))
→ [Macro transformation]
(#%app
(let ()
(qi0->racket
(thread
(esc
(λ (lst)
((cstream->list
(inline-compose1
[map-cstream-next string-upcase]
list->cstream-next))
lst)))
(#%partial-application
((#%host-expression foldl)
(#%host-expression string-append)
(#%host-expression "I"))))))
(list "a" "b" "c"))
As it stood, we were only able to see that the output expression was not the optimized version we were expecting, but we were not able to inspect the syntax at intermediate stages to probe why. For instance, did the syntax never take on the form that would match the pattern we had written down? Or, even if the overall pattern looked right, was there an expected syntax property like chirality that might be missing? Or did it match the pattern but produce incorrect code?
It would be ideal if we could see the expression after expansion, and then after each compiler pass -- for example, the expression after the normalization pass, and then the expression after the deforestation pass. We were unsure how this could be accomplished, and whether syntax-spec might be able to afford some help here. But in any case, it would be nice if we could expose the stages of compilation as if they were expansion passes, to any IDE tools.
It turned out that in the syntax class we had written for foldr last time:
(pattern (#%partial-application
((#%host-expression (~literal foldr))
(#%host-expression op)
(#%host-expression init)))
#:do [(define chirality (syntax-property #'stx 'chirality))]
#:when (and chirality (eq? chirality 'right))
#:attr end #'(foldr-cstream op init))
... we were getting the chirality property from "stx", which we were assuming was the input syntax, but we weren't actually binding stx to anything.
When we copy-pasted this to the foldl pattern, it now was failing to match. Adding the binding via the ~and trick:
(define-syntax-class fusable-fold-operation
#:attributes (op init end)
#:datum-literals (#%host-expression #%partial-application)
(pattern (~and (#%partial-application
((#%host-expression (~literal foldr))
(#%host-expression op)
(#%host-expression init)))
stx)
#:do [(define chirality (syntax-property #'stx 'chirality))]
#:when (and chirality (eq? chirality 'right))
#:attr end #'(foldr-cstream op init))
(pattern (~and (#%partial-application
((#%host-expression (~literal foldl))
(#%host-expression op)
(#%host-expression init)))
stx)
#:do [(define chirality (syntax-property #'stx 'chirality))]
#:when (and chirality (eq? chirality 'right))
#:attr end #'(foldl-cstream op init)))
... did the trick!
It's unclear why this was ever working before for foldr, though.
With the introduction of the optimizing compiler, we are changing the semantics of the language in some aspects. Specifically, we are doubling down on Qi as a language for expressing functional, immutable computations, and shedding any guarantees outside of this paradigm if it would result in faster performance. The main optimization we've implemented so far in this direction is deforestation, which transforms a series of functional transformations on lists into a single transformation of a stream. In doing this, we change the temporal order in which computations are done. In particular, with a list going through a filter → map transformation, any side effects of the filtering function (e.g. printing something to the screen) would be done for all of the input list elements prior to the side effects of the mapping function. Something like:
1 is odd
2 is even
3 is odd
4 is even
5 is odd
1 squared is 1
3 squared is 9
5 squared is 25
... if we filter to odd numbers and then square them, and we happen to print these messages involving the input list elements. With stream fusion in Qi, we would now instead print something like:
1 is odd
1 squared is 1
2 is even
3 is odd
3 squared is 9
4 is even
5 is odd
5 squared is 25
In other words, we are no longer providing the same order of effects that the original unoptimized expression would have had. So far, we have talked mainly about how we are willing to shed such guarantees without focusing on the guarantees we do provide. But we agreed that the guarantees retained by the language are still quite strong, and are representative of the kind of language Qi is. In particular, we assume that any dependencies across flows should be entirely represented in the values that are passed between them as inputs and outputs. If there happen to be dependencies in the side effects (e.g. constructing a list of intermediate values taken on over the course of the flow), then that is not something that we consider to be modeled in the language, even though the actual behavior will still make sense (e.g. the effects reflect the modified rather than original order of operations). It would be up to the user, in this case, to explicitly indicate a preference for order of effects by using the effect form -- in which case, it would be a modeled effect, understood by Qi, and would not be deforested, preserving the intended order of effects. In other words, while Qi does not assume that flows are free of side effects, it makes no guarantees about "accidental," undeclared effects.
Built-in map, foldl and foldr accept multiple input lists, and the function employed in these operations receives as many input values as there are lists (taking one from each list, in sequence), and is expected to produce exactly one output value. Our current implementation of stream fusion assumes one input value and one output value. We agreed that regressing on functionality already provided by Racket would be a blocker as far as merging the compiler work is concerned, so that means that supporting multiple input values in our implementation becomes a priority in the near term.
In order to do this, we would likely need to change the semantics of "yield" in the stream implementations so that it provides multiple values to the operation being performed at each step (i.e. f in map and filter, and op in foldl and foldr), and we'd probably need to change "done" and "skip" behavior as well. We will probably first complete the implementations for single values, as we have been doing, before generalizing them this way.
It would also be desirable to support multiple output values, in order to be able to deforest list-like transformations on values using core Qi combinators like ><, but that isn't a blocker for merging the compiler work since that is only an optimization rather than a semantic difference.
As we've talked about before, we still don't have any formal guarantees that compiler passes will terminate. It will be useful, once the initial optimizing compiler is ready, to construct a reasonable example and show it through the successive stages of optimization under compiler passes (along with a similar sequence under the "reference compiler" on the main branch). If we can find a reasonable implementation that breaks (i.e. does not terminate), or even a pathological one, then that would give us some data from which to start thinking more formally about it.
(Some of these are carried over from last time)
- Write benchmarks using
foldl. - Validate that optimization passes can prematurely terminate if they don't return false when they don't transform the input (and then fix it).
- Contact other people working on compilers (e.g. LLVM, Racket/Chez) to get an idea of best practices on testing optimizations.
- Implement streams for the other list operations described in St-Amour's writeup (i.e.
unfoldrmapfilterfoldlzipaverageupto). Note: implementingaveragemight benefit from having "multi-valued CPS" for deforestation. - Write unit tests for more compiler rewrite rules.
- 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><, maybeifandpass) and see whether it would make sense to extend fusion to them. - Should Qi provide a
maputility (overriding the default one) that supports "0 or more" values (as was discussed in the RacketCon talk)? - Describe the sequence of compilation for input expressions with the optimizing compiler against the reference compiler, showing cases in which these do not terminate.
- Design a core continuation form(s?) for Qi, and show how
trycan be implemented in terms of it. - Review other bindings cases that we could support next (e.g. selective binding, packing values, and binding exceptions in
try).
Dominik, Sid
Home | Developer's Guide | Calendar | Events | Projects | Meeting Notes