今年読んだ面白CS論文紹介カレンダー 9 日目みたいなもの
今年読んだ面白CS論文紹介カレンダー 9 日目？ですか？カレンダーとはなんぞやという感じですが、いつ書いてもいいっていわれたので今書きます。
皆さんが大変真面目な紹介をしているところ非常に心苦しいのですが、ボクにはとても面白げに紹介なんてするできる気がしないので、ここはもう開き直って、最早紹介という体さえなさずに、ボクのためのメモを書きます！
Tail call elimination on the Java Virtual Machine
infoQ のインタビューより。
The first usual suspect is always tail recursion.
JVM 上で末尾再帰の最適化はなかなか難しいですねという話です。
末尾再帰の最適化手法というのがいくつかあるのですが、どれも JVM 上ではうまくいきません。
- プログラムを一つの巨大な関数と巨大な switch に変換する
JVM のメソッドの大きさに制限があるから無理。
- トランポリンを使う。
遅すぎる。
Continuation ない。
ちなみにじゃあどうしよう、という部分で「実行時に必要そうになったらトランポリンにする」という、そうですか…みたいな話なんですが、そこはまあ別に面白くもなんともなくて、昔は末尾呼び出しの最適化する VM あったんだなあとか、そういう部分が面白かったです。
あれ、これ本当に面白かったのか…？
Invertible Syntax Description: Unifying Parsing and Pretty Printing
去年の頭に流行った Invertible Syntax です。今更ですが読みました。真面目に説明するのめんどくさいので面白いところまで飛ばします。
"The need for invertible function can also be understood from a categorical point of view." ヤメローーッ！
人間劇場ツイッターに悲痛な叫び声が響き渡るところから物語りは始まります。
（略）ということで、パーザとプリンタはそれぞれ関数とその逆関数だったわけです。
…プログラムとその抽象構文木を例に考えると、プリンタはただの単射だし（プログラムに変換不能な抽象構文木は多分ないですよね？それがプログラムとして valid かどうかは兎も角）、パーザは全射でも単射でもない（パーズできないものがあるので全射でないし、空白とか入れ放題だから単射でもない）から、逆関数「っぽいもの」だとボクは思うんですが論文では "invertible function" とか言われてて…はてー＜(｡εﾟ)＞
めんどくさいので以下では逆関数と呼びます。
パーザが小さいパーザとしての関数を組み合わせて大きいパーザを作るように、プリンタが小さいプリンタとしての関数を組み合わせて大きいプリンタを作るように、パーザとプリンタも「小さい関数と逆関数の対」を組み合わせて大きいパーザとプリンタを作れるようにすればいいじゃん！というのが提案された手法です。
パーザ、プリンタを組み合わせるというのは、関数を組み合わせるということで、関数を組み合わせるって何ぞや、ということになるわけですが、これはまあカテゴリカル・ポイント・オブ・ビューですよ。ヒョエー！
Haskell のモナドというのは通常 Hask の圏における自己関手の圏のモノイドになってるわけですけど（なにいってんだこいつみたいな顔しないでください）、Hask というのは射を関数で表そうみたいなものです。ただ、今は関数と逆関数の対をコネコネしたいので、そのための圏を作らないといけない。作りました。これを Iso と呼びましょう。
Iso がモナドだといいんですが、残念ながらモナドじゃない…困りました。
でもパーザは実はアプリカティブっていうのでなんか書けるらしいから、じゃあそれで！と思ったら Iso はアプリカティブにもできない…困りました。
アプリカティブっていうのは、ようは関数がまずあって、部分適用を繰り返したいみたいな気持ちがあって使うわけです。
f
f x
f x y
f x y z
こんなの。で、部分適用みたいなのは Iso の逆関数のほう（プリンタのほう）で定義できないので困ってるわけです。
しかしそもそも部分適用とかせずとも値のほうを積み重ねていけばいいのでは…？
x
(x, y)
(x, y, z)
f (x, y, z)
これだと最後の関数適用はファンクタですむので、じゃあ後は値を積み重ねるためのものがあればいける！これをプロダクトファンクタと呼ぼう！定義できた！勝った！
というお話だったのさ…ということなんですが、この論文半分くらい Iso の話してませんかね…？
で、あまり関係ないんですが、この ProductFunctor と scalaz の ApplicativeBuilder って同じじゃね？みたいなのがあります。どうでもいい。
The Monad Zipper
id:ranha さんが「モナドを『層』みたいに考えてるとモナドスレイヤーに惨たらしく殺されるって The Monad Zipper に書いてた」みたいなことを言っていたので、読みました。
expression problem というのがあります。型と関数がそれぞれ閉じてるせいで色々困るねっていう話です。
それを解決するために、型クラスで拡張可能な直和型を、open recursion で拡張可能な関数をつくって、やった解決したー。
ところがどっこい Haskell にはモナドがあった！こいつをどうにかしないといけない。
拡張可能な関数があります。拡張可能な関数は部分関数を捏ね上げて作ります。
各部分関数は、それぞれが自身の定義のためのモナドを要求したりしなかったりします。
関数を拡張しましょう。拡張したい時はこねる部分関数を増やしてやります。
まずは部分関数を新しく定義します。これも矢張りモナドを要求したりしなかったりします。
適当に既存の部分関数の中にぶち込んで捏ね上げれば拡張完了です。めでたしめでたし…
とはいかなくて、ここで新しい部分関数が要求しているモナドを、既存の部分関数も要求していたとしましょう。すると、既存の部分関数が期待していたものと違う、新しい部分関数のためのモナドが既存の部分関数に降ってきて、既存の部分関数が壊れます。
ダメじゃん！モジュラーじゃないじゃん！
…なんてことがあると困るから、なんとかしよう！。
モナドっていうのはモナドトランスフォーマーで積み上げられるものだよ。積み上げられたもの、モナドスタックにマスクをかけられるようにしたよ！これで見たくないモナドを無視できるようになったよ！スゴイ！完！
という話なんですが、これボクの理解では、いずれにせよ何か追加したら、マスクは変えないといけないはずなので、結局モジュラーじゃないような…ウーン分かりません。誰か教えてください！
モナドすきなひとはぜひよんでみてください（てきとう）
これ読んでから expression problem をどの言語でどう解決できるか、みたいなのに興味があって、色々調べたり調べなかったりしているのでまた何か書くかも知れません。
Purely Functional Lazy Non-deterministic Programming
今読んでます。既に面白いので読み終わったら書く。
カレーを食べにいかないといけなくなったのでこんなの書いてる場合じゃないのです！！！
