謎の書きかけ小説メモ

数学

私は既にもう何時間も砂漠を歩き続けていた。足元をかさかさと歩く虫のような虚数や，時折生えている枯れそうな行列にももう慣れた。ずっと前にオアシスで汲んだ集合が水筒の中にあと少し残っていたはず…背負ったリュックを地面に下ろして開くと，関数に吹かれて飛んできた変数がリュックの中に入り込んだ。水筒の中身はあと僅かだった。集合…包含関係…平面図示，境界含む，含まない…。集合を節約しつつ一通りの証明を終え，私は一時的に喉を満たした。

私が迷い込んでしまったこの世界は，なにもかもが数学らしい。間違いのないように一つ一つ証明を確かめながら行動しないといけないため，何をするにも頭が疲れてしまう。というか私はもう気が狂いそうだ。だから一刻も早くこの世界から抜け出すために，私は今歩いているのだ。

私は歩き続けた…そして遂に，この世界の出口に繋がっているとされる巨塔，自然数にたどり着いたのだった。

私は自然数の入り口の前に立った。地面と同じ高さに1階があり，任意の階の上に「上の階」がある。2つの階が異なるならば，その「上の階」も異なる。1階の上には2階，2階の上には3階があり，それが永遠に続いていた。自然数は高く，上の方は当然雲に隠れて見えないのだが，近くで見ると意外と横にも大きかった。高さ加算無限の塔を支えるのだから当然だろう。

私は乗法単位元の定義を確認した上で，石の扉をゆっくりと開けた。

1階。ずっと一人で砂漠を彷徨っていた私は，そこに人がいるのに驚いた。壁にもたれかかって煙草をふかしていた，もう何日も風呂に入っていなさそうな男たちが，そろって私を見た。

「あんた，どこから来た」

「ええと，なんか迷い込んじゃって…気付いたらここに…」

「ふうん？」

彼らはそれ以上私に興味を示さなかった。

私は数1のもつ性質をおさらいしながら，薄暗い空間をまっすぐ進んでいった。任意の整数は1の倍数…即ち1を約数にもつ。1は素数ではない…1が素数だと定義しても何のメリットも得られないだろう，素因数分解の一意性が失われてしまうのが最大の欠点だろうか。1のa乗はaに関わらず1…aは整数，実数，複素数，いや今後どんな数学的概念を考えるとしても，そこに累乗という名の付いた演算を定義するならばおそらく1のa乗は1とするだろう。

しばらく歩き続けると，私の前に大きな壁が立ちはだかった。壁沿いに歩くと何かあるはずだ。右に行くか左に行くか少し迷ったが，どちらでも大して変わらないはずだと思い，右に行くことにした。そうして壁伝いにまたしばらく歩き，ついに壁の向こうに繋がるドアを見つけた。

ドアを開けると，その向こうにはまぶしい世界が広がっていた。老若男女たくさんの人々が楽しそうに笑って話していた。

「平方のmodをとるとさーww」

「あれ左辺は2の倍数じゃん？」

人種もさまざまだった。白人，黄色人，黒人が何の抵抗も無く語り合っていた。数学には国籍も人種も関係ない…平和な世界の一端が垣間見えた気がした。

そのとき，おいしそうないい匂いが漂ってきて，私はもう何日も集合しか口にしていないことに気付いた。空いていた近くの椅子に座って，テーブルの上の料理に伸ばした手が止まった…ええと，なんというか得体の知れないものだった。なんだコレ…累乗と割り算を含む式…が，整数となるような…組を全て求めよ…？私はその料理に全く手が付けられなかった。その横に添えてある小さな実だけでも食べようとして口に入れたがしかし…n以下でnと互いに素な正整数の個数…が，nと互いに素な正整数aの右肩に指数として乗っかっていて…nを法として1と合同…？全く，歯が立たなかった。何か他に，食べられそうなものは無いか…。辺りを見回しても，どのテーブルに置いてある料理も見たことの無いものばかり。私がおろおろしていると，一人の女性がやってきて私がさっき食べようとした固い実を手にとり，

「ん，たまにこの味が懐かしくなるのよねー」

そう言っておいしそうにかみ砕いた。私の唖然とした視線に気付いた彼女に

「どうしたの？」

と尋ねられ，私はしどろもどろになりながらやっと答えた。

「あ，あの…今のそれ，どうやって…ったんですか…？」

「ん，今のって…ああ，ファイ関数のやつ？」

「ファイ…関数…」

n以下でnと互いに素な正整数の個数…何に使うんだかよく分からないようなその関数には，ファイという名が付いていた。

「あなたここに来たばかりなのね。いいわ，教えてあげる。オイラーの定理と言う重要な定理よ」

定理1. (オイラーの定理)

nとaを互いに素な正の整数とするとき, a^φ(n)≡1 (mod n) (ただしφ(n)はn以下でnと互いに素な正整数の個数)が成り立つ。

C++の歴史

プログラミング

注. この記事は学校の課題で書いたレポートの内容を写したものです。

C++の誕生

