再帰的ブロック構造を持つ並列プログラムに対する可逆実行環境

本論文では，並列に実行されるブロック構造を持つプログラムの実行を解析することを目的とした可逆実行環境を示す．並列プログラムを抽象機械のバイトコード列に変換して実行する．順方向の実行時は逆向き実行に必要な情報をスタックに保存し，その実行を逆向きにたどる実行環境を実装する．この実行環境では，順方向の抽象命令を逆方向の抽象命令を逆順とし，ジャンプ命令と変数更新命令を対応する逆方向の命令に変換することで逆向き実行を実現する．筆者らはバイトコードによる実行環境複数の抽象機械でバイトコードを順方向および逆方向の2つのモードで並行実行する実行環境をPythonのmultiprocessingモジュールによって実現した．本論文では，実際的なプログラムの構文要素として，ブロック構造，手続き呼出し，関数呼出しを含むように拡張した．Hoeyらの手法に従って変数のスコープを扱うために，各ブロックに名前を付け，参照情報をパスとして表し，局所変数を実現する．本研究で新たに提案する方法として抽象命令生成時に作成する並列ブロックの開始および終了番地を記録したテーブルを用いて並列ブロックを起動することにより順方向，逆方向ともに並列の入れ子構造を実現する．これらの実現手法によって，ブロック構造を持つプログラミング言語に対して単純な抽象機械の実行メカニズムによって逆方向実行が可能となることを示し，並列プログラムのデバッグのための基盤として提案する．

This paper presents a reversible runtime of simple parallel programs with blocks. A program is translated into a sequence of three-address abstract machine instructions and abstract machines running in parallel execute the instructions. The runtime stores the information of variable updates and program counter jumps associated with process identifies on stacks in the forward execution. In the backward execution, the abstract instructions for forward execution are executed in the reversed order with jump and update instructions altered to the corresponding instructions. In our previous work, we presented a runtime for parallel programs with flat-fixed structures. The runtime concurrently executes multiple abstract machines in the forward and backword modes using the multiprocessing module of Python. This paper extends the runtime for practical language features, including blocks, procedure-call, and function-call. To deal with the scope of variables in blocks, we assign the path information with block names following Hoey et al. Besides variable paths, the runtime records the invocation history of parallel blocks as a table to reverse the invocation of parallel blocks. We realize parallel nested structures in both directions. We illustrate that executing abstract machines makes bi-directional execution simple even with the recursive structure of blocks. We propose them as a foundation for behavioural analysis such as debugging.