2022-06-20

有限体上の線形代数を探訪する～線形空間から次元定理まで編～

前回の記事から随分と間が空いてしまったが*1、本稿では有限体上の線形空間について考えてみたいと思う。単に線形空間とだけ言うと対象が広大になり過ぎるため、本稿では次元定理が成り立つことを確かめるところまでをスコープにする。そのために、まずは線形空間、線形写像および線形空間の基底が有限体上でも定義し得るかを考えた後、有限体上の線形空間でも次元定理が成り立つことを確認する。

なお、本稿はこちらのブログ記事に触発されて考え始めたものである。本当はこのブログで紹介されている参考文献「Lovász, "Combinatorial Problems and Exercises"」も参照したかったが、あまりにも高価な本なのでこちらは読めていない。

線形空間

複素数体上の線形空間の定義を本[1]より引用する*2。

線形空間

集合 $V$ がつぎの二条件(Ⅰ), (Ⅱ)を充すとき, $V$ を複素線型空間あるいは複素ベクトル空間と言う.
(Ⅰ) ・・・省略・・・
(Ⅱ) $V$ の任意の元と任意の複素数 $a$ に対し, ${\bf x}$ の $a$ 倍と呼ばれるもう一つの $V$ の元 (これを $a{\bf x}$ で表わす) が定まり, つぎの法則が成立つ：
  (5) $(a + b) {\bf x} = a {\bf x} + b{\bf x}$ ,
  (6) $a({\bf x} + {\bf y}) = a {\bf x} + a {\bf y}$ ,
  (7) $(ab) {\bf x} = a(b{\bf x})$ ,
  (8) $1 {\bf x} = {\bf x}$ .

このうち、体に関わるのは条件(Ⅱ)の方だけなので、(Ⅰ)は割愛した。問題は、ここで複素数となっているところを単に有限体の元と読み替えれば、そのまま有限体上の線形空間の定義として妥当なものになるか？である。

1つずつ見ていこう。(5)は和さえ定義されていれば妥当な条件となる。(6)は体の性質はどうでも良い。(7)は積が定まっていれば良い。条件(8)は積の単位元が存在すれば良い。これらは全て体であれば問題なく満たされるため、有限体に対しても複素数と同様に線形空間を定義することができる。

線形写像

$K$ を $\mathbb{C}$ か $\mathbb{R}$ の一方を表すものとする。その上で線形写像の定義を本[1]より引用する。

線形写像

$K$ 上の線型空間 $V$ から $K$ 上の線型空間 $V'$ への写像 $T$ が二条件
$\displaystyle{ \begin{eqnarray} &&T({\bf x} + {\bf y}) = T({\bf x}) + T({\bf y}) \\ &&T(a{\bf x}) = a T({\bf x}) \end{eqnarray} }$
を充すとき, $T$ を $V$ から $V'$ への線型写像と言う。

これを見ると、 $a$ は単にベクトルの係数として登場するだけであり、有限体の元であったとしても定義の妥当性を貶めることはない。よって有限体上のベクトル空間にも同様に線形写像を定義できる。

基底

以下では有限次元ベクトル空間についてのみ考える。線形空間の基底の定義を本[1]から引用する。

基底

線型空間 $V$ の有限個のベクトル ${\bf e}_1, {\bf e}_2, \cdots , {\bf e}_n$ がつぎの二条件を充すとき, ${\bf e}_1, {\bf e}_2, \cdots , {\bf e}_n$ は $V$ の基底であると言う：
1) ${\bf e}_1, {\bf e}_2, \cdots , {\bf e}_n$ は線型独立である；
2) $V$ の任意のベクトルは ${\bf e}_1, {\bf e}_2, \cdots , {\bf e}_n$ の線型結合として表わされる.

これらの定義において体に関係するのは線形結合として表すときの係数くらいしかなく、有限体上のベクトル空間に対しても同様に定義可能である。

次元定理

これは本[1]には次元定理という名前では書かれていないが、Wikipedia[2]にはこの名前も記載されている。要するに、線形写像 $T$ を $V$ から $V'$ への線形写像、 $o'$ を $V'$ の零ベクトルとしたとき、以下が成立することを次元定理と言う。

