日本ソフトウェア科学会第 33 回大会 (2016 年度) 講演論文集

二分木のランク計算のクリーン可逆シミュレーション
大久保 雄飛

横山 哲郎

金山 知俊

可逆計算システムで用いる可逆アルゴリズムのひとつとして，二分木の列挙やランダム生成に有用な二分木のラン
ク・アンランク計算のクリーン可逆シミュレーションを提案する．二分木のランク計算やその逆計算を行う非可逆ア
ルゴリズムは 1970 年代から研究が行われてきており，これらの成果を用いてランク計算の関数とその逆関数のそれぞれの可逆シミュレーションを組み合わせてクリーン可逆シミュレーションを行うことはできる．しかし，こうした可逆シミュレーションでは，複数回のパスおよびに実行時間に比例した大きさのメモリが必要である．これに対してわれわれの可逆シミュレーションは，1 パスで，漸近的な実行時間とメモリ使用量が元のアルゴリズムと同じである．本稿中の可逆プログラムは，可逆言語 Janus の処理系で動作を確認できる．

As a reversible algorithm for reversible computing systems, we propose a clean reversible simulation of
ranking and unranking binary trees, which is useful for enumerating and randomly generating binary trees.
Algorithms for ranking binary trees and their inverses have been studied since 1970s, and combining theresults leads to a clean reversible simulation. However, such a reversible simulation requires multiple paths
for traversing given data and/or intermediate data, and extra storage being proportional to the length ofcomputation. The proposed reversible simulation is one path and its asymptotic running time and memory
usage are equivalent to the original. All the reversible programs in this paper can be run on an interpreterof the reversible programming language Janus.

可逆シミュレーションでは，計算中に必要なメモリお1 はじめによび元のアルゴリズムでは出力されないゴミ出力の可逆計算システムでは，可逆演算を基本とするとそ

量が実行時間に比例した大きさにまでなってしまう問の上で使うアルゴリズムの設計が容易になる．可逆性

題がある．一方，問題固有の情報を考慮して可逆アル制約が考慮された可逆アルゴリズムの設計と解析にゴリズムを設計するとこうしたものを小さくできる．

は，その制約があるので通常のアルゴリズムの設計

任意の単射関数に対して，必ずゴミ出力無しの，すな

および解析とは異なる手法が必要である．一般的に，

わちクリーンな可逆シミュレーションが作れることが（非可逆）アルゴリズムを可逆計算システム上で可逆知られている．しかし，任意の非可逆プログラムを同シミュレーションするような互いに時間計算量・空間等の計算複雑度でゴミ出力が無い可逆プログラムに計算量などがトレードオフ関係にある一般解法が知する体系的な方法は知られていない．したがって，少られている [3] [8] [25] [26]．しかし，こうして得られるなくとも現在のところ，クリーン可逆シミュレーショ
ンの最適化は，個別のアルゴリズムについて経験や勘∗

Clean Reversible Simulation of Ranking Binary
Trees
This is an unrefereed paper. Copyrights belong to
the Authors.
Yuhi Ohkubo, Tetsuo Yokoyama, Chishun Kanayama,
南山大学理工学部ソフトウェア工学科, Department ofSoftware Engineering, Faculty of Science and Engineering, Nanzan University.

を頼りに手動で行わざるを得ない．
木構造は節点の間の「枝分かれ」によって情報を配置する構造であり，計算システムやアルゴリズムにおいて最も重要な構造のひとつである．たとえば，代数式の表現やアルゴリズムの解析に木構造を用いる手法が知られている [19]．本稿では，二分木のランク・アンランク計算のクリーンな可逆アルゴリズムを設計・は量子計算の基礎のひとつになっている [16] [8]．

解析する．二分木のランク・アンランク計算は，一様物理的な可逆性を論理レベルで扱うには，論理回分布したランクに対応する二分木をランダムに生成す

路 [27]，計算機アーキテクチャ [29]，プログラミングることに応用できたり二分木の列挙のアルゴリズムの言語（ [22] [15] [2] [13] [17] [33] など），およびアルゴリ

基礎になったりするアルゴリズムである [28] [18] [19]．

ズムのすべての階層を可逆に設計する必要がある．しこのように応用範囲が広いにもかかわらず，筆者の知かし，可逆アルゴリズムの研究は次のような一部の例

る範囲では，その可逆アルゴリズムの提案はこれま

外を除くとこれまで深くは行われてこなかった．

でなされてこなかった．本稿では，まず，非可逆アル

非可逆アルゴリズムで失われるデータや制御情報

ゴリズムから埋め込みによって可逆シミュレーションをすべて憶えるようにしたアルゴリズムは可逆になを得て，次に Bennett 法でそれらを組み合わせるこる [3]．この変換を（非可逆計算の可逆計算への）埋とでクリーン可逆シミュレーションを得る．さらに，

め込みと呼ぶ．埋め込みによる可逆シミュレーション

漸近的な実行時間と使用メモリ量が元のアルゴリズの実行には，時間計算量，空間計算量，消去情報量，ムと同じという意味で効率的な可逆アルゴリズムを

および実時間性などの観点でトレードオフをもつ手提案する．

法が提案されている（たとえば，文献 [13] [26] および

文献 [28] によると，二分木のランク・アンランク計

その参考文献を参照）．

算は，Knott によるアルゴリズム [18] が最初である．

埋め込みよりも効率的で特定のアルゴリズム族に適

本稿では，Knott による Algol プログラムを基に可用可能な可逆シミュレーションが存在する．任意の入逆シミュレーションを考える．ランク・アンランク計

力 x に対する関数 f の返却値 y とその返却値 y を入算のアルゴリズムを二分木の数え上げを 3 つに場合力としたその逆関数 f −1 の返却値として x が得られ分けすることで詳解する．これらの対応をとってランる場合，両者の可逆シミュレーションのゴミ出力が必

ク・アンランク計算の可逆シミュレーションを融合すず一致するならば，2 パスの可逆シミュレーションをることで効率的な可逆アルゴリズムを得る．

構成できる [32]．たとえば，この可逆シミュレーショ

本 稿 の す べ て の Janus プ ロ グ ラ ム の 完 全 版 は ，ンを利用して，2 パスの可逆な range coding が実現

われわれのウェブサイト http://tetsuo.jp/ref/

された．また，任意の比較ソートには，ゴミ出力量がJSSST2016/ のリンク先で閲覧することができる．ま最小で 2 パスの可逆シミュレーションが存在する [1]．

た，そのウェブサイトのリンク先に設置された Janus

可逆論理回路の設計では，特定の関数族に適用が可のオンラインインタプリタで実行をして動作を確認

能な可逆シミュレーションが提案されている（たとえすることができる．

ば， [30] を参照）．たとえば，Mealy 機械を用いた手法で in-place に定数倍をする乗算器を生成する方法

2 関連研究がある [23]．

可逆計算の研究が始まった動機のひとつは，計算にこれらの一般解法よりも問題固有の情報を使うこと必要なエネルギー量や発熱量の特定と削減であったで効率的な可逆アルゴリズムを実現できる．挿入整列[11] [21] [4]．非可逆計算における情報の消去には（正法，バブルソート，選択整列法，併合整列法，クイッの）発熱が伴うというランダウアの原理 [20] が観測

クソートといった比較ソートは複数の整列前の入力列されている [5]．一方，可逆計算は情報の消去を原理が同一の整列された出力列となるので非単射であるの的に回避できることが 40 年以上前から知られているで，それらの可逆シミュレーションにはゴミ出力が必[3]．もちろん，現在の電子回路では論理演算以外に多要であるが，最悪ゴミ出力量が最小になる可逆アルゴ

くのエネルギーを費やしているが，論理的状態を微リズムが知られている [22] [9] [25] [1]．Burignat らは，視的状態で実現できると可逆性は重要な特性になる．

動画圧縮規格のひとつである H.264 の符号化器のプ

可逆計算は，量子計算の特別な場合であり，その成果

ロトタイプのチップを作製した [6]．このチップの内部で使用されている効率的な整数変換は可逆である．

行目のように C 言語でも使われる複合代入演算子 +=,可逆計算における元々の問題とは無関係に計算の-=，^= を使わねばならない．ただし，複合代入演算

可逆性は計算機科学において便利な概念である．可子式 x ⊕ = e の左オペランド x で指し示されるオブ

逆計算モデルには，多くの非可逆な計算モデルにそジェクトが右オペランドの式 e に出現してはならず，

れぞれ対応するものが知られている（たとえば，文献

左オペランドが添え字演算子式の場合 (x[ei ] ⊕= e)[35] とその参考文献を参照）．他にも，可逆性は，計算複雑性理論，可逆デバッグ †1 ，プログラム逆変換

はその添え字 ei にも出現してはならない．この制約
は x -= x のような非単射な計算を行う文を記述で[15] [14] [24]，データベースのビュー更新問題や双方向きないようにする．プッシュ push(x,g) は，スタッモデル変換 [12] で有用な性質である．

ク g の先頭へ変数 x の値を追加して x の値を 0 にする．ただし，push(c,g) の c が定数である場合は，そ3 可逆プログラミング言語 Janusの定数の値をスタック g の先頭へ追加する．ポップ

本稿では，命令型可逆プログラミング言語 Januspop(x,g) は，スタック g の先頭から取り除いた値をの拡張版 [31] でプログラムを書いてある（以下，単にゼロクリアされた変数 x に格納する．スタック g のJanus と呼ぶことにする）．Janus は，C 言語に似た先頭要素の値は式 top(g) によって求められる．制御構文に加えて可逆性を保証するための構文要素をも文において制御の合流地点では実行時アサーション

つ．本稿で用いる Janus は，非可逆なプログラムがを使うことで可逆性を保証する．可逆選択文 if e1

記述できない，すなわち単射関数しか表せないというthen s1 else s2 fi e2 は通常の選択文のように動意味で可逆であることが証明されている．

作するが，アサーション e2 の値が then 節が実行さ

例を通して可逆プログラミングを一瞥する．n (≥ 0)
(2n)
1
は漸化式
番目のカタラン数 Bn = n+1
n
6Bn−1
Bn = 4Bn−1 −(n ≥ 1)(1)
n+1
によって効率的に計算できることが知られている（文れた後には真，else 節が実行された後には偽でなけ

献 [18] および文献 [19] の 2.3.4.4 節を参照）．以下のい．do 節 s1 は e1 と e2 の評価の間に，loop 節 s2 は可逆プロシージャは，正整数 n とゼロクリアされた配列 B を受け取り †2 ，カタラン数列 B , B , . . . , B

e2 と e1 の評価の間に実行される．then 節，else 節，

を B[0:n-1] に格納する:される．local 節は，指定した局所変数を指定した式

0

1

n−1

procedure mk_catalan_tbl ( int B [] , int n )B [0] ^= 1
3
local int i = 0
4
from i = 0 do
5i += 16loop
7B [ i ] ^= 4* B [i -1] - 6* B [i -1]/( i +1)
8
until i = n
9delocal int i = n
1
2

Janus の構文と意味論の概要を示す．変数の基本型
は，整数型，整数型の配列とスタックである．Algolで使われるような単純代入 x := 1 は使えず，2, 5, 7
†1 たとえば，https://www.gnu.org/software/gdb/
news/reversible.html, http://caml.inria.fr/
pub/docs/manual-ocaml/debugger.html†2 ゼロクリアとは，変数の値が 0 であったり，配列の全要素の値が 0 であることを意味する．

ればならない．可逆繰り返し文 from e1 do s1 loop

s2 until e2 では，アサーション e1 が，実行前に真，その後は繰り返すごとに偽と評価されなければならな

do 節，および loop 節は，空文のみをもつ場合は省略の値で初期化する．local 節と対になる delocal 節
では，局所変数の値と指定した式の値が等しいことが要求され，局所変数がスコープから除かれる．call
文は，プロシージャを呼び出す．引数は参照渡しされる．uncall 文は，プロシージャの逆呼び出しを行う．
すなわち，call 文とは逆順にプロシージャ本体のそれぞれの文を逆実行する．プロシージャの呼び出し・
逆呼び出しの引数渡しには参照渡しが使われる．
プロシージャmk_catalan_tbl は本体の中のルー
プ が n 回 繰 り 返 さ れ る の で 実 行 時 間 が O(n) であ る ．B0 , . . . , Bn−1 が B[0:n − 1] に 格 納 さ れて い る 場 合 ，プ ロ シ ー ジャ逆 呼 び 出 し uncall

mk_catalan_tbl(B,n) によって B[0:n − 1] はゼロ
クリアされる．

任意の関数 f : X → Y に対して，ある G が存在′するような単純代入式の文 b := 4*b - 6*b/(n+1)

して任意の x ∈ X に対して fst(f (x )) = f (x ) となるは Janus では記述できないので，9–13 行において局

単射関数 f ′ : X → Y × G が存在する．ただし，fst

所変数 b1 の導入とプッシュ文によって不要なデータ

は fst(x, y) = x となる射影関数である．必ずしも単をゴミスタック g に移すことで b に格納されたカタ射にならない関数 f から上記の条件を満たす単射関

ラン数を更新している．さらに，何番目のカタラン数′

数 f を作ることを単射化と呼ぶ．G の要素は，元のを計算しているかを記憶した局所変数 n は 15 行目で関数 f の出力には出現しないことからゴミ出力と呼解放される直前でその不要になった値がゴミスタック

ぶ．特に，G がスタックである場合，G に属するス

g に移されている．このように制御情報と不要データ

タックをゴミスタックという．

を共にゴミスタックに移動させることで，常に埋め可逆言語 R のプログラム q が非可逆言語 IR のプロ込みによる可逆シミュレーションは実現できる．問題

グラム p の可逆シミュレーションであるとは，任意のは，入力される値 b に対して実行時間 O(b) が必要で

RIR

x に対して fst([[q]] (x)) = [[p]] (x) であること，すなRIR

わち [[q]] が [[p]]あるが，メモリもこれに比例した量だけ使用しなけから単射化された関数であることればならないことである．なお，本稿では埋め込みをいう．可逆言語 R の可逆シミュレーション q がク

（Embedding）によって作成されたプロシージャを区

リーンであるとは，q の出力が元の出力のみでゴミが別しやすくするためにその接尾辞に E を用いている．

含まれないこと，すなわち [[q]] : X → Y × 1 のよう

本稿では以下の記法を用いる．コードは typewriter

Rにゴミ出力がユニット型 1 であることをいう．

font で，数式・意味領域の値・メタ変数は italic font

任意の非可逆プログラムに対して，制御情報や消で記す．同じ識別子でも異なるフォントの場合は意去されるデータを計算履歴としてゴミスタックに貯味が異なる．たとえば，変数 i の値を i と記す．長めることによる埋め込みをして，その可逆シミュレー

さ n の配列名 p の配列を p[0:n − 1] と記す．配列

ションを得ることができる．以下は，埋め込みをし

p[0:n − 1] が与えられた場合，p[i : j] は，i ≤ j < nてその後に一部最適化されたプロシージャで，callの場合は配列 p[0:n − 1] の i 番目から j 番目の要素

catalanE(b,g) で呼び出されると，ゴミスタック gの値の列とし，i > j の場合は空列とする．すべてのに不要なデータを貯めながら b 番目のカタラン数を要素が s である部分配列の値を (s, . . . , s) と記す．

求めてその値を変数 b に格納する:
procedure catalanE ( int b , stack g )if b =0 then3b ^= 1 // B0
4
push (0 , g )5else
6
local int n = b7b -= 18
call catalanE (b , g )9local int b1 = b
10push (b , g )11b ^= 4* b1 - 6* b1 /( n +1) // 式 1 より
12
push ( b1 , g )13delocal int b1 = 0
14push (n , g )15
delocal int n = 0
16
push (1 , g )17fi top ( g )=0
1
2

17 行目の選択文のアサーション top(g)=0 は，then

以降では，表記を簡潔にするために，カタラン数
列 B0 , . . . , Bn−1 を格納した配列 B[0:n − 1] の要素
はどこでも読み込めるものとする．

4 二分木とランク計算
本章では，まず本稿で扱う（ラベル無し）二分木の定義を与える．また，二分木を列挙したときの列の添え字に対応するランクの計算方法とその逆にランクに対応する二分木の計算方法を紹介する．さらに，以降の章で用いる二分木の表現である木置換について説明する．これらは基本的に文献 [18] に掲載されたものであり †3 ，次章で議論する効率的な可逆シミュ
レーションのために詳解したものである．

節と else 節のそれぞれ最後のプッシュ文でゴミス
タック g に追加された互いに異なる制御情報によって必ず成立する．また，式 1 の漸化式にそのまま対応†3 文献 [18] では木置換の要素とランクは共に 1 から始まるが，本稿では簡単な記述を目的に 0 から始める．

4. 1 二分木の定義と二分木の順序と節点数対してその列の先頭要素を 0 番目とする添え字がそ（ラベル無し）二分木とは次の 1, 2 によって再帰

れぞれの二分木のランクである．二分木 T に対する的に定義される節点の有限集合 T である．1) T は空rank ′ (T ) は，節点数 |T | の二分木において T に対応集合である．2) または，根としての節点および共通

する B|T | − 1 以下の一意の 0 以上の整数である．

部分を含まない 2 つの集合 Tl , Tr の順に一意に分割され，Tl , Tr は二分木である．Tl , Tr をそれぞれ二分
木 T の左部分木，右部分木と呼び，l(T ), r(T ) と表
す．二分木 T の節点数を |T | と表す．特に，|T | = 0の二分木 T を空木と呼ぶ．
二分木の上に同値関係や順序を定義する．二分木

rank ′ (T ) は再帰関数
rank ′ (T ) = if |T | = 0 then 0 else
( ∑Gj,|T |
0≤j<|l(T )|(5)+ rank ′ (l(T )) × B|r(T )|)+ rank ′ (r(T ))によって計算できる．then 節の項が 0 であることは，

T1 , T2 が一致するとき T1 ≡ T2 と表す．二分木の二空木より小さい木がないことに対応する．else 節の項関係 T1 ≺ T2 は以下のように再帰的に定義される:

3 つの項は，それぞれ

1. |T1 | < |T2 |,(a) |l(T ′ )| < |l(T )|2. |T1 | = |T2 | かつ l(T1 ) ≺ l(T2 ), または
3. |T1 | = |T2 |, l(T1 ) ≡ l(T2 ), かつ r(T1 ) ≺ r(T2 ).

(b) |l(T ′ )| = |l(T )| かつ l(T ′ ) ≺ l(T )(c) l(T ′ ) ≡ l(T ) かつ r(T ′ ) ≺ r(T )≺ は木の上の自然順序と呼ばれる．二分木 T1 , T2 がという条件の二分木 T ′ の数に対応する．条件 (a) を満

T1 ≡ T2 もしくは T1 ≺ T2 であるとき T1 ⪯ T2 と表

たす二分木の左部分木の節点数は j = 0, 1, . . . , l(T )−1

す．⪯ は二分木の上の全順序である．
互いに異なる節点数 n の二分木の集合を T (n) と表す:の範囲になる．第 1 項は，そうした二分木の数 Gj,|T | の和である．第 2 項は，l(T ′ ) ≺ l(T ) を満たす l(T ′ ) の数

rank ′ (l(T )) とそうした各左部分木に対応する右部分
T (n) = {T | |T | = n}(2)

木の数 B|r(T )| の積である．第 3 項は，r(T ′ ) ≺ r(T )T (n) の元の数，すなわち互いに異なる節点数 n の二を満たす r(T ′ ) の数 rank ′ (r(T )) である．条件 (a),分木の数は n 番目のカタラン数 Bn になる．

(b), (c) は互いに排反であり，これらの条件を満たす

節点数が n (≥ 1) で左部分木の節点数が j (≥ 0) である二分木の数を Gjn と表す．このような条件の二分二分木の数の和は T と同じ節点数で T より小さい二分木の数である rank ′ (T ) に一致する．

木の右部分木の節点数は n − j − 1 である．左部分木の特に，二分木 T が同じ二分木を子どもにもったと大きさが与えられたとき，左部分木と右部分木の数のしても，l(T ) が空集合である場合と r(T ) が空集合で積が二分木の数である: G|l(T )|,|T | = B|l(T )| ×B|r(T )| .

