Syoyo Fujita's Blog

raytracing monte carlo

Month: May, 2009

GM to file Chapter 11?…

さて、6/1 に発表されるという GM の行方ですが…
そもそもなんでこんなことになったのか、
駆け込み需要(?)として GM 関連の書籍を読んでみました.

そこで分かったことは、単純に大企業病にかかって経営がうまくいかず… というわけでもなく、
UAWや年金の問題というのも見えてきました.

なぜGMは転落したのか―アメリカ年金制度の罠
http://www.amazon.co.jp/dp/4532353521

書いたひとはロジャー•ローウェンスタインと、LTCM 破綻に関する本を書いたひとでもあります.
GM とありますが、内容の多くは副題にあるように年金制度に関するものです.

簡単にまとめるとこんな感じ.

-> 1900 年代前半、もともと労働者は虐げられ、年金も社会保険も無く働いていた…
-> 労働者にも権利を! UAW(組合)結成. ストして権利要求します!
-> GM: 働いてくれなくては困る… まー儲かっているし、いろいろ権利認めてやるよ
-> UAW: 年金、社会保険、家族への福利厚生とかゲット!
-> 世界恐慌到来.
-> GM: すいません、景気わるいんでリストラします.
-> UAW: オラオラー、勝手に首切るなー、雇用を保障せよ、ストします!
-> GM: 働いてくれなくては困る… 分かった、雇用保障します. 仕事なくて働いてなくても賃金 95% 保証するよ.
-> その後、GM は成長し、それにともない UAW の要求もエスカレート. 年金とかスゲー額に.
-> GM: まあ儲かってるからまだ問題ないでしょ. それに年金支払いは数十年後だし…
-> エコ社会到来、競争も増してきて、経営が苦しくなる
-> さらに高齢化社会到来、退職者への年金支払いとかのコストが増える
-> 2000 年頃からさすがにダメオーラが出始める…
-> GM: 無理っす、もう年金とか払えません…
-> UAW: いやいやダメだ、オレらが勝ち取った権利は手放さん!なんとかすべし.
-> そんなこんなで現在に至る.

なるほど、だから GM の破綻に関連するニュースでは、「UAW が…」 と組合がよく引き合いに出されていたのですね.
今の GM という会社はいったい誰のものなのか、考えされます.
こうも利害関係が複雑になると、会社の経営というのも大変ですね.
経営者は好き勝手にやるわけにもいかず、いろいろなことを考えなくてはなりませんね…

[Paper, ICFP09] ICFP09 papers: review5

[Paper, ICFP09] ICFP09 papers: review4 の続きです.

Complete and Decidable Type Inference for GADTs

GADTs は, データ不変性やプログラムの正しさを確証するための価値のある言語拡張であることが証明されています.
しかしながら、GADTs には, 型推論を行うときに困難な問題あります.
モジュラーな型推論に必要な原理型性質(principal-type property)を失ってしまうのです.

GADT パターンマッチによる局所型仮定(local type assumptions)のための新しくシンプルな型推論のアプローチを提案します.
我々のアプローチは完全(complete)であり、決定的(decidable)です. しかしそれでいて既存の似たようなアプローチよりも自由度があります.

コメント: この論文は全部をある程度読んでみました. GADTs に対する型推論は非常に困難な問題であることが知られていたが、ちょっとアノテーションを加えれば GADTs に対しても完全な型推論が可能になるというものらしい.

Control-Flow Analysis of Function Calls and Returns by Abstract Interpretation

単純な高階関数型言語のためのコントロールフロー解析(control-flow analysis)を導き出します.
既存の直接的なスタイルの解析とは逆に、我々の解析はファーストクラス(first-class)としての関数と末尾呼び出し最適化(tail-call optiomization)が存在する環境での関数呼び出しとリターンのインタープロシージャルコントロールフローを近似します.
抽象環境(abstract environment)に加えて、我々の解析は各エクスプレッションに対して抽象コントロールスタック(abstract control stack)を計算し、関数がリターンを呼び出す場所を効率的に近似します.
解析は一連のガロア接続(Galois connections)を用いて、Flanagan らのスタックベースの CaEK 抽象マシンの抽象解釈(abstract interpretation)を行うことによりシステマチックに計算されます.
抽象解釈は統一的な状況を与えます. これについて我々は 1) CPS 変換の結合とそれに続くスタックなし CPS マシンの抽象解釈と同等の解析を証明します. 2) 同等の制約ベースの形式化を取り出し、抽象解釈の原理から制約ベースの CFA の合理的な再構築を与えます.