$\displaystyle{ \mathrm{dim}\ V = \mathrm{dim}\ T^{-1}({\bf o'}) + \mathrm{dim}\ T(V) }$

これの証明の概略を本[1]に沿って説明する。まず、 $\mathrm{dim}\ T^{-1}({\bf o'})$ は $V$ の部分空間となる（これの証明は割愛する）。そのため、 $\mathrm{dim}\ T^{-1}({\bf o'})$ を張る基底 $<{\bf e}_1, {\bf e}_2, \cdots , {\bf e}_s >$ が存在する。これを拡張して $V$ の基底 $<{\bf e}_1, {\bf e}_2, \cdots , {\bf e}_n >$ を得たとき、 $< T({\bf e}_s), T({\bf e}_{s+1}), \cdots , T({\bf e}_n) >$ が $T(V)$ の基底であることを言えばよい。

$T: V \to T(V)$ は全射なので、任意の ${\bf x}' \in T(V)$ に対して ${\bf x}' = T({\bf x})$ となる $V$ の元 ${\bf x} = \sum_{i=1}^{n} x_i {\bf e}_i$ が存在する。よって ${\bf x}' = T({\bf x})= \sum_{i=s+1}^{n} x_i T({\bf e}_i)$ である。

あとは線形関係 $\sum_{i=s+1}^{n} c_i T({\bf e}_i) = {\bf o}'$ があったときに、 $c_{s+1} = c_{s+2} = \cdots = c_n = 0$ であることを言えばよい。引用が多くなり過ぎるとよろしくないのでこれくらいでやめておくが、これは $\sum_{i=s+1}^{n} c_i T({\bf e}_i) = T\left(\sum_{i=s+1}^{n} c_i {\bf e}_i \right)$ から $\sum_{i=s+1}^{n} c_i {\bf e}_i \in T^{-1}({\bf o'})$ であることなどから言える。

この証明の中で、体は係数として使われているだけであり、内積のように有限体の場合に困るような操作は行っていない。そのため有限体でも次元定理は成立すると言える。

まとめ

本稿では有限体上でも線形空間や線形写像が実数や複素数の場合と同様に定義されることを確かめた。また、有限体上の線形写像に対しても次元定理が成立することを確かめた。

もともとは次回を最終回として固有値・固有ベクトルや対角化について考える予定だったが、本稿を書いているうちに他に気になるところが出てきた。次回はそちらの疑問を解消しようと思う。

参考

[1]

線型代数入門 (基礎数学)

作者:齋藤正彦
東京大学出版会

Amazon

[2] https://ja.m.wikipedia.org/wiki/%E9%9A%8E%E6%95%B0%E3%83%BB%E9%80%80%E5%8C%96%E6%AC%A1%E6%95%B0%E3%81%AE%E5%AE%9A%E7%90%86#:~:text=%E6%95%B0%E5%AD%A6%E3%81%AE%E7%B7%9A%E5%9E%8B%E4%BB%A3%E6%95%B0%E5%AD%A6,%E6%AC%A1%E5%85%83%E5%AE%9A%E7%90%86%E3%81%A8%E3%82%82%E5%91%BC%E3%81%B0%E3%82%8C%E3%82%8B%E3%80%82

*1:実は今年の1月に転職しており、慣れるまでは仕事関係の勉強を優先したため、数学が手につかなかった。最近やっと心が落ち着いてきたので、ぼちぼち数学にも時間を割いていこうと思う。

*2:本[1]では「線型空間」と書いているが、本ブログのシリーズのタイトルに「線形代数」と入れているので、本稿では引用箇所を除き「線形」で統一する。

2022-03-21

有限体上の線形代数を探訪する～行列編～

線形代数有限体

前回と前々回の記事では有限体の元を成分に持つ数ベクトルについて調べた。本稿ではその続きとして、有限体の元を成分に持つ行列について考えてみたいと思う。

確かめたいこと

あまり網羅的なアプローチではないが、さしあたり有限体の元を成分に持つ行列について私が気になっていることについて明らかにしていきたいと思う。以下にその一覧を示す。

基本変形はできるのか？
rankの概念は定義できるのか？
行列の列ベクトルが全て一次独立であれば行列式は0にならないか？

本稿ではこれらについて考えてみる。なお、議論を発散させないために、線形空間や線形写像に関する話題は本稿のスコープ外とし、可能な限り持ち出さないようにする（ただし、どうしても1箇所だけ避けられなかった）。

基本変形

基本変形とは、対象となる行列に対して基本行列と呼ばれる3種類の行列を左右どちらかの方向から掛けることで行われる変換であった。

その意味で、「基本変形はできるのか？」と言われれば、体（というか環）であればできるということになるだろう。しかし、基本変形を行う通常のモチベーションは、行列を以下のような標準形に変形することにある。

$\displaystyle{ \begin{pmatrix} E_{r, r} & O_{r, n-r} \\ O_{m-r, r} & O_{m-r, n-r} \end{pmatrix} }$

ただし、 $m, n, r \in \mathbb{N}, r \le m, r \le n$ で、 $E_{r, r}$ は $r$ 次単位行列、 $O_{a, b}$ は $a$ 行 $b$ 列の零行列を表す。

これはいつでも可能なのだろうか？以下で考えてみよう。

標準形への変形

$\mathbb{R}$ や $\mathbb{C}$ 上の $m$ 行 $n$ 列の行列の場合、標準形への変換は以下のように行われるのであった。

$i = 1$ とする。
もし $(i, i)$ 成分が0なら、行や列の入れ替えを行い0でない値になるようにする。もし $i$ 行目以降、及び $i$ 列目以降の全ての値が0なら処理を終える。
$(i, i)$ 成分の乗法の逆元を $i$ 行目の全ての数に掛ける。これで $(i, i)$ 成分は1になる。
全ての $j (j = i+1, \cdots , n)$ に対して、 $i$ 列目に $(i, j)$ 成分の値を掛けたものを $j$ 列目から引く。これで $(i, j)$ 成分が0になる。
全ての $j (j = i+1, \cdots , m)$ に対して、 $i$ 行目に $(j, i)$ 成分の値を掛けたものを $j$ 行目から引く。これで $(j, i)$ 成分が0になる。
もし $i = \min(m, n)$ なら処理を終える。さもなければ $i$ に1を足して手順2以降を再度実施する。

これを見ると、やっているのは四則演算に過ぎず、また正標数ゆえに不意に和が0になって困るようなステップもないため、成分が有限体であっても標準形に変形できると言える。

もし環だったら

一般の環の元を成分に持つ行列の場合、必ずしも標準形に変形できるとは限らない。これは乗法の逆元が存在しないために対角成分を1にできないケースがあるからである。

例えば、 $\mathbb{Z}/4\mathbb{Z}$ の元を成分に持つ以下のような行列があったとする。

$\displaystyle{ \begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix} }$

