qi
qi copied to clipboard
drym-org
Add the ability to define bindings
We can leverage Racket's bindings at the top level of Qi flows, but don't have a way to name intermediate values produced in flows, without decomposing the flows themselves and naming the results of each component using Racket definition forms like define and let.
The other option available now is to use "control" inputs, that is, pass parameters for a flow specification as runtime inputs to the flow. This option is perhaps equally expressive, but in some cases it is more complicated than using bindings would be.
Examples
Here are some examples illustrating what bindings in Qi might look like:
- Accumulating "state" as a side effect.
(~> (5)
(-< _ (~> list (as S))) ; `as` produces no output so only one value flows
(-< sqr (~>> list (append S) (as S)))
(-< add1 (~>> list (append S) (as S))))
- Equivalence with Racket's lambda:
(map (flow (~> (as args) (gen args) ...)) my-list)
equivalent to
(map (λ args (~> ...)) my-list)
- Naming exceptions:
(try flo [(as exn:fail err) handler-flo])
(Note: this syntax conflicts with the use of as elsewhere.)
Context: #29
More generally, the ability to introduce Qi-native bindings in this way allows us to name intermediate values computed in a flow, providing an alternative to the use of "control" inputs to parametrize flow specifications (and would allow us to do this syntactically instead -- e.g. (~> (6) ... (as n) (feedback n add1)) instead of (~> (-< 5 (gen (flow add1))) feedback). See #34 .
Bindings syntax options
(as v w)
(as v . args) ; probably can't because dot is special
(as . args) ; probably can't because dot is special
(as* v args)
(as* args)
Implementation
Could we embed Racket's pattern matching language (match) into Qi to get bindings with minimal effort? It might not be as flexible in terms of scoping rules though. Just an option to keep in mind, maybe even just as an initial version.
cc @michaelballantyne
I suggested using boxes in the implementation. I made the changes to the current compiler branch (patch at the end) and ran the benchmarks on both sides. What I saw was surprising. 35/79 (~44.87%) of the benchmarks ran slower. 16 (~20.25%) ran at exactly the same speed. The remaining 28 (~35.44%) ran faster. 48 (~60.76%) have an absolute percentage-change of less than 10%.
Those outside the 10% are (roughly)
- any? (17% speedup)
- crossover (24% slowdown)
- group (17% speedup)
- live? (15% slowdown)
- none (11% slowdown)
- none? (24% slowdown)
- one-of? (21% slowdown)
- sep (13% slowdown)
- thread-right (14% slowdown)
I might investigate these benchmarks if I have time, but I should note that the absolute difference in these "largest changes" has a spread from 5ms to 28ms.
I don't know if any benchmarks use the bindings, which is one place I'd want to really investigate.
I also don't know if these numbers include compilation time (which I would expect to suffer mildly from this change). To get the data, I ran make build && (make profile &> profile-$(git describe)) from each branch, so I would expect the relevant pieces to already be compiled?
Raw data + simple calculations (sample size: one run on each branch ‼️)
racket qi-sdk/profile/local/report.rkt
bench: compiler(ms) boxes(ms) delta=compiler-boxes(ms) delta/compiler%
AND: 99 95 4 4.0404
NAND: 44 43 1 2.27273
NOR: 40 42 -2 -5
NOT: 4 4 0 0
OR: 25 25 0 0
XNOR: 52 52 0 0
XOR: 35 33 2 5.71429
all: 131 142 -11 -8.39695
all?: 28 26 2 7.14286
amp: 203 202 1 0.492611
and: 19 19 0 0
and%: 157 153 4 2.54777
any: 101 106 -5 -4.9505
any?: 29 24 5 17.2414
apply: 104 105 -1 -0.961538
block: 10 10 0 0
bundle: 22 22 0 0
catchall-template: 112 108 4 3.57143
clos: 120 113 7 5.83333
collect: 83 82 1 1.20482
count: 90 92 -2 -2.22222
crossover: 90 112 -22 -24.4444
currying: 97 95 2 2.06186
effect: 60 60 0 0
esc: 85 77 8 9.41176
fanout: 188 200 -12 -6.38298
feedback: 136 136 0 0
foldl: 111 110 1 0.900901
foldr: 140 136 4 2.85714
gate: 81 78 3 3.7037
gen: 69 73 -4 -5.7971
ground: 16 16 0 0
group: 157 185 -28 -17.8344
if: 77 79 -2 -2.5974
input_aliases: 43 39 4 9.30233
inverter: 132 132 0 0
live?: 39 45 -6 -15.3846
loop: 168 173 -5 -2.97619
loop2: 1285 1390 -105 -8.17121
none: 134 149 -15 -11.194
none?: 25 31 -6 -24
not: 12 13 -1 -8.33333
one-of?: 41 50 -9 -21.9512
or: 19 20 -1 -5.26316
or%: 161 160 1 0.621118
partition: 239 228 11 4.60251
pass: 131 133 -2 -1.52672
rectify: 65 69 -4 -6.15385
relay: 180 180 0 0
relay*: 61 66 -5 -8.19672
select: 5 5 0 0
sep: 87 99 -12 -13.7931
sieve: 160 163 -3 -1.875
switch: 154 154 0 0
tee: 17 17 0 0
template: 19 20 -1 -5.26316
thread: 205 216 -11 -5.36585
thread-right: 126 144 -18 -14.2857
try: 191 183 8 4.18848
unless: 85 88 -3 -3.52941
when: 82 84 -2 -2.43902
cd qi-sdk/profile/nonlocal; racket report-intrinsic.rkt -l qi
bench: compiler(ms) boxes(ms) delta=compiler-boxes(ms) delta/compiler%
conditionals: 217 209 8 3.68664
composition: 8 8 0 0
root-mean-square: 791 820 -29 -3.66625
range-map-car: 14 14 0 0
filter-map: 114 110 4 3.50877
filter-map_(large-list): 274 258 16 5.83942
filter-map-foldr: 237 236 1 0.421941
filter-map-foldl: 205 218 -13 -6.34146
long-functional-pipeline: 107 111 -4 -3.73832
range-map-sum: 68 73 -5 -7.35294
filter-map-values: 276 284 -8 -2.89855
double-list: 476 496 -20 -4.20168
double-values: 425 421 4 0.941176
factorial: 195 194 1 0.512821
pingala: 228 220 8 3.50877
eratosthenes: 92 91 1 1.08696
collatz: 60 59 1 1.66667
racket qi-sdk/profile/loading/report.rkt qi-sdk/profile/loading/report.rkt
bench: compiler(ms) boxes(ms) delta=compiler-boxes(ms) delta/compiler%
(require_qi): 185 189 -4 -2.16216
Patch
commit 0806b5b1a7d249396b02f8ed6eecd1546c6e1f83
Author: D. Ben Knoble <[email protected]>
Date: Mon Dec 18 10:08:57 2023 -0500
bindings: use a box
diff --git a/qi-lib/flow/core/compiler.rkt b/qi-lib/flow/core/compiler.rkt
index 84adc4e..50ed118 100644
--- a/qi-lib/flow/core/compiler.rkt
+++ b/qi-lib/flow/core/compiler.rkt
@@ -102,8 +102,15 @@ (define (bound-identifiers stx)
;; wrap stx with (let ([v undefined] ...) stx) for v ∈ ids
(define (wrap-with-scopes stx ids)
- (with-syntax ([(v ...) ids])
- #`(let ([v undefined] ...) #,stx)))
+ (with-syntax ([(v- ...) (generate-temporaries ids)]
+ [(v ...) ids])
+ #`(let ([v- (box undefined)] ...)
+ (let-syntax ([v (make-set!-transformer
+ (syntax-parser
+ #:literals {set!}
+ [(set! var val) #'(set-box! v- val)]
+ [var #'(unbox v-)]))] ...)
+ #,stx))))
(define-qi-expansion-step (process-bindings stx)
;; TODO: use syntax-parse and match ~> specifically.
I started a PR to add any benchmarks that might reveal a difference here, #138 .