Internals: backtracking

The jq language is a generator/backtracking-type functional language. Expressions produce zero, one, or more results. Producing zero results is the same backtracking, and as a result the empty builtin triggers backtracking.

When backtracking, the VM unwinds the stack, freeing garbage as it goes, up to a saved point (a ”fork point“), restarting at that point. The resumed instruction knows that a backtrack has occurred and can do a variety of things as a result, such as: produce the next result in some low-level operation (e.g., EACH, for .[], INDEX for .[expr]). Many built-in generators work by catching backtracking and producing the next value until there are no more values to produce, in which case they backtrack.

Generators can be implemented in terms of existing jq language functionality. For example, the new range(init;upto;by) builtin is a jq-coded function, using only:

Programmers familiar with the internals of Schemes, LISPs, or more esoteric languages like Prolog or Icon, will probably understand easily how jq generators and backtracking work.

Leave a Comment