ここで、2は単元ではないため何を掛けても1にできない。従ってこの行列は標準形には変形できない。

rank

ここまで標準形の存在について述べてきたが、一意性については触れてこなかった。 $\mathbb{R}$ や $\mathbb{C}$ 上の行列の場合、標準形は変形のしかたによらず一意に定まり、そのとき対角成分に並ぶ1の数をその行列のrankと呼ぶのであった。そのため、有限体であっても標準形の一意性が保証されるかどうかは重要な問題である。以下で考えてみよう。

ところで、rankは他にも同値な定義がある。それらについては線形空間に触れる必要があって本稿のスコープ外だったり、私の興味の外だったりするため、本稿では触れないことにする。

rank の一意性

標準形の対角線上に並ぶ1の数という意味でのrankの一意性については、本[1]の定理4.2に証明がある。それをここで写経することは割愛するが、証明には四則演算の他に以下の定理を用いている。

$n$ 次正方行列 $A$ に対し, $XA = E$ となる $n$ 次行列 $X$ が存在すれば $A$ は正則である. $AX = E$ となる $X$ の存在を仮定しても同様である.

有限体の場合、四則演算は問題なく行えるが、逆行列は同じように定義されるのだろうか？

これについては逆行列の構成方法を考えれば分かる。 $A$ の余因子行列を $\tilde{A}$ とすると、逆行列 $A^{-1}$ は以下のように表される。

$\displaystyle{ A^{-1}= \frac{1}{\det{A}} \tilde{A} }$

行列式も余因子行列も、究極的には四則演算さえできれば求められるため、これらは有限体上でも同様に計算できる。また、 $\det{A} \ne 0$ の場合のみ意味を持つという点も同様である。

以上により、有限体の元を成分に持つ行列であっても逆行列という概念は $\mathbb{R}$ や $\mathbb{C}$ の場合と同様に定義できそうだ。すなわち、rankの一意性は保証されると言えるだろう。

一次独立な列ベクトルの個数と行列式

ここでは正方行列についてのみ考える。

まずは私が疑問を持った具体例について説明する。 $\mathbb{F}_5$ の元を成分に持つ以下の行列について考える。

$\displaystyle{ \begin{pmatrix} 1 & 2 \\ 3 & 1 \end{pmatrix} }$

これの行列式は普通に計算すると-5になるが、今は $\mathbb{F}_5$ で考えているので0になる。一見すると正則に見えるような行列であっても行列式が0になってしまうというのは、どう解釈すればよいのだろうか？

実は、このカラクリは前々回の記事と関係している。すなわち、有限体の元を成分に持つベクトルは、一見すると互いに平行かどうかが分かりにくいのである。そして、今は2つの列ベクトルの間に $\begin{pmatrix} 2 \\ 1 \end{pmatrix} = 2 \begin{pmatrix} 1 \\ 3 \end{pmatrix}$ という関係があり、これらのベクトルは互いに平行だったのである。

結局、私の心配は杞憂であったと言えそうだ。

証明

行列の列ベクトルが全て一次独立であれば行列式は0にならないことの証明は以下のようになる[2]。

$n$ 次正方行列 $A$ の列ベクトルの間の線形関係が自明なものに限られることから、 $\mathrm{Ker}A = \{{\bf 0}\}$ となる。つまり $A$ が表す線形写像は単射である。ここで次元定理により $\mathrm{dim}\mathrm{Im}A = n$ となるので、結局これは全単射である。よって $A$ が表す線形写像には逆写像が存在し、その表現行列は $A$ の逆行列となる。

次元定理は成立するのか？

不本意ながら最後の最後で線形写像の道具を使ってしまったわけだが、次元定理は有限体上の線形空間に対しても成立するのだろうか？というか、そもそも有限体上の線形空間に対する線形写像ってなんかヤバそうだが、どういう感じなんだろうか？

次元定理については成り立つと書いているブログ[3]が存在するが、証明はないため現時点では良く分からない。

まとめ

本稿では有限体の元を成分に持つ行列の性質について調べた。結論として、平行なベクトルの見かけに騙されなければ、特に通常の行列と変わりはなさそうだということが分かった。

次回は線形写像、特に次元定理について考えてみたいと思う。その後は余力があれば対角化や固有値・固有空間についても考えてみたいが、まだ先は長そうだ。

参考

[1]

線型代数入門 (基礎数学)

作者:齋藤正彦
東京大学出版会

Amazon

[2] Period on Twitter: "前半の条件はつまりAを左からかける写像が単射であることに他ならないので次元定理から全射でもあるので言えます… "
[3] 有限体上の線形代数 - むしゃくしゃしてやった，今は反省している日記

2022-03-17

有限体上の線形代数を探訪する～数ベクトル編その2 ～

線形代数有限体

前回の記事で有限体の元を成分に持つ数ベクトルについて考えた。本当は次は行列についての記事を書こうと思ったのだが、そちらを書いている最中に数ベクトルの一次独立性について疑問点が生じてきたので、本稿ではそれについて考えてみる。

