「正規(regular)」とは何なんだ

檜山正幸 (HIYAMA Masayuki)
Wed Mar 30 2005:start
Fri Apr 01 2005:draft

正規表現、正規言語などにおける「正規」という概念について考えてみます。 また、それを糸口に再帰代入系への道筋を示し、ウルトラ・マクロな立場/ア プローチも紹介します。

目次

1. はじめに

この記事のタイトルにある「正規(regular)」は、正規表現(regular expression)、正規言語(regular language)、正規集合(regular set)な どに付いている形容詞である「正規」のことです。 さまざまな正規ナントカがあるのですが、「正規」という形容詞を付けていい状況、 正規と呼ぶにふさわしい対象とは何でしょうか。それを探ってみます。

この記事の内容は、「属性のための正規表現」 に関係してます。「属性のための正規表現」を全部ていねいに読む必要はあり ませんが、第5節までザッと目を通してくだ さい。また、 「再帰代入系 1」「再帰代入系 2」とも深く関係し ます。ですが、「再帰代入系 1 and 2」は、分量がおおいし読みやすくもない ので、今から(この記事の準備として)読む必要はありません。むしろ、この 記事が「再帰代入系 1 and 2」を読むための足がかりとなるでしょう。もし、 記号とその意味に関して困惑/混乱を感じたら、 記事「『形式的』とは何だろう」が多少の助け になるかもしれません。

