Deforestation Progress

Although it has been more than a year since Qi 5 was released, the work on deforastation in qi/list has steadily progressed forward finally yielding an (almost) unified interface for defining new deforestable operations.

The development of optimizing compiler for list operations provided by the Qi language which are similar to those provided by racket/list turned out to take much longer than anticipated.

However right now - in the development branches - there is a unified syntax form for defining the deforestable primitves of all three kinds:

• producers,
• transformers, and
• consumers.

There are not many producers implemented (yet), however they use the following - very streamlined - interface:

(define-deforestable #:producer list->cstream
  #:fallback
  identity
  #:impl
  (lambda (done skip yield)
    (λ (state)
      (cond [(null? state) (done)]
            [else (yield (car state) (cdr state))])))
  #:prepare
  (lambda (consing next)
    (lambda (lst)
      (next (consing lst))))
  #:contracts
  (list?))

If there are no runtime arguments to check with contracts, the #:contracts section is optional and defaults to an empty list of contracts. And if there are any formal arguments to be defined a curried define form is used to specify the formals. In this example however this is a producer without arguments. Actually it is the default producer which converts a list into a stream.

Although there are many transformers already defined, many are missing and the new interface will hopefully allow us to specify more and more every day. It has to be noted that there are some limits to this interface for transformers which we plan to address in the future. With that said, the interface is already prety versatile. Two major examples show the improvements. Firstly the following is the map transformer - a stateless transformer:

(define-deforestable #:transformer (map [floe f])
  #:fallback
  (lambda (vs)
    (map f vs))
  #:impl
  (lambda (f next ctx src)
    (λ (done skip yield)
      (next done
            skip
            (λ (value state)
              (yield (f value) state))))))

As we can see, it does not need any persistent state (like normal map) and transforms each element of the stream using given flow expression - that is what the floe identifier stands for.

Secondly we have a look at a stateful transformer which takes the first n elements of the stream and then terminates it - like normal take does:

(define-deforestable #:transformer (take [expr n])
  #:fallback
  (λ (vs)
      (r:take vs n))
  #:impl
  (lambda (next ctx src)
    (λ (done skip yield)
      (λ (take-state)
        (define n (car take-state))
        (define state (cdr take-state))
        (if (zero? n)
            (done)
            ((next (λ ()
                     ((contract (-> pair? any)
                                (λ (v) v)
                                'take ctx
                                #f
                                src)
                      '()))
                   (λ (state)
                     (skip (cons n state)))
                   (λ (value state)
                     (define new-state (cons (sub1 n) state))
                     (yield value new-state)))
             state))))))

This one is a bit more complex but it follows the usual done/skip/yield interface we defined early on in the deforestation efforts. The interesting part is of course the inner done passed on to the upstream next that handles insufficient number of incoming elements by construcing an artificial contract and immediately failing it with the right context and original source information.

And thirdly we can have a look at deforested assoc and related assw, assv and assq:

(define-deforestable #:consumer (assoc` [expr v] [floe is-equal?])
  #:fallback
  (λ (vs)
    (assoc v vs is-equal?))
  #:impl
  (lambda (v is-equal? next ctx src)
    (λ (state)
      (let loop ((state state))
        ((next (λ () #f)
               (λ (state) (loop state))
               (λ (value state)
                 (if (is-equal? (car value) v)
                     value
                     (loop state))))
         state)))))

(define-qi-syntax-parser assoc
  [(_ v:expr) #'(assoc* v equal?)]
  [(_ v:expr is-equal?) #'(assoc` v is-equal?)])

(define-qi-syntax-parser assw
  [(_ v:expr) #'(assoc` v equal-always?)])

(define-qi-syntax-parser assv
  [(_ v:expr) #'(assoc` v eqv?)])

(define-qi-syntax-parser assq
  [(_ v:expr) #'(assoc` v eq?)])

This looks like a overkill at the first sight, doesn't it? Quite contrary! The define-deforestable in #:consumer mode is used to define the generic version with explicit value (as an expression) and equal procedure (as a flow expression). This generic version is then augmented by a few uses of simple define-qi-syntax-parser which parameterizes it as required by each different variant.

Hope you liked a glimpse into the current Qi development and hopefully we will get Qi version 6 just in time for summer solstice!

See ya next time!