正標数はつらいよ

$\mathbb{R}$ や $\mathbb{C}$ 上の数ベクトルの場合、一次独立とはベクトル間に自明でない線形関係が存在しないことを言うのであった[1]。

$\mathbb{R}$ や $\mathbb{C}$ は標数0なので良いのだが、正標数の場合には1つ心配なことがある。それは、0でない2数を足すと0になるケースがあるということである。「それを言うなら $\mathbb{R}$ だって $1+(-1) = 0$ ではないか」と言われればそれまでなのだが、一見すると正の数のように見える2数（もちろん有限体に正も負もないわけだが感覚的な話として）を足して0になるという点について、一次独立性を考える際に何か落とし穴がないのか？というのがふわっとした疑問であった。

この疑問をさらに深く考えてみたときに、疑問の正体は平行性の定義との整合性であることに気づいた。つまり、平行でない2つのベクトルの線形結合を成分ごとに計算した結果、正標数であるが故にたまたま全て0になってしまうようなことがないか？ということである。もしこういうことが起こると、まともな議論ができないだろうと思ったわけである。

これについて、結論としては直観に反する結果にはならないことが分かった。以下でそれを示してみる。

平行でない2ベクトルの間に非自明な線形関係が存在しないことの証明

この章のタイトルだけ見ると「何を当たり前のことを言っているんだ」と思われるかもしれないが、ここではあくまで有限体の元を成分に持つ数ベクトルについて考えていることを再度強調しておく。

$n$ を自然数、 $q$ を素数冪とする。互いに平行でない $n$ 次元ベクトル ${\bf x}, {\bf y} \in \mathbb{F}_q^n ({\bf x} \ne {\bf 0}, {\bf y} \ne {\bf 0})$ について、これらの間に以下のように非自明な線形関係が存在すると仮定する。

$\displaystyle{ a {\bf x} + b {\bf y} = {\bf 0} }$

両辺に $b(q-1) {\bf y}$ を足して整理すると以下のようになる。

$\displaystyle{ \begin{eqnarray} a {\bf x} + b q {\bf y} = b(q-1) {\bf y} \\ {\bf x} = \frac{b(q-1)}{a} {\bf y} \end{eqnarray} }$

よって ${\bf x}, {\bf y}$ は互いに平行となるが、これは矛盾である。よって仮定は誤りで、 ${\bf x}, {\bf y}$ の間に非自明な線形関係は存在しない。

考えてみればなんとも呆気ない結果であった。

まとめ

有限体上の線形代数を考えていると、いろんな定義がwell-defineのようなそうでないような、また様々な定理が当たり前のような当たり前じゃないようなそんな感覚に襲われ続ける。こういうときは愚直に1つずつ考えて、少しずつ親しみが持てるようになっていきたいところである。

次回こそは有限体の元を成分に持つ行列について考えてみようと思う。

参考

[1]

線型代数入門 (基礎数学)

作者:齋藤正彦
東京大学出版会

Amazon

2022-01-21

有限体上の線形代数を探訪する～数ベクトル編～

線形代数有限体

有限体上での線形代数はどうなるのか？

以前の記事で有限射影幾何というものを少し扱った。その中で、そもそもそんな難しいことをやる以前の問題として、有限体上の線形代数が分かっていないことが致命的に厳しいと感じた。

例えば、 $\mathbb{R}$ や $\mathbb{C}$ 上での線形代数でよく使われる概念が同じように定義できるのかとか、有名な定理が同様に成り立つのかと言われると、答えられない自分がいた。

とはいえ、流石に私がそれらを独力で調べ切るのは今の生活 (転職したばかりで、かつ膨大な時間を子育てに使っている状態) では厳しい。

そんなわけで、全体としてどこまでやれるかは分からないが、差し当たり本稿では有限体上の線形代数の初歩として、有限体の元を成分に持つ数ベクトルについて考えたいと思う。

有限体の元を成分に持つ数ベクトル

位数 $q$ ( $q$ は素数冪) の有限体を $\mathbb{F}_q$ とする。 $n$ を自然数として、以下では $\mathbb{F}_q^n$ について考える。

ベクトルの平行性

零ベクトルでない2つのベクトル ${\bf a}, {\bf b} \in \mathbb{F}_q^n$ に対して、それらが平行であるということはうまく定義されるのだろうか？ユークリッド空間上のベクトルの類推で考えると、ある定数 $c \in \mathbb{F}_q$ が存在して、 ${\bf a} = c{\bf b}$ となることを平行性の定義とするのが良いだろう。

しかし、 $\mathbb{F}_q^n$ の元は $q^n$ 個と有限である。そのため、互いに平行なベクトルの集合は幾何学的にはどんな様子になるのか？というところが気になるところである。以下ではそれを具体例を見ながら考えてみよう。

$q = 5, n = 2$ の例

例として $\begin{pmatrix} 1 \\ 2 \\ \end{pmatrix} \in \mathbb{F}_5^2$ について考えてみよう。これに2, 3, 4を掛けたベクトルはそれぞれ以下のようになる。

$\displaystyle{ \begin{pmatrix} 2 \\ 4 \\ \end{pmatrix}, \begin{pmatrix} 3 \\ 1 \\ \end{pmatrix}, \begin{pmatrix} 4 \\ 3 \\ \end{pmatrix} }$