C++を考案したのは, デンマーク人のビャーネ・ストラウストラップである*1[1]. 彼はケンブリッジ大学計算機研究所で, 博士論文のために複数のコンピュータに仕事を分散させて組織化する方法を研究しており, コンピュータ間の複雑な通信を再現する大規模なシミュレーションをSimulaというプログラミング言語を使って行っていた. Simulaは1960年代に作られた世界初のオブジェクト指向プログラミング言語であり, 名前の通りシミュレーションに適していた. 当時の他の言語と異なり, 全体のプログラムを小さなプログラムの集合体として作るという方式をとっていたため, 一つの大きなプログラムを作る方式より理解しやすく修正しやすいコードが簡単に書けた. 他にもバグを抑える包括的型チェックなどSimulaには様々な利点があったのだが, 残念なことに動作が重く, 大きなプログラムをコンパイル・リンクするのに膨大な時間がかかったため, 実際にシミュレーションを行ってデータをとることができそうになかった. このままではプロジェクトが中断してしまう. そこでビャーネは別の言語BCPLを使った. BCPLは1966年に作られたプログラミング言語であり, 後のC言語の元になったB言語の元になった言語である. シミュレーションに適していないBCPLでコードを書くのは大変に骨の折れる作業であった. 最終的にはなんとか機能するプログラムを作ることができたが, ビャーネは適切な道具（・・・・・）を使わずに難題に取り組むような真似を二度としてはいけないという教訓を得たのであった.

ケンブリッジ大学を去った後, ビャーネは早速適切な道具（・・・・・）を作ることにした. 結論から言うとそれはSimulaの機能を引き継いだ新しいプログラミング言語である. 彼は"A History of C++: 1979-1991"([2])の中で「良い道具」について次のように述べている:

  1. 良い道具はSimulaのプログラム構造 --- 即ち, クラス, 何らかの形のクラスの階層構造ヒエラルキー, 何らかの形による並行処理コンカレンシーのサポート, そしてクラスに基づく強い(=静的スタティックな)型検査機構タイプチェックシステムを持っているべきである. プログラム言語は, プログラムを実装するためだけのものではなく, 発明やデザインの過程を手助けするものであると, 私は見なしているのである.
  2. 良い道具は, BCPLと同じくらい高速なプログラムを作る能力を有し, BCPLの分割コンパイルされたユニットを結合する能力を引き継ぐべきである. C, Algol68, Fortran, BCPL, アセンブラなどの言語で書かれたユニットを一つのプログラムにまとめるためには, 簡単な統一規則が必要であり, そのため, どれか一つの言語固有の制限に捕らわれないようにしなければいけない.
  3. 良い道具は, 移植性の高い実装をも可能にするべきである. 私のこれまでの経験では, 私が「良い」機能を必要としていても, それが実装されるのは大抵その「翌年」であり, さらに実装されたとしても私の手に入りうる環境では動かなかった. つまり, 機能は多数の環境で実装されるべきであり(独占は特殊な環境のユーザや貧しい大学院生にとって満足できる対応ではない), かつ, 移行のための複雑な実行支援機構ランタイムサポートシステムではなく, 道具と環境のほんの少しの統合のみが必要たるべきだということである.

1979年春, ベル研究所計算機科学研究センターでのLANで接続されたコンピュータのネットワーク上でUNIXカーネルがどの程度の範囲まで分配されうるのかを明らかにする試みが始まってすぐに, いくつかの問題が生じた. ネットワーク通信を分析する方法と, プログラム内でカーネルの処理をモジュール化する方法が分からなかったのである. ビャーネは, それらの問題がまさに, かつて適切な道具・・・・・を使わずに取り組むような真似を二度としないと誓った難題であると気付き, すぐに適切な道具・・・・・の開発に取りかかった. 新しい道具を作るにあたって彼が注目したのが, プログラミング言語Cである. 1972年に開発されたCは当時既に普及していて実績があったため, それをベースとすることで技術分野のコミュニティに参加できるという利点があった. また, Cは基本的な機能を全て備えており, それでいて余計な機能が無いので動作が速かった. Cの持つ危険性はあまり問題ではないとみなされた.

1979年10月, 彼はCにSimulaの機能を付け加えるために, Simula風のコードをCに変換する前処理器プリプロセッサCpreを作った. 書いたコードを一度Cに変換してから動かすことで, 高速な動作を可能にしようと試みたのである. Cpreはその後洗練されてゆき, 1980年の3月には実際のプロジェクトで使われるまでになった. Cpreに通すコードの言語をC with Classesと呼んだ. 中断や再開が可能なコルーチンをサポートするタスクシステムは, C with Classesの有用性にとって必須であり, 後のC++において鍵となる最初のライブラリになった.

次の4月から10月までの間にC with Classesは「道具」というよりも「言語」として認識されるようになったが, まだモジュール性と並行処理の機能を備えたCの拡張としかみなされていなかった. しかし, Cに本来存在しない並行処理をサポートするライブラリを書くためにクラスの継承とメンバ関数を利用した際にある重大な決定がなされた. 各々が別のモデルの並行処理を必要としている数々のアプリケーションのために, 観点の違う複数の並行処理を表現可能にすること. この決断が下されたことでこの言語は, 特定の分野のアプリケーションのためだけの拡張機能を持つCの変種にはならず, プログラムを作るための一般的な機能を提供する汎用言語になった. また, C並の実行速度, コードのコンパクトさ, データのコンパクトさを実現することがC with Classesの明確な目的であったため, 実行時の余分処理ランタイムオーバーヘッドによるプログラムの3%もの効率低下が指摘されるとすぐに余分処理は削除され, クラスオブジェクトの管理ハウスキーピングデータ*2も置かれなかった. さらに, C with Classesが使用できる状況が制限されることを防ぐにはCでできることと同じことがC with Classesでもできる必要があったため, Cのビット操作などの極めて低レベルな操作や型システムを意図的に破壊する危険な機能をC with Classesから取り去ることはできなかったが, 他の機能を充実させることでそのような推奨されない機能に頼る必要性は排除された. C with Classesはプログラマーに特定のスタイルを要求することなく, むしろ効果が実証された様々なスタイルを奨励し, よくある罠や落とし穴に引っかかることが無くなるように設計された.

