ハッカーの系譜(11)スタートアップ養成する「Yコンビネーター」 (7) 養成機関の名前は「Yコンビネーター」

牧野武文

May 30, 2017 08:15
by 牧野武文

養成機関の名前は

グレアムのスタートアップ養成機関は、2005年4月にローンチした。グレアムは、この養成機関に「Yコンビネーター」という名前をつけた。これは日本語では不動点演算子と呼ばれるもので、これ以上ないというほどうってつけのネーミングだった。

プログラミングには「リカーシブルコール(再帰呼び出し)」という技法がある。授業で、ハノイの塔の解法プログラムや階乗の計算、フィボナッチ数を求める計算などの例題で教わったはずだ。

もし、読者がプログラミン技法に馴染みがないのであれば、今回の記事はあまりためにならないかもしれない。しかし、ポイントは再帰呼び出しというのは、ある関数が自分自身を呼び出すプログラミング技法のことだ。計算に長い時間がかかるという欠点があるが、代わりに不動点演算子(Yコンビネーター)を使うと、同じことが爆速でおこなえるということだ。

つまり、グレアムとしては、「スタートアップ経験者がスタートアップを養成する」再帰呼び出しの事業をおこなうのだが、長い時間はかけず、爆速で養成するという意味を「Yコンビネーター」という名前にもたせた。ある程度のプログラム経験者であれば、ニヤリと笑みを浮かべてしまうネーミングなのだ。

再帰呼び出しを使ったプログラムは、例えば、フィボナッチ数を求めるプログラムであれば次のようになる。
 
fibo(x)
if x<2
 return 1;
else
 return fibo(x-1)+fibo(x-2);

 
この関数は、中にも同じ関数があるため、fibo(x)を計算するためにはfibo(x-1)とfibo(x-2)を先に計算しなければならない。fibo(x-1)とfibo(x-2)を計算するには、fibo((x-1)-1)とfibo((x-1)-2)、さらにはfibo((x-2)-1)とfibo((x-2)-2)を計算するというように、無限に入れ子関数の螺旋階段を降りていかなければならない。終わるのは、xが2未満になって、停止条件である1が返されたときだ。すると、そこを底として、今まで降りてきた螺旋階段を逆に登っていくことになる。

フィボナッチ数列というのは、数例の前ふたつの和が次の項になるというものなので、このプログラムで計算することができる。このプログラムを、xが1から1つずつ増えていくループの中に入れてやれば、0、1、1、2、3、5、8、13、21、34、55、89、144、233…と求めていくことができる(本来は0周りの処理が必要だが、煩雑になるので省略した)。

ところがこの再帰呼び出しという技法は、現実にはあまり使われない。とくに業務用のプログラムでは再帰呼び出しが必要な計算というのは少なく、多くは数学的な問題の解法に必要となるだけだ。

フィボナッチ数列を計算するというのは、株式や為替相場の予測プログラムなどで使いそうだが、実際に再帰呼び出しを使って、フィボナッチ数列をご丁寧に計算するプログラムを書くプログラマーはいないだろう。なぜなら、再帰呼び出しは、入れ子の関数を掘り下げていくので、膨大な計算時間がかかり、メモリーリソースも大量に消費するからだ。

フィボナッチ数列を計算するプログラムを本体とは別につくり、暇なときに計算させて、その結果をテーブルに保存しておき、本体のプログラムはそのテーブルを参照するようにした方が賢い。

計算効率が悪い原因

再帰呼び出しの計算効率が悪い原因は明らかだ。同じ計算を何回もしなければならないからだ。先ほどのフィボナッチ数列を求めるプログラムをxを1から100までループで回すとき、x=5のときはfibo(4)とfibo(3)を計算しなければならない。しかし、このfibo(4)を求めるにはfibo(3)とfibo(2)を計算しなければならない。ここまでで、すでにfibo(3)を2度計算している。これが、効率を悪くしている原因だ。

もし、fibo(1)を計算したときにその結果をメモリーに保存し、fibo(2)を計算したときにメモリーに保存し…ということをしていき、それを次の計算で再利用できるとしたら、計算効率は格段に向上するだろう。

しかし、一般的な再帰呼び出し式のプログラムでは、計算結果をメモしておき、それを再利用して計算効率をあげるという命令を書くことができない。再帰呼び出しは、計算の考え方がそのままプログラムになっていて人間にとっては理解しやすいが、効率のいいコーディングではないのだ。

超効率よくおこなえるプログラミング技法

そこで登場するのがYコンビーネーターだ。Yコンビネーターは不動点演算子と呼ばれるもののひとつ。

関数には、値を入力しても出力が変わらない不動点と呼ばれる特異点を持つものがある。例えば、f(x)=2x+1という関数に、-1を入力するとf(-1)=2*(-1)+1=-1という数値が出力され、入力値と出力値が同じになる。座標で言えば、(-1、-1)の不動点を持つことになる。

この不動点がどのような数学的な意味を持つかは、数学の教科書を参照していただきたいが、ある関数が不動点をもつかどうかで、その関数の性質がいろいろとわかってくるのだという。

この不動点を利用すると、再帰呼び出しと同じ演算をすることができるため、優れたプログラマーは再帰呼び出しではなく、不動点演算子を使うことの方が多い。関数に入力できるのは数値だけではなく、別の関数を入力してもかまわない。数値の不動点と同じように、ある関数を入力して、同じ関数が出力される関数が不動店演算子と呼ばれる。

「ある関数を入力して、同じ関数が出力される演算子って、いったいなんの役に立つのか」と思われると思うが、これが再帰呼び出しの1ステップ分と同じ働きをするのだ。

再帰呼び出しはいったん計算を始めたら、何重もの再帰呼び出しが停止条件にあたって戻ってくるまでなにもできないが、不動点演算子を使うと、再帰呼び出しと同じ演算を1ステップずつ進めていくことができる点が異なる。
つまり、不動点演算子を使ったプログラムであれば、何度も同じ計算をしなければならないfibo(3)、fibo(2)などの計算結果をメモリーに保存しておき、次に必用になったときに再利用するというコードを挟みこむことができる。そのため、再帰呼び出し計算を爆速でおこなえるのだ。

つまり、ここが重要なのだが、Yコンビネーターとは再帰呼び出し計算を、超効率よくおこなえるプログラミング技法なのだ。

グレアムが、自分の養成機関にYコンビネーターという名前をつけた理由は明らかだ。グレアムの養成機関は、グレアムというスタートアップ経験者が次世代のスタートアップ企業を養成するという再帰呼び出し的な事業だ。しかも、その再帰呼び出しは、従来とはまったく違って、超効率よくおこなわれるのだ。Yコンビネーターは、スタートアップを再生産する関数なのだ。
 
(8回に続く)




学校サイトに銃器売買の広告!? 中国ブラックハットSEO技術

August 14, 2017 08:00

by 牧野武文

安徽省合肥市の11の学校の公式サイトに、銃器売買、代理出産、替え玉受験、セックスドラッグなどの違法広告を表示させたとして、安徽省蘆江県検察院は、張家恒、陳安、潘志剛の3人を、計算機情報システム違法制御の罪で起訴をしたと検察日報が報じた。 怪しい公告はでない仕組み サイト運営者にとっては、埋め込み広告…