つまり、これらのベクトルは平行であると言える。

同様に考えて、各ベクトルを位置ベクトルと見なし、平行なベクトル同士を座標上に同じ色でプロットしたものを以下に示す。

www.desmos.com

これを見ると、何となく対称性のあるパターンにはなっているものの、ユークリッド幾何学的な意味での平行とはかけ離れていることが分かる。とは言え、これ以外によい定義方法もないし、 $\mathbb{F}_q^n$ における平行性とはこういう抽象概念なのだと考えるのが良いだろう。

平行性による同値類とその個数

互いに平行関係にあるというのは、実は同値関係になる。これはほぼ自明なので詳細な説明は割愛する。

$\mathbb{F}_q^n$ から零ベクトルを除いた $q^n - 1$ 個の元を同値類にまとめたとき、1つの同値類には $q- 1$ 個の元が含まれる。というのも、零ベクトルでない適当なベクトルに $\mathbb{F}_q^{\times}$ の元を掛けたものはそれぞれ相異なるベクトルになるためである。これは $\mathbb{F}_q^{\times}$ が巡回群であることなどから言える。

そのため、同値類の個数は以下のようになる。

$\displaystyle{ \frac{q^n - 1}{q - 1} }$

以前の記事でも書いたが、実はこの同値類の集合は有限体上の $n-1$ 次元射影空間になっている。当時は射影空間の元の数 (つまり同値類の数) はGaussian binomial coefficientによって求められると書いたが、そんな小難しい道具でオーバーキルせずとも、上記のような簡単な式で表現できることが分かった。

ベクトルの内積

$\mathbb{F}_q^n$ において、ベクトルの内積を通常と同じ方法で定義することはできない。それを示すために、まずは内積が満たすべき性質について振り返ってみよう[1]。

内積の公理

$V$ の二元 ${\bf x}, {\bf y}$ に対し, 内積と称する $K$ の元 (これを $({\bf x}, {\bf y})$ で表す) が定まり, つぎの性質を持つ：
(1) $({\bf x}, {\bf y_1} + {\bf y_2}) = ({\bf x}, {\bf y_1}) + ({\bf x}, {\bf y_2})$
・・・中略・・・
(4) $({\bf x}, {\bf x})$ は0または正の実数であり, $({\bf x}, {\bf x}) = 0$ となるのは ${\bf x} = {\bf 0}$ のときに限る.

ただし、 $K$ は引用元の本では $\mathbb{C}$ または $\mathbb{R}$ のいずれかと定められている。

このうち最後の(4)が重要である。例えば $\begin{pmatrix} 1 \\ 1 \\ \end{pmatrix} \in \mathbb{F}_2^2$ 同士の内積をユークリッド空間の場合と同じように計算してみると0になってしまう。これは(4)に反する。

「標数が2だから特殊なんでしょ？」と思うかもしれないが、 $\begin{pmatrix} 1 \\ 1 \\ 1 \\ \end{pmatrix} \in \mathbb{F}_3^3$ 同士の内積も0となり、標数2に限った話ではないことが分かる。

つまり、内積が関係するようなベクトルの性質やベクトル空間に関する概念 (計量ベクトル空間、直交補空間、固有空間等) の扱いは注意を要するか、そもそも定義できない可能性があると考えるべきだろう。これらについては本稿のスコープを外れるので、ここでは深追いしない。

まとめ

本稿では有限体の元を成分に持つ数ベクトルの性質について調べた。結論として、内積がうまく定義できないという大きな制約があることが分かった。

次回は有限体の元を成分に持つ行列について考えてみたいと思う。さらにその次も多少ネタはあるのだが、このシリーズをどこまで頑張るかはその時のコンディションで考えたい。

参考

[1]

線型代数入門 (基礎数学)

作者:齋藤正彦
東京大学出版会

Amazon

2021-05-10

popen関数の挙動まとめ

C言語のpopen関数の挙動にいつも混乱させられるので、自分用メモとして挙動をまとめてみる。

popen関数の挙動

popen関数はファイルを開くようなノリでプロセスをopenできる。popenの戻り値としてファイルディスクリプタが返ってくるので、それを使ってopenしたプロセスにread/writeの指示を行うことができる。

混乱の種はこのプロセスに対するread/writeである。これはpopenをコールした側の視点に立って考える必要がある。つまり、readであればopenしたプロセスの標準出力を読み取るし、writeであればopenしたプロセスに標準入力を与えることになる。考えてみれば当然なのだが、popenをコールする側・される側でin/outの関係が逆になっており、それが混乱を招く。

以下に挙動をまとめた表を示す。

popenのフラグ	popenコール側の挙動	popenでopenされる側の挙動
"r"	fgets関数などを使用してopenしたプロセスの標準出力をreadする。	標準出力にデータを吐き出す（かもしれない）。
"w"	fputs関数などを使用してopenしたプロセスに標準入力を与える（writeする）。	標準入力からデータを受け取る（かもしれない）。

サンプルプログラム

以下のサイトを参考にサンプルプログラムを書いてみた。

popenでコマンドの出力を読み込む - C言語入門

Readモードでopenする例

#include <stdio.h>
#include <stdlib.h>
#define BUF 256

