A Deep Semantic and Operational Mini-Book

This is not documentation. This is not a tutorial. This is a semantic excavation.

We will treat jq as:

• A stream calculus

• A purely functional reduction algebra

• A tree traversal and rewrite system

• A scoped evaluation engine with explicit rebinding

Note

To run a jq file do that:

  Copy
  
  Copy

$ jq -f test.jq file.json


  
  

And also some sections will implicitly reference these files

• file1
• file2

1. The Execution Model: Streams, Not Values

Every jq filter is:

  Copy
  
Filter : Value → Stream<Value>

  
  

Even if it emits one value, it is still a stream. Even if it emits zero values, it is still a stream.

Composition:

  Copy
  
a | b

  
  

means:

  Copy
  
for each v in a(input):
emit b(v)

  
  

This is critical: | is not sequential mutation. It is stream composition.

2. Shape Discipline: Streams vs Arrays

Given posts.json:

  Copy
  


.[] | .title


  
  

This emits a stream of titles. NOT an array.

To collect:

  Copy
  


[ .[] | .title ]


  
  

Collection operator:

  Copy
  
[ stream ] : Stream<a> → [a]

  
  

This distinction is the root of most errors.

3. Reduction Semantics: add “Waits” for Structure

Consider:

  Copy
  


.[] | .title | length | add


  
  

At add, . is a number. But add expects an array.

Correct:

  Copy
  


[ .[] | .title | length ] | add


  
  

Execution flow:

  Copy
  
Step 1: .[] emits Post
Step 2: .title emits String
Step 3: length emits Number
Step 4: [ ... ] collects Numbers into Array
Step 5: add reduces Array to Number

  
  

Important: add cannot begin until the array is fully constructed. This is structural waiting, not concurrency.

4. group_by vs reduce: Structural vs Algebraic Grouping

Structural grouping

  Copy
  


sort_by(.userId)
| group_by(.userId)
| map({ meanTitleLen: map(.title | length) | add / length })
| sort_by(.meanTitleLen) | reverse | .[:3]


  
  

Execution:

  Copy
  
Array<Post> → sorted Array<Post> → Array<Array<Post>> → map over groups → produce Array<Summary> → sort_by mean → reverse → slice top 3

  
  

reverse and slicing

  Copy
  
reverse : [a] → [a] (reorders elements)
.[:n] : [a] → first n elements
.[m:n] : slice range

  
  

These are structural array transforms. They do not operate on streams.

5. reduce: Generator Scope vs Update Scope (Deep Explanation)

The previous explanation described the two scopes mechanically. But this example is doing something deeper:

It is emulating group_by using a fold.

Consider:

  Copy
  


reduce .[] as $p ({};
  .[$p.userId | tostring] |= (
    . // {lengths:[], maxn: 0}
    | {
        lengths: (.lengths + [($p.title | length)]),
        maxn: (
          if ($p.title | length) > .maxn
          then ($p.title | length)
          else .maxn
          end
        )
      }
  )
)


  
  

What group_by normally does

If we wrote:

  Copy
  
sort_by(.userId)
| group_by(.userId)

  
  

We would obtain:

  Copy
  
Array<Post>
→ Array<Array<Post>>

  
  

That is structural grouping.

It requires:

• Sorting first

• Holding the entire array in memory

• Building nested arrays

• Running a second aggregation pass with map

It constructs structure first. Then aggregates.

What reduce does instead

reduce performs incremental grouping.

  Copy
  
reduce GEN as $x (INIT; UPDATE)

  
  

Is equivalent to:

  Copy
  
foldl UPDATE INIT (GEN(input))

  
  

In this example:

  Copy
  
GEN   = .[]
INIT  = {}
UPDATE = object accumulation

  
  

We iterate over posts one by one.

What the accumulator represents

The accumulator starts as:

  Copy
  
{}

  
  

After several iterations, it becomes:

  Copy
  
{
  "1": { lengths: [...], maxn: ... },
  "2": { lengths: [...], maxn: ... },
  ...
}

  
  

This is a map keyed by userId.

Each key holds aggregated statistics for that group.

That is exactly what group_by + map would compute — but without ever building nested arrays.

Why the two scopes matter

During execution:

  Copy
  
GEN scope:
"." = each post
$p = that post

UPDATE scope:
"." = accumulator object
$p = current post

  
  

Two separate "." worlds.

Inside UPDATE:

  Copy
  
.[$p.userId | tostring]

  
  

Means:

"Access the accumulator bucket corresponding to this post's userId."

If it does not exist yet:

  Copy
  
. // {lengths:[], maxn: 0}

  
  