ある場合，すなわち左部分木のみをもつ場合と右部分

よって，n > j ≥ 0 となる任意の n と j に対して

木のみをもつ場合ではそれぞれ別の二分木であり，そGjn = Bj × Bn−j−1(3)という関係が成り立つ．

れらのランクが互いに異なることに注意して欲しい．
異なる節点数の二分木が同じランクをもつことはあるが，節点数が与えられた場合はそのような

4. 2 二分木のランク
二分木 T のランク rank ′ (T ) とは，節点数が |T | であり T よりも自然順序で小さい二分木の数である †4 :rank ′ (T ) = #{S | S ≺ T, S ∈ T (|T |)}(4)

こ と は な く，任 意 の n に つ い て rank ′ : T (n) →{0, 1, . . . , Bn − 1} は単射である．したがって，与えられた二分木の節点数とランクを組で返すようにした関数

すなわち，ある一定の大きさのすべての二分木を自然

rank (T ) = (|T |, rank ′ (T ))順序で並べた列を考えた場合，それぞれの二分木には単射である．次章では rank の可逆シミュレーショ
ンを考える．

†4 #X は集合 X の要素数を表す．

(6)

4. 3 ランクから二分木の計算

1

rank は単射なのでその逆関数が存在する．rank (T )/の逆関数 unrank (n, r) は，節点数 n = |T | と T のラ\0

ンク r が与えられたら式 5 の rank ′ (T ) の再帰的定5/義を用いて以下のように T を構成する方法で計算で

\

3

きる．

6
\

もし n = 0 かつ r = 0 であるならば，これらは4

then 節で計算されたものであり，T として空木を構

図1

二分木の例

成して終了する．

else 節で計算されたものについて考える．任意のたとえば，図 1 に示されたランク 49 の二分木に対n (≥ 1) に対して 0 ≤ j ≤ n − 1 なら Gjn > 0 であり，応する木置換は 104235 である．この木置換において，0 ≤ rank (l(T )) および 0 ≤ rank (r(T )) < B|r(T )|1 が根に 0 が左部分木に 4235 の各要素から 1 を減じで あ る こ と か ら ，第 2 項 と 第 3 項 の 和 を B|r(T )|た 3124 が右部分木に対応する．

で割ると商が rank (l(T )), 剰余が rank (r(T )) と一

本稿では，二分木とその木置換による表現を同一視

意に決まる．また，第 2 項と第 3 項の和の最大値

する．次章以降のプログラムでは，節点数 n の（ラベ(B|l(T )| − 1) × B|r(T )| + (B|r(T )| − 1) は G|l(T )|,|T | =ル無し）二分木を配列 p[0:n − 1] に格納された木置

B|l(T )| × B|r(T )| より 1 小さい．したがって，第 1 項

換で表す．特に，空木を表す空の順序組は 1 ≤ a ≤ n

から第 3 項までの和から Gj,|T | を j = 0, 1, . . . の順でを満たす a を用いて空列 p[a : a − 1] で表す．

繰り返し減算を行っていって初めて Gj,|T | 未満になっ文献 [18] のランクおよびアンランクを計算する Al-

た場合の j が |l(T )| である．|r(T )| = |T | − |l(T )| − 1

gol プログラムは入出力される変数を読み替えると次より |r(T )| が求まる．|l(T )| と |r(T )| の情報を用いの条件を満たすプロシージャ rankA および unrankAてそれぞれ rank (l(T )) と rank (r(T )) について以上と見なせる．節点数 n の二分木 T に対応する木置換を再帰的に計算することで得られる l(T ) と r(T ) かが p[0 : n − 1] の場合を考える．この場合，

ら T を構成できる．
′

rank (T ) の then 節と else 節の値は排反ではない
ことに注意して欲しい．ランクが 0 でも節点数が 1以上の場合（r = 0 かつ n ≥ 1 の場合）は else 節に
よって二分木を構成しなければならない．

[[rankA]]Algol : (p[0 : n − 1], n) 7→ (n, r)(7)′となり，r = rank (T ) である．また，節点数 n のラ
ンク r に対して[[unrankA]]Algol : (n, r) 7→ (p[0 : n − 1], n)(8)となり，二分木 T = unrank (n, r) に対応する木置換が p[0 : n − 1] である．次章では rankA と unrankA

4. 4 木置換による二分木の表現の可逆シミュレーションを考える．

本稿では（ラベル無し）二分木を木置換で表現す
る．木置換は，集合 {0, 1, . . . , n − 1} の置換のうち

5 二分木の可逆なランク計算

ある条件を満たしたものである．すなわち，木置換

二分木のランク計算とその逆計算の方法を前章で

p[0 : n − 1] は，0 個の節からなる空木を表す空集合

みた．本章では，まず，Bennett 法 [3] にしたがって，（n = 0）の要素からなる空の順序組であるか，自然

それら 2 つの計算の埋め込みによる可逆シミュレー

数 s と s 未満の要素からなる木置換 pl と s より大きションと，それらの可逆シミュレーションの組み合わい要素からなり各要素から s を減じると木置換になせによる複数パスのクリーン可逆シミュレーションをる pg が連接された spl pg である．s が根に，pl が左実現する．次に，われわれは 1 パスで使用メモリが部分木に，pg の各要素から s を減じたものが右部分少ない可逆シミュレーションを提案する．

木にそれぞれ対応する．

によってゴミスタック g に移す．
// 木置換 p [ a : a +n -1] -( s ,... , s ) の ラ ン ク を r に
2 procedure rE ( int p [] , int n , int a , int s ,int r , stack g )3local int j = 0
4// ( a ) 符 号 化 し た |l(T )|を r に 格 納
5from j = 0 loop
6
r += B [ j ]* B [n -j -1] // Gjn を r に 追 加
7j += 1
8
until j = p [ a ] - s// |l(T )|

1

9
10
11
12
13
14
15
16
17

// ( b ) rank (l(T ))の情報を r に 追 加
if j >= 1 then// |l(T )| ≥ 1の場合
local int r1 = 0
call rE (p ,j , a +1 ,s , r1 , g )r += r1 * B [n -j -1]
push ( r1 , g )delocal int r1 = 0
fi j >= 1

18
19
20
21
22
23

// ( c ) rank (r(T ))を r に 追 加
if n -j -1 >= 1 then// |r(T )| ≥ 1の場合
call rE (p ,n -j -1 , a + j +1 , s + j +1 ,r , g )fi n -j -1 >= 1
delocal int j = p [ a ] - s

24// 木 置 換 p [0: n -1] の ラ ン ク を r に
26 procedure rankE ( int p [] , int n , int r ,stack g )27
call rE (p ,n ,0 ,0 , r , g )28call clear_array (p ,n , g ) // 配列 p を ク リ ア
25

