letマップ付きグラフ - (保存用) 檜山正幸のキマイラ飼育記メモ編

式を名前に束縛することは極めてよくある。letマップとは、この束縛機構を表すデータ構造だとする。ラムダ計算のlet式に相当する。再帰（自己言及）向けのletをletrecとして分けることが多いが、ここでは、letのなかにletrecも含めて考える。

letマップのひとつの項目をletエントリーと呼ぶことにする。letエントリーは、名前とその名前が指す対象物へのポインターリンクから構成される。

例題として次のスキーマを考える。



type Friend = {

  "name":  string,

  "email": string?,

  "addr" : string?,

  "bestFriend": bestFriendChain

};
type bestFriendChain = {

  "name": string,

  "bestFriend": bestFriendChain,

}?;

名前 Friend, bestFriendChain に対応する2つのletエントリーも含めて図示すると次のようになる。

ピンクと赤が、名前による参照に関わるのノードと辺。ピンク楕円のノードは、名前参照ノードで、構文的には「単なる名前の出現」に相当する。出現した名前は、いったんletエントリーを経由して他の式を参照することになる。letマップは名前空間と言っても同じである。

インライン・ネーミング

fetch問い合わせ式では、より簡略な表現ができる。



{

  "name":  string,

  "email": string?,

  "addr" : string?,

  "bestFriend": @= bestFriendChain {

      "name": string,

      "bestFriend": bestFriendChain,

   }?

}

bestFriendChainという名前による参照があるが、参照される先の名前をインラインで定義できる。インライン・ネーミングの構文が @= で、直後の式に名前を与える。この例では、次の部分式に名前bestFriendChainが与えられている。



{

   "name": string,

   "bestFriend": bestFriendChain,

}?

この部分式内に名前参照bestFriendChainが出てくるので、結果的に再帰構造となる。

インライン・ネーミングの場合も、暗黙のletマップを備えたグラフ構造なのだと考えることができる。式全体には名前が与えられてないが、空白の（あるいはデフォルトの）letエントリーが式全体を指しているとする。以下の図となる。

サイクリックグラフ

空白のletエントリーは省略して、letマップの枠線も省略すると次の図になる。

bestFriendChainという名前により2つのノードが結ばれている。bestFriendChainという名前は、ローカルに定義したもので、別の名前、例えば foo にリネームしてもかまわない。論理の限量子束縛変数や、ラムダ計算のラムダ変数と同じく、名前の綴りはなんでもよくて自由にリネーム（アルファ変換）できる。なので、名前の綴りも無視してしまうと次の図になる。

図のピンクと赤の部分は、自分自身に戻る辺＝サイクルを表現するための方便に過ぎない。テキスト構文でサイクル（やシェアリング）を表現するためには、中間に名前を挟む必要がある。しかし、この一時的な名前は単なる便宜的な手段なので、図では不要なのだ。

結局、letマップと名前参照ノードを使って表現したかったスキーマのデータ構造は、次のようなサイクリックグラフだったわけだ。

テキスト構文として書き下す都合で、名前はどうしても必要だ。名前のメカニズムがletマップ（名前の定義）と参照ノード（名前の出現）だが、図＝グラフとしては不要であり、中間的・一時的な名前を排除すると事情が単純になる。

以下にグラフ描画のソース。ほとんどコピペで作ったが全部載せておく。

/* -*- coding: utf-8 -*- */
/* letMapppedGraph-1.caty */

[

  [
     gv:node --shape=box --style=filled --fillcolor=pink --label="bestFriendChain" e_bestFriendChain,
     gv:node --shape=box --style=filled --fillcolor=pink --label="Friend" e_Friend,

  ] | gv:cluster  --label="let map" letMap,

  gv:edge --color=red e_bestFriendChain bestFriendChain,
  gv:edge --color=red e_Friend Friend,

/*

type Friend = {
  "name":  string,
  "email": string?,
  "addr" : string?,
  "bestFriend": bestFriendChain
};
*/

  gv:node --label="{}" Friend,
  gv:node --label="string" Friend_name,
  gv:node --label="string?" Friend_email,
  gv:node --label="string?" Friend_addr,
  gv:node --style=filled --fillcolor=pink --label="→" Friend_bestFriend,

  gv:edge --label="name"  Friend Friend_name,
  gv:edge --label="email"  Friend Friend_email,
  gv:edge --label="addr"  Friend Friend_addr,
  gv:edge --label="bestFriend"  Friend Friend_bestFriend,

  gv:edge --color=red Friend_bestFriend e_bestFriendChain,

/*

type bestFriendChain = {
  "name": string,
  "bestFriend": bestFriendChain,
}?;

*/
  gv:node --label="{}?" bestFriendChain,
  gv:node --label="string" bestFriendChain_name,
  gv:node --style=filled --fillcolor=pink --label="→" bestFriendChain_bestFriend,

  gv:edge --label="name"  bestFriendChain bestFriendChain_name,
  gv:edge --label="bestFriend"  bestFriendChain bestFriendChain_bestFriend,
  gv:edge --color=red bestFriendChain_bestFriend e_bestFriendChain,


] | gv:graph letMappedGraph-1

/* -*- coding: utf-8 -*- */
/* letMappedGraph-2.caty */

