参照をサポートするインクリメンタルステッパの実装
秋山 雛乃, 浅井 健一
お茶の水女子大学{akiyama.hinano, asai}@is.ocha.ac.jp
概 要
本研究では、OCaml プログラムの計算過程を１ステップごとに出力するプロ
グラムであるインクリメンタルステッパを拡張して、これまでは不十分であった参照をサポートする。先行研究では、インクリメンタルではない OCaml ステッパでの参照の実装は行われていたが、インクリメンタルステッパへの対応には課題が残っていた。参照をインクリメンタルステッパに対応するための課題となった点は、ロケーション状況
を入力プログラムとして OCaml で読み込める形で表現することと、インクリメンタル
ステッパにすることで全ての状態を出力しなければいけない必要性が出てきたことである。本研究では、一つ目の課題に対してはロケーション状況の表示を内部では任意の型を持ちうる式に参照の情報を付与したものを用いることで、二つ目の課題に対してはロケーション状況とその先の値の対応をプログラムに attribute として付与することで解
決した。

1

はじめに

プログラマがプログラムを理解する方法として、プログラムを１ステップごとに書き下す方法がある。しかし、初学者にとって自分の手でプログラムの書き下しを行うことは困難である。そこで、プログラム実行の流れを書き下すステッパというツールが開発された。本研究では、OCaml を対象言語としたステッパであるインクリメンタルステッパに参照の構文をサポートすることを目指す。
参照は実際にお茶の水女子大学の関数型言語の授業で扱われる機能であり、初学者用のステッパとして対応する必要があると考える。
本論文は、インクリメンタルステッパに比較的、素直に参照を導入できたのでその模様を報告するものだが、合わせてインクリメンタルステッパ自身も（我々のグループの修士論文 [1] 以外では）未発表なので、それについても紹介する。この先、OCaml ステッパとインクリメンタルステッパの概要と参照を実装する際の問題点を概観し、ふたつの実装上の課題について述べる。続いて、一つ目の課題の解決手法を 2 節で示し、二つ目の解決手法を 3 節で示す。その後、4 節にてインクリメ
ンタルステッパの現状について、5 節にて関連研究について触れ、6 節でまとめる。

1.1

OCaml ステッパとインクリメンタルステッパ

まず我々のグループで開発された OCaml ステッパと OCaml ステッパを発展させたインクリメ
ンタルステッパについて説明する。OCaml ステッパ [2] は、入力として型チェックの通ったプログ
ラムを受け取り、プログラムの計算過程を１ステップごとに出力する。使用者は普段通りにプログ
ラミングを行い、エディタ上のボタンを操作することで、プログラムを最初から最後までステップ実行していく流れを確認することができる。ステッパの実装の手間を軽減するため、既存の OCaml
コンパイラをなるべく再利用して実装しており、特に OCaml コンパイラのパーザや型検査器に変更は加えず、ステップ実行を行う部分のみで必要な情報を全て得ることができるようにしている。
例えば、税抜き価格を受け取ったら、税込み価格を返す関数 shohizei は以下のように定義されるが、let shohizei x = (x * 110) / 1001（授業で時々見られる間違いとして）以下のように割り算を先に計算するように書いてしまった時、

let shohizei x = x * (110 / 100)
税抜き 100 円の税込み価格を求める計算をステッパで実行すると以下のようになる。

(* Step 0 *) let test = (shohizei 100)(* Step 1 *) let test = (100 * (110 / 100))(* Step 1 *) let test = 100 * (110 / 100)(* Step 2 *) let test = 100 * (1)(* Step 2 *) let test = (100 * 1)(* Step 3 *) let test = (100)
ここで、Step 1 から Step 2 にかけて、110 / 100 が 1 となってしまい想定の結果が得られていないことを確認できる。このように、自分の想定の計算結果と異なる箇所を視覚的に理解することができるため、デバッグにおいて初学者には有用なツールとなっている。また、計算される箇所はハ
イライトでわかるようになっている。ハイライト機能の実装方法は 1.3 節で詳しく示す。
OCaml ステッパの内部では、インタプリタにステップ出力機能を追加したものに対して、入力
プログラムを渡し、全てのステップの文字列を生成する。そして、プログラムを全て実行するか、
ステップ数の上限に達すると実行を終了し、ユーザには最初のステップを表示する。その後ユーザの操作に従って表示を行う。例として以下のような OCaml プログラムを考える。

