ポインタのない C 言語 *1 はチューリング完全でしょうか。
昨日は酒井さんとの話で
では pointer-free な C 言語はどうか、と聞いてみましたが、union でなんとかできそうとの返事。
と書きましたが、union は型変換ができるだけでポインタを取り出すことはできないのでだめそうとのこと。うーん。
僕の考えた解答ですが、コードを全部 CPS 変換した上で、可変長引数を悪用すれば brainfuck インタプリタが書けるような気がしました。va_list を 2 要素の組 (= cons) とみてリストを作る感じ。
void alloc(int len, ...) { va_list ap; va_start(ap, len); if(len > 0) { alloc(len - 1, 0, ap); } else { continuation(ap); } va_end(ap); }
ただしこれで得られるリストは「一回しか読めない」という重大な制限があります *2 。従ってリストから値を読み出すときは、ついでに新しいリストを構築しなければなりません。以下は idx 番目の値をとってくる関数です。code を壊してリストをなめつつ、ap を構築し、最終的に継続に val と ap を渡します。ただし ap は code と逆順であるため、反転する必要があります。
void fetch( int idx, int val, int code_len, va_list code, int len, ... ) { va_list ap; int v; va_start(ap, len); if(code_len > 0) { v = va_arg(code, int); if(idx == 0) val = v; fetch(idx - 1, val, code_len - 1, code, len + 1, v, ap); } else { continuation(val, len, ap); } va_end(ap); }
これで brainfuck インタプリタが書けると思います。多分。嘘だったらごめんなさい。関数ポインタも禁止なので、実際に書くのはすげー面倒そうです。すごい勢いでスタックを消費する *3 から、Hello, world! すら動かなかったりして。
ポインタ禁止といいつつ、可変長引数なんていうものすごくポインタくさいものを使っているわけで、あんまり納得はできてません。もっとエレガントな解答を募集。
