gistfile1.md

テーマ「型」

６さいカンファレンスのレジュメ的な何か

自己紹介

はいはい、どうも、ちゅーんさんですよ。

日々C#でシャチクりながら暇を見てHaskellを嗜んでいるプログラマです。Haskellerとゆー奴ですね。 知らない人のために簡単に補足しておくと、Haskellととゆーのはプログラミングの一種で、 最近はやりの「関数型」というプログラミングのジャンルの筆頭みたいな奴です。 東京都内で「ゆるふわHaskell入門回」という、入門者向けの勉強会を主催してたりします。

前置き

さて、今日はHaskellの世界から、プログラミング全般に幅広く応用できる理論・・・というか、「考え方」のお話をしようかと思います。

プログラミングについて習ったり、ググったり、本を読んだりすると、アルゴリズム、言語の機能の使い方や裏ワザ、その応用例なんかは色々充実しているけど
ある程度大きなものを作るのにあたっての「体系的な設計方法」や「綺麗なプログラム」に関する資料は情報は漠然としていてしっくりと来ない人も多いのでは無いでしょうか。

実の所、そういったテクニックは半分は職人技です、才能と感と経験の世界です。
一方ではしっかりとした土台となる理論があって、経験をカバーする事ができる、という事でもあるのです（！）

と、ゆーわけで、今日のお題は「型のお話」張り切って行ってみましょー。

高階関数とクロージャ

さて、実践的な話に入る前に、ちょっと確認しておきたい事があります。この中で「高階関数」「クロージャ」わからないお！って人どのくらい居ます？ 多分手続きプログラムメインでやってる人は馴染みが無かったり、高度なテクニックという認識があるかもしれませんが、 関数プログラミングでは「高階関数」や「クロージャ」は基本的なテクニックです。みんな空気のようにこれらを使います。

今回は、得に何かターゲットの言語を選ぶわけでは無いので、適当に擬似言語を見繕ってみましょう。
defunというのが関数定義、varが変数宣言のための構文です。

defun fizzbuzz(arg){
  if(arg % 3 == 0) return "Fizz";
  if(arg % 5 == 0) return "Buzz";
  if(arg % 15 == 0) return "FizzBuzz";
  return toString(arg);
}

defun main(){
  for(i = 1 to 100){
    var str = fizzbuzz(i);
    print(str);
  }
}

。。。勘で読めますよね？ さて、この言語の特徴は、fizzbuzzのような「関数」も、変数に格納する事ができるという事です。イメージできますか？次の例を見て下さい、

defun dbl(arg){
  return arg * 2;
}

defun add2(arg){
  return arg + 2;
}

defun main(){
  var func = dbl;
  print(func(5)); // --=> 10

  func = add2;
  print(func(5)); // --=> 7
}

同じようにして、関数を引数に渡したり、、、

defun apply5(func){
  return func(5);
}

defun main(){
  print(apply5(dbl)); // --=> 10
  print(apply5(add2)); // --=> 7
}

関数の返り値を関数にしたりする事もできます。

defun getfunc(arg){
  if(arg) return dbl;
  return add2;
}

defun main(){
  var func = getfunc(true);
  print(func(5)); // --=> 10
  func = getfunc(false);
  print(func(5)); // --=> 7
}

このように、「関数を返えしたり」「関数を引数として受け取ったり」する関数の事を「高階関数」と言います。

さて、せっかく関数を返す事ができるのですから、関数を関数の中で作れれば捗りそうです。
そこで、値として関数を作るための「関数リテラル」を用意しました。

defun main(){
  var add100 = defun(x){
    return x + 100;
  };
  print(add100(30)); // --=> 130  
}

関数リテラル内では、その関数リテラルの記述されたスコープから参照できる変数を参照する事ができます。
このような機能を「クロージャ」と言います。

defun main(){
  var i = 100;
  var addi = defun(x){
    return i + x;
  };
  print(addi(30)); // --=> 130  
}

なんと、クロージャを使えば、例えば次のように「関数を作る高階関数」を作ることができるのです！

defun makeAdder(x){
  return defun(y){
    return x + y
  };
}

defun main(){
  add100 = makeAdder(100);
  add500 = makeAdder(500);
  print(add100(50)); // --=> 150
  print(add500(50)); // --=> 550
}

さて、これで「高階関数」「クロージャ」について解りましたか？ この擬似言語は、この説明のために作ったので、もう忘れてしまったOKですｗ

通常、このように関数がintやString等ののように「値」として使う事ができる事を、「関数が第一級（ファーストクラス）オブジェクトである」などと言います。

型の記法

さて、少し脇道に話がそれましたが、型に話を戻しましょう。 おそらく静的型付けの言語で皆さんが見慣れた「関数の型の引数と型の宣言の仕方」は次のようなものでしょう。

int f(int x, int y)

しかし、これからここでは、次のように書くことにします。

f : (int, int) -> int

例えば、数値を取って文字列に変換して返すtoString関数は次のように宣言できますね。

toString : int -> string

では、次の型はどういう意味でしょう？ちょっと考えてみて下さい。

g : int -> int -> int

そうです、intを取って、int -> intという関数を返す高階函数でした。 では次は？

h : (int -> int) -> int

そうですね、int -> intという関数を引数にとり、intを返す高階関数です。 もし、皆さんが良く知っているプログラミング言語の記法で高階関数を表記しようとすると、例えばC#の場合、次のようになります。

Func<int, int> g(int x)
int h(Func<int, int> f)

ちょっと解りづらいですね(´・ω・｀)
もし、型がややこしい関数を宣言する必要が出てきたら、このように書き換えて考えてみると捗りますよん。

型で設計する