let a = 3 + 5 * 7
OCaml ステッパでは以下のような実行結果となり、(* Step 0 *) let a = 3 + ( 5 * 7 )(* Step 1 *) let a = 3 + ( 35 )(* Step 1 *) let a = ( 3 + 35 )(* Step 2 *) let a = ( 38 )ユーザには、以下が出力される。

(* Step 0 *) let a = 3 + ( 5 * 7 )(* Step 1 *) let a = 3 + ( 35 )そして、ユーザから次のステップを表示する命令が来ると、次の Step 1 から Step 2 が出力される。
OCaml ステッパはプログラムの実行が終わるまでユーザへの出力ができないため、長い OCaml
プログラムを入力した際に実行時間が長くなる1 ことや、無限ループをするプログラムだった場合、（ステップ数を適当なところで打ち切るなどをしないと）ステッパを使用できない課題があった。無限ループに対処する際、同じ式が無限に繰り返される様子を観察できるなど、ステッパは無限ループの解消にも有用なツールであると考え、OCaml ステッパと表面上は同じ動作をするが、内部での処理方法や速度が大きく異なるインクリメンタルステッパが開発された。 [1, 第 5 章]
インクリメンタルステッパは、インタプリタにステップ出力機能を追加したものに対して、入力
プログラムを渡し、１ステップの簡約を計算したら直ちにそのステップを出力する。出力後は続きを実行するのではなくプロセスを終了する。ユーザから次のステップを表示するなどの命令が指示され次第、前回の出力の一部を新しい入力として受け取り次の１ステップを実行する。例えば、先ほどの例のプログラムをインクリメンタルステッパで実行すると、
1
例えば、ダイクストラ法を使った最短路問題のプログラムなどをステップ実行すると、結果が出るまでかなりの時
間、待たされる。

2

(* Step 0 *) let a = 3 + ( 5 * 7 )(* Step 1 *) let a = 3 + ( 35 )の１ステップを出力し、直ちにプロセスを終了する。ユーザから次のステップを表示するという命令が来たとき、Step 2 を出力するために、外部のプログラムが現在のステップが Step 1 であるという情報と現在のプログラムが let a = 3 + 35 という部分を抜き出して再度ステッパに入力する。
この時、インクリメンタルステッパが次のステッパに渡すプログラムは完全なプログラムである
必要性と、コメントとして書かれているステップ数に関しても次のステップに引き継ぐ必要性に注意する。インクリメンタルステッパは１ステップごとに結果を出力するとプロセスを終了する。そして次のステップを実行する際、その前のステップで出力されたプログラムを OCaml コンパイラ
で構文解析して読み込む。そのため、ステッパによって出力される OCaml の式が OCaml コンパ
イラで構文解析可能である必要がある。また、ステップ数に関してはユーザに見せる際にはコメン
トで出力しているが、コメントは次のステップで読み込む時 OCaml コンパイラには無視されてしまう。コメントを構文解析するために新たにプログラムを書くことを避けるため、インクリメンタ
ルステッパでは上手にステップ数を引き継ぐ必要がある。

1.2

OCaml の attribute