コメント: 抽象解釈を用いて関数型言語のインタープロシージャル解析をする手法らしい. インタープロシージャル最適化に使えるか? そうであるとグラフィックス言語にも応用があるのでより詳しく読みたいところ.

… あとのこり 22 papers ほどです.
んー、そろそろ誰か他に興味があるひとにも手伝ってもらいたくなってきた気がするが、そもそも ICFP papers を輪講したい!というコンパイラ野郎, 関数型言語野郎がどれだけ日本にいるのかなぁ…

[Paper, ICFP09] ICFP09 papers: review4

[Paper, ICFP09] ICFP09 papers: review3
の続きです.

Biorthogonality, Step-Indexing and Compiler Correctness

再帰のある単純型付き関数言語(simply typed functional language)と、SECD マシン の派生としての低レベルプログラムの操作挙動(operational behavior)との論理的な関連を定義します.
双直交性(biorthogonality)と step-indexing を用いて定義される「関連」は、数学的で領域理論的(domain-theoretic)な関数を実装するための低レベルコードの一部とは何を意味するのかを捉え、また単純なコンパイラの正しさを証明するために使われます. 成果は Coq 証明支援により形式化されています.

コメント: んー、抽象的でよくわかりませんが、コンパイラの検証にも使える手法なのかな.

Causal Commutative Arrows and Their Optimization

アロー(Arrow)は抽象計算(abstract computation)の一般的な形式です.
モナド(monad)よりも汎用的で、より広く応用が効き、特に抽象信号処理やデータフロー計算をうまく抽象化します.
最も特筆すべきものとして、アローは Yampa とよばれるドメイン固有言語の基礎を構成しています. Yampa はいろいろな具体的なアプリケーション、アニメーション、ロボティクス、サウンド合成、制御システム、グラフィカルユーザインターフェイスに使われています.

我々の主要な興味は、Yampa により表現される抽象計算のクラスのをよりよく理解することです.
しかしながら、アローはこれを精度よく行うには十分に具体的ではありません.
この状況を改善するために、平行計算(concurrent computations)の非干渉な性質の一種を表現する、可換アロー(commutative arrows)という概念を導入します.
また、 init 操作を追加し、そしてアロー効果のカジュアルな性質を表現するきわめて重要な法則を確認します.
我々は本提案により導出される計算モデルをカジュアル可換アロー(casual commutative arrows)と呼ぶことにします.

この計算のクラスをより詳しく調べるために、我々はカジュアル可換アロー(casual commutative arrows, CCA)と呼ばれる単純型付きラムダ計算の拡張を定義し、その性質を調べます.
我々の主要な寄与は、カジュアル可換標準形(casual commutative normal form, CCNF)とよばれる CCA の標準形の検証です.
terminating normalization procedure を定義することにより、アローの既存の実装に対してパフォーマンスの劇的な改善となる最適化戦略を発案しました.
このテクニックは Haskell で実装してあり、我々のアプローチの効果を検証するベンチマークを実施しました.
ストリーム融合(stream fusion)と組み合わせたとき、全体的な手法は 100 倍以上のスピードアップを実現します.

コメント: 信号処理をうまく(関数型言語で)抽象化するそうなので、シェーディング言語とかに使えそう. しかもそれを高速に処理できるらしい. まずはアロー、 Yampa を調べることからですね.

… のこり 24 papers ほどです.

Shotgun: web-based collaboration tool

http://www.shotgunsoftware.com/

某プロダクションの方から教えていただきました.

web ベースのプロダクション向けプロジェクトマネージメントツールらしい.
見た目がいいですね 🙂
ただ、できることは基本的に(プロダクション向けの)進捗管理なので、アセット管理やレンダーキューのマネジメントなどはできないとのこと.

ちょうど別件で、プロダクション用途ではない通常のプロジェクト管理にも使えるツールを探していたりするのですが、
見た目もいいこともあり、Shotgun を普通のプロジェクト管理という用途にも流用できるならちょっと使ってみたいなーと考えています.
ただこのツール、幾らかかるのかなぁ…なんだか高そう… 🙂

Particle renderer shuld be separeted or integrated to lucille?

 lucille は基本的にポリゴンや形状などのデータを受け取りレンダリング処理をするというタイプのレンダラです.
多くの商用レンダラに見られるようなタイプのレンダラです.

一方で、パーティクル系(水、煙、炎、ボリュームなど)専用のレンダラというものも存在します.
こちらはあまり商用では見られません(RealFlow RT くらい?)

そして lucille 教の布教活動をしていると、
「うーん、パーティクルレンダラも興味あるんスよ. そこんとこどうっすか?」
という要望を多く聞きます 🙂

パーティクル系レンダラは通常のレンダラとはかなり異なっています.

– まず、内部データ構造が違う
– データ量が膨大でファイルに一旦落としてレンダリングするなどが難しい
– 効率的なレンダリングをしたいときに使うレンダリングアルゴリズムが異なる
– シミュレーションという処理とも絡んできて、制作パイプラインとの統合方法が違ってくる

そのような関係で、パーティクルレンダラは通常別のレンダラソフトウェアとして実装されています.
また、あまり外販はされておらず、
多くのパーティクル系レンダラは各スタジオでインハウスツールとして製作されています.
これは、各スタジオの要求ごとにカスタマイズされていたり、
プロジェクトごとに毎回カスタマイズされたものを作るため、
一般的なソフトウェアとして販売するのが難しかったり、仮に売ったとしても十分な数にならないから、
というのが原因であるためと言えます.

とはいえ、やはり要望としてパーティクルレンダラを望む声を多く聞くので、
lucille とのレンダラシナジーを向上させるため、
何かしらの方法でいずれパーティクルレンダラも取り込みたいなぁと考えています.

このとき、別々のお互い独立したレンダラという方向で、
外部パーティクルレンダラとのアライアンスを組むか.
たとえば RealFlow RT をサポートするなど.

または統合レンダラという方向で、
lucille でもパーティクルのサポートを頑張って追加してみるか、
他パーティクルレンダラを M&A するなどして統合レンダラとしてパーティクルをサポートするか.

なんだか会社経営や、会社のビジョンをどうするかに似ていますね 🙂
前者はコア事業が明確なベンチャー企業、
後者は総花的な企業、たとえば日本最大のコングロリマット企業であるサイガグループやフランスの Vivendi(水道屋さんがいつのまにかゲーム屋にも!)みたいなものと言えます.

ri, mi and li

ちょっと面白いことに気づきました.

ri -> 某レンダラ(のフォーマット)のことですね.

mi -> 某レンダラ(のフォーマット)のことですね.

そうきたら、やっぱ某レンダラは 「 li 」(エル、アイ) ですよね〜.
というわけで li で行くことにします.
いやー、謀らずとも、既存の某レンダラ群とネーミングが被らなくてよかった…

というわけで、「魏」 「呉」 「蜀」ならぬ、「ri」 「mi」 「li」 のレンダラ三国志が実現!
「li」は、後発かつ最後には天下を取るということで、さしずめ「呉」でしょうか 😉

… ウィング関先生にみられるように、三国志ブームにちょっと乗っかってみました.

My MOTEKI has come as an compiler writer?

[En]

Recently I’ve been asked about business opportunity on compiler construction for graphics language(there are few well-known graphics language, you know, hehe) using LLVM from some people/company(in worldwide).

I’ve convinced that there are really few people on the earth who really knows graphics(e.g. raytracing, opengl/shader, global illumination) and compiler construction/optimization.

On the other hand, recent graphics demand needs a compiler for application-dependent higher performance computation(e.g. through JIT) and supporting industrial standards(e.g. GLSL or OpenCL).

I think this gap is the reason why people ask me the compiler construction for graphics language. Many people in the industry seeks good compiler writers, but no one seems respond their demand.

