データ・コード双対性、エルゴット繰り返し、ツインコードスタック抽象機械

データとコード（プログラム）のあいだに、双対性があるような気がするんですよ。ハッキリと説明しろと言われるとちょっと困りますが、ありそうな雰囲気。で、あんまりハッキリしない雰囲気的な話をします。

内容：

コンウェイ演算子とエルゴット演算子
エルゴット繰り返しとbegin/repeat制御構造
begin/repeat制御構造のためのツインコードスタック機械
データ・コード双対性

コンウェイ 演算子とエルゴット演算子

公理的に定義された不動点演算子はコンウェイ演算子（Conway operator）と呼ばれます。コンウェイ演算子はかなり一般的な圏（プレモノイド圏）に対して定義できます。これに関しては次の論文を参照してください。

Title: TRACED PREMONOIDAL CATEGORIES
Authors: Nick Benton and Martin Hyland
URL: http://research.microsoft.com/pubs/67350/premonitapdf.pdf

トレース付きデカルト圏におけるコンウェイ演算子の具体的表示は、f^† := Tr(f;Δ) となります。Trはトレース演算子、Δは対角射です。余デカルト圏、つまり直和に関するモノイド圏を考えて、Tr'を直和に関するトレース、∇は余対角だとすると、Tr(f;Δ) の双対として Tr'(∇;f) という表示が得られます。

不動点演算子の記号としては、f^† のように“右肩のスターやダガー”がよく使われます。不動点演算子の双対は、左肩のダガーを使うことにしましょう。（通常は、両方とも右肩に付けて文脈で区別します。）

^†f := Tr'(∇;f)

このように定義される圏論的演算子 ^†(-) は、コンウェイ演算子の双対と言っていいでしょう。この余コンウェイ演算子（あるいは余不動点演算子）はエルゴット演算子（Elgot operator）と呼ばれます。

エルゴット繰り返しとbegin/repeat制御構造

エルゴット演算子は、プログラムのルーピング制御構造を与えるので、エルゴット繰り返し（Elgot repetition）とも呼ばれます。エルゴット繰り返しの表現方法のひとつとして、僕はbeginとrepeatというキーワードによる制御構造が良かろうと思っています。



begin {

  ...

  ...

  ... repeat;

}

これだけです。beginによりブロックが作られ、そのブロック内でrepeatが実行されるとブロック先頭に戻ります。

例えば、カウントダウンするプログラムなら次のように書けます。



var n = 10;
begin {

    if (n >= 0) {

	println(n);

	n--;

	repeat;

    }

}

beginブロックの内部を、「整数引数を1つだけ取り、整数を返す関数」のように考えましょう。その場合に、beginによる制御構造は次のような高階関数（JavaScriptを使用）として書けます。

function begin(n /* 整数 */, f /* 関数 */) {
    var k = n;
    while (true) {
	var r = f(k);
	if (r.repeat !== undefined) {
	    // 繰り返し
	    k = r.repeat;
	} else {
	    // 繰り返しではない
	    return r.break;
	}
    }
}

先の例のbeginブロック内部は、次の関数で表現します。

function countdown(n /* 整数 */) {
  if (n >= 0) {
    println(n);
    n--;
    return {"repeat": n};
  } else {
    return {"break": n};
  }
}

3からカウントダウンするプログラムは、begin(3, countdown) を実行すればいいわけです。firebugなどで実行するときは、printlnをalertに置き換えてください。

一般にbeginは無限ループする可能性があるので注意してください。例えば、次の関数をbeginのなかで実行すると（n >= 0 のとき）終りません。

function countNotDown(n /* 整数 */) {
  if (n >= 0) {
    println(n);
    return {"repeat": n};
  } else {
    return {"break": n};
  }
}

begin/repeat制御構造のためのツインコードスタック機械

概念的かつ記号的な仮想機械を抽象機械と呼ぶことにします。begin/repeat制御構造に向いた抽象機械を定義してみます。

コンピュータのコード領域の抽象化として、式（項）の列 {E₁, E₂, ...} を考えます。式は評価（evaluate）されて、結果として値が得られます。話を簡単にするために、評価環境は単一の値（入力と考えていいです）としましょう。

評価規則の基本は x₀ {E₁, E₂, ...} → x₁ {E₂, ...} です。これの意味は：

評価環境（＝入力）は、x₀ であった。
コード領域は {E₁, E₂, ...} であった。
E₁を評価した。その結果は x₁ 。
新しい評価環境（＝次の入力）は、x₁ となった。
新しいコード領域は {E₂, ...} となった。

式の列であるコード領域は、左から順に評価されていくとします。このコード領域は、左端がスタックトップであるスタックのように扱うので、コードスタックとも呼びましょう。

さて、今までのコードスタックとは別にもう1本のコードスタックを準備します。そして、抽象機械の計算状況（computational configuration）は、{..., F₂, F₁} x {E₁, E₂, ...} と表します。真ん中のxは、現在の評価環境となる値です。左側の {..., F₂, F₁} もコードスタックですが、こっちはスタックトップを右端とします。2本のスタックを区別するために、左コードスタックと右コードスタックと呼び分けます。

この抽象機械の左コードスタックは、出現したbeginブロックを記録しておくために使います。begin, repeat, end の評価規則は次のようになります。なお、endはbeginブロックの閉じ括弧（「}」）に相当します。

{..., F₁} x {begin{E}, ...} → {..., F₁, E} x {E, ...}
{..., E} y {repeat, ...} → {..., E} y {E, ...}
{..., F₁, E} y {end, E₂, ...} → {..., F₁} y {E₂, ...}

もう少し詳しく言うと：

beginの実行：左コードスタックにbeginの内部Eをプッシュし、右コードスタックのトップをEとする。
repeatの実行：左コードスタックのトップを、右コードスタックのトップにコピーする。
endの実行：左コードスタックをポップする。

右コードスタックは、これから実行すべきコードであり、左コードスタックは、繰り返しにより実行する可能性のあるコードを一時的に保存します。左右2本のコードスタックの操作により、begin/repeat制御構造（エルゴット繰り返し）を実現できます。

データ・コード双対性

正規表現を構成する演算子（メタ文字）である、連接（「,」または空）、選択（「|」）、繰り返し（「*」）は、プログラムの逐次実行、分岐、繰り返しに対応します。この事実は、再帰降下方式パーザーなどを作るときに利用されます。クリーネ代数による定式化もあります。

正規表現は再帰的なデータ領域を定義します。より一般的な再帰的データ領域は、領域を操作する関数の不動点として定義されます。データ領域に関する不動点の圏論的な定式化がコンウェイ演算子です。

コンウェイ演算子とその双対をベースとした「データとコードの対応関係」は、クリーネ代数のときほどに直接的ではありません。直積と直和の双対性が介在しているからです。ひょっとすると、単一の双対性ではなくて、いくつかの双対性が絡んだ対称性を持っているのかも知れません。begin/repeatプログラミングをしてみると何かわかるでしょうか？と、そういう下心は置いておくとしても、begin/repeatは面白いですよ。