OCaml 4.02 以降では、OCaml の構文木の中に情報を attribute という形で付与することができる。attribute は名前と OCaml のプログラムやシグネチャなどの引数を持ち、attribute の中身についても構文木として構文解析や pretty printing が可能となっている。また、attribute を付与す
る対象は式だけでなく、型定義やプログラム自体にも付与することができる。
まず、式 e に OCaml プログラム P を引数に持つ name という名前の attribute を付与した式は
e[@name P] と表記する。例えば、let f n = n + 1 という OCaml の式がある時、n に名前 attr
で"integer"というプログラムを付与すると、let f n = n[@attr "integer"] + 1 となる。
次に、プログラム全体に付与する attribute について説明する。OCaml のプログラムは structure
item のリストであり、structure item には式や変数定義、型定義、モジュール定義、attribute な
どの種類がある。プログラム全体へ付与する attribute は structure item のリストに structure item
である attribute を追加する形で付与する。表記方法は、name という名前で P というプログラムを付与する時、[@@@name P] となる。例えば、以下のプログラムに
let a = 1 + 5 + 9
step という名前で 1 というプログラムを付与すると、以下のようになる。
[@@@step 1]
let a = 1 + 5 + 9
入力プログラムに attribute があると構文解析されて構文木になるが、特別なことをしない限り
attribute は無視される。ここでは attribute を実行することはせず、単に情報伝達の手段として用
いる。

1.3

ステッパでの attribute の使用

OCaml ステッパでは、attribute の構文解析や pretty printing が可能という点を生かして、ユー
ザにわかりやすく計算過程を伝えるためのハイライト機能や、インクリメンタルステッパにおいて次のステップで入力として受け取るためのプログラムを作成する機能を実装している。

3

(* Step 0 *)let a = (4 + 2) * ((8 - 1)[@x ])(* Step 1 *)let a = (4 + 2) * ((7)[@t ])(* Step 1 *)let a = ((4 + 2)[@x ]) * 7(* Step 2 *)let a = ((6)[@t ]) * 7(* Step 2 *)let a = ((6 * 7)[@x ])(* Step 3 *)let a = ((42)[@t ])(* Step 0 *)let a = (4 + 2) * (8 - 1)(* Step 1 *)let a = (4 + 2) * (7)(* Step 1 *)let a = (4 + 2) * 7(* Step 2 *)let a = (6) * 7(* Step 2 *)let a = (6 * 7)(* Step 3 *)let a = (42)

図 1: OCaml ステッパの結果

図 2: ユーザが見る結果

OCaml ステッパでは、ステップ実行の前の簡約される式に [@x ] を、ステップ実行後の簡約された式に [@t ] を付与することで、ユーザがみる結果にハイライトがつくような処理を行っている。2
この時、初学者が自分で書いたプログラムがどのように実行されているかのみを確認することができるように、ユーザがみる結果では attribute が指す部分をハイライトした上で、attribute 自身は削除している。例えば、let a = (4 + 2) * (8 - 1) というプログラムを OCaml ステッパで実行すると、ステッパ内部では図 1 となり、ユーザには図 2 のようなハイライトがついた状態で表示される。
インクリメンタルステッパでは、ハイライトの他に、インクリメンタルにしたことで起こる情報の欠落に対して、attribute を用いて解決した。OCaml ステッパでは実行結果が既に全て作成されており、ステップ数に関しては、ステッパのプログラム内のグローバル変数を用いて表示が行われている。それに対して、インクリメンタルステッパではユーザから次のステップを表示する命令が来ると、その前のステップで出力されたプログラムを入力として受け取る。この時、ステップ数や現在のプログラムを [@@@stepper.process ....] という attribute としてプログラムに付与し、次のステップを計算する際は付与した attribute をもとに計算することにした。
例えば、以下のプログラムをインクリメンタルステッパで実行すると
let a = (4 + 2) * (8 - 1)
以下のようにステッパの内部では出力される。

(* Step 0 *) [@@@stepper.process[@@@stepper.counter 0]
let a = (4 + 2) * (8 - 1)]
let a = (4 + 2) * ((8 - 1)[@x ])(* Step 1 *) [@@@stepper.process[@@@stepper.counter 1]
let a = (4 + 2) * 7]
let a = (4 + 2) * ((7)[@t ])2

x は redex の略、t は reduct の略である。ステッパの出力は OCaml の pretty printing を使っているが、短い名前の attribute にすることで（ハイライトするために）attribute を削除した後に改行などが不自然にならないようにしている。

4

