2009-08-18

[ソフト開発][ネタ]わかりやすいプログラムの書き方

※このエントリは、Arata Kojima/NPO法人しゃらくさんが公開しているわかりやすい技術文章の書き方の改変です。

このページは、プログラムやコードなどを書く方々のために、分かりやすいプログラムを書くためにはどうすればよいのかについて説明しています。
 1. 自分が伝えたいこと・訴えたいことを誤解しないように相手に読んでもらうにはどうするべきか。
 2. プログラムを書くにあたって知っておくべきルールは何か。
 3. プログラムを書く前にどのような手順を踏めば、分かりやすいプログラムを作れるか。
などについて参考にしていただければ幸いです。

プログラムを書く前に

プログラムを書く前に次のことをしっかりとイメージしておく。

何を書くのか。
書こうとしている物は正確に何であるのか。
仮定して良い、必ず成り立つ前提（状況／状態）は何か。
成り立つ事が単に多いだけ／今はたまたま成り立っている、という仮定してはならない前提（状況／状態）は何か。
核となる概念・構成物は何か。

プログラムを知る

プログラムとは何か

現実世界の課題が与えられ、または自分が課題を提起し、
その課題に対して明確な解を与え、
その課題を取り巻く現実世界を正確に定義する語彙を作成して、それによって解を記述する。

cf. 「プログラム＝動きを書く物」は集団幻想

標準的な構成要素とは何か

プログラムの構成は、言語により様々であるが

モジュール・パッケージ・名前空間
クラス・インタフェース・モジュール
メソッド・関数
ブロック・コード片

という要素が標準的である。次にそれぞれの要素について簡単に見てみる。

モジュール・パッケージ・名前空間: 互いに強く関連するクラス・インタフェース・モジュールをまとめる。
クラス・インタフェース・モジュール:

提供するメソッド・関数によって実現するただひとつの責務は何か。
責務に対する考え方は明確で十分単純であり、かつ、一貫しているか。
その責務を果たすために本当に依存すべき前提は何か。
状況依存や前提を切り離して、責務がより単純にならないか。
- 必須ではない他のクラス・インタフェース・モジュールに依存していないか。依存先を上位の型に変更できないか。
- 必須ではない値を保持・利用していないか。依存先の型に任せられないか。

メソッド・関数:

引数に対して返却すべき物は何か。それは明確であり、かつ、一貫しているか。
切り離せる状況依存や前提を抱え込んでいないか。引数に追い出せないか。引数の型を上位の型に出来ないか。
必須ではない非ローカルの変数（グローバルやクラスなど）を利用していないか。引数に追い出せないか。
記述のレベルは詳細過ぎないか、具体型に依存し過ぎてないか。意味が明確な下位関数に切り出してそれを利用して書けないか。引数側に任せられないか。
複数の事をしていないか。別関数に出来ないか。
所属している上位要素（クラス・モジュール）は適切か

ブロック・コード片: 変数の意味を明確かつ一貫させ、スコープを最小にする

そのほかに、プログラムの利用のためにはプログラムのドキュメント・マニュアル、確認にはテストなどを書く。

プログラムを組み立てる

プログラミングにおける語彙とは何か

プログラミング＝対象の分析、プログラム＝対象の定義

プログラムとは、日本語や英語ではなくプログラミング言語を使って、「対象」＝実現しようとしている事の定義」を書いたもの。対象が大きければ、対象を分析して、定義に必要なプログラミング言語上の語彙を増やす。もちろん、その語彙とは名前。そして、名前だけじゃなくて、それが示すものの定義をプログラミング言語で書く。こうやって語彙を積み上げていって、実現しようとしている事の定義を書く事がプログラミングに他ならない。

プログラムを書き始めるときに使える語彙は、環境に用意されたライブラリしかない。その語彙を利用して組み合わせて、新しい語彙の定義を書く。そうやって新しく作った語彙、環境に用意されている語彙を組み合わせて、対象の定義を書くのに必要な新しい語彙を積み上げる。そうやって作った、対象にフィットした語彙を使って、実現しようとしていること全体の定義を書いた物がプログラム
そのソースコードが汚い理由：共通した根源的な間違い - よくわかりません

プログラムを組み立てる順番

課題を取り巻く現実世界を細分化する:

プログラムを書くときにはまず実装を省いた概略プログラムつまり主要語彙集を作る。実装を省いたプログラムを作成するためには、課題を取り巻く現実世界を細分化する。

細分化するためには、課題に対する解の思い付きに対して次のような質問をする。

本当にそうなのか？
どういう意味だ？
いつから、いつまで？
どこで？
誰からの視点か、誰にとって該当するか？
どのようにして？
どんな状態なのか？
どうやって行うのか？
なぜなのか？
ほかの事例ではどうか？
これについては？
これだけか？
すべてそうなのか？
どうすべきだろうか？

それぞれの質問について、現時点で思いつくことのできた答えのアイディアや仮説をメモする。しかし、この答えは仮の目標であり、語彙集のネタである。

答えを思いつかなかった場合は、どんなことを調べれば答えられそうかを調べ、そのアイディアを書き込む。思いついた答えに問いを与え、それぞれの問いをさらに細分化する。

細分化した問いから主要語彙集へ:

細分化した課題を取り巻く現実世界を、実装を省いた概略プログラムつまり主要語彙集に持っていくためには問いを捨てる。その基準としては、

解を記述するのに最も重要な問いを中心に据える。
その課題を解決するために関連する問いや話題をピックアップする。
使用できるライブラリや既存実装を調べ、利用できそうかどうか、語彙がうまく噛み合うかを検討する。
粒度は適切か

主要語彙集からプログラムへ:

簡単なトップレベルのみの動かないプログラムを作る。
語彙の不足があれば補う
使用している語彙に、短くて正確な名前を与える。
名前に適合する実装を与えるため、必要なブロックやコード片を付け加えて、メソッド・関数を作る。
それぞれのメソッド・関数から不要な物を削り、実装を簡潔にする
長くなりすぎたメソッド・関数を、いくつかのブロックやコード片に整理し直し、可能ならそれらを別の下位レベルまたは同レベルの語彙として独立させる
それらを再度精査する。以下、繰り返し。

分かりやすい表現で書く

語彙の用意とその定義記述を区別する

木下是雄氏は「事実と意見（判断）との区別を明確にすることが特に重要である」と述べている。木下氏の考えはおいておいて、語彙の選択とその定義記述際の注意点を紹介する。

用意する語彙の選択の注意点:

課題を取り巻く実世界に関してそのプログラムのなかで書く必要があるのは何かを十分に吟味する。
抽象的であっても、どのような場合でも成り立つ明確な意味にする。
できるだけ明確な意味を持たせ、引数などのパラメタや子クラスなどの各実装側が責務を負えばよい詳細や具体性を混入させない。

語彙の定義記述の注意点:

語彙の意味を完全に記述する。
その定義に必要なレベルの粒度の語彙を使用して出来るだけ短く書く。
詳細は他の語彙に頼るが、正確に使用する。
語彙の意味に対して、勝手に前提条件を加えていないか注意する。
先に考えた語彙の意味に問題があれば、語彙自体を見直す

さまざまな表現に対する指針

プログラムはさまざまな表現で成り立っている。その表現の書き方を次に紹介する。

変数:

スコープはできるだけ短く。
変更不要であれば変数ではなく定数にする
同じ変数を複数の用途に使用しない
原則的に変数の数は減らして簡潔にする。int a=0;a=hoge();return a;ではなくreturn hoge();

return:

関係ない場合はすぐにreturnする。if(hoge){長い長い実処理;;}returnではなくif(!hoge)return;長い長い実処理;;

ループ:

ループは繰り返しではなく契約で考えて記述する。ループ事前条件、ループ中不変条件、ループ事後条件。
do-whileは原則使わない（賛否あり）

名前:

型の名前はそれがどういうものであるかを、値の名前は使い途を。
キャメルケースやスネークケースなどは、コーディング規約や言語の通例に従う。

プログラムを書く上でのポイントなど

最後に、プログラムを書く上でのさまざまなポイントをリストアップしておく。

「動けばいい」という発想がどこかに混入していないか、常に疑いを持つ。

参考文献

引用・参照したWebページ

『わかりやすい技術文章の書き方』（http://www.123kobe.com/doc/writing/)改変元ネタ
『あなたのソースを汚くして生産性も下げている、たったひとつの間違い』（http://d.hatena.ne.jp/r-west/20090516/1242489952）
『きれいなソースコードを書くために必要な、たったひとつの単純な事』（http://d.hatena.ne.jp/r-west/20090510/1241962864）

この作品は、クリエイティブ・コモンズ・ライセンスの下でライセンスされています。

※中盤辺りで順番がおかしいなどネタレベルの草稿なのであとで断りなく修正するかも知れません。

2009-05-16

そのソースコードが汚い理由：共通した根源的な間違い

ソフト開発

この内容には私も全面的に賛成で、クラスやフィールド、メソッド、名前空間など、とにかく文字として表れる名前には、必ず、例外なく、正しく誤解のない命名を徹底することが非常に重要だ。
http://blog.livedoor.jp/lalha/archives/50261226.html

先のエントリは、danさん *1やlalhaさんにまで言及いただき大変光栄で、なにより多くの人に読んでもらえた。多謝。
一方で、自分で読み直すと「先のエントリ」は、いくぶん観念的でいまいちよく分からないところもあるかなと思った。というわけで、より実践に結びつきやすいように、「何に気をつければいいのか」「どういう考え方でコードを書けばいいのか」を書いてみる。

lalhaさんがエントリで強調したかったという

(1) 適当に書いたコードは後でとても大きな被害をもたらす可能性が高い

への包括的な対策であり、

(2) たくさんのソフトウェアの「つくり」に触れ、APIを熟知しよう

