12
$\begingroup$

jq is a command-line tool for filtering and transforming JSON data, in the vein of sed and awk, including a bespoke programming language for writing the filters. Its original author described it as

designed to be concise and easy to use for simple tasks, but if you dig a little deeper you'll find a featureful functional programming language hiding underneath

The paradigm of that programming language is unusual: it is pure-functional, but the core model is of a single stream of filters selecting or producing values, connected by pipes (as in a shell pipeline). I won't rehash the manual, but a few core characteristics in brief:

  • Each filter takes in one data value at a time and can produce any number of outputs, all of which are projected through the next filter individually.
  • Certain constructs capture many produced outputs into a single one, like the array construction circumfix [ .articles[].title ], which produces one array containing all values from the filter inside.
  • Other constructions implicitly project single values into multiple entries, like using a multi-output filter within an object constructor [1,2,3]|{x: .[]}, which will produce multiple objects into the stream.
  • Inputs can be distributed across multiple filters with a comma .[] | tostring, sqrt, producing the combined output of all of them interleaved.
  • Variable bindings can remember a specific value from an ancestor filter in the derivation of the current value — one of the ways it's visibly not just a flat stream.

Some properties silently fall out of these rules unnoticed, like [1,2,3] constructing an array of three numbers. The manual provides a more complete description of the language semantics, and there could well be corner cases or other features that are relevant.

Is there a name for this evaluation model and paradigm, that I could use to find more instances of it?

There are strong similarities to the list monad, with | as the bind operation, and it is clearly a data-flow system in many respects, but I'd like to find the term or terms that encapsulate or collectively identify the paradigm of the language. It may well (likely will) be a conjunction of terms, though if there's a single established name that'd be great too.

$\endgroup$
11
  • 3
    $\begingroup$ The relevant terms seem to be dataflow programming, pipelines and stream processing, but these terms mostly appear in your question. So I'm not sure this is worthy of an answer. $\endgroup$
    – kaya3
    Jun 7, 2023 at 13:28
  • 1
    $\begingroup$ I personally think this is on-topic. It is about a programming paradigm. Also, I'm not sure of the name myself and want to know more about it. So maybe the question author can add a question regarding resources about the paradigm? $\endgroup$ Jun 7, 2023 at 19:44
  • 2
    $\begingroup$ @kaya3 It's possible that "dataflow pipeline" is the best available term, but the answer I'm hoping for is something like "this is x-based y dataflow programming", with X and Y accounting for e.g. the preservation of derivations whenever it branches rather than being a flat pipeline. That is, that there's a specific family of pipeline processing that this is, not just within the broad category - it's not semantically parallel to Unix pipes, for example. I'm not going to be shocked if there isn't one, but I figure it's more likely than not that there's something to identify them. $\endgroup$
    – Michael Homer
    Jun 7, 2023 at 22:43
  • 2
    $\begingroup$ @kaya3 An object pipeline (like PowerShell) is not, I think, the same model as jq — those are generally flat pipelines as far as I know, where each output object just goes into the one stream that the next filter takes in, but jq remembers how you got there — it's more list monad than pipeline. Consider something like jq -n '1,2,3 | {x:., y: (. * 2)} | .x as $a | .x, .y | "\($a) \(.)"', where $a holds the corresponding value from earlier. You can't write that in PowerShell, because each filter only runs one time for the whole pipeline, just like a Unix pipeline. $\endgroup$
    – Michael Homer
    Jun 8, 2023 at 2:05
  • 1
    $\begingroup$ XPath is probably relevant, since it has a similar data model for querying XML. And it’s much more thoroughly specified, so somewhere in that hefty amount of text might be a mention of terminology and prior art. $\endgroup$
    – Jon Purdy
    Jun 13, 2023 at 9:09

1 Answer 1

8
$\begingroup$

There are strong similarities to the list monad, with | as the bind operation, and it is clearly a data-flow system in many respects, but I'd like to find the term or terms that encapsulate or collectively identify the paradigm of the language.

In the academic literature, this ability for a single expression to evaluate to multiple values is known as nondeterministic choice, often shortened to just nondeterminism. (Yes, this can be confusing, as it has little to do with what most working programmers would call “nondeterminism”.) It’s sometimes also called ambiguous choice, though this is an older term that has mostly fallen out of usage.

To my knowledge, this concept was first introduced by John McCarthy (creator of Lisp) in A Basis for a Mathematical Theory of Computation (pdf) from 1961. McCarthy defines a function amb(x, y) that has “possible values” x and y. When used within a larger expression, the expression can be evaluated by choosing either value, much like ±x can be interpreted as either +x or −x, even when incorporated into a larger expression.

The term “nondeterminism” is used to describe these sorts of expressions because, in a sense, you can think of amb(1, 2) as “nondeterministically” evaluating to 1 or to 2. In many systems, like jq or the Haskell list monad, the program’s result involves collecting all possible results of a given expression, but from within the expression itself, these “parallel universes” cannot be directly observed. The timeline is simply split.

More modern treatments provide a variety of different interpretations and formulations of nondeterministic choice, so I will not attempt to summarize them here; you can search Google Scholar for “McCarthy nondeterminism” and get plenty of results. However, one particularly topical example of nondeterminism in the literature is the Verse language currently being developed by Epic Games, which (perhaps surprisingly) is at its core a functional logic language with nondeterministic choice very deeply baked-in.

Of course, jq includes much more than just nondeterministic choice. It also includes stream processing, a combinator language for building up parts of the program and delimiting the parts that get split into “parallel universes”, a broadcasting-like mechanism for implicitly introducing choice points, and feedback mechanisms that resemble those in functional reactive programming. But I think the core of your question—the semi-magical way that single expressions seem to produce many values—is most closely identified with nondeterminism.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .