計算論

分かった気になれそうでなれないカリー化についての理解メモ (兼 『計算論』読書メモ )

More than 1 year has passed since last update.

序文という名の駄文

最近、Qiitaで小説っぽいことを書いているのは、知っている人は知っているかと思いますが、その中で「カリー化について取り上げて欲しい」という要望がありました。

自分で考えてみると、「カリー化が何をすることかはわかるけれど、それが実際何をしているのかはよくわかっていないなー」ということがあったので、最近『計算論 計算可能性とラムダ計算』の、そのあたりの部分を写経していたら、ちょうどそのあたりについて書いてあったので、勉強メモとしてここに書き残しておきます。

ちなみに、ちゃんとした話を読みたい場合は、上の本を購入されることを勧めます。(たぶん、数学用語とか適当なので。編集リクエストとマサカリを期待します)

先に

こういうエントリを見た方が早い

カリー化とは

ざっくり言ってしまうと、多変数関数(複数の引数を取る関数)を、一次変数関数で(一つの引数しか返さない関数の連鎖)で表現してしまうこと

そこでラムダ

関数とは、ある集合(例としてN)に対して、ある集合の点(この場合もN)に対応させるものであるっぽい……。

といってもピンとこないので、要するに、例えば自然数の集合Jに対して二倍すると、偶数の集合が取れたりする。この集合をEと呼べば、(x2):J → Eという写像になる。で、これを実数全体の集合をRとすれば、基本的には、なんらかの関数はf: R → Rとなる。

もう少し、具体化した関数の形を考えよう。何かの集合をとって、何かの写像を返すという意味で、g: X → Yという関数が考えられる。このとき、g(x) = tと書くことができる。

このとき、わざわざg: X → Yを定義してあとに、g(x) = tとするのは、非常に冗長である。そこで、xをとったときに、ある集合(例えばN)のtに属するという関数を定義できるようなSyntaxがあれば便利だろう。

そこで、上のようなg(x) = tg = λx ∈ X.tと書けたら便利だろう。このような1変数関数、すなわち引数を一つだけ取る関数に対する記法をλ記号と呼ぶ、らしい。

でも関数ってたくさんの引数をとるじゃん

さて、そこで、疑問になるのは、λ記法というのは、先ほども行ったように1変数関数に対するものである、ということだ。しかし、現実的には多変数関数、つまり複数の引数を取る関数は現実的に存在する。例えば、3変数関数としてf(x, y, z) = x + y * 2という関数を考えることは簡単だ。

なんどもいうように、λ記法というのは、1変数関数に対するものだ(と、理解している。マサカリ歓迎)。とすると、λ記法自体を拡張して、多変数ラムダということを考えることもできる(数学モデルとプログラミングモデルは違うものだか、現実的にラムダ的な記法を使う場合は、多変数関数としてのラムダが定義できる)。

しかし、ポイントになるのは、1変数関数のラムダさえあれば、多変数関数は表現できる、という点にある。

λ記法の特徴は、λにしたものは関数として扱えることができるということだ。

先ほどf: R → Rという話をしたが、これとは別に、(R → R)を作る関数それ自体を指し示す用法を定義しよう。これが便利なのは、まず一つに「引数に対して関数が取れる」ということと、もう一つは「関数を返す関数」が定義できるということがある。

まず、f(x, y, z)xの値だけを固定し、yを変化させる。このとき、fx: N → (N → N)、つまりNという集合に対して、「NからNに写像する関数」を作るようにすればよい(この辺り、用法が曖昧なので修正が必要)。

例えば、fxであるならば fx = λy ∈ N.fx,yとできるわけだが、このfy,zλy ∈ N.λz ∈ N.f(x, y ,z)とすることができる。

さて、このようなfxは少々冗長ではある。3変数あるのだから、3回関数を返してやればよい。そこでf*: N → (N → (N → N)))を定義してやる。すると、先ほどのf(x, y, z)f* = λx ∈ N.λy ∈ N.λz ∈ N.f(x, y, z)と置き換えることができる。

これはf*(3)(5)(7) = f(3, 5, 7)と等価になる。

今回は3変数を使ったが、どうやら多変数関数にも利用ができる。つまり、定義を拡張し:

f*(x1)(x2)(x3)...(xn) = f(x1, x2, x3 ... xn)

は、形式が違うけれど、同じ対応をさせることができる。これを同一視すれば、1変数関数のλ記法で、多変数関数を表現できることができる。これを、カリー化と呼ぶとのこと。

わかりにくいからコードで説明しろや

最初に貼ったリンクをみればわかるように、基本的には匿名関数の入れ子を作ればいいという話。そこで、『アンダースタンディング・コンピュテーション』の例をPythonで書き直して見よう。なぜPythonかというと、少しだけわかりやすいから。

plus = lambda x, y: x + y
plus(1, 2) # => 3

plusc = lambda x: lambda y: x + y
plusc(1)(2)

上を見てみればわかるように、xの引数を渡すことによって、lambda y: x + yという関数を渡すという構造になっている。もちろん、この中のxはクロージャとしてスコープを持っているので大丈夫ということになる。

Haskellの事例

ここで想定できるのはHaskellの事例である。もちろん、上記の議論とは等価ではないが、手助けにはなる。

例えば、Haskellについては、以下のような関数を書くことが可能である。公平のために、下のコードは『関数型プログラミング入門 ―Haskellで学ぶ原理と技法―』による

plus :: (Integer, Integer) -> Integer
plus (x, y) = x + y

plusc :: Integer -> (Integer -> Integer)
plusc x y = x + y

この違いは、一見わからないが、実際になんらかの変数にBindすると、その違いが明確になる。

let plus_sample = plus (x, 1) 
-- Error!! => Not in scope: `y'
let plusc_sample = plusc 3
plusc_sample 9
-- => 12

どうやらHaskellの関数は標準でカリー化されているみたいなのだけれど、上記の場合も一緒で、暴力的に言ってしまえば、plusc 3 yとなった関数が、plusc_sampleにバインドされるようになるということだと思う。

ちなみに、Haskellの場合だと、上のような挙動のというのは、下と一緒である:

plusc x y
(plusc x) y 
plusc x $ y

部分適用との区別

雑に言ってしまうと、部分適用は上記のような「1変数関数のラムダによって多変数関数が表現できる」ということとは関係がない。あくまでも「変数の引数の一部を決定する」というところが焦点になるものだ。

上記の例でいうと、plusc x yの関数自体は「カリー化」されていると言えるのだが、では、それをplusc_sample = plusc 3とした場合は、部分適用となる、という風に理解すると良い筈。

じゃあ、クロージャはどうなるの

読者の課題とします(著者が途中で調べるのに疲れて放置するための便利メソッド)