[@@@stepper.process ...] の中の [@@@stepper.counter ...] がその時点のステップ数を表し、その下のプログラムがその時点のプログラムを表している。（上の例の場合、次のステップの実行に必要なのは Step 1 の [@@@stepper.process ...] のみだが、現在の実装では各ステップにこの情報を付与している。）次のステップを表示する命令が来た時、[@@@stepper.process ...] の中身である以下のようなプログラムが入力としてインクリメンタルステッパに渡される。
[@@@stepper.counter 1]
let a = (4 + 2) * 7
このように [@@@stepper.process ...] の部分は、次のステップの情報を得るのに使われるが、この部分はユーザには見せず、ユーザにはこれまで通りのステップ実行結果のみを見せる。なお、本論文では、以降の節でインクリメンタルステッパの出力に付与されている [@@@stepper.process...] や [@@@stepper.counter ...] は省略して表記する。

1.4

参照とは

次に本研究でインクリメンタルステッパにサポートする参照について説明する。参照とは、書き換え可能なフィールドを一つだけ持つものを指し、生成・書き換え・中身の取り出しの３つの動作を行う。参照の生成は ref 関数で行われる。ref 関数は参照先に格納する初期値を引数としてとり、そこへの参照を返す。参照は、内部的にはそのデータのロケーション（アドレス）を持つデータである。参照から格納された値を取り出すのには前置演算子!を使用する。そして、参照の書き換え（もしくは代入とも呼ばれる）には中置演算子:=を使用し、左に置かれた式を評価した結果の参照に、右に置かれた式の評価結果を代入する。代入を行った式全体の値は () になる。 [3]以下の OCaml プログラムを例に説明する。

let a = ref 1
let b = !alet c = a := 3
let d = !a
1 行目の ref 関数により参照の生成が行われ、初期値が 1 となる。そして 2 行目にて参照の取り出しが行われ、変数 b の値は初期値の 1 となる。その後、3 行目にて参照の格納が行われ、参照 a の値は 3 になる。そのため、4 行目で参照の取り出しを行った結果は 3 となる。

1.5

参照実装の問題点

参照をインクリメンタルステッパに対応するために問題となった点は、ロケーション状況を入力
プログラムとして OCaml で読み込めない点と、インクリメンタルステッパにすることで全ての状態を出力しなければいけない必要性が出てきた点である。
例として、以下の OCaml プログラムを考える。

let a = ref 1
let b = !aOCaml ステッパでは、以下のような実行結果となる。
(* Step 0 *) let a = (ref 1)(* Step 1 *) #1: 1 let a = (#1)(* Step 1 *) #1: 1 let b = ! (a)(* Step 2 *) #1: 1 let b = ! (#1)(* Step 2 *) #1: 1 let b = (!(#1))(* Step 3 *) #1: 1 let b = (1)52 行目の式の前にある「#1: 1」はその時点のロケーション状況とそれに対応する値を表している。
（実際には適宜、改行が入り、もう少し見やすい表示になる。）そして式の中で青くなっている「#1」はロケーション状況を表している。この記法は我々のステッパ独特で OCaml の構文ではない。これは「ステッパを使うのには OCaml のプログラムのこと以外を知る必要がない」というステッパのメリットを損なう恐れがある。
OCaml の構文のみを使って参照を表現するには、例えば call-by-need の定式化 [4, 5] に用いられているように、let 文で共有情報を表現することなども考えられる。しかし、このようにしても複雑な表現になってしまうことは避けられず、初心者に分かりやすいものとなるとは考えにくい。ここでは、参照を理解するにはロケーション情報の理解は避けられないと考えて、ロケーションという概念（のみ）を導入してステップ実行することにした。
上記のステップ実行に際しては、さらに次のようなことが行われている。まず、参照を使ったプ
ログラムの実行には、ロケーションとそこに入っている値の情報が必要である。これは、グローバ
ル変数 ref_env を用いて管理されており、書き換えが行われるたびにグローバル変数の中身を変更している。次に、参照の値がロケーションになったとき、それを #1 のように表示する必要がある。
プログラムの表示には OCaml コンパイラの pretty printer をそのまま使用しているため、ロケー
ションについてもうまく表示できるようにしなくてはならない。以前の OCaml ステッパでは無理
矢理 "#1" という名前の変数の構文木を使っていたが、インクリメンタルステッパではこの方法は使えず、別の方法をとっている。これについては後に詳しく述べる。
一方、インクリメンタルステッパで上のプログラムをステップ実行すると、まず以下の１ステップを出力する。
(* Step 0 *) let a = ref 1(* Step 1 *) #1: 1 let a = (#1)
その後、ユーザから次のステップを表示する命令がきたとき、以下のプログラムがステッパの入力となる。

