1から5までの和を，計算過程らしきものを含めて，計算するプログラム

2週間程前に，1から100までの和（1 + 2 + ... + 99 + 100)を計算するプログラムを書きましょう．ただし変数は1つだけ（しか）宣言出来ませんという問題が，twitter上に出現した覚えがあります．
（形式的な問題の定義とかは知らないので，なんとなくそれっぽい問題という程度で認識してください）

良くわからんけどまぁそんなのは問題なく書けると思うのですが，それよりももうちょっと面白い縛りで，http://favstar.fm/users/osa_k/status/184175881265221634 を見かけまして，何時間か挑戦してみたという話があります．

で，その時に書いたプログラムを何故か昨日のBoost.Contextオンリーイベントで発表というか宣伝して，もっと良い解を皆さんで考えてみませんかという話を少ししました．

しかしclosedな場で宣伝する前に，blogで触れた方がどう考えても他の人の目につく筈で，遅ればせながら本エントリを書いているという次第です．

私が最終的に書いた（昨日発表した）プログラムが以下
https://twitter.com/#!/ranha/status/184493702817910785

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int f();
int main();

int f(void)
{
    srand(182551180);
    if((((uint64_t)main) + 13) ==
       *(((uint64_t*)__builtin_frame_address(0)) + ((5-1) * 6) + 1)){
        puts("5");
        return 5;
    }
    for(;;) {
        if((((uint64_t)main) + 13) ==
           *(((uint64_t*)__builtin_frame_address(0)) + ((rand() % 5) * 6) + 1)){
            printf("%d + ",(rand() % 5) + 1);
            return ((rand()%5) + 1) + f();/* a + bはaが先にcallされるとする */
        }
        else {
            (void)(rand()%5);
            (void)(rand()%5);
        }
    }
}

int main()
{
    printf("%d\n",f());
    return 0;
}

です．
昨日も，プログラムを画面に出して終わりで説明も何も無かったので，以下，このプログラムについて少し解説でもさせてください．

アイディア

まず再帰を使うことにしました．（狭義の）for-ループではなくなぜ再帰なのか?ということについては，ループを変数無しで，というか「プログラム中に」明確に現れない「状態を持つ何か」を使わずに，制御する術が思いつかなかったからです．

さて，再帰させることになったわけですが，何れにせよ再帰関数f中で，f自身が「俺は，mainから何度目に呼び出されたfなのか」が分かっていると嬉しいです．
普通この情報を知りたい場合は，そのまんま「何度目に呼び出された俺なのか」を保持する引数を，関数が取るようになっていれば良いのですよね．その場合は，

const int n = 適当に与える;

int sum(int nandome)
{
  if(nandome == n)
    return nandome;
  else
    return nandome + sum(nandome + 1);
}

int main(){
  printf("%d\n",sum(1));
  return 0;
}

とすれば済む話です．でもこれはなんというかなぁ…という話で，もうちょっと先に進んでみましょう．

"Cのプログラム中に，何度目に呼び出された俺か情報を含んだ何かを出現させる"ことを禁じられた場合，つまり，"Cのプログラム中には明確に出なくても，何度目に呼び出された俺か情報を含んだ何かを得る"ということはあり得ないでしょうか??

Cのプログラムに表示されていないことを考えるので，ここから先は，well-definedなCのプログラムであるかどうかというのを余り考えないことになります．

Cのプログラムの実行時のモデルとして普通スタックにおけるあれこれを考えますが，まぁとにかくスタック．もうちょっと分かりやすい所としてはアセンブリで考えても良いと思いますが，何れにせよスタックが普通の筈でとにかく…．
さて，プログラムを書くうえで，時に"継続"という概念を知っておくとなんか良い感じになることがあるようですが，Cの場合はreturn addressとかそういうのは，「この後計算される情報」に相当するでしょう．この関数からreturnした時にどこに戻るのか，というのは，更にその後続いて行く処理の1つの開始点を得ることになります．

では，main関数から再帰呼出しされるf関数の視点から考えてみましょう．f関数の中で，return addressを取得して，それがmainの中に存在しているならばfはmainから1度目に呼び出された関数であることが分かります．では，取得したreturn addressがmainの中ではなくてfの中にある場合，これはすなわちmain → f → f ... と，mainから2つ以上離れた所にいるfであるということが分かる筈です．

つまりこの，mainから今どれだけ離れているかという考えを使えば，それはすなわちmainから何度目に呼び出されたfなのかということが分かるので，それを用いよう…という話です．

GCCでは，http://gcc.gnu.org/onlinedocs/gcc/Return-Address.html この辺りでreturn addressを引っ張ってくることが出来ます．

今俺はmainからどれだけ離れているんだ

自分自身がmainからどれだけ離れたところまで来ているかを調べるのには，まぁなんかどんどん遡って行けば良いというのは既に述べた通りなのですが，「どんどん遡る」ってどうするのか問題があります．便宜上，http://gcc.gnu.org/onlinedocs/gcc/Return-Address.html　の__builtin_return_addressを使うことを考えることにしましょう．この関数は，n段遡ることが出来ます．
どんどん遡る為に，素直にループでもって1から「順番に」__builtin_return_addressを用いれば良い筈ですけども，今変数が使えない以上これも中々難しいです．変数が使えなくとも，generateという呼び出す毎に1,2,3,...,N,N+1,...と増えて行く関数 + generateを初期化する関数init,があるとすれば，何とかなるでしょう．

int f(void){
  init();
  for(;;) {
    if( __builtin_return_address(generate()) が mainの中に居る  ) {
      if(generate() - 1 == N) {
        printf("%d\n",N);
        return generate() - 2;
      }
      else {
        printf("%d\n",generate() - 2);
        return (generate() - 3) + f(); /* ただし， a + b でaの方が再帰に評価されるとする */
    }
  }
}

で，このような関数initとgenerateを実現する為に，上のプログラムではsrandとrandを用いました．

generateは増加数列を作るという制限がありますが，実際はもうちょっと弱めることが出来て，1からNまでの数を生成する間に，0以下もしくてN+1以上の数を一度も生成しなければ良いような関数に弱めても実装することが出来ます．ただしその際には，111 222 000 333 222 000 … などと3連続のブロックでないと扱えないので云々という話があって，都合の良い乱数列を作る為のシード値を頑張って探しましょうというのがあって…

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i=0;
    srand(182551180);
    for(i=0;i<15;++i)
        printf("%d\n",rand()%5);
    return 0;
}

これを実行すると，

となって大変都合が良い！！以上です．

自分の書いたプログラムについて

srandが引数を取っているので，見た目的にもの凄く悪い．

あと，__builtin_return_addressを使わずにframeの方を使っているのは，return使ってると自分の環境でSeg.fault.して死ぬからっていう単にそれだけで，全く深い意味はありません．

それと，今回書いたプログラムは，Appel様（http://www.cs.princeton.edu/~appel/papers/）の "Intensional Equality ;=) for Continuations"を読んで思いついたものです．この論文は大変面白いものですので，是非一度読んでみてください．個人的には，あのような人もこんなプログラムを書くのかというあたりも楽しかったのですが．

皆さんに宛て

この変数無しで総和書く問題をどのように捉えても自由だと思うのですが，書いてると今まで殆ど意識していなかった色んなことに触れる羽目になって結構楽しいです．
スタックがどうとかそういうのは拘らなくても勿論結構ですので，何かやってみると面白いのではないでしょうか．

むしろ逆に，こういう制限だと書けないという証明をこさえるというのもありで，個人的にはそっちもちょっとやってますが，まぁ色々，色々ですが兎に角色んなやり筋をみてみたいです．