このような数々の工夫により, 1982年の間にC with Classesは小さな成功を収めた. ここにおいてビャーネはC with Classesの後を継ぐ言語を作ることにした. 新しい言語の名前は「new C」や「C84」などの紆余曲折を経て「C++」となった*3. これがC++の誕生である. 1985年, C++で書かれたC++からCへのトランスレータをCで書かれたC++のインタプリタをコンパイルしたものに通したものに自身をトランスレートさせたものをCのコンパイラに通すという手法を用いて, 最初のC++のコンパイラCfrontが作られ, リリースされた. C++の標準規格としてThe Annotated C++ Reference Manual(注解C++リファレンスマニュアル)が出版される1989年までの間, CfrontそのものがC++の規格だった.

初期のC++で, Hello worldを表示するコードは次のようになる[3]:

#include <stream.h>
int main(){
    cout << "Hello, world!\n";
}

これをC++のコンパイラがトランスレートし, Cのコンパイラがコンパイルし, リンカがI/Oストリーム用のオブジェクトファイルとリンクし, Munchがパッチを当てて*4, 最終的に「Hello, world」と出力するプログラムが生成される.

その後ARMがC++の機能を明文化し, テンプレートの仕組みを大幅に改善したり, 膨れ上がるライブラリへの対策として名前空間を導入したりした. また, C++が爆発的に普及するとともに公式な標準化が求められるようになったためAT&Tベル研究所の協力とHewlett-Packard社の主導のもとに1989年から開かれたANSI X3J16 C++標準化委員会は, 1991年ISO C++標準化委員会と合わさってWG21としてC++の規格を作り上げていった. 言語仕様や機能, ライブラリをよりよくすると同時に, 言語の方言化や沈滞を防ぐことを目的とした尽力の結果, 1998年ついに最初の標準規格であるISO/IEC 14882:1998が制定された. その後見つかったバグは2003年の改訂版ISO/IEC 14882:2003で修正された. AT&T, Borland社, IBM社, Microsoft社, Texas Instruments社など多くの組織や人間がそれぞれ独自の信念のもとに関わって作ったこの規格の中には後に短所が発覚した例外などの機能もあったが, 後から大きく規格を作りかえて混乱をまねくような真似はできないため, C++の仕様は今後非常に複雑な進化をとげてゆくことになる.

テンプレートとSTLの進化

C++の標準ライブラリ(Standard Template Library, 通称STL)には可変長配列ベクタ, 連結リストリスト, 順序付集合セット, 連想配列マップなど数々のコンテナがある. ここで, 総称的ジェネリックプログラミングと呼ばれる, 「コンテナはどんな型も要素として扱うことができるべきだ」(即ち, 例えばvectorは整数の配列も浮動小数点数の配列も, さらには配列の配列も扱うことができるべきである)という理想を実現するために, C++における最大の闇と言われる, テンプレートというものが使われている. C++においてテンプレートは重要な位置を占めており, C++はテンプレートとともに進化してきた. テンプレートで書かれたSTLのおかげで平衡二分木などの高度なデータ構造を楽に使えるようになり, もっと言えば自分で実装する能のない未熟なプログラマも気安く取り扱えるようになった. もっとも, 理解もせずにSTLを適切に使い分けられるかどうかはまた別問題だが. ただ木の回転などの複雑な処理は理解できても実装するのが大変なことがあるため, それに時間を費やすよりも専門のプログラマにより確実に最適化して実装されているSTLを使うというのはよい判断である.

STLはメモリ確保と解放*5の処理を選り分けて「アロケータ」と呼ばれるクラスにやらせている. コンテナの核心となる要素追加や探索などの処理と違って, メモリ操作の仕方だけは型ごとに異なるためである. だから, コンテナのテンプレート引数は本来は要素の型TとそのアロケータAの2つなのだが, 例えばvector<int, allocator<int>>などと書くのが面倒なので, 定義の際にtemplate<class T, class A = allocator<T>>と既定することでallocator<int>を省略してvector<int>と書けるようにしている. このことはコンパイラが吐くエラーメッセージによく表れてくる.

