エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

クロージャーの調査(1)

プログラム電卓の仕様

クロージャーの基礎となる代数的構造の調査をしていましたが、今回はプログラム電卓クロージャーを導入するとどうなるか、という方向で考えていきます。まず関数の定義を導入していきます。現在、一つの式で定義できる関数以外、関数の定義はできません。データはクロージャーを含まない代数的構造として定義することができます。

プログラム電卓では実行を中断できるようになっています。指定した回数のステートメントを実行した後いったん停止して、そのときに「Break」ボタンを押すと中断することができます。中断した後「Cont」ボタンを押すと実行を再開できます。いったん停止したとき何もしない場合は、指定した時間の後自動的に再開されます。

また、「STOP」ステートメントを実行することによっても、実行を中断することができます。この場合も、中断した後「Cont」ボタンを押すと実行を再開できます。

「INPUT」ステートメントを実行すると、いったん停止して入力ができるようになります。入力した後「OK」ボタンを押すと、実行が再開されます。「GET」ステートメントを実行すると、いったん停止して入力ができるようになります。こちらは何も入力しなくても指定した時間が経過すると実行が再開されます。

実行が再開されるとき、中断する前に最後に実行したステートメントの次のステートメントから再開されます。

プログラム電卓への関数の定義の追加

これに複数のステートメントからなる関数の定義を追加することを考えます。関数の実行中に中断できるようにします。実行が再開されると、中断する前に最後に実行したステートメントの次のステートメントから再開され、関数の実行が終了すると、関数が使われている式が再開されます。

これを実現するには式についても「次の位置」から再開できるようにする必要があります。現在は、式の内部に「次の位置」というものはないのですが、FORTH電卓と同様の処理にすれば「次の位置」を導入することができます。FORTH電卓では、式とステートメントのような区別はなく、すべて逆ポーランド記法で記述するようになっています。これによってプログラム電卓と同様の

を実現しています。

QuickBASIC(wikipedia:QuickBASIC)の仕様では、関数の定義は

  • 定義の内部で使われている変数は引数かローカル変数
  • 外部の変数を使うことはできない
  • 引数は参照で渡される

となっていますが、引数に変数を追加すれば外部の変数を使うことと同じことになります。

  • 関数定義の内部で関数を定義できる
  • 関数を引数や戻り値にすることができる
  • 「引数に追加した変数」のアドレスは、その関数定義の外部の関数で使われるローカル変数のアドレス

とすれば、クロージャーとして使うことができます。

このとき中断するにはどうすれば良いか考えていきます。

FORTH電卓へのクロージャーの実装

FORTH電卓では関数(FORTHの用語ではワード)定義の内部で関数は定義できない、ローカル変数は使えないという仕様になっています。これは、JavaScriptで実装するためアドレスを使えるようにする意味があまりないのと、FORTHの仕様が不明だったためです。これを

  • 関数定義の内部で関数を定義できる
  • ローカル変数が使える
  • さらに、関数のアドレスを使うことができる

とすればどうなるか考えていきます。

  • 関数の引数、戻り値はスタックに入れる(パラメータースタック)
  • ローカル変数はスタックのような構造(ただし参照されているデータは消去されない)で実装(C#ではImmutableStackでできそうです。これをローカル変数スタックとします。)
  • 関数のアドレスをスタックに入れることができ、関数のアドレスから関数を呼び出すことができる

とすればクロージャーを実現できそうです。関数呼び出しの情報は関数呼び出しスタック、ループ情報はループ情報スタックに保存するとします。

  • パラメータースタック(引数、戻り値)
  • ローカル変数スタック
  • 関数呼び出しスタック
  • ループ情報スタック

を保存すれば、クロージャー実行中に中断して、入出力の後戻って来ることができます。

BASIC、FORTHの仕様は以下の本を参考にしています。

galapagosstore.com