« Rはプログラミング言語でない? | Main | 数理科学12月号 »

ポインタなしC言語の提案

C言語はユーザからレジスタの自由を奪う事によって成立した。今度はポインタの番だ。

目標:
C言語からポインタを取り除く事:
これによりヌルポインタアクセス、バッファオーバラン、リークなどの問題から一切解放される。さらに多重参照(エイリアシング)の問題から解放される。またmalloc/freeなどのメモリ管理コードが不要になる事により行数が削減される。ガベージコレクション停止はない。

注意しなければならないのは、python、rubyなどのLLやJavaでさえ、糖衣により見えにくくしただけでポインタの問題は解決できてないことだ。identity演算子、強/弱の参照の使い分け、エイリアシングによるバグ、ガベージコレクタによる停止などの形でポインタの問題はユーザを悩ませ続けている。


現在のC言語で出来る事は何でも出来る事:
UNIXカーネルなども原理的には書き換え可能であること。

C言語で出来たライブラリを呼び出す事が出来る事:

将来的には:
Cよりも速く走る事が可能な言語仕様にする。


なぜ可能であるか:
どうしてC言語からポインタを除く事が可能かは、なぜC言語にポインタがあるのかを考えれば分る。以下に見るようにすべて現代では当たり前の機能によって置き換え可能である。つまり少々モダンな言語機能を足せば可能である。

1、今のプログラミング言語であれば、配列や構造体のようなデータ構造を関数に渡したり、関数から返したり出来る。しかしC言語ではそれを省略してポインタで間に合わせることにした。

2、今のプログラミング言語では、複数の戻り値を返す事ができる物が多い。しかしC言語ではそれを省略してポインタで間に合わせることにした。

3、今のプログラミング言語であれば関数は配列などの大きなデータ構造を返す事が出来る。しかし、Cではそれが出来ないので、関数にポインタを渡して値を入れてもらう。あるいは関数の中でmallocして、ポインタを返す。

4, 今の言語ではリスト、ベクトル、ハッシュ、構造体がある。他のデータ型はこれらから作る事ができる。
対して、Cではこれらすら用意するのがめんどくさかった。
  配列を*(a+i)のシンタックスシュガーにしてコンパイラを単純にしたかった
    -> 最小のコンパイラで最大の効果
    -> 現代の視点ではコンパイラを単純にするより言語を単純にすべき
  単に最初のCコンパイラは最適化がほとんどなかったから

5、今のC実装では配列のindexing a[i]はポインタよりも早い事さえある。だけど昔の実装ではポインタを使ったほうが早かった

6,今の言語ではいろいろな型(多相)を返せる、受け取れる。Cは出来ないのでしばしばポインタのキャストが使われる。また構造体Aに構造体Bが含まれ構造体Bに構造体Aが含まれるというような時にはポインタが必要。これも任意の型を入れる事が出来ればOK。

以上のように今では普通の機能を足せばポインタは必要なくなる。

あと一つだけ、漏れているのは
7, ヒープアロケートしたものが欲しい
たとえば、生成と解放の順序が予測不能(というよりコールグラフで表現不能)なものがある( ex. 人間などが順不同に生成、削除するものなど)、グラフ構造を作りたい(たとえばwindowのView Hierarchy)という場合。この辺りがいかにも神秘精妙に見えるから、ポインタを無くする事が出来ないという信仰につながるのだと思う。
これについては、ユニークなキーを自動生成する関数と組み合わせた連想配列で十分。その速さは原理的に最悪でもmallocと同じにできる。(キーの列挙不能な連想配列をmallocと同一視するプラグマが可能だから。現実的には違う種類のグラフや入れ物を混合するmalloc/freeは遅い。)


次に提案言語のプログラムがなぜCよりも速く走ることが出来るのか。第一には現在多くの最適化の障害になっているのはエイリアシングであり、それがない分だけ最適化がアグレッシブにできる。(c.f 「多重参照 (aliasing)」の問題点 )

第二には、現代的な配列などを使いポインタを無くすれば、コンパイラはデータをヒープに置くかスタックに置くか、レジスタで済ますかを自由にオプティマイズできるからだ。ヒープに対してスタック上のalloca()は何倍も速く確保できる。
例えば行列のライブラリを作ったとすると一般の場合に適用できるようにデータはヒープ確保になる。しかし、ローカルな寿命しか持たなければstack上に何倍も速いalloca()で確保できたはずである。さらに行列が小さければレジスタに確保できたかも知れない。
もちろんCでもこれらのオプティマイズは手作業で可能である。しかし現実的にはそこまで手間をかけられない事のほうがが多く、提案言語の方が速くなる。

C言語のプログラマはポインタを生成するとき、必ず頭の中で、ポインタで指される先は関数呼び出しで変更されるのかされないのか、エイリアスの可能性はあるのか、ポインタの寿命はどこまでか、指し示されるメモリの寿命はどこまでかを追跡している。この種の静的解析はコンパイラの方がずっと上手にできる。これから解放されたらどれだけ楽になる事か。
最初にC言語がレジスタを隠蔽したとき「そんなので速いプログラムを書く事が出来るのか」と言われた。しかし今では人間が割り当てるよりも速く走る。今度はポインタを人間の手から奪うべき時だ。

またポインタがないことにより、多くの場合データを所有している継続が1つになり、自動的な並列化を行いやすいことも速さにつながる。


段階的進行:
第一段階:
C++へのコードトランスレータとして実現する。
copy on write

第二段階(将来):LLVM上で最適化を実装。
データのメモリへのストアの仕方がコンパイラの自由になることを利用
参照数のコンパイル時追跡によるコピーの削除、参照カウントの削除。ヒープ割り当てからスタックやレジスタへの割り当て。配列長の追跡による配列長の省略。

遠い将来:
これをC++言語にまで適用したい。C++の膨大な言語仕様の大半はポインタがなければ削除可能であろう。そしてtemplateとconstexpr周りを新しいマクロ機能として再構成したい。

UNIXカーネルの書き直しなど

|

« Rはプログラミング言語でない? | Main | 数理科学12月号 »

Comments

Post a comment



(Not displayed with comment.)


Comments are moderated, and will not appear on this weblog until the author has approved them.



TrackBack


Listed below are links to weblogs that reference ポインタなしC言語の提案:

« Rはプログラミング言語でない? | Main | 数理科学12月号 »