1998年のC++98で標準ライブラリにSTLとして用意されたコンテナは, vector, list, dequeの配列コンテナ3種, map, multimap, set, multisetの連想コンテナ4種, queue, priority_queue, stackのコンテナアダプタ3種, そしてstringやvalarray, bitsetなどのコンテナ相当である. これらは整理のために全てstd名前空間の中に入っており, 外から呼び出すときは名前の前にstd::を付ける必要がある*6. C++の規格はそれぞれのコンテナについて「どの機能を持たなければいけないか」を規定したが, 「それらをどのようなアルゴリズムを用いて実装するか」についての規定は一切しなかったため, コンパイラによって差異がある可能性がある. vectorは可変長配列で, 各要素への直接参照ランダムアクセスが定数時間で可能である. 末尾に適度な空き領域を設けておくことで, 要素の末尾への追加プッシュバックや末尾からの削除ポップバックもかなり高速に行ってくれる*7. 挿入についても他のコンテナを上回るほどの高速性を見せる[5]. 演算子ではなくat関数を使うことで範囲外アクセスも防いでくれる. また要素にbool型を指定したときだけは1要素あたり1ビットしか使わないように特殊化されている. listは双方向連結リストで, 各要素から「次の要素」と「前の要素」が参照できるようになっていて, 要素の挿入と削除が定数時間で可能である. dequeはvectorよりも定数倍遅いが, 末尾だけでなく先頭にも空き領域を持っていて先頭への追加プッシュフロントも定数時間で可能なので, ARC077-C「pushpush」などのごく稀に特殊な状況において効果を発揮するらしい. またvectorよりも中間挿入が定数倍速いという説もある[6]. set, multisetは順序付き集合で, 比較可能な型に対して「要素を追加する」操作と「値を指定して, それに等しい要素が存在するか調べる, あるいは個数を数える」操作がともに対数時間で可能な二分探索木である. 「赤黒木」と呼ばれる平衡二分探索木によって実装されることが多い. それぞれのノードに対して子への参照が高々2つ格納されており, 一方の子孫は全て親より小さく, もう一方の子孫は全て親より大きいため, 根から順に大小比較を繰り返せば高速に探索できるのである. 注:蟻本に載っている. しかし昇順配列を先頭から追加するなどの特殊なケースにおいて偏りが生じないように, 常に回転処理を行って平衡を保つ必要がある. 注:蟻本にすら載っていない. setとmultisetでは, 既に存在する値を追加したときの挙動が異なる. キー(要素)の型K, アロケータAの他に, キーを比較するbool型関数を()演算子bool operator()(const K &x, const K &y) constとして持つ関数オブジェクトCをテンプレート引数にとる. Cはデフォルトでヘッダfunctional内のless<K>となる. テンプレート引数が省略されたときは前から順に適用されるため省略しない引数よりも前の引数を省略することができないので, より省略されやすいアロケータAが最後に置かれてtemplate<class K, class C = less<K>, class A = allocator<K>>となる. map, multimapは順序付き連想配列で, set, multisetの要素をキーと値のペアとしたものである. キーを指定して要素の追加と検索が対数時間で可能である. 配列が大きすぎて持てない場合によく役立つ. multimapでは同じキーに複数の値が対応するため, 値を取り出すためにはpair<multimap<K, V, C, A>::iterator, multimap<K, V, C, A>::iterator>型の変数が必要となる. queueはdeque, stackはvectorを内部に保持していて, それぞれFIFO(First In, First Out), LIFO(Last In, First Out)による要素の追加・取り出し・削除のみが可能である. テンプレート引数にdeque<T>, vector<T>をデフォルトとする内部コンテナCを持つ. priority_queueは要素の追加と最優先要素の取り出しがともに対数時間で可能で, 通常ヒープを用いて実装される. 優先度は普通「より大きい」または「より小さい」で, テンプレート引数Cmpで指定する(ただし最も優先度が低いものから取り出される). ヒープは完全二分木で, 常に親より子がCmpたるように保たれるため, 根が最もCmpでない要素となる. 内部コンテナはvectorである. テンプレート引数は<T, C, Cmp>であるから, 優先度関数Cmpを指定するためにはコンテナCも指定しないといけない. このように仕様に多少の欠陥が見られるが, ダイクストラ法やプリム法などでよく使われ有用性は高いので重要である(ただしダイクストラ法やプリム法は1980年代に発明されたフィボナッチヒープによってさらなる高速化が可能となってしまった). stringは文字列で, C言語の文字列charの使いにくさを克服するために作られたものである. =演算子による代入や==演算子による比較が可能で, 他のコンテナの要素としても安全に使用できる. valarrayは配列で, 2つの配列の各要素を加減乗除したり, 要素の総和, 最大値, 最小値を求めたり, いくつかおきに要素を抽出したりする処理が最適化されている. bitsetは固定長ビット配列で, 複数のビットをまとめて論理演算やシフトが効率的に行える. 2n通りの組み合わせが考えられるビット探索などで動的に使用すると絶大な効果を発揮する.

これらのSTLには, 要素を参照する手段としてポインタの代わりにイテレータというものが用意されている. 先頭のイテレータはbeginメンバ関数, 末尾のイテレータはendメンバ関数で得られ(ただしend関数が返すのは末尾の次の要素へのイテレータ), 単方向イテレータは++演算子によるインクリメント, 双方向イテレータは加えて--演算子によるデクリメント, さらにランダムアクセスイテレータは2項+演算子, 2項-演算子による移動や[]演算子によるアクセスも可能となる. コンテナを先頭から末尾まで走査するときなどによく役立つが, イテレータで指定した要素を削除するときなどはコンテナによって挙動が異なるため注意が必要である.

STLの他には安全なスマートポインタ*8auto_ptrを提供するmemory, ソートや二分探索をするalgorithm, 三角関数指数対数累乗平方根絶対値床天井などを算出するcmath, 国による環境の違いに対応するためのlocaleなどが標準ライブラリに用意された.

