drym-org / qi Goto Github PK
View Code? Open in Web Editor NEWAn embeddable flow-oriented language.
An embeddable flow-oriented language.
I guess capturing continuations in flo is an interesting idea. Assuming Qi supports let/cc
form:
(define-qi-syntax-rule (let/cc flo)
(esc (λ args (let/cc cc (apply (☯ flo) cc args)))))
(define-qi-syntax-rule (let/ec flo)
(esc (λ args (let/ec ec (apply (☯ flo) ec args)))))
We can use let/cc
as loop :
(define (factorial m)
(define-values (loop n res) (let/cc cc (values cc m 1)))
(if (zero? n)
res
(loop loop (sub1 n) (* n res))))
(define factorial
(☯
(~> (let/cc (==* _ _ 1)) ; loop × n × res
(if (~> 2> zero?)
3>
(~> (==* _ (-< _ _) _) ; loop × n × n × res
(==* (-< _ _) sub1 *) ; loop × loop × (sub1 n) × (* n res)
(_ _ _ _))))))
In general for compiler optimizations, we can assume that flows are free of side-effects(!). For cases where there are side effects, it will probably make sense to introduce a new do
form which will not do any optimizations. E.g. (do (~> some side effecting functions))
.
Conjecture: Any sequential composition of functions (i.e. via ~>
) operating on either:
... can be expressed in such a way that computing the result involves at most one pass over the input values.
I'm using the word "conjecture" here not to imply that this is an unknown theoretical result to be established but, rather, to represent my ignorance as to whether this result is true or not 😆
Some rough justification for the likelihood of the above is the "universality of fold" with respect to with map- and filter-like operations. So the problem seems to reduce (so to speak) to, "is any composition of functions that fold over the input list expressible as a single function that folds over the list?"
It may be that we should narrow the scope of the optimization specifically to map
, filter
, and fold
operations, rather than any functions composed via ~>
. Towards this end, it may be useful to first determine the pairwise composition:
(~> (fold f init-a) (fold g init-b))
→ (fold h init-c)
... where we'd need to define h
in terms of f
and g
and init-c
in terms of init-a
and init-b
(where f
, g
and h
are the binary functions used in folding, and init-a
, init-b
and init-c
are the seed values used).
Since we already have ways to transform map
to fold
and also filter
to fold
in general (by virtue of "universality"), that should mean that we can transform any sequence of map
, filter
, and fold
operations into a sequence of fold
operations alone, and then with the above pairwise composition available, we would be able to express that as a single fold operation by iterating the pairwise composition (folding over the folds!).
Presumably, it will be easier to focus on lists at first to understand the general approach while using a standard data structure. Then, the approach could be easily(?) extended to work with pure values not contained in any collection (i.e. pipelines like (~> (>< f) (pass g))
).
Assuming we can define the pairwise composition of folds mentioned above, then iterating this (by folding) on the input syntax could be one way to achieve deforestation.
The docs for Rebellion re: "transducers" describe how they can be thought of as a state machine (an intuitive way to look at it!). This could be another implementation strategy.
Is there anything in academic literature or in other programming languages that could be applicable here? Here are some resources that may be relevant:
Positive Supercompilation for a Higher-Order Call-By-Value Language (from @soegaard)
Clojure's Transducers
Common Lisp's Series
Note: Qi is already macro-extensible as of 80509ab. But this does not use the scheme proposed in the above paper, and is only a small step toward the eventual goals on this front (articulated below).
What we'd like to achieve here is "first class" syntactic extensibility -- i.e. extensions written by users should have the same status as "core" Qi forms -- with the following goals in mind:
At the moment, the Qi core contains many forms of broad utility. But some forms are arguably more specialized and need not be in the core (such as the numerous boolean gates). We'd like to distill a core set of forms that could be housed in e.g. qi/base
(in analogy with racket/base
)
For instance, the aforementioned boolean combinators AND OR XOR NAND
and so on could be provided as a "Combinational Logic" language pack, making the core smaller. (require qi)
could include base
and also a few of these language packs, to achieve rough parity with what is already provided in the library.
But a more interesting benefit here is that such language packs could be written by anybody and distributed as independent packages on the package index. These would simply need to be require
d in source modules in order to augment Qi's capabilities for the task at hand.
Qi is a general purpose functional DSL. But there may be cases where we'd like to have similar but domain specific semantics. For instance, if we are working with analog circuit modeling, it may be necessary to introduce a number of additional forms specific to that domain, which (perhaps) would not be as relevant outside the domain. Likewise there may be forms currently in the Qi core that would be irrelevant here. We'd like to ensure the core is small enough to avoid this ever occurring, while also supporting such domain specific "dialects" of Qi to be written and for them to have first class status as languages on their own.
In addition to domain specific dialects that are different from Qi, it could potentially be useful to have dialects that are identical to Qi but which augment certain forms with behavior that may be helpful to achieve different goals. In particular, it is a design requirement of Qi to have good error messages (and this is a work in progress - please report bad error messages!), but where good error messages might conflict with performance, we generally favor performance until a good approach can be found. With a "debug" dialect of Qi, we could make the reverse tradeoff here, trading performance for good error reporting always. This could be a good language to use during development, switching to native Qi for production. Of course, such a language could be implemented as a completely parallel implementation, but that is gratuitous - it would be much better to be able to specialize the core to a dialect that modifies existing forms as needed.
Now, hopefully, good error messages can always be possible without necessitating a "debug" dialect - and that is still the preferred goal. But this example provides a window into possibilities here, which may have nothing to do with debugging. The idea is that "dialects" of Qi should be able to introduce new forms or override existing ones, and should have the same status as "Standard Qi."
Arity changes, that is, changes in the number of values being propagated, don't work in some routing forms (e.g. ==
, ><
and -<
). For instance, these don't work:
(on (5 7) (== (select) add1))
... should eat the first input value, producing only one value, i.e. the second one incremented by one.
(on (5 7) (== (-< _ _) add1))
... should split the first value into two, and increment the second, producing 3 values in all.
(on (5 7) (>< (-< _ _)))
... should split both input values into two, yielding 4 values in all.
(on (5) (-< (-< _ _) _))
... should split the input value into 2, further splitting the first into two, yielding 3 values in all.
In all of these cases, the error resembles:
; returned two values to single value return context
v8.6
Welcome to Racket v8.6 [cs].
> (require qi)
> (~> (1 2 3) (clos +) (_ 4))
10
> (~> (1 2 3) (+) (_ 4))
compose: contract violation
expected: procedure?
given: 0
argument position: 2nd
[,bt for context]
>
Welcome to Racket v8.6 [cs].
> (require qi)
> (~> (1 2 3) (clos +) (_ 4))
10
> (~> (1 2 3) (+) (_ 4))
10
>
I think currying a function directly is similar to using clos
, but to my surprise Qi seems to avoid this usage intentionally, is there any special reason?
Arguments are by default supplied in the leading positions. Employing the right-threading operator causes arguments to be supplied in the tail position, but this doesn't propagate to nested forms, requiring a fresh use of right-threading within those nested forms.
Example:
(on ("b") (~>> (string-append "a"))) ; => "ab"
as expected, but
(on ("b" "c") (~>> (>< (string-append "a")))) ; => "ba", "ca"
rather than the expected "ab", "ac"
Implementation Considerations:
At the moment, right-threading is implemented by setting a syntax property on the contained clauses in (~>> clause ...)
. This happens only in the expansion rule for the right-threading operator, and as a result, any nested clauses don't inherit this property since other expansion rules aren't aware of it.
Replacing all of the rewrite rules to explicitly propagate syntax properties via datum->syntax
instead of a simple #'
would possibly work, but it seems gratuitous. Maybe there's an easier way.
Workaround:
Explicitly indicate right-threading within the nested form:
(on ("b" "c") (~>> (>< (~>> (string-append "a"))))) ; => "ab", "ac"
or use a template:
(on ("b" "c") (~>> (>< (string-append "a" _)))) ; => "ab", "ac"
Just like Racket's cond
vs if
and Qi's switch
vs if
or partition
vs sieve
, we'd like to have a multi-clause version of bundle
:
(-< (~> (select 2 4) min)
(~> (select 1 3) max))
could be written as:
(bundle (2 4) min max)
but, to be more explicit, and in case there are more than just two cases, it could be written as:
(bundle* [(2 4) min]
[(1 3) max])
Here's a macro that does it:
(define-qi-syntax-rule (bundle* [(index ...) f] ...)
(-< (~> (select index ...) f)
...))
Suggested by @jairtrejo .
[Continuing a discussion with @benknoble and @TrueQueenBee from Racket Discord]
There may be cases where we want to transform inputs if a condition is met, and pass them through unchanged, otherwise.
Here are some considerations in designing the solution:
only-when
and only-unless
forms analogous to when
and unless
that have this behavior?when
and unless
forms currently ground when the condition is not met. Is this useful behavior?switch
)?when
rather than introduce a new form.if
, when
, unless
, pass
, gate
. Are these forms all distinct enough from one another, or is there overlap that we feel would be better avoided? How would introducing only-when
/ only-unless
vs repurposing the current when
/ unless
affect this?To help identify a good solution, we need examples! There are a few patterns here to look out for which may be relevant to consider:
(if (< a b) a b)
In your readme, and via https://pkgs.racket-lang.org/package/ionic
https://pkg-build.racket-lang.org/#f shows the build failed during docs
https://pkg-build.racket-lang.org/server/built/fail/ionic.txt for details:
current-directory: `exists' access denied for /home/root/racket/
Would you be up for creating a GitHub/racket template application for Qi?
https://racket.discourse.group/t/racket-templates-project/156?u=spdegabrielle
User 1e1001 on Discord pointed out that an expression like this is accepted:
(~> (1) (feedback _ add1))
This ends up expanding to:
(#%app
(#%app
compose
(flow (feedback _ (then _) add1)))
1)
and then to:
[Edit: added this intermediate expansion to illustrate the problem more clearly]
(#%app
(#%app
compose
(flow (~> (esc (power _ (flow add1))) _)))
1)
which then is treated as a fancy-app template, eventually becoming:
((compose
(compose
values
(lambda (_1) (power _1 add1))))
1)
This does not do what is expected (it returns the function add1
as the output).
Possible resolution: It should probably look for _
being passed in the N position and raise a compile-time error in this case.
In order to define recursive flow, I have to manually wrap it. I wonder if Qi can give a more elegant solution?
(And in this case, -<
is not equivalent to (~> (fanout N) (== flo ...))
, is it necessary to point out in the documentation?)
Welcome to Racket v8.6 [cs].
> (require qi)
> (define inf1 (☯ (-< inf1)))
> (define inf2 (☯ (== inf2)))
inf2: undefined;
cannot reference an identifier before its definition
in module: top-level
[,bt for context]
> (define inf3 (☯ (~> inf3)))
inf3: undefined;
cannot reference an identifier before its definition
in module: top-level
[,bt for context]
> (define inf4 (let ([inf4 (λ _ (apply inf4 _))]) (☯ (~> inf4))))
v8.6 [cs]
Welcome to Racket v8.6 [cs].
> (require qi)
> (procedure-arity (☯ (==* add1 add1)))
(arity-at-least 0)
> (procedure-arity (☯ (-< add1 add1)))
(arity-at-least 0)
Welcome to Racket v8.6 [cs].
> (require qi)
> (procedure-arity (☯ (==* add1 add1)))
2
> (procedure-arity (☯ (-< add1 add1)))
1
Currently, _
and __
can be used independently but not together.
There are cases where it could make sense to use them together:
(~> ("a" "c" "d") (string-append _ "b" __))
It'd be worth exploring what it would take for this to work -- ideally it can be done while leveraging functionality provided by dependencies (such as fancy-app
), without having to reinvent it.
Also, _
can be used in the first (function) position, as of #58 . But __
cannot. Would it be worth supporting a case like this one: (~> (+ 1 2) (__ 3 4 5))
?
There are no outstanding (payable) balances.
There are no outstanding (unpayable) debts.
Working with multiple values in Racket is cumbersome, requiring the use of e.g. call-with-values
. In Qi it's typically much more natural. So it would be great if in all such cases we could just use Qi. But in the case of a single expression that generates multiple values, Qi doesn't currently have an especially compelling way of handling it.
E.g. the time-apply
utility returns many values. We'd like to be able to use its results in a convenient way.
With Racket:
(call-with-values (λ _ (time-apply + (list 1 2 3))) list)
With Qi, currently:
(~> () (esc (λ _ (time-apply + (list 1 2 3)))) list)
Preferable, something like:
(~> () (gen* (time-apply + (list 1 2 3))) list)
Could it be even nicer?
Is gen*
a good name for this?
This:
(switch (-5 3) (% 1> 2>) [positive? add1])
... produces
-5, 3
... since none of the conditions match. But it should probably be
3
... instead, since that corresponds to the expectation in the consequent flows for each of the conditions. This expectation is essentially encoded in the divert clause as the "type" or "meaning" of the switch
expression.
Could this error message be improved? The most recent version of it I saw was from a new user who tried
(~> (range 1 (add1 max)) sep …)
(Notice the lack of brackets for the values of the threading form.)
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.
Here are some examples illustrating what bindings in Qi might look like:
(~> (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))))
(map (flow (~> (as args) (gen args) ...)) my-list)
equivalent to
(map (λ args (~> ...)) my-list)
(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 .
(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)
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.
The current performance benchmarks in profile/
that are run via make profile
are inaccurate, and additionally, are not comprehensive.
E.g. @michaelballantyne reports:
the difference between the flat and recursive benchmarks is an artifact of your benchmarking infrastructure. In particular,
check-value
constructs a list that is as long as the number of iterations of the test, astake
is an operation over lists rather than sequences:(for ([i (take how-many (cycle inputs))])
(fn i))It looks like the cost of constructing that list accounts for much of the time in the "Conditionals" benchmark, for example. With a testing setup that doesn't construct such a list, the Racket implementation is much faster than Qi. I suspect that in the recursive benchmarks the cost of the computation is higher relative to the construction of the list of inputs and therefore is more visible in the benchmarks.
profile/forms.rkt
to include all Qi forms (currently these include only a few such as relay
and group
).Members of the community,
If you know of any works or ideas that seem to you to be related to this project, please comment below.
Any reported related work will be considered in the process of Dialectical Inheritance Attribution (DIA) to determine:
Any reports (themselves) of related work that are accepted by the arbitrators as related represent acts of value and are recognizable as such in an ABE system.
As we add nonlocal compiler optimizations (including e.g. deforestation, #77 ), we need some way to track that the optimizations are actually making a difference. Since these are nonlocal optimizations and not related to any specific form (alone), it would be nice to expand the suite of competitive benchmarks in profile/competitive.rkt that compare performance against Racket.
This way, we would see both progress against Qi's own past performance, but also gains against Racket. It'd be nice to even beat Racket performance once in a while 😉 . Given that we are able to assume "no accidental side-effects", which Racket cannot, this seems achievable.
Examples of benchmarks we could add include:
map
, filter
and fold
)Racket includes a statistical profiler that can be useful for profiling in general. This profiler produces reports containing measured aggregate times for various functions, along with the proportion of time spent in each function, and allows you to sort the report in terms of these columns in the data. This data can be useful to identify performance bottlenecks and avenues for improvement.
Yet, the data isn't especially easy to decipher, and takes experience and some art. For Qi, it would be useful, in addition, to have a "pipeline" or "structural" profiler, which measures the time spent in each flow component. For instance, in a flow like:
(~> sqr (-< add1 sub1) *)
There are many flows of interest here -- the overall flow, each of its components, and each component of those components, which come out to 1 + 3 + 2 = 6 flows. The pipeline profiler should report on the time spent in each of these flows, organized hierarchically. This could prove to be a more intuitive and accessible alternative to the usual statistical profiler, for users looking to make quick performance assessments.
A color-coded visualization (e.g. red = "clogged", green or blue = "free flowing") built on top of the underlying performance profile data would be ideal.
Possible implementations:
A. Implement the profiler as a macro which rewrites component forms, e.g. (profile (~> sqr (-< add1 sub1) *))
. It may not be straightforward to rewrite nested flows, though, e.g. the contents of -<
.
B. Implement this as a Qi dialect, with forms like -<
and ~>
overridden to be equivalent versions that also record performance data, possibly as side effects, or in a hash. This may be feasible once a "core language" has been distilled, but it seems like a rather heavyweight option. It may involve overriding every form in the core language.
I'm quite interested in learning how to use Qi 🙂 and am going to try to use it in some of my small personal projects or coding exercises. Thanks for creating it!
I tried to install it using raco pkg install
but it seems to fail:
> raco pkg install qi-lib
Resolving "qi-lib" via https://download.racket-lang.org/releases/8.2/catalog/
Resolving "qi-lib" via https://pkgs.racket-lang.org
Downloading repository https://github.com/countvajhula/qi.git?path=qi-lib#reorganize-package-as-lib-test-doc-redux
git: could not find requested reference
reference: master
repo: countvajhula/qi.git
context...:
/opt/homebrew/Cellar/minimal-racket/8.2/share/racket/collects/net/git-checkout.rkt:403:0: select-commits
[repeats 1 more time]
/opt/homebrew/Cellar/minimal-racket/8.2/share/racket/collects/net/git-checkout.rkt:73:8
/opt/homebrew/Cellar/minimal-racket/8.2/share/racket/collects/net/git-checkout.rkt:54:2: retry-loop
/opt/homebrew/Cellar/minimal-racket/8.2/share/racket/collects/pkg/private/download.rkt:102:2: download!
/opt/homebrew/Cellar/minimal-racket/8.2/share/racket/collects/file/cache.rkt:63:2: fetch-and-continue
I did get it to work by running the command raco pkg install --type git-url "https://github.com/countvajhula/qi.git?path=qi-lib#reorganize-package-as-lib-test-doc-redux"
but this isn't great UX. Any thoughts?
Also, I'm trying to play around with it a bit with parsing one of the inputs for the second Advent of Code challenge this year and I'm having some difficulty understanding how to approach the problem (specifically around dealing with two inputs in a flow). Is there some place that would be good to ask about it for some help or insight?
See previous discussion here: https://github.com/countvajhula/qi/pull/59
@NoahStoryM : I noticed that when switch-lambda and flow-lambda use rest-args, rest-args is treated as input to flow directly. Can we consider converting rest-args from list to values first? I think it is more in line with the point-free style.
@benknoble : I would like to point out, though, that when looking at (flow-lambda args …), I can tell that the flow expects 0 or more input values, and by analogy with regular Racket I expect the values to be in a list. It is not difficult to use sep as the first part of the flow to split the rest-args. Breaking the analogy to regular Racket would be odd, and might also cause confusion in the way inputs to the flow are handled.
When the benchmarks step fails, it still returns a success error code, and the job only fails on the next step, obscuring the source of the problem, like in this example.
See this conversation for more context. Excerpts:
"the |
used in this command obscures the error result of the first command in the pipeline. Should be able to fix this in the future: https://unix.stackexchange.com/questions/14270/get-exit-status-of-process-thats-piped-to-another"
"yea, I suspect set -o pipefail
is what you want for that."
Add a loop
form, which would compile to a lambda expression defined in terms of itself, and would be specified in terms of a set of functions, something like:
(define result (loop ('(1 2 3)) (until empty?) (map first) (combine +) (next rest))
... along with the lambda forms:
(define sum-nums (loop-lambda (nums) (until empty?) (map first) (combine +) (next rest))
and
(define-loop (sum-nums nums) (until empty?) (map first) (combine +) (next rest))
Of course, these examples may be better expressed simply using folds or the built-in for
forms. But there may be other cases where this approach is preferable. For instance, it may be that these would be preferable to named lets and handwritten recursive functions in some cases. The idea is simply to provide forms to define loops exclusively in terms of functions with the arguments already implicit (much like the other forms provided by this package), and see where that gets us.
Qi recently got a try
form for exception handling. At the moment it is very basic -- a simple predicate-based dispatcher for exceptions encountered while attempting a flow on inputs.
(~> ("5")
(try add1
[exn:fail:contract? (~> ->number add1)]
[exn? 0]))
Here are some proposed improvements to this form (comments welcome):
Python's try
form supports an else
clause that is only executed if no exception was encountered, and a finally
clause that is always executed, whether an exception was encountered or not.
finally
typically would not be needed since we would commonly use (~> (try ...) finally-flo)
, but in cases where an exception is likely to be re-raised within the try
form, a finally
flow could be useful. It is questionable, though, since unlike python where side effects and mutation are common, Qi flows typically accept input and produce output. A finally
clause that is expected to be hit only when try
is in the process of re-raising an exception, seems to suggest that this flow would only be used for side effects and mutation.
It probably wouldn't be hard to support finally
if we wanted to, and in that case it would likely be treated as another "handler" flow just like any of the other handler clauses in the try
statement. On the other hand, since its use is likely to be a fringe usecase in Qi (unlike python, and even there finally
is already uncommon), its inclusion would perhaps encourage unidiomatic code (i.e. mutation and side effects) more often than it would be useful. Still, it may be better to give users the flexibility to do weird and unidiomatic things than to not trust them. "Idiom", it could be argued, is best encouraged by convention rather than by constraint. On the nth hand, well-designed constraints help the user find better ways to do things.
else
seems useful for the same reasons as the python version.
Note that else
here would mean, "if no exception was encountered" rather than "for any other exception that is encountered". For a catch-all exception, we would use exn?
or even _
.
Currently, each of the predicates in the try
form receive the raised exception, while the corresponding handler flows receive the inputs to the try
form. It may be that in some cases we would want to be able to manipulate the raised exception even in the handler flows, for instance, if we use data contained in the exception to compute an appropriate output, or if we re-raise a fresh exception based on the contained data.
There are a few different options here:
First, we could support a (=> ...)
form in handler flows, similarly to switch
where using this form propagates the output of the predicate flow to the consequent flow as the first input.
A second possibility is to support it via a syntax parameter of some kind, so that within the handler flow, a name like e
could be used and it would be bound to the exception object. I'm not sure whether this would be straightforward to implement or not, since typically, syntax parameters need to be exported at the module level, and we only want this identifier to have meaning not just within Qi but in fact within a subform of Qi (specifically try
). Using a syntax parameter I think would mean that whatever reserved word we use here (e.g. err
) would need to be exported in the Racket namespace. That seems non-ideal. It may be that we could use binding spaces for this, so that we only need to export the binding in the qi
binding space. Of course, we only need it in a subform of Qi rather than anywhere in Qi, so it's still a little more heavy-handed than would seem to be necessary, but it may be fine since we can pick an identifier that's unlikely to collide with anything else in Qi, at least.
Another option is to support a subform (as ...)
like (try flo [(as exn:fail err) handler-flo])
which would introduce the err
binding in the handler flow. I'm not sure whether inserting the binding here would be straightforward or not, and it's possible this would require broader support for bindings in Qi as a whole (which is already planned, so this wouldn't discount this option).
We could also support a combination of the above.
Any other ideas?
Loved your talk at RacketCon.
I've created a quickscript to make it easy for DrRacket users to insert ☯
https://gist.github.com/spdegabrielle/a6c1dc432599591bb7808c01ec04cfdb
bw
Stephen
PS you have my head buzzing thinking of PL's like APL and Joy.
Here's some old Frosthaven Manager code:
(define (element-cyclers es)
(for/fold ([@states empty]
[views empty]
#:result (values (reverse @states)
(reverse views)))
([e (in-list es)])
(define-values (@state view) (element-cycler e))
(values (cons @state @states)
(cons view views))))
Ignoring the details, the general pattern is that we have a function element-cycler
that returns two values; we want to map that function over function over a list es
and collect the resulting values in two parallel lists. The above code implements that, but the intent is obscured.
Using for/lists
, which I only learned about later, we could in fact write
(define (element-cyclers es)
(for/lists (@states views)
([e (in-list es)])
(element-cycler e)))
What is the corresponding Qi idiom? At first glance, it doesn't seem like ><
(amp
) and collect
are enough, because we need to split the values into parallel "streams" or "flows." Naïvely, we could write a Qi macro that wraps for/lists
via esc
; to be "natural" Qi, though, I would argue that the resulting lists should be passed as values to subordinate flows, rather than be given back as lists directly (use collect
to retrieve the lists: hopefully a compiler will avoid list-to-values-to-list).
Alternately, we could probably write a Qi macro over loop
or the fold forms that translates the original fold/cons/reverse pattern.
In either case, the number of parallel streams in the result should (must?) be a parameter of the flow.
Based on discussion in the Racket Discord.
See previous discussion here: #61
Here are some examples and rules that I believe useful: (from section 6.5.1 of Category Theory for Computing Science)
#lang racket
(require qi)
(define add (procedure-reduce-arity + 2))
(define mul (procedure-reduce-arity * 2))
(define id (procedure-reduce-arity values 1))
;; f(x, y) = x^2 + 3xy.
;; λ Calculus style
(define f (λ (x y) (add (mul x x) (mul (mul x y) 3))))
;; Cartesian Closed Categories style
(define f
(☯ (~> (-< 1> 1> 1> 2> 3) ; x x x y 3
(==* mul mul id) ; x*x x*y 3
(==* id mul) ; x*x x*y*3
(==* add)))) ; x*x+x*y*3
;; (==* f) is f
;; (==*) may map (values) to (values) ?
;; rules among `~>`, `-<` and `==*`
;; `==` is just a special case of `==*`
(-< (~> u f) (~> v g)) ; (-< (~> u f) (~> v g))
(~> (-< u v) (==* f g)) ; (~> (-< u v) (== f g))
(==* (~> f1 g1) (~> f2 g2)) ; (== (~> f1 g1) (~> f2 g2))
(~> (==* f1 f2) (==* g1 g2)) ; (~> (== f1 f2) (== g1 g2))
(-< f g) ; (-< f g)
(~> (==* _ _) (>- f g)) ; (~> (==* id id) (== f g))
Once a reliable baseline is available for Qi's performance, we will want to write a Qi-specific compiler that operates on the generated Qi code in the expansion step, to produce optimized Racket expansions.
Qi will soon have first class macro-extensibility, which means that Qi macros written by users would be indistinguishable from built-in Qi forms, allowing extension in arbitrary ways. At that stage, many of Qi's current "core" forms could themselves be implemented internally as such macros, which would expand into a small core language yet to be distilled.
In tandem with that effort, we also will want to write a compiler that will enter the lifecycle after the macro expansion phase and expand the resulting Qi forms into optimized Racket code for improved performance.
Define Qi*
to be the full Qi language including both the core forms as well as any macros, and let Qi0
be a "core" Qi language, representing the end state of Qi macro expansion. Then, the full lifecycle of a Qi expression before it is evaluated is:
Qi* → Qi0 [Qi macro expansion phase]
Qi0 → Racket [Qi compilation]
... followed by the usual Racket lifecycle which it mirrors:
Racket → Fully Expanded Racket [Racket macro expansion phase]
Fully Expanded Racket → Racket bytecode [Racket compilation]
More:
Fully Expanded Racket
Racket bytecode
Each individual macro expansion rule is a syntax transformation Qi* → Qi*
. The macro expansion phase as a whole (i.e. with repeated application of transformation rules) is a transformation χ
:
χ : Qi* → Qi0
That is, the deliverable for this phase is Core Qi.
Each individual compilation pass is a syntax transformation IR_i → IR_i+1
for some intermediate languages IR_i and IR_i+1. The initial input to this pipeline is Qi0
(i.e. IR_0 = Qi0
), and the final output is Racket (i.e. IR_n = Racket
), so that the compilation phase as a whole is a transformation ξ
:
ξ : Qi0 → Racket
That is, the deliverable for this phase is Racket.
As long as the process starts with Qi0 and delivers Racket, there are no constraints on what the intermediate languages IR_i could be. For instance, they could all be Qi0 (except the last), so that the rules are mainly nonlocal optimizations mapping combinations of Qi expressions into optimized versions. Or only some of them could be Qi0 (e.g. the early stages, consisting of nonlocal optimizations), or it could even be that IR_1 ... IR_n-1 don't resemble either Qi or Racket at all -- the point being just that there are no constraints here.
Michael Ballantyne @michaelballantyne writes:
"Here's an example of how the compiler in flow
might be transformed into a compile-time function; I'll just show one case for all
:
(begin-for-syntax
(define (qi0->racket stx)
(syntax-parse stx
[(_ ((~datum all) onex:clause))
#`(give (curry andmap #,(compile-flow #'onex)))]
...)))
The overall compiler would compose the code generator with other passes:
(begin-for-syntax
(define (compile-flow stx)
(compose qi0->racket optimize-flow)))
Finally, the new flow macro would compose a macro expander for Qi with the compiler:
(define-syntax-parser flow
[(_ flow-exp)
((compose compile-flow expand-flow) #'flow-exp))])
So all that's left is to write the macro expander expand-flow
."
Michael Ballantyne writes:
"The binding spec DSL [...] implements the macro expander part. If you wrote it by hand, it would look something like this, again just showing the case for all
:
(begin-for-syntax
(define (expand-flow stx)
(syntax-parse stx
[((~datum all) onex:clause)
#`(all #,(expand-flow #'one-x))]
...)))
plus a macro expansion clause like the one you've added to flow
right now.
The clauses for all the various Qi0 forms each follow the same pattern: match the syntax, recur on subexpressions, and reconstruct syntax. The declarative DSL implements this more concisely. (And when your language has binding forms, handles scope and binding too.)"
(For reference, the binding spec DSL.)
One of the nice things about Scribble docs is the seamless dense cross-linking that just happens when you use the simple markup provided by the language.
Unfortunately, the vast majority of Qi's forms don't benefit from this cross-linking at the moment because they are forms of the DSL that exist within the scope of the flow
macro, and aren't toplevel forms exported by the collection.
E.g. @soegaard reports, "In the code example for collect in the docs, neither the up nor down pointing triangle is clickable."
And @benknoble suggests "I think it's because they are datum-literals and not bindings"
As a result, Scribble doesn't automatically link them.
This affects all Qi forms, i.e. everything on this page, e.g. ><
, feedback
, and
, etc., except the ones that happen to have an identically-named toplevel export, such as ~>
and switch
. Even here, though, at the moment, having the toplevel switch
means that documenting the Qi-level switch
(in the "Qi Forms" page) would cause a duplicate identifier warning, unless the latter is marked with #:link-target? #f
. This causes the link to be excluded from the sidebar, so if someone is just scanning the sidebar for the form they need (e.g. in this case, switch
), they would not find it there, even though it is present in the file (workaround: click on the "Conditionals" header to navigate there and find the switch
form within it).
Related issues:
The sketching
library has a similar issue where "the identifiers aren't provided from sketching but are inserted into the expansion of the module that uses sketching," and also don't get linked in the Scribble docs.
Attempts so far:
One suggestion (also from @soegaard ) was to provide identifiers corresponding to the Qi forms from a dummy module, e.g. a file doc-helper.rkt
in the qi-doc
package, and have that export identifiers corresponding to the forms of Qi using a (provide (for-doc ...))
, and then (require (for-label qi/doc-helper))
in the Scribble file.
This succeeded in coloring the links, but didn't actually link them to the content and instead underlined them in yellow which I think indicates broken link. I haven't had a chance to try again so I'm creating this issue for now to record progress towards a fix.
At the moment, Qi supports local side effects that receive the same inputs as the annotated flows and which do not affect the functioning of those flows.
In addition, we would like to support global side effects that can be specified in one place in reference to a flow such that every component of the flow inherits the side effect.
The simplest version of this could be where the side effects compose trivially by virtue of not propagating any outputs -- similar to the way local side effects behave now, where the output is simply grounded. This could be used, for instance, to attach a (>< displayln)
side effect to every component of the flow in one place.
But it would be even more useful if these side effects could themselves compose in useful ways, i.e. I think what we are looking for here is a way to encode monadic behavior within the flow specification.
This would likely involve specifying a set of lambdas corresponding to either bind
/unit
or join
/map
/unit
, in order to define the composition semantics. We could either provide a dedicated implementation for Qi here, or possibly use the interfaces from the functional-lib package.
loop2
seems odd. It appears to expect specifically two inputs, and produces specifically one output:
Should it instead support the inputs being any number of values? Should the output be any number of values? We probably can't do both here since there would be no way to differentiate inputs to be processed from in-progress outputs. Most likely, the output should be a single value (including a list), while the input should be any number of values (and the in-progress result can be fed forward as the first input).
More generally, when are loop
and loop2
useful? Most existing usecases appear to be covered by amp
and the folds, <<
and >>
. Finally, feedback
seems to cover remaining cases. When do we need loop
and loop2
? Is it perhaps that these could be considered lower-level forms with which to implement amp
and >>
/ <<
?
User 1e1001 brought up in the inaugural Design Challenge that it would be convenient if the feedback
form could accept the N
parameter as a flow input. More generally, they pointed out that there are cases where some of the flows are unchanged across iterations, and it would be nice not to have to feed these back in each time.
A. The number of times to feed back (vs feeding back based on a while
condition) is awkward to use in some cases
B. Managing unchanging parameters in the feedback specification seems unnecessary
(feedback 3 ...)
My suspicion is that for (1), the answer is no, and for (2) the answer is yes. [Input needed: Do you agree with these answers? Also see below for more re: the rationale for the ability to modify these parameters at runtime]
Assuming the answers above are borne out, then we could formalize the design of the feedback form this way:
(feedback N)
(feedback N flo)
(feedback N (then then-flo))
(feedback N (then then-flo) flo)
(feedback (while cond-flo))
(feedback (while cond-flo) flo)
(feedback (while cond-flo) (then then-flo))
(feedback (while cond-flo) (then then-flo) flo)
In all of these cases, if any of the parameters are not specified syntactically, then they must be provided as runtime inputs. These inputs will be expected in a standard order: the while condition (cond-flo
), the final transformation (then-flo
), the actual recursive flow (flo
), followed by the data inputs.
If no parameters are specified syntactically,
feedback
... then the first input will be expected to be cond-flo
(and not N
), since the while condition is after all more general, and could model the N
case if needed. Arguably if we are modifying this parameter at runtime -- already perhaps unusual behavior -- then the need for the modulating the former is less conceivable than the latter, and so the latter could be more practically useful. But it's hard to design for such cases without practical examples to work with (and the former preserves backwards compatibility so there would need to be a concrete reason to change it).
Now, to be honest, I don't really recall the motivation for the ability to modify parameters (e.g. cond-flo
) at runtime to begin with, but at least, it's a pattern that doesn't overlap with the syntactic usecases, so there's no harm in supporting both until we can find out whether it is truly more expressive in some way, or not. It does seem interesting that you can essentially write parts of the program at runtime by providing flow inputs, but I'm not quite sure what to make of it. Edit: The reason for accepting parameters as runtime or "control" inputs is that this is an alternative to having bindings. That is, we are able to leverage Racket's bindings at the top level of a flow specification, via e.g. define
, let
or even (define-flow (v ...) ...)
, but we cannot use these to give names to derived values that are produced at intermediate stages of a flow. Qi does not currently offer a way to produce bindings "natively." The options here are to either decompose flows into components whose outputs are named (using Racket definition forms), or to parametrize forms using the "control" inputs. This does mean the answer to (1) above is yes - there are cases where flow parameters cannot be specified syntactically, and would require the use of runtime "control" inputs. But the only thing this affects in the design is the pure identifier form, feedback
, and whether that should accept a while condition or a number.
All of Qi's forms can be fully specified syntactically, e.g. (>< sqr)
. But some of them can also be specified using flows encoded as input values (which we'll call "control" inputs) to these forms at runtime, e.g. (~> (-< (gen sqr) 1 2 3) ><)
. In this second version, the ><
form is specified purely at runtime, including the function to map over the input values which is provided here as a "control" input. This allows the ><
form to be controlled at runtime rather than determined at compile time.
Many Qi forms (such as pass
, feedback
, and more) already support full runtime specification, but many still don't. Review these and ensure that all forms that need to support this behavior, do.
Note to the reader: if you arrived here having encountered a case where you wanted a form to be controllable at runtime, please comment below and that form will be prioritized.
We are aiming to launch the pilot phase of Attribution Based Economics this week on the initial seed repos -- that is, Qi, Symex, and Old Abe. This issue is to track that launch from the perspective of the Qi project.
If you are a Qi contributor and I don't have your payment information, rest assured that I (as the de facto trustee -- although the process of DIA could nominate anyone to be the trustee in charge of receiving and distributing payments) will get in touch with you as soon as the amount owed to you exceeds the minimum payment threshold (likely to be set at 5 USD initially, to minimize the number of small transactions), but if you send it to me proactively, that would help: please email me at skasivaj at gmail dot com (include your Venmo or Paypal ID or any way in which you prefer to receive payment).
Learn more about Attribution Based Economics:
The talk introducing it at EmacsConf
The Extended Q&A covering a lot of questions about the implementation and goals
The ABE Financial Model
See also the companion issues for the other repos in the pilot:
It came up in the inaugural Design Challenge in the #qi room on Discord that fanout
only accepts literals and not arbitrary Racket expressions (e.g. variables).
Example (working):
(define (compose-val N f)
(flow (~> (clos f)
(-< (gen N) _) ;; since (fanout N) only works when N is a literal
fanout compose apply)))
We'd like it to also support:
(define (compose-val N f)
(flow (~> (clos f)
(fanout N) compose apply)))
This currently results in:
fanout: undefined;
(Pointed out by @benknoble)
Observed behavior: In cases where both a divert
clause as well as a =>
condition output clause are present in a switch
expression, the consequent clause in the divert expression operates on the (result of condition flow + original inputs).
Expected behavior: It should operate only on the original inputs, and the result of the condition flow should be forwarded to the consequent flow as is (as the first input).
Example:
(switch (4 -4)
(% 1> 2>)
[add1 (=> + sqr)])
This should be 5 + -4, squared = 1
, rather than + 4, squared = 16
.
Please licence under the same terms as Racket.
At the moment, the syntactic forms support ways to conveniently derive standard predicates like "less than 5" as (< 5)
by internal use of currying, while in general if the expression is not a standard one, it is compiled naively without modification. This means that custom predicates and functions are convenient to use when they have the same arity as the number of arguments in the on
/switch
form, but if they have a greater arity, they must be curried / partially applied by the user in order to present the appropriate arity in the predicate position.
Another approach to a similar but more specialized problem is that taken by the threading package, which passes the (singular) argument in the leading position, unless a different position is indicated syntactically. If this approach can be used here without compromising the generality of the forms, then that would certainly be desirable, since it would mean that we could leverage the context set by the syntactic forms in predicates of any arity without the use of currying on the client side.
Add @benknoble's generalized sieve functionality, as described in this Discourse post.
(Just creating an issue so this doesn't fall through the cracks)
The current outstanding (payable) balances are:
Name | Balance |
---|---|
Sid | 9.78 |
Racket | 3.14 |
(Michael Sid) | 2.81 |
Ben | 1.80 |
Noah | 1.19 |
typed-stack | 0.91 |
Stephen | 0.85 |
adjutor | 0.68 |
mischief | 0.68 |
Jay | 0.57 |
Michael | 0.50 |
rackunit | 0.39 |
(Ben Sid) | 0.29 |
Cassie | 0.27 |
Sam | 0.25 |
Kasivajhula 2014- | 0.23 |
Sergiu | 0.22 |
greg-racket-makefile | 0.19 |
Laurent | 0.17 |
Nia | 0.17 |
metapict | 0.16 |
cover | 0.16 |
Haskell | 0.16 |
Scheme | 0.16 |
Bogdan | 0.15 |
racket-collections | 0.13 |
cover-coveralls | 0.13 |
relation | 0.13 |
(Jesse William) | 0.12 |
APL | 0.12 |
Anonymous | 0.12 |
Threading macro | 0.12 |
pipeR | 0.12 |
Clojure | 0.11 |
Rash | 0.10 |
Lisp | 0.10 |
Symex | 0.08 |
Debug | 0.06 |
Soegaard | 0.06 |
1e1001 | 0.06 |
Scratch (MIT) | 0.06 |
VHDL | 0.06 |
Verilog | 0.06 |
Hsiao-Peng et. al. 1999 | 0.06 |
jo-sm | 0.06 |
Unix pipelines | 0.06 |
Scala | 0.06 |
Erlang | 0.06 |
Ballantyne et al 2020 | 0.05 |
(Sorawee Jack) | 0.05 |
Sarna | 0.04 |
ML | 0.04 |
Hughes 2000 | 0.04 |
Vim | 0.04 |
Python | 0.01 |
Ruby | 0.01 |
DIA | 1.50 |
Old Abe | 0.30 |
Total = 30.00
There are no outstanding (unpayable) debts.
[See Qi macro: generalized sieve (partition)]
The options here seem to be:
syntax/parse
(the current behavior)(require qi)
, and provide syntax/parse
with (require qi/macro)
(require qi)
, and don't provide syntax/parse
with (require qi/macro)
eitherFor (1):
The drawback is that users need to (require syntax/parse)
in order to use syntax patterns and syntax classes.
The benefit is that it's more explicit, and is symmetric with usual Racket behavior of having to do this in defining Racket macros. Yet, the difference here is that we have the forms define-qi-syntax-rule
without having to require something like qi/syntax-parse
which is not the case in Racket.
For (2):
The drawback with (2) is that users would need to (except-in ...)
if they happen to already require syntax/parse in the module, which could be annoying, especially if they aren't using Qi macros (but are using Racket macros).
The benefit is that users who haven't already required syntax/parse
in the module would have access to syntax patterns and classes without an additional (require syntax/parse)
For (3):
This seems to be a good compromise where users would only need to (except-in ...)
if they are already using syntax/parse
in the module and they specifically mean to write Qi macros as well. It would be backwards incompatible however, and not sure if there are any other concerns with exporting all of syntax/parse
that aren't talked about here (e.g. would it take up more memory / slow down the loading of the requiring module?).
For (4):
A final possibility for completeness is the same as (3) but without providing syntax/parse
, so that the macro module is required only on demand, and likewise syntax/parse
too must be explicitly required. This is the most conservative option, but may have some benefits (e.g. lower memory / require-time latency? Is this a real concern?). This too is backwards incompatible.
In choosing a solution, it would be ideal of course to avoid breaking backwards compatibility, but at this stage of development it is better to do the right thing than commit to supporting a wrong thing that may be a design error. So backwards compatibility should perhaps be considered a tie breaker rather than the main consideration.
For the moment, the usage for (1) has been better documented (e.g. in Defining Macros as well as in Common Encountered Errors).
Opinions welcome needed!
It appears that the Coverage step in the CI workflow fails when run on a pull request on any fork other than drym-org
, with the following error:
curl: (22) The requested URL returned error: 422
coveralls: request to coveralls failed
context...:
/home/runner/.local/share/racket/8.5/pkgs/cover-lib/cover/raco.rkt:95:3
/usr/share/racket/collects/racket/logging.rkt:43:0: with-intercepted-logging
body of (submod "/home/runner/.local/share/racket/8.5/pkgs/cover-lib/cover/raco.rkt" main)
/usr/share/racket/collects/raco/raco.rkt:41:0
body of "/usr/share/racket/collects/raco/raco.rkt"
body of "/usr/share/racket/collects/raco/main.rkt"
E.g. see this workflow log.
My guess is that it has something to do with the COVERALLS_REPO_TOKEN
secret which is part of the test-env
environment that's used by CI. This is the same environment that is used on all commits, so I'm not sure why the secret would be present only when running CI on @countvajhula commits vs someone else's commits.
It might be related to lemurheavy/coveralls-public#1435 .
UPDATE: The repo settings page on GitHub at Settings -> Secrets -> Actions, says this: "Secrets are not passed to workflows that are triggered by a pull request from a fork. Learn more." I didn't see any elaborations of this in the "learn more" link.
@sarna reported on Discord that startup time is on the order of hundreds of milliseconds. They suggested this way to test it:
base.rkt:
#lang racket/base
(displayln "hey!")
qi.rkt:
#lang racket/base
(require qi)
(displayln "hey!")
After running raco setup
to ensure that Qi is compiled, the results are:
$ time racket base.rkt
hey!
real 0m0.270s
user 0m0.134s
sys 0m0.085s
$ time racket qi.rkt
hey!
real 0m0.812s
user 0m0.661s
sys 0m0.141s
Suggestions from @Bogdanp:
"[There's not much you can do] apart from ensuring those [...] are compiled (by running raco setup). lazy-require may help if some of the work can be deferred, and raco demod might help, too, depending on how often you run the code (raco demod takes a while to run and it doesn't work in all cases)."
"If this is for a CLI tool, then I'd recommend raco demod + raco exe
raco demod foo.rkt && raco exe -o foo foo_rkt_merged.zo"
@jackfirth suggests:
"using #lang racket/base instead of #lang racket helps
but options are limited
it's a problem that really needs some VM work to solve"
Qi already does use #lang racket/base
in all modules (except in test modules, but I don't think that would matter here) but worth double checking. Also, once the core language is available (#49 ), Qi should be able to provide something analogous to racket/base
, like qi/base
, with the option to include additional functionality via separate requires just like in Racket.
Bogdan suggests:
"I think the best library authors can do is depend on less code and write macros that generate minimal amounts of code (i.e. write helper functions and have macros expand to calls to those functions instead of generating the same code over and over). Depending on a subset of a module won't help, but restructuring modules such that less code is loaded overall can."
This can definitely be explored. I didn't really consider this kind of thing before so it's likely there can be some quick gains here.
Initially suggested by Sergiu Ivanov (scolobb) in the Racket Discourse. See that thread for some context.
It would be both very interesting as well as potentially useful to develop a typed version of Qi. Just registering interest here for now and there are no specific plans yet.
TBD - input welcome.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.