lambda関数だけのPython世界で四則演算

お察しかもしれないがラムダ計算についての話である。

最近あったPyConで気になるチュートリアルがあった：

www.youtube.com

このブログでも何回か話題にしたことがあるDavid Beazleyが教えているチュートリアルで、

Pythonのlambdaキーワードで作る無名関数だけで、ラムダ計算の世界をのぞいてみよう

という趣旨。

かなり面白かったので、備忘録的にメモってみる＆内容を少しだけ発展させて自然数のわり算まで実装してみる。

ルール

Pythonのlambda関数しかない世界。

なのでできるのはlambda関数の作成と呼び出しのみ。

さらにいうと単一引数のみ。

例えばこんな感じ：

X = lambda x: x
Y = lambda y: y(X)
Z = lambda x: lambda y: lambda z: z(x)(y)

Z関数ではcurryingにより、単一引数ながらも複数の値を入力として受け取る関数が定義できることがわかる。記述がややこしくなるのを避けるため、今後このようなcurryingされている関数のことを「ある関数がn個の引数をとる」「ある関数の第一引数、第二引数」などという表現をする。

便宜上トップレベルでは変数への代入をしているが、あくまで名前付けのためのみ許される。

言い換えると、変数を値の式ですべて書き直すことが可能である必要がある。

このルールでどうすれば計算を表現することができるか。

真偽値

まずはTRUE/FALSE：

TRUE = lambda x: lambda y: x
FALSE = lambda x: lambda y: y

この世界では

• 「真」は「引数xとyを順番に受け取り、xを返す関数」
• 「偽」は「引数xとyを順番に受け取り、yを返す関数」

に対応づけられる。

そうするとNOT, AND, ORも以下のように定義できる：

NOT = lambda x: x(FALSE)(TRUE)
AND = lambda x: lambda y: x(y)(x)
OR = lambda x: lambda y: x(x)(y)

データ構造

複数のデータをひとつのオブジェクトとしてまとめて、単一引数に渡せるようにしたい。

LispでもおなじみのCONSセルの出番である：

CONS = lambda x: lambda y: lambda f: f(x)(y)
CAR = lambda x: x(TRUE)
CDR = lambda x: x(FALSE)

CONSは引数二つをとって、ある関数を返す。その関数にTRUEを与えるとCONSの第一引数、FALSEを与えると第二引数を返す。

CARとCDRはその関数を受け取ってTRUE/FALSEを与えるだけ。

数字

ここから数字と対応づけられる関数が何か、を考えていく。話を簡単にするために０からはじまる自然数のみ。

考えていく、と言ったがそれは嘘で、昔から知られているチャーチ数を使うだけ。

ZERO = lambda f: lambda x: x
ONE = lambda f: lambda x: f(x)
TWO = lambda f: lambda x: f(f(x))

数字はすべて二つの引数をとる関数で、「第二引数に第一引数をn回適用した結果を返す関数」を自然数nに対応させる。

任意の自然数を作れるように、「ある数より１大きい数を作る関数」SUCCを定義する：

SUCC = lambda n: lambda f: lambda x: f(n(f)(x))

fが適用される回数が一回上がる。

SUCCを使えばたし算ができる：

ADD = lambda n: lambda m: n(SUCC)(m)

この関数は実は少し単純化できる：

ADD = lambda n: n(SUCC)

というのも、この世界だとすべてのものが関数なので、以下の等式が（ほとんどの場合）あてはまる：

lambda x: X(x) = X

（先行評価・遅延評価の関連であてはまらないケースについては後述する）

なので

lambda n: lambda m: n(SUCC)(m) = lambda n: n(SUCC)

となる。

たし算を使ってかけ算を定義：

MUL = lambda n: lambda m: n(ADD(m))(ZERO)

次にひき算を定義したいのだが、そのためには「一個前の数」を返すPRED関数が必要になる。

ここで以前定義したCONSを使う：

PRED = (
  lambda n: 
    CDR
      (n(lambda x: CONS(SUCC(CAR(x)))(CAR(x)))
        (CONS(ZERO)(ZERO))))

（横幅が足りなくなってきたので()内では複数行に分割できるというPython構文を利用している）

この定義は：

自然数n-1は(0, 0), (1, 0), (2, 1), (3, 2), (4, 3), ...という無限列のn番目のCONSセルのCDR