C++98が発行されたのち, 当時のC++の標準ライブラリに足りなかった機能を補うために, 有志プログラマのボランティアによってオープンソースのライブラリであるBoost C++ Librariesが作られた. 汎用整数を扱うBoost.Integerを皮切りに, 分数を扱うBoost.Rationalや関数オブジェクトを扱うBoost.Functionalなど次々と有用なライブラリが実装されていった. 開発者の中にはC++委員会のメンバも多くいた. さて, WG21は東芝, 日立, 富士通, NECを含む日本企業の合弁組織に促されてthe Performance Technical Report(TR)をもとにC++に足りないものをかき集め, C++を大きく進化させるために動き始めた. ビャーネ他委員会のメンバは, 規格というものは多くの人に広まらないと欠点が見つからないため, 一定の期間が経過するまで新機能の開発を開始してはならないという規則がISOに存在すると思って2002年までC++の新機能の作業を始めなかったのだが, 実はそんな規則は存在しなかった. このせいでC++の進歩は大きく遅れた. 新たなC++には2つの目標が設定された: C++を, (数値計算やWindowsアプリケーションに特化した機能でなく)システムプログラミングとライブラリ構築に適したよりよい言語にすること, そして, より画一的かつ確実で初心者にとっても使いやすく, 教育に適したものにすることである. 新しい規格はC++0xと呼ばれ, 公開時にxに年数を入れる予定だったが, 結局間に合わずにC++11(ISO/IEC 14882:2011)となった. C++11では標準ライブラリが強化されただけでなく並行処理が可能になったが, GUIやインターネットに関するライブラリはTR2に回されるなどして実装されなかった.

また, テンプレートはそもそもSTLを書く手段として作られたものであるが, そのために再帰テンプレートや特殊化による分岐処理をできるようにした結果, C++のテンプレートがチューリング完全*9になっていることが2003年明らかになった[7]. つまりコンパイラが吐く実行ファイルではなくコンパイラそのものに任意の処理をさせられるのである. さらに展開に失敗してもめげずに他の可能性を試すSFINAE(Substitution Failure Is Not An Error, 置き換え失敗はエラーではない)を利用することによりコンセプトを指定したテンプレートメタプログラミングの可能性がさらに広まった. C++ユーザーが新たなコーディング技術を次々と発見するため, 委員会はC++をそれらに適した形に変えていかなければならなかった. C++11ではauto型推論, decltype型取得, usingエイリアスが追加された.

C++11を作る際に大きな弊害となったのが, 互換性であった. 2004年時点で3,270,000人がC++を使っていたため[8], C++の悪い機能を勝手に削除して古いC++で書かれたコードが動作しなくなってしまうと, 甚大な被害が出る恐れがある. 利用者の中にはMicrosoft社やApple社の人間も多くいた. もういっそ全てのファイルに「このコードはC++○○で書かれています」とでも書かせておけばよかったのだが, 残念ながら20世紀にそんな発想は無かった. 幸いにして, 賢いプログラマたちは悪い機能を使うことを自ら避けていたため, 「この機能は非推奨で, いずれ削除されます」と発表することで解決を図ることができた.

C++11ではauto, 拡張for, ラムダ式などの言語仕様が追加され, 冗長なコードが非常に簡潔に書けるようになった. 例えばそれまでfor(std::vector<int>::iterator it = v.begin(); it != v.end(); it++) std::cout << *it << std::endl;と書いていたものはfor(auto i:v) std::cout << i << std::endl;となる. constexprによるコンパイル時定数計算も可能になり, プログラマの手間がさらに省けた. また, 標準ライブラリにたくさんの機能が追加された. 並行処理に関する機能はthread, mutexの他に高レベルなfuture, promiseから低レベルなatomicまで幅広くサポートされ, 安全な資源管理ポインタunique_ptr(コピー不可), shared_ptr(コピー可, 遅い), weak_ptr*10, タプルtuple(3つ以上の変数の組), 正規表現regex(文字列をより解析しやすくなる), 乱数を扱うrandom_device(処理系ごとに非決定論的で予測不可能な乱数を生成する)などの新たな機能も追加された. また, テンプレートの山括弧を2つ続けて閉じるときにスペースを開ける必要を無くすというちょっとした配慮もなされた. また, オブジェクトのアドレスを取得する手段としてはもともと&演算子が用意されていたが, &演算子の中身を自由に再定義オーバーロードして改変できるようになったため, 絶対に正しくアドレスを取得するための新たな手段としてaddressof関数が用意された. cmathヘッダの数学関数には逆双曲線関数, 2を底とする指数対数関数, 指数が0に近いときの指数対数関数を高精度に計算する関数, 立方根をとる関数, 2つの実数の平方和の平方根(言い換えると直角三角形の斜辺や2点間の距離, ベクトルの大きさ)を算出する関数, 誤差関数と相補誤差関数, ガンマ関数(階乗)とその自然対数, ゼロ方向への丸め, 四捨五入, そして丸め方を指定できる丸め関数, 小数の余りあり割り算, 2つの実数を与えると絶対値を変えずに一方の符号を他方に合わせる符号関数, NaNを生成する関数, 実数をできるだけ小さく増やす, または減らす関数, 2つの実数の最大値, 最小値, 差を求める関数, 掛け算と足し算を同時に行う(3つの実数x, y, zを与えるとx*y+zを計算する)関数, 数の属性(有限か無限かなど)を判定する関数, 大小比較関数が追加された.

