今日の料理

f:id:nisemono_san:20160513135542j:plain

博多のソウルフードです。

出版社/メーカー: サンポー食品
メディア: 食品&飲料
この商品を含むブログを見る

概要

ラムダ計算を学習する上において、コンビネーターというものが登場する。これは、変数が全て束縛変数となっているラムダ項で定義できるものを指す。その中で特に重要なものとして、SKIコンビネーターが存在している。このSKIだけで、基本的なラムダ計算を実装することができる。そこで、今回そのSKIコンビネーターを勉強するためのライブラリを作るのに失敗したので、その経緯を説明する。

難解関数型プログラミング言語

プログラミング言語界隈には、難解プログラミング言語というものが存在する。この難解プログラミング言語は、実用を目指したものではなく、遊びか、あるいは理論的な側面に基づいたプログラミング言語である。その中で有名でかつ、実装しやすいものとして、Brainfuckが挙げられる。非常に簡単に実装できるので、実装してみるのもいいと思う(普段使っている言語なら1時間もかからないだろう)。

さて、このような難解プログラミング言語の一つに、Unlambdaと、Lazy Kが存在している。難解プログラミングの中ではいわゆる「関数型プログラミング言語」向きのアプローチを利用している。それはどういうことかというと、両者ともラムダ計算論などで言及されるSKIコンビネーターをメインに置いているのである。

SKIコンビネーターとは何か

この文章を読むより

のあたりか、『アンダースタンディングコンピュテーション ―単純な機械から不可能なプログラムまで』を読んでおけば十分だと思う。それでも、この文章を読みたい奇特な人のために解説するならば、SKIコンビネーターについて、Pythonでその挙動を再現してみよう:

S = lambda x: lambda y: lambda z: x(z)(y(z))
K = lambda x: lambda y: x
I = lambda x: x

ぱっと見てみればわかるように、Iは引数をそのまま返す振るまいをし、Kは引数を2回渡されたら、1回目を渡す。そして一番ややこしいのはSで、これは3回目の引数を2番目に適用したものを、1回目の引数で適用したものに適用する。日本語が下手なのでややこしいけど、コードを見て理解して欲しい。

さて、上のコードを見たときに、ふと気がつくはずだ。これはどうして、下ではないのかと。

NS = lambda x, y, z: x(z)(y(z))
NK = lambda x, y: x

これ自体には二つの答えかたがある。

まず一つに、実装と説明の問題で、引数が揃ってはじめて適用される関数は扱いづらいということ。例えば、これからIコンビネーターはSKKで表現できることを説明しようと思うのだが、これを全部の引数を揃えてやるのは、利便性がすこし減る。もう一つの答えかたとしては、理論上、n引数の関数は1引数の関数だけで表現できることが知られている。これは過去のブログでも説明した通りである。

さて、SKIコンビネーターの原始的な実装ができたところで、こいつを使ってみよう。先に、IはSKKで表現できるという話をしたけれども、歴史の経緯上、単位元のコンビネーターは自明として定義しておいたほうが分かりやすいということでもあるらしい。そのような経緯はともかくとして、実際にそのように振るまうかどうかを確認してみよう。

I = lambda x: x
SKK = S(K)(K)
assert SKK("foo") == I("foo")

Pythonではassertは、式がTrueで保証されていることを示しているため、これは同一であることを示している。

SKIコンビネーターで拡張する

関数合成

と、ざっくりとSKIコンビネーターの話をしたわけだが、これだけだと、一体何が面白いのか、さっぱりわからないところだ。SKIコンビネーターの真骨頂は、SKIだけで、様々な機能が作れるという点にある。

例えば、関数合成はS(KS)Kとして表現することができる。実際にやってみよう。

SKSK = S(K(S))(K)
assert SKSK(lambda x: x - 3)(lambda x: x * 2)(10) == 17

しかし、結果だけ見せられても、何でこのようになるのか、釈然としないだろう。そこで、一つ一つの挙動をおいかけてみよう。便宜上、与えられた変数を小文字にして、.でくぎるような表記を採用する。

S(KS)K.xyz 
=>(KS).x(K.x).yz # Sによって、KSとKに対して、xが配布される
=>S(K.x).yz      # KSは、Sとxの引数を取る。ここで、KはSを採用する
=>K.xzyz         # Sは3つの引数、(K.x), y, zを取る。このとき、(K.x)とyに対してzをあたえる
=>xyz            # Kは2つの引数、xとzを取る。このとき、xが採用される
=>x(y(z))        # 整理すればこのようになる

以上、関数合成が定義できる。このようなコンビネーターの簡約を「Weak reduction」と呼ぶ。さて、SKIによって見事に関数合成ができた。これをあとで再利用できるように、Bと定義しておこう。

無限ループ

さて、さらにこのSKIコンビネーターから、無限ループするような挙動を作りだすことが可能だ。これはSII(SII)によって定義ができる。

SII = S(I)(I)
SII(SII)

ここで、RecursionErrorになれば成功である。何が起きているのかを、上記に会わせて説明すれば:

SII(SII)
=> I(SII)I(SII) # Sが3番目に渡されたSIIを2番目と3番目のIに配る
=> SII(I(SII))  # IにSIIが渡されたので、SIIをそのまま返す
=> SII(SII)     # カッコの中のIも、SIIをそのまま返す

