Hi all,
We've been sharing these meeting notes privately among attendees and enthusiasts, but some of us felt it would be fun and useful to share them on here, so we'll start doing that. The Qi compiler project has really picked up steam lately and there are lots of very interesting avenues for exploration. They are open to all -- come on by!
Here are the latest notes (actually from Friday -- but the topic is so that this can be reused weekly).
Basically the last example raises correctly an exception while the "Qi foldr under left threading" truly behaves like "Qi foldr under right threading". Which is the weird behavior you've already noticed.
Should the semantics remain the same (I assume they should) than foldr must work only with the right chirality and foldl only with left chirality.
Right now only the optimized foldr misbehaves - which means this is the right time to make sure it not only gets fixed but we put at least some tests in place so that this does not hit us in the future with other optimizations. I am pretty confident that other fusion-terminating operations will have similar problems with chirality. And I used non-commutative operation (string-append) to double-check. Commutative operations hide a lots of errors here so another suggestion is to make sure we include non-commutative operations in any tests for fold-like optimizations.
OTOH I hope I got it right: right chirality means the values go as the first (leftmost arguments) and left chirality means they go last (rightmost). I am not sure about this, on a second thought it might be the other way round. That means I might be using a flipped terminology here - yet still I am fairly confident the examples show a real problem. Can anyone re-check my naming of left/right chirality for threading macros in Qi?
;; Right-threading is just normal threading but with a syntax
;; property attached to the components indicating the chirality
(define-qi-syntax-rule (thread-right onex:right-threading-clause ...)
(~> onex.chiral ...))
This snippet probably means that default really is left and if chirality is set, the default is right (reverse).
And a little side note (I'll officially announce it later), the official Actor Basic is now hosted at:
It is just one package out of a collection of packages aimed at writing roguelike (more like rogue-lite as I am interested in the real-time nature of such environments) games.
The splicing case syntax @countvajhula mentioned in the notes is:
It's very rudimentary, but shows the purpose and simple implementation of splicing syntax in dispatching expressions.
Interesting, I'll have to think about this some more (or you could explain it at the next meeting!), but I think you may be confusing the "chirality" in the code with a different idea. In the code, chirality refers to where in the original expression the argument(s) should be placed. Right chirality means that the argument will be passed in the last argument position (it's very similar to the right threading operator in the threading library):
(~>> (filter odd?) (map sqr))
would be equivalent to
(~> (filter odd? _) (map sqr _))
(just for illustration), which, in the reference (non-optimizing) compiler (to use your terminology ), compiles down to:
(map sqr (filter odd (list 1 2 3)))
Left chirality is the default and means the argument will be passed in the first position of each application.
(~> (filter odd?) (map sqr))
would be equivalent to
(~> (filter _ odd?) (map _ sqr))
which the reference compiler compiles to:
(map (filter (list 1 2 3) odd?) sqr)
So use of left-threading should be an error for both foldl and foldr since all of these functions expect the list in the last position rather than the first position.
But it's quite possible that going through the stream elements from left-to-right vs right-to-left (which I think is what you're talking about) would have different considerations for foldl vs foldr. I don't recall how it is in St-Amour's writeup (mentioned in several places in recent meeting notes - for anyone following along) but maybe he already accounts for this?
Among other things, we discussed the feedback on compiler testing approaches from the other thread. We'll likely continue that discussion in the coming weeks.
It only covers the before/after optimization (just before introducing bindings), but this is probably the right approach. It allows us to keep some expansion to happen in different order than the plain macro expansion going from the outermost to the innermost expressions and yet present it as distinct transformation steps. All we need to do is to use emit-local-step in the right places of the Qi compiler (like it is probably used in the normal Racket macro expander).
I still have to verify that this is what the normal Racket expander does internally. Or perhaps @ryanc can chime in?
The macro expander emits lots of different kinds of events that allow the macro stepper to reconstruct the context and steps of expansion. In the expander, the interface with the macro stepper is mainly in log.rkt. Look for calls to log-expand etc in expr.rkt and other files in that directory.
For example, in the expansion of a lambda expression, the expander would emit a visit event ("I'm about to start expanding this expression"), then a prim-lambda event ("After inspecting the expression and resolving the head identifier, looks like Racket's lambda syntax"), then a lambda-renames event ("Here are the formal parameters with the new lexical scope applied"), then events for its body, then various events to indicate that it's exiting the context of the lambda expression. (I've skipped a few for simplicity.)
The macro stepper parses that sequence of events into a tree --- yes, parses, using Racket's LALR(1) parser generator --- and then it uses that tree to generate reduction steps. The tree structure is used to determine the context of each expansion step, so macro steps within the lambda expression's body show the surrounding lambda expression, show arrows between lambda-bound variables and apparent references, etc.
The macro-debugger/emit API doesn't provide a way to set the context of a remark or artificial step, but that could probably be added, at least in a limited form.
The discussion on how to allow users to extend Qi compiler optimizations (starting at "deforestation for bepoke datatypes") was an especially interesting topic that came up.
Incidentally, next time, @dominik.pantucek is planning to give a demo of the 3D rendering engine for the Racket Roguelike Library, powered by Actor Basic (another flow-oriented language like Qi). If you're a fan of 80s/90s era games, I think you wouldn't wanna miss it.
The notes on delayed computation by building a description and executing is (IIUC) essentially the monad-interpreter pattern: an algebraic datatype describes the operations and is equipped with monadic structure; the functions (such as map) return a value of the datatype rather than performing the computation. One can then independently specify how to execute the computation, such as via a reference interpreter or via an optimizing compiler, by writing programs over the type of the computation.
The classic IO monad does something like this internally in Haskell, and I think the pattern is commonly used for other problems.
I’m interested in helping with the inlining issue if you’d like to provide more information.
Edit: I should probably leave a general note on this issue. The approach of define-inline is that it’s a macro, not normal inlining done by the compiler, while begin-encourage-inline attaches a 'compiler-hint:cross-module-inline syntax property that, well, encourages inlining. In particular, higher-order use isn’t inlined by define-inline (it expands to a variable reference in this case), while there can be more things done by the compiler. This is likely what is causing the issue, because Qi is probably relying on the higher-order usage? I would suggest just simply use begin-encourage-inline and let the compiler figure out the optimization.
This commit is the context. If you clone the repo locally (you may find Getting Started helpful) and run:
$ make profile-competitive
The filter-map and filter-map (large list) benchmarks shows the most improvement with bothbegin-encourage-inline and define-inline, but as I recall, if we remove either of those, it gets noticeably slower.
So onlybegin-encourage-inline doesn’t work well because the inlining very easily exceeds schemify’s fuel (which governs cross-module inlining), I guess. Actually, in such cases, I think a more aggressive define-inline form (in the sense that it also inlines variable-reference case) will be useful. This may be a good addition to define-inline itself. (And it also doesn’t handle case-lambda, right? So it’s another thing that can be done.)
Highlights (some of these issues affect compilers in general and aren't specific to Qi):
we continued discussing good ways to test a compiler (still iterating there -- please join next week if you're interested)
how to report good error messages in terms of the source code (rather than the target code)?
how to deal with a combinatorial explosion in match patterns in deforesting "fine grained" argument templates like (~> (range _ _ 10) (filter odd? _) (map sqr _))?
can we simpify match patterns by reducing inferred syntax properties like "chirality" (i.e. left- or right-threading) to an explicit use of a core language?
), compiles down to:
