離散凸解析

数学

前に何かで知って気になってたので勉強してみた。

離散凸解析の考えかた 最適化における離散と連続の数理

離散凸解析の考えかた 最適化における離散と連続の数理

簡単に言うと
f(x)が下に凸ならば「f(a)が最小値 <->f'(a) = 0 」
などの連続関数に関する定理の離散関数版を考えるとかいった話。

んで, 離散関数にもいろいろあるらしくL凸関数とかL^{\natural}凸関数とか沢山でてきてはっきりいって全然理解できていないわけだけども, 連続世界と離散世界を自由自在に行ったり来たりできるスキルを身につけられたら面白いだろうなぁと感じた。

特に, 面白そうだと思ったのは最小費用流問題の項で, この本には詳しく書いていなかったのだけれども, フロー <-> 電流, テンション <-> 電圧, コスト <-> エネルギーといった対応により最小費用流問題は非線形抵抗からなる電気回路の問題と対応させることができるのだとか。そしたら, 今度は回路に関して成立する他の定理を離散化する事で, 最小費用流問題に関する別の解釈を自然に得る事ができるんだろう。


当然, コンパイラでの最適化に使えないか考えるわけですが, 例えばデータフロー方程式は直感的に何らかの保存則(流量保存則)に対応するだろうと思えます。するとデータフロー方程式を利用する種々の最適化は, 何らかの保存則が成り立つ一つの系の上での何らかの物理量の最小化問題に対応させて統一的に理解できるのではないかと思うわけです。

つまり

  • A最適化 <-> 系Xでの物理量Pの最小化
  • B最適化 <-> 系Xでの物理量Qの最小化

みたいに異なる最適化を一つの同じ系X上の問題とみなすことができるはずだと...。
例えば帰納変数除去とか共通部分式除去を部分冗長性除去が内包しているという事実も, 上のような見方ですっきり理解できそうな気がする。


それから例えばレジスタ割り当てはグラフカラーリング問題と同じわけでNP完全なのだけれども,
凸関数じゃないものに対しては離散凸解析は無力なのだろうか。あとNP完全であることと凸関数でないということは同値ではないのだと思うのだけど, よく分からなかった。


とりあえずもうちょっと勉強してみたいと思った。どうするのがいいだろう。
てか離散凸解析より前に凸解析を勉強すべきか。

C++の配列引数の問題

C/C++

C++0xの勉強をしていたはずが, C++の勉強になってしまっているorz

昨日C++0xではVLAがサポートされないと書いたが,これはもともとC++には配列引数にまつわる問題があるので, このあたりをいじりたくないという事情があるのではないかと思う。
前になんかの本で読んだけどすっかり忘れていた。

つまり, 派生クラスのポインタから基底クラスへのポインタへのアップキャストが暗黙に行われてしまうということが問題で

class A {
  ...
};

class B : public A {
  ...
};

void f(A x[100]){
  ...
}

int main(..) {
  B array[100];
  f(array);
}

みたいな事をすると, B*->A*と暗黙に変換されてしまうので要素のアドレス計算がくるってしまうという事が起こる。ということでこれはしょうがない。

これは残念だ。

[C/C++] C++のクラスに関する識別子規則

急遽C++0xを勉強することになったので, いろいろ見ていたのですが,
以下のコメントのやりとりが気になったので捕捉説明します。(と思ったらすでにid:uskzさんが指摘なさっていましたorz)

えーと…クラス名と同じ名前の変数って作れないですけど・・・
↓認識違ってます？

class widget {
　int widget;
};

http://d.hatena.ne.jp/faith_and_brave/20070925/1190716744#c

えーと, 実はクラス名と同じ名前のメンバ変数は定義する事が可能です。
例外的に「クラスがユーザ定義のコンストラクタを持つ場合についてのみ」クラス名と変数名は重複してはいけないということになっています。
つまり,

class x {
public:
    int x;  // OK
};
class x {
public:
    x();
    int x;  // NG
};

class x {
public:
    void f();
    int x; // コンストラクタがなければOK
};

ということです。
C++0xのドラフトでは"9.2 Class members"に書いてありますが厳密には,以下の物がクラス名と重複不可となっています。

  • staticなメンバ変数
  • メンバ関数名
  • クラス内で定義される型名(typedef名やインナーclass/struct/union/enum名など)
  • enum定数名
  • 無名unionのフィールド名 (無名classと無名structはどこいったんだろうか? C++0xのドラフトでは無名classと無名structを禁止する様な文章は見当たらないが...)
  • ユーザ定義コンストラクタがある場合のnon-staticなメンバ変数

「ユーザ定義のコンストラクタを持つ場合のみ」という奇妙な規則はC言語の名残でしょう。
"3.3 Declarative regions and scopes"などもぐちゃぐちゃしていて酷いことになっていますが, C++からの仕様なので今さら文句の付けようがないですけれども。

Cの理解出来ない文法

C/C++ Compiler

Cのパーサを書いた経験から, Cの全く理解不可能な仕様を幾つか紹介。

まずはこれ

int const long typedef volatile long volatile unsigned x;

これは

const volatile unsigned long long int

のxへのtypedefだけれども,Cの規格上正当でもちろんgccも通す文法.
規格ではここの文法がどう定義されているかというと,

  • 記憶域クラス指定子 : static extern typedef ..
  • 型指定子 : char short int .. unsigned ..
  • 型修飾子 : const volatile ..
  • 関数指定子 : inline

となっていて, 宣言文の最初に

  • (記憶クラス指定子|型指定子|型修飾子|関数指定子)*

を付けられるという文法になっている。
「文法上の都合」からtypedefは記憶域クラス指定子に含まれるので, typedefを途中に書くこともできる。

さらに, 型修飾子と関数指定子は何回書いても１個と見なすという奇妙な規則があり,例えば

int inline inline inline inline const const const const f(){
    ...
}

も正当な文法. inlineをたくさん書くとコンパイラがinlineに積極的になるとかそういうこともない。



まぁそれでも構文解析をするだけならば単純で、意味解析をするときにすごく面倒になる。
例えば並び順が決まっていたら,

const unsigned long int

を

int -> long int -> unsigned (long int ) -> const (unsigned (long int))

と自然に解析できるけれども, 並び順が任意だと「全ての修飾子をリストに入れる」->「ソートする」->「解析する」という事をしなければならない。(実際はパースしながらインサーションソートしつつ重複も同時に除くみたいな事をしたりする)
さらにunsigned単独ならunsigned intになる等、型なのか修飾子なのかが文脈で変化するという事も考慮しなければならない。

もっと問題なのが, 同じ構文が違う意味を持つという点。
例えば

static int x;
typedef int x;

は構文解析上は同じだが, 意味が全く違う。他にも

struct x {
  ...
};

と

struct {
  ...
};

と

int;

も構文解析上は同じだが,1つめは正当で2つめは警告で3つめはエラー。規格上2番目は禁止されてないので, エラーにしてはいけない。

struct x;
static struct x;
long struct x;

では2つめが警告で3つめはエラーなど,構文規則上区別できないものが違う意味を持つという事が多々ある。


Cの構文解析には他にも名前空間の問題とかもあるけれども、理解不能という意味ではこのあたりが一番だった。
パーサが書きやすくなるわけでもないし、Rubyの様にユーザが書きやすいようにパーサで苦労するというのとも違うし。yaccで書かなければ面倒じゃないのかもしれない。gccもcoinsも構文解析器使っていないのはそういう事情があるのかも。