int main (int argc, char *argv[])
{
    FILE *fp;
    char *cmdline = "ls";
    if ((fp=popen(cmdline, "r")) == NULL) {
        perror ("popen failed");
        exit(EXIT_FAILURE);
    }

    char buf[BUF];
    while(fgets(buf, sizeof(buf), fp) != NULL) {
        printf("=> %s", buf);
    }

    pclose(fp);

    return 0;
}

実行結果は以下の通りである。

shinya@DESKTOP-Q1NSEEU:~/programs/popen% ./a.out
=> a.out
=> correct_read.c
=> correct_write.c
=> wrong_read.c
=> wrong_write.c

Writeモードでopenする例

#include <stdio.h>
#include <stdlib.h>
#define BUF 256

int main (int argc, char *argv[])
{
    FILE *fp;
    char *cmdline = "python3";
    if ((fp=popen(cmdline, "w")) == NULL) {
        perror ("popen failed");
        exit(EXIT_FAILURE);
    }

    char buf[BUF];
    char* data1 = "print(\"Hello\")\n";
    char* data2 = "quit()\n";
    fputs(data1, fp);
    fputs(data2, fp);

    pclose(fp);

    return 0;
}

実行結果は以下の通りである。

shinya@DESKTOP-Q1NSEEU:~/programs/popen% ./a.out
Hello

バグについて

マニュアルを見ると、popenには何やらバグがあるらしい。端的に言うと、readモードでopenしたプロセスの標準入力、及びwriteモードでopenしたプロセスの標準出力の扱いがザルということである。

Man page of POPEN

以下にこのバグを踏むプログラムの例を示す。

Readモードでopenしたプロセスと標準入力を共有してしまう例

#include <stdio.h>
#include <stdlib.h>
#define BUF 256

int main (int argc, char *argv[])
{
    FILE *fp;
    char *cmdline = "python3";
    if ((fp=popen(cmdline, "r")) == NULL) {
        perror ("popen failed");
        exit(EXIT_FAILURE);
    }

    int data0 = 0;
    scanf("%d", &data0);
    printf("input data = %d\n", data0);

    pclose(fp);

    return 0;
}

実行結果は以下の通りである。