正規表現とBNF(Backus Naur Form)は知っているものと仮定します。 正規表現に関しては、いたるところに参考資料があるでしょう。BNFについ て 以前に僕 (檜山)が書いた記事 (http://www.atmarkit.co.jp/fxml/ddd/ddd004/ddd004-bnf.html)があり ますから、必要があれば参照してください。

2. 正規表現の書き方

正規表現で普通に使われる構文的演算子(メタ文字)は、「|」、「*」、「?」、 「+」です。通常、連接には特別な演算子は使いませんが、ここでは「,」を連 接を表すメタ文字としましょう。「,」と「|」が中置2項演算子で、「*」、「?」、 「+」は後置単項演算子となります(「*」、「?」、「+」を前置にする書き方 もありますが、あまり使われません(*注1))。

注1

RFCをよく呼んでいる人にはお馴染みかもしれません。

メタ文字、すなわち記号1文字による構文的演算子は、式をコンパクトに書け てとても便利ですが、演算子を関数呼び出し形式で書くほうが扱いやすいこと もあります。そこで、次の表のような対応で、演算子に関数としての名前も付 けておきます。また、何も出現しないことを表すためにEMPTY/emptyを使いま す。

TABLE: メタ文字と関数名
メタ文字 関数名
, concat
choice
? option
* repeat
+ positiveRepeat

関数呼び出し形式を使うと、例えば (x?, (a+ | (b, c*)) という正規表現は、 concat(option(x), choice(positiveRepeat(a), concat(b, repeat(c)))) と書 けます(長たらしい!)。concatとchoiceは標準で2つの引数を取りますが、 concat(a, b, c)とかchoice(x, y, z, w)のように、2個以上の引数をとっても いいとしましょう。

NOTE: カンマの使い方

老婆心で言いますが、(a, b) と concat(a, b) という2つの表記法における カンマの使用法はまったく別です。注意してください。カンマを2項演算子記 号とみなすときは、算数の「+」や「×」と同じ使い方です。ただ、スペース の取り方を (a,b) とか (a , b) とか書くとどうも気持ちが悪いので (a, b) と書いてます。

それに対して、関数呼び出し形式 concat(a, b) におけるカンマは、2つの引 数を分けるための単なる区切り記号です。

関数記号の引数の個数を明示するために、option/1とかconcat/4というように、 名前の直後に「スラッシュ+引数の個数」を添えて示すことにします(*注2)。こ の書き方を使って今まで登場した関数記号/定数記号をすべて列挙すると次の通りで す。

  1. empty/0
  2. option/1, repeat/1, positiveRepeat/1
  3. concat/2, concat/3, concat/4, ...
  4. choice/2, choice/3, choice/4, ...
注2

これはプログラミング言語Prologでよく使われる書き方です。

「再帰代入系 1」「『形式的』とは何だろう」を読んでいるかた は、そこで出てきた関数記号集合の概念を憶えてますか? 今までの話は、次 のような関数記号集合F=(F0, F1, F2, ...)を定義してます。
  1. F0 = {empty}
  2. F1 = {option, repeat, positiveRepeat}
  3. F2 = {concat, choice}
  4. F3 = {concat, choice}
  5. …(以下同様)
NOTE: 正規表現の標準的解釈

上に挙げた構文的演算子と定数EMPTYの標準的解釈を示しておきましょう。こ こで「標準的」といったのは、それ以外の解釈もあり得るからです。が、特に断 りがなければ標準的(あるいは常識的)解釈で考えます。

演算子は「,」(concat)、「|」(choice)、「*」(repeat)だけを考え、 A? は (A | EMPTY)、A+は (A, A*)の略記とみなしましょう。Σはアルファベット (基本記号の集合)だとして、Σをベースとした正規表現Eの意味(解釈)を M(E)とします。M(E)は、アルファベットΣ上の言語(つまり列の集合)となり ます。

  1. a∈Σのとき、M(a) = {"a"}。ここで"a"は、aだけからなる長さ1の列です。
  2. M(EMPTY) = {""}。ここで""は、長さ0の列(空列)です。
  3. M(A, B) = M(A)・M(B)。ここで「・」は、言語の連接演算です。
  4. M(A | B) = M(A)∪M(B)。
  5. M(A*) = {""}∪M(A)∪M(A)2∪M(A)3∪... 。ここでXnは、Xのn回の 連接です。

例えば、(a, (b | c*))の意味(標準的解釈)は次のように計算されます。

M(a, (b | c*))
= M(a)・M(b | c*)
= {"a"}・(M(b)∪M(c*))
= {"a"}・({"b"}∪({""}∪{"c"}∪{"c"}・{"c"}∪...))
= {"a"}・({"b", "", "c", "cc", ...})
= {"ab", "a", "ac", "acc", ...}

3. 正規表現の変種

記事「属性のための正規表現」の第1節で、 正規表現には、いくつかの変種があることを述べました。ここでは、変種をさ らに2つに大別します。

  1. 表現の変種: 通常の正規表現の方言。その正規表現が表す対象(用 途)は変わらない。つまり、語(文字列)や文(語の列)のパターンを記 述します。
  2. 対象の変種: その正規表現が表す対象が、通常の語や文のような1次元的 列ではなくて、他の種類のデータ(のパターン)である。「属性のための 正規表現」で紹介した集合正規表現は、XML属性、レコード(構造体)、 列挙型データ、集合(セット)型コレクションなどのパターンを表現する ための正規表現でした。

この記事で考えたいのは、「対象の変種」のほうです。が、この節で「表現 の変種」に関する注意を述べておきます。その注意とは、表現の変種に関する 同等性とは何か?ということです。(この節のここから後の部分は寄り道の話 題なので、スキップして次の節に進んでもよい。)

いま、正規表現の方言が2つあるとして、それらをA方式の正規表現とB方式の 正規表現としましょう。例えば次のような状況です。

2つの方式は「表現の違いはあっても同等である」場合があります。実際には、 列パターンを表すための正規表現の方言はどれもすべて同等です(そうでない と、正規表現とは呼ばないので)(*注3)。この同等とはどういうことかをハッ キリと述べておきましょう。同等性を定義するには、正規表現が意味するもの (対象)が決まってなくてはなりません。正規表現が意味するものは、その正 規表現にマッチするすべての列からなる集合です。列の集合は“列言語”と呼 ぶので、「正規表現の意味は列言語だ」とも言えます。なお、各種演算子や EMPTYの“意味”は常識に従うとします(常識的意味については、 前節のノートを参照)。

注3

本質的ではないささいな差はありえます。例えば、(空列からなる単元言語 ではなく)空集合を表す定数があるかないかなどです。

さて、「表現の違いはあっても同等である」ことを定義しましょう。それは 次のようなことです。

  1. A方式の正規表現があったとき、B方式の正規表現で意味が同じものを常に 構成できる。
  2. B方式の正規表現があったとき、A方式の正規表現で意味が同じものを常に 構成できる。

「意味が同じ表現の構成」を系統的に行うために翻訳手順があると便利です。 翻訳手順があるとは次のようなことです。

  1. A方式の正規表現が与えられると、ある手順でB方式の正規表現を作り出せ る。できたB方式の表現は、もとのA方式の表現と同じ意味である。
  2. B方式の正規表現が与えられると、ある手順でA方式の正規表現を作り出せ る。できたA方式の表現は、もとのA方式の表現と同じ意味である。

興味があるかたは、先に例として挙げた2つの方式に関して相互翻訳を具体的 に定義してみてください。つまり、次のような手順を与えてみてください。

  1. 演算子「,」、「| 」、「*」、「?」と定数EMPTYを含む正規表現から、同 じ意味で、演算子「,」、「| 」、「+」と定数EMPTYを含む正規表現を作 り出す手順。
  2. 演算子「,」、「| 」、「+」と定数EMPTYを含む正規表現から、同じ意味 で、演算子「,」、「| 」、「*」、「?」と定数EMPTYを含む正規表現を作 り出す手順。

「『形式的』とは何だろう」の第4節の項の 定義のように、正規表現を帰納的(inductive)に定義しないと、翻訳の定義 もうまくいきませんよ(翻訳も帰納的に定義します)。

4. 一般的正規性を求めて

ここからが、この記事の本論です。つまり、正規表現の「表現の変種」ではなく て、「対象の変種」について考えていきましょう。

通常の列言語とは違った対象を扱う正規表現の一例を記事 「属性のための正規表現」に示しました。ほん の少し復習しましょう -- 基本記号の集合として{a, b, c}を採ったとき、 "aa"や"ccbba"は基本記号から成る‘列’です。それに対して、{a}や{a, b, c}は基本記号から成る‘集合’です。列の集合(例:{"aa", "ccbba"})を ‘列言語’と呼ぶので、同様な理由で集合の集合(例:{{a}, {a, b, c}})は ‘集合言語’と呼んでいいでしょう(*注4)

注4

形式言語理論における言語とは、単に(構文的対象と思えるナニカの)集合 に過ぎません。それ以上でも以下でもないのです。「言語」という言葉に対し て、人によっては強い先入観やら見識やらをお持ちだろうから、この乾いた (感情を含まないサッパリし過ぎた)定義には違和感を抱くでしょう。しかし、 余計な“思い”をはぎ取った定義のほうが議論をスムーズに運びやすいという メリットは確かにあるのです。

列と集合は性質が異なるデータなので、列言語と集合言語も違った性質を持 ちます。例えば、基本記号が{a, b, c}の3個でも無限個のメンバーを持つ列言 語はあります(例:{"a", "aa", "aaa", ...})が、無限個のメンバーを持つ 集合言語は存在しません。また、列言語に対してなら意味のある連接演算は、集合言語 には存在しません(代わりとなる集合演算を「&」で表しました、 詳細は「属性のための正規表現」第6節)。

世の中にはさまざまなデータ構造があります。列(リスト)、集合(列挙)、 バッグ(マルチセット)は典型的なコレクション・データ構造です。これらに 対する正規表現を考えられます。列正規表現は普通の正規表現です。集合正規 表現は「属性のための正規表現」で定義しました。バッグ正規表現は 宿題ですが、たぶん定義できるでしょう。 他に、ツリー正規表現やヘッジ正規表現も既に誰かが(複数の方式で)定義し ているでしょう。レコード正規表現やグラフ正規表現はどうでしょうか? こ れも探せばあるかもしれませんね。列というデータ構造に対して'列'言語、 '列'正規表現、'列'正規言語(正規表現により定義される言語)という概念が定義で きたのと同じように、データ構造××に対して、××言語、××正規表現、×× 正規言語が定義できるのかもしれません。

前段落で「かもしれません」と曖昧な言い方をしたのは理由があります。例 えば、どこかの誰かが新しいデータ構造△□◎に対して「△□◎正規表現/正規言語を定 義した」と主張したとき、我々は彼/彼女の主張を評価判断する確たる手段を 持ってません。つまり、正規表現/正規言語と呼んでもよい資格基準 がこれといってありません。ですから、「××言語、××正規表現、××正規 言語が定義できる」という命題が正しいとも正しくないとも断言できないのです。

列に限らずに、いろいろなデータ構造(の集合)に対して正規性 (regularity)を考えたいなら、列を越えてもっと一般的に通用する「正規」 概念を確立する必要があります。

5. 絶対的正規性ではなくて相対的正規性

前節は僕の問題意識の説明になっています。が、誤解されそうな気もするの で、この節で補足をします。

僕が欲しいものは「正規性の一般論」です。それは事実です。が、「正規性 の一般論」が欲しいというのは、何か天上の存在としての「聖なる正規性」を 求めることではありません。むしろ正反対であり、現実的な状況に応じてどう にでもカスタマイズできる道具として、正規性の概念を準備したいのです。

重要な論点だから、言葉を換えて言いましょう。「正規性」を、天上の存在 としての聖なる正規性と解釈してしまうと、それを探す行為は実にナンセンス だと思います。考えてもしょうがない、あるいは、考えるにあたいしない問題 です。絶対的な正規性なるものが先験的/一意的に存在するような事態は考え にくい、信じがたいわけですよ、僕の感覚では。

「正規性とは何であるか」を求道者のごとく追い求める態度ではなく、「正 規性を定義したいと思ったとき、その場その場で便利に使える道具立ては何で あるか、どんなものがあるか」という問(とい)の立て方をします。そうする と、「その場の状況に応じて」という要件が非常に重要になってきます。そし て、「その場の状況」が定義のなかにパラメータとして入り込んでくるので、 正規性の定義は必然的に(状況に対して)相対的なものになるのです。

どうして僕がこの節で「先験的/一意的な正規性などない」と注意したかと いうと、列言語に関していえば、正規言語という概念はどうも神様が造ったよ うに見えるからです。どのようなアプローチをしても、同一の正規性概念にた どりつくので、これは人為的なものではなくて、天上におわします聖なる正規 性の“あらわれ”のように思えるのですね。それが真実であれ幻想であれ、こ の絶対性は列言語に特有な現象だろう、というのが僕の観察です。つまり、他 のデータ構造に関して列のときと同様な予定調和の世界を期待すべきではない、 と警告したいのです。

6. 繰り返し演算から再帰的定義へ

能書きはこれくらいにして、実際に「相対的正規性」を定義する道具立ての 話をしましょう。端的に言ってしまえば、 記事「再帰代入系 1」で導入した 再帰代入系が、正規性を定義するための道具/枠組みです。

冒頭で「再帰代入系 1 and 2」は読んでなくてもよいと言ったので、これか らその概要を説明しながら進みます。読んでいるかたも退屈しないように、正 規性の視点から語りましょう。

列の正規表現/正規言語の場合を反省することからはじめます -- 列の正規 表現で特徴的なのは、繰り返しを表す演算「*」の存在でしょう。「*」以外の 操作は、有限集合から有限集合を作り出すことしかできません。無限個のメン バーを持つ言語を生み出す力は「*」に集約されています(*注5)。しかし、こ の“力”は、必ずしも単項演算子の形をしてなくてもよいのです。

注5

A+は、(A, A*)なので、「+」は「*」の派生物です。あるいは、「+」を ベースにすれば、「*」は「+」の派生物です。

たとえば、元祖BNF記法では、定義(生成規則の右辺)に使える演算子は、連 接(「,」演算子)と選択(「|」演算子)だけです(*注6)。x ::= (a, b*, c?) と定義したいなら、次のような生成規則を書けば、「*」や「?」の代用に なります。

 x ::= a, u, v
 u ::= EMPTY | b, u
 v ::= EMPTY | c

注6

我々が普通BNFと呼んでいる記法は、拡張BNFです。

ここで特に「u ::= EMPTY | b, u」に注目してください。生成規則の左辺にも 右辺にも変数uが出てきています。「自分(u)を定義するために自分自身(u) を使う」という状況が生じてますね。これが再帰(recursion)です。

つまり、再帰的定義を許せば、無限生成を表す演算子がなくても同等な定義 を書き下せます。もちろんこれは、「*」のような無限生成の演算子を禁止す ることではありません。無限生成の力を単一の(あるいは数個の)演算子とし て抽出しにくいときは、無理に演算子を定義しなくてもよいということです。

7. 再帰代入系への道

さて、上に例として出したBNF生成規則の右辺を、関数呼び出し形式に書き換 えてみます。第2節を思い起こしてくださいね。

 x ::= concat(a, u, v)
 u ::= choice(empty, concat(b, u))
 v ::= choice(empty, c)

BNFでは伝統的に記号「::=」を使いますが、記号の選択は趣味の問題なので、 より短い「=」に置き換えれば、生成規則群は等式系(system of equations) とみなせます(*注7)。(任意の等式というわけではなく、「左辺は変数だけ」 という制限を受けます。)

 x = concat(a, u, v)
 u = choice(empty, concat(b, u))
 v = choice(empty, c)

注7

記号は趣味の問題だから「::=」から「=」に替えたら、ほら等式系でしょう、 という議論は乱暴というか、ヒドいものですが、今はこれでかんべんしてくだ さい。

等式系に出現する変数は、x、u、vの3つですが、uとvは後から導入した作業 用の一時変数ですから、xとは区別されます。u、vをt1、t2に置き換えた次の 等式系でも結局は、xを(a, b*, c?)と定義できます。

 x = concat(a, t1, t2)
 t1 = choice(empty, concat(b, t1))
 t2 = choice(empty, c)

今まで、a、b、cは定数のように扱ってきました。たぶん、aは'a'という文字 そのものと思ったいたかもしれません(それでよかったのですよ)。しかし、 これらが定数である必然性もありません。そこで、a、b、cは外部から値が与 えられる変数だとみなしましょう。つまり、a、b、cは入力パラメータです。

結果として我々のBNF定義は、入力パラメータa、b、cと出力パラメータxを持 つ等式系となりました。この事情をハッキリと示すために、次のように書いて みましょう。

 input: a, b, c;
 output: x;
 working: u, v;

   x = concat(a, u, v)
   u = choice(empty, concat(b, u))
   v = choice(empty, c)

こうすると、等式系は、入出力を備えた一種の計算装置(プロセッサ)とみ なせます。では、どんな値に対してどんな計算をする装置なのでしょうか。

もともとが言語の記述・定義から出発したので、計算する値は数値ではなくて言語 です。言語とは列の集合でした。つまり、この計算装置は、入力変数(この事 例ではa、b、c)に実際の集合を割り当てて走らせると、出力変数(この事例 ではx)に結果集合を返して終了するのです(*注8)。計算の途中では作業変数u、 vを使いますが、これは計算装置にプライベートなもので利用者(外部)から 見える必要はありません。ですから、利用者に迷惑をかけることなく、作業変 数の取り替え、たとえば{u, v}→{t1, t2}を行ってもかまいません。

注8

実際には終了しないかもしれません。なぜなら、再帰方程式を解くには無限 回の繰り返し計算が必要になるかもしれないからです。しかし、無限回の計算 も有限時間内に終わるといフィクションを導入することにより、議論がスッキ リすることもあります。

実は、これまでの説明で再帰代入系のエッセンシャルな部分はだいたい登場 してます。上の例のような、再帰方程式系(BNF生成規則群と同等)に、入力 (input)、出力(output)、作業用(working)の変数の宣言を付け加えたも のが‘再帰代入系’に他なりません。

ここまで読んだかたは、 記事「再帰代入系 1」の第5節、 第6節記事「再帰代入系 2」の第5節 などを読んでも、それほど唐突な印象を抱かないと思います。“形式的”な 雰囲気に慣れるために「『形式的』とは何だろう」 にも目を通しながら進むなら、「再帰代入系 1」と「再帰代入系 2」の第一部 までは読み通せるのではないかと思います(無理に読まなくていいですけど)。

8. XMLの事例

ここらでXMLに関連した事例を出しましょう。この事例により、次のようなこ とを示したいと思います。

  1. 正規性の概念が列以外にも定義可能なこと
  2. 再帰的定義が無限個のメンバーを生成可能なこと
  3. 入力パラメータの使い方

XMLの事例とは言っても、オモチャのXMLを使います。僕が以前雑誌で紹介し たことがあるTiny Toy XMLで考えます。Tiny Toy XMLでは、属性のない(名前 だけを持つ)要素しか考えません。テキスト(文字データ)さえも存在しませ ん。

Tiny Toy XMLのデータは3つの型(タイプ)を持ちます。雑誌記事にあわせて、 3つのデータ型を、Name, List, Treeとします(*注9)。データが型を持つの で、変数や関数も型(引数の型と戻り値の型)を持ちます。定数/関数の型を、 プログラミング言語の宣言のように書いてみれば、次の通り。

注9

List, TreeよりSequence, ElementのほうがXMLらしい、というご指摘はごもっ ともです。が、たしか雑誌のほうでは、データ構造の流れで話をしたので List, Treeにしたような記憶があります。

いくつかの注意をしておきます。

  1. Name, List, Treeという型は、実はインスタンスの型ではありません。イ ンスタンス集合(言語)に対する型です。ですから、正確に言えば、たと えばconcatという関数は「リスト(列)の集合を2つ引数に取り、リストの 集合を返す」のです。
  2. 変数と区別するため名前(タグ名)のリテラルは、'foo' のように引用符 でくくります。リテラル'foo'の実際の意味は、'foo'だけからなる集合 {'foo'}です。
  3. choice関数はオーバロードされています。つまり、同じ名前でも引数型に より働く領域が異なります。1つはリスト集合(列言語)の合併で、もう1 つはツリー集合(ツリー言語)の合併に対応します。
  4. ご希望なら、concatとchoiceを、2引数以上の多引数に対して定義しても かまいません。
  5. 最後に挙げられている関数surroundは、名前とリストから、「その名前を タグ名として、そのリストを要素とするツリー(Tiny Toy XML要素)」を 作る関数です。
  6. TreeからListに暗黙の型変換が働くとします。つまり、自動的に、ツリー (の集合)は長さが1のリスト(の集合)とみなすことにします。

さて、では実際の再帰代入系を出しましょう。等式(生成規則)のお尻にセ ミコロンが付いているのは、全体の雰囲気をプログラミング言語風にするため で、他意はありません。

 input: /* なし */;
 output: Tree y;
 working: Tree e, x;

   y = x;
   e = surround('a', empty);
   x = choice(e, surround('a', x));

eとxの定義は、おそらく次のように書いたほうがわかりやすいでしょう。

 e = <a/>;
 x = e | <a>x</a>;

さらに、次のようにeを消去してしまった方がより見やすいかもしれません。

 x = <a/> | <a>x</a>;

この再帰的定義(再帰方程式、不動点方程式)から、xの意味となるツリー集 合がどんなものか予測はできると思います。次のような集合です。

{
<a/>, <a><a/></a>, <a><a><a/></a></a>,
<a><a><a><a/></a></a></a>, <a><a><a><a><a/></a></a></a></a>,
...
}

先の再帰的定義は、無限個のメンバーを持つツリー集合を生成してますが、 それはリスト(列)の繰り返し連接とはちょっと違います。要素の入れ子操作 に対して繰り返しを行っていますね。入れ子操作の繰り返しを、1つの演算子 で表すこともできますが、そうしてもあまり有意義とは思えません。むしろ、 いちいち演算子を定義しなくても、無限生成能力を利用できるところが再帰的 定義のいいところです。

今の例は、empty、concat、choice(オーバロード)、surroundをベースにし た再帰代入系でしたが、他の関数集合をベースにしてもかまいません。また、 Name, List, Treeからなる型システムも、他の型システムに置き換えてもかま いません。再帰代入系という大枠に従って定義した言語/集合はなんであれ、 正規言語/正規集合と呼んでしまおう、というのが我々の「正規性」概念 の定式化なのです。

さてここで、もうひとつの例を出しましょう。

 input: Name a; List t;
 output: Tree y;
 working: Tree e, x;

   y = x;
   e = surround(a, t);
   x = choice(e, surround(a, concat(t, x)));

xの定義を簡便で分かりやすい形に書けば:

 x = <a>t</a> | <a>t x</a>;

ただし、今度はaもtも変数です。しかしそれでも(変数を含んだままでも)、 xの意味となるツリー集合を予測できます -- やってみてください。そのとき、 「<a>t<a>t</a></a>」のように書いた“インスタンス”は、実はほんとのイン スタンスではなくて、インスタンス・パターンですね。なぜなら、aとtは変数 (プレイスホルダー)ですから。

この記事では深入りしませんが、入力パラメータ(今回の例ではaとt)を持 つ正規代入系において、入力パラメータを具体化してから(方程式系としての) 解を求めても、入力パラメータを具体化しないまま作ったインスタンス・パター ン集合を後から具体化しても結果は変わりません。これは、call-by-value式 の実評価と、具体化を任意に遅延した記号的評価に本質的差がないことです。

NOTE: デザインパターンを形式化できるかも

僕は、「XMLボキャブラリ のデザイン・パターン」という記事を書いたことがあります。そのなかで、 説明のためのインフォーマルな記法として、次のような書式を用いました。

  <Document>
    <!-- Content: (Head, Body) --> 
  </Document>

このなかで、Document、Head、Bodyなどはプレイスホルダーです。Headと Bodyは何らかの要素を表す変数と考えられますね。そして、Documentは任意の タグ名と任意の属性並びに具体化できる変数と考えられます。

インフォーマルとは言いましたが、上のような表現は、構文的な型により型 付けされた構文的な変数を含む項(term)として解釈できるだろうと考えてい ます。もっとも、デザインパターンのキモは、その考え方や運用指針ですから、 デザインパターンの総体を形式化できるとは毛頭考えてません(ノートの見出 しはキャッチィ目的)。形式化できそうなのはパターンの構文記述です。

9. ウルトラ・マクロな立場

再帰代入系(の枠組み)が、列にも集合にも、XMLのようなツリー構造にも適 用できることを、雰囲気としては感じてもらえたでしょうか。再帰代入系の定 式化では、なにか1つの再帰代入系を考えるのではなくて、あらゆる再帰代入 系を全部一度に考えて、それら全体が作る社会(あるいは世界)のマクロ構造 を探ります。

再帰代入系において使える関数記号と変数記号(の全体)を固定しても、非 常に多くの再帰代入系が考えられます。関数記号の集合をF、変数記号の全体 集合Kとして、それから作られる再帰代入系の全体をRAS(F, K)と書くと、この RAS(F, K)は十分に大きな世界です。しかし、我々(って、いまのところ僕一 人)の立場は、FとKを固定するのではなくて、FとKも動かして考えます。つま り、FとKをあらゆる可能性に渡って動かしたときの、「世界全体の世界」 の構造が問題になります。

そんな大げさなことをする必要があるのか? あります。僕は、 記事「再帰代入系 2」の第8節 で次のように書きました。

意味論中立で構文(外部表現)中立だと何がうれしいかというと、非本質的 で不毛な議論やら作業やらから逃れることができる。どうでもいい煩雑さ に心底ウンザリ!している僕にとっては、これは実に素晴らしい特徴なの だ。

「世界全体の世界」を考えるウルトラ・マクロな立場では、それが合理的で ある限り、あらゆる構文、メタ構文、対象領域が許されます。どんな特殊特定 的な存在も、全体のなかで位置付けられます。つまり、極度に寛容な立場なの です。

「AとB、どちらが良いか決定する」必要は確かにあります。が、それに先ん じてAとBを比較する方法がないと何も正確な議論はできないでしょう。比較す るためには、A、Bそれぞれを全体のなかで位置付けなくてはなりません。つま りは全体という場、あるいは環境が必要です。マクロな立場における「世界」、 ウルトラ・マクロな立場における「世界全体の世界」は、そのような場・環境 を提供するはずです。

とかいうと、思想信条が混じった言い分に聞こえてしまいそうですが、そう いうことではありません。相対的正規性のまっとうな定式化にしろ、構文定義 のモジュール化/モジュール操作にしろ、結局はマクロ、またはウルトラ・マ クロな立場でしか遂行できそうにないのです。僕は、思想信条も政治的態度も すべて排除して、実利的(ただし、ロングタームの利益の)観点から考えてい るつもりです。