パイプライン指向JSON処理プログラミング言語jqを手計算する妄想

JSONを処理するjqについて、下記の記事を読んで「おもしれー言語」と思い、妄想が捗ったのでメモしておく。

パイプライン指向JSON処理プログラミング言語 jq - 檜山正幸のキマイラ飼育記 (はてなBlog)

無限列

自然数の集合 {0, 1, …} をNと書くことにする。 集合A上の無限列とは、NからAへの写像xs: N → Aである。

厳密な話がしたいわけでもないので、例示する場合は写像ではなく外延的な記法で無限列を書くことにする。 例えば、偶数の無限列は<0, 2, 4, …>と書くことにする。なぜ [] ではなく、<> を使うかと言うと、JSONの配列に [] が使われてしまったからだ。残念。

$ jq -n 'def even(n): n, even(n + 2); even(0)'
0
2
4
.
.
.

有限列

自然数n ∈ Nから得られる有限集合{0, 1, …, n - 1}をnと書くことにする。 集合Aの有限列とは、nからAへの写像xs: n → Aである。

こちらも厳密な話がしたいわけでもないので、例示する場合は写像ではなく外延的な記法で有限列を書くことにする。 例えば、写像0 ↦ 5, 1 ↦ 2, 2 ↦ 8については、「↦」の右側のみを残し、<5, 2, 8>と書くことにする。

$ jq -n '(5, 2, 8)'
5
2
8

列

集合A上の列とは、A上の無限列、または有限列のことである。 集合A上の列の集合を<A>と書くことにする。 すなわち、<A> = $${\{\text{xs}: \bf{N} \to A\} \cup \bigcup_{\text{n} \in N} \{\text{xs}: n \to A\} }$$である。

逐次的に列を計算したいことがあるので、列の先頭をカンマで切り離して書けることにする（「<」がカンマを自在にすり抜けるイメージ）。

<5, 2, 8>
= 5, <2, 8>
= 5, 2, <8>
= 5, 2, 8, <>

$ jq -n '(5, 2, 8)'
5
2
8
$ jq -n '5, (2, 8)'
5
2
8
$ jq -n '5, 2, (8)'
5
2
8
$ jq -n '5, 2, 8, empty'
5
2
8

列値写像

集合値写像のノリで、列を返す写像を列値写像と呼ぶことにする。 つまり、列値写像の終域は列の集合でなければならない。

• f: A → <B>なら、fは列値写像

例えば、列値写像f(x) = <x, x>について、f(5) = <5, 5>と計算できる。

$ jq -n '5 | ., .'
5
5

高階列値写像

高階関数のノリで、列値写像を引数にとったり、列値写像を返す写像を高階列値写像と呼びたい。

おそらくjqのフィルターを構成するもっとも基礎的な要素は列値写像だろう。 その列値写像を別の列値写像にするためのオペレーターが高階列値写像だと思われる。そして、高階列値写像を支える基礎的な操作は列の連接である。

列の連接

ある列の後ろに別の列をつなげて新たな列を作る操作を連接と呼ぶことにする。 列xsとysの連接をxs, ysと書く。注意として、この表記を採用した瞬間に、列の入れ子は表記できなくなる。しかし、jqにおける列（ストリーム）は入れ子にできないので、あまり問題にならない。

• <>, ys = ys

• (x, xs), ys = x, (xs, ys)

例えば、次のように計算できる。

<5, 2, 8>, <3, 7>
= 5, (<2, 8>, <3, 7>)
= 5, 2, (<8>, <3, 7>)
= 5, 2, 8, (<>, <3, 7>)
= 5, 2, 8, <3, 7>
= 5, 2, <8, 3, 7>
= 5, <2, 8, 3, 7>
= <5, 2, 8, 3, 7>

$ jq -n '(5, 2, 8), (3, 7)'
5
2
8
3
7

列の連接の単位元

空列<>は列の連接における単位元である

• <>, xs = xs

• xs, <> = xs

例えば、次のように計算できる（「>, <」が溶けて消えるイメージ）。

<>, <5, 2, 8>
= <5, 2, 8>

<5, 2, 8>, <>
= 5, (<2, 8>, <>)
= 5, (2, (<8>, <>))
= 5, (2, (8, (<>, <>)))
= 5, (2, (8, <>))
= 5, (2, <8>)
= 5, (<2, 8>)
= <5, 2, 8>

