-
Notifications
You must be signed in to change notification settings - Fork 12
Qi Meeting Jan 26 2024
Qi Meeting Jan 26 2024
Adjacent meetings: Previous | Up | Next
We discussed what, precisely, Qi's guarantees (or lack thereof) regarding order of effects might be. We also discussed the benchmarking suite and the modular compiler architecture.
Last week, we triaged all of the outstanding issues we'd been carrying forward in our queue of "next steps," and created a lot of issues on the source repo to track them, retaining only the immediate work. Sid had also started a docs PR to properly update the main docs to reflect the compiler work and all of its user implications. That started some discussions around what we are really promising on order of effects, as that needs to be communicated accurately to users.
Now, we have been saying for some time that a core tenet of Qi's theory of optimization is that there shall be no "accidental" side effects, and that if such effects exist, they may be reordered, and the behavior on that score is unmodeled as far as Qi is concerned. If we want a particular order of effects, we could use the effect form to explicitly indicate an effect, and we assumed that this form would not be reordered.
But in our actual implementation, we haven't made any special exclusions from optimizations for the effect form. We even discussed a possible do form recently that could suspend optimizations, but decided against adding it. Now that the time has come to advertise what exactly we are promising with regard to order of effects, we've had to confront that, in fact, we haven't exactly done what we've been saying, or what we've been assuming we would do.
The question is, are we being negligent here, and maybe it's high time we fulfilled our obligation by introducing ways to ensure a particular order of effects? Or is what we are actually doing the right thing for Qi after all?
The truth is, effect doesn't actually do anything special with regard to order of effects. A flow f that contains an implicit effect e is essentially equivalent to (effect e f') where f' is pure, with e extracted from it.
Yet, effect is an important stylistic choice in Qi since it encourages pure functions and separating effects from such functions. This has all kinds of benefits that have nothing to do with order of effects.
The only real guarantee we seem to provide is around the esc form. The flow wrapped in esc is a Racket expression that evaluates to a function. It is expanded and compiled by Racket, and Qi does not attempt to optimize it. Therefore, if a specific order -- that is, Racket's order -- of effects is desired, then the flow must be specified using esc. Of course, this is less a way to indicate a specific order of effects than it is a choice to use a different language to describe the flow. But Qi makes it easy enough to mix in Racket code, so this seems quite reasonable.
We could say that, aside from esc, Qi provides no guarantees about order of effects. Or we could find another way to provide such guarantees.
We considered a number of possibilities around what we could do if we did want to provide a way to ensure a certain order of effects while writing Qi.
For instance, a has-effect or EFFECT form, which would designate a "watershed" point in the flow, where all the effects prior to that point would happen before it, and all effects past that point would happen after it. Essentially, this would mark a boundary point which optimizations would not cross.
But after we considered the many permutations of the manner in which a flow could be effectful, for instance:
- The flow contains an effect, or is annotated with
effect - The flow invokes another flow internally that contains an effect
- The flow has an effect in its dynamic extent
... we felt that we could not neatly capture these cases using an approach as simple as, say, attaching a syntax property to the containing flow and propagating that transitively. Sometimes, the has-effect form may be within a definition that is referenced as a variable in a flow, and thus it is not syntactically visible in the calling context. In this case, inlining the flow definition would cause the has-effect form to be visible, and optimizations to be suspended. Since the behavior would be different when inlined, this would not be referentially transparent.
The remedy for this could be a kind of type system with effects, propagating type information at compile time, such as the existence of the has-effect property, into referencing flows.
We agreed that the remedy was complicated, but also questioned whether a remedy was called for.
While it may well be the case that we can be comfortable not providing guarantees on order of effects, is it really the case that, aside from esc, we do not provide any such guarantees? We looked at some examples.
In a flow like this one:
(~>> (filter my-odd?) (map my-sqr))
... where my-odd? and my-sqr are effectful, printing their inputs to the screen, we agreed that, due to deforestation, this changes the order of effects from an equivalent Racket version of this flow.
For instance, for an input list (1 2 3), this might print 1 1 2 3 3, whereas Racket would print 1 2 3 1 3, since for Racket, filter would process the entire list, and then map would process the entire resulting list. Qi would follow each individual list element through all of its transformations before doing the same for the next element.
Racket guarantees that all of the effects in the filter are done before any of the effects in map -- a strong guarantee. Does Qi guarantee anything here?
Another example is this one, a normalization rule that performs deforestation of pure values, analogous to what we do for lists. The performance gain in this case is only modest, however, since it is a simple code transformation that does not actually implement a stream. Nevertheless, it does affect effects:
(~> (pass my-odd?) (>< my-sqr))
->
(>< (if my-odd? my-sqr ⏚))
Here, the order on the a priori flow would have been to perform all of the my-odd? effects first, and then all of the my-sqr effects. But that of the posterior flow would be, analogous to the list case, the my-odd? effect followed by the my-sqr effect, for each value, one at a time.
That brings us to what may be the real guarantee provided by Qi: effect locality.
Given a function f₁ that performs an effect e₁ and another function f₂ that performs an effect e₂:
Define a relation "g is downstream of f" to mean either that:
- the output of
fis necessary to determining (e.g. is) an input tog - the output of
g'is necessary to determining an input tog, andg'is downstream off
Equivalently, we say that f is upstream of g.
Qi's guarantees seem to be:
- For a flow
fwith effecte(either implicit, or explicitly declared usingeffect),eis always performed whenfis invoked -- we will never separate an effect from the flow it annotates. - If
f₁is upstream off₂, thene₁is performed beforee₂(this follows from (1) and the definition of "upstream").
These are weaker guarantees than Racket's, and indeed, these guarantees are also satisfied by Racket's stronger guarantees.
Looking at our earlier example:
(~>> (filter my-odd?) (map my-sqr))
... one might argue that (2) does not hold here, since the effects of my-odd? and my-sqr are interleaved. Yet, we do not consider the mere invocation of some operation such as displayln to be an effect on its own. Instead, we adopt the more precise definition that an effect is parametrized by the input argument. The invocation (my-odd? 1) precedes the invocation (my-sqr 1), and in accordance with the guarantees above, the effect (e₁ 1) precedes the effect (e₂ 1).
It could also be argued that the output of (filter my-odd?) as a whole could be used to determine the input to each invocation of my-sqr, and so, all of the my-odd? effects should happen before any my-sqr effects. But in fact, while this is sufficient for this purpose, having the entire result of the filter step is not necessary to determining the input to each invocation of my-sqr in the map step. The relation of "being downstream" is defined in terms of necessity.
Indeed, we could have written the flow this way:
(~>> (ε e₁ (filter my-odd?)) (ε e₂ (map my-sqr)))
In this case, it's easy to see that e₁ does in fact happen before e₂ (and the sequence is not deforested). The key distinction is, the effects here are "on" the filter and map functions, whereas formerly the effects were on the my-odd? and the my-sqr functions. This brings up another point that we would proffer: effects are coupled to function invocations (and thus parametrized by a set of inputs (that function's inputs), as we suggested earlier), which we reference by saying that an effect is "on" a function. It does not make sense to speak of an effect without an associated function invocation. In the case where there is a "pure effect," we take the associated function to be the identity function or values.
In the other example we considered:
(~> (pass my-odd?) (amp my-sqr))
->
(amp (if my-odd? my-sqr ground))
The order of effects in the a priori flow is (e₁ 1), (e₁ 2), (e₁ 3), (e₂ 1), (e₂ 3), and the order of effects in the posterior flow is (e₁ 1), (e₂ 1), (e₁ 2), (e₁ 3), (e₂ 3).
Either of these orders satisfies the guarantees above!
Finally, it's worth considering whether it is useful to consider Racket as representing the ground truth on order of effects. Since Qi deviates from Racket's order of effects, we may feel that Qi is changing the meaning of some presumed Racket program that is the basis of the Qi program.
But perhaps this isn't the right way to think about it, and instead, we could see Qi's handling of effects as simply an alternative semantics, without according Racket a privileged status of being "right." The question is, is there something about Qi's handling of effects that would in some more objective sense be considered theoretically flawed? Given the proposed guarantees above, can we exhibit a Qi program where an optimization abiding by those guarantees, either an existing one or a conceivable one, where we could agree that, in fact, the behavior is unexpected and inappropriate?
We were not able to come up with such an example.
No doubt, we will be discussing this issue regarding effects further, and will come to understand it more clearly over time.
(Some of these are carried over from last time)
- Review and merge the modular compiler architecture
- Incorporate the new benchmarking suite into the SDK (including Makefile targets) and CI workflows
- Review whether we can continue optimizing a single syntax node at many levels
- Investigate ways to extend the compiler (e.g. language composition or compiler macros) and use that to implement
qi/list(deforestingracket/list) as a proof of concept. - Preserve the source syntax through expansion in Syntax Spec.
Dominik, Michael, Sid
Home | Developer's Guide | Calendar | Events | Projects | Meeting Notes