契約更新しました
まだ契約書が届いていなくて押印していないのですが…！まあいいでしょう。
一昨日の 30 日付けで、4 月からの契約が無事（？）終わりました。9 月からどうなるのかなあと思ってたら、当たり前のように契約更新することになりました。ありがたい話なのですが、毎月赤字で働いていて貯金ももうなく、すぐに答えられる状況でなかったので、もっと早くせっつけばよかったなあと思いました。いや、せっついた記憶はあって…まあいいか。次の契約は、今年いっぱいらしいです。
病気のほうは相変わらずで、いつになったら治るのやらという状態です。それがわからないから困っているわけですが…とはいえ、貯金も底をつきかけているので、働く時間を増やさざるを得ないという大変厳しい状況で…増やすといったところで、思うように働けるかどうかは、日々の体調次第なので、なんともかんとも。
まあ兎に角、今年いっぱいは頑張ってみようと思います。それでダメなら本格的に色々考えないといけないですね。人生の難易度設定、難しすぎないないですかね…
そんなわけでお金がないです。何か買ってもらえると大変助かります。サポーターとかサポーターとかサポーターとか。トラックボールはスクロールがほとんどまともに動作しなくなってて大変不便なので自分で買いそう…ところで欲しいものリストは、身の回りの世話をしてくれる人とかを登録できないのがイマイチだなあと前から思っているのですが、いつになったら改善されるのでしょうか。
2012年に読んだ面白論文を紹介する会
例のアレです。今年は五月頃にソニーリーダーを失くしてしまう、しかも突っ込んでいた論文のバックアップを取っていなかったという悲劇のおかげで、ちょっとアレがアレしてるんですけど…バックアップは大事ですね！
Sound Predictive Race Detection in Polynomial Time
race なんて大嫌いだーってなってる頃に読んだ論文です。今も変わらず嫌いですけど…とりあえず id:shinichiro_h さんがもう書いているのでアウトソーシング。
…だけだとあまりにも酷いので、えーっと何が面白いかというか嬉しいかというと。兎に角 race というのは、race のないコードを書くのも一定大変なんですが、あるコードに race がないことを保障することができない、というのが何より辛いわけです。いくら race detector を利用して race が見つけられたとしても、false-negative が含まれている可能性があると悲しくって、矢張り本当に欲しいのは sound な race detector なわけです。この論文における実験では、実行効率のために導入する制限で若干 soundness が損なわれているのですが、それでも sound な race detector の提案というのは、素晴らしいなあ…という。
この論文は、practical な感じのものではなくって、今後 sound な race detector の研究をする人たちの足がかりになりたい、というような感じになっていて、じゃあその後はどうなってるのかなあと思って調べてみたのですが、特にこの一年で発展は無いようです。残念。
しかし primary author の人が "Residual Investigation: Predictive and Precise Bug Detection" とかいう、これまた面白げな論文を出されてるようなので、そのうち読みたいですね…
最後に、これは私感ですが、本当に race がないことを保障したいのなら、race detector で頑張るとかよりは、session type とかになるのかなあと思います。ただ、この論文を読み始めた頃のボクのモチベーションは「いかにして race のないコードを書くか」だったので…ちなみに論文を読んでも「いかにして race のないコードを書くか」については大して学べなかったので悲しかったです。
Data types a la carte
お前去年これ参照してる論文読んでただろ、という突っ込みは勘弁して頂きたい…何はともあれ kinaba さんが書いているのでアウトソーシング。とはいえこっちは紹介と言う感じでもないので、一応真面目に紹介。
所謂 Expression Problem （以下 EP）を解決しましょうという良くある論文なのですが、これの面白いのは、実は新しい手法とかは全く提案していなくて、既に提案されている手法を組み合わせるだけで EP を解決してしまっている、というところです。面白いというか、すごくよくまとまっているというか。
ADT が F-algebra の initial algebra として捉えられることも、型クラスで型の直和を表現し、"subtype" の関係の成り立つ型に injection や projection を提供する型クラスを使う手法も、ずっと昔から知られています。Free モナドもあまり調べていませんが Category theory 界隈では良く知られていたものだったようなので、多分全部 20 世紀のうちには発見されてるんじゃないでしょうか…それが 2008 年に LtU なんかで紹介されて一定盛り上がったのだから、面白い話ですね。この論文はまさに伝記系ラノベと呼べるのではないでしょうか。
ちなみに去年読んでたというのは "The Monad Zipper" ですね。先にこっち読んでいれば、どれだけ理解が楽だっただろうか…
A pattern for almost compositional functions
世の中には「ほとんど合成可能な関数」というものが存在します。定義を説明するのは面倒なので具体例を挙げると、例えば AST に対するα変換的な namer とか、インクリメントを代入式に置き換かえるような desugar とか。そういうのです。
これらの処理は、普通に実装すると AST に対する再帰関数になります。しかし、こういう再帰関数があまりたくさんできてしまうのは嬉しくないです。というのも、値コンストラクタが増えた際に全て書き換えないといけなくなるし、そうでなくとも本質的な処理に集中したいのに AST を舐めるための再起処理ばかり書かされるはめになりがち、特に practical なコードの AST なんかは値コンストラクタたくさんもっていることが多いので、本質的な処理を見失いがち。そんなわけで、本質的な処理のみを切り離して記述できるように、AST を舐める処理はまとめてしまいましょう、という話。
というと、これって "The Essence of the Iterator Pattern" （以下 EIP） の Traversable なんじゃない？と思う人もいると思います。ボクも最初は思いました。ところが少し違っていて、
class Functor t => Traversable t where traverse :: Applicative m => (a -> m b) -> t a -> m (t b) class Functor t => Compos t where compos :: Applicative m => (t a -> m (t b)) -> t a -> m (t b)
みたいになっています（実際に論文に出てくる型クラスによる定義は GADTs のために rank2-polymorphism を使った定義になっています）。
Traversable は勝手にデータ構造を走査してくれます。逆にいうと、データ構造の走査をコントロールすることはできません。一方 Compos ではそれが可能になっています。逆にいうと、コントロールしてやる必要があります。それだけといえばそれだけなんですが、それぞれを catamorphism 的に使う場合、これは結構面白い物と対応していて…というのはちょっと今回は秘密です。2012 年に読んだ論文の話じゃないから…（本当は次の comfrk のネタにするかもしれないからだからなんて、言えないね！）
論文には他にも、相互再帰的な複数の型から成るデータ構造を扱う話や、GoF の Visitor で Compos を実現する話や、SYB を利用する話等色々あるのですが…兎に角、EIP の Traversable と違い、データ構造に対する走査をコントロールすることができる、しなければならないというのが EIP の Traversable を知っている人には面白いポイントなのではないかなと思います。知らない人には、こういう風に書けば AST みたいなのうまく扱えるんだへー、ぐらいの話だと思います。
実はこの論文は "A Pattern for Almost Homomorphic Functions" という、よりとんがった論文を読むために読んでいたのですが、そっちは内容が Haskell 的な意味で重すぎ（closed type families とか出てきます）なので、あまりおすすめしません。とりあえず hackage へのリンクだけおいて置きます。0.9 から 2.0 にバージョンあがってるのが謎、Typeable 周りで 1.0 どっかいったのかな。これ、モチベーションは面白いんですけどねえ…
Extensibility for the Masses Practical Extensibility with Object Algebras
大変面白い論文なのですが、ちょっと面白い部分の説明が難しいです。実際のコード例が簡単な分、余計に…
これも "Data types a la carte" 同様、所謂 EP を解決しましょうというよくあるお話なのですが、それを Java や C# のような、それほど強力な型システムを持たない、シンプルな generics しか備えていない言語で解決してしまいましょう、というものです。そのために Object Algebras というものを提案しています。これは、極論すると GoF の Visitor パターンと Abstract Factory パターンと Builder パターンを組み合わせてより上手く構成したものです…といってもなんのことか分かりませんよね。
おさらい。オブジェクト指向プログラミングでは、オブジェクトの階層としてデータ構造を表現します。このデータ構造に対し、ADT でいうところの値コンストラクタ相当を新たに追加することは簡単です。単純に継承を利用するだけで、既存のコードの変更もなく追加することができます。一方で、データ構造に対する操作を追加する際には、愚直にやると既存のクラスに片っ端から新たにメソッドを実装していくことになってしまうため、かなり大変です。
Visitor パターンは、この問題を解決するために、オブジェクトの階層として表現されたデータ構造に対する decomposition を、元のデータ構造を表現するクラスとは分離した形で実現するものとして GoF で定められたデザインパターンです。このパターンの弱点は、decomposition の実現に必要なダブルディスパッチのために元のデータ構造を表現するクラスに "accept" メソッドを用意しておく必要がある点です。つまり、完全には元のデータ構造を表現するクラスと分離できてはいないわけです。
Object Algebras は、データ構造の表現自体を抽象化してしまおう、という手法です。
interface IntAlg<A> { A lit(int x); A add(A e1, A e2); }
これは "Lightweight Modular Staging" の値表現の抽象化にかなり近い手法ですね（多分…）。"Lightweight Modular Staging" も紹介したかったのですが、一度名前だけ出してるしまあいいかみたいな…それはよくて。
値を生成するコードは、このインターフェースを利用するようにします。これにより、具象的な値表現に依存することはなくなります。
<A> A make3Plus5(IntAlg<A> f) {
return f.add(f.lit(3) + f.lit(5));
}
あとは、IntAlg を実装するだけです。例えば式を表すクラス群 Exp, Lit, Add が既にあるとして、
class IntFactory implements IntAlg<Exp> { public Exp lit(int x) { return new Lit(x); } public Exp add(Exp e1, Exp e2) { return new Add(e1, e2); } }
こんな具合に実装します。これを先ほど定義したメソッドに放り込んでやると、
Exp e = make3Plus5(new IntFactory());
ちゃんと式が得られる、と。それだけです。本当にそれだけです。おしまいです。
論文の内容紹介としては、後はこの IntAlg が既存のコードの変更無しに拡張可能になっていること、つまり値コンストラクタを後から追加できることや、IntFactory のようなその実装も同様に拡張可能になっている、つまり値コンストラクタが後から追加されても、その部分だけ実装しなおせばよい、よってコードの重複等は発生しないこと…つまり EP が解決できていることが具体的なコード例でもって延々と説明されます。応用例なんかも出ます。特に難しいものではないので、是非読んでみて下さい。
兎に角重要かつ面白い部分は、データ型のエンコーディングの抽象化と、その基礎の部分です。なのですが、この部分がいかに面白いかを説明できるほどの能力がボクに備わっていなかったのでここでおしまいです。残念。
Scala Conference in Japan 2013 に参加しました
あと発表しました。インシデントがあった気もしますが、運営スタッフの機転により重大ななんかは生じなかったですね？何もありませんでしたね？
皆々様、本当に大変見苦しい発表になってしまい、申し訳ありませんでした…
あまりに見苦しかったために、今日の Hack-a-thon の後の懇親会で「rpscala でまた話しませんか」と話を振られたりしたので、多分やります。全く同じだとつまらないと思うので、その時にはおまけをつけたいと思います。多分次の第 99 回かなあ。
そんなわけでスライドを公開しました。公式サイトで後日公開ということだったので、すぐにアップロードするのは控えていたのですが、どうも問題ないらしいので slideshare にあげてしまいました。当初は完全に発表向けのスライドを作るつもりだったのですが、色々あって、後でスライド単体でみてもある程度の資料価値はでるくらいの分量になってる…といいなあ。
発表内容について。
表題通りの内容でございます。「Scala 初心者でない人の中には、Scala の関数型プログラミングの方にばかり目を向けて、オブジェクト指向プログラミングのための言語機能についてきちんと理解できてない人って、多分いますよね」みたいなのを最初にぶちかまそうと思っていたのですが、時間もおしていたのでやめておきました。あと Odersky already did it とかのジョークも通じないかなあ…と思ってスライドにいれるのはやめておきました。"Scala has the features that Java lacks!" とかの部分が最初はそんな感じでした。
兎に角疲れましたが（実際体力限界で横になったりしてましたが…）楽しかったです。@jroper さんの発表が実際スゴイでした。あと Conference の懇親会で、海外勢の英語が聞き取れはしても全く喋れなくって、英語難しいなあ…と思いました。ボクが聞き取れたのも、気を使って分かりやすい英語で喋ってもらってたおかげだと思っているのですが。折角来日して貰えたのにあんまり話せないと悲しいですね。普段あまり会ったり話したりする機会のない日本の方とはぼちぼち交流できたような気がしますが、交流しすぎて顔とか名前とか大体忘れたので、言語問わずコミュニケーションは難しいのだなあと思います。ボクが頭が悪いだけかもしれませんね…
あとここで発表すると告知していたのでどうでもいいのですが、発表者と lyrical_logical という id は紐付かないように自己紹介とかスライドとか作っていたのに、ツイッターの実況で色々台無しになってて悲しかったです。美少女なら嬉しかったのですが。
発表は録画されていたらしく、おかげで死にたいという気持ちに対する理解が一段と深まりました。ありがとうございました。
もし次があるなら、その頃には体を治して、スタッフとして貢献できるといいなあ…と思いました。もしくは LT したい。あと銅鑼鳴らしてみたい。
おしまい。
null さんとのお付き合い
ちょっと暇つぶしに書きます。ついらーで null で盛り上がったので。
Read morescala 関係近況
色々溜まったのでまとめて書きます。
Scala Conference in Japan 2013 でスピーカーとして発表させていただくことになりました。内容は、どうせ他の人は functional functional うるさい感じになるだろうと思っていたのと、前々から書きたかったこともあって、オブジェクト指向言語としての Scala についてです。そんなに難しい話にする予定ではないですが、重要な話をする予定です。難しさと重要さは直交する概念です。まあそんななので、オレは OO Scala Ninja だぜ！っていう人には退屈な発表になるかもしれませんが、興味がありましたら是非…といっても、もうチケットが既にキャンセル待ちがこれを書いている時点で 50 人弱もいる…のですが、LT スピーカーになれば別枠でチケットが購入できるらしいので是非 LT しましょう！締め切り明日までですけどね！
97 回の Scala 勉強会 in 本郷 で発表してきました。前日少しだけ発表する気があったのですが、当日色々あったので今日はいいかなあ…と思ってたら圧力かけられてヤメロー！ヤメロー！ってなりながら、雑に作った資料で雑な発表をしました…スライドはこちら。内容は PartialFunction についてです。スライド単体で資料になるように書く余裕がなかったので、Ust の録画を見ながら…と思ったら Ust の録画音が出ないという残念なことになってました。残念。気合で分かってください！！！
あと日本 Playframework ユーザー会になんかメール投げたりしてました。Play 2 の Java API 利用している人には有用な情報かもしれないので、導線だけはっておきます。
ドキュメントが古いの直ってないようなので、誰かつついたほうがいいかな…見てる人で誰か適当な人つつくなりしてください、ボクはしんどいです。
菱形継承問題の再考と整理
菱形継承問題というと、多重継承が槍玉にあげられる際の筆頭ですが、なんとなく wikipedia を見てみたら酷いことになってたので、ちょっとなんか書きます。
言語 independent な記述にするために微妙な単語のチョイスがあったりするかもしれませんがフィーリングでなんとかしてください。言語 dependent な部分は多分横文字じゃない感じになると思います。
まず、所謂菱形継承問題が生じる条件を整理します。
これによって生じる問題は三つあります。一つずつ見ていきましょう。
- B, C の利用する A のインスタンスの扱いに困る
B と C は A のサブクラスなので A の状態やら何やら、つまり値表現*1を持っているわけですが、D は B と C のそれぞれのために A の値表現を二つ持たないといけないのか、それとも一つにして B と C には同じ値表現を使ってもらえばいいのか、という問題があります。
C++ は普通に継承してると前者に、仮想継承というニッチな言語機能を利用すると後者になります。やあ、よくよく考えられた言語ですね C++ は…
一方他の言語は大体後者しか選べない気がします。いや前者しか選べない言語もあるよ、両方選べる言語他にもあるよ、とかあったら教えてください。言語毎の事情調べるのサボってかいてます。
兎に角、値表現を共有するか否かという問題があるわけです。
- メソッド呼び出し時の解決が曖昧になる
ようは D のメソッドを読んだときに B と C に同じシグネチャのメソッドがあるので解決する時に困るね、という話です。二番目に持ってきましたが、多分これが一般的な菱形継承問題の認識なんじゃないかなあと思います。
これは、指定する方法があるなら指定するなり、呼び出したい方のクラスにアップキャストするなりで回避できます。
しかしこの問題は、実のところ菱形継承特有のものではありません。兎に角、同じシグネチャのメソッドを持つ複数のスーパークラスがあればいいのだから、多重継承に因る問題です。
- メソッド定義時の解決が曖昧になる
曖昧になるのは呼び出し側だけではありません。当然、メソッドを定義する側でも起こり得ます。
例えば、同じシグネチャのメソッドを持つクラスを複数スーパークラスとして持つクラス内で、スーパークラス毎のメソッドはどのように扱われるでしょうか？
C++ では区別されません、というよりはできません（確か…）。そのため、スーパークラス毎にメソッドをオーバーライドする、というようなことはできません。vtbl は普通クラス毎に存在するはずなので、不思議な話ですね。仕様ではその辺の実装まで踏み込んでないからかな。まあオーバーライドは別個に別のクラスで行ってそのクラスを継承する形に書き換えれば解決できます。
さて、この三つの問題は、全てが菱形継承ないし多重継承固有の問題なのでしょうか？実はそうでもありません。
まずメソッド定義時の解決について。Java の interface では、同じシグネチャを持つメソッドは、異なる interface で宣言されていたとしても、区別できません（確か…）。C++ と同じですね（未確認なのも含めて…）。
一方で、C# の場合は区別できます、というか区別しないといけないんだったかな…同じシグネチャのメソッドでも、別の interface で宣言ないし定義されているのならば、それは別物であるということです。
しかし、これが区別できてしまうと、前述のメソッド呼び出し時の解決の曖昧性の問題が生じます。Java の場合は、そもそも定義側で区別ができない、同じものとして扱われているのだから、呼び出し側で区別をする必要がそもそも生じません。ところが C# の場合は区別できてしまう、区別しなければならないわけです。解決方法は矢張りアップキャストです。
あまりまとまりませんでしたが、菱形継承問題について今更なんか書きました。場合によっては、問題の一部は多重継承のない言語でも発生するんですよ、というおまけつき。C++, Java, C# 以外の言語は reference なしにちょっと語る自身がなかったので触れていません。仕様とかちゃんと確認してないので、嘘があったら教えて貰えると嬉しいです。他の言語での事情は、詳しい人がいたら教えてください。Python の C3 linearization とかその辺…まあ Scala の linearization と大体同じかなーと勝手に思ってるんですが。
ここにメッセージベースの OO とかプロトタイプベースの OO とか入ってくると多分わけが分からなくなるので、それはもう勘弁してください。うう、こんなもの書いてる場合じゃないし書くんじゃなかった…疲れた…
おしまい。
*1:この言葉は今作ったので読み終わったら忘れてよい
