可逆計算が面白いから、JavaScriptで書いてみた - 檜山正幸のキマイラ飼育記 (はてなBlog)

グリーンとアルテンキルヒ（Alexander S. Green, Thorsten Altenkirch）の「可逆計算から不可逆計算へ（From reversible to irreversible computation）」という10ページの短い論文があります。タイトルのとおり、可逆計算から不可逆計算が出るよ、ってハナシがこの論文の眼目なんですが、可逆計算の部分（前半）が面白かったので紹介します。

何が面白いかというと、可逆計算だと古典計算も量子計算も差がないのですよ。同じ定式化を許します。古典計算において可逆計算に慣れておくことは量子計算へのよい準備になると思います。とか言っても、今回は難しい話は全部すっ飛ばして、JavaScriptの関数をいくつか書いてみるだけですがね。

このエントリーを書こうとしてJavaScriptでミスを犯した顛末は「JavaScriptでハマった件：さすがにJavaScriptだな、ウム」に書いてあります。

内容：

用語と記号に関する注意
可逆多値関数
可逆多値関数の例
可逆多値関数の積（並列結合）
条件分岐 if-then-else
メタ計算法則

●用語と記号に関する注意

今回の文脈では、「計算」と「プログラム」は同義語です。ハードウェア実装をイメージすると、「コンピュータ」、「回路（サーキット）」、「ゲート」も、「計算」と同義語です（人によっては、「ゲート」を回路を組み立てる基本部品という意味で使いますが）。

可逆計算（＝可逆プログラム＝可逆コンピュータ＝可逆回路＝可逆ゲート）とは、出力から入力を完全に再現できる計算のことです。足し算 x, y → x + y は可逆ではありません。符号反転 x → -x は可逆です。

計算（プログラム）を組み合わせる方法を制御構造と呼びます。計算を関数で表現すると、制御構造は高階関数で表現できます。次の表に、このエントリーで扱う制御構造をまとめます。

制御構造	グリーン／アルテンキルヒの記号	ここで使う記号	JavaScript関数
逐次実行	白い小さな丸	セミコロン「;」	Comp(f, g)
並列実行	テンソル積（環積）	シャープ「#」	Prod(f, g)
条件分岐	縦棒	縦棒	Cond(f, g)

●可逆多値関数

多値関数を考えますが、複数の値をタプル（JavaScriptでは配列）にまとめて返すという安直な方法で実現します。次は多値関数の例です。



function addsub(x, y) {

 return [x + y, x - y];

}



js> addsub(2, 3)

5,-1

js>

さらに、引数の個数と戻り値の個数（この場合は配列の長さ）が同じような関数だけを考えます。後で使う都合から、引数の個数（戻り値の個数でもある）を関数の_arityというプロパティに記録しておきましょう（アンダスコアなしのarityというプロパティは予約されていますから自由に使えません）。



function addsub(x, y) {

 return [x + y, x - y];

}

addsub._arity = 2;

このような関数を扱う際、普通の関数合成では不便なので、次のような高階関数Compを作っておきます。



function err(message) {

 alert(message);

 throw new Error(message);

}
function Comp(f, g) {

 if (f._arity != g._arity) {

  err("Comp: _arityが一致していません.");

 }

 var fun = function() {

  var y = f.apply(null, arguments);

  return g.apply(null, y);

 };

 fun._arity = f._arity;

 return fun;

}



js> Comp(addsub, addsub)(2, 3)

4,6

js>

addsubは可逆です。これは、次のことを意味します。

addsubInvという関数*1があり、Comp(addsub, addsubInv) も Comp(addsubInv, addsub) も何もしない関数と一致する。

addsubの逆であるaddsubInvは次のような関数です。



function addsubInv(s, t) {

 return [(s + t)/2, (s - t)/2];

}

addsubInv._arity = 2;

実験：



js> Comp(addsub, addsubInv)(2, 3)

2,3

js> Comp(addsubInv, addsub)(2, 3)

2,3

js>

●可逆多値関数の例

可逆多値関数の例をいくつか出します。



function id1(x) {

 return [x];

}

id1._arity = 1;
function id2(x, y) {

 return [x, y];

}

id2._arity = 2;
function swap(x, y) {

 return [y, x];

}

swap._arity = 2;

JavaScriptは型がルーズですが、型が厳しい言語では、何種類ものid1を作る必要があるでしょう。JavaScriptでも、あえて引数をブール値（boolean）に限定した関数を2つ定義しておきます。



