Forth と再帰

Forth における再帰はちょっと面白いのだが、歴史的なところまで含めた日本語での解説がないみたいなのでちょっと書いてみたい。きっかけは Forth とメタプログラミングという話題が TL に流れてたのでちょっとつぶやいてみたのだが、プログラミングについての話題はかなり貪欲に RT する某氏にスルーされたためでもある

現代の Forth と再帰

現代的な Forth では、RECURSE というワードで、「現在定義中のワードの再帰呼び出し」をプログラムできる。 http://www.geocities.jp/naosacra/mops/forbeginner/19.html や id:quek:20080502:1209740080 を参照
そのような専用のワードがあるのは、Forth では伝統的に、現在定義中のワードはふつうは参照できない、ためである。そうなっていると、元のワードを再利用しつつ、新しいワード定義でオーバーライドすることが簡単にできる。たとえばよく使われる例で、"/" というワードを、0 で除算しようとするとエラーメッセージを表示するよう定義し直す、など

Forth の実行モデル

Forth インタプリタのモデルについて簡単に説明する。ご承知のかたは次に飛ばれたい
Forth プログラムはトークンに（通常、空白で）区切られ、外部インタプリタと呼ばれているインタプリタに送られる。外部インタプリタの基本的なモードに、インタラクティブモードとコンパイルモードがあり、まずインタラクティブモードを解説する。インタラクティブモードでは、トークンがリテラルであれば、それに対応するものがスタックに積まれ（たとえば "1" であれば 1 がスタックに積まれ）、トークンがワードであれば、そのワードを実行する（たとえば "+" であれば、スタックの先頭とその次を取り出し、加算し、結果をスタックに積む）、というのが基本的な動作である。リテラルも、そのリテラルに対応する値を積む、というワードであり、全てはワードである、と解釈する向きもある
":"（コロン）というワードを実行すると、外部インタプリタはコンパイルモードになる。この時、コロンの次のトークンを名前として、そのような名前をもつワードの定義が辞書（Python などのデータ構造でいう「辞書」ではなく、Forth ではワードの定義のかたまりを辞書と呼ぶ）に作られ、以後のトークンは実行されるのではなく、対応するコードが辞書中のエントリに書き込まれてゆく
実際に書き込まれるのは「スレッデッドコード」という構造なのだが、ここでは深入りしない（google:スレッデッドコード）
ここで作られるコードを実行するのが、内部インタプリタと呼ばれるインタプリタで、非常に小さなインタプリタである（CISC なら数命令）。外部インタプリタからのワードの実行も、さらには外部インタプリタ自体を実行しているのも、内部インタプリタである

最初期の Forth と再帰

http://www.colorforth.com/HOPL.html によると、「Mohasco, 1968」という節に

SMUDGE avoided recursion during the interpretation of a definition. Since the dictionary would be searched from newest to oldest definitions, recursion would normally occur.

という説明がある。つまり、最初期の Forth は後の Forth とは異なり、定義中のワードが参照できてしまうという仕様であり、SMUDGE （ぼかす、不鮮明にする、という意味がある。ペイント系グラフィックツールにそんな名前のブラシがあったりしますよね）というワードで、定義中のワードを参照してしまうのを防ぐ（そうすることで、同名ワードの再定義の時、古い定義を参照する）ようになっていた

その後の Forth と再帰

マイコン時代に入り、Forth はマイコンで広く使われるようになるが、その頃の Forth では既に、定義中のワードは参照できない、という仕様であった。当時の資料（本稿は手元にある、共立出版の井上著『標準FORTH』を参考にした）などで確認できる
しかし、SMUDGE というワードは使われており、上記の Charles H Moore 氏の説明とは全く逆に、即ち再帰呼び出しをするために、使われていた。しかしおそらく、SMUDGE というワード自体の定義は変わっていなかっただろうと思われる。以下、どういう仕掛けなのかを説明する
Forth の辞書中のエントリにおけるワード定義のデータ構造は、他の、プログラミングにおいて一般的なシンボルテーブル等と同様の、まずヘッダがあり各種属性などのビットや名前があり、可変長の本体が続く、という形になっている
この辞書のエントリにおけるヘッダ内に SMUDGE ビット、というフラグがあり、ワードの探索時にそれを見てスルーしたりしなかったりする、というようになっている（このへんは言語仕様的には実装の詳細ということになるのだろうが、Forth はそういうことは気にしない文化（という気がする））。そして SMUDGE というワードは、この SMUDGE ビットを反転する、というワードである
さて、ここで気になるのが、「コンパイルモード中は、ワードは実行されず、コードが書き込まれるだけ」ということである。どうやってコンパイル中に SMUDGE を実行し、定義中のワードの可視性を変更するのか？
Forth のワードには、「イミディエイト」という属性があり、これがオンになっている「イミディエイトワード」は、コンパイルモード中であっても実行される。最も典型的なイミディエイトワードに "[" と "]" があり、これはコンパイルモード中に外部インタプリタを一時的にインタラクティブモードにするワードで、これを使って [ SMUDGE ] のようにすれば、SMUDGE をワード定義中に実行できる（余談。Forth のコンベンションに、あるワード abc のイミディエイト版は [abc] のようにする、というものがある）
SMUDGE の動作は、前に書いたように「SMUDGE ビットの反転」、すなわち（定義中の）ワードの可視性の「反転」である。おそらく、最初期の Forth と、以後の Forth では、定義中のワードの可視性のデフォルトが変わっただけで、SMUDGE の意味はそのままだったのではなかろうかと思われる

標準 FORTH