このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

データの部分構造とパート

「ハイパースキーマまでの道」に書いた予定に従って、JSON向けのシンプルセレクターの次はパートという概念を定義します。

内容:

  1. プロパティ/項目からパートへ
  2. パートの例
  3. パートのドメイン型とコドメイン
  4. パートの利用例
  5. BNFによるパート定義の構文
  6. パートに関する制約と代数構造
  7. その他のこと

プロパティ/項目からパートへ

パートとは、“オブジェクトのプロパティ”や“配列の項目”を拡張した概念です。最初にプロパティと項目について復習しておきます。

xが、JavaScriptJSONのオブジェクトデータのとき、x.foo や x["foo"] でプロパティにアクセスできます。yが配列なら、y[2] のようにして項目にアクセスできます。代入は、x.foo = 10, x.[2] = "hello" のようにします。以上のことを、メソッド記法を使って書いてみれば次のようになるでしょう。

  • x.getProp("foo")
  • y.getItem(2)
  • x.setProp("foo", 10)
  • y.setItem(2, "hello")

パートは、単一のプロパティや項目に限らず、複合データの任意の部分に名前を付けたものです。パートからの値の取得、パートへの値の代入が次のように行えます。

  • z.getPart(パート名)
  • z.setPart(パート名, パート値)

つまり、パートの目的は次の2つです。

  1. JSONデータから部分構造の抽出を行う。
  2. JSONデータの部分構造の更新を行う。

パートの例

次のデータを例とします。


{
"givenName" : "トン吉",
"familyName" : "坂東",
"birth" : {
"year" : 1985,
"month" : 10,
"day" : 10,
}
}

このデータのスキーマは次のようだとします(Catyスキーマ言語による定義です)。


type Person = {
"givenName" : string,
"familyName" : string,
// 日付の制約は厳密ではない
"birth" : {
"year" : integer,
"month" : integer(minimum=1, maximum=12),
"day" : integer(minimum=1, maximum=31),
}?,
"email" : string(format="email")?
};

名前と生年だけを取り出すパートは次のように定義します。パートを定義するための構文は暫定的で、まだ確定はしてません。


part nameBYear = {
"givenName" : %value("givenName"),
"familyName" : %value("familyName"),
"birthYear" : %value("birth.year")
};

パート定義は型定義と似てますが、型名が入る部分に「value関数」の呼び出しが書かれています。value関数は、パス式*1を引数として値を取り出す関数です。パス式は「JSON向けのシンプルセレクター」で述べたセレクタ式の特別な形式(ワイルドカードなし)と思ってかまいません。パーセント記号は、関数呼び出しであることを明示するための目ジルシです。

最初に挙げたインスタンスデータをxとして x.getPart("nameBYear") の結果は次のデータとなります。


{
"givenName" : "トン吉",
"familyName" : "坂東",
"birthYear" : 1985
}

パートのドメイン型とコドメイン

パートは、与えられたデータから別なデータを生成する関数と考えることができます。パート定義は簡単な関数定義と言えます。しかし、先のような定義では、関数のドメインとコドメインの型がハッキリしません。そこで次のような形で、パートのドメイン/コドメインを明示します。


type NameBYear = {
"givenName" : string,
"familyName" : string,
"birthYear" : integer?
};

part nameBYear :: Person -> NameBYear = {
"givenName" : %value("givenName"),
"familyName" : %value("familyName"),
"birthYear" : %value("birth.year")
};

Person -> NameBYear の部分がパートのドメイン/コドメインの指定で、プロファイルと呼ばれます。処理系が十分に賢ければ、パートのドメイン型定義とコドメイン型定義、そしてパートの定義自体を見て、これらが整合的かどうかをチェックできます。整合性のチェックとは、パートpに対して次のことを保証することです。

  1. xがドメイン型のインスタンスなら、x.getPart(p) はコドメイン型のインスタンスである。
  2. xがドメイン型のインスタンス、vがコドメイン型のインスタンスなら、x.setPart(p, v) はドメイン型のインスタンスである。

