prog_0001 のバックアップ(No.4)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
prog_0001 へ行く。
- 1 (2014-10-03 (金) 16:05:52)
- 2 (2014-10-03 (金) 18:30:55)
- 3 (2014-10-07 (火) 18:28:16)
- 4 (2014-10-14 (火) 10:58:21)

C言語における汎用的な関数

(by K, 2014.10.03)

↑

(0)

以前はoSasKdotにプログラミング一般系の話題を書いていたけれど、今は使えないので、書くところがない。
ということでここに書くことにする。

↑

(1)

たとえば<stdlib.h>のqsort()では、一般化された比較関数として、
```
int compare(const void *a, const void *b);
```
みたいなものを使っている。
これは、任意の2引数関数を表現していると一般には思われている。でも僕はこれが十分ではないと思う。

こんな状況を考えよう。すごくよく似た関数を100本書かなければいけないとする。それぞれの関数は95%は共通で、違いはわずかだとしよう。このとき、関数をそのまま100個作ればいいのだけど、そうしたらプログラムはむやみに長くなるし、バグも入り込んでしまうかもしれない。・・・そうであれば、関数を一つにして、引数を一つ増やして、その増やした引数で100個のどれなのかを選べるようにしたらどうだろう。このほうがずっといいと思う。
となると、関数は本来の引数のほかに、関数をカスタマイズするための構造体のポインタが必要なんじゃないか、と考えた。
つまりintを2つとる汎用関数ならこうなる。
```
int func(void *customize, int a, int b);
```
このスタイルを採用するのなら、qsort()はこうなる。
```
void qsort(base, num, size, compare, customize);
```
このcustomizeはcompareを呼び出すときに必ず渡される。つまり汎用の関数を渡すには、単に関数ポインタだけでは不十分で、カスタマイズ構造体のポインタが必要なのだ。
これが今回の僕の主張である。
ちなみに何も渡すデータがないのなら、customizeはNULLでいいし、compare関数もcustomize引数の値は無視すればいい。

↑

(2)

ここで関数として、なんらかのVMというかインタプリタみたいなものを考える。そしてカスタマイズ構造体の中に、インタプリタで実行したいプログラムが入っているとする。これならたった一つの関数しかなくても、データだけ変えればどんな処理もできるということになる。
- まさに汎用的だ！

↑

(3)

機械語を実行時に動的に生成してもよければ、常にあるカスタム構造体を適用して呼び出すような関数を自動生成することはできる。

void *makeFunc(void *baseFunc, void *customize, int x, int y)
{
    p = mallocして、実行権限を付ける.
    メモリに機械語を書いて、f(x,y) { return baseFunc(customize, x, y); }
    に相当する関数を作る.
    return p;
}

だからこれを前提にすれば、カスタマイズ構造体へのポインタを含まなくても、関数のポインタだけで汎用性を確保することはできる。
でもこの処理はもちろんコンパイラ的な処理が必要なので機種依存する。関数呼び出しの深さも増えているので、オーバーヘッドもある。

↑

こめんと欄

(1)は関数型言語での「クロージャ」に近い発想ですね。Cだと関数から引数以外に見える外界はグローバルスコープだけですが、クロージャを備えた言語なら例えば「[=](int a, int b) -> int { return func(customize_000, a, b); }」という式を書けば、(ローカル変数かもしれない)customize_000をfuncの第1引数に固定して呼び出す関数への関数ポインタが得られます(KさんならCに近い言語が分かりやすいと思ったのでこの例はC++0xです)。コンパイラの実装次第ですが、voidポインタを持ち回るのとだいたい同等のコードが生成されそうです。(3)と同じ動作としては「カリー化」という概念があります。さすがに動的に機械語を生成する実装は知りませんが、ヒープに確保した(カスタマイズ構造体に相当する)データ構造に固定する引数を保持する実装が主流だと思われます。オーバーヘッドより移植性を重視するのが近年の流れでしょうか。 -- yao 2014-10-07 (火) 18:28:16
おお、yaoさんありがとうございます！ -- K 2014-10-14 (火) 10:58:21

コメント	お名前	NameLink