と非常によく整合して親和する考え方だと思ってる。

プログラマの良心を自ら邪魔している、プログラマ自身の誤解に基づく行動、それは

プログラマたる者、誰だって自分のソースコードはきれいに書きたいと思っている、はず。プログラマはきれいにしたいと思っているのに、その希望に反してソースが汚くなるとき、またはきれいではなくなるとき、プログラマは決まってある事をやっている。
自分はこれが諸悪の根源で、かつ、ソースを汚くする原動力となる上にハマリによる時間の浪費を招き、バグをも増やしてコードの汎用性まで下げる、コーディングに現れる悪魔みたいなものと思ってる。それは、

「必要な動きにしようという考えで、ソースに手を入れる」という自己破壊

… (ﾟДﾟ)ﾊｱ?

これを徹底的に排除する事で、様々な効果得られ、ソースコードも必然的に綺麗になる。

な…　何を言ってるのか　わからねーと思うが（ｒｙ。

「そんなん、きれいとか汚いとか関係なく、やらなきゃしょうがないことだろ」と思う読者が多いかもしれない。でも、実際はそうではないこと、「必要な動きにしようという考えで、ソースに手を入れる」事を排除して、ソースコードを綺麗に書き、バグを減らして、変更に強いプログラムにできる事を以下で述べたい。

まず、「必要な動きにしようという考えで、ソースに手を入れる」と、どういう事が起きるか、から。

正しい名前、つまり「それは何？」という思考が抜ける・弱まる・後回しになる

名前の重要性は、前回書いた通り。「正しい名前」とは、それが何なのかを、そのスコープにおいて的確に表現している名前のこと。「それは何？」を一言で言うには、その名前以外に言い様がないような名前。

「正しい名前」へのこだわりは、名前そのものがよくなるだけでなく、「正しい名前」を考える事で「それは何？」という思考がはたらき、ソースの整理をうながし、設計まで改善される所にその威力がある。きれいなソースとは、すべてについて「それは何？」が明確となっていて整理されているソース。逆に汚いソースとは、「それは何？」という事が曖昧で整理もままならないようなソース。

「必要な動きにしようという考え」でソースをいじり、「必要な動き」を実現したらどうなるか。普通の人間なら、「ふう、できた。」とひとつの達成感が得られるだろう。しかしそのとき、「必要な動き」が出来ただけならば、ソースコードについて「正しい名前である事」が壊れている。「必要な動き」を実現する事自体には、「正しい名前」を維持する必要がまったくないのだから。

「必要な動き」がソースを破壊する

スーパープログラマーは分からないが、自分のような平凡なプログラマは、コーディングで大なり小なりの試行錯誤が入る。テスト段階でもNGが出たら直すし、使い始めてバグが出てもソースを直す。ソースは一度タイプしたらそれで完成するものではなく、どんどん書き直されるものだ。

だから、最初の時点ではすべてについて「それは何？」が明確となっていて整理されたきれいなコードを書いていても、「こうすれば必要な動きになる」という修正が入っていく事で、本来の「それは何？」を表していた名前と、実際の実態が少しずつずれていく。

「hogehoge」という関数・メソッドに、「ここでこれをやれば『必要な動き』になる」と、「hogehoge」には不要な処理が追加される。
「fugafuga」という関数・メソッドが、「ここでやる事を変えれば『必要な動き』になる」と、「fugafuga」じゃないものに変容する。
「pugepuge」という変数に、「ここでこういう値を入れれば『必要な動き』になる」と、「pugepuge」じゃない値が入れられる。
「geregere」というクラスに、「ここにこういうメソッドがあれば『必要な動き』を作れる」と、「geregere」の責任ではない機能が追加される。

こうやって、きれいだったソースも、だんだんきれいでなくなっていき、汚くなっていく。

これはそのコードを最初に書くときも同じ。「こういう動きが必要だな」という事を考えて、その動きをさせるべくソースを書いていくと、上記のようにめちゃくちゃなソースになる。

漠然とした「ソースをきれいにしたい」は、強力な「必要な動き」に必ず負ける

汚いソースは様々な害悪を振りまきながらも、そのときはなんとか「必要な動き」だけはやってくれる*2。そしてその場限りの労力を考えると、ソースをきれいに保つより汚く修正する方が非常に楽ちん。そして、「動き」は否応なく結果が出るのに比べて、「きれい」かどうかというのは人が判断する分、かなり曖昧。

だから「きれいに保ちたい」という漠然とした気持ちを持っていてそれに従って頑張ろうとしても、「必要な動き」という発想を基本思考としてソースを修正する限り、「動き」の強さに負けて基本的にソースは汚くなっていく。

「必要な動き」から逃れられれば、ソースはきれいになる。

ソースをきれいにしたいと思って頑張っても、「必要な動き」を追う限り、ソースは汚くなる。しかし逆に言えば、「必要な動き」にさえ束縛される事がなければ、ソースをきれいにしたいと思いがあり「正しい名前」を維持する労力を払えば、当然ソースはどんどんきれいになる。ならば、解決方法は決まっている。

「必要な動き」という発想を最初から捨ててしまえばいい

話は簡単。ソースをきれいにするには最初から「必要な動き」という発想を捨ててしまえばいい。

「プログラム＝動きを書く物」は集団幻想

プログラムを学び始めた初心者が読む本の多くは、Hello worldみたいな例から入って、if文やfor文などの説明に入っていき、「こういう書き方をするとプログラムがこう動く」という観点で説明が書かれる。自分が読んだのもそうだったと思う*3。そのため、ほとんどのプログラマは「プログラム＝動きを書く物」という基礎認識を最初から持たされることになり、習熟して経験を積んでもその認識の影響から逃れることが難しい。

しかし、そのような認識は、初心者向けの方便に過ぎない。ソースをきれいにしたければ、そのような誤った認識から脱却しないといけない。じゃあプログラムとはどういうものと認識すればいいのか。

プログラミング＝対象の分析、プログラム＝対象の定義

プログラムとは、日本語や英語ではなくプログラミング言語を使って、「対象」＝実現しようとしている事の定義」を書いたもの。対象が大きければ、対象を分析して、定義に必要なプログラミング言語上の語彙を増やす。もちろん、その語彙とは名前。そして、名前だけじゃなくて、それが示すものの定義をプログラミング言語で書く。こうやって語彙を積み上げていって、実現しようとしている事の定義を書く事がプログラミングに他ならない。

プログラムを書き始めるときに使える語彙は、環境に用意されたライブラリしかない。その語彙を利用して組み合わせて、新しい語彙の定義を書く。そうやって新しく作った語彙、環境に用意されている語彙を組み合わせて、対象の定義を書くのに必要な新しい語彙を積み上げる。そうやって作った、対象にフィットした語彙を使って、実現しようとしていること全体の定義を書いた物がプログラム。

「正しい名前を付けて、正しい名前である事を維持」する事＝「プログラム＝対象の定義」という認識

このプログラムに対する認識は、大仰な書き方に見えるかもしれないけど、実際は発想の問題に過ぎない。「正しい名前を付けて、正しい名前である事を維持する」事を本当に至上命題としてプログラミングしていたら、実際にやる事はまったく変わらない。

対象を定義するのに必要な物を考える。
それに名前を付けて、名前の定義を書く（＝名前のついた物を実装する）。
実装を動きではなく意味で見直し整理・洗練させる。
- 名前を付けられる独立性がある部分は名前を付けて独立させる。
名前と定義（実装）が合っているか確認する。
- 単純に定義（実装）の方が間違っていたら定義（実装）を直す。
- 必要だと思っていた物（名前）が実は違っていて定義（実装）の方が必要なことを正しくやっていたのであれば、名前のほうを直す。
繰り返し

この認識で、プログラムのきれい・汚いは、

プログラムが汚いとは、語彙の意味があやふやで不安定であること

プログラムがきれいとは、語彙の意味が明確で一貫していること

という風に考えられる。

語彙の意味があやふやで不安定だとどうなるか

プログラミング言語でなくて日本語などの普通の言語でも、言葉はその意味が安定しているから使うことができる。「赤」は、波長700nm前後の光であると言うことに安定しているから、「リンゴが赤い」「真っ赤な血」「フェラーリの赤」のように様々な物の記述に使えて、その記述が意味をなす。
これが、「動き」という意味不明な物の都合のために、あるときは500nm前後の光を指し、またあるときは1000nm前後の光を指し、しまいには「よくわからないけどこれで必要な動きになるんですよ」といってリンゴを指したり、というようでは、そんな言葉でまともに何か書くことはできない。

プログラムも全く同じ。というよりもっともっと厳しい。日本語を読む人間は融通を利かせて意図を汲んでくれるが、コンピュータは一切融通が利かない。めちゃくちゃな言葉で書かれていたら、書かれたとおりのめちゃくちゃな結果を出す。たまたま、言葉がめちゃくちゃでも結果オーライになることは確かにある。しかし、それはそのときその場だけの結果オーライ。定義（プログラム）に手を入れるとき、使える言葉の意味がこの「赤」のようにめちゃくちゃであれば、そんな言葉を使ってまともな定義を書くことは、きわめて困難で無駄な労力を必要とするうえに、結果も予測困難な危険な作業になる。

バグ＝語彙(名前)の定義記述の誤り

プログラムがプログラミング言語での対象の定義だとすると、それがおかしくなるのは、こういう時。

使ってる語彙の定義が間違ってる
- 「それ」を指しているはずの名前に対して、その定義が「それ」の定義としておかしい
語彙の使い方が間違ってる
- 「それ」をさしている名前を、「あれ」を指していると思って使っている

これがバグの目に見えない本当の姿。だからその修正は、「必要な動き」なんかを求めるんじゃなくて、