$ jq -n 'empty, (5, 2, 8)'
5
2
8
$ jq -n '(5, 2, 8), empty'
5
2
8

列の連接の結合律

列の連接は結合律を満たす。そのため連続する連接の括弧は省略できる。

• (xs, ys), zs =xs, (ys, zs)

例えば、次のように計算できる。

(<0, 1>, <2, 3, 4>), <5, 6, 7>
= <0, 1, 2, 3, 4>, <5, 6, 7>
= <0, 1, 2, 3, 4, 5, 6, 7>

<0, 1>, (<2, 3, 4>, <5, 6, 7>)
= <0, 1>, <2, 3, 4, 5, 6, 7>
= <0, 1, 2, 3, 4, 5, 6, 7>

$ jq -n '((0, 1), (2, 3, 4)), (5, 6, 7)'
0
1
2
3
4
5
6
7
$ jq -n '(0, 1), ((2, 3, 4), (5, 6, 7))'
0
1
2
3
4
5
6
7

連接列値写像

列値写像f: A → <B>を、列を受け取るように拡張した写像f*: <A> → <B>が作れる。 これを連接列値写像と呼ぶことにする。 連接列値写像は、入力の列の各値に列値写像を適用し、得られた列を連接することで最終的な列を得る。

• f*(<>) = <>

• f*(x : xs) = f(x), f*(xs)

例えば、列値写像f(x) = <x, x>から作った連接列値写像f*は次のように計算できる。

f*(<5, 2, 8>)
= f*(5, <2, 8>)
= f(5), f*(<2, 8>)
= f(5), f(2), f*(<8>)
= f(5), f(2), f(8), f*(<>)
= f(5), f(2), f(8), <>
= f(5), f(2), f(8)
= <5, 5>, <2, 2>, <8, 8>
= <5, 5, 2, 2, 8, 8>

$ jq -n '(5, 2, 8) | ., .'
5
5
2
2
8
8

fをf*に変換する * :  (A → <B>) → (<A> → <B>)は高階列値写像である。

列値写像の合成（パイプ、|）

列値写像の合成をパイプで書く。

• (f | g)(s) = g*(f(s))

例えば、列値写像f(x) = <x, x>, g(x) = <x + 1>について、次のように計算できる。

(f | g)(5)
= g*(f(5))
= g*(<5, 5>)
= <6, 6>

$ jq -n 'def f: ., .; def g: . + 1; 5 | (f | g)'
6
6

パイプ | : (A → <B>) × (B → <C>) → (A → <C>)は高階列値写像である。

パイプの単位元（ドット、.）

与えられた値から成る単一の列を返す列値写像を単位unitと呼ぶことにする。 つまり、unit(x) = <x>である。 単位はパイプの単位元になる（モナド則の単位元的なやつ）。

• unit | f = f

• f | unit = f

例えば、列値写像f(x) = <x, x>について、次のように計算できる。

(unit | f)(5)
= f*(unit(5))
= f*(<5>)
= <5, 5>

(f | unit)(5)
= unit*(f(5))
= unit*(<5, 5>)
= <5, 5>

f(5)
= <5, 5>

$ jq -n 'def f: ., .; 5 | (. | f)'
5
5
$ jq -n 'def f: ., .; 5 | (f | .)'
5
5
$ jq -n 'def f: ., .; 5 | f'
5
5

連接と合成の順序交換

合成してから連接列値写像へ変換しても、連接列値写像に変換してから合成しても同じ写像になる（モナド則の結合律的なやつ）。

• (f | g)*(xs) = g*(f*(xs))

例えば、列値写像f(x) = <x, x>, g(x) = <x + 1>について、次のように計算できる。

(f | g)*(<5, 2, 8>)
= (f | g)(5), (f | g)(2), (f | g)(8)
= g*(f(5)), g*(f(2)), g*(f(8))
= g*(<5, 5>), g*(<2, 2>), g*(<8, 8>)
= <6, 6>, <3, 3>, <9, 9>
= <6, 6, 3, 3, 9, 9>

g*(f*(<5, 2, 8>))
= g*(<5, 5, 2, 2, 8, 8>)
= <6, 6, 3, 3, 9, 9>

$ jq -n 'def f: ., .; def g: . + 1; (5, 2, 8) | (f | g)'
6
6
3
3
9
9
$ jq -n 'def f: ., .; def g: . + 1; ((5, 2, 8) | f) | g'
6
6
3
3
9
9