function idb(b) {

 if (typeof b != 'boolean') {

  err("idb: 引数がbooleanではありません.");

 }

 return [b];

}

idb._arity = 1;
function not(b) {

 if (typeof b != 'boolean') {

  err("not: 引数がbooleanではありません.");

 }

 return [!b];

}

not._arity = 1;

ここで挙げたid1, id2, swap, idb, notはいずれも可逆です。それぞれの逆関数を探してみてください。

●可逆多値関数の積（並列結合）

Compは直列（逐次、シーケンシャル）結合でしたが、並列な結合Prodも定義します。Prodは積（product）からの命名です。



function toArray(x) {

 var a = [];

 for (var i = 0; i < x.length; i++) {

  a.push(x[i]);

 }

 return a;

}
function Prod(f, g) {

 var fun = function() {

  var args = toArray(arguments);

  var x = f.apply(null, args.slice(0, f._arity));

  var y = g.apply(null, args.slice(f._arity));

  return Array.prototype.concat.call(x, y);

 };

 fun._arity = f._arity + g._arity;

 return fun;

}

なんかややこしそうですが、fもgも1変数のときなら、h = Prod(f, g) とすると、h(x, y) = concat(f(x), f(y)) です。Prodの実例を見てみましょう。



s> Prod(swap, id1)(1, 2, 3)

2,1,3

js> Prod(id1, swap)(1, 2, 3)

1,3,2

js> Prod(swap, swap)(1, 2, 3, 4)

2,1,4,3

js> var h = Comp(Prod(swap, id1), Prod(id1, swap))

js> h(1, 2, 3)

2,3,1

js>

wap, id1 を組み合わせると、実はアミダの実験ができます。

●条件分岐 if-then-else

条件分岐、つまり if-then-else文に対応する高階関数Condは次のようになります。



function Cond(f, g) {

 if (f._arity != g._arity) {

  err("Cond: _arityが一致していません.");

 }

 var fun = function(b) {

  if (typeof b != 'boolean') {

   err("a function made by Cond: 第1引数がbooleanではありません.");

  }

  var args = toArray(arguments);

  args.shift();

  var x;

  if (b) {

   x = f.apply(null, args);

  } else {

   x = g.apply(null, args);

  }

  return Array.prototype.concat.call([b], x);

 };

 fun._arity = 1 + f._arity;

 return fun;

}

fもgも1変数のときなら、Cond(f, g)(b, x) は、if (b) {return f(x);} else {return g(x);} とほぼ同じです。違う点は、bも戻り値に含まれることです。条件となるブール値bも一緒に返すことにより、Cond(b, f, g) が再び可逆多値関数になることを保証します。

●メタ計算法則

制御構造は、計算＝プログラムにたいする演算子と考えられます。よって、制御構造を含むプログラムの議論は、計算の計算、つまりメタ計算となります。制御構造を演算子らしい記号で表して、いくつかのメタ計算法則を書き下してみましょう。

記法：

fの逆はf^-1
fとgの逐次結合は f;g
fとgの並列結合は f#g
fとgの条件分岐は (f|g)

メタ計算法則：

(f;g)^-1 = g^-1;f^-1
(f#g)^-1 = f^-1#g^-1
(f|g)^-1 = f^-1|g^-1
(idb#h);(f|g) = (h;f)|(h;g)
(f|g);(idb#h) = (f;h)|(g;h)
(f|g);(f'|g') = (f;f')|(g;g')
(f|g)#h = (f#h)|(g#h)
(h|h) = (idb#h)
(f|g);(not#idA) = (not#idA);(g|f)

これらの法則の実例（法則そのものではない）は、高階関数Comp, prod, Condを使って確認できます。例えば、4番目の法則で h = swap, f = id2, g = swap としてみると、(idb#swap);(id1|swap) = (swap;id2)|(swap;swap) となりますが：



js> var j = Comp(Prod(idb, swap), Cond(id2, swap));

js> var k = Cond(Comp(swap, id2), Comp(swap, swap));

js> j(true, 1, 2)

true,2,1

js> k(true, 1, 2)

true,2,1

js> j(false, 1, 2)

false,1,2

js> k(false, 1, 2)

false,1,2

js>

*1:可逆計算の可逆はreversibleですが、逆関数の逆はinverseです。