2012年5月14日月曜日

代数と余代数 最初の一歩


代数と余代数 最初の一歩

檜山正幸 (HIYAMA Masayuki)

Wed May 11 2005:start
Sat May 14 2005:draft
Mon May 16 2005:prefinal

形式的体系の初歩的知識を仮定して代数と余代数の紹介を試みる。特別な条 件を満たすソート付き形式的体系の指標（signature）を代数指標／余代数指 標と定義して、それのモデルとして代数／余代数を導入する。余代数とオブジェ クト指向との関係にも言及する。

1. はじめに

後々の説明の都合を考えると、代数と余代数について早めに解説すべきだ、 と感じた。そこでこの記事では、あまり予備知識を仮定しない(*注1)で、代数 と余代数をラフかつインフォーマルに紹介する。

注1

圏論はまったく使わない。

「余代数」は聞き慣れない言葉かもしれないが、「代数」という言葉には、 なにかしら（それぞれに）印象を持っているだろう。そういう印象や先入観 はすべて捨てたほうがいい。この記事で導入する概念・用語である「代数／ 余代数」とは、特定の分野における専門用語（ほとんどジャーゴン）である。 既にあなたが知っている代数とは接点を持たない概念かもしれない(*注2)。分 かりにくいと感じたら、見出しに「解説：」と付いているノートも一緒に読む とよいだろう（原則としてノートは飛ばしてもよいが）。

注2

実際のところ、この記事で導入する代数概念の特殊ケースとして通常の代数 概念が説明できる。だが、最初はそのようなことを気にしないほうがいい と思う。

2. 事例の提示

この記事全体で、記事「『形式的』とは何だろう」 と記事「『正規（regular）』とは何なんだ 3 補足、実例など」を参照する。特に、 「『正規（regular）』とは何なんだ 3」の第3節で導入したソート付き の形式的体系の概念を再確認してほしい。

この節では、いくつかのソート付き形式的体系を事例として挙げる。なお、 事例に付けられた名前（例：「ペアノ流の自然数」）は、気持ち（下心）を表現し たものであり、その名前から連想されような"意味"を持つとは限らない。体 系の名前は、名目上は単なるラベルである。なお、下心（したごころ）につい ては、 「『形式的』とは何だろう」の第5節を参照。 理解をうながすために、下心（「××に使いたい」、「××に使うつもり」） も説明されているが、あくまでも「こんな下心もあり得る」というだけであ ることに注意。

・ 事例1： ペアノ流の自然数

  • ソートの集合：{Nat}
  • プロファイル「->Nat」の関数記号の集合：{0}
  • プロファイル「Nat->Nat」の関数記号の集合：{suc}

ソートの集合が単元（singleton）集合{Nat}なので、これはソートなしの体 系として定式化してもいいのだが、ここでは明示的にソートNatを考える。Nat は自然数の全体、sucは1を足す関数（例：suc(1)=2）のつもりである、

・ 事例2： 自然数の算数

  • ソートの集合：{Nat}
  • プロファイル「->Nat」の関数記号の集合：{0, 1}
  • プロファイル「Nat, Nat->Nat」の関数記号の集合：{add, multiply}

気持ち（下心）としては、足し算（add）と掛け算（multiply）を含む計算式 （項）を記述したい。定数は0と1だけだが、もちろん実際はもっとたくさんの 定数を導入するほうが便利だ。今は便利さを問題としてはいないけれど。

・ 事例3：スタック

  • ソートの集合：{Item, Stack}
  • プロファイル「Stack->Item」の関数記号の集合：{top}
  • プロファイル「Stack->Stack」の関数記号の集合：{pop}
  • プロファイル「Stack, Item->Stack」の関数記号の集合：{push}

これは単純化してあって、スタックがあふれたり、空になっても特にエラー や例外は出ないとしている。適当に特殊値を選んで、スタックが空であること を知らせるような状況を考えよう（あくまでも気持ちの問題）。

・ 事例4： Tiny Toy XMLのインスタンス

