最短（？）のフィボナッチ数列計算プログラム

swap over +

　ただこれだけ。これで次々にフィボナッチ数列が計算できる。
これ以上に短いプログラムでフィボナッチ数列が計算できる言語・方法があるのかは正直良くわからないが、そこそこに短い方ではないかと思う。ちなみに対象の言語は Forth と Paraphrase である。

　このプログラムはあくまでも計算するだけである。
しかし、計算すればその結果を見たくなるのが人情というものである。
なので、計算結果を表示させると以下のコードとなる（少し長くなった）。

swap over + dup .

　実際に計算させてみると以下のようになる。このコードで使用しているワードは Forth とコンパチ（なハズ）なので、今回は拙作のParaphrase を用いた（行頭の > は Paraphrase インタプリタのプロンプトである）。

> 1 1 // F1 F2 をスタックに積む
 ok.
> swap over + dup .
 2 ok.
> swap over + dup .
 3 ok.
> swap over + dup .
 5 ok.
> swap over + dup .
 8 ok.
> swap over + dup .
 13 ok.
> swap over + dup .
 21 ok.
> swap over + dup .
 34 ok.
> swap over + dup .
 55 ok.
> swap over + dup .
 89 ok.

なぜ計算できるのか？　その仕組の解説

スタックの上から 2 番目（セカンド）に F_{n-1} が、1 番上（TOS=Top Of Stack）に F_n が格納されているとする。

+---------+
| F_n     |
+---------+
| F_{n-1} |
+---------+

swap で、

+---------+
| F_{n-1} |
+---------+
| F_n     |
+---------+

となり、over で、

+---------+
| F_n     |
+---------+
| F_{n-1} |
+---------+
| F_n     |
+---------+

となり、+ にて、

+----------------------------+
| F_n+F_{n-1}　つまり F_{n+1} |
+----------------------------+
| F_n                        |
+----------------------------+

を得る。

Forth では、スタックの変化前と変化後を --- というキーワードを用いて表現する。
この記法を用いると、swap over + というプログラムは、

F_{n-1} F_n --- F_n F_{n+1}

という変化をスタックにもたらす。

おわりに

　Forth は長い歴史を持つ言語である。そのため、おそらくここに書かれているようなことは既に誰かがとうの昔に書いている可能性も高い。もしご存知の方がいたら、コメント欄にでも書いていただければ幸いである。