let a = #1
let b = !a
この時点で多くの問題が発生する。まず、このプログラムは # の部分でシンタックスエラーが起きてしまう。これは、1.1 節で説明した、次のステップの計算を行う時の入力プログラムが完全なプログラムになっていないことが原因である。これが、一つ目の課題である、ロケーション状況を入力プログラムとして OCaml で読み込めない点である。次に、たとえ #1 という表記をプログラム
として読み込み可能であり、参照の意味を有したデータにできたとしても、Step 2 から Step 3 にかけて行われる参照の中身の取り出しの動作のとき、#1 という参照の参照先の値が 1 であるという情報が引き継がれていないため、中身を取り出すことができない。これは、1.3 節で示した次のス
テップへのプログラムを attribute として残す際に参照と参照先の値の情報が attribute として付与されていないことが原因である。これが二つ目の課題である、インクリメンタルステッパにしたことで、全ての状態を出力しなければいけない点である。
本研究では、一つ目のロケーション状況を入力プログラムとして OCaml で読み込めないという課題に対して、ロケーション状況の表示を内部では任意の型を持ちうる式に参照の情報を付与したものを用いることで、二つ目のインクリメンタルステッパにしたことで、全ての状態を出力しなけ
ればいけないという課題に対して、ロケーション状況とその先の値の対応をプログラムに attributeとして付与することで解決した。

62

任意の型を持ちうる式への変換

一つ目の課題であるロケーション状況を入力プログラムとして OCaml で読み込めない点に対して本研究では、ロケーション状況を• OCaml で読み込み可能• 任意の型を持ちうる• 参照の情報を attribute として持つ
ようなデータとして表現する。参照に対応する値は整数や文字列、ペア、リストなど様々な型を持ち得る。そのため、ロケーション状況を別の式で表現する時、その式は任意の型を持ち得る式でなければならない。以下のプログラムを例とすると、

let a = ref 1
let b = !a + 3
let c = ref "abc"
let d = !c ^ "def"
この時、変数 a は int ref 型を持ち、変数 c は string ref 型を持つ。このように参照は中身に様々な型を持つことができ、型もその中身によって異なる。そのため、様々な型を持ちうるロケー
ション状況を同じ式に変換しようとすると、変換先の式は任意の型を持つ必要がある。
試しに、ロケーション状況を"stepper.ref"という文字列に参照が生成された順番を attribute として付与した式に変換すると、1 ステップ実行後、以下のような入力をステッパは受け取る。

let a = "stepper.ref"[@stepper.ref_address 1]
let b = !a + 3
let c = ref "abc"
let d = !c ^ "def"
この時、変数 a は string 型となってしまう。しかし、2 行目の式で a は int ref 型となる必要がある。そのため、プログラムとして型エラーとなってしまう。
ここで、先ほどのプログラムで、ロケーション状況を任意の型を持ちうる式 assert false に
stepper.ref_address という名前で参照情報を付与したプログラムに変換すると、以下のようになる。