「『正規（regular）』とは何なんだ 3」 の第4節とは違って、Tiny Toy XMLのインスタンスについて考えるから注意。 choiceは言語に対する演算でインスタンスには定義できないので除いてある。 （といったことも、気持ちの問題だが）。
  • ソートの集合：{Name, Tree, List}
  • ソートの順序： Tree < List
  • プロファイル「->Name」の関数記号の集合：すべての名前リテラル
  • プロファイル「->List」の関数記号の集合：{empty}
  • プロファイル「List,List->List」の関数記号の集合：{concat}
  • プロファイル「Name,List->Tree」の関数記号の集合：{surround}

NOTE: 解説：形式的体系は無意味な記号システムに過ぎない

くどいが、形式的体系を理解するカナメは、記号とその意味を区別する ことである。記号システムが提示された段階では、その意味は特定されていな い。例えば、上の「事例1： ペアノ流の自然数」に出てくる、Nat、0、sucという 記号は単なる記号であるから、Foo、hoge、helloと改名しても本質的な変化は ない。

「まったく意味を持たない」ことと、それでも「暗黙には使用法を想定して いる」という、やや矛盾した状況を表現するために僕は、「下心 = まだ行使さ れてない隠れた意図」という言葉を使っているのだ。

3. 形式的体系の指標（シグニチャ）