使ってる語彙の定義が間違ってる
- 「それ」を指しているはずの名前に対して、その定義を「それ」の定義になるように書き直す。
語彙の使い方が間違ってる
- 「それ」をさしている名前は「それ」として使う。「あれ」が必要なら「あれ」を使う。
  - 「あれ」がなければ、「あれ」を使わない定義方法を考える
  - もしくは、「あれ」を新しく定義する

こうやる。

こういう発想でプログラミングをしていけば、「必要な動き」に足を絡め取られることなく、ソースはどんどんきれいになり、ハマりによる無駄が回避され、バグも減り、変更に強いプログラムになる。

API・ライブラリ＝最初から用意されてる語彙。よい作り＝うまい言い回し・文章構造

ここまで、ソースをきれいに書くということを中心に述べてきた。一方、効率よくには、なんでも自前で語彙を作るのではなく最初から用意されてる語彙を熟知して、うまく使うことが重要なのはいうまでもない。日本語の言葉を知らない作家が失格であるように、プログラミング言語に用意された語彙を軽視していてはプログラマとして問題だ。

わかりやすく整理された文章は、うまい言い回しやうまい文章構造を備えている。先人たちがたどり着いたうまい言い回しやうまい文章構造を学ばずに、全部自分でオリジナルに考えるというのは無謀に過ぎる。プログラミングにおいても、全く同様。「巨人の肩の上に立つ」のは、何事においても、よい成果を上げる必須条件だろう。

以上、当初公開時より若干推敲・改変・追記してます。疑問質問歓迎。

というわけで、Haskellやろうぜ！あと、Ozも。（おまけ）

「プログラム＝動きを書く物」という認識は根強くて、頭の切り替えは楽ではない。しかし、できるだけ「プログラム＝対象の定義」という認識を意識しつつ、なにより「正しい名前を付けて、正しい名前である事を維持する」という鉄の意志を持ってプログラミングに望むことで、だんだん慣れていく。これが普通だと思う。

ただ、ここでひとネタ。強制的にその認識を矯正する方法のひとつとして、Haskellをやってみるというのもよいかも知れない。なんたって、この言語には「動き」がない*4。まさに関数の定義を書いていって定義を積み上げた物がプログラム。定義の中身がどういう順番で動くか解らない。ただただ、正しく定義を書くだけ。

荒療治だが、他にも色々学べる事が多いと思う。

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門

posted with amazlet at 09.04.17

青木峰郎
ソフトバンククリエイティブ
売り上げランキング: 68076

Amazon.co.jp で詳細を見る

WebにHaskellの情報は結構あるけど、大半が玄人向け。「やさしいHaskell入門(A Gentle Introduction to Haskell)」というドキュメントがあるが、これは「天才な人にはやさしい」という意味なので要注意。ふつうの人には、この本がふつうの意味でやさしいくていい感じ。興味が湧いた人には、まずこの本を読むのがお勧め。

あと、同様に動く順番不明での書き方がある言語「Oz」。その言語とともに、プログラミングの色んなモデルを学んで視野を広げられる、通称「CTMCP（または「ガウディ本」）」も紹介しておく*5。

