⛳

JavaScript代数学 (1)

2021/04/06に公開

2021 年初めに公開された以下の記事では、クライアント・サーバー同型写像 (client-server isomorphism) という概念が提唱されました。しかしながら、この記事ではこの用語について少し触れられただけで、クライアント・サーバー同型写像という学問領域はまだ霧に包まれています。そこで、 JavaScript 代数学シリーズでは、最終的にクライアント・サーバー同型写像を理解することを目標として学習を進めていきます。

同型写像とは？

この用語で目につくのは「同型写像」という用語です。写像とあることからも分かるようにこれは数学用語ですね。Wikipedia の「同型写像」の記事で調べてみましょう（本当は数学書のような専門的な文献にあたるほうが良いでしょうが、このシリーズでは面倒なので Wikipedia を参照しながら進めていきます）。Wikipedia によれば、次のように書かれています。

数学において，同型写像（どうけいしゃぞう、（英: isomorphism）あるいは単に同型とは，準同型写像あるいは射であって，逆射を持つものである．

ということで、同型写像という概念を理解するためには「準同型写像」または「射」、および「逆射」の概念が必要であるようです。このシリーズでは、準同型写像ルートから攻略を目指します。

準同型写像の定義を見てみる

次は「準同型」の記事を見てみます。

準同型（じゅんどうけい、homomorphic）とは、複数の対象（おもに代数系）に対して、それらの特定の数学的構造に関する類似性を表す概念で、構造を保つ写像である準同型写像（じゅんどうけいしゃぞう、homomorphism) を持つことを意味する。

何だか抽象的な説明ですね。これは定義ではないようです。定義は記事の少し下に書いてあります。

A を台集合として、代数的構造 R をもつ代数系を (A, R) と記す。R は演算と呼ばれる写像 $\alpha: A \times \cdots \times A \to A$ の集まりである。同類である二つの代数系 (A, R), (B, S) (R = $\{\alpha_\lambda\}_{\lambda \in \Lambda}$ , S = $\{\beta_\lambda\}_{\lambda \in \Lambda}$ ) に対し、(A, R) から (B, S) への準同型写像 (f, F): (A, R) → (B, S) (F = $\{f_\lambda\}_{\lambda \in \Lambda}$ ) とは、台集合の間の写像 f: A → B であって、R, S の各々対応する演算 $\alpha_\lambda$ , $\beta_\lambda$ を可換にする（あるいは両立させる）写像 $f_\lambda$ を引き起こすものをいう。つまり

$f\circ \alpha _{\lambda }=\beta _{\lambda }\circ f_{\lambda },\quad {\Bigg (}f_{\lambda }((x_{i})_{i\in I_{\lambda }}):=(f(x_{i}))_{i\in I_{\lambda }}{\Bigg )}$

となる写像の組 (f, F) を準同型写像と呼ぶのである。ここで、 $\alpha_\lambda$ , $\beta_\lambda$ は $|I_\lambda|$ 項演算であるものとする。通常は (f, F): (A, R) → (B, S) を単に準同型 f: A → B と略記する。

これなら明確ですが、ちょっと難しいですね。ここで理解する必要はありません。それよりも注目すべきは、よく見ると最初の文に「代数系」なるものが登場しており、これが前提知識と伺われることです。まずこちらを学ぶ必要がありそうですね。

代数系とは？

Wikipedia の「代数的構造」の記事から冒頭を引用します。

数学において代数的構造（だいすうてきこうぞう、algebraic structure）とは、集合に定まっている算法（演算ともいう）や作用によって決まる構造のことである。代数的構造の概念は、数学全体を少数の概念のみを用いて見通しよく記述するためにブルバキによって導入された。

また、代数的構造を持つ集合は代数系（だいすうけい、algebraic system）であるといわれる。すなわち、代数系というのは、集合 A とそこでの算法（演算の規則）の族 R の組 (A, R) のことを指す。

特に最後の一文に「代数系」の定義が書いてありますね。つまり、代数系というのは集合とその上の演算を合わせて考えたものです。もっとざっくりした言葉で言えば、「計算ができる集合」とも言えます。

数学の世界には代数系の例がいくらでもあります。例えば、整数の集合 ${\mathbb Z}$ と整数の加算を合わせたもの $(\mathbb{Z}, +)$ は代数系です（特に、これはアーベル群になります）。

この記事は JavaScript と冠した記事なので、もう少し JavaScript 使いの方にとって馴染み深い例を考えてみましょう。配列（有限長の列）の集合を $\mathrm{Arr}$ とし、配列を結合する（concatメソッドにあたる）演算 $++$ を考えてみれば、 $(\mathrm{Arr}, ++)$ もやはり代数系です（これはモノイドと呼ばれる種類の代数系になります）。

$\mathrm{Arr}$ 上の $++$ 演算の例:

$[1, 2, 3] ++ [4, 5] = [1, 2, 3, 4, 5]$
$[3, 4] ++ [1] = [3, 4, 1]$
$[] ++ [1, 2] = [1, 2]$

要するに、何か集合（プログラマ的に言えば、対象となるデータ型）を決めて、その集合の要素に対する演算を定義してあげればそれが代数系なのです。ちなみに、集合に対する演算は 2 つ以上であっても構いません。環などは、複数の演算を持つ代数系（のクラス）の代表例でしょう。

JavaScript 代数系

以上でなんとなく代数系が分かりました。これでやっとこのシリーズのスタート地点に立つことができました。

このシリーズではクライアント・サーバー同型写像の考察の足がかりとすべく、 JavaScript 代数系を定義して今後の考察対象としていきます。

このシリーズでは、JavaScript 代数系とはJavaScript の AST ノード集合を台集合とする代数系のこととします。台集合というのは演算の対象となる集合のことであり、 $(\mathrm{Arr}, ++)$ の $\mathrm{Arr}$ 部分のことです。

JavaScript 代数系の例を見てみましょう。JavaScript の式を表す AST ノード全体の集合をExpと呼ぶことにします。さらに $\mathrm{plus}: \mathrm{Exp} \times \mathrm{Exp} \to \mathrm{Exp}$ という演算を定義してみましょう。すなわち、これは与えられた 2 つの AST ノードを受け取り、1 つの AST ノードを返す関数です。 $\mathrm{plus}(\mathrm{a}, \mathrm{b})$ は、a と b を+演算子（加算演算子）で結んで得られる式のノードを表すことにしましょう。

例えば、 $f =$ "foo", $b =$ "bar".repeat(3)とします（f と b はそれぞれ式を表す AST ノードです。以下では単に「式」と呼びます）。ここで $s = \mathrm{plus}(f, b)$ とすると、上の定義にしたがって $s =$ "foo" + "bar".repeat(3)となります。

他にも、1 引数関数 $\mathrm{toNum}: \mathrm{Exp} \to \mathrm{Exp}$ として次のようなものを考えることができます。

与えられた式が数値リテラルならそのまま返す。
それ以外なら、与えられた式を引数にNumber関数を呼び出す式を返す。

例えば toNum(foo) = Number(foo), toNum(1) = 1, toNum(3 + 0.14) = Number(3 + 0.14)などとなります。

まとめ

JavaScript 代数学シリーズの第 1 回として、JavaScript 代数学を学ぶ目的を説明し、さらにJavaScript 代数系を定義しました。次回は準同型写像について学び、JavaScript 代数系における準同型写像について考察します。

ではまた次回お会いしましょう。

練習問題

適当な AST の実装（例えば @babel/parser）を用いて、この記事に登場したplusとtoNumを実際に実装してみましょう。

GitHubで編集を提案