檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
ところで、アーカイブってけっこう便利ですよ。タクソノミーも作成中。

2010-09-08 (水)

こんな簡単なトレース付きモノイド圏があったなんて

| 09:26 | こんな簡単なトレース付きモノイド圏があったなんて - 檜山正幸のキマイラ飼育記 を含むブックマーク

「こんな簡単な×××があったなんて」というタイトル、けっこう人目を惹きそうでしょ。でも「×××」が「トレース付きモノイド圏」じゃねぇー、誰も集まってこないわな。まーいいや。

内容:

  1. GoI構成とInt構成
  2. 自然数の基本的な性質
  3. 自然数の順序から作る圏
  4. 自然数の足し算から作るモノイド圏
  5. 引き算で作る対称モノイド圏上のトレース

GoI構成とInt構成

GoI(Geometry of Interaction)なんてことを言い出したのは、線形論理の創始者ジラール(J.-Y. Girard)だと思います。GoI構成とは、トレース付きモノイド圏からコンパクト閉圏を作り出す操作です。GoI構成は別名Int構成とも呼びます。ジラールとは独立に同じ方法が発見され、Int構成と名付けられたのだと思います。Int構成の起源が誰なのかは知りません*1

GoIは"Geometry of Interaction"の略記ですが、Intの語源はなんでしょう? Integer -- 整数です。自然数から整数を構成するのと同じ方法なのでInt構成と呼ぶのですね。つまり、自然数はトレース付きモノイド圏で、整数はコンパクト閉圏なんです。

一度に説明するのは大変なので、まず今日は自然数の全体 {0, 1, 2, 3, ...} がトレース付きモノイド圏となることを説明します。正確に言えば、{0, 1, 2, 3, ...} は圏の対象集合で、{0, 1, 2, 3, ...}×{0, 1, 2, 3, ...} の一部が射の集合となります。

自然数の基本的な性質

これから考える数は自然数(0を含める)だけです。記号「≦」は大小関係、記号「+」は足し算、記号「-」は引き算を表すとします。自然数に関する法則を以下に列挙します。法則の仮定を横棒の上に、結論を横棒の下に書きます。

    (仮定なし)
  ---------------[1:反射律]
     a ≦ a


   a≦b   b≦c
  ---------------[2:推移律]
      a≦c


   a≦b   c≦d
  ---------------[3:足し算]
   a+c ≦ b+d


   x+a ≦ x+b
  ---------------[4:引き算]
     a ≦ b