[

  [
     gv:node --shape=box --style=filled --fillcolor=pink --label="bestFriendChain" e_bestFriendChain,
     gv:node --shape=box --style=filled --fillcolor=pink --label=" " e_Friend,

  ] | gv:cluster  --label="let map" letMap,

  gv:edge --color=red e_bestFriendChain bestFriendChain,
  gv:edge --color=red e_Friend Friend,

/*

{
  "name":  string,
  "email": string?,
  "addr" : string?,
  "bestFriend": @= bestFriendChain {
      "name": string,
      "bestFriend": bestFriendChain,
   }?
}

*/

  gv:node --label="{}" Friend,
  gv:node --label="string" Friend_name,
  gv:node --label="string?" Friend_email,
  gv:node --label="string?" Friend_addr,

  gv:edge --label="name"  Friend Friend_name,
  gv:edge --label="email"  Friend Friend_email,
  gv:edge --label="addr"  Friend Friend_addr,
  gv:edge --label="bestFriend"  Friend bestFriendChain,


  gv:node --label="{}?" bestFriendChain,
  gv:node --label="string" bestFriendChain_name,
  gv:node --style=filled --fillcolor=pink --label="→" bestFriendChain_bestFriend,

  gv:edge --label="name"  bestFriendChain bestFriendChain_name,
  gv:edge --label="bestFriend"  bestFriendChain bestFriendChain_bestFriend,
  gv:edge --color=red bestFriendChain_bestFriend e_bestFriendChain,


] | gv:graph letMappedGraph-2

/* -*- coding: utf-8 -*- */
/* letMappedGraph-3.caty */

[

  gv:node --shape=box --style=filled --fillcolor=pink --label="bestFriendChain" e_bestFriendChain,
  gv:edge --color=red e_bestFriendChain bestFriendChain,

/*

{
  "name":  string,
  "email": string?,
  "addr" : string?,
  "bestFriend": @= bestFriendChain {
      "name": string,
      "bestFriend": bestFriendChain,
   }?
}

*/

  gv:node --label="{}" Friend,
  gv:node --label="string" Friend_name,
  gv:node --label="string?" Friend_email,
  gv:node --label="string?" Friend_addr,

  gv:edge --label="name"  Friend Friend_name,
  gv:edge --label="email"  Friend Friend_email,
  gv:edge --label="addr"  Friend Friend_addr,
  gv:edge --label="bestFriend"  Friend bestFriendChain,


  gv:node --label="{}?" bestFriendChain,
  gv:node --label="string" bestFriendChain_name,
  gv:node --style=filled --fillcolor=pink --label="→" bestFriendChain_bestFriend,

  gv:edge --label="name"  bestFriendChain bestFriendChain_name,
  gv:edge --label="bestFriend"  bestFriendChain bestFriendChain_bestFriend,
  gv:edge --color=red bestFriendChain_bestFriend e_bestFriendChain,


] | gv:graph letMappedGraph-3

/* -*- coding: utf-8 -*- */
/* letMappedGraph-4.caty */

[
  gv:node --shape=point --color=pink e_bestFriendChain,
  gv:edge --color=red e_bestFriendChain bestFriendChain,

/*

{
  "name":  string,
  "email": string?,
  "addr" : string?,
  "bestFriend": @= bestFriendChain {
      "name": string,
      "bestFriend": bestFriendChain,
   }?
}

*/

  gv:node --label="{}" Friend,
  gv:node --label="string" Friend_name,
  gv:node --label="string?" Friend_email,
  gv:node --label="string?" Friend_addr,

  gv:edge --label="name"  Friend Friend_name,
  gv:edge --label="email"  Friend Friend_email,
  gv:edge --label="addr"  Friend Friend_addr,
  gv:edge --label="bestFriend"  Friend bestFriendChain,


  gv:node --label="{}?" bestFriendChain,
  gv:node --label="string" bestFriendChain_name,
  gv:node --style=filled --fillcolor=pink --label="→" bestFriendChain_bestFriend,

  gv:edge --label="name"  bestFriendChain bestFriendChain_name,
  gv:edge --label="bestFriend"  bestFriendChain bestFriendChain_bestFriend,
  gv:edge --color=red bestFriendChain_bestFriend e_bestFriendChain,


] | gv:graph letMappedGraph-4

/* -*- coding: utf-8 -*- */
/* letMappedGraph-5.caty */

[

/*

{
  "name":  string,
  "email": string?,
  "addr" : string?,
  "bestFriend": @= bestFriendChain {
      "name": string,
      "bestFriend": bestFriendChain,
   }?
}

*/

  gv:node --label="{}" Friend,
  gv:node --label="string" Friend_name,
  gv:node --label="string?" Friend_email,
  gv:node --label="string?" Friend_addr,

  gv:edge --label="name"  Friend Friend_name,
  gv:edge --label="email"  Friend Friend_email,
  gv:edge --label="addr"  Friend Friend_addr,
  gv:edge --label="bestFriend"  Friend bestFriendChain,

  gv:node --label="{}?" bestFriendChain,
  gv:node --label="string" bestFriendChain_name,

  gv:edge --label="name"  bestFriendChain bestFriendChain_name,
  gv:edge --label="bestFriend"  bestFriendChain bestFriendChain,


] | gv:graph letMappedGraph-5