コンピュータプログラミングの概念・技法・モデル(IT Architect' Archiveクラシックモダン・コンピューティング6) (IT Architects’Archive CLASSIC MODER)

posted with amazlet at 09.05.16

セイフ・ハリディピーター・ヴァン・ロイ Peter Van-Roy Seif Haridi
翔泳社
売り上げランキング: 74139

Amazon.co.jp で詳細を見る

求められてなくても勝手にお返事

読んでくれた方、賛同してくれた方、ありがとうございます。皆さんが苦しんでいるように（？）自分も周りに十分理解を得られてるとは言えないので、疑問には答えたいと思っています。なので、一方的に勝手に答えてしまいます。ご了承あれ。

id:thesecret3 その「必要な動き」って例えばデータベースが極端に遅い場合に、同じデータを複数回読まないようにするためには・・とやると一気にソースは汚れるけど、やるなともいい難かったりする。
http://b.hatena.ne.jp/thesecret3/20090517#bookmark-13499672

最終的に動くのは当然の事実で、事実を無視しては正しい定義は確かに書けませんね。なのでそれはたとえば、「DBから○○を取ってきた結果」じゃなくて「このリクエスト処理のスコープにおける○○のデータ」というような語彙を用意してやって、それを使うというような解決になるのではと思います。あるいは、本当は○○のデータが要らないのであれば使わないに超したことはなく、それは定義から無駄を省くことに他ならないと思います。意識が必要なことは要件として対象として意識して、使う・用意する語彙を工夫して不要な依存(DBアクセス)を排除するという事自体が、「それは何？」でプログラムを書くことだと思います。

id:h_tksn 結論に絶望した。
http://b.hatena.ne.jp/h_tksn/20090517#bookmark-13499672

えええ〜〜〜っ！？な、なんで？というか、その「結論」って？。☆を付けてるid:polyamidも教えてください。
あ、HaskellとOzは、全然必須じゃないですよ。すごく役に立って面白いハズだけど、興味がある人だけで。興味がなければ、「プログラム＝対象の定義」「正しい名前を付けて、正しい名前である事を維持する」という鉄の意志を持ってそれを実行してれば十分だと思ってます。紛らわしかったのではっきり「おまけ」と書き直しました。すみません。

id:Zephid 正しい名前を付け、その通りの処理内容にする。/でも自分は分割されまくったコード読むのが苦手。辞書のまた引き状態になって目的を見失う

（後半について）そこで「正しい名前」ですよ！「また引き」になるのは、関数・メソッドが出てくる度にその中身を読みに行くからですよね？中身を見に行かなくても名前を見るだけで「それは何？」のキモが解るようにしてあれば、中身を読みに行かなくても大体解るはず。さらに最初に読んでる関数・メソッド自体も、一言で名付けられる位短い物になっていれば、「先（使ってる関数・メソッドの中身）」を読みに行く事無しにその関数・メソッドの全体のキモ・概要を把握出来ます。
なので、まずは「先（使ってる関数・メソッドの中身）」を読みに行くことなくその処理のキモ・概要を把握して、それから必要に応じて詳細を確認するために「先」を見に行く、ってのがよいと思ってます。これが出来るようにソースを書いて、こういう読み方になれると、長々じっくりと大量のソースを読み込む必要なく、さっくりと処理のキモ・概要が把握する事も可能になるので、実際のプログラミングでは超絶便利です。

*1:こっちから勝手にリクエストしたんだけど^^

*2:やってくれなかったらきれい汚い以前の問題

*3:遙か昔で忘れてしまったが、ナイコン(年がばれるｗ)の身で図書館で借りたBASICの本

*4:乱暴な言い方だけど

*5:紹介しておきながら、自分は積ん読状態…。すみません

2009-05-13

きれいなソースに重要なのは、よい名前というより…

（ここに書いてた記事は「きれいなソースコードを書くために必要な、たったひとつの単純な事 - よくわかりません」の「追記」に移動しました）

2009-05-10

きれいなソースコードを書くために必要な、たったひとつの単純な事

ソフト開発

「構造のきれいなプログラムを書けるようになるためにはどうすればいいのか？」という質問を受けたので、「はて？どうしているだろうか？」と考えてみました。あ、形式知にきちんとなっているようなテクニックみたいなもんじゃなくて、モノローグなので、あまり凝ったものは期待しないように。
http://blog.shibu.jp/article/28983162.html

自分なりにもっと凝縮版を。渋川さんが言っている事全体もその通りとは思うけど*1、もっと簡単で、しかも射程が広い、と自分が思っている事。

渋川さんはちょろっと触れてるだけだけど、自分はこれが最も基本的で汎用的、かつ、ソースをきれいにする原動力となる上にバグをも減らしてコードの汎用性まであげる、コーディングのエンジンみたいなものと思ってる。それは、

「すべてに正しい名前を付けて、そして、正しい名前であることを維持する」という鉄の意志

クラス、モジュール、メソッド・関数、変数（モジュール、クラス、インスタンス、ローカル、etc）など、プログラムで名前がつくものすべてについて、「正しい名前」を付ける。そして、「正しい名前」であることを維持する。維持するためには、コードの方を変える事も、名前の方をより正しい新たな名前に変える事も、どちらもやる。さらに、その言語では名前が付けられないような、ブロック、ループ、数行のコードの固まり、などなどにも、正しい名前を付けたがる姿勢まで含む。意志なんてヌルいものではなく、名前原理主義、名前パラノイア、などと言ってもいいかも知れない。

「正しい名前」とは、それが何なのかを、そのスコープにおいて的確に表現している名前のこと。「それは何？」を一言で言うには、その名前以外に言い様がないような名前。
それ自体は、至極シンプルな事。でも、それを徹底的に突き詰める事で、まったく単純ではない様々で莫大な効果得られ、ソースコードも必然的に綺麗になる。では、なんで「正しい名前」でソースコードが綺麗になるのか。

※本エントリに関連して、実践するために気を付ける事や考え方みたいのを書きました。よろしければこちらも。
　「そのソースコードが汚い理由：共通した根源的な間違い」

「名前が正しければ、そりゃソースは読みやすくなる」は違う

もちろんそれはそれで非常に大事な効果。意味がない名前や実態と合ってない名前が溢れてると、ソースを見ても、何をやってるか分からなかったり、勘違いを招く。それがなくなれば、ソースは大幅に読みやすくなる。大きなメリットであり非常に重要ではあるけど、それは効果のほんのごく一部に過ぎない。「正しい名前付け、正しい名前の維持」で生まれるのは、そんな当たり前の事だけではない。「正しい名前」を付けるために、コードの方も直すのだから。

「すべてに正しい名前」を求める意志は何を生むか

偉そうなことをいっておいて、実は全然整理されてないけど*2、思いつくところを順不同で挙げていく。抜けてる物・説明もたくさんあると思う。それぞれは完全に独立したものではなく、多分にオーバーラップしつつ、全体で上記に挙げたメリットに繋がる。

そのコード・その部分がやることが明確になる

たとえば、メソッドや関数。適当な名前で「なんとなく」で書き始めてなんとなく動いたら終わり、では、目的不明確でコードがヨレがち。ヨレてフラフラしたコードが綺麗な訳がない。その各部分（ブロックなりループなり、メソッド・関数内の数行の塊なり）に注目しても、単に不完全な断片にしかならない。

しかし、まじめに的確に名前を付けようとすれば、それが何をする物なのか明確に考えなくちゃならない。そして、明確になったら名前としていったん固定され、実装ではその固定された「やる事」をぶれずに書き下す。もちろん、実装中に名前の方が実は間違ってる事に気が付いたら、名前の方を直す。書き上がってからも、名前と実態が合ってるか、名前にそぐわぬコードが混ざってないか見直す。これにより、無駄やヨレがなくなり、コードは綺麗になり、バグも減る。

部分についても同様。実際に言語では名前を与えられなくても、各部分部分について的確な名前を考え、コードもそれに合わせるように直していけば、部分についてもやる事が明確になり、無駄・ヨレの排除でコードが綺麗になり、バグも減る。

クラスでもモジュールでも、話は同じ。

変数であっても同じ。その変数は何なのかきちんと考えて固定すれば、役割が明確になる。役割が明確なら、役割に合わない値を入れたり、役割と違った目的で値を使う事がなくなる。というか、なくす。もちろん、最初考えた役割の方が間違ってたら、正しい役割を表す名前に直して、その役割と使い方がすべて合ってるか見直す。これも、ヨレを無くし、バグを減らす。

「それは何なのか」が一貫する

適当な名前で何となく書かれた関数なりクラスなり変数なりは、曖昧がゆえに実装の部分部分や使われる場所によって、それがどういう物なのかが微妙にまたは大きく揺らぎが生じる。これもヨレや無駄、そしてバグの元。

一方、かならず的確な名前を付けるようにしていれば、その実装やその使い方がそこから外れる事が無くなる。実装や使い方が、その名の通りに一貫される。使い方を間違えない。

スコープが最適になる

なんとなく処理に必要な変数を用意して使っていると、それが必要な範囲も漠然としてしまう。

変数に最も的確な名前を考え、コード内の部分（ブロックなりループなり、メソッド・関数内の数行の塊なり）についても的確な名前を考えていくと、変数がその名前にふさわしい役割で必要とされている範囲がはっきりしてくる。そして、スコープで適切な名前にしようとすると、自然と本当に必要な範囲だけのスコープの変数になっていく。

スコープが最適になると言う事は、それが本来無用の場所でも間違って使われたり、読むときも無用に意識する必要がなくなるという事。ソースは綺麗になり、バグも減る。

プログラムが「とにかくそう動く」ではなく、意味レベルで整理・洗練される

そのコードが何なのか一貫した認識がなく、またそのコードで使ってる変数や関数も何なのか曖昧だと、「ああなってこうなって…、えーと…、ウン、よし、動くな」と、動き中心でコードが書かれがち。それでは、何とかそのときは動くコードにはなるが、コードは洗練されない。

きちんと的確な名前を付けようとすると、動きでなく意味で考えざるを得なくなる。意味で考えて意味通りのコードにしようとすれば、コードはただ動くではなく、洗練の方向が明らかになるし、洗練させずには意味通りのコードにはならない。

コードの凝集度が上がる

そのコードが何なのか一貫した認識がなく意味レベルで整理されていなければ、「動く」という理由で、関係の深い物も浅い物もバラバラに配置されたままになる。

意味で考えられていて、コードを意味に合わせていれば、関係ある物はどうしたって集まってくるし、関係が浅い物は離れていって別メソッド・関数や別クラスなどに分離されていく。これはコードの凝集度が上がる事に他ならない。凝集度があがると、コードは綺麗だし、変更の影響範囲が狭い範囲に閉じるし、コードの依存事項も小さくなり、いい事づくめ。

設計が本当に必要な最適解に近付いていく

名前と実装の絶え間ない改善のスパイラルは、実装を書いてみて気が付いた大事な事を吸収しながら、ソースコードを明確な意味達の集まりに洗練していく。これはソースコードを、事前設計では得られない正しい設計に導く。

さらに、それぞれの意味が明確に名前で表されていれば、必要なものとのズレも見付けやすくなる。これによって、そのズレを直すべく設計をさらに洗練させる事になる。

複雑さが名前で表現できる範囲に押さえられる

名前は名前であり、それなりに簡潔であるべき物。簡潔な名前の意味にあったコードにするには、そもそもダラダラと長く複雑なコードではいられなくなる。長いコードは、その部分（ブロックなりループなり、関数内の数行の塊なり。あるいはメソッドの集まりであったり）についてもそれが何であるのか名前を付けようと意味を明確にしようと考える事で、部分の役割が明確になって、関数やクラスに独立させる事になる。

コードがシンプルになる

正しい名前にするために意味で整理して凝集度が上がることで、メソッド・関数なりクラスなりは小さな単位になっていく。これは、一つ一つの役割は小さくなり、小さな役割について意味を明確にしようとして、その明確な意味通りのコードにしようとすれば、それは自然に短くシンプルになる。

コードの矛盾・ズレ・間違いが排除される

使ってる物（変数・メソッド・関数・クラス、など）の正しい名前・意味が曖昧なままだと、使ってる物に何か変更が入ったときも、もともとの意味が曖昧なので使い方に矛盾・ズレ・間違いがあっても目立たない。

使ってる物の名前・意味が明確ならば、使い方の矛盾・ズレ・間違いは目立つし、かつ名前・意味を明確であり続けさせようとすると、そのような矛盾・ズレ・間違いは排除しない訳に行かない。

依存の少ない変更に強いコードになる

使ってる物（変数・メソッド・関数・クラス、など）や部分（ブロックなりループなり、関数内の数行の塊なり。あるいはメソッドの集まりであったり）の名前・意味が曖昧なまま整理されないと、それらが依存する（影響を受ける）ものも必要以上に増えた状態になる。そのため、別の部分を修正したときも、本来関係ないはずであっても影響を受けてしまいやすくなる。

的確な名前を考え意味で整理され無駄が無くなっていると、本当に必要な物だけが使われるので、関係ないものへの依存が無くなり、変更に強くなる。

コードの重複が排除される

その部分の名前・意味が曖昧で依存が広く塊も大きいと、似たような事をやるにもちょっとした違いのためにそれを利用できず、また部分的にはほとんどそのまんまでも、部分を切り出す事が困難になり、似たような別のコードを書かなくてはならなくなる。

明確な名前と意味で整理されたコードは、自然と凝集度が高く独立性が高い小さな単位(メソッド・関数、クラス、など)の集まりになる。役割が小さく意味が専門化させていくと、そもそも「似た処理」の本当の共通の性質部分そのものの意味になりやすい。「似た処理」が必要と思ったとき、その部分について本当に的確な意味として既に切り出されて専門化されている。

汎用な物が抽出され、それを利用する事で、コードがさらに簡潔になる

前項とほとんど同じだが、部分部分の小さな単位に的確な名前を付けて独立させると、それは小さく、そして元の場所のしがらみから離れて汎用的な物になる。そうやって汎用的な物がどんどん独立していき、そしてそれらの塊にも適切な名前を与えるべく専門の塊にしていくことで汎用性を持つライブラリが出来ていく。

そのようなライブラリを他からも使用する事で、コードは全体としてさらに簡潔に書きやすくなっていく。

一番大事なのは、常に正しい名前を求める意志であり、場合によっては必ずしもその通りの名前を付けなくてもいい

もちろん普通はその名前を付けた方がいい。いいけど、上記のメリットは正しい名前を求める意志・思考自体によるところが大きい。だから、言語でのお約束として、たとえば自明なレベルではループカウンタはi,j,k,...を使うなら実際のコードではそれを使ってもいいし、とにかく簡潔な名前を使う慣習の言語では、名前に若干の説明不足が生じても仕方ない*3。*4

名前重要、超重要。そしてその先

ちゃんと名前を付けるってのは、基本と言えば余りに基本的な事。でもそれは、その一言ではとても尽くせない、広大な汎用性を持つ超重要事項。それに本気になればなるほど、それに見合ったご利益が得られる、と思う。

このエントリでは、一般的な「きれいな」ソースコードのための超絶最重要事項として正しい名前を挙げた。これは自分なんかが言わなくても、実践できてる人も多いかも知れない。そういう人は、もう一段上の「美しい」コードについて、ハッカー達の濃い思いをじっくり味わうのもよいかも知れない。「きれいな」と「美しい」の違いとかは、danさんが書いてくれる事を期待（→ なんとホントにdanさんがエントリ書いてくれました！ 404 Blog Not Found:いい仕事をするためのたった一つの心得 - 「美しい」から「かっこいい」へ）。

ビューティフルコード

posted with amazlet at 09.05.10

Brian Kernighan Jon Bentley まつもとゆきひろ
オライリージャパン
売り上げランキング: 101149

Amazon.co.jp で詳細を見る

追記

コメントやブクマを見て、説明不足だったかもと思ったところを補足。

きれいな名前じゃなくて、「正しい」名前

重要なのは、しゃれた名前とか、縁起のいい名前とか、知的な名前とか、詩的な名前とか、かわいい名前とか、そういうのじゃない。ただ単に「それは何？」という事を考え抜き、コードに対して「そのまんま」な名前を考える。そして、名前そのまんまのようにコードを書き、そのまんまになるように直す。それだけ。センスがある人は(邪魔にならない限り)そう言う要素を混ぜてもいいかも知れないけど、必要なのはもっと愚直に考える事。

「それはどんなかんじ？」じゃなくて、「それは何？」

たとえば、手に負えないようなぐちゃぐちゃなソースに対して、"spagetti"なんて名前を付けても、まあ確かにある意味そのまんまかも知れないけど正しい名前じゃない。「中身がどう」じゃなくて「中身が何か」を表さなくては意味がない。

「こんなのに正しい名前なんて付けられない」じゃなくて、正しい名前を付けられるように整理して分割する

俗に「ひとつの関数・メソッドは、25行(1画面)以内」というプログラミングの格言がある。自分がプログラミングをまともに始めた頃は、そんな無茶なという認識だった。その頃は、それに一言で正しい名前なんて付けられないようなのを書いてた。でも、正しい名前を付ける事を強く意識して内容を一言で言える単位毎にまとめて整理・分割していくと、いつのまにか25行以上なんて関数・メソッドはごく例外的なものだけという状況になっていた。曖昧にダラダラ書いた関数・メソッドでは、正しい名前は付けられない。そこをうんうんムリに考えるんじゃなくて、関数・メソッドの方を整理して分ける。これは、クラスやモジュールでも同じ。いつの間にデカくなってきたクラスやモジュールは、「正しい名前であること」を維持できているか見直して、整理して分割して、正しい名前を付け直す。

名前そのものじゃなくて、正しい名前を付けられるソースにする事

大事なのはソースをよくする事であって、名前はそのきっかけや手掛かりに過ぎないとも言える。目的はソースを見やすくするだけじゃなくて、構造や設計を含めてきれいにする事だし。

役割がシンプルで単一なものになるように整理分割されてないと、一言でそのまんま言い表せる名前は付けられない。中身を一言でうまく言えないソースは、部分部分にそれぞれ正しい名前を付けられるように整理して正しい名前で分割する。これをしなければ、名前だけそこそこの物を考えても、「名前でソースをきれいに」としては全くの片手落ちで、前のエントリで書いた効果の多くが得られない。

「正しい名前」の実現は、ソースを書き換えてきれいにしていくための方法であり、考え方。漠然とソースを書き換えてもきれいになるとは限らない。だから羅針盤が必要。その羅針盤が、「正しい名前」と「名前通りのソース」を追い求める事。

「きれいなソース｣は、リターンの大きい、時間の投資

正しい名前を考え、ソースもきちんと直すには、確かに時間はかかる。目の前の10行だか100行だかを、ただとりあえず動くだけのレベルで書くのに比べたら、余計に時間はかかる。その程度の規模で、動いたらもうメンテせずに棄ててしまうプログラムならば、こだわってもご利益に見合わないかもしれない。

しかし、たいていのプログラミングは、目の前の10行だか100行だかを書いて終わりじゃない。実際は、全体としてもっともっと沢山のコードを書き、そしてその後それをメンテナンスしなくてはいけない。そこで、「きれいなソース」のために投じた時間に、莫大な利子が付いて返ってくる。整理されてなくて、何やってるかも不明確で、ちょっと条件が変わると動かなくなるようなソースが一部分でもあると、それに関係するプログラムを書くときに何かにつけてあれやこれやの無駄な時間を食われる。それが一部分じゃなくて、大部分のソースがそんな状態だと、もはや手枷足枷目隠しをされてプログラミングするのと同じだ*5。

そしてもうひとつ。きちんとそれが何かを徹底的に考え、徹底的にプログラムを整理する事は、こだわった分だけ、ほかならぬそのプログラマ自身のスキルを着実に向上させる。プログラムをただ書くのではなく、ちゃんと考えて整理するために仮にいまは10の時間が掛かっても、それをやった分、次は9の時間でそれができ、その次は8の時間で、というふうに、投資に必要な時間がどんどん短くなっていく。投資額は小さくなっていくが、リターンは減るどころかどんどん大きくなる。こんなにおいしい投資をしないのは、あなたの時間とあなたの誇りを自ら捨ててる事と同義ではないか。

-疑問・質問歓迎-

疑問・質問・その他、歓迎。米欄のほか、続きのエントリ「そのソースコードが汚い理由：共通した根源的な間違い - よくわかりません」の末尾で（求められてなくても勝手に）回答。

*1:ただし、引きこもりがきれいなコードをかけないということは全くないと私は思います

*2:なので、後で断り無く記事をブラッシュアップするかも。→実際ちょっと加筆修正してます（おもに、すこし「部分」を強調。あと設計にも触れた）。

*3:そういう場合は、長い「正しい名前」はコメントとして付しておくといいかも

*4:あと関数型言語とかだと、抽出したものが余りに抽象的でまんまの意味となる的確な名前を簡潔になんて付けようもなかったりするけど、そういう言語ではそう言う物は既に標準ライブラリに大抵入ってるし、大事なのはそう言う思考って事で

*5:恐ろしいのは、大なり小なり、プログラミングとはそう言うものだという認識がまかり通っている組織が往々にして存在する事。

2009-04-22

さあ、Yコンビネータ(不動点演算子)を使おう！

前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。

Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。

じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？

というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。

今回、プログラムの例をJavaScriptで書きます。Yコンビネータ(不動点演算子)は、amachang先生の定義を拝借します*1。

function Y(f) {
  return (function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })(function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })
}