ランクの計算は，補助プロシージャ rE で行われる．
プロシージャ rE は局所変数 j へのメモリの割り当て，
上述の条件 (a), (b), および (c) に対応する 3 つのコー
ド片，ならびに局所変数 j のメモリの解放からなる．
ここで，木置換 p[a : a + n − 1] − (s, . . . , s) に対応す
る二分木を T とする．局所変数 r1 は暫定的なランクを，局所変数 j は T の左部分木の節点数 |l(T )| をそれぞれ記憶するのに用いられる．ここで，8 行目の式

p[a]-s の値は，木置換 p[a : a + n − 1] − (s, . . . , s)の先頭要素であり，T の左部分木の節点数を値としてもつ．
図 2 のプログラムは，単純な埋め込みを行っただけではなく，制御の流れを変えることなく行える最適化を行ってある．たとえば，6 行目では，元のプログラムにおいて代入によって行われていた値の上書きを複合代入演算子 += を用いて実現している．また，ランクを一時的に記憶するための局所変数は 1 箇所のみに使用した．さらに，選択文や繰り返し文のアサー
ションは，それぞれの場所で使用できる変数や配列を

図2

ゴミスタックを使った木置換のランク計算

用いて勘と経験を頼りにして構成することができた．
次節のプログラムでもこうした最適化を断り無く行っ

5. 1 埋め込みによるランク計算ている．

図 2 の 26–28 行目に示された rankE は，rankA のこれらの可逆プロシージャは，元の Algol プロシー

計算履歴を記憶することで Janus の可逆プロシージャ

ジャと比較すると，制御の流れが同じであるために，で実現したものである．この可逆プロシージャでの漸近的な実行時間は任意の入力に対して一致する．し

計算履歴は，具体的には，使わなくなった局所変数とかし，15 行目では，以降では使われないデータがゴ入力された木置換の配列に格納されたデータである．

ミスタック g にプッシュされている．このために実行

プロシージャ呼び出し rankE(p,n,r,g) における引時間に比例したメモリ使用量が追加で必要になってし数は，それぞれ木置換を格納した配列 p, 木置換の長まっている．

さ n, ランクの計算結果を格納するための変数 r, 計算

実行時間を悪化させることでメモリ使用量を削減

途中のゴミ情報を格納するためのゴミスタック g でする最適化は可能ではある．15 行目の push(r1,g)

ある．

をその 2 行前のプロシージャ呼び出しに対応するプ

図 2 の 2–23 行 目 に 示 さ れ た 補 助 プ ロ シ ー ジャ

ロシージャ逆呼び出しに置き換えても元の出力を計

rE(p,n,a,s,r,g) は部分配列の値 p[a : a + n − 1] の算する可逆シミュレーションが実現できる．この実各要素からオフセット s を引いた木置換のランクを計

現は，call-copy-uncall の組み合わせからなる局所的算する．プロシージャ rE の呼び出しによってランク

Bennett 法 [34] を利用しているといえる．プロシー

が変数 r に格納されたのちに，元の出力では必要のな

ジャ呼び出しによって計算された r1 とゴミスタック

いデータである配列 p[0:n − 1] のすべての要素を 28へ追加されたデータが，同一のプロシージャの逆呼び

行目のプロシージャ呼び出し clear_array(p,n,g)出しによって可逆的に消去されるからである．しかし，再帰的にプロシージャが呼び出されるたびに，同// 符 号 化 さ れ た r か ら |l(T )|を j に 抽 出
procedure clT ( int j , int n , int r )from j = 0 loop
れることで，指数的にプロシージャの呼び出しと逆呼 3
4
r -= B [ j ]* B [n -j -1] // r か ら Gjn を減算
び出しの回数が増えてしまい，実行時間が悪化する． 5
j += 1
6
until r < B [ j ]* B [n -j -1]
上記のメモリ使用量の最適化を行ったとしても，
7 // {j = |l(T )|,r = rank (l(T )) × B|r(T )| + rank (r(T ))}一プロシージャが呼び出しと逆呼び出しの 2 回使わ

1rank の可逆シミュレーション rankE をクリーンにす

82// p [ a : a +n -1] に unrank (r, n)+( s ,. . .,s ) を 格 納procedure riE ( int p [] , int n , int a , int s ,int r , stack g )クリアをゴミスタック g を使わずに行わなくてはな
11local int j =0
call clT (j ,n , r )// ( a ) |l(T )|を j にらない．プロシージャrankE の中でのこうした最適化 12

るには，さらに，28 行目で行っている配列 p のゼロ

は，少なくとも配列 p を再度走査することが必要になるので，clear_array の呼び出しを置き換えるだ

9

10

13
14

16

けでは効率的に実現できない．

17
18

rankE が Algol プロシージャ rankA の可逆シミュ 19
レーションになっていることは次のことから確かめ

20
21

られる．節点数 n の二分木 T に対応する木置換が[[rankE]]Janus : (p[0 : n − 1], n) 7→ ((n, r), g)

2223p[0 : n − 1] の場合を考える．この場合，

24

(9)

となり，r = rank ′ (T ) である．ただし，ここで常に0 や nil をとる入出力は省略し，元の出力値は組の中の組で表した．ここで，任意の n と p[0 : n − 1] に対

25

27
28
29
30

32

Janus

fst([[rankE]]

33(p[0 : n − 1], n)) =[[rankA]]Algol (p[0 : n − 1], n)

34

(10)

35
36

であるので，可逆 Janus プログラム rankE は Algol
プログラム rank の可逆シミュレーションである．

// 根 の 設 定

if j >1 then// ( b ) l(T )の構築
local int r1 = r / B [n -j -1] //rank (l(T ))call riE (p ,j , a +1 ,s , r1 , g )push ( r1 , g )delocal int r1 =0
else
if j =1 then// |l(T )| = 1の場合
p [ a +1] ^= s
fi j =1
fi j >1

26

31

して

p [ a ] ^= j + s

15

37
38

if n -j -1 > 1 then// ( c ) r(T )の構築
local int r2 = r % B [n -j -1] //rank (r(T ))call riE (p ,n -j -1 , a + j +1 , s + j +1 , r2 , g )push ( r2 , g )delocal int r2 =0
else
if n -j -1 = 1 then // |r(T )| = 1の場合
p [ a + j +1] ^= j +1+ s
fi n -j -1 = 1
fi n -j -1 > 1
push (j , g )delocal int j =039// ラ ン ク r で 節 点 数 n の 木 置 換 を 計 算
procedure unrankE ( int p [] , int n , int r ,5. 2 埋め込みによるアンランク計算
stack g )42
call riE (p ,n ,0 ,0 , r , g )
図 3 の 41–43 行目に示されているのは，ランク r
43
push (r , g )40

41と二分木の節点数 n から木置換 p[0 : n − 1] を計算するプロシージャ unrankE(p,n,r,g) である．すな

図3

ゴミスタックを使ったランクから木置換の計算

わち，このプロシージャはゴミスタック g を使って
ランク r で節点数 n の木置換をゼロクリアされた配