そしてSTLには固定長配列array, 単方向連結リストforward\_list, 非順序連想コンテナunordered_map, unordered_multimap, unordered_set, unordered_multisetが追加された. arrayはコンパイル時に大きさが決定するためC配列に近い. forward_listはlistと違って次の要素は参照できるが前の要素は参照できない. unordered_が付いた連想コンテナは二分木を使わず, キーをハッシュ関数で小さな整数に変換して要素への参照番号とするため, 要素をイテレータで順番に取り出すことはできない.

Boostの方では, 2011年に計算幾何を扱うBoost.Geometry, 2013年に多倍長整数, 多倍長浮動小数点数(理論上無限の精度をもつ)を扱うBoost.Multiprecisionが追加された. 標準委員会が2014年に制定したC++14(ISO/IEC 14882:2014)ではunique_ptrを生成するmake_unique関数*11が追加され, autoやconstexprが拡張された. C++14を策定する際に組織されたStudy Group(SG)の成果はC++14では追加されなかったが, C++17の革新的な機能に貢献した. 2017年にはC++17(ISO/IEC 14882:2017)が策定され, 構造化束縛ストラクチャードバインディングによりついに関数が複数の値を返すことができるようになった. また長年プログラマ, 特にコードゴルファーを苦しめてきた副作用完了点問題も, ついに評価順序が規格上厳密に定められ処理系依存でなくなることにより解消した. 「Clangを信じろ」の時代は終わり, 「ちょっとかっこよくショートコーディングしてみる」というプログラマにとってのささやかな楽しみが許される時代が来たのである. また任意の型を代入できるanyクラス(もとはBoostにあった)の登場によりRubyのような全てのオブジェクトの元となるスーパークラスが疑似的に再現できるようになった. cmathヘッダの数学関数にはベータ関数, 指数積分, エルミート多項式, ラゲール多項式, ラゲール陪多項式, ルジャンドル多項式, ルジャンドル陪多項式, 球面調和関数のθ成分, 第一種完全楕円積分, 第二種完全楕円積分, 第三種完全楕円積分, 第一種不完全楕円積分, 第二種不完全楕円積分, 第三種不完全楕円積分, ノイマン関数, 球ノイマン関数, 第一種ベッセル関数, 第一種変形ベッセル関数, 第一種球ベッセル関数, 第二種変形ベッセル関数, そしてリーマンのゼータ関数が追加された. numericヘッダには最大公約数と最小公倍数も追加され, これらをプログラマが自分で実装する必要は無くなった.

*1:Wikipediaにはビャーネ・ストロヴストルップと記載されており, 実際の発音もストロヴストルップに近いものであるが, 綴りがBjarne Stroustrupなので英語圏ではストラウストラップと呼ばれることが多いようである.

*2:オブジェクトのメンバをメモリ上のどこに配置するかを記憶する管理データを新たに設けると余分なメモリ領域を消費して処理時間も遅くなるが, メンバをそれぞれ独立に扱えばそのコストは無くなる.

*3:「++」はCにおいてインクリメント, 即ち「1つ先へ進む」ことを意味する.

*4:コンパイルした複数のファイルをリンクするだけではグローバルオブジェクトのコンストラクタやデストラクタを呼び出すことができないので, 実行ファイルにパッチを当てる作業が最後に必要となる.

*5:ときどき「解放」ではなく「開放」と書かれていることがあるが, C++に限らず多くの規格書などによれば「開放」ではなく「解放」が正しいとされている.

*6:using namespace std;という「魔法の呪文」を書いておけばいちいちstd::を付ける必要はなくなる.

*7:g++では新たにメモリを確保するときにもとの2倍の領域をとるが, メモリ効率を考えると黄金比より少し小さい1.5倍が適切だという説もある[4]. vectorには一応空き領域のキャパシティを調整する機能もついているが, そんなことをしたがる人がもしいるとしたら自前で配列クラスを作っているだろう.

*8:C言語のポインタはコンピュータのメモリを直接書き換えることができる. いくら熟練したプログラマでも複雑なプログラム内で間違った場所のメモリを書き換えてしまうことがあり, 昔はそれがシステムの破壊につながることも多かった. 最近のOSではプログラムがクラッシュする程度で済むが, ポインタが危険だという考えは根強く残っている. 安全を確保するためにコンパイルにかかる時間が長くなったりプログラム自体が少し遅くなったりするのは, プログラマに快適なコーディング環境を提供するための小さな犠牲である.

*9:コンピュータを一般化した仮想の機械チューリングマシンと同じことができるということ. つまり現代のコンピュータを使って計算可能な処理ならば, 理論上全て可能である.

*10:これら3つが追加されたことによりauto_ptrは非推奨とされた

*11:委員会メンバーのブログ[9]によるとC++11では実装し忘れていたらしい.

数学的でない命題に自分を食わせる

「どんな法則にも例外がある」という命題があります。

この命題について考えるためには，まず「法則」とは何なのかはっきりとさせなければなりません。

例えばそうですね…英語における文法規則としてみましょうか。そして次のように捉えます：

 

規則1：肯定文は主語＋動詞の順番。(例外：Never have I seen such a beautiful sunset.)

規則2：不完全自動詞の場合動詞の後に補語が来る。(例外：The cat is in the kitchen.)

：