というわけで、元に戻ってきてしまうわけだ!!

チャーチ数

さらに、SKIコンビネーターでチャーチ数を表現することを考えてみよう。チャーチ数とは、乱暴に言うならば、ペアノ自然数を下のようにラムダで表現したものだということができる。詳しくは過去のブログを参考にしてほしい。

LZERO = lambda f: lambda x: x
LONE  = lambda f: lambda x: f(x)
LTWO  = lambda f: lambda x: f(f(x))

このとき、fの数だけ、数が増えていくと考えることができる。実際に、そのような関数を忍ばせてみよう:

LTWO(lambda x: x + 1)(0)

そうすれば、無事2が出力された筈である。さて、このような数を増やしていくような関数を、乱暴に言えば、後続者関数と呼び(正確な定義はS(x) = x + 1となるような関数)、通称Succとも呼ばれる。このような関数を同様にSKIコンビネーターでも作ってみることにする。

先に結論を伸べるならば、SKIコンビネーターにおけるチャーチ数とは以下の通りになる:

0 = KI
1 = I
2 = SBI
3 = SBSBI

ここで重要なのは、後続者関数らしき役割を果しているのがSBというものである。Bは先に出てきた関数合成のコンビネーターである。

Succ = lambda x: x + 1
print(K(I)(Succ)(0))                 # => 0
print((I)(Succ)(0))                  # => 1
print(S(B)(I)(Succ)(0))              # => 2
print(S(B)(S(B)(I))(Succ)(0))        # => 3
print(S(B)(S(B)(S(B)(I)))(Succ)(0))  # => 4

といったように、ちゃんと数が増えていっていることがわかる。

SKIコンビネーターを学ぶためのライブラリ

しかし、ここで問題がある。というのは、このような関数が実際にどのような挙動をしているのか、わかりにくいという点である。

で、ここでやっとPythonの自作ライブラリであるskiskiの紹介なのであった。ちなみに、Python 3標準という名目で作っているので、Python 2系だと動かない。たぶんpip install skiskiでインストールできるはずだ。

from skiski import S, K, I
sii = S(I).dot(I)
print(sii.dot(sii).w()) # => (S I I (S I I))
print(sii.dot(sii).w().w().w()) => (S I I (S I I))

インターフェイスとしては、S, K, I というクラスがそれぞれ定義されていて、dotのメソッドで引数を渡していく形となっている。wは、「weak reduction」の略となっている。これにより、ある程度自動的に簡約をしてくれるので、SKIコンビネーターの動きを理解するのに便利な筈である。

また、特殊なクラスとして、Vというのも定義されている。これはVariableの意味で、なんらかの変数を簡易的に挟みたいときに使う。例えば、先ほどのチャーチ数に関してはどうなのか気になるところ。そこでVariableの出番なのである。

from skiski import S, B, I, V
print(S(B).dot(I).dot(V("Succ")).w().dot(V("0")))
# => (B Succ Succ 0) 
print(S(B).dot(S(B).dot(I)).dot(V("Succ")).w().dot(V("0")))
# => (B Succ (B Succ Succ) 0)

これにより、SBIは、実はBx(Bxx)0の形になっているが故に、このxxの二重適用によって、数が増加していくことがわかる。

失敗点

とりあえず、学習用ということで割り切って実装しているのだけれども、幾つものおしい点がある。まず、とりあえず動くということを目指したために、Weak reductionする際に、その簡約が一足飛びになってしまっているというところである。例えば、上記のチャーチ数を作るところにおいて、手で書くとするならば:

SBIxy
=> BxIxy # 第3引数であるところのxをそれぞれ配布する
=> Bxxy  # Iは引数をそのまま返すのでxになる
=> x(x(y))

という風に展開していったほうが、遥かに教育的である。また、ラムダ式版のコードと比較してもらえればわかるように:

S(B)(I)(Succ)(0)
S(B).dot(I).dot(V("Succ")).w().dot(V("0"))

一度Weak reductionを挟まないと、余分な引数を受けとることができない。これは致命傷なので、もしかしたら、引数が満たされた状態でさらにdotを受けとった場合は、Weak reductionを発動させるなどの処置をしようかとも考えているが、それはどちらかというと実用面の問題なので、現状としてはwを使ったほうが、どういう挙動か置いやすいかもしれないということで、いったん保留している。

まとめ: SKIコンビネーターの学びにくさ

さて、実際のところ、SKIコンビネーターを日本語で学ぶのは非常に面倒であり、それに相応する文献が見つからないので、学ぶさいに、難儀するのが実感である。かろうじて、洋書には、以下の本があり、これはSKIコンビネーターとラムダ計算を持ちいながら勉強するスタイルとなっており、また英語にしては平坦に書かれているので、自分のような頭の悪い人間にもすんなりと入ってきた。が、Kindleでも7000円と高いのがネックではあるが。

Lambda-Calculus and Combinators: An Introduction

とにかく、UnlambdaとLazy Kを書くためにはSKIコンビネーターのスタイルを学ばなければならない。この文章と、このライブラリが、その手助けになったなら幸いである。