最後の法則を「引き算(の法則)」と呼んでいるのは、a' = x+a, b' = x+b と置くと次の形に書けるからです。

      a' ≦ b'
  ------------------[4:引き算']
  a' - x ≦ b' - x

これらの法則を見れば、自然数がトレース付きモノイド圏となることはわかるでしょう -- ってのは気が早過ぎですね。順番に見ていきましょう。

自然数の順序から作る圏

a, b を自然数だとして、a≦b であるペア [a, b] を射とする圏を考えます。[a≦b] と書くと事情がハッキリするので、射はこの記法で書くことにします。圏としての自然数をNaC(natural numbers as a category)として、圏の定義をちゃんと述べておきます。

  1. 対象の集合 Ob(NaC) = |NaC| は、{0, 1, 2, ...} である。
  2. 射の集合 Mor(NaC) は [a≦b] というペアの全体。
  3. dom([a≦b]) = a, cod([a≦b]) = b
  4. id(a) = [a≦a]
  5. [a≦b];[b≦c] = [a≦c]

以上に定義した構造が圏であるためには、f = [a≦b], g = [b≦c], h = [c≦d], ida = [a≦a] などとして、次が成立する必要があります。

  1. (f;g);h = f;(g;h)
  2. ida;f = f;idb = f

恒等射 ida = id(a) や結合「;」がちゃんと定義される(well-definedな)ことや、「;」の結合律と単位律は、先の自然数の基本的性質から簡単に導けますね。

自然数の足し算から作るモノイド圏

圏NaCに足し算を考えます。対象のあいだの足し算は普通の自然数の足し算そのものです。射の足し算は次のように定義します。

  • [a≦b] + [c≦d] = [a+c ≦ b+d]

対象と射が混じった足し算も次のように定義しておくと便利です。

  • a + [b≦c] = [a≦a] + [b≦c] = [a+b ≦ a+c]
  • [a≦b] + c = [a≦b] + [c≦c] = [a+c ≦ b+c]

x, y, z は対象でも射でもどっちでもいいとして:

  1. (x + y) + z = x + (y + z)
  2. 0 + x = x + 0 = x

f, g, h, kを射、a, bを対象として:

  1. (f + g);(h + k) = (f;h) + (g;k)
  2. ida+b = ida + idb

これらも、自然数の基本的性質からすぐに出ます。つまり、NaCに足し算「+」と足し算の単位「0」を一緒に考えると、モノイド圏となります。足し算は可換なので、より詳しくは対称モノイド圏です。[a+b ≦ b+a], [b+a ≦ a+b] が、a+b と b+a の同型(対称性)を与える射です。

引き算で作る対称モノイド圏上のトレース

まだ使ってない自然数の基本的性質は、引き算の法則です。[x+a ≦ x+b] のとき、「≦」の両側からxを引いてもいい、という法則です。この引き算は、対称モノイド圏NaCの上のトレースを定義します。

トレースってなんだ? その定義(むしろ雰囲気)は、「やっぱりこれからはフローチャートだな」で紹介した長谷川真人(はせがわ・まさひと)さんによる「再帰プログラムの意味論について」(PDF)の3.2節、特に9ページの絵を眺めてもらえるといいと思います。

自然数のひき算により定義されるトレースが、トレースの公理を満たしていることのヒントを並べておきます。Trx([x+a ≦ x+b]) = [a≦b] とします。

  1. 単位バニッシング:Tr0([0+a ≦ 0+b]) = [a≦b]
  2. 足し算バニッシング:Try(Trx([x + y + a ≦ x + y + b])) = Trx+y([x + y + a ≦ x + y + b])
  3. 左タイトニング:Trx([x+a ≦ x+b];[x+b ≦ x+c]) = [a≦b];Trx([x+b ≦ x+c])
  4. 右タイトニング:Trx([x+a ≦ x+b];[x+b ≦ x+c]) = Trx([x+a ≦ x+b]);[b≦c]
  5. スライディング:Trx([x+a ≦ x+b];[x+b ≦ x+b]) = Trx([x+a ≦ x+a];[x+a ≦ x+b])
  6. ヤンキング:Tra([a+a ≦ a+a]) = [a≦a] = ida
  7. スーパーポージング(強度性):Trx([x+a+c ≦ x+b+c]) = Trx([x+a ≦ x+b]) + c

トレース付きモノイド圏の典型例は、通りぬけ可能な紐が作る“組み紐の圏”でしょう。紐が互いに通りぬけ可能と仮定すると、もはや組み紐(ブレイド)と呼ぶのは不適切で、やっぱりアミダの圏かな。なんにしろ紐なんです。それと、再帰プログラムや正規表現のモデルもトレース付きモノイド圏です。自然数の順序と足し算から作るトレース付きモノイド圏は、おそらく(非自明な)一番簡単な例だろうと思います。

*1:ジョイアル/ストリート/ヴェリティ(Andre Joyal, Ross Street, Dominic Verity)の "Traced monoidal categories" (1996) じゃなかろうかと思いますが、見たことないので確証はありません。

トラックバック - http://d.hatena.ne.jp/m-hiyama/20100908

2010-09-07 (火)

今朝言われたこと

| 18:20 | 今朝言われたこと - 檜山正幸のキマイラ飼育記 を含むブックマーク

はー疲れた、今日はもう帰ろう。

で、今ふと思い出した。今朝、長男に言われた。

長男:「おとうさん、半ズボンとサンダルはやめなよ。もう大人なんだから」

着替えてから帰るべきか。

トラックバック - http://d.hatena.ne.jp/m-hiyama/20100907

2010-09-06 (月)

いまさらにHTTP通信とCOMET通信、そして双対性

| 09:18 | いまさらにHTTP通信とCOMET通信、そして双対性 - 檜山正幸のキマイラ飼育記 を含むブックマーク

準備というか伏線というか、このハナシしておかないとな -- というわけで。


一時期、COMETに飛びついた人は多いですよね。僕もその一人です。やってみた感想は、「これはやっぱりHTTPの裏技で、まっとうじゃないな」。まっとうじゃなくても、この技術を使わざるを得ないようなキラーアプリがあれば話が別なんですが、それも思いつかないし。

そんなわけで、COMET熱は冷めちゃったわけですが、今でも「COMETが出現して良かったな」と思うことはあります。それは、逆向きのHTTP通信に名前を与えたことです -- COMET通信ですね。

HTTPの場合、クライアントとサーバーが通信をするとき、事前の準備は特に必要ありません。COMETの場合、COMET通信の片方のエンド(=HTTPクライアント)が先にHTTPリクエストを送って通信チャンネルを開設しておく必要があります。これをイニシエーションと呼んでおきましょう。通常のHTTPの場合は、何もしないことがイニシエーションだと考えれば、通常のHTTP通信もCOMET通信も、「イニシエーションにより通信路が確立される」としてよいでしょう。

イニシエーションが終われば、通信の両端のあいだでデータのやり取りが出来るようになります。このとき、HTTP通信(通常のHTTP)とCOMET通信では、クライアントとサーバーの役割が逆転します。「COMETサーバー」という言葉は、COMETをサポートしたHTTPサーバーの意味で使われることが多いですが、ここではクライアント-サーバー・モデルでの役割を表して「COMETサーバー」「COMETクライアント」という言葉を使うことにします。

すると、次のような対応があります。

HTTP通信 COMET通信
HTTPクライアント COMETサーバー
HTTPサーバー COMETクライアント
HTTPリクエスト COMETレスポンス
HTTPレスポンス COMETリクエスト

実際は、HTTP上でP2Pモドキを実現したいときにCOMETが使われるので、クライアントとサーバーの区別を意識しないことが多いでしょうが、ここでは「役割の逆転」を強調します。

HTTPクライアント(=COMETサーバー)がブラウザのケースで説明しましょう; COMETイニシエーション手順として、ブラウザがHTTPサーバーにHTTPリクエストをすると、HTTPサーバー(=COMETクライアント)は、受け取ったHTTPリクエストを握ったままにします。これでCOMET通信路が確立するのです。

COMETクライアント(HTTPサーバー)がブラウザ(=COMETサーバー=HTTPクライアント)に何かの連絡や依頼をしたいことがあると、握っていたHTTPリクエストを手放してHTTPレスポンスを返します。このHTTPレスポンスが、COMETの意味ではリクエストとなるのです。ブラウザ(=COMETサーバー=HTTPクライアント)はCOMETリクエスト(HTTPレスポンス)を解釈して、COMETクライアント(=HTTPサーバー)にCOMETレスポンス(次のHTTPリクエスト)を返す(送る)のです。

何もかにもが逆転します。本来HTTPは可逆(リバーシブル)に設計されてないので「何もかにも逆転」することは不自然で無理があります。そこに技術としてのCOMETの弱点があります。

しかし、HTTPの不可逆なところを捨象してしまって、「まー、だいたい可逆だろう」とオオザッパに考えてみると、HTTP通信とCOMET通信はお互いが鏡像のような関係になります。「クライアント ←→ サーバー」「リクエスト ←→ レスポンス」という役割が入れ替わります。現実のプロトコルは通常のHTTPだけですが、そのプロトコルの使い方や両端の役割が、通常のHTTPとCOMETではひっくり返るのです。

別な言い方をすると、HTTP(通常のHTTP通信)とCOMET(逆HTTP通信)は双対です。これは比喩や言葉の流用ではありません。厳密な意味で双対です。では、いかなる解釈と文脈のなかで「厳密に双対」なのでしょうか? コンパクト閉圏(compact closed category)の双対性です -- 「それってなに?」 … そのうち語る機会もあるでしょう、今日はここまで。

トラックバック - http://d.hatena.ne.jp/m-hiyama/20100906

2010-09-03 (金)

状態遷移指向Webサービス設計の課題:可視化したってダメみたい

| 12:17 | 状態遷移指向Webサービス設計の課題:可視化したってダメみたい - 檜山正幸のキマイラ飼育記 を含むブックマーク

最近の記事群で、「クライアント側の状態遷移を中心にしてWebサービスの設計をしたらいいよ」と僕は言っているわけで、実践もしているのですが、まー課題もありますね。

もともと僕は、ハイパーリンクのグラフ構造を正確かつ完全に把握したいという強い要求・願望を持っていました。その1つの方法を提案したのが次の記事です。

少し長くなりますが、上の記事の最後を引用します。

一旦有向グラフが出来てしまえば、ノード間の可達性、ハブノードの存在、ノード間の経路距離などを判定/算出できます。入次数/出次数(in-degree/out-degree)などから何か計量的な指標が得られるかも知れません。特定のノード(Webコンテンツ)から距離nの近傍(距離がn以内のノードの集まり)を観察したり、可能な経路をすべて列挙してみることで、サイトに関する知見が得られるかも知れません。

「知れません」と書いたのは、実際にやってみないと有効性が分からないからです。もちろん、僕は有効だろうと思ってますがね。URLが、対応表を引くキーとかプログラムを起動するトリガーだったりすると、サイト内全コンテツを列挙して静的解析を遂行するのはかなり困難だと思います。「静的サイトと同じ作りにする」に拘っているCatyだから実行可能なタスクだと思えるので、やってみる価値はあります。

この当時僕が想定していた方法は、HTMLファイルを解析してハイパーリンクを取り出して、それをもとに有向グラフを描くという方法です。それができる前提は、「URLの書き換えやマッピングは一切しない」ことです。しかし、この前提は崩れてきているので、ファイルシステムをスキャンしてグラフを描く方法は使えない場面が増えています。

であるなら、ハイパーリンク(=クライアント側の状態遷移)を記述するデータを別に持てばいいだろう、と。それをもとにグラフを描けるでしょう、と。そこで「Webサービスを設計するための単純明快な方法」が登場するわけです。これは方法だけで、ツールは存在しません。その点は気にしています。

今述べたことを実践するには、ある程度の指針や方法が必要です。そこで、僕自身が使っているやり方を紹介します。あまり完成度は高くないし、現状ではサポートツールもないのですが、単純明快なのがメリットです。


現状、このような発想や方法を支援するツールが何も無いのがつらいところです。が、定式化がシッカリすれば、ソフトウェアによるサポートが特別困難だとは思っていません。

仮に、なんらかの「ハイパーリンク(=クライアント側の状態遷移)を記述するデータ」が定義できて、それをもとに有向グラフが描けたとします。果たしてそれでいいのでしょうか? 僕は最初「それでいい」と思っていました。

なにはともあれ、ハイパーリンクの全貌が目視で確認できたら、それは気持ちいいでしょう。精神衛生上は非常にヨロシイ。ですが、そのハイパーリンク -- グラフ構造ですが、それが正しいのを目視で確認するのは容易じゃないです。例えば、ノードが100個ある有向グラフを見せられて、「これは正しい?」と聞かれても答えられません。

事情は型システムと同じです。目の前に出されたデータが、型の制約を満たしているかを人間が目視で判断していたらやってられない。だから型システムがあるわけです。型はスキーマで定義され、バリデータでチェックされます。同様に、“ハイパー型”が“ハイパースキーマ”で定義され、“ハイパーバリデータ”でチェックされないとやってられない。

「ハイパー型システムが必要だなー、欲しいなー」と、僕は切実に思っています。

「ハイパーリンクはホントウに難しい」より引用:

ハイパーオブジェクトとトリガーという概念は、単なる雰囲気や比喩としてだけ語っていてはダメなんです。ソフトウェアにも人間にも明白に分かる記述が必要です。

おおよその枠組みは「Webサービスの設計: Webフローの図示法を再考する」で触れたようなモノでいいだろう、とは思っています。とはいえ、おおよその枠組みを考えるのと、細部を詰めるのは別な作業なので、試行錯誤の日々が続くでしょう。しゃーない。

2010-09-02 (木)

Webサービスの設計: Webフローの図示法を再考する

| 15:05 | Webサービスの設計: Webフローの図示法を再考する - 檜山正幸のキマイラ飼育記 を含むブックマーク

「Webサービスを設計するための単純明快な方法」「Webサービスの設計:Webの状態遷移図の描き方」で、Webにおける状態遷移の図を示しました。もう少し図の描き方について考えます。そして、それらの図がいったい何を意味するかにも触れます。

内容:

  1. アクション、ハイパーオブジェクト=状態、モジュール=サブシステム
  2. モジュールの図示
  3. いいことありそうだ

アクション、ハイパーオブジェクト=状態、モジュール=サブシステム

まず図の描き方の復習をしましょう。サーバー側の処理であるアクションは小さめの黒丸で表します。アクションのレスポンスとして返されるハイパーオブジェクトは大きめの白丸です。ハイパーオブジェクトはクライアント側の状態と解釈され、リクエストを発行するボタンであるトリガーを持ちます(トリガーが必須ではありませんが)。

いくつかのアクションとハイパーオブジェクト(=状態)のノード達は互いに繋がれて、メッセージングと状態遷移のフローを形成します。ノードを辺で繋ぐときには、リクエスト辺はリクエスト辺と、レスポンス辺はレスポンス辺と繋ぎます。もちろん、辺の方向も合わせないとダメです。実際には、リクエストもレスポンスもデータ型(メディアタイプとスキーマで定義される)を持ちますから、データ型も一致しないと繋げません。でも煩雑になるので、今回はデータ型はいちいち明示しません。

一群のノードと有向辺は有向グラフを作りますが、これらをひとまとまりのモノとして把握するために、四角い枠線で囲みます。そうやって作られた四角をとりあえずモジュールと呼ぶことにします。モジュールは、Webサービス・システムの一部分、つまりサブシステムを構成することになります。次の図はモジュールの例です。「ログイン成功したらマイページを表示する」のような流れを想定しています。

モジュールの図示

モジュールには、たいていリクエストかレスポンス(あるいは両方)が入り込みます。また、リクエストかレスポンスが出て行くことになります*1。要するに入り口と出口があるよ、ってことです。そこで「入り口 → 出口」をどういう方向で描くかって大問題が発生します。なんだかんだと悩みたくないので、方向は上から下、上が入り口、下が出口と決めます。断固決めます。

一番簡単なモジュールは、アクションかハイパーオブジェクト(状態)を1個だけ含むものでしょう。それらの中身を描いている時(図の上のほう)はいいのですが、中身を隠してしまう(図の下のほう)とちょっとした問題があります。

グラフの有向辺がリクエストかレスポンスか区別が付かないのです。ヨクワカラン図ですね。もっと大きなモジュールでも同じ問題が起きます(そして図が大きいとより深刻です)。点線を使うとか辺に色を付けるとかの方法もありますが、実際に描いてみるとメンドクサイ! そこで次の対策をします。

  • メッセージの入り口である四角形上部を左右に分けて、左をリクエストの入り口、右をレスポンスの入り口とする。
  • メッセージの出口である四角形下部を左右に分けて、左をレスポンスの出口、右をリクエストの出口とする。

念のために、リクエストとレスポンスを識別するマークも決めておきます、リクエストはR、…… ダメだ、どっちもRだ。ウーンと、リクエスト(reQuest)はQ、レスポンス(reSponse)はSとしましょう。このような約束事を設けて、実線だけでもリクエストとレスポンスの区別が付くようにします。

って書いておきながら、下の図では「R」だよっ。ウーム。僕、スキャン画像を修正するツール持ってないのよね。ごめんなさい、RはSに読み替えて

いいことありそうだ

今、とあるWebサーバーAがあったとします。このサーバーAは、Webクライアントからのリクエスト(略称Q)を受けて、レスポンス(略称S)を返すのですが、他のサーバーBが提供するWeb APIを呼び出すとします。つまり、サーバーAはBに対してはクライアントとなります。この状況を図示すると次のようです。(文字RはSに読み替えてください。レスポンスのことですね。

  1. クライアントからのリクエストがAに入ります。
  2. サーバーAがサーバーBにリクエストを送ります。
  3. サーバーAからのリクエストがBに入ります。
  4. サーバーBがレスポンスを返します。
  5. サーバーBからのレスポンスがAに入ります。
  6. サーバーAがクライアントにレスポンスを返します。

AとBが8の字形にワイヤー(有向辺)で繋がることに注目してください。この8の字繋ぎは、一般のモジュールを繋ぐときにも使えます。

[追記] 注意:ここから先は引いちゃう人がいるかもしれない。無理して読まなくてもいいし、流し読みして忘れてもらってけっこうです。[/追記]

さてここで、次の図を見てください。

8の字形の結合ですね。この図はサムソン・アブラムスキーのスライドだか論文(出典不明、調べれば分かると思うが)からコピーしたものです。そして次は、白旗優 (Shirahata, Masaru)さんの論文 "Geometry of Interaction explained" (http://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/43041/1/1318_19.pdf) にあった図です。

アブラムスキーが上から下なのに対して、白旗さんは左から右の方向を採用してます。先に述べたように、僕はアブラムスキーと同じ方向「上から下」を採用します。

アブラムスキーや白旗さんが扱っている話題は、コンパクト閉圏(compact closed category)とGoI構成(Geometry-of-Interaction construction)です。僕自身も随分と前からコンパクト閉圏やGoI構成を利用してやろうとたくらんでいました。

Webのメッセージフロー(リクエストとレスポンスの流れ)をうまいこと図示すると、結果的にトレース付きモノイド圏やコンパクト閉圏になるのです。もう少し正確にいうと、メッセージの直列結合と直和とフィードバック・ルーピングによりトレース付きモノイド圏(traced (symmetric) monoidal category)ができて、そのGoI構成(Int構成ともいう)によりコンパクト閉圏ができます。

「Webサービスの設計:Webの状態遷移図の描き方」の最後で次のように言いました。

ともあれ、「図式化すればいいことありそうだ」と僕は思ってますが、もっと経験を積まないとホントのところは何とも言えません。とりあえずは、状態遷移図をイッパイ描いてみることからスタートですね。

トレース付きモノイド圏やコンパクト閉圏、つまり圏論フローチャートの議論が使えるのが「いいこと」のひとつです。

フローチャートや副作用のような“嫌われ者”を、僕は「いいこと」に含めているのですが、そのへんの事情は次の記事とそこからのリンクをだとってみてください。

特にフローチャートについては:

*1:入る辺、出る辺がなくても別にかまいません。入る辺/出る辺がなくても、無意味ではありません。

2010-09-01 (水)

ハイパーリンクはホントウに難しい

| 12:35 | ハイパーリンクはホントウに難しい - 檜山正幸のキマイラ飼育記 を含むブックマーク

見出しに「Webサービスの設計」という語を含む一連の記事において、「ハイパーリンクこそがWebなんだから、Webでハイパーリンクを使わないなんてあり得ないぞ、使いまくれよな」みたいな話をしてきました。しかしながら、HTML以外のフォーマットでハイパーリンクを「使いまくる」のはなかなか難しいことです。そのへんの事情を話します。

内容:

  1. 高機能・柔軟なハイパーリンクの末路
  2. HTMLを真似るという方法
  3. HTMLを素直に真似できないときは
  4. ハイパーリンク構造の定義は型システムとは切り離す

高機能・柔軟なハイパーリンクの末路

HTMLは、アンカー(a要素)とフォーム(form要素)という形で“決め打ち・作り付け”なハイパーリンク機能を備えています。その機能は限定されており(HTML5でだいぶ増強されるようですが)柔軟性にも欠けます。XMLやJSONをベースフォーマットとするなら、もっと高機能で柔軟なハイパーリンク機能を設計することもできそうです。

と、そう思ってはみるのですが、高機能で柔軟なハイパーリンク仕様はことごとく失敗しています。古くはSGMLベースのHyTime -- 難解膨大な仕様で現実的な実装は登場しませんでした。HyTimeをずっとずっと軽量化してXMLベースとしたXLink -- これなら実装容易と思えたのですが、一筋縄ではいかない問題を抱えていました。HTMLフォームのスマートな拡張と思えたXFormsも普及していません。

この現実をみると、実は一般性なんて必要とされず、HTMLのa要素とform要素と同等な機能性を実現すれば十分なんじゃないのか、と思えます。実際僕はそのように考えて、JSONにもa要素/form要素相当の機能を入れようと思っていました。最近になって、それだけでもうまくいかない状況に遭遇しました。かといって一般化はしたくないし、… というジレンマに陥っています(←今ここ)。

HTMLを真似るという方法

まず僕は、既存の仕様であるJSONハイパースキーマを調べました。そのことは「JSONだってハイパーメディア -- JSONハイパースキーマ仕様をなんとかしたい」に書いてあります。

上記の記事で書いたことは、要するに「ハイパーリンクを表すデータ」という型を、型システムに入れるという話です。reference<T> がT型データへの参照型です。実例を挙げると次のようですね。

/** hCardAdr型の定義
 * microformats が定義している住所型
 */

type hCardAdr = {"adr" : 
 {
  "type" : ("work" | "home" | "pref" | "postal" | "dom" | "intl")?
  "post-office-box" : string?,
  "street-address" : [string*],
  "extended-address" : string?,
  "region" : string?,
  "locality" : string?,
  "postal-code" : string?,
  "country-name" : string?,
  * : any?
 }
};

/** 人物に関する短い情報 */

type email = string(format="email");

type ShortProfile = {
 /** 名前の文字列(フォーマット済み) */
 "fn" : string(minLength=1),
 /** メールアドレス */
 "email" : email,
 /** 住所への参照 */
 "adr" : reference<hCardAdr>?,
}

しかし、参照型を入れるだけではHTMLのハイパーリンク機能を実現できません。そこで、HTMLのa要素とform要素が持つ情報を寄せ集めてトリガー型というのを定義してみました(Webサービスの設計: ハイパーオブジェクトとトリガー)。以前の記事のトリガー型をそのまま引用すると:

type uri = string(format="uri");
type mediaType = string(format="media-type");
type httpMethod = ("GET" | "PUT" | "POST" | "DELETE" | "HEAD");

type Trigger<InputType> = {
 // 個々のトリガーを識別する属性
 "id" : string?,
 "name" : string?,
 "class" : string?,

 // ハイパーリンクの記述
 "href" : uri,
 "rel" : string?,
 "rev" : string?,
 "type" : mediaType?,
 "method" : httpMethod?,

 // 手続き呼び出し的なデータ項目
 "verb" : string?,
 "input" : InputType,

 // その他いろいろ
  * : any?
};

このトリガー型を具体化(型パラメータInputTypeを具体的型で置き換える)やサブタイピングすれば、HTMLのa要素/form要素に相当する情報を持つ型を定義できます。

これは、JSONのなかでHTMLをそっくり真似るという方法です。この方法が使える状況では、悪くないアプローチだと思います。

HTMLを素直に真似できないときは

新しくハイパーリンク機能を設計するときは、HTMLを真似ればいいでしょうが、既にあるデータ形式をハイパーリンクとして解釈したいときがあります。例えば、hrefプロパティ(XMLならhref属性)に相当するプロパティの名前がurlだったとします。これだけでHTMLを真似する方法は破綻します。

しょうがないので、urlという名前は「hrefに相当する」という情報をソフトウェアに伝えることになります。リネイム情報とかリマップ情報とか呼ばれ、HyTimeでも初期のXLinkでも使われていました(嫌な予感)。僕も、型定義(スキーマ内)のアノテーションにリマップ情報を入れる方法を考えたことがあります。次の定義のなかで、@[...] がアノテーションです。

@[trigger]
type LocationInfo = {
 @[trigger-prop("rel")]
 "type" : string,
 
 @[trigger-prop("href")]
 "url" : uri
};

アノテーションの意味を日本語で書いてみると:

  • @[trigger] -- 以下の型はトリガー型である。
  • @[trigger-prop("rel"] -- 以下のプロパティは標準トリガーのrelに相当する。
  • @[trigger-prop("href"] -- 以下のプロパティは標準トリガーのhrefに相当する。

rel相当とhref相当のプロパティが同じ階層にあるとは限りません。

@[trigger]
type LocationInfo = {
 @[trigger-prop("rel")]
 "type" : string,

 "info" : { 
    "comment" : string?,

    @[trigger-prop("href")]
    "url" : uri
 }
};

なんだか汚い。アノテーションで指定するのが良いか? どうも釈然としません。

ハイパーリンク構造の定義は型システムとは切り離す

与えられたデータからトリガーを抜き出して、その情報を解析するのはプログラムです。トリガーがどこにあって、どんな解釈をするべきかをソフトウェアに伝えない限りトリガーの処理(トラバースやリモートアクションの呼び出し)はできません。

逆に言えば、型システムにこだわらずとも、トリガーの場所と解釈方法を効果的に表現する方法があればいいことになります。「カジュアル過ぎるmicroformatsを少しだけ厳密に」の「データ抽出言語とマークアップの正しさ」において、CSSセレクタをベースにしたデータ抽出言語に触れましたが、同じように、トリガー情報抽出言語により、トリガーを記述することができるかもしれません。別な言い方をすると、非標準なトリガーを標準的なトリガーに変換する方法を示すことになります。プロパティのリネイムや階層構造の変更は、変換の一種と考えられます。

こんなやり方がベストだという自信はありません。が、ハイパーオブジェクトとトリガーという概念は、単なる雰囲気や比喩としてだけ語っていてはダメなんです。ソフトウェアにも人間にも明白に分かる記述が必要です。

2010-08-31 (火)

かくし絵

| 12:32 | かくし絵 - 檜山正幸のキマイラ飼育記 を含むブックマーク

次男:「この景色のなかに恐竜が10匹かくれています。探してください」
父親:「えーと、ウーンんと」

しばらく時間が経過。

父親:「ダメだ、わからん。見つからん」
次男:「ここに恐竜いるでしょ」
父親:「ウッヒャー、これは見つからんよー」
次男:「見つかるでしょ」
父親:「いやー、ムリムリ」
次男:「これくらいはかくし絵界では常識だよ」
父親:「かくし絵界? そんなんあるの?」
次男:「あります」

トラックバック - http://d.hatena.ne.jp/m-hiyama/20100831

2010-08-27 (金)

似顔絵

| 15:00 | 似顔絵 - 檜山正幸のキマイラ飼育記 を含むブックマーク

とある本に、栞<しおり>代わりにナプキンがはさまっていた。それに絵が描いてあったんだが、たぶんこれは長男が描いた僕の似顔絵。

でかい画像

内海内海 2010/08/27 15:30 >似顔絵
目元は、以前見た檜山さんの写真に似ていて雰囲気をつかんでいる感じですけど、輪郭線が大きすぎる気がします。私のイメージでは、檜山さんの輪郭線はすごくシャープな感じなので(^_^;)

m-hiyamam-hiyama 2010/08/27 16:50 内海さん、
> 目元は、以前見た檜山さんの写真に似ていて雰囲気をつかんでいる感じ
僕からすると、これは母親の目なんだけど、目元は母親に似てると言われるから、まー似てるんでしょうね、実際。
> 輪郭線はすごくシャープ
シャープでもないけど、絵のほっぺたは膨らみ過ぎかも。

トラックバック - http://d.hatena.ne.jp/m-hiyama/20100827

2010-08-26 (木)

Webサービスの設計: ハイパーオブジェクトは設計を極端に単純化する

| 10:24 | Webサービスの設計: ハイパーオブジェクトは設計を極端に単純化する - 檜山正幸のキマイラ飼育記 を含むブックマーク

昨日の話「Webサービスの設計: ハイパーオブジェクトはワークフローやインターフェースも運ぶ」の続きをもう少しします。ハイパーリンクを活用するとどんなメリットがあるか、ってことです。

昨日出した図をもう一度下に掲載します。

この図は、UMLのインタラクション図(シーケンス図)と少し似てます。このテの図は、アプリケーションレベルのプロトコルの記述に使われます。「あなたはまずこうして、そしたら私はああするから」みたいな手順とお約束を表すのです。

古典的なRPC(遠隔手続き呼び出し)ベースのシステムでは、通信の両端が共に手順・お約束に対する厳密な知識を持っていることを要求します。トリガーを含むハイパーオブジェクトを戻り値に使うなら、クライアント側に要求する知識を大幅に減らせます。ただし、ハイパーオブジェクトの解釈に関するメタな知識はやはり要求されることには注意してください。

さて、上のインタラクション図もどきの図は、次の状態遷移図に書き換えられます。(黒丸を描くのは省略してます。)

ハイパーオブジェクトは関数の戻り値であると同時にクライアント側の状態でもあり、トリガーにより「次にどうすべきか」の手順も表現します。つまり、ハイパーオブジェクトを利用すると、インタラクション図で表すようなプロトコル記述は状態遷移図に吸収されます。

状態遷移はクライアント側で生じるものですが、それをナビゲートしているのはサーバーなので、同じ図をサーバー側のリソースリンキングの図と解釈することもできます。

直線状の遷移グラフではつまらないので、次の例(これも昨日の例)を考えます。

状態ノードAに注目すると、このノードは次のインターフェース記述情報を含みます。

interface A {
  B b();
  C c();
}

インターフェース記述情報とは、UMLで言えばクラス図に相当します。

四角い枠線で囲まれた状態遷移モジュール内には4つのノードがあるので、これら全体が持つインターフェース記述情報を書き出してみると次のようになります。

module SomeService {
 interface A {
   B b();
   C c();
 };

 interface B {
   C c();
   D d();
 };

 interface C {
   D d()
 };

 interface D {
 };
};

このインターフェース記述にはメソッドしか書いてません。IDLやUMLクラス図の用語法では、メソッドをオペレーションと呼びます。データ項目は属性と呼びます(普通の言い方ならフィールドとかプロパティですね)。インターフェース記述のなかにデータ項目である属性も含めれば、それは型定義(スキーマ)になります。

つまり、ハイパーオブジェクトという概念を導入すれば、アプリケーションレベルのプロトコルの記述、クライアント側の状態遷移(サーバー側のリソースリンキング)の記述、インターフェースと型の記述が、単一の図で表現できます。単一の図で表現可能な理由は、概念として単純化されているからです。単純な概念を使えば、設計作業は(おそらく実装作業も)より容易になると期待できます。

単純化してしまうと、細かい区別や複雑・微妙な構造を記述できなくなります。柔軟性も失われます。しかし、Webはもともと単純なものです。そして(くどいけど)、Webはハイパーリンクにより出来上がっています。ハイパーリンクの能力とメリットを端的・直接的に利用する単純明快な方法を考えるがだと思います。

トラックバック - http://d.hatena.ne.jp/m-hiyama/20100826

2010-08-25 (水)

Webサービスの設計: ハイパーオブジェクトはワークフローやインターフェースも運ぶ

| 13:25 | Webサービスの設計: ハイパーオブジェクトはワークフローやインターフェースも運ぶ - 檜山正幸のキマイラ飼育記 を含むブックマーク

「Webサービスの設計: ハイパーオブジェクトとトリガー」において:

僕は「Webとはハイパーリンクなり」と考えているので、Web APIでもなんでもハイパーリンクを使ってないなら「Webっぽい」とは思いません。RPC(遠隔手続き呼び出し)的な要素を取り入れても、ハイパーリンクを活用しているならWebっぽいでしょう。「っぽい」とか「らしい」は単なる趣味嗜好の問題ではなくて、ハイパーリンクの活用は大きなメリットがあります(そのメリットの説明は今日[注:2010年8月11日]はしませんが)。

「ハイパーリンク活用の大きなメリット」について、今日(2010年8月25日)は説明します。

内容:

  1. 遠隔呼び出しとHTTP
  2. インターフェースと手順の合意
  3. あなたに任せるわ、私は言われるまま
  4. 理想のケースは人間がクライアントのとき
  5. 状態遷移モジュール
  6. インターネット/Webの驚嘆すべき頑健性

遠隔呼び出しとHTTP

関数呼び出しの関数本体が遠隔地(リモートロケーション)にあるとき、通信により関数呼び出しを行うメカニズムがRPCです。関数の識別情報と引数データをネットワークに送り出し、戻り値をネットワーク経由で受け取ります。次の図の上側は、遠隔呼び出しのイメージを描いたものです。

HTTPのリクエスト/レスポンスも大雑把な物言いをするなら「同じメカニズム」です(図の下側)。ですから、HTTPによる一連のやり取りをRPCモデルで考える事がただちに「悪」というわけではありません。しかし、ローカルの関数呼び出しのセマンティックスをネットワーク経由に直しただけだとWebとの相性が悪く、弊害をもたらします。

ここでは、クライアント側に要求する知識が多いことが「悪」「弊害」のひとつであり、ハイパーリンクによりこの問題をかなりの程度解消できることを説明します。

インターフェースと手順の合意

例題に次のようなインターフェースを考えましょう。

interface Service {
   A a();
   B b();
   C c();
}

A, B, C は型で、a(), b(), c() は関数(メソッド、手続き)だとします。関数の名前a, b, cをURLにして、どこからでも呼び出せるようにしたと仮定します。

このサービスを利用するクライアントは、上のインターフェース記述にあるような、関数の名前(URL)と戻り値型を知っている必要があります。それだけでなく、意味のある処理をするには、どの関数をどんな順序で呼び出すかなどの知識も必要です。

次の図を見てください。

これは、クライアントが a(); b(); c() の順序で関数を呼び出している図です。左側に書いてある番号(丸付き数字)が時間順を表します。ここで、「a(); b(); c() という順序は正しく、a(); c(); b() ではダメ」などの判断をしているのはクライアントです。つまり、クライアントはサーバーについて熟知している必要があります。

クライアントがサーバーについて知っていれば知っているほど、インターフェースや手順が変更されたときの影響に敏感になり、壊れやすいシステムになります。そもそも、サーバーとクライアントのあいだでの合意事項が多かったり共有すべき知識が膨大だと、なにかと手間がかかって大変ですよね。

あなたに任せるわ、私は言われるまま

遠隔呼び出しする関数の戻り値がハイパーオブジェクトだとしましょう。すると、戻り値データにトリガー(「Webサービスの設計: ハイパーオブジェクトとトリガー」を参照)を含めることができます。

関数a()の戻り値型Aがハイパーオブジェクト型で、関数b()を呼び出すトリガーを含んでいるとします。B型もハイパーオブジェクト型で、c()を呼び出すトリガーを含んでいるとします。すると、一連の呼び出しは次のようになります。

クライアントは、最初にa()を呼び出すことは知っている必要があります。しかしその後は、戻り値に埋め込まれたトリガーをたどって正しい呼び出し手順を実行できます。正しい手順を誘導しているはサーバーであり、クライアントはサーバーの提示した情報から次の行動をその場で決めていきます。時間順を表す番号(丸付き数字)が右側に書いてあるのは、手順を決める主導権が右(サーバー)にあることを示します。

トリガーを含んだハイパーオブジェクトは、単にデータ項目達を運ぶだけでなく、知識も運びます。「アプリケーションレベルのプロトコル、ワークフロー、ユースケース、シナリオ」などと呼ばれる「次に何ができるか/何をすべきか、どのようにそれをするか」という知識をクライアントに提供します。

この知識(ワークフローやインターフェース)は、事前に合意している必要がなく、その場で与えられます。例えば、ハイパーオブジェクトAに刷り込まれたインターフェースは次のものです。

interface A {
   B b();
}

その場で必要な、その場で許される呼び出しだけがコンパクトに記述されています。

理想のケースは人間がクライアントのとき

事前の合意や予備知識無しでもサーバー(が提供するサービス)を使える典型的な状況は、ハイパーオブジェクトがHTML形式であり人間がクライアントのときです。

アンカー(a要素)があれば、前後の文脈やリンクテキストを読んで、人間は「次に何をするか」をその場で決めます。フォーム(form要素)の場合はさらにすごくて、事前に入力データ(引数に相当)の型もセマンティックスも知らなくても、その場でフォームを埋めてサブミット(呼び出し)できます。

もちろんこれには、HTMLには自然言語の説明が書けて、人間は自然言語を解釈して知的な判断ができるという事情があります。プログラムがクライアントのときは、「リンクテキストを読む」とか、「その場でフォームの入力欄を埋めていく」ことはできません。しかし、人間がクライアントである状況に多少は近づけることはできるでしょう。人間は極めて頑健なWebクライアントです -- この頑健さを支えているメカニズムを真似れば、ソフトウェアWebクライアントを頑健にすることができると思うのです。

例えば先の例で、d()という関数がインターフェースに加わり、a(); b(); c() という呼び出しシーケンスが無効となり、a(); c(); d() に変わったとき、事前合意によるクライアントは破綻します。ハイパーオブジェクトとトリガーによりナビゲートされるクライアントは機能する可能性があります。

状態遷移モジュール

先の呼び出しシーケンス a(); b(); c() を「Webサービスの設計:Webの状態遷移図の描き方」で示したような図示法で描いてみます。ただし、アクションである関数を黒丸で描くのは省略しています。

四角の箱に入り込む矢印は1本しかありません。これが一連の手順を表す状態遷移モジュールへの入り口(エントリーポイント)です。入り口(への入り方)さえ知っていれば、それに引き続く状態遷移はサーバーがナビゲートしてくれます。それが箱の内部の遷移グラフです。

直線状の遷移グラフでは単純すぎるので、もうひとつ例を挙げましょう。

この状態遷移モジュールだと、「a(); b(); d()」、「a(); b(); c(); d()」、「a(); c(); d()」が“正しい”遷移経路となります。この遷移グラフを正規言語を認識するオートマトンとみなせば a, (b | b?, c), d という正規表現が遷移経路の表現になります。しかし、鳥瞰的に正しい経路を知っている必要はなく、各状態点ごとに局所的な情報 -- つまり次に「移るべき状態=次に呼び出すべき関数」さえ分かれば必然的に正しい経路をたどれます。

インターネット/Webの驚嘆すべき頑健性

「Webサービスの設計: ハイパーオブジェクトとトリガー」において次のような方針を述べました。

  • API体系は、人がブラウザで閲覧するためのサイトとまったく同じ構造にする。

Webはこの世で最も大規模で複雑な分散システムです。それがたいしたトラブルくもなく日々運用されています。サーバーは膨大な数だし、大きな多様性を持ち常に変化し続ける存在です。にも関わらずシステムは破綻せずに機能しています。この理由のひとつは、クライアントの大多数が人間+ブラウザだからでしょう。ハードコートされたソフトウェア・クライアントがWebの変化に追従するのは困難です。

この状況からすると、「ソフトウェア・クライアントも、人間+ブラウザに似せて作る」という方針は、既に成功している方法を真似るという意味で悪くないと思っています*1

*1:人とプログラムを区別しない理由は他にもありますが。