パイプの結合律

パイプは結合律を満たす。そのため連続するパイプの括弧は省略できる。

• (f | g) | h = f | (g | h)

例えば、列値写像f(x) = <x, x>, g(x) = <x + 1>, h(x) = <2x>について、次のように計算できる。

((f | g) | h)(5)
= h*((f | g)(5))
= h*(g*(f(5)))
= h*(g*(<5, 5>))
= h*(<6, 6>)
= <12, 12>

(f | (g | h))(5)
= (g | h)*(f(5))
= (g | h)*(<5, 5>)
= (g | h)(5), (g | h)(5)
= h*(g(5)), h*(g(5))
= h*(<6>), h*(<6>)
= <12>, <12>
= <12, 12>

$ jq -n 'def f: ., .; def g: . + 1; def h: . * 2; 5 | ((f | g) | h)'
12
12
$ jq -n 'def f: ., .; def g: . + 1; def h: . * 2; 5 | (f | (g | h))'
12
12

パイプのゼロ元（empty）

すべての値に空列を返す写像をemptyと呼ぶことにする。 つまり、empty(x) = <>である。 emptyはパイプのゼロ元である。

• empty | f = empty

• f | empty = empty

例えば、列値写像f(x) = <x, x>について、次のように計算される。

(empty | f)(5)
= f*(empty(5))
= f*(<>)
= <>

(f | empty)(5)
= empty*(f(5))
= empty*(<5, 5>)
= empty(5), empty(5)
= <>, <>
= <>

empty(5)
= <>

$ jq -n 'def f: ., .; 5 | (empty | f)'
$ jq -n 'def f: ., .; 5 | (f | empty)'
$ jq -n '(5, 2, 8) | empty'

２引数の写像の列への持ち上げ

２引数の写像 μ: A × B → C を列の２引数の写像 μ: <A> × <B> → <C> に持ち上げる（μを中置記法で書いており、無名関数を↦で書いている）。

• xs μ ys = (y ↦ (x ↦ <x μ y>)*(xs))*(ys)

例えば、数値の和について次のように計算できる。

<5, 2, 8> + <3, 7>
= (y ↦ (x ↦ <x + y>)*(<5, 2, 8>))*(<3, 7>)
= (y ↦ (x ↦ <x + y>)*(<5, 2, 8>))(3), (y ↦ (x ↦ <x + y>)*(<5, 2, 8>))(7)
= (x ↦ <x + 3>)*(<5, 2, 8>), (x ↦ <x + 7>)*(<5, 2, 8>)
= (x ↦ <x + 3>)(5), (x ↦ <x + 3>)(2), (x ↦ <x + 3>)(8), (x ↦ <x + 7>)(5), (x ↦ <x + 7>)(2), (x ↦ <x + 7>)(8)
= <5 + 3>, <2 + 3>, <8 + 3>, <5 + 7>, <2 + 7>, <8 + 7>
= <8>, <5>, <11>, <12>, <9>, <15>
= <8, 5, 11, 12, 9, 15>

$ jq -n '(5, 2, 8) + (3, 7)'
8
5
11
12
9
15

２引数の写像の列値写像への持ち上げ

列の２引数の写像 μ: <A> × <B> → <C> を列値写像の２引数の写像(D → <A>) × (D → <B>) → (D → <C>)に持ち上げる（μを中置記法で書いているので注意）。

• (f μ g)(x) = f(x) μ g(x)

例えば、文字列の連接を使った列値写像f(x) = <x + "a", x + "b">, g(x) = <x + "0", x + "1", x + "2">について、次のように計算できる。

(f + g)("/")
= f("/") + g("/")
= <"/a", "/b"> + <"/0", "/1", "/2">
= <"/a/0", "/b/0", "/a/1", "/b/1", "/a/2", "/b/2">

$ jq -n '"/" | ((. + "a", . + "b") + (. + "0", . + "1", . + "2"))'
"/a/0"
"/b/0"
"/a/1"
"/b/1"
"/a/2"
"/b/2"

なお、jqのいくつかの二項演算子は、二項演算を列値写像まで持ち上げたものとして理解できる。

単位元の列への持ち上げ

２引数の写像を持ち上げられるので二項演算も持ち上げられる。値の二項演算子μに単位元eが存在するとき、<e>は列の二項演算に持ち上げたμの単位元になる。