[Ja]

最近、同時多発的にグラフィックス言語(世の中によく知られているグラフィックス言語はまあ 5 個ぐらいじゃないっすかね. そのうちのいくつかです)のコンパイラ作成(とくに LLVM を使ったりして)に関する案件の問い合わせを国内外問わずいただいています. RSL コンパイラを LLVM と Haskell 使って作っているからでしょうか 🙂

「すわ、オレにコンパイラ野郎としてのモテキが訪れたというのかっ!人生にモテキはたった 2 回しかこないらしい. これはその 2 回のうちの一回なのかッ! このチャンスは何としてもモノにするべきか!?」

…なんちて.

とはいえ、グラフィックスと(最適化)コンパイラ作成の両方のスキルを持つ人財というのは、
世界中をみてもかなり少ないのではないかと思います. オフラインレンダラ野郎よりも希少かもしれません 🙂

もしグラフィックス言語(オフラインから、オンライングラフィックスまで)のコンパイラ作成で
お悩みの方が他にいましたらお知らせください.
可能な限り対応させていただきたいと思います.

私が割ける時間は有限ですので、私だけではどれくらい対応できるかはわかりませんが、
しかし希少動物同士は集まり合うという特性(?)がありますので、
その特性で知り合った他のコンパイラ野郎を紹介するということもできます.

ちなみに私のスタンスとしては、レンダラ野郎の巨塔を登り詰めトップレンダリストになるには
コンパイラ野郎でもなければならないと思っているのでコンパイラ関係をやっているだけで
(レンダラ野郎は大域照明言語を設計し、その最適化コンパイラを作れなければならない!)、
コンパイラ野郎の道も極めようとしているわけではありません 😉

[Paper, ICFP09] ICFP09 papers: review3

[Paper, ICFP09] ICFP09 papers: review2 の続きです.

Automatically RESTful Web Applications Or, Marking Modular Serializable Continuations

RESTful ってのは、web の世界で REST っていうアーキティクチャが使われているものを指す言葉のようです.

継続(continuation)ベースの web サーバは既存の web アプリケーション開発に対して差異のあるアドバンテージ、これはつまり強力な表現力、を提供します.
このパワーにより、少ないエラー、よりさまざまな応用を実現することができます.
さらに、これらの web サーバはプロトタイプではなく、いくつかの実際の商用アプリで使われています.
しかし残念なことに、スケーラビリティに欠けており、この更なるパワーを得るには高い代償を払わなければなりません.

我々はこの重要な問題を、スケーラブルな継続ベース web プログラムを生成するようなモジュラーなプログラム変換により解決します. 我々のプログラムはスケーラブルでない継続ベース web プログラムと同じ機能を利用することができるので、パフォーマンスのために強力な表現力を犠牲にすることはありません. 我々のシステムは既存のアプローチに必要なメモリ使用量の 10%(かそれより少量)しか使いません.

継続ベースによる web プログラムは、表現力がある代わりにスケーラビリティが無かった.
そこでスケーラブルにできる方法を見つけたよ、メモリも 1/10 に減らたよ、
という感じの論文らしい.

Beautiful differentiation

うぉおおおおおおおおおおお!!!!
Conal Elliot ではないか!!!
グラフィックスと関数型言語を融合させた初めての(?)男!!!

かつては氏はシェーダ言語を関数型で書いてみたぜー、なんてことをやっていました.
氏から私は関数型とグラフィックスの連携についての多くを学びました.

さて、beautiful differentiation, もともとはすでにどこかで発表していた気がします.
氏の blog でも取り上げられていますしね.

関数型で自動微分をする論文です.

自動微分(Automatic differentiation, AD)は正確で、効率的で、そして便利な関数の微分を計算する方法です.
前方向モード(forward-mode)での実装は、高階微分(higher-order derivatives)を計算するように拡張する場合でも、非常にシンプルに書く事が出来ます.高次元の場合も、ちょっと複雑な要因がありますけど思慮してみました.
多様体上の、究極的に一般的で優雅な条件での計算における、高次元、高階、前方向モードの AD 実装の実装について解説し、シンプルで正確な仕様からの実装を導出します.

