-
Notifications
You must be signed in to change notification settings - Fork 12
Qi Compiler Sync Oct 6 2022
Qi Compiler Sync Oct 6 2022
Adjacent meetings: Previous | Up | Next
We discussed two different ways in which bindings could be implemented in the compiler -- a "lifting lets" (ANF) approach and a "continuation passing" (CPS) approach. We also briefly discussed a possible approach to "deforestation" (a compiler optimization) that recently came up.
Last time, we talked about possible binding and scoping rules in Qi, and settled on a design. Briefly:
- bindings are scoped to the outermost containing threading form (i.e.
~>or~>>) - in the case of bindings appearing in a tee junction, earlier tines bind later tines
These rules can be ensured at the expander level by notating them in bindingspec, and they also need to be implemented at the compiler level.
When an as binding form is encountered within a threading form, wrap the (outermost) containing ~> with a let form binding those identifiers to placeholder values (e.g. undefined). Then, transform each occurrence of (as ...) to a use of set! to mutate the declared value.
Specifically, this approach entails the transformation:
- Escape to Racket to wrap outermost
~>with let and re-enter a Qi context:
(~> flo ... (... (as name) ...))
...
↓
...
(esc (let ([name (void)])
(☯ original-flow)))
- as → set!
(as name)
...
↓
...
(~> (esc (λ (x) (set! name x))) ⏚)
- Overall transformation:
(~> flo ... (... (as name) ...))
...
↓
...
(esc (let ([name (void)])
(☯ (~> flo ... (... (~> (esc (λ (x) (set! name x))) ⏚) ...)))))
This approach involves an extra initial pass to lift the lets, but once that's done, each component can be separately compiled.
This approach involves nesting to the right instead of separately compiling the components, ensuring sequential scope by wrapping subsequent components in layers of lambdas and call-with-values.
For instance,
(~> (~> f1 (as x)) (~> (lambda (y) (+ x y))))
... compiles to:
(lambda vs1
(call-with-values
(apply f1 vs1)
(lambda vs2
(let-values ([(x) (apply values vs2)])
(apply (lambda (y) (+ x y))
vs2)))))
More illustrative code examples are in the Appendix below.
We agreed that it would be good to continue with the ANF/lifting lets approach since it is perhaps simpler. We can revisit this in the future if any other considerations come to light (for instance, is the output of one or the other easier for the Racket compiler to reason about and therefore optimize? Naively, CPS seems to be more explicit about the binding structure).
We discussed a possible approach to deforestation that recently came up. We agreed that it would perhaps be best to treat map and filter as primitives as far as optimization rules are concerned since it may not be possible to compose folds in the general case.
- Continue implementing bindings in the compiler using the ANF approach
- Notate the binding specification in the expander
- Define the overall structure of compiler passes and continue experimenting with some initial optimizations
(From Michael, also including some examples of compilation steps and optimizations)
#lang racket/base
(match x
[(cons (cons a b) (cons c (? (lambda (v) (eq? v b)) d))
e])
;; compiles to
(let ([v x])
(if (pair? v)
(let ([v1 (car v)]
[v2 (cdr v)])
(match v1
[(cons a b)
(match v2
[(cons c d)
e])]))))
(~> (~> f1 (as x)) (~> (lambda (y) (+ x y))))
(let ([x undefined])
(~> (~> f1 (as x)) (~> (lambda (y) (+ x y)))))
[(~> f1 f2)
#`(compose
#,(compile-flow f2)
#,(compile-flow f1))]
;; compiles to
(let ([x undefined])
(compose
(~> (lambda (y) (+ x y)))
(~> (~> f1 (as x)))))
(let ([x undefined])
(compose
(lambda (y) (+ x y))
(compose
(as x)
f1)))
(let ([x undefined])
(compose
(lambda (y) (+ x y))
(compose
(lambda (v) (set! x v) v)
f1)))
(~> (~> f1 (as x)) (~> (lambda (y) (+ x y))))
;; compiles to...
(lambda vs1
(call-with-values
(apply f1 vs1)
(lambda vs2
(let-values ([(x) (apply values vs2)])
(apply (lambda (y) (+ x y))
vs2)))))
[(~> f1:id f2)
#'(lambda vs1
(call-with-values
(apply f1 vs)
f2))]
(~> (~> (~> f1 f2) f3) f4)
(~> f1
(~> f2
(~> f3
f4)))
(define (compile-flow f later)
(syntax-parse f
#:datum-literals (~>)
[(~> f1 f2)
(compile-flow #'f1
#'(lambda vs
(apply later vs)))]
[f:id
#'(lambda vs
(call-with-values
(lambda () (apply f vs))
later))] [(as x)
#'(lambda (x)
later)]))
(~> (~> f1 x)
f2)
#'(lambda vs1
(call-with-values
(apply f1 vs)
f2))]
(~>
(~> f1^ ; must return one value
(as x)) ; whole thread returns one value
(~> (lambda (y) (+ x y)) ; expects one value
)) ; thread returns one value
;; drop extra ~>
(~>
(~> f1^ ; must return one value
(as x)) ; whole thread returns one value
(lambda (y) (+ x y)) ; expects one value
)
;; fixed arity to pass; implement as just an application (or a let)
(lambda (vs)
(let-values ([(v1) (let-values ([(v2) (apply f1 vs)])
;; problem: can't bind x to be visible later because not ANF
(as x))])
((lambda (y) (+ x y))
x)))
;; lift out lets via ANF, expand (as x) to insert let binding
(lambda vs
(let-values ([(v2) (apply f1 vs)])
(let-values ([(x) v2])
(let-values ([(v1) v2])
((lambda (y) (+ x y))
x)))))
; Drop no-op let-values, inline application where argument is just a reference
(lambda vs1
(let ([x^ (apply f1 vs)])
(+ x x^)))
#lang racket/base
(require syntax/parse)
(define (compile-flow f later-stx)
(define/syntax-parse later later-stx)
(syntax-parse f
#:datum-literals (~> as)
[(~> f1 f2)
(compile-flow #'f1
(compile-flow #'f2 #'later))]
[f:id
#'(lambda vs
(call-with-values
(lambda () (apply f vs))
later))]
[(as x)
#'(lambda (x)
(later x))]))
(compile-flow #'(~> (~> f1 (as x))
f2)
#'values)
(-< f1 f2)
#;(lambda vs
(call-with-values
(lambda () (apply f1 vs))
(lambda (x)
((lambda vs
(call-with-values
(lambda ()
(apply f2 vs))
values))
x))))
Camilo, Michael, Sid
Home | Developer's Guide | Calendar | Events | Projects | Meeting Notes