• <e> μ xs = xs

• xs μ <e> = xs

例えば、次のように計算できる。

<0> + <5, 2, 8>
= <0 + 5>, <0 + 2>, <0 + 8>
= <5>, <2>, <8>
= <5, 2, 8>

<5, 2, 8> + <0>
= <5 + 0>, <2 + 0> + <8 + 0>
= <5>, <2>, <8>
= <5, 2, 8>

$ jq -n '(0) + (5, 2, 8)'
5
2
8
$ jq -n '(5, 2, 8) + (0)'
5
2
8

単位元の列値写像への持ち上げ

２引数の写像を持ち上げられるので二項演算も持ち上げられる。列の二項演算子μに単位元eが存在するとき、どのような値にも単位元を返すconst(e)は、列値写像の二項演算に持ち上げたμの単位元になる。

• const(e)(x) = e

• const(e) μ f = f

• f μ const(e) = f

例えば、列値写像f(x) = <x, x>について、次のように計算できる。

(const(<0>) + f)(5)
= const(<0>)(5) + f(5)
= <0> + <5, 5>
= <0 + 5, 0 + 5>
= <5, 5>

(f + const(<0>))(5)
= f(5) + const(<0>)(5)
= <5, 5> + <0>
= <5 + 0, 5 + 0>
= <5, 5>

f(5)
= <5, 5>

$ jq -n 'def f: ., .; 5 | 0 + f'
5
5
$ jq -n 'def f: ., .; 5 | f + 0'
5
5
$ jq -n 'def f: ., .; 5 | f'
5
5

結合律の列への持ち上げ

２引数の写像を持ち上げられるので二項演算も持ち上げられる。値の二項演算子μが結合律を満たす場合、列の二項演算に持ち上げたμも結合律を満たす。

• (xs μ ys) μ zs = xs μ (ys μ zs)

例えば、次のように計算できる。

(<0, 1> + <2, 3>) + <4, 5>
= <2, 3, 3, 4> + <4, 5>
= <6, 7, 7, 8, 7, 8, 8, 9>

<0, 1> + (<2, 3> + <4, 5>)
= <0, 1> + <6, 7, 7, 8>
= <6, 7, 7, 8, 7, 8, 8, 9>

$ jq -n '(0, 1) + ((2, 3) + (4, 5))'
6
7
7
8
7
8
8
9
$ jq -n '((0, 1) + (2, 3)) + (4, 5)'
6
7
7
8
7
8
8
9

結合律の列値写像への持ち上げ

２引数の写像を持ち上げられるので二項演算も持ち上げられる。列の二項演算子μが結合律を満たす場合、列値写像の二項演算に持ち上げたμも結合律を満たす。

• (f μ g) μ h = f μ (g μ h)

例えば、列値写像f(x) = <x, x>, g(x) = <x + 1>, h(x) = <2x>について、次のように計算できる。

((f + g) + h)(5)
= (f + g)(5) + h(5)
= (f(5) + g(5)) + h(5)
= (<5, 5> + <6>) + <10>
= <11, 11> + <10>
= <21, 21>

(f + (g + h))(5)
= f(5) + (g + h)(5)
= f(5) + (g(5) + h(5))
= <5, 5> + (<6> + <10>)
= <5, 5> + <16>
= <21, 21>

$ jq -n 'def f: ., .; def g: . + 1; def h: . * 2; 5 | ((f + g) + h)'
21
21
$ jq -n 'def f: ., .; def g: . + 1; def h: . * 2; 5 | (f + (g + h))'
21
21

列値写像の連接（カンマ、,）

列の連接を列値写像に持ち上げたものを列値写像の連接と呼び、カンマで書く。

• (f, g)(x) = f(x), g(x)

例えば、列値写像f(x) = <x, x>, g(x) = <x + 1>について、次のように計算できる。

(f, g)(5)
= f(5), g(5)
= <5, 5>, <6>
= <5, 5, 6>

$ jq -n 'def f: ., .; def g: . + 1; 5 | (f, g)'
5
5
6

カンマ , : (A → <B>) × (A → <B>) → (A → <B>)は高階列値写像である。

カンマの単位元

empty = const(<>)なので、emptyは持ち上げられたカンマの単位元である。

• f, empty = f

• empty, f = f

例えば、列値写像f(x) = <x, x>について、次のように計算できる。