let a = assert (false[@stepper.ref_address 1])
let b = !a + 3
let c = ref "abc"
let d = !c ^ "def"assert false は任意の型を持ちうるため、これは OCaml プログラムとして読み込むことができる。そして、2 行目の式をもとに a は int ref 型を持つと OCaml は判断する。その後、2 行目の計算に移るが、どのようにロケーション状況と対応する値を引き継ぐかは 3 節にて詳しく説明する。
そして、計算が進み、3 行目の変数 c の実行が行われると以下のような結果となる。
let a = assert (false[@stepper.ref_address 1])
let b = 4
let c = assert (false[@stepper.ref_address 2])
let d = !c ^ "def"7この時、4 行目の式をもとに、変数 c は string ref 型を持つと OCaml は判断する。このように、ロケーション状況の表示を別の式に変換する時は、変換先の式が任意の型を持ち得る式でなければならない。逆に任意の型を持ちうる式を使えば、元の式に比べて型制約が減るため、元の式に型がつくならば、変換先の式は必ず型がつく。3
任意の型を持ちうる式として、raise Not_found や failwith "..." なども考えられるが、本研究では、assert false を採用した。本研究では、参照の情報という特定の attribute のついた
assert false を使用し、それを特別扱いしているため、ステップ実行中に assert false が実際に実行されてしまうことはない。4 また、ユーザには assert false ではなく、インクリメンタルではないステッパの出力同様の「#」と「参照の生成が行われた順番」の表記が見えるようにする処理を行なっている。このような実装を行うことで、ユーザへの表示は OCaml ステッパと変わらず、
ロケーション状況をインクリメンタルに扱うことができるようになった。

参照情報の引き継ぎ

3

参照のロケーション状況とそれに対応する値の関係を、インクリメンタルではない OCaml ステッ
パでは、グローバル変数 ref_env に保管していた。
例えば、以下のプログラムを実行すると、

let a = ref 1
let b = ref "text"...
ref_env の中身は [("#1", 1), ("#2", "text")] となる。5 そして 3 行目以降で参照の格納や取り出しが行われるときは、この ref_env の情報をもとに実行される。
しかし、インクリメンタルステッパでは、新たにプログラムを受け取りそのプログラムを元に計算が行われるため、グローバル変数などプログラム全ての状態を次の入力となるプログラムに出力する必要がある。そこで本研究では、現在の ref_env を表す attribute を返す関数を作成
し、attribute として ref_env の情報を付与することとした。この時、1.3 節で示したステップ
数の attribute である [@@@stepper.counter ...] と同様に [@@@stepper.process ...] の中に[@@@stepper.ref_env ...] という形で attribute を付与する。その後、参照情報が付与されているプログラムを入力として受け取った時に、参照情報を獲得したり、新たな参照を ref_env に格納する関数を作成した。このような実装を行うことで、OCaml コンパイラのパーザをそのまま利用しつつ、参照情報をインクリメンタルに扱えるようになった。
この関数を用いて例のプログラムを実行すると、1 行目の実行でlet a = (assert (false[@stepper.ref_address 1]))
let b = ref "text"...
となり、参照情報の attribute である [@@@stepper.ref_env [("#1", 1)]] を作成し付与する。そのため、次のステップに行く際、以下のプログラムが入力として渡される。

3

OCaml コンパイラでは ref None など弱い型変数が最後まで残るプログラムはエラーとなる。assert false を使うことで、そのような場面が増えることが考えられるが、そのような式のステップ実行も可能にするため、ステッパでは弱い型変数が残っているかのチェックをしないよう変更を加えている。
4
また、ユーザが書いた assert false と混同されることもない。
5
正確には 1 と "text" はどちらも構文木になっている。従ってここで型エラーになることはない。

8

図 3: Emacs プログラム

図 4: Emacs ステッパ実行結果 1

図 5: Emacs ステッパ実行結果 2[@@@stepper.ref_env [("#1", 1)]]
let a = (assert (false[@stepper.ref_address 1]))
let b = ref "text"...
そして、次のプログラムでは受け取ったプログラムから、ref_env の中身を取り出し、2 行目を実行する。実行後は、以下のプログラムが実行結果となり、

let a = (assert (false[@stepper.ref_address 1]))
let b = (assert (false[@stepper.ref_address 2]))...
3 行目以降のステップを実行する際は以下のプログラムが入力として渡される。

9

図 6: OCaml Blockly のエディタ画面