38 行目で解放する直前に値をゴミスタック g に移動

列 p[0:n − 1] に格納する．同図の 10–38 行目に示ささせる必要がある．したがって，プロシージャ riE のれているのは，長さ n の木置換の各要素にオフセッ

呼び出し回数に比例した大きさのメモリがゴミスタッ

ト s を足したものを部分配列 p[a : a + n − 1] にするクのために必要である．プロシージャ riE の実行後

プロシージャ riE である．これらのプロシージャはに r に格納されている値は初期のランクの値でも 0

文献 [18] の（非可逆に）ランクから木置換を計算すでもない値が格納されている．この値が 43 行目におる Algol プロシージャを計算履歴の埋め込みを行っていてゴミスタック g に移されることで，変数 r はク

Janus の可逆プロシージャで実現したものである．

リアされる．

プロシージャ riE で使われている局所変数 j は，

この埋め込みによる可逆アンランク計算をゴミス

タックを使用しないクリーンなものにするには，局所

2 行目のプロシージャrankE の呼び出しでゴミ情報が的にコードを置き換えるだけでは不十分である．たとg に蓄えられつつ木置換 p[0 : n − 1] に対応するラン

えば，unrankE の本体で push の直前で r に格納されクが r に格納される．t にコピーされたランクとゴている値は，計算の途中で出現した値であり，木置換

ミスタック g に蓄えられたゴミ情報は 4 行目のプロ

p の中身を詳しく見なくては可逆的に消去することがシージャ rankE の逆呼び出しでゼロクリアされる．7

できない．

行目のプロシージャ unrankE の呼び出しでゴミ情報

前節で rankE が Algol プロシージャ rankA の可逆

を g に蓄えながら r に格納されたランクに対応するシミュレーションになっていることを確認したのと同木置換が q に計算される．8 行目で配列 p[0:n − 1]

じように，unrankE が Algol プロシージャ unrankAをゼロクリアされた配列 q[0:n − 1] にコピーするプの可逆シミュレーションになっていることは次のこと

ロシージャ copy(p,q,n) が逆呼び出しされて q がゼから確かめられる．節点数 n の二分木のランク r にロクリアされ，10 行目のプロシージャ unrankE の逆対して呼び出しによって p がゼロクリアされ g の値が nil に: (n, r) 7→ ((p[0 : n − 1], n), g) (11)

される．このように局所的に使われる変数 t，スタッと な り，T = unrank (n, r) に 対 応 す る 木 置 換 がク g, および配列 q, ならびに入力データである配列

p[0 : n − 1] である．ただし，ここで常に 0 や nil

p[0:n − 1] は解放時や実行後にはすべてゼロクリア

をとる入出力は省略し，元の出力値は組の中の組で表

される．

Janus

[[unrankE]]した．ここで，任意の n と r に対してJanus

fst([[unrankE]]

Bennett 法では，関数の可逆シミュレーションとそ
Algol(n, r)) = [[unrankA]](n, r)の逆計算および逆関数の可逆シミュレーションとその(12)

逆計算においてそれぞれ入出力データの走査が必要でであるので，可逆 Janus プログラム unrankE は Algol

あり，出力データのコピーが必要である．また，ゴミプログラム unrankA の可逆シミュレーションである．

データや中間データを格納するメモリが必要である．
これらの点で Bennett 法は時間的にも空間的にも効

5. 3 Bennett 法による可逆シミュレーション率が悪い．

単射関数とその逆関数の可逆シミュレーションを組
み合わせてクリーン可逆シミュレーションを実現する

5. 4 ランク計算のクリーン可逆シミュレーション

Bennett 法が知られている [3]．したがって，Bennett

図 2 と図 3 のプログラムは，着目する部分木の節法を用いると単射関数 rank とその逆関数 unrank を実

点数が 1 のとき以外は，類似した部分がある．条件

現する可逆シミュレーションである rankE と unrankE(a), (b), (c) に対応するコード片同士で，繰り返しやを組み合わせてクリーン可逆シミュレーションが実現

プロシージャの再帰呼び出しが出現しているところ可能である．具体的には，木置換 p[0 : n − 1] から，が類似している．また，rankE で入力される木置換とそのランクが r に格納され，配列 p[0:n − 1] がゼロ出力されるランクが unrankE で入力されるランクとクリアされるという手順で構成される:

出力される木置換と一致する場合，補助プロシージャ

local stack g = nil
call rankE (p ,n ,r , g )3local int t = r
4
uncall rankE (p ,n ,t , g )5delocal int t = 0
6
local int q [ n ] = {0}7call unrankE (q ,n ,r , g )8uncall copy (p ,q , n )9delocal int q [ n ] = {0}10uncall unrankE (p ,n ,r , g )11 delocal stack g = nilrE と riE の呼び出し木が一致する．こうした類似部

12分を共通化して作成したのが図 4 にあるプログラム// t,g をクリア

である．プロシージャunrank は，ランクと二分木の// 全要素を 0 に

節点数から木置換を計算する可逆シミュレーションで// q をクリア

ある．この可逆シミュレーションでは出力されるゴミ// p,g をクリア

情報はない．本節の以下では T は与えられた木置換

p[0 : n − 1] に対応する二分木とする．
実質的な計算は，ゼロクリアされた配列 p[a:a+n-1]

プロシージャ unrank は，前節の Bennett 法の可// 木置換にオフセット s を加えたものを p[a:a+n-1] に
2 procedure ri ( int p [] , int n , int a , int s ,int r )
3
if n >=1 then// |T | ≥ 1 の場合
4
local int j = 0
5call clT (j ,n , r )//(a)6local int r1 = r / B [n -j -1]//(b)7
r -= r1 * B [n -j -1] // {r = rank (r(T ))}8call ri (p ,j , a +1 ,s , r1 )9delocal int r1 = 0
10call ri (p ,n -j -1 , a + j +1 , s + j +1 , r ) //(c)11p [ a ] ^= j + s// 根を設定
12
delocal int j = p [ a ] - s// j は |l(T )|13
fi n >=1
1

14// 節点数 n のランク r の木置換を p[0:n-1] にprocedure unrank ( int p [] , int n , int r )17call ri (p ,n ,0 ,0 , r )15

逆シミュレーションと比べて効率が良い．なぜなら，
配列 p の走査は 1 回だけであり，中間データを記憶する t や q といった局所変数やゴミデータを記憶するスタックが不要であるからである．
ランク計算は，逆変換されたプロシージャunrankの呼び出しかプロシージャunrank の逆呼び出しで実現できる．
副次的な成果であるが，unrank は文献 [18] のアン
ランク計算をするプロシージャより使用している局所変数の数が少なく行数も少ないという点で効率的で

16

図4

アンランク計算のクリーン可逆シミュレーション

簡潔なものになった．