その1。無駄な再帰を省略して爆速化

まず、Yコンビネータや不動点の考え方の応用は、「メモ化(memoization)」という汎用関数です。

きしださんも例に用いていた、フィボナッチ数という数を計算する関数を考えます。

まず、Yコンビネータとか関係なく、普通に再帰するバージョンです。

function fib(x) {
  if (x < 2) {
    return 1;
  } else {
    return fib(x-1) + fib(x-2);
  }
}

fib(1)は1、fib(2)は2、fib(3)は3、fib(4)は5、fib(5)は8、fib(6)は13が返ってきます。これでちゃんと計算できるし、なにより、フィボナッチ数の定義通りのコードでとても解りやすいです。が、実はものすごい無駄があります。

    return fib(x-1) + fib(x-2);

ここです。たとえば、xが5のときは、fib(4)とfib(3)の両方を計算します。その前者fib(4)の計算では、同様にfib(3)とfib(2)の両方を計算します。fib(3)は、fib(5)の計算でもfib(4)の計算でも、どちらでも計算されます。答えは同じなのに２回計算されます。無駄です。同じ感じに、fib(2)は３回、fib(1)は５回計算されます。超無駄です。xが大きくなるにつれて、この無駄は凄い事になります。

自分のポンコツマシンとOpera9.64でfib(30)を実行してみたところ、結果は1346269で、1秒188msec掛かりました。fib(35)だと結果は14930352で、なんと14秒547も掛かりました。

遅い。なんとかしたい。再帰のところで、もう解ってるfib(x)は最初から計算せずに済ませたい！。ぜんぜん違うコードに書き直せば、出来るかも知れないけど、解りやすいコードがめちゃくちゃになるのも困る＞＜

そこで不動点です。

まず、fibをコードのキモの部分をそのままにして、前回説明した「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を用意してやります。前回で書いた $\small F$ に当たるものです。

function F_for_fib(f) {
  return function (x) {
    if (x < 2) {
      return 1;
    } else {
      return f(x-1) + f(x-2);
    }
  };
}

これをYに入力すれば、不動点すなわち再帰する関数が得られます。

fib = Y(F_for_fib);

不動点版fibが出来ました。ちゃんと動きます。fib(1)は1、fib(2)は2、fib(3)は3、fib(4)は5、fib(5)は8、fib(6)は13が返ってきます。

ここまでではYコンビネータを使うようにしただけでまだ高速化は何もしてません。そこで、Yコンビネータの方に(とりあえず安直な)キャッシュ機構を仕込んでみます。名前をYmemoとしましょう。

function Ymemo(f) {
  var memo = {};//キャッシュ
  return (function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })(function(g) {
    return function(m) {
      return (function(n){
        if (memo[""+n] == undefined) {//キャッシュにないときだけ、
          memo[""+n] = f(g(g))(n);//まじめに計算してキャッシュに入れる
        }
        return memo[""+n];//結果をキャッシュから返す
      })(m);
    };
  })
}

fib = Ymemo(F_for_fib);

「キャッシュ機構利用版」のfibが出来ました。ちゃんと動きます。fib(1)は1、fib(2)は2、fib(3)は3、fib(4)は5、fib(5)は8、fib(6)は13が帰ってきます。

で、こいつで時間を計測してみると、fib(30)は0msec、fib(35)でも0msecでした。計測不可能の瞬殺です。fib(30)は少なくとも1000倍以上、fib(35)は少なくとも1万4千倍以上の高速化ができました。もちろん結果はちゃんと1346269と14930352が帰ってきてます。爆速。

そして大事なのは、Ymemoはfib専用ではないと言う事です。Ymemoは、「キャッシュ機構付き再帰」を作り出す汎用のライブラリとして使えます。様々な「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」に対して、「キャッシュ機構付き再帰」を産み出してくれます。

Ymemoのほかの利用例として、「ハノイの塔」*2というパズルを解くプログラムを試してみます。

function Hanoi(x,a,b,c) {//パズルの状態を表すオブジェクト
  this.x = x;
  this.a = a;
  this.b = b;
  this.c = c;
}
Hanoi.prototype.toString = function() {//パズルの状態を表すオブジェクトのメソッド(オブジェクトを文字列化)
  return ["{",this.x,":",this.a,":",this.b,":",this.c,"}"].join('');
}

function hanoi(x) {//パズルの解法を文字列で返す関数
  if (x.x==0) {
    return "\n";
  }
  return [hanoi_(new Hanoi(x.x-1,x.a,x.c,x.b)),
          x.x, ":", x.a, x.b, "\n",
          hanoi_(new Hanoi(x.x-1,x.c,x.b,x.a))].join("");
}