図 7: OCaml Blockly の実行結果画面[@@@stepper.ref_env [("#1", 1), ("#2", "text)]]
let a = (assert (false[@stepper.ref_address 1]))
let b = (assert (false[@stepper.ref_address 2]))...

4

インクリメンタルステッパの現状

インクリメンタルステッパは現在、前節までに実装した参照の他に、if 文や、型定義、match 文、
引数付きの例外やモジュールなど初学者が扱いそうな構文（配列についてはまだサポートできていないが、本研究の参照のサポートをもとに対応予定）についてサポートしており、お茶の水女子大学で行われている関数型言語の授業に活用されている。授業では Emacs インターフェースでボタンを操作することで、ステップ実行の様子を見ることができる。例えば、関数型言語の授業にて出てくる「フィボナッチ数を計算する関数 fib の中で fib が何回呼び出されたのかを参照 counter でカウントするプログラム」を Emacs に書くと図 3 のようになる。そして図 3 の上部にある Start ボタ
ンを押すことで、図 4 のようにステッパが出力される。その後、Next ボタンを押すと次のステップ
が図 5 のようにユーザへ表示される。参照のプログラムを実行しても問題なく次のステップに移っていることが確認できる。

10

図 8: ステッパのデモページ

図 9: ステッパの結果画面 1

図 10: ステッパの結果画面 2
また、授業では初学者をサポートするツールとして、OCaml プログラムをブロックを組み立てるだけで作成することができる OCaml Blockly [6] というツールも活用している。OCaml Blocklyのエディター画面から実行ボタンを押すと、本研究で開発したステッパが開くようになっている。
例えば、1.1 節で例に出した消費税の計算を行う shohizei という関数定義とそのテストプログラムを図 6 のように作成し、右下にある実行ボタンを押すと図 7 のようなステップ実行結果を確認する
ことができる。この実行結果画面でも Emacs インターフェース同様、上部のボタンを操作するこ11

とで、前後のステップに移動したり、スキップすることができる。
開発したインクリメンタルステッパは、ダイクストラ法を使った最短路問題で、内部で木のモジュールを定義して使うようなプログラムに対してもステップ実行ができる。また、処理速度については、インクリメンタルにすることで最短路問題が動く程度になっている。このインクリメンタル
ステッパの実行を確認できるデモページも公開している。
（http://pllab.is.ocha.ac.jp/~asai/
Stepper/demo/）例えば、関数型言語の授業にて実際に課題となる「文字列を受け取ったら、その文字列に呼ばれるごとに異なる数字をつけた文字列を返す関数 gensym」とそのテストプログラムを用意し、図 8 の上部のボタンで OCaml プログラムをアップロード、下部の実行ボタンを押すと
図 9 のような結果が出力される。その後、上部の Next ボタン数回押すと、図 10 のように参照先の値が変化する様子が確認できる。OCaml Blockly は参照をサポートしていないが、デモページでは参照をサポートしている。また、近々ステッパのプログラムを git にて公開予定である。

5

関連研究

ステッパはもともと Racket 言語の教育用に制限された構文に対して作られた。これは Clements
ら [7] が設計したもので、以下の二点がステッパを作るために必要であるという考えのもと、ステッパ用の関数を定義した。

• 全ての簡約を正しい順番で表示する• プログラム全体を再構成するための情報にアクセスできる
Racket の最近のバージョンでは、言語として R5RS を選ぶと set-car! などの副作用命令をステッ
プ実行できるようだが、セルの内容は表示されない。また、インクリメンタルにする代わりに一定ステップを計算しても計算が終了しなかったら、さらに続けるか中断するかを選べるようになっている。
OCaml のステッパとしては、Cong と Asai [8] がコンテキストの記録およびそこから再構成したプログラムの出力を限定継続のオペレータ shift/reset を用いて行い、ステッパを実装した。そして、Furukawa ら [2] は shift/reset を用いて行っていた操作をダイナミックバインディングにて実装した。これらはいずれもインクリメンタルなステッパにはなっていない。本研究では shift/reset やダイナミックバインディングは使わず、代わりにコンテキストを明示的に引数として渡すようにしている。
Whitington と Ridge [9] は small-step のインタプリタを直接書くことで OCaml に対するステッパを実装した。それに対して本研究のステッパは big-step のインタプリタに手を加える形で作られている。また、彼らのステッパは、OCaml の標準ライブラリを読み込めるなど、かなり多くの命令をサポートしている。参照もサポートしており、参照情報を表示するために、プログラムの前に
let x = {contents = ...} in ... をつけるようにしている。これは一見、ロケーション専用の表記を導入することなく参照をサポートできているように見えるが、彼らの実装では、
let x = ref 0 in x := (!x + 1); !x;;というプログラムを実行すると、x が展開されて

let x = {contents = 0} in {contents = 0} := (!x + 1); !x;;という結果となる。この表示されたプログラムをそのまま OCaml で実行すると（もとの実行結果とは異なる）0 という結果が返ってくる。これは 2 か所に書かれている {contents = 0} が別物になるので、本来なら 1 が返ってきて欲しいところを 0 が返ってきてしまうためである。したがって、
この表記ではロケーション専用の表記を導入することなく初学者が理解可能な表記を提供すること

12

にはなっていない。ただし、これは表記上の問題であり、出力されるステップ実行の結果は正しいものとなっている。OCaml のプログラムとして正しい表記にするためには call-by-need の意味論
[4, 5] を模して x の値を代入することなく（共有関係を保ったまま）簡約していく必要があるが、その動きは初心者にとって必ずしもわかりやすいとは言えないと思われる。Whitington と Ridge は
このステッパをデバッグ用のツールとして開発しており、コンソール上で特定のコマンドを用いる
ことで実行できる。それに対して本研究のステッパはユーザがエディタ上でボタンの操作とロケー
ション状況が「#」と数字であるという知識のみでプログラムの流れを理解することができる点が異なる。

6

今後の課題とまとめ

本研究では、ロケーション状況を任意の型を持ちうる式に attribute をつけることで表現することと、ロケーション状況と対応する値の情報をプログラムに付与することで、先行研究では不十分であったインクリメンタルステッパでの参照のサポートを行った。できあがったインクリメンタル
ステッパはお茶の水女子大学の関数型言語の授業でブロック環境と Emacs 環境の両方で実際に使われている。
今後は、未対応である配列の実装と、ソースコードの整理をした上で公開し、より広く使えるよ
うにしていく予定である。また、授業での運用を通してステッパの教育的効果についても検証していくと共に、ユーザからの意見を蓄積しユーザインターフェースなどの改善をしていきたい。

参考文献[1] 古川つきの. 代数的効果を含むプログラムのステップ実行. 修士論文, お茶の水女子大学大学院 博士前期過程 人間文化創成科学研究科, 2020.
[2] Tsukino Furukawa, Youyou Cong, and Kenichi Asai. Stepping OCaml. In Proceedings Seventh International Workshop on Trends in Functional Programming in Education, Chalmers University, Gothenburg, Sweden, 14th June 2018, Vol. 295 of Electronic Proceedings in Theoretical Computer Science, p.
17–34, 2019.
[3] 五十嵐淳. プログラミング in OCaml. 技術評論社, 2007.
[4] Zena M. Ariola and Matthias Felleisen. The call-by-need lambda calculus. Journal of Functional
Programming, Vol. 7, pp. 265–301, 1997.
[5] Martin Odersky John Maraist and Philip Wadler. The call-by-need lambda calculus. Journal of
Functional Programming, Vol. 8, pp. 275–317, 1998.
[6] 松本晴香, 浅井健一. Blockly をベースにした OCaml ビジュアルプログラミングエディタ. 第 21 回プ ロ
グラミングおよびプログラミング言語ワークショップ論文集, 2019.
[7] John Clements, Matthew Flatt, and Matthias Felleisen. Modeling an algebraic stepper. In European
symposium on programming, pp. 320–334, Springer, 2001.
[8] Youyou Cong and Kenichi Asai. Implementing a stepper using delimited continuations. 7th International Symposium on Symbolic Computation in Software Science, Vol. 39, pp. 42–54, 2016.
[9] John Whitington and Tom Ridge. Direct interpretation of functional programs for debugging. In Sam
Lindley and Gabriel Scherer, editors, Proceedings ML Family / OCaml Users and Developers workshops,
Oxford, UK, Vol. 294 of Electronic Proceedings in Theoretical Computer Science, pp. 41–73, 2019.

13