規則xxx：任意の規則 n (1≦n≦xxx) について，これを満たさないような場合が存在する。

 

そして今後 xxx = 0 とし，規則0即ち「例外の法則」について，規則0自体がこれを満たすのかどうかを考えます。

 

次の2つの場合が考えられます。

(1)規則0を満たさないような場合は存在しない。

(2)規則0を満たさないような場合が存在する。

 

(1)の場合，規則0を満たさない例として，規則0そのものが挙げられるので矛盾，よって規則0は偽です。

ならば(2)は真か？規則0の存在によって命題の排中律が脅かされていることに注意してください。

(2)の場合，さらに2つの場合が考えられます。

 

(2.1)任意の規則 n (1≦n<xxx) が規則0を満たす。

(2.2)ある規則 n (1≦n<xxx) は規則0を満たさない。

 

(2.1)任意の規則 n が規則0を満たすならば，規則0自体が規則0を満たさないので矛盾します。

(2.2)規則0を満たさないような規則 n が存在するならば規則 n や規則0が規則0を満たさないので，規則0は真です。

 

よって矛盾の発生しない(2.2)のみが真実となります。

 

これを日本語的に言うと，例外の法則自体にも例外があるという結論が最も正しいということになります。

 

もう一つ，数学的でない命題を考えてみます。

「何事もほどほどに」という命題です。

例えば身長は高ければ高いほど良いわけではなく，(様々な条件を揃えてたくさんのパラメータをスカラー値に写像して考えれば)最適な身長 x0 cmが定まります。

さて，ここでまた新しい命題が生まれました。「身長は x0 cmに近ければ近いほど良い」です。これに対して「何事もほどほどに」を適用するとどうなるでしょうか。

「x0 cmに程よく近いのが良い」つまり「ある身長x1 cmとx2 cm (x1, x2は x0 に程よく近い)が存在して，x1 cmまたはx2 cmに近ければ近いほど良い」です。もう分かりましたね。このやり方を再帰的に繰り返すことによって，どんな身長についても，「それは最適ではない」ということになってしまいます。

この問題に対しては面白い解決策があります。

「x cmに近いほど良い」に「何事もほどほどに」を適用して「x cmに程よく近いのが良い」とする操作を何度も行おうとしているわけですが，この「何度も行う」というところに対して「何事もほどほどに」を適用すると，この操作はどこかでストップさせなければなりません。ほどほどなところで，です。

よって最適な身長がすっきりと求められることになります。

 

やってみたい人はこの理論を反駁してみてください。

 

以上です。読んで下さってありがとうございました。

ペンキ

プログラミング

一次元DPが大好きなので，ペンキ問題について書きます。

ペンキ問題は

おいおい，使いかけのペンキの缶を放っておいたら中のペンキが乾いてしまうよ。 | OJ

板がn枚あり，i番目の板の面積はsiです。

ペンキの缶がたくさん(加算無限個)あり，1缶分のペンキで面積Sを塗ることができます。

板のうち何枚かを選んで全てペンキで塗り残しなく塗りたいのですが，一度ペンキの缶を開けたら，中身を全て使い切らなければいけません。

塗れる面積の最大値を求めて下さい。

という問題です。

この問題を見て全探索とか考えてる人はね，DPの威力を思い知れよ。

はい，動的計画法は，値が整数であることを利用して大きな表を作るのが特徴です。

今回は，大きさΣs+1の1次元配列を使います。塗れるかどうかにだけ着目するのでstd::bitsetでいいです。

i番目までから選んだものの和としてありうるものは，i - 1番目までから選んだものの和としてありうるものにi番目の値を足したものと足さなかったものなので，動的計画法でできます。計算量はΣisi(だと思う)。全探索O(2^n)に比べれば，はい。(制約によるけど)

コードはこうなります：

#include <iostream>
#include <bitset>

#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)

int main(){
	int n, s[110], S, sum = 0, hoge = 0;
	std::bitset<1100000> able(1);
	std::cin >> n;
	REP(i, n){
		std::cin >> s[i];
		sum += s[i];
	}
	REP(i, n){
		RREP(j, hoge + 1) if(able[j]) able[j + s[i]] = 1;
		hoge += s[i];
	}
	std::cin >> S;
	for(int i = sum / S * S;; i -= S) if(able[i]){
		std::cout << i << std::endl;
		return 0;
	}
}

 いいですか，このやり方は強いですよ。std::bitset<1100000>をstd::array<int>(sum)に変えれば選び方を全て区別して，条件を満たすものが何通りあるかを調べることができます。似たような問題がatcoderで何度も出題されています。

 

強いので，普段使っていないという方は是非使って下さい。強くお勧めします。

 

ではまた。

スタックとレジスタ

プログラミング

関数呼び出しにおいて，実引数はスタックまたはレジスタで渡されます。

適当なコンパイラでは関数は「まずスタックを読み込み，読み切ったら今度はレジスタから読み込む」という方式を採用しているようです(Borland，EasyIDECなど)。

これを利用して，次のようなコードが書けます。

#include <stdio.h>

int main(void){
	int i = 3, j = 11, k = 36;
	printf("%d %d %d\n");
	printf("%d %d %d %d\n", j * k = i * j = 5);
}

これをEasyIDECで実行すると，

「36 11 3

75 15 5 3」