Initializes it.

Then it updates:

• Appending the title length

• Updating the maximum title length

Why this emulates group_by

Conceptually:

  Copy
  
group_by(.userId)
| map(aggregate)

  
  

Does:

  Copy
  
1. Partition into groups
2. Aggregate each group

  
  

reduce does:

  Copy
  
For each element:
  Find its group bucket
  Update that bucket

  
  

Instead of building:

  Copy
  
Array<Array<Post>>

  
  

It builds:

  Copy
  
Object<UserId → Aggregates>

  
  

It performs grouping and aggregation simultaneously.

Structural vs Algebraic Grouping

group_by is structural:

• Rearranges the data

• Creates nested arrays

• Requires sorting

reduce is algebraic:

• Keeps original order irrelevant

• Updates buckets in constant time

• Never constructs intermediate nested arrays

It is a streaming group-by.

The deeper insight

group_by builds structure, then folds.

reduce folds while grouping.

One is two-phase.

The other is single-pass.

That is why this pattern emulates group_by — but in a more algebraic and memory-efficient way.

6. Recursion: Evaluation Order and Waiting

Example

  Copy
  


def flatten_tree: if type == "array" then map(flatten_tree) | add else . end; flatten_tree


  
  

Input:

  Copy
  
[1,[2,[3,4]],5]

  
  

Flow:

  Copy
  
flatten_tree([1,[2,[3,4]],5])
→ map(flatten_tree)
→ flatten_tree(1) = 1
→ flatten_tree([2,[3,4]])
→ map(flatten_tree)
→ flatten_tree(2) = 2
→ flatten_tree([3,4])
→ map(flatten_tree)
→ flatten_tree(3) = 3
→ flatten_tree(4) = 4
→ add([3,4]) = 7
→ add([2,7]) = 9
→ flatten_tree(5) = 5
→ add([1,9,5]) = 15

  
  

Important:

• map waits for each recursive call to return.

• add waits for full array from map.

• Evaluation is depth-first.

7. type and walk

type inspects structure:

  Copy
  
"string"
"number"
"array"
"object"
"boolean"
"null"

  
  

walk(f) recursively applies f bottom-up.

Uppercase all strings (nested.json)

  Copy
  


walk( if type == "string" then ascii_upcase else . end )


  
  

walk semantics:

  Copy
  
descend to leaves
apply f to leaves
reconstruct upward

  
  

Bottom-up traversal.

8. paths, getpath, setpath: Tree Calculus

Enumerate scalar leaves

  Copy
  


paths(scalars) as $p | { path_location: $p, value: getpath($p) }


  
  

Here:

• paths emits path arrays

• . becomes a path

• Original root must be captured if needed

Why capture root?

  Copy
  


. as $root | paths as $p | select($root | getpath($p) == "rust") | ($p[0:-1]) as $parent | $root | getpath($parent)


  
  

After paths, "." is a path array. Not the document.

So:

  Copy
  
. as $root

  
  

preserves original context.

9. Ancestor Slicing: Upward Traversal

A path:

  Copy
  
["departments",0,"teams",1,"members",0,"skills",0]

  
  

Parent:

  Copy
  
$p[0:-1]

  
  

Grandparent:

  Copy
  
$p[0:-2]

  
  

General:

  Copy
  
$p[0:-n]

  
  

This is structural upward movement.

10. Structural Rewrite with reduce + setpath

Add remote:true to members with skill "rust"

  Copy
  


. as $root
| reduce ( paths as $p | select(getpath($root | $p) == "rust")
| ($p[0:-2]) ) as $member ($root; setpath($member + ["remote"]; true) )


  
  

Semantics:

  Copy
  
Generator finds paths to "rust"
Moves up two levels
Reduce accumulates updated root
Each iteration returns new root

  
  

Purely functional. Each setpath returns new structure.

11. getpath and setpath — Deep Semantics (Expanded)

Core idea: A path in jq is not traversal. It is data describing traversal. getpath interprets that data. setpath constructs a new structure using that data.

1. What Is a Path?

A path is an array of segments. Each segment is either:

• String → object key
• Number → array index

Example JSON:

  Copy
  
{
  "departments": [
    {
      "teams": [
        { "name": "compiler", "members": 5 },
        { "name": "runtime",  "members": 3 }
      ]
    }
  ]
}

  
  

Path to "runtime":

  Copy
  
["departments", 0, "teams", 1, "name"]

  
  

The path is plain data. It contains no execution.

2. Formal Semantics of getpath

  Copy
  
getpath : (JSON, Path) → JSON

  
  

