ハッカーの系譜(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回に続く)




地図サービスが悪用される!? 住所とピンのズレは裏世界の入り口

October 23, 2017 08:00

by 牧野武文

中国で最も多くの人が使っている百度地図に、不思議なPOI(Point of Interest)、いわゆるピンが大量に登録されている。ピンの位置と、説明に記載されている住所がまったくかけ離れているのだ。法制日報の記者が、この不思議なPOI地点に足を運んで取材をしてみると、そこは上海の裏社会に繋がってい…

こっそり仮想通貨をマイニングする侵入者たち

October 20, 2017 08:00

by Zeljka Zorz

仮想通貨を渇望しながら、購入やマイニングなどにお金を払いたくないハッカーたちは、ユーザーのウォレットやコンピューター、人気のウェブサイト、そしてパブリッククラウドコンピューティングー環境を利用して、仮想通貨を手に入れようとしている。 マイニングのソフトウェア・マルウェアは、すっかり周知となった厄介者…

IoTアダルトグッズからわかる「BLE通信のセキュリティ問題」

October 18, 2017 08:00

by 江添 佳代子

ペネトレーションテストとセキュリティサービスの企業組織体「Pentest Partners」の研究者が先日、IoTのアダルトグッズの脆弱性に関する研究結果をブログで発表した。人々の注目を集めやすいグッズの話題だったためか、それは単純に面白いセキュリティニュースとして一般メディアでも取り上げられている…

自動で犯人を見つけて警察に通報する中国の監視カメラシステム

October 16, 2017 08:00

by 牧野武文

米国のテレビドラマ『24』に登場するCTU(Counter Terrorist Unit=テロ対策ユニット)は、街頭の監視カメラに侵入し、テロリストの姿をいったん補足すると、次々と別のカメラを使って追尾をしていくシーンがある。広東省の深圳を始めとする各都市で、このような監視カメラ追尾システムの試験運…