shinya@DESKTOP-Q1NSEEU:~/programs/popen% ./a.out
Python 3.8.5 (default, Jan 27 2021, 15:41:15)
[GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 10
input data = 10  ★標準入力がpopenした側のプロセスに吸われた

>>>

Writeモードでopenしたプロセスと標準出力を共有してしまう例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUF 256

int main (int argc, char *argv[])
{
    FILE *fp;
    char *cmdline = "ls";
    printf("Hello ");

    if(argc == 2 && strncmp(argv[1], "-f", 3) == 0) {
        fflush(stdout);
    }
    if ((fp=popen(cmdline, "w")) == NULL) {
        perror ("popen failed");
        exit(EXIT_FAILURE);
    }

    char buf[BUF];

    pclose(fp);
    printf("world!\n");

    return 0;
}

実行結果は以下の通りである。

shinya@DESKTOP-Q1NSEEU:~/programs/popen% ./a.out
a.out  correct_read.c  correct_write.c  wrong_read.c  wrong_write.c
Hello world!  ★"Hello "を先に出力したはずなのにlsコマンドの出力が先に出てしまった

なお、後者についてはpopenの前にfflush関数をコールすることで回避できるようである。上で示したプログラムに"-f"オプションを付けて実行するとこの挙動になる。

shinya@DESKTOP-Q1NSEEU:~/programs/popen% ./a.out -f
Hello a.out  correct_read.c  correct_write.c    wrong_read.c  wrong_write.c
world!  ★"Hello "が先に出力された

まとめ

以上、popen関数の挙動についてまとめた。これでもう混乱することはないだろう。

2021-05-10

Clang LibToolingを用いたクラス内依存関係抽出ツールの開発

clang

久々に数学とは関係ない記事を書いてみる。

最近、「レガシーコード改善ガイド」という本を読んでいる。概要としては、「レガシーコードとはユニットテストが存在しないコードのことである」という独自の哲学の元、レガシーコードをいかにして改善するかということについて記載されている。

レガシーコード改善ガイド

作者:マイケル・C・フェザーズ
発売日: 2016/01/15
メディア: Kindle版

この本の中で「機能スケッチ」というものが登場する。これは、クラス内のメソッドが他のメンバー変数やメソッドをどのように利用しているかという依存関係を絵に描き起こすものである。これによって、巨大なクラスからいくつかのグループを見つけ出し、分割するためのヒントが得られる。

さて、本ではこれを手描きするように説明されているわけだが、絶望的に巨大なクラスに対してそんなことしてられないということもあるだろう。そこでツールによる自動化ができないかと考えた。こういうとき、まず思いつくのはPython等でテキスト処理をゴリゴリする方法だ。しかし、プログラミング言語の解析をそのように行うことは、もはや自前でパーサーを書くに等しい労力がかかるだろう。

そこで、clangのFrontendを利用できないかと考えた。ClangとはLLVMベースのC/C++/Objective-C コンパイラである。通常、コンパイラは大きく2つのレイヤーに分かれる。すなわち、ソースファイルから抽象的な構文木や中間言語を生成するためのFrontend、及びFrontendの出力を受けて機械語のコードを生成するBackendである。

実は、clangにはFrontend部分の出力を利用したコード解析系ツールの開発を支援してくれるLibToolingというライブラリが存在する。具体的には、clangが生成するASTと呼ばれる抽象構文木を辿ってノードの情報を引っ張り出すことができるようなライブラリが提供されている。

LibTooling — Clang 13 documentation

Introduction to the Clang AST — Clang 13 documentation

今回はこのclang LibToolingを用いて機能スケッチを自動生成するツールを作ってみたので、それについて説明する。

LibToolingのインストール

まずはインストール方法についてだが、公式ドキュメントを見ると「ソースからビルドしてインストールしてね」と書かれていて、いきなり心を折ってくる。頼むからパッケージからインストールさせてくれと思うわけだが、実は可能である。例えば私が使ったUbuntu20.04の場合であれば以下のパッケージをインストールすればよい。

clang
libclang-dev

LibToolingを用いた自作ツールのビルド

次にビルドである。手始めに以下のページに記載されているサンプルコードをビルドしてみようと思ったのだが、これがundefined referenceエラーで全然通らない。ここが一番苦しいポイントだった。

Tutorial for building tools using LibTooling and LibASTMatchers — Clang 13 documentation

結論だけ言うと、以下のサイトに従ったらうまくビルドできた。感謝しかない。

qiita.com

AST Matcherを用いたツール開発の流れ

LibToolingの重要な機能の1つにAST Matcherというものがある。これは、ASTから条件にマッチしたノードを検索するための仕組みである。AST Matcherを使った処理の流れは以下のようになる。

AST Matcherを用いてASTノードの検索条件を記述する。
検索にマッチした際に実行するコールバック関数を記述する。
MatchFinderと呼ばれるオブジェクトに検索条件とコールバック関数の組を登録する（複数登録可能）。

AST Matcherによる検索条件の記述

AST Matcherの条件の記述方針については以下のドキュメントに説明がある。

Matching the Clang AST — Clang 13 documentation

上記ページからリンクされているAST Matcher Referenceというページは頻繁に参照することになる。

AST Matcher Reference

ざっくりいうと、上記のreferenceを見て、自分のやりたいことに合致する条件式をガチャガチャと組み合わせていく流れである。慣れていないと、これはかなり厳しい作業になる。特に分かりづらい点として、ASTのノードはStmtやDeclなどのいくつかの型に分かれており、それらは共通の基底クラスやインターフェイスを持たない。そのため、今自分が操作したいノードが何の型なのかというのを意識しながら処理を記述する必要がある。

こういうものこそまさにCompositeパターンでシンプルに作れるのでは？と思ってしまうが、clangのASTはそうなっていないので仕方ない。

Matcherについては以下のサイトが非常に参考になるので、こちらを先に一読するとよい。

Exploring Clang Tooling Part 2: Examining the Clang AST with clang-query | C++ Team Blog

Clang queryについて

AST Matcherの条件式を作るのは苦痛を伴う作業であるが、幸いにしてこの苦痛を大幅に緩和するためのツールがある。それがclang-queryである。上でリンクを張ったMicrosoftのサイトでもclang-queryを使っている。

Clang-queryとは、LibToolingで実際に使える条件式を単独で実行し、結果を出力するためのツールである。Ubuntu20.04の場合はclang-toolsパッケージをインストールすることで使用できる。

条件式を考えたら、まずclang-queryにて試しに検索を行ってみるとよい。これにより、どういうコードが検索に引っかかるのかを実際に確かめることができ、条件式を期待通り記述するための助けになる。

ちょっとハマった点としては、C++11以降の機能を使いたい場合、clang-queryにその旨を示すオプションを付けてやる必要がある。例えばC++17以降の機能を使用しているlayer.cppを解析したい場合、以下のようにすればよい。

clang-query --extra-arg='-std=c++17' ~/programs/cnn/src/layer.cpp --

最後の"--"はなぜ必要かいまいち分からないが、これがないとエラーになる。

条件式の型について

条件式はプログラム上ではオブジェクトとして表現される。これの型をどうすべきなのか、本当に全然説明が見つからないので未だに分からない。私の場合はコンパイルエラーから類推してclang::ast_matchers::DeclarationMatcherとかclang::ast_matchers::StatementMatcherなどを使ってみて、これでコンパイルは通ったが、未だに正解がよく分からない。

以下にサンプルコードを示す。

MemberAccessMatcher.h

#ifndef MEMBER_ACCESS_MATCHER
#define MEMBER_ACCESS_MATCHER
#include "clang/ASTMatchers/ASTMatchers.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include <string>


class MemberAccessMatcher
{
public :
    MemberAccessMatcher(std::string targetName);
    clang::ast_matchers::StatementMatcher getMatcher();

private:
    clang::ast_matchers::StatementMatcher matcher;
};

#endif

MemberAccessMatcher.cpp

#include "../include/MemberAccessMatcher.h"
#include "clang/AST/ASTContext.h"

using namespace clang::ast_matchers;

MemberAccessMatcher::MemberAccessMatcher(std::string targetName) :
    matcher(memberExpr(hasAncestor(cxxMethodDecl(isExpansionInMainFile(), ofClass(hasName(targetName))).bind("fdecl"))).bind("mexpr"))
{
}

StatementMatcher MemberAccessMatcher::getMatcher()
{
    return matcher;
}

MemberAccessMatcherクラスのmatcherという変数が条件式を格納する変数である。この例ではイニシャライザにて条件式を設定している。

bindとノードの操作

AST Matcherでは検索に引っかかったノードを識別するためにbindという仕組みを使う。条件式にbind("文字列key")という形式で文字列keyを登録しておくことで、コールバック関数にて該当するノードの情報を引っ張り出すことができる。

そうやって引っ張り出してきたノードに対しては、そのノードの型に応じて様々な処理が可能である。それぞれの型についてどういった処理が行えるかは公式ドキュメントを見る必要がある。このドキュメントは殺意が湧くほど説明が足りないので、関数名から処理を推測し、trial and errorでコーディングしていく必要がある。

clang: clang Namespace Reference

ノードに対して行える操作の典型例を以下に示す。

変数名・関数名の取得
変数の型の取得
関数の戻り値の取得
関数の引数名や型の取得
メンバー変数・メンバー関数が所属するクラスの取得
クラスが継承している基底クラスの情報の取得

最後に書いた基底クラスの情報の取得については私が作ったツールでも使用しているのだが、これも殺意が湧くほど分かりづらいので、使用される方は覚悟が必要である。

コールバック関数

コールバック関数についても簡単に説明しておく。やれることは、ASTノードへのアクセスとContextへのアクセスである。Context (正式名称はASTContext) にはコードの行数など、ノードには含まれない副次的な情報が格納されているらしいが、詳しいことは分からない。気になる方は以下を参照のこと。

clang: clang::ASTContext Class Reference

以下にコード例を示す。

MemberAccessFinder.h

#ifndef MEMBER_ACCESS_FINDER
#define MEMBER_ACCESS_FINDER
#include "../include/Target.h"
#include "clang/ASTMatchers/ASTMatchers.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include <memory>


class MemberAccessFinder : public clang::ast_matchers::MatchFinder::MatchCallback {
public :
    MemberAccessFinder(std::shared_ptr<Target> tgt);
    // MatchCallbackクラスのrunメソッドをoverrideする
    virtual void run(const clang::ast_matchers::MatchFinder::MatchResult &result) override;

    /* 省略 */
};

#endif

MemberAccessFinder.cpp

void MemberAccessFinder::run(const MatchFinder::MatchResult &result) {
    ASTContext *context = result.Context;  // Contextの取得
    MethodInfoExtractor fie;
    std::string dep;
    // "fdecl"というkeyにbindされたノードをCXXMethodDecl型として取得
    if(auto *node = result.Nodes.getNodeAs<clang::CXXMethodDecl>("fdecl")) {
        // 関数名を取得 (詳細は後述のgithub参照)
        dep += "\"" + fie.extractFuncName(*node) + "\"";
    }

    dep += " -> ";

    // "mexpr"というkeyにbindされたノードをMemberExpr型として取得
    if(auto *node = result.Nodes.getNodeAs<clang::MemberExpr>("mexpr")) {
        // node->dump();
        auto decl = node->getMemberDecl();
        auto cls = node->Classify(*context);  // Contextからもいろいろ情報が取れる
        if(cls.getKind() == clang::Expr::Classification::Kinds::CL_MemberFunction) {
    /* 省略 */
}

おまけ：オプションパーサーについて

LibToolingではデフォルトでオプションをパースするための機能が備わっているので、基本的にはそれを利用する。自前でオプションを追加することも可能である。以下のサイトが参考になった。

clang-developers.42468.n3.nabble.com

こちらの質問者さんはうまく動かないと言っているが、私の環境ではこれに従ったら問題なくオプションが追加できた。

クラス内依存関係抽出ツールについて

いよいよ私が作ったツールについて説明する。ソースは以下のgithub リポジトリに置いた。

GitHub - peng225/class_dep: Class field and method dependency analysis tool.

ツールの概要としては、クラス内のメンバー変数・メンバー関数の依存関係を解析し、graphvizにてpngファイルとして結果を出力するものである。

例を見てみよう。まず、入力するソースコードを以下に示す。

sample.h

#ifndef SAMPLE_H
#define SAMPLE_H

class Sample
{
public:
    Sample();
    void setVal(int i);
    int getVal();
    virtual int addValAndGet(int addVal);
    int trivial();
protected:
    int hoge;
};

#endif

sample.cpp

#include "sample.h"

Sample::Sample() : hoge(0)
{
}

void Sample::setVal(int i)
{
    hoge = i;
}

int Sample::getVal()
{
    return hoge;
}


int Sample::addValAndGet(int addVal)
{
    return getVal() + hoge + addVal;
}


int Sample::trivial()
{
    return 5;
}

依存性解析だけが目的で、中身は全く無意味かつ命名もめちゃくちゃだがご容赦頂きたい。

このソースコードから得られるツールの出力は以下のようになる。

f:id:peng225:20210510150539p:plain — Sampleクラスの依存性解析結果

見た目にあまり気を使っていないので適当だが、四角がメソッドで丸がフィールドである。このように、依存関係が一目で理解できるようになった。

まとめ

以上、clangのLibToolingを用いて作成したクラス内依存関係解析ツールについて説明した。感想としては、clangのドキュメントが「あるだけマシ」というレベルで非常に辛かった。

コンパイラのFrontend機能を利用できるというのは普通に便利だしinnovativeだと思うので、もう少しドキュメントが整備されることを願って止まない。