5. 5 提案する可逆シミュレーションの計算複雑度
本稿のアルゴリズムの基になっている Knott によにランク r の木置換の各要素にオフセット s を加算る非可逆なランク計算およびその逆計算 [18] は，木置したものを格納するプロシージャri(p,n,a,s,r) に換の長さを n として計算時間が O(n2 ) であることがよって以下のように行われる．

知られている [10]．したがって，これらの埋め込みに

n が 0 の場合，すなわち |T | = 0 の場合は，空列
p[a : a − 1] が求めたい木置換であり，何もせず計算を終える．

よって作成された図 2 の rankE と図 3 の unrankE の計算時間も O(n2 ) である．
以下の考察から図 4 の unrank の計算時間も O(n2 )n が 1 以上の場合，すなわち |T | ≥ 1 の場合は，次である．ri の第 2 引数の値 n は構築する木置換の長のように再帰的に木置換を構築する．図 3 で定義ささを表している．ri は長さが j と n − j − 1 の木置れたプロシージャclT(j,n,r) の呼び出しにより，符換をそれぞれ 8 行目と 10 行目で構築している．また，号化された r から |l(T )| を抽出して j に格納し，条

5 行目のプロシージャclT の本体では，12 行目で解放

件 (a) を満たす二分木の数を r から減ずる．r1 をされるときに指定される値である |l(T )| の回数だけ

rank (l(T )) に初期化し，条件 (b) を満たす二分木の繰り返しが行われる．ここで 0 ≤ |l(T )| ≤ n − 1 であ数を r から減じてその値を rank (r (T )) にする．プる．したがって，ri の最悪実行時間 T (n) に関して

ロシージャri の再帰呼び出しにより，左部分木 l(T )T (n) =に対応する木置換 p[a+1:a+n-j-2] の各要素にオフという漸化式が得られる．よって

セット s を加算した配列を構築し，r1 をゼロクリア

T (n) ≤

する．同様に，10 行目におけるプロシージャ ri の再であるが，これは入力される配列の大きさが n のク

帰呼び出しにより，右部分木 r(T ) に対応する木置換

イックソートの計算時間に関する不等式に一致する

max (T (j) + T (n − j − 1) + Θ(j)) (13)0≤j≤n−1max (T (j) + T (n − j − 1)) + Θ(n) (14)0≤j≤n−1

p[a + j + 1 : a + n − 1] を構築し，r をクリアする． （文献 [7] の 7.4.1 節）．したがって，可逆な二分木のこのとき r の保持していた値 rank (r (T )) は条件 (c)ランク計算 rank は最悪実行時間が O(n2 ) となる．一

を満たす二分木の数である．木置換の根に対応する

方，式 13 の max において常に j が最大値を取る場合，

要素 p[a] には，左部分木の節点数 |l(T )| にオフセッ

すなわちすべての節が左の子のみをもつ場合を考え

ト s を加算したものが格納されている．したがって，

ると実行時間は Θ(n2 ) である．したがって，unrankj = p[a] − s であるが，この情報を用いて j の割り当の最悪実行時間は T (n) = Θ(n2 ) である．

てを解放する．

クリーンな可逆プロシージャ unrank は，以下の意

味で unrankA に対して最適な可逆シミュレーションである．可逆シミュレーションが，ゴミ出力が有界
で，かつ任意の入力に対して元の非可逆プログラム
よりも計算複雑度が同じかそれ以下で追加のメモリの大きさが入力 x の大きさ |x| に対して g(|x|) 以下
である場合は，g によって押さえられるゴミを用いた

faithful な可逆シミュレーションと呼ばれる [1]．また，
g によって抑えられるゴミを用いた faithful な可逆シ
ミュレーションよりもゴミ出力の大きさが漸近的に小さいものが存在しないとき，その可逆シミュレー
ションを hygienic と呼ぶ [1]．プロシージャ unrank
は，ゴミ出力が無く，任意の入力に対してランク計算

unrankA と計算複雑度が同じで，追加のメモリが必
要ないので，定数関数で抑えられる hygienic な可逆シミュレーションである．

6 まとめ
Knott のランク・アンランクのプログラム [18] について一般的な Bennett 法による可逆シミュレーショ
ンよりも時間的にも空間的にも効率的な可逆シミュ
レーションを提案した．特に空間計算量はオーダーでも効率的になり，可逆シミュレーションは時間的にも空間的にも元の非可逆なアルゴリズムと漸近的には同じ効率になった．これは，ランク・アンランク計算
をよく解析してそれらの冗長部分を融合できたことによる．
副次的な結果として元のアンランクプログラム

unrankA よりも計算ステップ数が少ない可逆プログ
ラムが得られたが，これはプログラムと逆プログラム
から可逆プログラムを作成する際に得られる知見がより効率的なプログラム・逆プログラムの作成に役立つ可能性を示唆している．
謝辞 本研究は JSPS 科研費 25730049 の助成を受けたものである．

参 考 文 献[ 1 ] Axelsen, H. B. and Yokoyama, T.: Programming
Techniques for Reversible Comparison Sorts, Programming Languages and Systems, Feng, X. andPark, S.(eds.), Lecture Notes in Computer Science,Vol. 9458, Springer-Verlag, 2015, pp. 407–426.

[ 2 ] Baker, H. G.: NREVERSAL of Fortune — The
Thermodynamics of Garbage Collection, International Workshop on Memory Management. Proceedings, Bekkers, Y. and Cohen, J.(eds.), Lecture Notes in Computer Science, Vol. 637, SpringerVerlag, 1992, pp. 507–524.
[ 3 ] Bennett, C. H.: Logical Reversibility of Computation, IBM Journal of Research and Development,
Vol. 17, No. 6(1973), pp. 525–532.
[ 4 ] Bennett, C. H. and Landauer, R.: The Fundamental Physical Limits of Computation, Scientific
American, Vol. 253, No. 1(1985), pp. 48–56. Bennett, C. H., and Landauer, R. (唐木幸比古訳): 計算の物理的な限界はあるか？, サイエンス, Vol. 9(1985),
pp. 104–114.
[ 5 ] Bérut, A., Arakelyan, A., Petrosyan, A.,
Ciliberto, S., Dillenschneider, R., and Lutz, E.:
Experimental verification of Landauer’s principle
linking information and thermodynamics, Nature,
Vol. 483(2012), pp. 187–189.
[ 6 ] Burignat, S., Vermeirsch, K., Vos, A. D., andThomsen, M. K.: Garbageless Reversible Implementation of Integer Linear Transformations, Reversible Computation. Proceedings, Glück, R. andYokoyama, T.(eds.), Lecture Notes in Computer
Science, Vol. 7581, Springer-Verlag, 2013.
[ 7 ] Cormen, T. H., Leiserson, C. E., Rivest, R. L.,
and Stein, C.: Introduction to Algorithms, The MIT
Press, 3rd edition, 2009.
[ 8 ] De Vos, A.: Reversible Computing: Fundamentals, Quantum Computing, and Applications,Wiley-VCH, 2010.
[ 9 ] Early, D., Gao, A., and Schellekens, M.: Frugal Encoding in Reversible MOQA: A Case Study
for Quicksort, Reversible Computation. Proceedings, Glück, R. and Yokoyama, T.(eds.), Lecture
Notes in Computer Science, Vol. 7581, SpringerVerlag, 2013, pp. 85–96.
[10] Er, M. C.: Enumerating ordered trees lexicographically, The Compututer Journal, Vol. 28,
No. 5(1985).
[11] Feynman, R. P.: Reversible computation andthe thermodynamics of computing (chapter 5),
Feynman Lectures on Computation, Hey, A. J. G.
and Allen, R. W.(eds.), Addison-Wesley, 1996,
pp. 137–184. Feynman, R. P. (Hey, A. J. G., Allen,
R. W. 編, 原康夫，中山健，松田和典訳): ファインマ
ン計算機科学, 第 5 章「可逆計算と計算の熱力学」, 岩波書店, (1999).
[12] Foster, J. N., Greenwald, M. B., Moore, J. T.,
Pierce, B. C., and Schmitt, A.: Combinators for BiDirectional Tree Transformations: A Linguistic Approach to the View Update Problem, ACM Transactions on Programming Languages and Systems,
Vol. 29, No. 3(2007), pp. 1–65.
[13] Frank, M. P.: Reversibility for Eﬃcient Computing, PhD Thesis, Massachusetts Institute ofTechnology, 1999.

