techlunch1.md

!SLIDE

YCombinator

!SLIDE

YCombinatorとは何か

!SLIDE

ベンチャーキャピタル

YコンビネータLLC（Y Combinator LLC）は、カリフォルニア州マウンテンビューのベンチャーキャピタルである。 主にスタートアップ企業に対し投資している。 2005年にポール・グレアム、ロバート・T・モリス、トリヴァー・ブラックウェル、ジェシカ・リヴィングストンにより設立された。

!SLIDE ではなく

!SLIDE

不動点コンビネータ

今回はこっちの話です

型無しラムダ計算においてよく知られた（そしておそらく最もシンプルな）不動点コンビネータはYコンビネータと呼ばれる。 これはハスケル・カリーによって発見されたもので、次のように定義される。

Y = (λf . (λx . f (x x)) (λx . f (x x)))

!SLIDE

不動点コンビネータの話

!SLIDE

定義

• 関数を引数に取って関数を返す高階関数Fを考えてみる
• Fにある関数gを適用すると同じgが返る
• つまりF(g) = gであるときgはFの不動点であるという
• 関数Fを引数に取って不動点gを返す関数を不動点コンビネータという

!SLIDE

ラムダ計算における実装

!SLIDE 不動点コンビネータを実装する方法はいくつかある

!SLIDE

Yコンビネータ

Y = λf. (λx. f (x x)) (λx. f (x x))

• ハスケル・カリーによって発見されたもの
• 名前渡し評価じゃないと使えない

!SLIDE

Zコンビネータ

Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))

• 値渡し評価でも使えるようにη変換したもの

!SLIDE

チューリングコンビネータ

Θ = (λx. λy. (y (x x y))) (λx. λy. (y (x x y)))
Θ = (λx. λy. (y (λz. x x y z))) (λx. λy. (y (λz. x x y z)))

• アラン・チューリングによって発見されたもの

!SLIDE

わからなかったこと

• なぜZは正格評価でも動くのか
• YやZが型付きラムダ計算で実装できないのは何故か