Racket: Qi 5 Released

Last week on January 24th, version 5 of Qi was released. This release contains support for flows in higher-order argument positions and in sequences of qi/list procedures a faster runtime code is produced by the compiler.

Although the work on Racket 8.16 is heading towards completion, Qi version 5 has already been released. It integrates more work on optimizing compiler for sequences of many list operations. Consider the following example of filtering odd values from a list and then squaring them all:

(define (square-odds lst)
  (map sqr (filter odd? lst)))

The order of procedure applications might be a bit counterintuitive for an ordinary human being as the filter gets applied first and then the map is applied onto the intermediate result. Although it is quite obvious (the arguments are evaluated first), it does not read like a natural language sentence which usually follows the time ordering of actions.

In the embedded Qi language, we can express the same algorithm more intuitively:

(define square-odds (flow (filter odd?) (map sqr)))

Although this is a very simple example, it can already benefit from the optimizing compiler as filter is a special form under qi/list and map is such too. You can see the comparison of optimizing compiler against baseline in the continuously created competitive benchmarks. A 40% speedup for such simple chain of operations is pretty impressive!

The trick is the compiled code does not need to generate intermediate lists. It does not filter the input list for odd? values first and it does not perform the sqr on all elements of the temporary result. It cleverly fuses the operations and directly starts generating the resulting list from the input one. This technique is known as deforestation and provides immediate benefits to many common scenarios.

The internal implementation of deforestation acknowledges there are three types of list operations that need to be addressed differently. They are "producers" which mark the start of the fusable sequence of operations, then there are "transformers" which transform the stream by removing, adding or changing the values of the fused stream and at the end of the sequence "consumers" convert the stream back into a plain old list.

The following operations are already supported by the qi/list module:

• producers:
  • range
• transformers
  • filter
  • map
  • filter-map
  • take
• consumers
  • foldl
  • foldr
  • car
  • cadr
  • caddr
  • cadddr
  • list-ref
  • list-ref
  • length
  • empty?
  • null?

Of course many more need to be implemented - mostly from the racket/list module. But this realease already gets you a more cohesive notation and on top of that some speedup for common scenarios as well.

Hope you liked this venture into the world of optimizing compilers of strange languages and see ya next time!