hanoi()にパズルの状態Hanoiを入力として渡すと、文字列で解法のステップが返ってきます。Hanoiのプロパティxがパズルの規模を表す値で、a,b,cはパズルで使う３本の棒を表します。

この普通のバージョンを実行したところ、x(パズルの規模)が20の時に23秒515msec、22の時には1分33秒781msec掛かりました。

さきほどのfibと同様に、hanoiをコードのキモの部分をそのままにして、「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を用意します。

function F_for_hanoi(f) {
  return function (x) {
    if (x.x==0) {
      return "\n";
    }
    return [f(new Hanoi(x.x-1, x.a, x.c, x.b)),
            x.x, ":", x.a, x.b, "\n",
            f(new Hanoi(x.x-1, x.c, x.b, x.a))].join("");
  }
}

そして、Ymemoに入力して「キャッシュ機構付き再帰」を取得します。

var hanoi = Ymemo(F_for_hanoii);

このYmemoで作った「キャッシュ機構利用版」hanoiを実行したところ、掛かった時間は、x(パズルの規模)が20の時に578msec、22の時には2秒125msecでした。fibほどじゃないですが、40〜50倍は高速化されています。

その2。Yコンビネータへの機能追加をpluggableに

Ymemoでは「メモ化」を直接Yコンビネータに組み込みました。しかし、他の機能も追加する事を考えると、これでは不自由です。ここで色んな機能を追加するための準備として、Yコンビネータと追加機能を分離します。Yコンビネータの方は素のままにしておき、Yコンビネータに渡す「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」の方に仕込みを入れる様にします。

function wrap(F,g) {//仕込みgを組み込んだ「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を返す。
  return function (f){
    return F(g(f));
  };
}

仕込みであるgは、受け取ったfのフリをする関数(fの偽物)を返すようにします。

では仕込みの例として、先ほどYコンビネータに直接組み込んだメモ化機能を、独立した仕込みとして切り出します。

function gen_memorizer() {//メモ化の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。
  var memo = {};
  return function (f) {
    return function(n){
      if (memo[""+n] == undefined) {
        memo[""+n] = f(n);
      }
      return memo[""+n];
    };
  }
}

これで、素のYコンビネータを機能を仕込んで利用できます。

fib = Y(wrap(F_for_fib, gen_memorizer()));

Yコンビネータは素のものです。F_for_fibの代わりに、メモ化の仕込みを入れた「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」をYコンビネータに渡します。ちゃんと、fib(1)は1、fib(2)は2、fib(3)は3、fib(4)は5、fib(5)は8、fib(6)は13が返ってきます。

ハノイの塔の方は、

hanoi = Y(wrap(F_for_hanoi, gen_memorizer()));

です。これもちゃんと動きます。

その3。ホントに動いてる？どう動いてる？トレース機能の追加

では、メモ化の次に、今度はデバッグ的な機能を追加してみます。

またも安直ですが、トレース機能の仕込み生成関数です。

function gen_tracer() {//トレース機能の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。
  return function (f) {
    return function(n){
      alert("called with argument: '"+n+"'");
      return f(n);
    };
  }
}

再帰の度に引数を表示します。（ここでは、alertを使って引数を表示しますが、デバッグと言う事でconfirmやpromptを使えば、実行中に変数の値などをユーザが変えてしまうような機能も作れますね）

fib = Y(wrap(F_for_fib, gen_tracer()));
fib(5);

とやると、
called with argument: '5'
called with argument: '4'
called with argument: '3'
called with argument: '2'
called with argument: '1'
called with argument: '0'
called with argument: '1'
called with argument: '2'
called with argument: '1'
called with argument: '0'
called with argument: '3'
called with argument: '2'
called with argument: '1'
called with argument: '0'
called with argument: '1'
called with argument: '4'
called with argument: '3'
called with argument: '2'
called with argument: '1'
called with argument: '0'
called with argument: '1'
called with argument: '2'
called with argument: '1'
called with argument: '0'
とダイアログボックスが出てきます。こんな感じに動いてるんですね。

やはり、同じ引数で何度も実行しているようです。では、さっきのメモ化版ではどう動いていたのでしょうか。

その4。複数の機能追加を組み合わせて使う

プラグイン化した追加機能は、組み合わせて使えます。

fib = Y(wrap(wrap(F_for_fib, gen_tracer()), gen_memorizer()));
fib(5);

wrapは、「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」に対して、機能を仕込んだ「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数」を返します。なので、それに対しても同様にwrapで機能を仕込めます。実行結果は以下の通り。

called with argument: '5'
called with argument: '4'
called with argument: '3'
called with argument: '2'
called with argument: '1'
called with argument: '0'
called with argument: '1'
called with argument: '2'
called with argument: '3'
called with argument: '4'
ずいぶん減ってますね。

もちろん組み合わせた機能も、fibだけじゃなくて、ほかの関数にも使えます。さっきのhanoiに使ってみます。

hanoi = Y(wrap(wrap(F_for_hanoi, gen_tracer()), gen_memorizer()));
hanoi(new Hanoi(5,'A','B','C'));

called with argument: '{4:A:C:B}'
called with argument: '{3:A:B:C}'
called with argument: '{2:A:C:B}'
called with argument: '{1:A:B:C}'
called with argument: '{0:A:C:B}'
called with argument: '{0:C:B:A}'
called with argument: '{1:B:C:A}'
called with argument: '{0:B:A:C}'
called with argument: '{0:A:C:B}'
called with argument: '{2:C:B:A}'
called with argument: '{1:C:A:B}'
called with argument: '{0:C:B:A}'
called with argument: '{0:B:A:C}'
called with argument: '{1:A:B:C}'
called with argument: '{3:B:C:A}'
called with argument: '{2:B:A:C}'
called with argument: '{1:B:C:A}'
called with argument: '{1:C:A:B}'
called with argument: '{2:A:C:B}'
called with argument: '{4:C:B:A}'
called with argument: '{3:C:A:B}'
called with argument: '{2:C:B:A}'
called with argument: '{2:B:A:C}'
called with argument: '{3:A:B:C}'

こんな感じにいくらでも作れる、組み合わせれる、しかも汎用

function 普通の再帰関数(x) {
  中身。「普通の再帰関数」を呼ぶ。
}

を、Yコンビネータに食わせる形の

function 関数を入力として受け取りその関数を使う新しい関数を作って出力する関数(f) {
  return function (x) {
    中身。「普通の再帰関数」の代わりにfを呼ぶ。
  };
}

にしておく事で、再帰に色んな機能をpluggableに追加できるよ、というお話でした。もちろん、機能を追加しないでそのままYコンビネータに入力してただの再帰にも出来ます。いろいろ遊んでみましょう。

以下、作ってみた追加機能を他にもダラダラ挙げてみます。

その5。一部の再帰を勝手にリモートマシンで実行する自動分散実行化機能

天気予報とか大きな規模の計算は、ひとつの「プログラム」*3をたくさんのマシンを使って協調させて走らせます。「プログラム」の方ではマシンの間の通信とかどのマシンで動いているとかはあまり意識せずに書きたいものです。

PCでも一昔前には、SETI@homeとかUDとか、世界中の参加PCを使って計算をするようなプロジェクトもたくさんありました。そんなわけで、弾さんのllevalサーバを利用させてもらって、再帰の実行をリモートに分散させて実行する自動分散化機能を。

function distribute(env, ftext, cond, argstr2exp, retstr2val) {//自動分散実行化の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。
  var make_uri =  function(n) {
    var envtext = "";
    for (i in env) {
      envtext += env[i] + ";\n";
    }
    n = argstr2exp(n);
    return "http://api.dan.co.jp/lleval.cgi?c=callback&s="
           + encodeURIComponent(envtext+'print(('+ftext+')('+n+'));')
           + "&l=js";
  }
  var read_as_text = function(is) {
    var result = '';
    var reader = new java.io.BufferedReader
               (new java.io.InputStreamReader(is));
    var line = reader.readLine()
    while(line != null){
        result += line;
        line = reader.readLine();
    }
    reader.close();
    return result;
  }
  var f_at_lleval = function(n) {
    var callback = function(a) {
      if (a.status != 0) {
        throw 'Error in lleval: ' + a.status + ' : ' + a.stdout +' : ' + a.stderr;
      }
      return a.stdout;
    }
    var conn = new java.net.URL(make_uri(n)).openConnection();
    conn.connect();
    if (conn.getResponseCode() != 200) {
      throw 'Error! : ' + getResponseCode();
    }
    var resultout = eval(read_as_text(conn.getInputStream()));
    return retstr2val(resultout)
  }
  return function (f) {//これが「受け取ったfのフリをする関数(fの偽物)」
    return function(n){
      if (cond(n)) {
        return f_at_lleval(n);
      } else {
        return f(n);
      }
    };
  }
}

ブラウザだとクロスドメイン制約のせいでうまくいかないので、Rhinoで動かします。ブラウザで動かないのは残念ですが、Rhinoでなくても、また中身的にはJavaScriptでなくても通信が出来る普通の言語環境なら問題ないですしErlangとかならお茶の子さいさいでエレガントに書けると思います*4。

こんな感じで実行します。

hanoi = Y(wrap(F_for_hanoi, 
          distribute(
            [Y, F_for_hanoi, Hanoi, 'Hanoi.prototype.toString='+Hanoi.prototype.toString],//env:実行環境情報(リモートに送る)
            'Y(F_for_hanoi)',//ftext:リモートで実行する関数
            function(n){return n.x%2==0;}, //cond:偶数番目を弾さんサーバで実行。奇数はローカル実行
            function(n){return 'new Hanoi('+n.x+',"'+n.a+'","'+n.b+'","'+n.c+'")';},//argstr2exp:リモートに渡す引数値を送信できる形式に変換
            function(n){return n;}//retstr2val:リモートからの返却結果を値に変換(hanoiだと変換不要なので意味はない)
         )));
