ヒビルテ(2009-12)

2009-12-02 [長年日記]

λ. PLDIr #4

PLDIの論文を読む PLDIr の第四回に参加。今回はPLDI2000の論文が対象で、私は以下の2本の論文を紹介した。

前者の論文は手続きがアクセスするポインタ・配列の範囲を解析するアルゴリズムの話で、競合の検出、自動並列化、範囲外アクセスの検出、範囲チェックの省略とかに使える。特徴は不動点計算を使わずに線形計画問題に還元して解くこと。

後者の論文はコンパイラの最適化の前後で意味が変わらないことを検証する話。等価性の定義として simulation relation というのを使っている。最適化器がevidenceとして simulation relation を出力すれば意味が変わらないことは容易に確認できるけど、最適化器が simulation relation を出力してくれなくても、多くの場合には simulation relation を推論できるとか。

発表資料 (PDF):

“Symbolic bounds analysis of pointers, array indices, and accessed memory regions”他の紹介＠PLDIr#4 from Masahiro Sakai

2009-12-11 [長年日記]

λ. 「最強の時間管理術」 by パク・ジョアン・スックチャ

文字通りの時間管理術を期待して聞きに行ったら、IMDの国際競争力ランキングとかワークライフバランスとかみたいな聞きあきた話がメインで、肝心の時間管理の話は手帳の使い方とかTODOリストとかの、これも良くある話だけだったので、ちょっとガッカリ。

あと、「定時退社で早く帰ってもやることがなくて困る人が多いはず」というような、大企業の仕事人間へのステレオタイプで話してたけど、聴衆にほとんどそういう反応をしている人がいなくて、ちょっと可笑しかった。定時退社で仕事が終わらなくて困るというのは分かるけど、やる事ややりたい事がなくて困るというのは正直想像がつかないな。

[ツッコミを入れる]

2009-12-13 [長年日記]

λ. HIMA #3 「副作用」

お題: 「副作用」
動機: 「Haskellには副作用がないので並列プログラミングに適する」という宣伝がある一方で，命令プログラマによってくりかえされる質問に「Haskellには副作用がないのにどうしてゲームが書けるのか」というのがあります．これに納得のいく説明というのを聞いたことがない気がしています．どのような説明なら，質問者も回答者も納得できるでしょうか．

私は、nobsunやkazuさん達が話しているのをほとんど眺めているだけだったのだけれど、「副作用」というものを自分がどう考えているか見直す良い機会になった(見直した結果は「関数型プログラマにとっての副作用」)。

2009-12-18 [長年日記]

λ. 関数型プログラマにとっての副作用

「Haskell に副作用なんて、あるわけないじゃん。大げさだなぁ」(死亡フラグ)と思っていたけれど、HAMA#3の話をみて自分の考え方を整理できた気がするので、ちょっと書いてみる。

入出力は副作用?

命令型プログラマに説明するときの便法としては、kazuさんの説明は確かに効率が良いとは思うものの、自分がこの説明をするのには結構抵抗がある。

どこに抵抗があるのかというと、その背後にある「入出力するなら副作用がある、Haskellは入出力する、だからHaskellには副作用がある。」というような考え方。この考え方では、言語がどのようなものであろうと、最終的に実行時に計算機上の現象として入出力が発生すれば、副作用が存在するということになってしまう。しかし、関数型プログラマにとって、副作用とはあくまでも言語や式の性質であって、実行時に計算機上で発生する現象のことではない。だから、実行時の現象のことを指して「副作用」と呼ぶのは category mistake だと感じてしまう。

要は「副作用」の定義の違いなのだけど、実行時の現象を指して副作用と呼ぶことの不合理はいくつかあるように思える。

第一に、この呼び方だとC言語の処理系を副作用のない言語で実装すれば、C言語には副作用が存在しないことになってしまうのではないか、という点。C言語に副作用が存在することは多くの人が認めるところだと思うので、これは矛盾であるように思える。(副作用のない言語なんて存在しないというなら別だけど)

第二に、以下のようなCプログラムは副作用を持つか? という問題。

int main(int argc, char** argv)
{
     return argc;
}

このプログラムは、外部からコマンドライン引数という入力を受け取って、そしてステータスコードを外部に出力しているので、明らかに入出力のあるプログラムである。したがって、入出力は副作用という考え方に従えば、副作用があることになる。しかし、実際には多くのプログラマは「このプログラムには副作用は含まれていない」と考えるはず。

関数型プログラマにとっての副作用とは?

では、関数型プログラマは何を副作用と呼んでいるのか?

副作用という言葉は色々な意味で使われるけれど、狭義には状態を書き換えることを指す。さらに広い意味で使われることもあって、この広義の副作用は、effectと呼ぶことが多いのだけど、これは式が持つ値以外の意味の総称である。これには値を求める際に発生する、狭義の副作用、入出力、非決定性、それから例外や大域脱出などの制御(controll)などが含まれる。また、非停止性などもeffectと考えることがある。

したがって、関数型プログラマの言う「副作用がない」ということの意味は、「式の意味は値であって、値以外の意味を考える必要はない」ということ。この性質はしばしば「参照透明性」と呼ばれる(実は参照透明性の定義も色々あって、ややこしいのだけど)。

だから、最終的な現象として入出力が発生したとしても、それが言語の上で値以外の意味を導入しない形で実現されていれば副作用は存在しないと言うし、最終的な現象として入出力が発生しないとしても、値以外の意味が存在すれば副作用があるという。 (例えば、この意味で例外による大域脱出は副作用である)

副作用を用いずに入出力を記述する

では、副作用を用いずに入出力を記述するプログラミング言語は可能だろうか?

入出力を記述するには、要は入力と出力の関係さえ定義出来ればいいので、そんなのは別にどうとでもなる。

例えば、入力と出力がそれぞれ標準入力と標準出力しかないとしたら、入力と出力の関係を定義するには String → String という関数を定義すれば十分である。なので、そのような関数としてプログラムを記述することにすれば良い。もちろん、これは非常に単純な場合しか扱っていなくて、問題も色々あるのだけど、副作用を用いずに入出力を記述するプログラミング言語が可能であることを示すには十分だろうと思う。

実際には標準入出力だけではなく、様々な種類の入出力を扱う必要があるので、実用的なプログラミング言語にするには、より一般的かつ柔軟な方法にする必要がある。 Haskellでは、過去には色々な方法が試みられていたけれど、今はIOモナドという方法に落ち着いている。 IOモナドを使う方法は、入力と出力の関係を String → String という関数で定義することに比べると遥かに複雑で巧妙な方法であるけれど、基本的な考え方には大きな違いはない(と思う)。

この話の目的はHaskellが採用している方法の詳細を説明することではないので、これで終わり。モナドやIOモナドについてのちゃんとした話はまたそのうち。