いつでもプロファイルが必要なわけではないので、パートのプロファイルは省略可能です。ドメイン型またはコドメイン型のどちらか一方を省略するときは、dont-careを意味するアンダースコアを使います。次がdont-careを使った例です。


part nameBYear :: Person -> _ = {
"givenName" : %value("givenName"),
"familyName" : %value("familyName"),
"birthYear" : %value("birth.year")
};

パートの利用例

パートは、JSONデータからハイパーリンク部分を抽出することを目的として考えたものなので、そのような例を挙げます。

まずは次の型定義; これは、画像を使った紙芝居ないしはスライドショーに使うようなWebページのデータ構造を想定しています。


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

type Page = {
/** ホームへのリンク */
"home" : uri,
/** 画像のURL */
"image" : uri,
/** 画像に対する説明文 */
"description" : string,
"links" : {
/** 次のページ(があれば)へのリンク */
"next" : uri?,
/** 前のページ(があれば)へのリンク */
"prev" : uri?,
}
};

このデータからハイパーリンクを抽出するためのパートを、次のように定義します。


type Anchor = {
"rel" : string?
// hrefが存在しないときはリンク先がないことを示す
"href" : uri?,
};

part home :: Page -> Anchor = {
"rel" : "home",
"href" : %value("home")
};

part next :: Page -> Anchor = {
"rel" : "next",
"href" : %value("links.next")
};

part prev :: Page -> Anchor = {
"rel" : "prev",
"href" : %value("links.prev")
};

type PageLinks = {
"home" : Anchor,
"next" : Anchor,
"prev" : Anchor
};

part pageLinks :: Page -> PageLinks = {
"home" : home,
"next" : next,
"prev" : prev,
};

pageLinksパートを使ってgetPartすれば、Pageデータからハイパーリンク情報を取り出せます。このようなことを、もっと系統的に行う手段が、(まだ何も書いてませんけど)トリガー定義です。

BNFによるパート定義の構文

暫定的な構文ですが、いちおうBNF構文定義を。


パート定義 ::= 'part' 名前 プロファイル? '=' パート式 ';'

プロファイル ::= '::' ('_' | 型表現) '->' ('_' | 型表現)

パート式 ::= 値抽出 | スカラーリテラル | パート名 |
配列式 | オブジェクト式 | タグ付き式

値抽出 ::= '%' 'value' '(' ダブルクォートされたパス式 ')'

スカラーリテラル ::= {任意のJSONスカラーリテラル}

パート名 ::= 名前 /* 他で定義されたパート */

配列式 ::= '[' (パート式 (',' パート式)*)? ']'

オブジェクト式 ::= '{' 文字列 ':' パート式 '}'

タグ付き式 ::= タグ パート式

タグ ::= '@' (タグに許容できる名前 | 文字列)

パートに関する制約と代数構造

pがパートとして、そのプロファイルが p :: X -> V だとします。x∈X (xは型Xのインスタンス)、 v, w∈V (vとwは型Vのインスタンス)だとして、次が成立しなくてはなりません。

  1. 次の2つの処理(状態遷移)の結果は完全に同じ。
    • x.setPart(p, v); x.setPart(p, w)
    • x.setPart(p, w)
  2. x.setPart(p, v) の後では、x.getPat(p) の値は v に等しい。

これは、変数からの値の取得と代入でも成立することです。ストレージの線形代数の観点からいうと、値の取得、値のコピー、破壊的代入などの操作は、まとめてフロベニウス代数とフロベニウス加群の構造を持ちます。破壊的代入に特有な特徴から、双代数上の双加群の構造も持ちます*2。これらの代数構造は、上の制約条件から導かれることです。

その他のこと

パートは、長年僕が手を変え品を変え、呼び名も変えて使い回してきた概念です。ファセット、ロール、仮想データとか。元データとパートを結ぶメカニズムもコネクター、ブリッジ、スパンとか。同じ概念でも、バッチ処理と対話処理では全然別物に見えます。パートには、あまり語られてない(と思われる)興味深い構造が色々あります。それはまたの機会に。

*1:先頭のドル記号は省略してもいいとします。

*2:これらのことは、ストレージの線形代数の続編として書くことがあるかも知れません。