C++を使わないbuild-in-placeの説明
……という説明は、C++マスターのk.inabaさんにはわかっていただけたのですが、O'Camlマスターの遠藤さんにはわかっていただけませんでした。k.inabaさんに通訳していただいたり、遠藤さんにわけわからんことをわめいているのを汲み取っていただいたり、めちゃくちゃでした。
再度挑戦させてください。
果たしてC++を、具体的にはコピーコンストラクタという言葉を使わずにbuild-in-placeを説明できるのか！？
えーと、前提知識。
うあああ、これだけでも言外にC++とJavaとかRなんとかの違いが知識として必須ですよと言ってるようなものじゃないか！？
ここから説明しないと駄目か……。
えーと。
CPUとかOSとかは大抵スタックというものを用意してプログラムに使えと言ってきます。ハスなんとかのような実行イコール簡約な言語とか、Prologのような実行イコール探索な言語はこれを壮絶に無視する実装も考えられますが、ブログラムをサブプログラムで構成して、各サブプログラムに入ったのと逆順に出て行く所謂構造化言語では、大抵、呼び出し関係やローカル変数をスタックに保存します。
ブログラムはメインから実行します。
+--------+ | メイン | +--------+
ここでサブプログラムAに入ります。
+--------+---+ | メイン | A | +--------+---+
Aから更にBに入ります。
+--------+---+---+ | メイン | A | B | +--------+---+---|
Bを抜けるとAに戻ります。
+--------+---+ | メイン | A | +--------+---+
Aを抜けるとメインに戻ります。
+--------+ | メイン | +--------+
メインを抜けると暴走します。
普通はメインの前に言語ランタイムの初期化処理があって、そこに戻ってきた場合はプログラムを終了させるようOSのシステムコールを行うようになっていますので暴走しません。
Aのローカル変数xとyは、A用に確保された領域を使用します。
+--------+-------+ | メイン | A | | +---+---+ | | x | y | +--------+---+---+
メイン側で、Aの実行結果を受け取ろうとしたとします。メインに戻ってきた時には既にxやyは消滅していますので、結果を受け取ることが出来ません。
CPUには、スタックのほかに、ヒープメモリやグローバル変数用のメモリやレジスタなどの記憶資源があります。
このうち、グローバル変数用のメモリは、同じサブプログラムに2回入ることを考えると、簡単には使用できません。
Aに再帰した場合、最初のAは、次のAの結果を受け取るのと、自信の結果を格納するのに、同じメモリを使うことになります。
+--------+---+---+
| メイン | A | A |
+--------+---+---+
v v
+---+
| |
+---+これでは困ります。ただし、初期Fortranのようにこれで良しとした言語もあります。良くないです。
レジスタも、言わばグローバル変数用のメモリと同じなのですが、レジスタはメモリと異なり、どんどん新しい値で書き換えてOKという暗黙の約束があります。
ですので、サブプログラムの結果を返すのには通常レジスタが使われます。
しかしレジスタは容量があまり無い上に、場所を示すアドレスを持ちませんので、サイズの大きな値や、他からアドレスで指し示される値を格納することが出来ません。
レジスタで返せる結果は単純なスカラー値か、アドレスそのものぐらいです。
では、ヒープはどうでしょうか。
+--------+---+---+
| メイン | A | A |
+--------+---+---+
v v
+---+---+
| | |
+---+---+サブプログラムは、ヒープメモリを確保して実際の結果を詰めて、レジスタを使用してヒープのアドレスを返します。
サブプログラムを呼び出した側は、結果を読み取った後で、ヒープを解放します。
なかなかよさそうです。これならパーフェクトです。
めでたしめでたし。
……全然別の結論に辿り付いたぞ！？今の無し無し無し。
ヒープは確かに万能ですが、割り当てや解放に探索を必要とします。つまり遅いため、普通いちいちヒープを確保したりしません。LL全盛の時代に言っても説得力無いな。
挫折しそうです。
え、えーと、ヒープは、メモリマネージャがあることを前提とした、高級すぎる機能なのです。
サブプログラム呼び出しなどというプリミティブな機能が、メモリマネージャに依存するわけにはいきません。何しろ、メモリマネージャをサブプログラムとして作らないといけないわけですから、いたちごっこになります。
スタックは、CPUまたはOSが用意してくれますので、作らなくても使うことが出来ます。
従って、スタックだけを使って、サブプログラムの結果を返す動作を実現しなければなりません。
……ええっ。はい。わかっております。嘘はいけないですね。
スカラー値はレジスタだけで返せますので、サブプログラムの結果にはスカラー値縛りでメモリマネージャを作れば、問題ないです。
大体が、ヒープメモリのパフォーマンスを云々しなければならない環境だと、高級言語なんて有り得ないです。アセンブラ一択です。なのでサブプログラムなんて概念自体どーにでもなります。逆にいえば高級言語を使おうとしている以上ヒープメモリ使って問題ないです。
メモリマネージャは言語側が用意する都合上、メモリマネージャを使ってしまうとミックスランゲージが難しくなりますが、そんなことはここではどうでもいいですしね。
困った。
開き直ります。
ヒープは確かに万能ですが、割り当てや解放に探索を必要とします。つまり遅いため、普通いちいちヒープを確保したりしません。そーゆーことをしているからLLは遅いんです。CPUネイティブの言語がLL並に遅くなったら価値が無いじゃないですかっ。
従って、スタックだけを使って、サブプログラムの結果を返す動作を実現しなければなりません。
……これで納得していただきたい。ホント勘弁してください。
スタックだけに戻します。
+--------+-------+ | メイン | A | | +---+---+ | | x | y | +--------+---+---+
ここで、計算結果xをAからメインに返したいとします。xがxの位置のままですと、Aから抜けてスタック上のA用の領域が消滅したときに、xも消滅してしまいます。
つまり、Aから抜けても消えない領域に値を保存する必要があります。
ヒープとグローバル変数用のメモリを使わない、レジスタには入らないとしますと、呼び出しもとであるメインが確保しているスタック上の領域しかありません。そこへ値をコピーします。
+--------+-------+ | メイン | A | | +---+---+---+ | | x'< x | y | +----+---+---+---+
Aから抜けてもx'は残ります。めでたしめでたし。
+--------+ | メイン | | +---+ | | x | +----+---+
実はめでたくないです。
この解決方法は、いままで挙げたどの解決方法と比べても、致命的な欠陥を持ちます。
値のコピーが発生する、ということです。
レジスタに入りきらない値ですから、さぞコピーに時間がかかる……なんて話ではないです。
そもそも何故レジスタを使わないのでしょうか。それは、レジスタには、サイズの大きな値や、他からアドレスで指し示される値を格納することが出来ないからでした。
ふたつ目の「他からアドレスで指し示される値」というのが重要です。
+--------+-------+
| メイン | A |
| +---+---+---+
| | x'< x | y |
+----+---+---+---+
^
+---+
| O |
+---+何か他から、xが参照されていたとしましょう。
xがコピーされた後に消滅しました。
+--------+
| メイン |
| +---+
| | x |
+----+---+
^
+---+
| O |
+---+困りました。Oの指す先が無くなってしまいました。
しかし考えてみれば、ローカル変数のアドレスはサブプログラムを抜けたら無効、当たり前の話です。こんなプログラムは作るほうが悪いです。
ですが、もしxがウィンドウだったらどうでしょうか？つまりAはウィンドウを作成して返すサブプログラムとなります。ウィンドウは当然、表示のためにOSへの登録が必要です。
ファイル然り、そこまでいかなくても効率のため内部データを共有してリンクリストでつなげる構造を取った場合も該当します。
でも作るほうが悪いのですから、xはコピー不可にしてしまいましょう。
これでxを返すサブプログラムは作れなくなりました。めでたしめでたし。
勿論めでたくないです。
そう、作るほうが悪いとはいえ、何かを作成するサブプログラムが書けないのでは、制限がきつすぎます。
実はこの「xを返すサブプログラムは作れなくなりました。めでたしめでたし。」状態がAda95でした。そして、Ada2005のbuild-in-placeこそが、その制限を取り去る機能です。
もう一度立ち返りましょう。
+--------+-------+ | メイン | A | | +---+---+---+ | | x'< x | y | +----+---+---+---+
xからx'へ値をコピーできるということは、Aにはx'の位置がわかっているということでもあります。
そう、最初からx'を使えば、全てが解決します！！
+--------+-------+ | メイン | A | | +---+ +---+ | | x'< | y | +----+---+---+---+
なぜこんなことが、2005年まで定められなかったのでしょうか？
それは、returnという文にあります。
procedure A is x, y : コピーできない型; begin 途中までyを使用して計算; 結果を計算してxにセット; return x; end A;
xとyは、同じように宣言されたローカル変数です。ここではreturn x;でxを返そうとしていますが、文法上はreturn y;とも書けます。これでは、コピーせざるを得ません。
表面上からxを取り去ってみましょう。
procedure A is y : コピーできない型; begin 途中までyを使用して計算; return 結果を計算; end A;
なかなか良いです。
しかし、コピー不可の値を作るような結果の計算とは、具体的に何でしょうか？
それは足し算や引き算では有り得ません。OSに登録したり、リンクリストを構成したりといった操作のはずです。分岐や他のサブプログラム呼び出しも使いたいはずです。式ひとつで書けというには苛酷過ぎます。
そういうわけで、Ada95では、コピーが出来ない値は返せませんでした。嘘です。実は参照返しになりました。正確には、Ada95では、コピーが出来ない値を作成して返すことができませんでした。既存変数を返すことはできました。
実際に言語によっては、returnを使う代わりにResultという特殊な変数が用意されていて、そこへ値をセットすることで結果を返すようになっており、そうした言語では最初からコピーなんて発生していませんでした。
しかしそうは言ってもAdaは既にreturn文を採用しています。それに、Result変数方式は、Result変数が暗黙に準備される変数のため、変数の初期化が明記できません。実行時にサイズが決まる型を持つAdaでは、そうした型の初期化時にサイズを渡さないといけないため、暗黙の変数による解決は不適です。
折衷案として、return文上にて、式ではなく、文で値を作るようにすれば、分岐や他のサブプログラム呼び出しも使えます。Ada2005の文法上の解決方法は、こういうものです。
procedure A is
y : コピーできない型;
begin
途中までyを使用して計算;
return x : コピーできない型 do
結果を計算してxにセット;
end return;
end A;return文上でxを宣言することで、xが特別であることがわかり、xが呼び出しもとのスタック領域に確保されるようになります。returnからend return;の間は、Result変数を宣言した状態です。明記していますので必要ならサイズも渡せます。
これで、コピーが出来ない値を返すことができるようになりました。
正確には、呼び出しもとの領域を使用することでコピーが出来ない値を返す機能がbuild-in-placeであり、拡張されたreturn文は別のため式だけで値が作れるならそう書けるのですが、説明したとおり機能としては表裏一体です。
……さあどこがおかしいでしょうか？
サイズ可変の型があるのに、呼び出しもとの領域を使用できてしまうのが変ですね。スタックは後から途中を伸ばしたり出来ないのですから。
そう、それこそが、gccバックエンドがprintfのような可変長引数をサポートしておきながら可変長返値をサポートせず、可変長返値を言語仕様に持ったAdaのGNATフロントエンドの暗黒面。
ううう、無駄に長くなった……。