hanoi(new Hanoi(5,'A','B','C'));

その6。先読み山かけ先行実行(speculative evaluation:投機的実行) 機能

function gen_speculative(vent){//先読み山かけ先行実行の仕込み生成関数。「受け取ったfのフリをする関数(fの偽物)」を返す。
  return function (f) {
    var make_f_caller = function(n) {
      return function() {
        f(n);
      }
    }
    var executor = java.util.concurrent
      .Executors.newCachedThreadPool();//spawnは激遅だった
    return function(n) {
      var forecasts = vent(n);
      for (var i in forecasts) {
        executor.execute(make_f_caller(forecasts[i]));
      }
      return f(n);
    };
  }
}

必要になると思われる再帰を、先取りして実行しておく機能です。wikipedia:投機的実行を見てください。メモ化機能と組み合わせて使います。最近のCPUのようにコアがたくさんあるマシンだと速くなるかも知れません。または、自動分散実行化機能と組み合わせてもいいかも知れません。

というわけで、Haskellやろうぜ！(おまけ)

落ち着いてみてみると、再帰というのはじつは「関数を入力として受け取りその関数を使う」関数の、特殊な場合という事が解ります。たまたま(?)入力されてきたのが自分自身だった場合が再帰というわけです。実際のところ、Yコンビネータじゃなくて単なる再帰の方が速いので自分はプロダクションコードで実際に使った事はないです。でも、目の前の状況しか考えてないコードよりも、一般的な形に書いておいた方が、ものすごく可能性が広がるという事を実感できれば、お仕事にも意味があるかなぁと思います。

関数型言語では、この考え方が徹底していて、ライブラリなんかももの凄い汎用的にできてます。それは単に文化だけでなく、関数型言語のパワーのおかげでもあります。

例えば、上記の再帰への機能追加関数達ですが、構造が似ていますね。これもちゃんとした関数型言語プログラマなら汎用的な関数を用意してしまうでしょう(自分は全然ちゃんとしてないので気持ち悪さに耐えてしまいました)。関数型言語では、処理(関数)を普通に気軽に後から渡してやれるし、数学の関数の様に縦横無尽に組み合わせやすいので、コードのありがちな構造自体すらライブラリ化できてしまうのです。

例えば、Haskellではfibを多分ふつうはこんな感じに書きます。Haskellではここで使ってる関数はみんなデフォルトでimportも不要で使えます。

fibs = 0:1:(zipWith (+) fibs (tail fibs))
fib = (fibs !!)

イメージを伝えるために上記をJavaScriptに翻訳すると、

var fibs = cons(0, cons(1, zipWith(plus, fibs, fibs.tail)))
var fib = function(n){return at(n, fibs).head;}

こんな感じです。使ってる関数は、JavaScriptにはないので、それらも翻訳するとだいたいこんな感じです。

function cons(h,t) {
  return {head:h, tail:t};
}
function plus(a,b) {
  return a + b;
}
function zipWith(op, xs, ys) {
  if (xs.tail && ys.tail) {
    return cons(op(xs.head, ys.head), zipWith(op, xs.tail, ys.tail));
  } else {
    return cons(op(xs.head, ys.head), undefined);
  }
}
function at(n, xs) {
  if (n==0) {
    return xs.head;
  } else {
    return at(n-1, xs.tail);
  }
}

zipWithが構造自体をライブラリ化したものの例と言えると思います。何か同じ計算を沢山のデータに対して行う、というありがちなパターンのプログラムの構造を、関数としてライブラリ化してある訳です。JavaScriptは関数をファーストクラスが扱える(関数を関数のまま引数に渡したり出来る)ので、言語としては上記のように関数型のプログラミングも可能です。ただ、こういう使われ方を想定してないので、こういうライブラリを探して*5きてさらに実行時環境にも用意してやり、そう言うコーディングするあなたを変態と呼ぶ心無い人に耐えられればＯＫです。しかし、関数をそのように扱えない言語だと、こういうやり方をするために、かえっていろんな無駄な記述が必要になっり、トリッキーなテクニックが必要になってしまいます。

あと、JavaScirptの例ではfibsの所が関数じゃなくてただの値なのにfibs自身を参照していてエラーになってしまうと思います。Haskellでは、データ自体でも問題なく自己参照が出来ます。さらに、fibsは長さ無限ですが、Haskellは、プログラムの必要になった部分だけを必要になってから評価(実行)するのでノープロブレムです。

さらに、エントリの冒頭に書いたように、数学(主に基礎論系。)との対応付けもよくなされていて、何気ないライブラリが数学的に証明されているもの凄い汎用性とパワーを持っていたりします。超汎用的なライブラリをちょこちょこと組み合わせるだけで、どんどん高度なプログラムが出来ていきます。モジュールを組み合わせてさらにモジュールを作るようにプログラミングしていけば、プログラムの機能は、コードの規模にたいして、足し算ではなく、掛け算的に広がっていきます。上記のfibもずいぶん短く書けていますが、大きなプログラムになればなるほど差は倍々に広がっていきます。

この感覚というか習慣は、関数型言語を使う事で最もよく培われて最もよくパワーを発揮すると思いますが、JavaなりPHPなりでのコーディングにも必ず良い影響をもたらすと思います。目の前の状況しか考えてないコードよりも、一般的な形に書いておいた方が、ものすごく可能性が広がるという事自体は、どの言語でも同じだからです。そんなわけで、実用系関数型言語の極北(??)、Haskellの本を紹介しておきます。

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門

posted with amazlet at 09.04.17

青木峰郎
ソフトバンククリエイティブ
売り上げランキング: 68076

Amazon.co.jp で詳細を見る

WebにHaskellの情報は結構ありますが、玄人向けです。「やさしいHaskell入門(A Gentle Introduction to Haskell)」というドキュメントがありますが、これは「天才な人にはやさしい」という意味なので気を付けて下さい。ふつうの人には、この本がふつうの意味でやさしいくていい感じです。興味が湧いた人は、まずこの本を読む事をお勧めします。

偉そうな事を書きましたが、自分は真性のへなちょこなので、玄人がこのエントリを見たら炊飯ものだと思います*6。それでも、仲間が増えて欲しいという思いであえて恥をさらさせて貰います。

追記

Haskell版fibの定義で、当初カッコが抜けていたのを修正しました。(2009-04-24)

*1:オリジナルは名前空間汚染を回避していますが、ここでは気にしていません。あしからず。あと、本当はZコンビネータと言うのでしょうが、不動点演算子なら別によいのです

*2:ご存じでない方はググってください、すみません

*3:一本のソースという意味ではなくて、ひとつの目的のひとつのまとまりという意味で

*4:自分は使った事無いですが…

*5:または自分で書いて

*6:間違いにはツッコミを頂けたら幸いです

2009-04-17

おとうさんにもわかるYコンビネータ！(絵解き解説編)

先日YコンビネータのきしださんのYコンビネータのエントリが話題になっていました。

ずいぶん日にちが経ってしまいましたが、自分も、自分なりにYコンビネータのあたりを絵解きで整理してみたいと思います。きしださんのエントリタイトル*1に引っ掛けて、目標として、自分の父親(非プログラマ。その辺のおっさん)でも解る内容を目指します。

なぜ不動点演算子というのか、不動点だったらなぜ再帰なのか、この辺りも含めて、実感を持って納得できればいいなと思います。

きしださんのエントリのおさらい

本題の前に、きしださんのエントリをおさらいしておきます。

Yコンビネータはただのオモチャじゃないんだよ
関数だけで色んな事が出来る
- 条件分岐をする関数ってのもある。
- 再帰(ループ)を作れる関数もある。←これがYコンビネータ。
- 数値も関数で表現できる。
つまり、関数だけで、条件分岐も、再帰(ループ)も、数値も作れちゃう！！

って事が書いてありました。

普通のプログラミング言語では常識である、if文もfor文やwhile文も、仮引数以外の変数・変数代入も、果ては数値すらすべて使わずに、ただただ関数だけでそれらを「エミュレート」できちゃってます。関数というか、正確にはλという単純な文字列変換ルールだけでできちゃってます。
λSUGEEEEEEEEEEEEEEEEEEEEEE!!!!!!!!*2

きしださんのエントリの趣旨は、「λSUGEEEEEEEEEEEEEEEEEEEEEE!!!!!!!!」であって、Yコンビネータはその一部な訳ですが、そのお話の一部であるYコンビネータの所を、今回整理してみまず。絵が汚いのはご愛敬。

以下、本題。

関数ってのは、何かを入れたら、何かが出てくるモノだ

中学校で習いましたね。

関数に関数を入れたっていいじゃない

中学校では、関数に関数を入れるというのはやらなかったかも知れませんが、いいじゃないですか入れたって。

関数を入力とする関数のなかに、Yってのがある

通称Yと呼ばれるある関数があります。こいつは関数を入力として、関数を出力します*3。

Yから出力される関数の性質

このYが出力する関数(図では☆=Y(M))は、ある性質を持ちます。自分の元ネタであるYに入力した関数(図ではM)に入れると、また自分と同じ関数(図では☆=M(Y(M))=Y(M))が出てくるのです。Mからの出力である☆とMへの入力である☆とが同じという訳ですから、M(Y(M))=Y(M)と言う訳です。

Yから出力される関数の性質ーもういちどMに入れ直してみる

最初にMにY(M)を入力したときの出力はM(Y(M))ですね。それをもう一度Mに入れてます。すると出てくるのはM(M(Y(M)))と言う事になりますが、これもやはり同じく☆であり、Yから出てきたときの☆=Y(M)と同じです。つまり、M(M(Y(M)))=Y(M)と言う訳です。

