VC is just a calculus, and as such there are no performance concerns. Still, I find it weird that `all` is essentially a collector operation, and that's the only way to "get all the outputs" of an [generator] expression. In jq, because the jq executable itself outputs all the values of the given jq expression [applied to every input to the jq executable, unless -n is given] there is no need to collect all outputs in order to do something with them. What this amounts to is that the jq programmer can trivially implement list fusion, for example, as jq expressions are by default online, and you only lose the online property if you resort to collecting values.
I've not yet looked at the Verse programming language, but I would hope that the language -unlike the calculus- does not force one to give up the online property all the time like VC does.
OTOH, the `one`<->`all` duality is quite elegant -- a tour de force, and a great insight.
This has me wondering how to add unification to jq, or even what a jq calculus might look like.
For example, we can cut the jq language way down, removing even `reduce`, array and object constructor syntax, array and object index syntax, and even `if`, and have just values, expressions, very few built-ins (like `empty/0`, `first/1`, array and object constructor and indexer functions, and maybe a `cond/3`) and application, then we can construct reduction out of recursion, and then the rest of the jq prelude. jq is very close to a calculus as it is.
In particular how to add unification to jq... here's my thoughts:
- add a unification operator, like `?=`, so `lhs ?= rhs | e` would evaluate `e` with all the unified bindings in `lhs` and `rhs` when the equation is true -- the `lhs` and `rhs` would have to be destructuring binders, not regular expressions
- to evaluate the lhs and rhs evaluate all of the rhs for each value produced by the lhs, and then whenever their binders are equal execute the downstream expression `e`
This could be optimized so that as the VM evaluates the rhs it would prune the evaluation as soon as a binding does not match the binding established by the lhs. Right, the evaluation of the rhs can proceed as usual but it wouldn't establish new bindings but, rather, whenever it would have had it been the lhs just check that the binding to be established matches the one currently established, and if not then backtrack immediately.
A bit brute force, being O(N^2), but hey, first the jq programmer can arrange things so that the pruning behavior yields better performance than N^2, and second the compiler could learn to reason about the lhs and rhs and come up with better solutions, though at the cost of compile-time (which for an interpreted language is not unimportant).
VC is just a calculus, and as such there are no performance concerns. Still, I find it weird that `all` is essentially a collector operation, and that's the only way to "get all the outputs" of an [generator] expression. In jq, because the jq executable itself outputs all the values of the given jq expression [applied to every input to the jq executable, unless -n is given] there is no need to collect all outputs in order to do something with them. What this amounts to is that the jq programmer can trivially implement list fusion, for example, as jq expressions are by default online, and you only lose the online property if you resort to collecting values.
I've not yet looked at the Verse programming language, but I would hope that the language -unlike the calculus- does not force one to give up the online property all the time like VC does.
OTOH, the `one`<->`all` duality is quite elegant -- a tour de force, and a great insight.
This has me wondering how to add unification to jq, or even what a jq calculus might look like.
For example, we can cut the jq language way down, removing even `reduce`, array and object constructor syntax, array and object index syntax, and even `if`, and have just values, expressions, very few built-ins (like `empty/0`, `first/1`, array and object constructor and indexer functions, and maybe a `cond/3`) and application, then we can construct reduction out of recursion, and then the rest of the jq prelude. jq is very close to a calculus as it is.
In particular how to add unification to jq... here's my thoughts:
- add a unification operator, like `?=`, so `lhs ?= rhs | e` would evaluate `e` with all the unified bindings in `lhs` and `rhs` when the equation is true -- the `lhs` and `rhs` would have to be destructuring binders, not regular expressions
- to evaluate the lhs and rhs evaluate all of the rhs for each value produced by the lhs, and then whenever their binders are equal execute the downstream expression `e`
This could be optimized so that as the VM evaluates the rhs it would prune the evaluation as soon as a binding does not match the binding established by the lhs. Right, the evaluation of the rhs can proceed as usual but it wouldn't establish new bindings but, rather, whenever it would have had it been the lhs just check that the binding to be established matches the one currently established, and if not then backtrack immediately.
A bit brute force, being O(N^2), but hey, first the jq programmer can arrange things so that the pruning behavior yields better performance than N^2, and second the compiler could learn to reason about the lhs and rhs and come up with better solutions, though at the cost of compile-time (which for an interpreted language is not unimportant).