普段使っているプログラミング言語。使う分には特に来にすることは無いと思うのですが、しかし、いったいどこまでシンプルに形式化することができるのでしょうか。そこでPythonのlambdaという構文を紹介し、これを使うだけで、どれだけ複雑な表現ができるか試していこうと思います。ちなみに、要求されるPythonのレベル自体は初級ですが、ある程度プログラミングの経験がある方が聞かれると、理解が深まる内容になるかと想定されます。

このトークによって、コンピュータサイエンスにおける一つの知見が得られ、それに少しでも興味持ってもらえることを期待しています。特に、単純な規則によって複雑な規則が生みだされることによって、シンプルに考えることの重要性や、あるいは一つのアプローチの仕方のインスピレーションが生まれること、また単純な実務に直結する内容ではなく、理論を学ぶことによって、より深い理解が生まれることを期待しています。

# Hello, Lambda World. Pythonを使っていると、「関数の宣言」を使わずにプログラミングすることは殆どないかと思います。Pythonで関数を宣言することは、素朴にやれば下のようにすることができます。 def hoge(n): return n このとき、Pythonの`lambda`を使えば`hoge = lambda x: x`とすることができます。`lambda`の目的は、一つには「関数それ自体」と、「関数の名前」を分離することによって、関数それ自体を現すことができることです。これを利用した関数として、`map`や`filter`などがあります。例えば、偶数を取得する場合、次のように使うことができます。 list(filter(lambda x: x % 2 == 0, range(0, 10))) ちょっと覚えると便利な`lambda`ですが、実はこの`lambda`だけを使うことによって、様々な規則を作り出すことが可能になります。 # 簡単なラムダ入門 もちろん、コンピューターサイエンスにおけるラムダと、いわばPythonにおける`lambda`は、厳密には違うものです。ですが、多くの部分を似せて書くことはできます。 例えば、関数には複数の引数が取れることがわかっています。しかし、実際のところ、任意の数の引数は、一引数の関数にすることができます。これをカリー化といいます。具体的にコードに直すと、次のようにすることができます: no_curry = lambda x, y: x + y curry = lambda x: lambda y: x + y assert no_curry(1, 2) == curry(1)(2) 以下、このセッションでは、`lambda`を利用するとき、この見地に基づき、`lambda`は1つの引数だけを取るものとして利用していきます。 # ラムダによる自然数、真偽値、IFの実装 ラムダだけによって、如何なる表現ができるのかについて説明します。基本的なところでは、自然数の構成、真偽値、IFの実装になるでしょう。先にコードを紹介すると、以下の通りになります。 ZERO = lambda f: lambda x: x ONE = lambda f: lambda x: f(x) TWO = lambda f: lambda x: f(f(x)) THREE = lambda f: lambda x: f(f(f(x))) # Pair PAIR = lambda x: lambda y: lambda f: f(x)(y) LEFT = lambda p: p(lambda x: lambda y: x) RIGHT = lambda p: p(lambda x: lambda y: y) # Calc INC = lambda n: lambda p: lambda x: p(n(p)(x)) SLIDE = lambda p: PAIR(RIGHT(p))(INC(RIGHT(p))) DEC = lambda n: LEFT(n(SLIDE)(PAIR(ZERO)(ZERO))) TRUE = lambda x: lambda y: x FALSE = lambda x: lambda y: y # Syntax OLD_IF = lambda f: lambda x: lambda y: f(x)(y) IF = lambda f: f IS_ZERO = lambda n: n(lambda x: FALSE)(TRUE) このように、ラムダによって、表現することが可能です。これらは実際に動くのです。 # SKIコンビネータを導入する このラムダに対して制限を入れます。その制限とは、三つの規則を持つ項の組み合わせだけを使うということです。この三つの規則というのが、他ならぬS, K, Iというコンビネーターのことです。コードに直すと次のようになるでしょう: S = lambda x: lambda y: lambda z: x(z)(y(z)) K = lambda x: lambda y: x I = lambda x: x さて、先程のラムダでのリストと比較すると、ひどくすくなく、不安を覚えます。実のところ、 ここで Iコンビネータを定義していますが、これはもっと言うならば、S(K)(K)で表現できますので、実際に必要なのは、SKの二つのみなのです!! # SKIコンビネーターを使って表現する 本当にこれだけの規則で、様々な表現をすることは可能なのでしょうか。驚くべきことに、SKIコンビネーターの表現力というのは豊かなものです。実際、SKIのみで、関数合成を行なう関数を定義することが可能です: SKSK = S(K(S))(K) assert SKSK(lambda x: x - 3)(lambda x: x * 2)(10) == 17 そして、この関数合成を使うことによって、自然数の表現も同様に行なうことができます: 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コンビネータは多数の可能性があるのです! # 可能性としてのSKIコンビネーター このようなSKIコンビネーターを基礎として持つ難解プログラミング言語として、Umlambdaや、Lazy Kがあります。もし、この発表で、これらの言語についてある程度「なるほど、こういうことだっだのね」と思うようになって頂ければ幸いです。 # 参考文献 ## [『アンダースタンディング コンピュテーション――単純な機械から不可能なプログラムまで』][1] 今回の発表の元ネタとも言うべき本です。残念なことに、SKIコンビネータについては詳しい利用法が書いてないことと、コードがRubyで書かれていることを除けば、ラムダ計算を実装というアプローチから見た場合の導入の本として、非常にわかりやすく書かれているかと思われます。上記の概要で興味を持たれた方は先に購入すると、理解が深まるでしょう。 ## [『素数夜曲―女王陛下のLISP』][2] SKIコンビネータについて、日本語の文献の中では拡張されたB, C, Fコンビネータまで解説されており、触りを学ぶには十分かと思われます。ただし、こちらは大方がLisp(Scheme)と整数論を広範囲に渡ってくりいろげてあるので、SKIのことだけを期待すると、思わぬ肩すかしをくらいます [1]: https://www.oreilly.co.jp/books/9784873116976/ [2]: https://pycon.jp/2016/ja/proposals/76/www.amazon.co.jp/dp/4486019245