という考察がベースとなっている。ちなみにこの定義だとZEROのPREDはZEROのままであることに注意。

PREDがあればSUBは簡単：

SUB = lambda n: lambda m: m(PRED)(n)

さらに比較用の関数：

ISZERO = lambda n: n(lambda _: FALSE)(TRUE)
LE = lambda n: lambda m: ISZERO(SUB(n)(m))
EQ = lambda n: lambda m: AND(LE(n)(m))(LE(m)(n))
LT = lambda n: lambda m: AND(LE(n)(m))(NOT(LE(m)(n)))

さて、残る四則演算はわり算のみとなったのだが・・・

考え方としては

nからmを繰り返し引いていって、残った数がmより小さくなるまでの回数

を返す関数を作りたい。この「繰り返し」を実装するために再帰ができるようにしたい。

再帰

まずはルール違反な例を挙げる：

BADFACT1 = lambda n: ISZERO(n)(ONE)(MUL(n)(BADFACT1(PRED(n))))
BADFACT2 = lambda n: ISZERO(n)(ONE)(lambda _: MUL(n)(BADFACT2(PRED(n)))(_))

BADFACT1はそもそも無限再帰になってしまいうまくいかない。ISZERO(n)(m)(p)でIF分岐しているのだが、nもmもpもすべて評価してからnの値によってmかpかを選ぶ、という評価戦略になっているのが理由だ。

無限再帰を避けるため、BADFACT2では

lambda x: X(x) = X

があてはまらないケースを利用している。関数の中に入れることでXの評価を遅延させることができる。最終的にすべて評価されれば値は同じになるはずだが、これだと無限再帰を起こさない。

しかし、このようにBADFACT2の定義の中でBADFACT2という名前を利用するのはルール違反である。

この定義を「名前なしで」書こうとするとやはり無限ループが起きて、式の長さが無限になってしまう。

ルール内で再帰を実現するためにはYコンビネータを使う：

Y = (
  lambda f: 
    (lambda x: lambda _: f(x(x))(_))
    (lambda x: lambda _: f(x(x))(_)))

Yコンビネータに関しては解説できるほど理解が進んでいないのであらかた割愛するが、一点だけ。

普通はYコンビネータといえばlambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))のような形で出てくるのだが、やはり遅延評価して無限再帰を回避するために追加でlambda _: ...というステップを追加している。

Yコンビネータを使えばFactorialやFibonacciがルール内で以下のように書ける：

FACT = (
  Y
    (lambda f: lambda n: 
      ISZERO(n)
        (ONE)
        (lambda _: MUL(n)(f(PRED(n)))(_))))

FIB = (
  Y
    (lambda f: lambda n: 
      LE(n)(TWO)
        (ONE)
        (lambda _: ADD
          (f(PRED(n)))
          (f(PRED(PRED(n))))(_))))

わり算

これでピースは全て揃った。あとは書くだけ：

DIV = (
  lambda n: lambda m: 
    Y
      (lambda f: lambda x: 
        LT(CAR(x))(m)
          (CDR(x))
          (lambda _: f(CONS(SUB(CAR(x))(m))(SUCC(CDR(x))))(_)))
      (CONS(n)(ZERO)))

考え方としては前述の通り

nからmを繰り返し引いていって、残った数がmより小さくなるまでの回数

を返す関数。初期値がnとZEROのCONSセル(p, k)に対して再帰的に(p-m, k+1)に変えていき 、pがm未満になった時点でkを返す。

普通のPythonで書くならこんなロジック：

def divide(n, m):
  def f(p, k):
    return k if p < m else f(p-m, k+1)
  return f(n, 0)

使ってみる

まずは他にいくつか数字を定義しておく：

THREE = ADD(ONE)(TWO)
FIVE = ADD(TWO)(THREE)
TEN = ADD(FIVE)(FIVE)
HUNDRED = MUL(TEN)(TEN)

この世界の数字に対応するPythonの数字をプリントする関数を定義：

def show(n):
    print(n(lambda x: x+1)(0))

この関数はラムダ計算世界の結果を、我々が理解できるように出力するためだけに使う（演算には使われていない）。のでルール外の存在。

この関数を使ってFACT, FIB, DIVを使った計算結果を出力してみる：

>>> show(FACT(FIVE))
120

>>> show(FIB(TEN))
55

>>> show(DIV(HUNDRED)(THREE))
33

成功。