前の節で挙げた4つの例を、次のような構文で記述することにしよう。 

  /* 事例1： ペアノ流の自然数 */  signature Peano {   sort: Nat;   function:     0:->Nat;     suc:Nat->Nat;  }    /* 事例2： 自然数の算数 */  signature Arith {   sort: Nat;   function:     0, 1:->Nat;     add, multiply:Nat->Nat;  }    /* 事例3：スタック */  signature Stack {   sort: Item, Stack;   function:     top:Stack->Item;     pop:Stack->Stack;     push:Stack, Item ->Stack;  }    /* 事例4： Tiny Toy XMLのインスタンス */  signature TinyToyXMLInstance {   sort: Name, Tree, List;   order: Tree < List;   function:     //     // 名前リテラルは膨大になるので省略     //     empty: ->List     concat:List, List ->List     surround: Name, List ->Tree  }

この記法で、signatureという綴りが出てきたが、「ソート集合、ソートの順 序（あれば）、関数記号集合」の記述を、形式的体系の'指標'（シグニチャ、 signature）と呼ぶ。指標が与えられると、（変数を含まない）項の集合が完 全に定まる。例えば、Peanoという指標の項は、0, suc(0), suc(suc(0)) など である(*注3)。

注3


見つける方法を数は直交している

記号「0」は引数がない関数記号だから、引数を渡す括弧を添えて「0()」と 書くべきかもしれないが、通常、そんなうるさいことは言わない。

指標をΣ、Δなどで表し、指標Σとソート付き変数集合Xから作られる項の集 合をTermΣ(X)とする。Xが空のとき、TermΣ(0)を単にTermΣ とも書く（0は空集合）。

NOTE: 解説：指標とインターフェース

指標の記述例を眺めてもらえれば分かるだろうが、指標はプログラミング言 語（あるいはIDL）で記述されるインターフェースと似ている。ほぼ次のよう な対応がある。

  • 指標 ⇔ インターフェース
  • ソート ⇔ 型の名前
  • 関数記号 ⇔ 関数やメソッドの名前
  • プロファイル ⇔ 関数やメソッドの引数・戻り値の仕様

用語法としては、Javaなどで"signature"が「メソッド名＋引数仕様」の意 味で使われるので混乱しがちである。形式的体系におけるsignatureは、基本 記号一式のことである。「指標」と漢字で書くことにしたのも、用語の混乱を 避けるためである。

4. 複合ソートとプロファイルの変形

「『正規（regular）』とは何なんだ 3」の 第3節でも述べたように、ソートは単なる記号である。記号を組み合わせて 複合記号を作ることができるが、次のような組み合わせ方（記号操作）を導入 しよう。
  1. カンマをはさんで2つ以上の記号を並べる（記号列を作る）。必要があれ ば、まとまりをつけるために丸括弧を使ってよい(*注4)。
  2. 空白をはさんで2つの記号を並べ、全体をブラケットで囲む。

注4

丸括弧は補助的な記号なので、不要なら適宜省略してよい。

与えられたソートの集合を基本にして、上の2つの操作によって作られる記号 を'複合ソート'と呼ぶ。ソートの集合が{Name, List, Tree}のとき、次は複 合ソートの例である。

  • Name, List
  • [Name List]
  • [([Name List], Tree) List]
  • [Name [List Tree]]

これから先、ソートといった場合には、複合ソートも含めて呼ぶことに する。もう少し正確に言うと、'ソート'を次のように再定義する。

  1. 与えられたソートの集合に属する記号はソートである。（基本ソート）
  2. 空列はソートである。必要なら空列をεと表記する。
  3. αとβがソートなら、(α, β)はソートである。（複合ソート）
  4. αとβがソートなら、[α β]はソートである。（複合ソート）
  5. 以上の手順で得られるものだけがソートである。

αとβがソートのとき、αとβの間に区切り記号「->」をはさんだもの（こ れも複合記号）をあらためて'プロファイル'と呼ぶ。

天下りで機械的であるが、次の2つの操作をプロファイルの'基本変形'と呼 ぶ。

  1. プロファイルのどこかに、(α, β)の形が出てきたとき、それを (β, α) で置き換える。
  2. α, β->γ の形のプロファイルを α -> [β γ] にする。

例えば、Name, List -> List というプロファイルは次のように変形できる。

  1. Name, List -> List
  2. List, Name -> List （Name, List を List, Name と置き換え）
  3. List -> [Name List] （Nameを左から右に移動）

複合ソート、プロファイル、プロファイルの変形の意味づけについては次節 で述べる。

5. プロファイル変形は何に使うか -- カリー化を中心に

前節で導入したプロファイルの変形は、まったく機械的な記号操作であ る。この機械的操作を何に使うかを説明しておこう。

この節の「高階関数とカリー化」の説明はあまり分かりやすくないかもしれ ない。いずれ、実在するプログラミング言語（たぶんGroovy）を使った説明を 書くつもりだ。必要と興味に応じて、この節の下 のノートも読むといいだろう。いずれにしても、高階関数とカリー化を完全に 理解してなくても後続の節を読めると思うので、あまり気にしないで欲しい。

・ 引数の順序交換

一例としてsurround:Name,List->List というプロファイルを考える。これの 意図（下心）は：

  • surroundという関数は、Name型とList型の2つの引数を取り、List型の値 を返す
というものである。ここで、引数の順序がName, Listであることに絶対的な根 拠はない。List, Nameの順にしてもよい。つまり、引数の順序交換は許される だろう。引数の順序交換をすれば、プロファイルは List,Name->Listとなる。 いま使った「引数の順序交換」に対応する記号操作が、（ソート／プロファイ ルの）基本変形の1つ (α, β) 〜> (β, α) である。（記号「〜>」は記号 的変形のつもり）

・ 高階関数とカリー化

もう1つの基本変形 (α, β->γ) 〜> (α -> [β γ])は少しやっかいである。 複合ソート[β γ]とそれを含むプロファイル(α -> [β γ])がなにを意図し ているかを知る必要がある。それには、高階関数とカリー化の概念が必要にな る。

おおざっぱにいえば、複合ソート[β γ]が表す型は、β->γという 関数が値である型である。別な言い方をすると、[β γ]は、β->γとい う関数を値とみなしたモノの集合を意図している。関数を値とみなすとい うことは、関数を引数や戻り値にも使う（使ってもよい）ことを意味する。 "関数引数の関数"や、"関数を返す関数"などを考えることになる。そういっ た"関数を扱う関数"を'高階関数'と呼ぶのだ。

カリー化とは、「2引数の関数を1引数の関数値関数（高階関数）にする」技 法である。このカリー化を以下に簡略に説明しよう。

fが2引数の関数のとき、引数x, yに対するfの値をf(x, y)と表記する（これ は常識的な記法だね）。ここで変数xをaに固定して、yだけを動かすと、y→ f(a, y)という"yを変数とする関数"が定義できるが、それをと書くことにする （「よく使う記法など」の第2節参照）。

関数は、値aごとに決まる。つまり、a→ という対応がある。この対応は、値aに"1引数関数"を 割り当てるから、>と書けるだろう。「変数xをaに固 定して」と言ったが、いまやaも変数だから（単に気分の問題から）xに戻すと、 >となる。


単位ベクトルとは何か

最初の関数fはだったが、上の手順で変形した関数 は>の形になった。>は高階関 数である。ここで、変数x, yの型をそれぞれX, Yとし、fの戻り値の型をZとす る。するとfは X, Y → Zという型仕様（プロファイル）を持つ。さらに、Y → Z という関数を値とみなした型を[Y Z]と書くことにすると、 高階関数>の型仕様は、X → [Y Z] となる。

f:X, Y → Z という関数から、上の手順でf':X → [Y Z] という関数を作り 出す操作を'カリー化'と呼んでいる。カリー化によるプロファイルの変化に だけ注目すると、X, Y → Z から X → [Y Z] と、Zが左から右に移動してい るように見える。この図式的変形を機械的記号操作として取り出したのが、 （ソート／プロファイルの）基本変形 (α, β->γ) 〜> (α -> [β γ])である。

NOTE: 物理現象とカリー化

方眼を描いた鉄板をコンロで熱するような状況（鉄板焼き）を考えよう。方 眼が描かれているから、鉄板にX-Y座標系がある。座標が(x, y)である点の温 度をf(x, y)とすると、温度分布を表す関数fは2変数（2引数）関数である。

このケースでは、2つの平面座標変数xとyは対等であり、どちらかをひいきする理由はない。つ まり、2変数のまま扱ったほうが自然である。さて、温度分布は時間と共に変 化するから、時間tを第三の変数として、関数f(x, y, t)を考えよう（同じ文字fを 使ったが、2変数のfとは区別すべきである）。3変数のfでは時間変数tが異質 だから、f(x, y, t)の代わりにf(t; x, y)とでも書いておこう。

ある特定時刻sの温度分布（スナップショット）はf(s; x, y)で与えられる。 座標変数(x, y)に対する関数を"温度分布"というタイプの値だと捉える と、「時刻→温度分布」という対応が考えられる。

以上の過程は、3変数関数f(x, y, t)のtを特別扱いしてf(t; x, y)として、 さらに t → f(t; x, y) と"時間変数に温度分布を対応させる関数"とみな したことになる。温度分布の実際の表現は2変数（xとy）関数だから、「時刻 →温度分布」は"関数を値とする関数"、つまり高階関数である。

x, y, tの3変数関数から、tだけを変数とする高階関数を作り出す手続きはカ リー化の例になっている。このカリー化は、実際上も意味のある操作で、例え ば、熱の偏微分方程式を高階関数の常微分方程式として扱うことを可能とする。

NOTE: コンピュータとカリー化

カリー化とは「2変数関数を1変数関数だと思い直す」ことだと説明したが、 より一般的に「n変数関数を(n - k)変数関数だと思い直す」ことである。鉄板 焼きの例では、3変数関数を1変数関数だと思い直しているから、n=3、k=2の事 例である。

さて、n=1、k=1のケースは「1変数関数を0変数関数だと思い直す」ことにな る。これもカリー化の例である。そしてこれは、関数を値だと思うことになる。 別な言い方をすると、機能や動作として認識していた対象をモノ扱いすること （モノ化）である。

現代のコンピュータでは、計算を行う関数（のプログラム）も、ビット列と してメモリ領域にストアされているから"モノ化"されている。実はカリー化 とは、現代のコンピュータにとっての根源的なアイディアである「コードをデー タとみなすこと」の表現である。カリー化された関数は、部分的に（あるいは完全に）データとみ なされている。データを再びコードとして解釈するために、適用とか評価を作 用させることになる。

カリー化、高階関数、関数空間（指数）が、あちらこちらで顔を出すのは、 それが必然的な存在だからだろう。

NOTE: シーケントとカリー化

論理のシーケント（sequent）をご存じなら、プロファイルをシーケントと比 べてみるとよい。

基本変形 (α, β) 〜> (β, α) は構造規則の「換」に相当する。基本変形 (α, β->γ) 〜> (α -> [β γ]) は、含意の導入規則である。本文の定式化では 明示的な合接（AND演算）は存在しないが、∧を合接とすると、(α, β) を α∧β に置き換える規則として合接の導入規則を定義できる。

本文で述べた機械的記号操作に合接を入れて多少手直しすれば、合接（直積 に対応）と含意（指数に対応）を含んだ、極端に単純な（しかし、それなりに 面白い）シーケント計算システムが作れる。

6. 指標に対するモデル

通常の形式的体系は、項（term）以外に式（formula）を持ち、いくつかの式 を公理として指定する。さらに、推論機構（演繹系、証明系）を備えているこ ともある。だが、この記事では式や推論を扱わないので、形式的体系は指標だ けで完全に決まってしまう。つまり、この記事のように単純化された状況設定 では、「指標 = 形式的体系」である。

さて、指標から一意的かつ完全に決まってしまう形式的体系に意味を与えよ う。ここで、意味付けとは、次のようなことだとする。

  1. 指標に出現する各ソート記号（基本ソート）に対して、集合を割り当てる。 ソートsに対する集合をD[s]と書くことにする（domain of s）。
  2. ソートの順序に対して、集合のあいだの単射を割り当てる。つまり、s < t のとき、D[s] → D[t] という1：1の写像が与えられる(*注5)。
  3. ソートとしての空列には、（何でもいいから）一点集合を割り当てる。つ まり、D[ε] = {*} （*はなんでもよい）。
  4. D[(α, β)] には D[α]×D[β] を割り当てる。演算×は直積である （「タプルと直積」参照）。
  5. D[[α β]] には Map(D[α], D[β]) を割り当てる。Map(X, Y)は、Xから Yへの写像の全体からなる集合である。
  6. 指標に出現する各関数記号 f:α->β に対して、D[α]→D[β]である写像 を割り当てる。記号fに対するホントの写像をF[f]と書くことにする （function of f）。

注5

「s < t」のように不等号を使うときは、不等号の向きをどう決めるかでたい てい悩む。ここでは、D(s) ⊆ D(t) という集合の不等号（包含関係）との類 似性から不等号の向きを決めた。

以上に述べた「意味づけ」の定義は、TermΣに属する項の「値を求める」 ために必要な準備だといえる。実際、変数を含まない項（TermΣのメンバー） の帰納的定義にそって、その値を計算することができる（詳細は省略）。


eathsの傾きの度合いは何ですか

上の定義で出てきた、ソート記号／関数記号に意味（数学的実体）を割り当 てる対応D[-]とF[-]の組を'モデル'と呼ぶ。モデルは、指標に含まれる記号 に対して定義されるものだから、「指標Σのモデル」のような言い方をする。

指標を1つ固定しても、そのモデルはいくらでもありえることは、 「『形式的』とは何だろう」の第6節で指摘 したことである。極端な例として、次の指標を考えてみる。 

  signature Trivial {   sort: Any;  }

この指標には、ソート記号がただ1つあるだけで、関数記号はない。よって、 Trivialのモデルとは、記号Anyに対して集合D[Any]を対応させるものである。 つまり、なんでもいいから1つの集合を選ぶと、それはTrivialのモデルになる。 別言すれば、Trivialのモデルの数は集合の数(?)だけある。

練習問題として、次のような簡単な指標のモデルがなんであるかを考えてみ よ。 

  signature Pointed {   sort: Any;   function:     point:->Any;  }    signature Shiftable {   sort: Any;   function:     shift:Any->Any;  }    signature Peekable {   sort: State, Value   function:     peek:State->Value;  }

7. 代数指標と余代数指標

我々はソート付き体系の指標を考えているので、指標には少なくとも1つのソー ト（型を表すつもりの記号）が存在する。関数記号はなくてもいい。だから、 一番簡単な指標は先に例示したTrivialである。

ソートのなかの1つが'主要ソート'（primary sort）として指定されている ような指標を考える。例えば、指標StackにはItemとStackという2つのソート が登場するが、我々は気持ちのなかでは暗黙に「Stackが主役でItemは補助的 なものだ」と想定している。このような、暗黙の思いを明示的にした概念が主 要ソートである。

この記事では、主要ソートがあるとき、それを丸括弧で囲って示すことにす る（まったく臨時の記法）。例えば、ソートStackが主要ソートであることは 次のように表す。 

  signature Stack {   sort: Item, (Stack);   function:     top:Stack->Item;     pop:Stack->Stack;     push:Stack, Item ->Stack;  }

指標のなかで、次の条件を満たすものを'代数指標'（algebra(ic) signature） と呼ぶ。

  1. 主要ソートが指定されている。
  2. 主要ソートをsとするとき、関数記号のプロファイルがどれも α->s の形 をしている。αは、任意のソート（複合ソートも許す）である。

今までに出した例に主要ソートの指定をすると代数指標となるものがある。 以下は、そのようにして作られた代数指標である。 

  signature Trivial {   sort: (Any);  }    signature Pointed {   sort: (Any);   function:     point:->Any;  }    signature Shiftable {   sort: (Any);   function:     shift:Any->Any;  }    signature Peano {   sort: (Nat);   function:     0:->Nat;     suc:Nat->Nat;  }    signature Arith {   sort: (Nat);   function:     0, 1:->Nat;     add, multiply:Nat->Nat;  }

指標のなかで、次の条件を満たすものを'余代数指標'（coalgebra(ic) signature）と呼ぶ。

  1. 主要ソートが指定されている。
  2. 主要ソートをsとするとき、関数記号のプロファイルがどれも s->αの形 をしている。αは、任意のソート（複合ソートも許す）である。

次は、 今までに出した例に主要ソートの指定をして余代数指標としたものである。 

  signature Trivial {   sort: (Any);  }    signature Shiftable {   sort: (Any);   function:     shift:Any->Any;  }    signature Peekable {   sort: (State), Value   function:     peek:State->Value;  }

余代数指標の例のなかで、TrivialとShiftableは代数指標でもあるし、つま らない例である。Peekableも面白くない。StackやTinyToyXMLInstanceが余代 数指標になってくれればいいのだが、残念ながら、このままでは余代数指標で はない。

NOTE: 解説：なぜに「代数」、なぜに「余代数」

この段階で、ある特定の条件を満たす指標を代数指標とか余代数指標と呼ぶ のか？ と疑問を感じるのは当然である。が、ときに背景や由来の詮索を中止 して、天下りの定義を受け入れたほうが建設的なこともある。

先走って言えば、代数指標のモデルが"伝統的に代数と呼ばれていた構造" を比較的よく表現することが、形容詞「代数」を付ける理由である。そして、 余代数は代数を鏡に映したような対称的な構造だから、相棒／相方を意味する 「余」（co）が付いている。

まー、だいたいそういう事情なのだが、（僕の経験から言って）そのような ことに神経を使いすぎるのは、先に進む障害になるだけのようだ。僕が、「こ だわるな」という事をこれだけシツコクこだわって言っていることから、僕が かつて、こだわるべきでない事にこだわってどれだけ損をしたかが察せられる だろう。

8. スタック指標を余代数指標とみなす方法

指標が余代数指標であるためには、次の条件を満たす必要があった。

  • 主要ソートをsとするとき、関数記号のプロファイルがどれも s->αの形を している。

Stackの場合、関数記号のプロファイルは次のとおりである。 

     top:Stack->Item;     pop:Stack->Stack;     push:Stack, Item ->Stack;
見ればわかるとおり、pushが余代数の条件を破っている。

さて、pushのプロファイルである(Stack,Item->Stack)に基本変形をほどこす と、Stack->[Item Stack]となる。もし、基本変形後のStack->[Item Stack]を pushのプロファイルに採用してよいのなら、関数記号のプロファイルは次のよ うになる。 

     top:Stack->Item;     pop:Stack->Stack;     push:Stack->[Item Stack];

こうなれば、すべての関数のプロファイルが Stack->α（αは任意）と なり、余代数指標の条件をクリアする。プロファイル(Stack,Item->Stack)を プロファイルStack->[Item Stack]に置き換えても、意味付けに支障をきたさ ないので、我々はプロファイルの基本変形を遠慮なく使うことにする。

なぜ「意味付けに支障をきたさない」かといえば、pushの意味F[push]が、 D[Stack]×D[Item]→D[Stack]という写像として与えられているとき、カリー 化によりF[push]を、D[Stack]→Map(D[Item], D[Stack])という"高階関数" とみなせるからである。

カリー化を自由に行ってよい、ということであれば、余代数指標の条件を次 のようにゆるめてもよい。

  • 主要ソートをsとするとき、関数記号のプロファイルがどれも α, s, β-> γの形をしている。ここで、α、β、γは（空列でもよいし、複合ソート でもよい）任意のソート。

α, s, β->γ は、順序を交換してまとめなおせば s, (α, β)->γ となり、 カリー化を使って s->[(α, β) γ] とできるので、余代数指標の条件を満た すプロファイルになる。


いずれにしても、スタックの例は余代数指標とみなせる。 

  signature Stack {   sort: Item, (Stack);   function:     top:Stack->Item;     pop:Stack->Stack;     push:Stack->[Item Stack];  }

9. 余代数指標とインターフェースの関係

ある指標が余代数指標であることを明示するために、signatureの代わりに coalgebraというキーワードを使うことにしよう。さらに、次の約束も導入す る。

  1. 指標の名前と主要ソートの名前を必ず一致させる。
  2. 主要ソート以外のソートがあれば、それを指標名のパラメータとして山括 弧（実際は不等号）で囲んで記述する。例えば、Stack のようにな る。
  3. キーワードfunctionの代わりに、キーワードmethodを使う。
  4. プロファイルに出現する主要ソートを省略（削除）する。

スタックについて考えると次のようになる。

  1. 指標の名前と主要ソートの名前を共にStackとする。
  2. 指標の宣言を coalgebra Stack ではじめる。
  3. キーワードmethodを使う。
  4. top:Stack->Item; を、top:->Itemに変更する。その他も同様。

push:Stack->[Item Stack]; に関しては、push:->[Item ]; とするとワケが 分からなくなるので、もともとのプロファイル push:Stack, item->Stack; か らStackを取り除いて push:Item->; とする。結果として、次のような指標記 述が得られる。 

  coalgebra Stack {   method:     top:->Item;     pop:->;     push:Item->;  }

実を言うと、「プロファイルに出現する主要ソートを省略（削除）する」の がいつでもうまくいくとは限らない。プロファイルの（「->」の）左右に高々 1回しか主要ソートが出現しないときしか省略できないが、とりあえず、うま くいくときだけ考える。

こうしてみると、（都合のよいケースだけ考えれば）余代数指標は、オブジェ クト指向言語におけるパラメータ付きの（テンプレートとかジェネリックスと か呼ばれる）インターフェースとほとんど同じものである。念のため、Javaの 構文で書いてみれば次のとおり（J2SE5のjavacでコンパイル可能）。 

  interface Stack {     Item top();     void pop();     void push(Item item);  }

省略して書かないことにした主要ソートとはthis（とかself）の型に相当す る。メソッドが引数を持たないときでも、暗黙のthisが渡されているし、メソッ ドが戻り値を持たないときでも、thisへの副作用を持っている（可能性がある）。 要するに、オブジェクト指向において暗黙的に仮定される「thisの型」が、余 代数指標の主要ソートである。そして、余代数の条件とは結局「関数がメソッ ド（として解釈可能）であること」を主張しているに過ぎない。

10. 言い残したこと色々

この記事は「最初の一歩」だから、この辺でそろそろ終わりにしたい。説明 が中途半端だから気になることが色々あるだろう。手短にいくつかコメントす る。

まず、前節の説明を読むと、余代数指標がインターフェースを説明するため にでっち上げた数学的概念のような気がするかもしれない。が、そうでは ない。歴史的には、代数概念を一般的に定義する手段として代数指標が出現し た。余代数指標は代数指標から双対化という操作で得られた概念で、特別にオ ブジェクト指向におもねっているわけではない。

代数指標／余代数指標は定義したのだが、代数／余代数は定義してない。簡単に 触れておくと、（余）代数指標のモデルが（余）代数である。余代数指標がほ ぼインターフェースに対応するから、モデルである余代数はインターフェース の実装に当たる。インターフェースの実装はクラスといってもいいだろう。ま とめれば、「余代数指標がインターフェース、余代数がクラス」という（おお よその）対応がある。

余代数はオブジェクト指向のためにあつらえた概念ではないが、オブジェク ト指向的な計算現象の説明に割と適合する。すべての現象が余代数で説明できるわ けではないが、余代数が適用できればうまく説明できる可能性が高いのだ。実 際、「余代数指標がインターフェース、余代数がクラス」という対応から導か れる事実や知見は多い。

ところで、Tiny Toy XMLの例を出したが、Tiny Toy XMLの例は代数とも余 代数とも言ってなかった。試みてみると分かるが、ツリー構造の指標は、代数 でもなければ余代数でもない。代数と余代数が混じったような構造なのだ。

非常におおざっぱにいうと、代数は関数型のプログラミング・パラダイムと 相性が良く、余代数はオブジェクト指向のプログラミング・パラダイムと相性 が良い。しかし、ツリー構造は、代数でもないし余代数でもない(*注6)。これは、 XMLデータのようなツリー構造は、関数型パラダイムで扱ってもオブジェクト 指向パラダイムで扱ってもうまくいかないことを示唆する。

注6

正確に言えば、ツリー構造は代数になるし余代数にもなる。問題は、どち らとも見なせるが、どちらかに決定できないことなのだ。

僕は、XML応用言語（ボキャブラリ）やXML処理系の設計・実装・運用を通じて、ずっ と、なんかイヤーな感じをいだき続けてきたのだが、この「イヤーな感じ」の 正体の（少なくとも一部）は、ツリーが代数でも余代数でもないことに起因し ていると思っている。理論的には、代数と余代数の両方の構造を持つような定 式化が必要なのだろうし、プログラミング手法としては単一のパラダイムでは なくハイブリッド・パラダイムが必要なのだろう。

現実世界の仕様について（かなり強引に）言えば、「XML 1.*」仕様は代数を 定義しており、「DOM *」仕様は余代数を定義している。さらに強引に言えば、 「XML 1.*」仕様が構文の基礎であり、「DOM *」仕様がプログラム処理の基礎 である。だが、このような両極をつなぐような包括的な枠組みは欠けている。

だから、僕はとりあえず、ツリーやグラフのようなデータ構造を具体例とし て、代数的側面と余代数的側面をつなぐ現実的な枠組みを求めているわけだ。



These are our most popular posts:

関係データベース管理システム - Wikipedia

導出関係とは、関係代数もしくは関係論理の式に名前を付けたものである。導出関係は 関係の ... なおこれに対し SQL CREATE TABLE 文で定義するような基本的な関係 ( テーブル) を基底関係という。また導出関係を ... [編集] RDBMSの用語の歴史. 1969年 、 ... read more

Haskell/Denotational semantics - Wikibooks

正格、非正格な言語で⊥を含んだ任意の代数的データ型がどのように発散するかは、 セクション代数的データ型で扱われています。 ..... 動機付けとして Integer 型間の部分 関数の場合を処理した後に、現在のHaskellにおける任意の代数的データ型の表示的 意味論に範囲を拡張したいと思います。 ... この用語は、より一般的な名前 で、私たちの領域がcpo(完全半順序)であると判断し、値の集合と一緒に不動点反復を 可能に ... read more

インラインマークアップ — Sphinx v1.0.6 documentation

Sphinxは解釈済みのテキストのロールというものを使用して、用語の意味を記述して、 リンクを張ったりすることができます。これを記述する ... 必要に応じてどのように使用して もかまいません。例えば変数名 .... テキスト中の用語の定義を書くのに使用します。 .... 文法のトークンの名前です。 productionlist ディレクティブ内の定義との間でリンクが 作成されます。 ... デフォルトでは3つの代数がドキュメントシステムから提供されてい ます。 read more

プロセス計算 - Wikipedia

プロセス演算子の代数学的規則を定義し、プロセスの表現を方程式を解くように操作 可能とする。 [編集] プロセスの数学. プロセス計算を定義するには、通信手段を提供する ことを目的とした「名前（name）」または「通信路（channel）」を始点とする。多くの実装で 、 ... read more
投稿者 時刻:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)