Advanced Topics

PRELIMINARY DRAFT

TOC

• Inner functions
• Generators
• Streams
• Recursion and Tail Recursion Optimization

Inner Functions

jq supports inner functions, which are sometimes called subfunctions. They are invisible outside the defining function.

Subfunctions are often appropriate when a function requires a specialized helper function that makes specific assumptions about its input or arguments.

Subfunctions also make it possible to write recursive functions without incurring the overhead that would otherwise be required. Examples of this are provided in the section on recursion below.

####Example#### Here is an example from jq's builtins:

def range(init; upto; by):
  def _range:
    if (by > 0 and . < upto) or (by < 0 and . > upto) then ., ((.+by)|_range)
    else .
    end;
  if by == 0 then init
  else init|_range
  end
  | select((by > 0 and . < upto) or (by < 0 and . > upto)) ;

Notes####

• The inner function definition(s) must be placed ahead of the body of the main function.
• Inner functions may themselves contain inner functions.
• The outer function parameters are visible to the inner functions.
• Shadowing of variables takes place.

Generators

Expressions such as range(0;10) generate values. These values can, for example, be passed along individually in a pipeline to the next function, or collected into an array using "[ ... ]". When a sequence of generated values is finally emitted, each value is followed by a newline.

There are at least three noteworthy points to be made about jq generators:

• Unless specifically harnessed (as discussed in the next section), generators generate all their values to completion.
• Functions that have at least one argument and that have been written as though at least one of the arguments will be a single value will act as generators if a generator is specified instead.
• If f is a jq function and if g is a generator expression, then the expression f(g) is evaluated without first generating all the values of g.

The following examples using the builtin has/1 illustrate the first two points, and the third point is the topic of the following section. For brevity, only the expression and its value (or values) are shown:

    range(0; 2)
    0
    1

    {"a": 1} | has("a")
    true

    {"a": 1} | has("a", "a")
    true
    true

Harnessing Generators

In jq 1.4+ (that is, in sufficiently recent versions AFTER 1.4), generators can be "reined in" or "harnessed". For example, limit(n; g) will terminate the generator, g, after n values have been generated:

limit(2; range(0,10))
0
1

limit/2 achieves this power courtesy of the special construct named foreach, but the important point here is that any jq function can be written to harness generators. That is, as mentioned above, jq does not compute f(g) by first generating the full sequence of values generated by g. It is as though g is passed, as an expression, into the body of the function and only probed for a value "on demand".

In jq 1.4+, there are other constructs useful for harnessing generators, notably foreach and while.

Streams

jq and jq filters are designed to process streams of JSON entities. A stream, however, is itself not a JSON entity.

If the input to a jq filter is a stream of entities, then each is presented to the filter separately. What a filter does with each item will depend on the filter. For example, empty never produces any output, whereas range(m,n) produces a stream of n-m integers for each input item.

The "," operator

The "," operator simply concatenates streams. For example, the expression

[ range(0;10), range (10; 20) ]

produces the same array as to [ range(0;20) ].

"Regular" functions

Suppose f/1 is a jq filter (i.e. a filter with arity 1), and that S is a stream. If (null | f(S)) emits the same stream as S | f(.), then we say that "f is regular at its first argument". Since regular functions have this regularity property, they have a certain predictability, and most jq functions are regular, but in special cases, the irregular behavior is precisely what is intended.

Examples:

• if S then T else U end is regular at every position.
• Short-circuit semantics: and is regular in the first input but irregular in the second. ++ If S is a stream with n items, then S | (false and .) is a stream of n values, but (null | (false and S)) simply yields false.

#####Conversion between streams and arrays The previous example shows how a stream can be converted to an array. Arrays can be converted into streams using the postfix [] operator, e.g. [1,2][] yields range(1;3).

"Cartesian product" behavior of some filters

Some filters have a kind of "Cartesian product" behavior: for example, suppose f has this definition:

def f(x;y): [., x, y];

If S, Sx and Sy are streams of respectively Sn items, Sxn and Syn items, then the expression: S | f(Sx;Sy) will produce a stream of Sn * Sxn * Syn arrays.

This Cartesian product behavior is, in a sense, the norm, so there can be surprises. For example, the expression "\( (true, false) ) and \( (true, false) )" produces 4 strings, whereas the expression (true, false) and (true, false) produces only three boolean values, because 'false and (true, false)' evaluates simply to false as the generator is never given the chance to start.

Recursion and Tail Recursion Optimization

In general, the use of recursion comes with a penalty proportional to the depth of recursion, but in jq 1.4+ (that is, in sufficiently recent versions of jq), an important class of tail-recursive functions are automatically optimized to avoid such a penalty. In particular, since around July 1, 2014, arity-0 tail-recursive functions are automatically optimized.

This optimization is often applicable when it is possible to transform a recursive function into a tail recursive function, since the latter can then be rewritten so that the only recursion occurs in a 0-arity tail-recursive inner function.

Consider, for example, the standard recursive definition of the factorial function:

def fact(n):
  if n <= 1 then n
  else n * fact(n-1)
  end;

This is nearly tail-recursive, but not quite. To make it tail-recursive, one can introduce an accumulator. To do this and to avoid the recursion-depth penalty, we will introduce a 0-arity tail-recursive inner function:

def fact(n):
  def _fact:
    # Input: [accumulator, counter]
    if .[1] <= 1 then .
    else [.[0] * .[1], .[1] - 1]|  _fact
    end; 
  # Extract the accumulated value from the output of _fact:
  [1, n] | _fact | .[0] ;

In summary, the trick is to use an inner function, and to set things up so that all the information it needs at each step is available either from its inputs or from the parameters of the outer function.

As a footnote, it should be emphasized that because jq has generators, an efficient way to compute factorials is to use reduce:

def fact: reduce range(1; .+1) as $i (1; . * $i);