(f, empty)(5)
= f(5), empty(5)
= <5, 5>, <>
= <5, 5>

(empty, f)(5)
= empty(5), f(5)
= <>, <5, 5>
= <5, 5>

f(5)
= <5, 5>

$ jq -n 'def f: ., .; 5 | (f , empty)'
5
5
$ jq -n 'def f: ., .; 5 | (empty , f)'
5
5
$ jq -n 'def f: ., .; 5 | f'
5
5

カンマの結合律

列の連接は結合律を満たすので、持ち上げられたカンマは結合律を満たす。

• (f, g), h = f, (g, h)

例えば、列値写像f(x) = <x, x>, g(x) = <x + 1>, h(x) = <2x>について、次のように計算できる。

((f, g), h)(5)
= (f, g)(5), h(5)
= (f(5), g(5)), h(5)
= (<5, 5>, <6>), <10>
= <5, 5, 6, 10>

(f, (g, h))(5)
= f(5), (g, h)(5)
= f(5), (g(5), h(5))
= <5, 5>, (<6>, <10>)
= <5, 5, 6, 10>

$ jq -n 'def f: ., .; def g: . + 1; def h: . * 2; 5 | ((f, g), h)'
5
5
6
10
$ jq -n 'def f: ., .; def g: . + 1; def h: . * 2; 5 | (f, (g, h))'
5
5
6
10

列値写像の条件分岐

通常の条件分岐をif-then-else-endで書くと次のようになる。

• if true then x else y end = x

• if false then x else y end = y

この定義を使って、列値写像の条件分岐を定義する。

• (if p then f else g end)(x) = (c ↦ if c then f(x) else g(x) end)*(p(x))

例えば、列値写像p(x) = <x % 2 == 0, x % 4 == 0>, f(x) = <1, -x>, g(x) = <0, -x>について、次のように計算できる。

(if p then f else g end)(2)
= (c ↦ if c then f(2) else g(2) end)*(p(2))
= (c ↦ if c then f(2) else g(2) end)*(<true, false>)
= (c ↦ if c then f(2) else g(2) end)(true), (c ↦ if c then f(2) else g(2) end)(false)
= f(2), g(2)
= <1, -2>, <0, -2>
= <1, -2, 0, -2>

$ jq -n 'def p: (. % 2 == 0), (. % 4 == 0); def f: 1, -.; def g: 0, -.; 2 | if p then f else g end'
1
-2
0
-2

変数、束縛

jqの変数がどう解釈されるのか、よくわからない。構文の変換が必要になる気がする。

• (f as $f | g)(x) = (($f' ↦ ($f ↦ g(x)))(<$f'>))*(f(x))

例えば、列値写像f(x) = <x, -x>について、次のように計算できる。

(f as $f | (x ↦ $f + <x + 1, x + 2>))(5)
= (($f' ↦ ($f ↦ (x ↦ $f + <x + 1, x + 2>)(5)))(<$f'>))*(f(5))
= (($f' ↦ ($f ↦ ($f + <6, 7>)))(<$f'>))*(f(5))
= ($f' ↦ (<$f'> + <6, 7>))*(f(5))
= ($f' ↦ (<$f'> + <6, 7>))*(<5, -5>)
= ($f' ↦ (<$f'> + <6, 7>))(5), ($f' ↦ (<$f'> + <6, 7>))(-5)
= (<5> + <6, 7>), (<-5> + <6, 7>)
= <11, 12>, <1, 2>
= <11, 12, 1, 2>

$ jq -n 'def f: ., -.; 5 | f as $f | $f + (. + 1, .+ 2)'
11
12
1
2

おわり

力尽きたのでここまで。おそらくリストモナドに詳しい人だと地道に計算しなくても、既存の知識でjqを理解できるんじゃないでしょうか。私はリストモナドもモナドもわからないので、詳しい人がjqをどう解釈するのか気になります。

手計算をする前、jqのサンプルをパッと読んで、「パイプと持ち上げた二項演算子で分配律が成り立つのではないか」と変な勘違いをしてしまいました。手計算してみたら全然成り立たないという。

ここまで書いておいてなんですが、今までJSONを処理する場合は別のスクリプト言語を使っていたので、これからもjqを使う機会はあまりなさそうです。まあ、手計算していくうちに、jqの脳内シミュレーターの精度が上がっている感じがして楽しかったのでヨシ！