Qi Compiler Sync Sept 8 2023

Implementing more fusable streams

Qi Compiler Sync Sept 8 2023

Adjacent meetings: Previous | Up | Next

Summary

We implemented foldr using a stream data type, and then rewrote it in the continuation passing style.

Background

Last time, we completed the overall layout of the compiler so that (1) there were distinct passes, (2) subexpressions at any position could be optimized and (3) so that optimizations in each pass would be recursively applied to a fixed point. We still had only implemented map and filter as fusable streams, so this time, we decided to continue implementing more streams.

foldr

We implemented foldr this way, following St-Amour's writeup:

(define (foldr-stream op init s)
  (define (next state)
    (match ((stream-next s) state)
      ['done init]
      [(cons 'skip new-state) (next new-state)]
      [(list 'yield value new-state)
       (op value (next new-state))]))
  (next (stream-state s)))

We ran into some difficulties converting this to the continuation passing style before observing that the fold can only ever be a terminating step in a functional pipeline, an alternative to converting the stream back into a list.

Continuation-passing foldr as a terminal step

We implemented it in a similar way to cstream->list:

(define-inline (foldr-cstream-2 op init next)
  (λ (state)
    (let loop ([state state])
      ((next (λ () init)
             (λ (state) (loop state))
             (λ (value state)
               (op value (loop state))))
       state))))

Other ideas and possible optimizations

We could have a pass that infers types, and that could allow us to employ type-specific operations. This could be connected to the "arity inference" pass we've talked about before.

The possibility of a "splicing" macro was brought up, that could be useful to allow users to generate multiple syntax objects spliced together, which doesn't seem to be easy to do in Racket. We may look at some examples of intended use next time.

Sidetracks

We also discussed Sokoban, computer games from the 90s, Atlantis, Riemannian geometry and the flat Earth, topological manifolds and infinite time zones, and other fun diversions.

Ferdinand the cat has also been outfitted with cyborg enhancements (an insulin monitor for diabetes) and he demonstrated these enhanced abilities.

Next Steps

(Some of these are carried over from last time)

• Add testcases and benchmarks that use foldr and foldl in functional pipelines
• Implement streams for the other list operations described in St-Amour's writeup (i.e. unfoldr foldr map filter foldl zip average upto).
• Write unit tests for compiler passes to ensure expressions are rewritten as expected.
• 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 ><, 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)?
• Review other bindings cases that we could support next (e.g. selective binding, packing values, and binding exceptions in try).

Attendees

Dominik, Ferdinand, Sid, Stephen