さあ、いよいよ本題です。 これから「図書館システム」について考えてみましょう、ある図書館のシステムでは本のデータを扱っており、様々な本の情報を取得する関数が用意されています。

getIndex : Book -> int
getName : Book -> string
getSummary : Book -> string

こうして見ると、本のデータは「Index」「Name」「Summary」といった情報を保持している事が解りますね。
さらに、図書館にある沢山の本を保持しておくためのリスト、「BookList」というコレクション型がある事が解っているとします。 さて、我々の仕事は、この「本」の情報を様々な情報を元に絞り込みを行う仕組みを開発することです。

例えば、Indexを元に絞り込みたいのであれば・・・

findIndex : (int, BookList) -> BookList

NameやSummaryの検索は次のようになりますね。

findName : (string, BookList) -> BookList
findSummary : (string, BookList) -> BookList

ところで、このような要望が増えていくたびに新たな検索関数を追加していくのは大変だと思いませんか？
今回のように単純にインデックスや名前で検索かけるだけなら良いかもしれませんが、 実際に似た動きをする関数を沢山作らされるシチュエーションはよくある事です。

３つの検索関数をよく見てみましょう。

findIndex   : (int   , BookList) -> BookList　　　　
findName    : (string, BookList) -> BookList　　　　
findSummary : (string, BookList) -> BookList　　　　

どれもほとんど同じ形をしています。なんとか効率良くできないでしょうか？

まず、引数のBookListは検索する「元の」書籍のリストです、intやStringは本を検索するためのキーになります。 これらの関数は「なんらかの条件を満たした本だけ抽出する」という意味で、全ての同じ処理になります。 なんとかひとつに纏められないでしょうか？

「なんらかの条件を満たす」というのはどういう事でしょうか？「条件を満たしているか否か」はなんという型を使って表しますか？

そうです、booleanです。BookListの中の各要素、つまりBook型がある条件を満たすかどうか確認したいのだから、例えば、次のような関数を使って判定できそうです。

indexIs1 : Book -> boolean
indexIs2 : Book -> boolean
indexIs3 : Book -> boolean

...

indexIs100 : Book -> boolean

...

indexIs1000 : Book -> boolean

勿論、全ての書籍について、こんなふうに関数を作るなんてナンセンスです。 しかし、良く考えてみて下さい、我々には高階関数という武器があります。

indexIs : int -> Book -> boolean

同じようにして、NameやSummaryに文字列が含まれているか確認する関数は次のような型を持つはずです。

inName : string -> Book -> boolean
inSummary : string-> Book -> boolean

これらの高階関数に値を適用すると、全ての型を Book -> boolean に揃える事ができます。

indexIs(100) : Book -> boolean
inName("Tune") : Book -> boolean
inSummary("Haskell") : Book -> boolean

そして検索関数を、これらの関数を引数に取る高階関数に書き換える事で、一つの関数にする事ができるのです！ ちょっとややこしい形になりましたが、わかりますか？「Book -> boolean」という関数と、BookListを取ると、引数の関数の結果がTrueになる書籍だけが、 BookListから絞り込まれるという寸法です。

findBooks : ((Book -> boolean), BookList) -> BookList

これなら、先ほどの「indexIs」「inName」「inSummary」を使って簡単に目的の本を絞り込む事ができますし、関数リテラルを使えば新たな関数を作らなくても、 たった一回の関数呼び出しであらゆる条件で検索処理を行う事ができます！！すばらしい！

さらに、次のように高階関数に変更してやる事によって、条件を固定して複数のBookListに対する同じ検索処理を簡単に行う事ができるようになります。 (余談ですが、このような変換を「カリー化」といいます。)

findBooks : (Book -> boolean) -> BookList -> BookList

まとめ

ところで、高階関数とクロージャの説明を終えてから今まで、ずっと型について話をしていましたが、ここまで一度も「実装」や「具体的な動作」の話をしていない事に気がついたでしょうか？ にも関わらず、型の短い記述だけで、皆さんは各関数の作りや使い方、その動作をイメージする事ができたんじゃないかと思います。

これはつまり、今のこのカンファレンスの間で、皆さんはこの図書館システムについての設計を頭に入れる事ができたという事です。 しかも、難しいと言われている「クロージャ」や「高階関数」を駆使しているのにもかかわらず！

このように、適切にプログラムを設計する事によって、型は雄弁にそのプログラムについて説明しはじめます。 この性質は、プログラムの規模が大きく複雑になればなるほど心強い味方になるでしょう。

型の歴史ちょびっと

いかがでしょうか、「型なんてちょっとしたニアミス防止だよ」と思っていた人も、型の凄さの一端を知っていいただけたのでは無いかと思われます。 「型」は昔から計算機科学者にとって興味の対象となっており、原型となる単純型付きラムダ計算が生まれたのはは1940年代・・・なんと、コンピュータが真空管だった頃まで遡る事ができます。

その後も研究は続けられており、「定理証明系」と呼ばれる分野では無くてはならない物になっています。 これは、プログラミングの型と、数学の論理学が実はまったく同じ形をしているという驚くべき事実（カリーハワード対応といいます）を利用して、数学の証明をコンピュータを使って支援したり、あるいは自動化してしまおうという研究です。

そしてさらに驚くべきことに、この事を利用すると「ある関数が仕様を１００％満たしている」という事をコンパイル時に「証明」する事で、文字通り「バグの無いプログラム」を実現可能にするのです！(もちろん、そんな簡単な話ではありませんが・・・(^_^;)

さて、今日の６さいカンファレンスはこれで終わりになりますが、最後に、今日の話で型に興味を持ってくださった人は・・・

http://www.haskell.org/platform/

ぜひぜひ、Haskellやりましょ☆ 以上、ご清聴ありあとやしたーm(_ _)m