実装の動機と発見のために、本論文では次の問題を提示します「実装は別にして、AD とは何を意味するのか?」
ひとつの答えは、関数のサンプリングとその導関数の本質について、という形で現れます.
自動微分は連鎖律を用いることで、この本質的な条件から逃れます.
一階から高階の AD に変化していくことは、一つ(の導関数)ではなくすべての導関数をサンプリングすることに対応します
次に、設定を任意のベクトル空間に拡張します. ここでは微分値は線形写像になります. AD の仕様はこの優雅で非常に一般的な設定に適応し、これはさらに(実装の)開発を簡略化します.

… のこり 26 papers ほどです.

[Paper, ICFP09] ICFP09 papers: review 2

[Paper, ICFP09] ICFP09 papers: review1 の続きです.

A Universe of Binding and Computation

束縛(binding)と計算(computation)をミックスしたデータ型をサポートする論理フレームワークを作り上げます.
依存的に型付けされたプログラミング言語 Agda 2 の世界(universe)でこれを実装します.
well-scoped な de Brujin incides を用いて、束縛を代名詞的(pronominally)に表現します.つまり型は変数のスコーピングに関する理由(reason)として使うことができます.

weakening, substitution, exchange, contraction and subordination-based strengthening のデータ型ジェネリックな実装が我々の世界では用意されます.
したがってプログラマは彼らが定義する言語において、自由にこれらの操作を使うことができます.
我々のミックスされて代名詞的な設定のもとでは、weakning と substituion は型のいくつかの条件の元でのみ有効であり、しかしこれらの制約条件は多くの場合自動で解放させることもできることを示します.

最後に、この研究の分野から、いろいろなよくある困難なテストケース、たとえば型無しラムダ計算の評価による正規化(normalization-by-evaluation)などをプログラムし、クリーンかつ簡潔なコードを保ちつつも、プログラムの型の中で変数の利用についての詳細な不変性を表現できることを示します.

(コメント) まだいったいどんなことができる論文なのか私の知識では分かりません.

Attribute Grammars Fly First-Class: How to do aspect oriented programming in Haskell

アトリビュート文法(attribute grammar)プログラムは二つの軸に分解することができます. 関数軸(function axis)とデータ軸(data axis)です.その結果、これらは用意に適応させたり拡張させたりすることができます.

問題は、プログラミングに対してのアトリビュート文法のアプローチが組み込みドメイン固有言語(embedded domain specific language, EDSL)として Hasnell に実装することができるかどうかです .

本論文では、これらが型クラスの機構を広く利用することで達成することができることを示します.
本論文は、アトリビュート文法の固有の性質を見つけ出し、それらをエミュレートする方法を示し、いままでの試みが持っていたいくつかの問題を克服する方法を示します.

最後に、どのようにアトリビュート文法プログラミングにおいて見つかる共通のパターンが明示的に得られ、それが我々の EDSL の主要な拡張となっているかを示します.

(コメント) んー? aspect 指向プログラミングを Haskell で実現する手法っぽい.

… 残り 28 papers くらいです.

[Corpoate low] Chief XYZ Officer

社長、会長、相談役、専務、常務、etc…

じつはこの肩書き、会社法では設定されておらず、任意に決められるって知ってました?
会社法で制定されているのは、(代表)取締役や監査役という役職になります.

なので、「代表取締役ニート」、「代表取締役トップレンダリスト」というのもできちゃったりします.
(その会社が認めればですけどね)

海外では、Chief Executive Officer(CEO, 最高経営責任者), Chief Technology Officer(CTO, 最高技術責任者) とかいう役職をよく見かけますね.

そんなわけで、いくつか考えてみました.

Chief Rendering Officer: 最高レンダリング責任者
Lead Renderist: トップレンダリスト
Chief Creative Officer: 造物主.
Chief Laughing Officer: フ○○○ーヌ様を笑わせることが我らの役目!!!
Chief Standing Officer: 最高○ョ○ョ立ち責任者、またの名を鬼教官!! WRYYYYYYYY!!

んー、以外とアリかもしれない.