Qi Meeting Sept 13 2024

Much Ado About Binding

Qi Meeting Sept 13 2024

Adjacent meetings: Previous | Up | Next [None]

Summary

We looked at some recently discovered issues with bindings to see if they might be resolved with the recent release of a new version of Syntax Spec, and learned more about what's going on there.

Background

We discovered a few cases where bindings in Qi were behaving unexpectedly.

Michael submitted a PR to upgrade Qi to Syntax Spec v2 earlier this week.

Bindings are implemented in Qi using the "lifting lets" approach of introducing a wrapping let form and then assigning the variable at the appropriate place using set!.

Trying Syntax Spec v2

The sole change in Qi's use of Syntax Spec was this:

- #:binding {(bind v) nested}
+ #:binding (scope (bind v) nested)

Sid was assuming it was purely a syntax change but Dominik's spidey senses, primed through decades in the security field, picked up that there was likely more behind the change. So we decided to try out the new branch and see if, indeed, it had any effect on the bindings issues.

Qi binding in a Racket expression

The issue records this behavior:

flow.rkt> (~>> (odd?) (as p) (range 10) (filter p))
; /Users/siddhartha/work/lisp/racket/qi/qi-test/tests/flow.rkt:11:16: let: duplicate identifier
;   at: p
;   in: (let ((p undefined) (p undefined) (p undefined)) (qi0->racket (thread (thread (esc (λ (p2) (set! p p2))) ground) (esc ((λ (v) (λ rest (apply v 10 (append rest (list))))) (contract (->* (real?) (real? real?) any) (range->cstream-prepare (cstream-next->li...

We tried this expression now and found that, indeed, it produces the expected result of '(1 3 5 7 9)!

Hooray!

Alright, how about the next one.

Qi binding in a Qi expression

flow.rkt> (~> (odd?) (as p) (range 10) △ (pass p))
; filter: contract violation
;   expected: (any/c . -> . any/c)
;   given: #<undefined>

We found that this still happens. Investigating, we saw that this was the Racket runtime for pass:

#'(curry filter-values (qi0->racket onex))

… where onex is p in this case. The entire eariler expression expands to:

(#%app
 (let-values (((p) undefined))
   (#%app
    compose
    (#%app curry filter-values p)
    (qi0->racket sep)
    (qi0->racket
     (#%blanket-template
      ((#%host-expression range) __ (#%host-expression 10))))
    (qi0->racket
     (thread (esc (λ (p1:45) (set! p p1:45))) ground))))
 odd?)

As curry evaluates its arguments immediately, it ends up evaluating p at compile time when the p has not yet been assigned to the runtime input odd?. We've encountered problems like this before with the use of curry, and our usual fix has been to replace it with a lambda, which evaluates its body when it is actually invoked at runtime. We replaced the implementation with this:

#'(λ args
    (apply filter-values
           (qi0->racket onex)
           args))

And that fixed the issue!

Alright, next.

Using a Qi binding as a Primitive Flow

flow.rkt> (~> (odd?) (as p) p)
; compose: contract violation
;   expected: procedure?
;   given: #<undefined>
;   argument position: 1st
;   other arguments...:
;    #<procedure:composed>

What we are expecting here is instead an arity error, as this expression is equivalent to this one:

(~> () odd?)

which is just:

(odd?)  ;=> odd?: arity mismatch;

We discovered that the unexpected error in the original expression was due to its expanding to the following:

(#%app
 (let-values (((p) undefined))
   (#%app
    compose
    (#%host-expression p)
    (qi0->racket
     (thread (esc (λ (p1:20) (set! p p1:20))) ground))))
 odd?)

The #%host-expression is expanded by Syntax Spec (at least in this instance) simply by unwrapping the host expression:

(#%app
 (let-values (((p) undefined))
   (#%app
    compose
    p
    (qi0->racket
     (thread (esc (λ (p1:20) (set! p p1:20))) ground))))
 odd?)

As a result, at this stage we can see that, due to Racket's left-to-right evaluation order, the identifier p is evaluated to undefined before the set! is evaluated.

Lazy Compose

One option we considered was to come up with some form of lazy compose, so that the bindings are not prematurely evaluated. We could potentially wrap things in lambdas to achieve this, but we didn't immediately think of how. There's also an approach (a standard approach?) where we could rewrite the compose as a series of wrapping let's, and name intermediate values using temporaries. But this approach would not be able to handle an arbitrary number of values between component functions.

Right-to-left Compose

We tried writing an rcompose function that composes functions right-to-left by first reversing them:

(define (rcompose . args)
  (apply compose (reverse args)))

And rewrote the threading rule from:

[((~or* (~datum ~>) (~datum thread)) onex:clause ...)
 #`(compose . #,(reverse
                 (syntax->list
                  #'((qi0->racket onex) ...))))]

to

[((~or* (~datum ~>) (~datum thread)) onex:clause ...)
 #`(rcompose . #,(syntax->list
                  #'((qi0->racket onex) ...)))]

so that we don't reverse the functions beforehand, to begin with.

But we discovered that even this version was evaluating the binding prematurely.

Alternatives to #%host-expression?

This case works already:

(~> (odd?) (as p) (gen p))  ;=> #<procedure:odd?>

And we realized it's because gen is already lazy as it compiles to a lambda:

[((~datum gen) ex:expr ...)
  #'(λ _ (values ex ...))]

On the other hand, #%host-expression simply unwraps the contained expression and it is evaluated immediately, and that's why using the function-valued binding as a flow doesn't work, even though gen-ing this function-valued binding does.

One resolution could be to say that we aren't able to handle this because #%host-expression is opaque from Qi's perspective and doesn't differentiate between Qi bindings and arbitrary host expressions. So, potentially, if we had a way to recognize such bindings, they could be tagged using a #%dsl-binding form instead, which we could perhaps compile to a lambda so that it's lazily evaluated.

Better Ways to Compose

We discussed that compose is in general naive and therefore slow. Thus, we should be able to improve performance of threading flows in the compiler by exploiting information we might have, such as arity of the component functions.

Next Steps

(Some of these are carried over from last time)

• 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, Sid