CleanやHaskellといった純粋関数プログラミング言語は生産性が高いとあちこちに書いてあったので、いろいろと勉強しているところだ。 勉強していると、Pythonなどの最近の命令型(imperative)あるいは手続き型(procedural)といわれる言語でもかなり似たような記述ができそうな気がした(さすがにJavaやCとかだと無理そうだが)。そこで、Pythonを使って関数プログラミングの醍醐味をどこまで味わえるかチャレンジしてみることにした。あまり関数プログラミングに馴染みのない人にも理解しやすく説明できるように心がけるつもりだ(というか私もあまり馴染みがない)。

純粋関数プログラミング言語では、遅延評価を行えることが特徴となっている。遅延評価とは、すごく簡単に言ってしまうと、必要になるまで式の評価や文の実行をしないことだ。たとえば、無限に続く数列(数値のリスト)を生成する関数を考えてみよう。Pythonで書こうとすると次のようになるが、実際にはこの関数が値を返すことはない。

def nums():
	result = []
	n = 0
	while True: # このループを抜け出せない
		result.append(n)
		n += 1
	return result # 実際はこの文に到達せず、この関数は値を何一つ返せない

for n in nums():
	if n >= 5:
		break
	print n

幸いPythonにはジェネレータがあるので、関数nums()を次のように書くことができる。

def nums():
	n = 0
	while True:
		yield n
		n += 1

このようにジェネレータを使うと、ある程度遅延評価を行うことができる。 しかし、ジェネレータを直接使うのは、ちょっと都合が悪い場合がある。次の要素を先読みしたい場合などである。 そこで、Pythonのリストデータ型ではなく一方向リストを使ったConsのリスト導入することにする。 ConsはLispで有名な次のようなデータ構造だ。CleanやHaskellでリストといえば、このデータ構造を指す。

    cons            cons         nil
+-----+-----+   +-----+-----+   +---+
|value|next |   |value|next |   |   |
|  *  |  *--+-->|  *  |  *--+-->|   |
+--+--+-----+   +--+--+-----+   +---+
   |               |
   v               v
+------+       +------+
|value0|       |value1|
+------+       +------+

Pythonのリストと混同しないように、便宜上、上記のデータ構造をCleanやHaskellに於いてもConsと呼ぶことにする。 このデータ構造、図を見てわかるように先読みをすることはできる。ただし、左側のノードが右側のノードを参照するため、右側のノードが確定しなければ左側のノードを作成することができない。これだと、最後の要素が決まるまで先頭の要素を返せないので、たとえば無限に続く数列をConsで表すことができず遅延評価にも役立たない。 そこで、次のノードを参照しようとしたときにそのノード値を決定するような怠惰なConsを導入することにしよう。次のようなクラス構成とリストとなる。

Consデータ構造を表すクラス図

__all__ = ["Cons"]

class Cons(object):
    def __init__(self):
        pass

    def isNil(self):
        return False

class NilCons(Cons):
    def __init__(self):
        Cons.__init__(self)

    def isNil(self):
        return True

nilObj = NilCons()

# 前方参照や相互参照があるスタティックメソッドのスマートな書き方があれば誰か教えて

@staticmethod
def nil():
    return nilObj

Cons.nil =  nil


class StrictCons(Cons):
    def __init__(self, value, next=Cons.nil()):
        Cons.__init__(self)
        self._value = value
        self._next = next

    def value(self):
        return self._value

    def next(self):
        return self._next

class LazyCons(StrictCons):
    def __init__(self, value, next):
        StrictCons.__init__(self, value, next)

    def next(self):
        c = (self._next)()
        self._next = lambda : c # 次回呼ばれたときも同じ値を返す
        return c


@staticmethod
def cons(value, next=Cons.nil()):
    return StrictCons(value, next)

Cons.cons = cons

@staticmethod
def lazyCons(value, expr=lambda : Cons.nil):
    return LazyCons(value, expr)

Cons.lazyCons = lazyCons

def _toCons(seq):
    try:
        v = seq.next()
        c = Cons.lazyCons(v, lambda : _toCons(seq))
        return c
    except StopIteration, e:
        return Cons.nil()

@staticmethod
def toCons(seq):
    return _toCons(seq)

Cons.toCons = toCons

メソッドCons.lazyCons()やメソッドLazyCons.next()に注目してほしい。メソッドLazyCons.next()は、Consの次のノードが必要になった時点でそのノードを生成し返却するという振る舞いとなる。このように、ジェネレータ以外にも、クロージャ(あるいは関数、ラムダ式)によっても遅延評価を実現できる。

上記のコードには、Pythonのリスト(正確にはイテレータまたはジェネレータ)をConsに変換する関数Cons.toCons()が含まれているので、次のようなコードで動作を確認できる。関数infinite()は無限に現在時刻を生成するジェネレータなので普通に考えるとConsに変換できないが、上記のLazyConsのおかげでConsに変換できる。下記のプログラムでは、実際は先頭のConsのノードしか生成されない。

from cons import Cons

def infinite():
    import time
    while True:
        t = time.localtime()
        print time.strftime("%H:%M:%S", t)
        yield t

list = Cons.toCons(infinite())

続いて次のコードを追加すると、Consはトータルで2つ生成される。

list = list.next()

以上で、遅延評価を行うために、Pythonジェネレータとクロージャが使えること、エンドレスのデータを表すデータ構造としてのConsの準備ができた。 次回は、これらを使って関数プログラミングらしい実装をしてみる。