と出力されます。printf関数は，「%d」を見つけて次の引数を読み込もうとしますが，スタックに何も格納されていないので，レジスタから値を読み込んでいるのです。

というかそもそもこのコード，左辺値でないものに代入しています。これは本来コンパイルエラーになるはずですが，EasyIDECはアマアマですね，プロじゃない。

どうやらEasyIDECは右から計算するようです。「j = 5」「k = i * j」「j * k」の順に計算され，EAXレジスタには75，ECXレジスタには15が残されます。printf関数はこれを読み込んでいるわけです。

恐ろしいですね。

 

やっぱりgccやclangを使いましょう。

ポインタとconst

プログラミング

ポインタはアドレスを格納する変数。

constは変数を書き換えないようにする修飾子。

この2つを組み合わせると面倒です。

int main(){
	int a, b;
	const int *p = &a;
	a = 10;
	//*p = 10;	エラー
	p = &b;
}
int main(){
	const int a = 10, b = 0;
	int const *p = &a;
	//a = 10;	エラー
	//*p = 10;	エラー
	p = &b;
}
int main(){
	const int a = 10, b = 0;
	//int *p = &a;	エラー
	p = &b;
}

 const int *型(int const *と書いても同じ)は，const int型へのポインタです。

int main(){
	int a, b;
	int * const p = &a;
	*p = 10;
	//p = &b;	エラー
}

 int * const型は，int型へのconstポインタです。

int main(){
	int a, b;
	const int * const p = &a;
	//*p = 10;	エラー
	//p = &b;	エラー
}

const int * const型(int const * constと書いても同じ)は，const int型へのconstポインタです。

ポインタのポインタをとってみましょう。

int main(){
	int a;
	int *p1, *p2;
	int **pp = &p1;
	**pp = 10;
	*pp = &a;
	pp = &p2;
}

これにconstを付けてみます。

int main(){
	int a;
	int *p1;
	const int *p2;
	const int **pp;
	//pp = &p1;	エラー
	pp = &p2;
	*pp = &a;
	//**pp = 10;	エラー
}

const int **は，const int *型へのポインタです。int *型はconst int *型に変換されましたが，int **型はconst int **型に変換できません。

int main(){
	int a;
	int *p1;
	int * const * pp;
	pp = &p1;
	//*pp = &a;	エラー
	**pp = 10;
}

 int * const *型は，int * const型へのポインタです。int **型はint * const *型に変換できます。int * const *の参照先のポインタは変更できませんが，参照先の参照先は変更できます。

int main(){
	int a;
	int *p1, *p2;
	int ** const pp = &p1;
	//pp = &p2;	エラー
	*pp = &a;
	**pp = 10;
}

int ** const型は，int *型へのconstポインタです。

思考と言語

この記事は完全に僕の独自の考えであり，決して学術的なものではないということを最初に断っておきます。この内容は安易に信じないでください。

 

まず，一つの事例を見てみましょう。

一家の息子であるTさんは，普段から自然に人の求めていることを察知できる人間でした。ある日来客があり，Tさんは客人に対して数々の自然な気配りをしました。客人が帰った後，母親はTさんに対して「Tは気配り上手ね」と言いました。すると次の日から，Tさんは人に対する気配りの仕方が分からず，逆に人に迷惑をかけるようになってしまいました。一体どうしたのでしょう。

 

この事例には，言語と思考の関係が顕著に表れています。言語と思考の関係について見ていきましょう。

 

まず，言語が無い状態で思考はできるでしょうか。これに関しては野矢茂樹さん他たくさんの研究者が研究しています。結論から言うと，言語が無いと論理的思考はできません。なぜかというと，言語が無いと，現実にないことを仮定することができないからです。仮定ができないと，未来を見通すこともできないし，後悔も生まれない。つまり言語は高等な思考に必須だということです。

では，実際の思考において言語はどのような役割を果たしているのか。

簡単に言うと，言語とは「今と過去を結びつける」ものです。今起こっている出来事を言語で表して，過去起こった同じような出来事と結び付ける。それを繰り返して，思考というものは成り立っています。逆に言うと，言語を使っている限り，思考は「過去に縛られている」ということです。過去に無かったものを新しく考え出すことは容易ではありません。むしろ，言語を以て何かを考えるときには必ず過去に考えたこと，感じたことと照らし合わせながら考えているのです。

また，言語で表現することによって，思考を外側から観測することと記憶・記録することが可能になります。メタ認知は言語で表現してから生じるものです。

ここまでは多くの人が常識と捉えているでしょう。

 

問題は，「思考を言語で表現する」ことはできても，「言語で表現された通りに思考する」ことはできないということです。「思考→言語」の変換は不可逆であり，「言語→思考」の変換ができません。

ある思考を一度言語化して観測すると，その観測した記憶が残っている限り，その思考を再現することはできません。観測した記憶を思考の記憶よりも先に思い出してしまい，思考の記憶から思考を再現する余地を失うからです。これが，最初のTさんの事例で起こっていたことです。

 

この現象を防ぐことは，残念ながらできません。では，起こってしまったときにはどうすればいいのか。

かつての自分の思考がどんなものであったかを，少しずつ思い出していくより他はありません。無理に思い出そうとしてはいけません。あまり悩まずに過ごしていれば，そのうちふっと思い出すときが来るかもしれません。ただその時を待つのみです。

 

この記事はここで終わりです。読んで下さってありがとうございました。