[14] Glück, R. and Kawabe, M.: Derivation of deterministic inverse programs based on LR parsing,
Functional and Logic Programming. Proceedings,
Kameyama, Y. and Stuckey, P. J.(eds.), Lecture
Notes in Computer Science, Vol. 2998, SpringerVerlag, 2004, pp. 291–306.
[15] Gries, D.: The Science of Programming, Texts
and Monographs in Computer Science, SpringerVerlag, 1981, chapter 21 Inverting Programs,
pp. 265–274.
[16] Gruska, J.: Quantum Computing, McGraw-Hill,
1999.
[17] James, R. P. and Sabry, A.: Information eﬀects,
Principles of Programming Languages. Proceedings,
ACM Press, 2012, pp. 73–84.
[18] Knott, G. D.: A numbering system for binary trees, Communications of the ACM, Vol. 20,
No. 2(1977), pp. 113–115.
[19] Knuth, D. E.: The Art of Computer Programming, Volume 1: Fundamental Algorithms, Vol. 1,
Addison-Wesley Professional, 3rd edition, 1997.
[20] Landauer, R.: Irreversibility and Heat Generation in the Computing Process, IBM Journal of
Research and Development, Vol. 5, No. 3(1961),
pp. 183–191.
[21] Landauer, R.: Information is Physical, Physics
Today, Vol. 44, No. 5(1991), pp. 23–29. Landauer,
R. (小柳義夫訳): 情報は物理過程だ, パリティ, Vol. 6,
No. 11(1991), pp. 30–39.
[22] Lutz, C.: Janus: A time-reversible language,
1986. Letter to R. Landauer.
[23] Mogensen, T. Æ.: Garbage-Free Reversible Multipliers for Arbitrary Constants, ACM Journal
on Emerging Technologies in Computing Systems,
Vol. 11, No. 2(2014), pp. 1–18.
[24] Nishida, N., Sakai, M., and Sakabe, T.: Partial Inversion of Constructor Term Rewriting Systems, Term Rewriting and Applications. Proceedings, Giesl, J.(ed.), Lecture Notes in Computer Science, Vol. 3467, Springer-Verlag, 2005, pp. 264–278.
[25] Perumalla, K. S.: Introduction to Reversible
Computing, CRC Press, 2013.
[26] Pesu, T. and Phillips, I.: Real-Time Methods
in Reversible Computation, Springer International
Publishing, 2015, pp. 45–59.
[27] Saeedi, M. and Markov, I. L.: Synthesis and Optimization of Reversible Circuits — A Survey, ACM
Computing Survey, Vol. 45, No. 2(2013), pp. 21:1–
21:34.
[28] Sprugnoli, R.: The Generation of Binary Trees
as a Numerical Problem, Journal of the ACM,
Vol. 39, No. 2(1992), pp. 317–327.
[29] Thomsen, M. K., Axelsen, H. B., and Glück,
R.: A Reversible Processor Architecture and Its
Reversible Logic Design, Reversible Computation.
Proceedings, De Vos, A. and Wille, R.(eds.), Lecture
Notes in Computer Science, Vol. 7165, Springer-

Verlag, 2012, pp. 30–42.
[30] Wille, R. and Drechsler, R.: Towards a Design
Flow for Reversible Logic, Springer-Verlag, 2010.
[31] Yokoyama, T., Axelsen, H. B., and Glück,
R.: Principles of a Reversible Programming Language, Computing Frontiers. Proceedings, ACM
Press, 2008, pp. 43–54.
[32] Yokoyama, T., Axelsen, H. B., and Glück, R.:
Optimizing Clean Reversible Simulation of Injective
Functions, Journal of Multiple-Valued Logic andSoft Computing, Vol. 18, No. 1(2012), pp. 5–24.
[33] Yokoyama, T., Axelsen, H. B., and Glück, R.:
Towards a Reversible Functional Language, Reversible Computation. Proceedings, De Vos, A. andWille, R.(eds.), Lecture Notes in Computer Science,Vol. 7165, Springer-Verlag, 2012, pp. 14–29.
[34] Yokoyama, T. and Glück, R.: A Reversible
Programming Language and Its Invertible SelfInterpreter, Partial Evaluation and SemanticsBased Program Manipulation. Proceedings, ACM
Press, 2007, pp. 144–153.
[35] 森田憲一: 可逆計算, 近代科学社, 2012.

A 補助プロシージャ
本章では，本稿中に用いた補助プロシージャを示す．
可逆プロシージャclear_array は，配列 p[0:n−1]の値をゴミスタック g に移す．
procedure clear_array ( int p [] , int n ,stack g )2
local int i = 0
3
from i = 0 do
4
local int t = p [ i ]5p [ i ] ^= t // クリア
6
push (t , g )7delocal int t = 08i += 1
9
until i = n
10
delocal int i = n
1

可逆プロシージャcopy は，x[0:n−1] を y[0:n−1]に排他的論理和の複合代入演算子を用いて可逆的にコピーする．したがって，x[0:n − 1] と y[0:n − 1] の全要素が同一の値を格納している場合は y[0:n − 1]をゼロクリアする．copy は呼び出しと逆呼び出しとで振る舞いは変わらない．
procedure copy ( int x [] , int y [] , int n )local int i = 0
3
from i = 0 do
4y [ i ] ^= x [ i ]5i += 1
6
until i = n
7
delocal int i = n12