Qi Meeting Nov 1 2024

Rank Polymorphic Qi

Qi Meeting Nov 1 2024

Adjacent meetings: Previous | Up | Next

Summary

We continued discussing how to extend Qi's deforestation to custom list operations via "deep" macros, and whether these could support application templates (i.e. _ and __). It brought up some longstanding design questions regarding the intended handling of multiple values in Qi.

Background

Last time, we discussed a very complicated way to add two numbers that was nevertheless a simple proof-of-concept for extending Qi's compiler to custom operations. There were some gaps still to be filled, including how to encode appropriate DSL expansion while also providing the Racket runtime to be used at the code generation step.

Resolving Some Questions

"... But No Simpler"

Last time, Sid attempted to simplify Michael's proof-of-concept by removing what appeared to be an extraneous macro helper, changing this:

(begin-for-syntax
  (define (op-transformer info)
    (syntax-parser
      [(_ e1 e2) #`(#%optimizable-app #,info e1 e2)])))


(define-syntax define-optimizable-op
  (syntax-parser
    [(_ name codegen-f)
    ...
    (define-dsl-syntax name my-expr-macro
      (op-transformer #'info))]))

to this:

(define-syntax define-optimizable-op
  (syntax-parser
    [(_ name codegen-f)
    ...
    (define-dsl-syntax name my-expr-macro
      (syntax-parser
        [(_ e1 e2)
         #'(#%optimizable-app info e1 e2)]))]))

But it emerged that the reason for it is that although the two versions are functionally identical, the version without the helper ends up generating a lot of extra code each time.

Generally speaking, for a macro-defining macro, we want to use such an indirection to avoid generating excess code.

Circular dependency?

Another concern was, in the proof of concept example, the compiler purely performs code generation and simply invokes itself recursively to compile component DSL expressions. But Qi uses an optimizing multi-pass compiler that performs code generation at the end. Could recursively invoking the compiler in the runtime of the bespoke operation -- that is, at the code generation step -- entail a circular dependency? That is, the compiler would invoke code generation, which itself would invoke the compiler, and they are in different modules. Having to employ a lazy require to resolve this seems non-ideal. It also seems as though it might complicate proving and enforcing theoretical guarantees provided by the language.

Instead, we discussed that each compiler pass should be responsible for fully traversing syntax and optimizing component expressions within its purview -- even traversing into such bespoke operations that may not themselves be optimized by these passes (and thus fall through to the supplied runtime).

So for instance, in something like:

(☯ (map (~> sqr add1 1))

… the normalization pass would normalize component expressions so that, perhaps, the nested flow would become simply 1, and since the map is used on its own here it is not deforested and would fall through to the runtime supplied in the macro definition, which might be something like this:

(define-deforestable map
  ...
  (λ (f)
    #`(λ (vs)
        (r:map #,f vs))))

… where r:map is simply Racket's map.

When we get to the code generation step, it would simply recursively invoke code generation on the component expressions (rather than the full compiler), the same as for any other Qi forms.

Encoding proper expansion in the "deep" macro

The main other issue was, the "deep macro" mechanism allowed us to specify a Racket runtime for use at the final stage of compilation, but did not allow us to indicate expansion in a flexible way, for instance, to indicate which component expressions might be floe positions that should be expanded.

We discussed a few possible syntaxes for declaring which arguments are flows vs Racket expressions:

(foldl f e) ; f and e are matched literally as datums
(foldl f:floe init:expr)
(foldl floe expr)
(foldl #t #f)
(foldl [f floe] [e expr])

These would be indicated as something like this:

(define-deforestable
  (foldl [f floe] [init expr])
  (λ (f init)
    #`(λ (vs) ; single list input
        (r:foldl #,f #,init vs))))

… where, once again, r:foldl is simply Racket's foldl.

Underscores?

In Qi on the main branch, list operations like map, filter and foldl are used directly as functions from the racket/list module. This means that they inherit all of the flexibility of function application syntax in Qi, including fine-grained templates, blanket templates, and partial application with left- and right-threading.

qi/list (in development on the deforestation branch) provides these operations as syntactic forms, that is, as Qi macros. This allows them to employ flows in higher-order positions, but it means that we do not inherit the application templates available to functions. Not long ago, we discussed this and felt that it would be useful to provide an analogous implementation of templates for qi/list forms to ease the transition from racket/list. We had discussed that we could do this by employing a "meta language" for defining forms which would make use of such templates, and that this approach would avoid duplicate implementations of template pattern matching in each such form. Since then, we've prototyped such a "metalanguage" in the form of the example we discussed at length last time. We could augment this scheme to support templates.

But after discussing it further today, we realized that some templates introduce ambiguity to the syntax that cannot be handled at expansion time. That is, we need to be able to indicate to the expander which positions are floe vs expr nonterminals, as the former would need to be expanded by the Qi expander. With fine-grained templates, that is, _, we would be able to reliably identify the positions that are floe positions. But with blanket, __, templates, if we had an unusual map utility that supported multiple higher-order arguments, something like:

(weird-map f e e f e)

… where the f represent floe positions and e, expr positions (i.e. it's one of the candidate syntaxes for indicating floe vs expr positions considered earlier), then if we use it this way:

(weird-map __ a b)

… it's impossible to know whether a is a floe position or not, as this could be invoked with 0 or more arguments at runtime. We could make a stipulation that __ can only be used after all floe positions have been provided, so that all arguments following it would be expanded as Racket expr, but this seems arbitrary.

So we agreed that blanket templates should not be supported. It seems as though supporting _ should still be possible, but we agreed that it would be wise to start with no support for underscores and consider adding it later.

For now, we will consider use of underscores with qi/list forms as invalid syntax. We will also expect the non-list arguments to be indicated syntactically. This would mean that something like this would no longer be possible:

(~> (sqr '(1 2 3)) map)

It would need to be, instead:

(~> ('(1 2 3)) (map sqr))

Although, note that current use of this kind on the main branch involves the racket/list function rather than the new qi/list form, so it is not technically a backwards incompatibility, but rather more of an obstacle to easy migration from racket/list.

Designing for Multiple Values

The original talk on Qi suggested that we could use multiple values in traditionally single-valued positions with some interesting semantics, which we attempted to codify in the docs as "flowy logic." Not long ago, we discussed this again and realized that there were still a few different options that may feel natural from different perspectives.

We felt that one way that could help identify the right way to handle multiple values in such cases would be to look at simpler operations like list-ref. From looking at what (list-ref 2) ought to do when given multiple input lists, we could imagine the analogous "lifting" to multiple values for more complex operations like map. It may be that the version lifted in the implied natural way would have different semantics from Racket's map (or other operations) when those are given multiple values. For instance, in the present case, it seems natural for:

(~> ('(1 3 5) '(2 4 6)) (list-ref 2))

… to produce

5
6

… as separate values. Analogously, it would seem that

(~> ('(1 3 5) '(2 4 6)) (map sqr))

… should produce

'(1 9 25)
'(4 16 36)

(as it happens, this is consistent with the guidelines in Flowy Logic – except that those guidelines are referring more to something like (map sqr (values '(1 3 5) '(2 4 6))))

Yet, Racket's map also accepts multiple values, and its semantics in this case is to treat the higher order function as an n-ary operator and provide it corresponding elements from each input list to produce a single output list. (map sqr '(1 3 5) '(2 4 6)) would be an error since sqr is unary, but this would work:

(map + '(1 3 5) '(2 4 6)) ;=> '(3 7 11)

Assuming that the earlier behavior is natural for Qi, we should also ask: how would Racket's map behavior be best modeled in Qi? Do we need to introduce a new idea to capture applying an n-ary operation to lists of arguments? Perhaps we need a new generalized zip form for this purpose.

In any case, we agreed that these multiple values in list-oriented forms should all be assumed to be lists rather than arbitrary values. That is, list-oriented operations would in general receive "zero or more" lists as input, and nothing else.

Single Valued Efficiency

We've talked about how using multiple values in this way can be expressive, yet incurs a heavy cost in performance. There are planned optimizations like arity-inference that we could leverage here, but it may also be worthwhile to have explicit single-valued operations in some cases. That is, we could potentially have single-valued and multi-valued deforestation implementations existing side-by-side, and use the single-valued version when we can.

In the past, we've talked about how Racket has single-valued compose1 in addition to variadic compose to help make exactly this kind of thing easier, but it doesn't have map1. We could consider adding a map1 to qi/list, and potentially also to racket/list, as one measure that could help here.

Known-Arity Efficiency

Potentially another way to improve efficiency of multi-valued pipelines is something like "generalized arrays" (SRFI 231) that Brad told us about some time ago.

Initial Implementation

In sum, despite the allure of these designs and their implementations, we agreed that it would be prudent to first aim for:

• no support for templates (not even fine-grained templates, as we are assuming the implicit inputs will always be lists)
• assuming that there will be exactly one implicit argument to flows and that it's a list

Among other things, this would mean that we wouldn't need to worry about matching all the combinatorial possibilities of templates in the actual implementation of deforestation, and the implementation of fusion already supports specifically one input list in most cases so we could continue with that assumption (and it would probably be easiest to remove the handling of multiple input values in operations such as map and foldl for now rather than implement the alternative semantics discussed above ...).

We agreed that this would simplify things a lot, and would be a good first step towards the other planned improvements.

"Rank Polymorphic Qi"

Michael commented on the similarity of some of these directions to languages like APL and Remora, and that we may be trying to make "rank polymorphic Qi" (whatever that means! I'm sure we'll find out soon enough).

Other Design Considerations

foldl

In foldl, should init be a flow? As literals in Qi are interpreted as functions producing them, (foldl + 0) could potentially apply the 0 flow to the input list argument in order to derive the init value to be used in the fold.

But no, we felt this was too much and we should just keep it a number – a non-function argument, mmkay? Not everything has to be a function!

Next Steps

(Some of these are carried over from last time)

• Implement a handful of list operations such as map in the proof-of-concept extension scheme.
• Incorporate the extension scheme into Qi deforestation.
• Resolve the issue with bindings being prematurely evaluated.
• Implement more fusable stream components like append, drop, and member.
• Provide a runtime and indicate floe positions by enriching the syntax of #%deforestable
• Implement the generic scheme for promoting position-oriented Qi macro definitions to handle templates
• Update the benchmarking infrastructure (vlibench and also the basic ones in qi-sdk)
• Define an extension scheme for deforesting custom list APIs.
• Fix the bug in using bindings in deforestable forms like range
• Finalize and document guiding principles for Git commits in the developer wiki
• Revisit extending deforestation to multi-valued settings.
• Write a proof-of-concept compiling Qi to another backend (such as threads or futures), and document the recipe for doing this.
• Ask Ben to review tests from the perspective of Frosthaven Manager.
• Review Cover's methodology for checking coverage.
• Document the release model in the user docs and announce the performance regression (and the remedy) to users.
• Improve unit testing infrastructure for deforestation.
• Discuss and work out Qi's theory of effects and merge the corresponding PR.
• Decide on appropriate reference implementations to use for comparison in the new benchmarks report and add them.
• Deforest other racket/list APIs via qi/list
• Decide on whether there will be any deforestation in the Qi core, upon (require qi) (without (require qi/list))
• Continue investigating options to preserve or synthesize the appropriate source syntax through expansion for blame purposes.

Attendees

Dominik, Michael, Sam, Sid