Given a current context ".", and a path array:

  Copy
  
getpath(["a", 0, "b"])

  
  

jq evaluates:

  Copy
  
(((.["a"])[0])["b"])

  
  

Conceptually:

  Copy
  
function getpath(root, path):
  current = root
  for segment in path:
    current = current[segment]
  return current

  
  

Important: getpath does not modify structure. It is pure navigation.

3. setpath — Structural Reconstruction

  Copy
  
setpath(PathArray; Value)

  
  

  Copy
  
setpath : (JSON, Path, JSON) → JSON

  
  

Key insight: jq structures are immutable. setpath does not mutate. It reconstructs the tree.

If we do:

  Copy
  
setpath(["a",0,"b"]; 42)

  
  

jq conceptually performs:

  Copy
  
function setpath(root, path, value):
  if path is empty:
    return value

  head = path[0]
  tail = path[1:]

  copy = shallow_copy(root)

  copy[head] = setpath(root[head], tail, value)

  return copy

  
  

So only the nodes along the path are rebuilt. The rest of the tree is structurally shared.

4. getpath vs Direct Access

These are equivalent:

  Copy
  
.["a"][0]["b"]
getpath(["a",0,"b"])

  
  

Difference:

• Direct access hardcodes traversal.
• getpath makes traversal data-driven.

That enables meta-programming.

5. Data ↔ Structure Duality

paths turns structure into data:

  Copy
  
paths

  
  

produces:

  Copy
  
Stream<Path>

  
  

Then:

  Copy
  
getpath($p)

  
  

turns data back into structure traversal.

This is a reversible bridge:

  Copy
  
Structure → Data → Structure

  
  

6. Scoping Is Critical

Both getpath and setpath operate relative to the current ".".

Example:

  Copy
  
. as $root
| paths as $p
| select(getpath($p) == "runtime")

  
  

After paths, "." becomes a path array. If you do:

  Copy
  
getpath($p)

  
  

it will try to interpret the path relative to the path itself — not the original document.

Correct version:

  Copy
  
$root | getpath($p)

  
  

Always remember:

  Copy
  
getpath and setpath are relative to "."

  
  

7. Structural Rewrite Pattern

Canonical rewrite:

  Copy
  
. as $root
| reduce (paths as $p | select(...)) as $target
    ($root; setpath($target; NEW_VALUE))

  
  

Interpretation:

• Find structural coordinates
• Use them to reconstruct a new tree

No mutation. Only pure structural rebuilding.

8. Algebraic View

Think of JSON as a tree.

A path is a coordinate.

getpath is coordinate evaluation.

setpath is coordinate rewrite.

Together they form a minimal tree algebra.

9. Mental Model

  Copy
  
"." = current root
Path = list of instructions
getpath = interpret instructions
setpath = rebuild tree along instructions

  
  

Once internalized, jq stops being a query language. It becomes programmable tree transformation.

12. Two-Scope Problem

  Copy
  


.value | . as $u | . + { anyAboveMean: ($u.lengths | any(. > $u.meanTitleLen)) }


  
  

Inside any, "." is each element. Outer "." would be lost. So:

  Copy
  
. as $u

  
  

captures outer binding. Lexical closure simulation.

13. flatten vs flatten(1)

From your structural wrapper example:

  Copy
  


[[[[ pipeline ]]]] | flatten(1)


  
  

flatten removes nested arrays. flatten(1) removes one level only.

Important distinction:

  Copy
  
flatten is structural
.[0] is positional unwrap

  
  

14. Full Aggregation Pipeline with Scope Isolation

  Copy
  


def mean: add / length;
[[
    del(.[] | .body)
    | map(select(.userId >= 4))
    | reduce .[] as $p ({}; .[$p.userId | tostring]
      |= ( . // {lengths:[], maxn: 0}
    | { lengths: (.lengths + [($p.title | length)]),
        maxn: (if ($p.title | length) > .maxn then ($p.title | length)
               else .maxn end) } ) )
    | map_values( . + { meanTitleLen: (.lengths | mean),
                        anyLongTitle: (.lengths | any(. > 50)),
                        allLongTitles: (.lengths | all(. > 20)) } )
]]
| flatten
| .[0]
| to_entries
| map( .value + { userId: (.key | tonumber) }
        | . as $u
        | . + { anyAboveMean: ($u.lengths | any(. > $u.meanTitleLen)) } )
| sort_by(.maxn)
| reverse
| (max_by(.maxn).maxn) as $gmax
| map(. + { globalMax: $gmax })
| .[:3]


  
  

Observe:

• Wrapper arrays force delayed evaluation.