Yから出力される関数の性質ー何度も何度もMに入れ直してみる

何遍やっても変わりませんね。M(M(M(M(M...M(Y(M)))...)))) = Y(M)です。Mにとって、Y(M)という入力は、変わらずにそのまま出てきてしまう特別な入力なのです。この特別な入力を不動点と言うらしいです。

…で？それと再帰／ループと何の関係があんの？

ですよねー。何回もMを適用(呼び出し)してるあたりがちょっと関係ありそうですけど。きしださんのエントリだと、ここが僕には解りずらかった。で、考えてみました。

もともと、再帰／ループがやりたかった

中学校で習った1次関数

$f(x) = 3x + 4$

は、 $\small f$ に $\small x$ を入力すると、 $\small 3x + 4$ を計算した結果が出力されます。

例えば、 $\small x$ として2を入力すると10が出力されます。

再帰というのは、関数が自分自身を使ってる事です。この関数 $\small f(x) = 3x + 4$ は再帰してません。でも例えば、それをちょっといじった、こんな関数にしてみます。

$f(x) = 3x + 4 + f(x-1)$

自分( $\small f$ )で自分( $\small f$ )を使っています。これが再帰です。

再帰する関数を図にしてみる

再帰する関数 $\small f(x) = 3x+4+f(x-1)$ を、ここまでと同様の絵にしてみます。

$\small 3x+4+f(x-1)$ の $\small x$ の所を入力として受け取って、?にそれを当てはめた結果が出力されます。

ちょっといじって、 $x$ じゃなくて $f$ の所を入力とする、別の関数 $F$ を作ってみる

ここで、 $\small x$ じゃなくてむしろ $\small f$ の所を入力として受け取るようにいじった、別の関数を作ってみます。

この関数は、関数を入力として受け取ります。そして、その関数を使う新しい関数を作って出力します。入力も出力も関数です。とくに再帰もしてないです。入力として関数を受け取ると、 $\small 3x+4+?(x-1)$ の $?$ の所にその関数を当てはめた結果が出力されます。

例えば、入力が $\small g(x)=2x$ という関数だったら、

$\small 3x+4+2(x-1)$ つまり $\small 5x+2$ という関数が出力されます。もちろん、この出力された関数は普通に使う事が出来る普通の関数です。例えば、1を入力したら7が出力されます。

この関数を $\small F$ と呼ぶ事にしましょう。

$F$ に $f$ を入力してみよう

$\small F$ は、関数を入力として受け取ります。ここで、もともとの関数 $\small f(x) = 3x+4+f(x-1)$ を入力してみましょう。

すると、出力されるのは、 $\small 3x+4+f(x-1)$ 。入力である $\small 3x+4+f(x-1)$ とまったく同じです。

関数 $\small F$ には、いろいろな関数を入力できますが、関数 $\small F$ にとって $\small f$ は特別な入力ですね。

$f$ は $F$ の不動点だ

$\small f$ は、そのままでも、 $\small F$ に入力した結果でも、まったく変わりません。このような特別な入力を、不動点というらしいです。
これを式で書くと、

$\LARGE f=F(f)$ (「 $\LARGE f$ は $\LARGE F$ の不動点である」と言っている式)

です。

$\small F$ の実体は $\small 3x+4+?(x-1)$ だったので、上記の式の右辺 $\small F(f)$ は $\small 3x+4+f(x-1)$ ( $\small ?$ に $\small f$ を当てはめた)です。

つまり、上の式は、

$\LARGE f=3x+4+f(x-1)$ (「 $\LARGE f$ は $\LARGE F$ の不動点である」と言っている式2)

と同じ事です。これは、上で $\small f$ の内容を決めたときの式とまったく同じです。 $\small f$ が、自分( $\small f$ )で自分( $\small f$ )を使っている＝再帰する関数であるという事を、式で書いたもの、そのものずばりです。

つまり、どういう事かというと、

「 $\LARGE f$ は $\LARGE F$ の不動点である」という事が、

「 $\LARGE f$ は再帰する関数である」という事と同じ！！*4。

という事です。

今の話は最初の方の図の下半分の例

$\small f$ や $\small F$ という具体例で考えてみた不動点ですが、これは、最初の方の図の下半分の例です。Mの例が $\small F$ 、☆の例が $\small f$ です。

実例を見てみた事で、下半分のリアリティが出たでしょうか。

じゃあ上半分は？

実例で見た説明を当てはめると、最初の方の図はこうなります。

Yと呼ばれるある関数は、入力された関数(例: $\small F$ )の不動点(例: $\small f$ )を出力します。不動点を出力するので、Yは、不動点演算子であるとか、Fixed point combinatorであるとかいうらしいです。Yの出力は不動点なので、Yに入力した関数(例: $\small F$ )にそれ(例: $\small f$ )を入力すると、そっくりそのままそれ(例: $\small f$ )が出力される、と言う訳です。

Yに入力するのは何でもいい訳じゃなくて、「関数を入力として受け取り、その関数を使う新しい関数を作って出力する関数(入力も出力も関数)」です(もちろん $\small F$ もそうなってました)。そうするとYから、そいつの「不動点である関数」＝「再帰する関数」が出力されてきて、関数だけで再帰が出来るという訳です。めでたしめでたし。

Yコンビネータは、使い道がない？

Yコンビネータの一番偉いところは、そのおかげで、関数(正確にはλという単純な文字列変換ルール)だけでプログラムがすべて表現できるという事だと思います。それによって、プログラミングに関するいろんな原理の研究に数学のスーパーパワーを使いやすくなります。数学のスーパーパワーを使うと、完全に正しいと保証されたプログラミングに関する技術が産み出せます。その辺のさわりを、きしださんが解説されています。

きしださんは、

結論をいえばYコンビネータには、なにかの処理を便利にする能力はない。関数であらゆる計算ができるということが示せれば、あとは用なしだ。理論の礎としてうまってしまえばいい。
http://d.hatena.ne.jp/nowokay/20090413#1239617061

といいます。たしかにYコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。

さあ、Yコンビネータ(不動点 演算子)を使おう！

意味がない事はないと思います。Yコンビネータとか不動点とかで出てくる考え方は、理論だけじゃなく、実際のプログラミングでも応用できたりもします。ちょっとそれを見てみましょう。

…つづく

というわけで、Haskellやろうぜ！(おまけ)

いきなりですが、Haskellの宣伝です。

ぬぬ、スタックオーバーフロー。
これは、式がそのまま評価されてしまうことに問題があるようです。そこで遅延評価するための変換をいれてみます。
http://d.hatena.ne.jp/nowokay/20090409#1239268405

ぬぬ、またしてもオーバーフロー
これは、boolで真の場合も偽の場合の式もその場で評価されてしまって無限ループになってしまうためで、やっぱり遅延評価しないといけません。
http://d.hatena.ne.jp/nowokay/20090409#1239268405

きしださんのエントリで、普通のプログラミング言語の規則である評価順番が小さな躓きポイントとして挙げられていました。ただでも込み入った事を考えているのに、こういった躓きポイントは痛いです。それに、それを回避するために、本当は「正しい」はずのコードをもう一捻りして書き換えてやらなくてはいけないのも、めんどくさいしすっきりしません。

でも、Haskellなら大丈夫。デフォルトで遅延評価だからです。必要なところを必要なだけ評価していくので、このような問題は起きません。単純に正しく書いておけば、きちんと動くプログラムになってくれます。

さらに、Yコンビネータというか不動点演算子をこんなにすっきり書く事が出来ます。

y(f) = f(y(f))

このコードは、上で書いた

$\LARGE f=F(f)$ (「 $\LARGE f$ は $\LARGE F$ の不動点である」と言っている式)

に対して、

$\LARGE f=Y(F)$ (「 $\LARGE f$ は $\LARGE Y$ に $\LARGE F$ を入力した結果である(上の最後の図の上半分)」と言ってる式)

を当てはめた式、

$\LARGE Y(F)=F(Y(F))$ (" $\LARGE f$ "を" $\LARGE Y(F)$ "に書き換えた式)

そのものです。大文字と小文字が違うだけで、プログラムとこの式はまったく同じですね。定義をそのまま正しく書いてやるだけで、ちゃんと動くプログラムになってます。評価順とか関係ないです。すごいですHaskell。

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門

posted with amazlet at 09.04.17

青木峰郎
ソフトバンククリエイティブ
売り上げランキング: 68076

Amazon.co.jp で詳細を見る

*1:何か元ネタがあるんでしょうか

*2:ちなみに、Smalltalkもif文やwhile/forなしの様ですね。Booleanのメソッド+クロージャ／クロージャのメソッド(?)+クロージャで実現しているようです。これはどういう算法なんでしょう?

*3:ざっくり言って、入力が関数で、出力も関数である関数をコンビネータと言います

*4:正確には、 $F$ への言及が無くなってるから、同じと言うより含意してる、といったところか

2009-03-30

トップはてなー愛用のベスト「人生、生活、料理」本・ツール Top23 まとめ

TopHatenarで購読者数またはブクマ数のいずれかでトップ100にランク入りしてる人達のエントリで、より多くのTopHatenarの人に取り上げられてるアイテムを集計しました。ただし、都合上、はてなダイアリーだけを対象にしてます。正確には、はてブでカテゴリが「生活・人生」に分類されているページを対象として、amazonへのリンクがはてブに抽出されている数をカウントしています。人数が同じ場合は、紹介回数で順序を付けています。

そのアイテムを取り上げているエントリへのリンクも付けました。

ほかのはてブカテゴリもデータを取ってあるので、それらも後でエントリにしたいと思っています。

★作成済みエントリ