[forth] [SikiLanguage]

なぜForthがこれほどうまく機能するのか

ということで、さっそくつらつらと書き進めましょう。

「ぐだぐだにならなきゃ良いけどね」

まあ、その辺は気にせずに。今日はプログラム言語について──その奇抜さからマイナーな地位に甘んじているForthについて語ろうかと考えています。

「あんたの作っている俺言語もForthベースだね」

はい。Forthだけではないですが、基本的な部分はForthベースで作成しています。

普通、Forthというと、

1. 逆ポーランド記法
2. スタックベース
3. ワード・ディクショナリ指向

という特性を持っていると言われます。これらの特性はForthとそれ以外を分ける大きな違いで、これらの特性から形作られる連鎖性(Concatenative)はForth最大の利点だと言えるでしょう。

「まあ、Forth最大の悪夢でもあるわけだけどな。ConcatenativeについてはスタックとConcatenativeあたりを参照だね」

で、式鬼言語にForthの特長を取り込むにあたり、『なぜForthがこれほどうまく機能するのか』ということについて自分なりに考えてみました。

「Forthの作者(Charles Moore)の宿題だね」

そうですね。Charles Mooreは『線形的というよりもむしろ対数的に成長してきたことと、言語が推奨している“因数分解”的手法が、問題に取り掛かるときの“問題を要因に分割する”手法を促進した』と言っていますが、私はちょっと違うかな、と感じています。

結論をまとめて言ってしまうと、『２つのスタックによって作り出される連続的／多層的な局所性』という点に集約されるのではないか、と私は考えています。

「…………そりゃ一体なんだい？」

まあ、何とも説明し辛いですが……。Forthは、極端な話、計算結果を保存する“データスタック”と、これから実行する命令を並べたスタック────仮に“オペコードスタック”と呼びましょう────のトップをひたすら操作し続けることによって計算を行っています。

「２スタックマシン──チューリングマシンの亜種だね」

いえ、いえ。２スタックマシンの場合ですと、ある命令を処理するための命令セットはスタックのどこか途中に埋め込まれています。ある命令を実行しようとすると、２つのスタックのデータをあっちに動かしこっちに動かしして実行命令を探す必要があるんですよね。Forthのようにキレイに逐次処理はできないんです。Forthの場合、ここでディクショナリが威力を発揮します。

Forthではディクショナリ──実行命令を探し出す仕組みが存在しますので、スタックのどこかに命令セットを埋め込む必要はありません。２スタックマシンだとトップを移動させて命令セットを探すところですが、Forthではその代わりにディクショナリから命令セットを探します。つまりForthでは２スタックマシンとかチューリングマシンとは違って、トップ（ヘッド）を動かさなくても命令を探して展開することができます。これは便利。

「チューリングマシンの厄介なランダムアクセス性をディクショナリに追い出した、つうことかね」

そうですね。２スタックマシンからランダムアクセス──パラレル性の高いところを切り離してシリアル性を高めたとでも言いますか。

結果として、Forthでは“データスタック”と“オペコードスタック”のトップをひたすら操作し続けることによってプログラムを実行することが可能になりました。チューリングマシンや２スタックマシンのようにわざわざスタックの途中のデータを参照する必要もありません。プログラムで処理される部分がトップ付近に局所化されています。

ここからは具体的な例を見てもらった方が良いですね。プログラムの動作を見てもらいましょう。サンプルコードはせっかくなので式鬼言語にします。

[][1 2 3 ..add .double ..add]

ここで、

1. 左側の[ ]：データスタック（戻り値保存用）。中央寄り（右側）がトップ
2. 右側の[ ]：オペコードスタック（操作保存用）。中央寄り（左側）がトップ

となります。

またオペコードスタックに積まれているのはデータではなく、『データスタック／オペコードスタックに対する操作』になります。“1”とか“2”はつまり『データスタックに整数値を積む操作』ですね。“..add”は『データスタックの上２つのデータを足し合わせたデータを積む操作』で、“..double”は『ディクショナリから“.. double”に関連付けられている命令“.dup ..add”（データスタックのトップをコピーして加える）をオペコードスタックに積む操作』になります。

また、データとしての数字は“(1)”のようにカッコで囲うことにしましょう。

このプログラムを少しずつ実行すると、

    [         |       ][1         |2 3 ..add .double ..add]
    [         |    (1)][          |2 3 ..add .double ..add]
    [(1)      |       ][          |2 3 ..add .double ..add]

    [(1)      |       ][2         |  3 ..add .double ..add]
    [(1)      |    (2)][          |  3 ..add .double ..add]
    [(1)(2)   |       ][          |  3 ..add .double ..add]

    [(1)(2)   |       ][3         |    ..add .double ..add]
    [(1)(2)   |    (3)][          |    ..add .double ..add]
    [(1)(2)(3)|       ][          |    ..add .double ..add]

    [(1)(2)(3)|       ][..add     |          .double ..add]
    [(1)      | (2)(3)][..add     |          .double ..add]
    [(1)      |    (5)][          |          .double ..add]
    [(1)(5)   |       ][          |          .double ..add]

    [(1)(5)   |       ][.double   |                  ..add]
    [(1)(5)   |       ][.dup ..add|                  ..add]
    [(1)(5)   |       ][          |       .dup ..add ..add]

    [(1)(5)   |       ][.dup      |            ..add ..add]
    [(1)      |    (5)][.dup      |            ..add ..add]
    [(1)      | (5)(5)][          |            ..add ..add]
    [(1)(5)(5)|       ][          |            ..add ..add]

    [(1)(5)(5)|       ][..add     |                  ..add]
    [(1)      | (5)(5)][..add     |                  ..add]
    [(1)      |   (10)][          |                  ..add]
    [(1)(10)  |       ][          |                  ..add]

    [(1)(10)  |       ][..add     |                        ]
    [         |(1)(10)][..add     |                        ]
    [         |   (11)][          |                        ]
    [(11)     |       ][          |                        ]
    ※縦棒は単なる補助線です。
      スタック構造の中にこのようなマークはありません。

となります。

これを見れば、勘の良いひとならだいたいわかると思いますが……。縦棒の内側と外側の部分に注目してください。内側が操作の対象となっている部分で、外側はそれ以外の部分です。ご覧の通り、操作の対象となっている部分は一つながりとなっていて、それ以外の部分はまったく変更していない──すなわち、局所的に操作が行われていることがわかると思います。この局所的な操作がいくつも繋がって、結局のところプログラム全体を構成してるということですね。

「むむむ……。大きなプログラムも、結局のところ局所的な操作に分解することができる、つうことかね」

そうですね。純粋にスタック操作だけで実装する必要がありますけど。

「いわゆる『分割して統治』の形だね」

ええ、そうです。局所的な部分が上手いぐあいに入れ子的・階層的になっているので、簡単な原理にもかかわらず高度で複雑なことも実現できるんですよね。

ただ同時に、……この高度な多重構造がForthの欠点でもあります。

「そりゃ何で？」

この辺はLispと一緒ですね。人間が扱えないほど複雑なレベルまで簡単に到達してしまうんですよ。他人のソースコードを読むのは非常に大変ですし、注意しないとあっという間に制御不能になってしまいます。特にForthの場合は、プログラムの多重構造がとても複雑かつ柔軟になっているのでたちが悪いですね。

「上記の例でもそうだね。縦棒があるからまだ見やすいけど、実際にはシームレスに操作しているわけだからね」