• flatten resolves structural staging.

• .[0] unwraps single layer.

• reverse + .[:3] implements top-N.

• Global aggregate captured with as.

15. Mental Model Summary

  Copy
  
"." = current context
map(f) = rebind "." to element
any/all = rebind "." to element
reduce = two separate scopes
paths = "." becomes path array
as $x = lexical capture
reverse = array reorder
.[:n] = structural slice
[0:-n] = ancestor slicing
walk = bottom-up recursive transform
add = fold over array (waits for structure)

  
  

Closing

jq is:

• A streaming calculus

• A fold algebra

• A tree rewriting system

• A scoped evaluation machine

Once you internalize:

  Copy
  
Rebinding of "."
Structural vs Stream
Generator vs Update scope
Upward vs downward traversal

  
  

You no longer “write jq”. You derive jq.

Part II — Formal Semantics, Category Theory, and Execution Visualization

17. A Formal Evaluation Model

Let’s define jq more formally.

A jq filter is a function:

  Copy
  
F : JSON → Stream(JSON)

  
  

A stream is an ordered (possibly empty) sequence of values.

Composition:

  Copy
  
(a | b)(x) = flatten( map(b, a(x)) )

  
  

This is Kleisli composition for the list monad.

jq is literally programming in the Kleisli category of lists.

18. Evaluation Diagram for Pipe Composition

Consider:

  Copy
  


.[] | .title | length


  
  

Formal evaluation:

  Copy
  
Input: [Post]
Step 1: .[] : [Post] → Stream<Post>
Step 2: .title : Stream<Post> → Stream<String>
Step 3: length : Stream<String> → Stream<Number>

  
  

Graphically:

  Copy
  
Input Array
│ .[]
│ Stream<Post>
│ .title
│ Stream<String>
│ length
│ Stream<Number>

  
  

Important: Each stage consumes a stream and produces a stream.

19. Reduce as a Fold (Catamorphism)

reduce is a fold.

  Copy
  
reduce GEN as $x (init; update)

  
  

Equivalent to:

  Copy
  
foldl update init (GEN(input))

  
  

Where:

• GEN : JSON → Stream

• update : accumulator × a → accumulator

  Copy
  
(identity, associative combine)

  
  

  Copy
  


[true, false, true] | any


  
  

  Copy
  
false OR true OR false OR true

  
  

  Copy
  
map(id) = id
map(f ∘ g) = map(f) ∘ map(g)

  
  

  Copy
  
map(f) = collect(.[] | f)

  
  

  Copy
  
.[] destroys structure (becomes stream)
map preserves structure (returns array)

  
  

  Copy
  


walk( if type == "string" then ascii_upcase else . end )


  
  

  Copy
  
Traverse children
Apply f to children results
Reconstruct parent

  
  

  Copy
  
JSON = Null | Boolean | Number | String | Array [JSON] | Object {String: JSON}

  
  

  Copy
  
Tree → Stream < Path >

  
  

  Copy
  
(Path, Tree) → Value

  
  

  Copy
  
(Path, Value, Tree) → Tree

  
  

  Copy
  
Structure ↔ Data

  
  

  Copy
  


reduce .[] as $x (0; . + $x)


  
  

  Copy
  
GEN context: "." = each element of input array
UPDATE context: "." = accumulator
$x = element

  
  

  Copy
  
Input Array
│ GEN (.[])
│ Stream<Element>
│ reduce loop:
│ accumulator₀ = 0
│ accumulator₁ = accumulator₀ + element₁
│ accumulator₂ = accumulator₁ + element₂
...

  
  

  Copy
  
. as $root | paths as $p | ...

  
  

  Copy
  
Register "." = input
Push $root
Run paths:
For each path:
Register "." = path
Push $p
Evaluate body

  
  

  Copy
  
Call stack:
flatten_tree([1,[2,[3,4]],5])
flatten_tree(1)
flatten_tree([2,[3,4]])
flatten_tree(2)
flatten_tree([3,4])
flatten_tree(3)
flatten_tree(4)

  
  

  Copy
  
3 + 4 = 7
2 + 7 = 9
1 + 9 + 5 = 15

  
  

  Copy
  
Recursion builds structure.
Reduction collapses structure.

  
  

  Copy
  
reverse : [a] → [a]

  
  

  Copy
  
.[:n]
.[m:n]
.[-n:]

  
  

  Copy
  
$p[0:-1]
$p[0:-2]

  
  

  Copy
  
Kleisli(List)

  
  

  Copy
  
f >=> g

  
  

  Copy
  
x ↦ flatten(map(g, f(x)))