関数プログラミングのアプローチ (8)

Thunk

前回、モンテカルロ法のプログラムを関数的に書き直すことに成功しました。モンテカルロ法を用いた考察はこれで終わりです。次回以降は別のテーマを立てて、それを元にさらに考察を深めていきます。
次のテーマに移る前に、LazyListについてもう少し詳しく見ておきたいと思います。

class LazyList:
    def __init__ (self, fun):
        self.undef = True
        self.fun = fun
    def __next__ (self):
        if self.undef:
            self.value = self.fun()
            self.undef = False
        return self.value

def next (x):
    return x.__next__()

このオブジェクトを使ったときは、self.fun()がリストの先頭の要素とリストの残りの部分の２つの値を返すことを前提としていました。しかし、オブジェクトの定義自体は、self.fun()がどのような値を返すかということについては、特に制限を設けていないことが分かります。
例えば、次のコードを考えてみてください。

x = LazyList(lambda: 1 + 2)

このコードは next(x)を実行すると遅延リストではなく 3 を返します。これは、1 + 2という計算の呼出を、next()が呼ばれるまで遅らせていると考えることができます。このようなデータ構造を一般的にThunkと呼びます。上のLazyListをThunkという名前に書き換えたものを、下に掲載します。（ついでに、コードを改良して、インスタンス変数を１つ減らしています。）

class Thunk:
    def __init__ (self, fun):
        self.fun = fun
    def __get__ (self):
        if self.fun:
            self.value = self.fun()
            self.fun = False
        return self.value

def get (x):
    return x.__get__()

Thunkを用いると、call-by-need（必要呼び）という関数呼び出しを実現することができます。次のコードは、ifを関数として定義したものです。if_call_by_value()が通常の関数呼び出しを使ったもので、if_call_by_need()がThunkを使ったものです。

def if_call_by_value (cond, t, f):
    if cond:
        return t
    else:
        return f

def if_call_by_need (cond, t, f):
    if cond:
        return get(t)
    else:
        return get(f)

ここで、次のように loop()という無限ループをする関数を用意して、これを先ほど作ったif関数に適用してみます。

def loop ():
    while (True):
        pass

if_call_by_value(1 == 1, 'ok', loop())
if_call_by_need(1 == 1, Thunk(lambda: 'ok'), Thunk(loop))

if_call_by_value()の方は無限ループになってしまいますが、if_call_by_need()の方はloop()は呼び出されることなく関数が結果を返します。
このように、Thunkを使うことで、Thunkオブジェクトを作成するオーバーヘッドを支払って、不要な計算を省いたり、計算のタイミングを遅らせたりすることができるのです。そして、この機能は、関数的なプログラミングを行う上で、非常に重要な役割を果たすのです。

参考文献

これまでの説明に関する参考文献をまとめておきます。
モンテカルロ法のプログラムはSICPの例題にあった問題を参考にしています。第3章には、命令的なプログラムの例と関数的なプログラムの例がschemeを用いて説明されています。また、遅延リストやThunkについても、第3章で説明されています。

疑似乱数生成器の実装には、xorshiftアルゴリズムを用いています。これは、高速・省メモリ・シンプルな実装で比較的質のよい乱数を生成するアルゴリズムです。

参照透明性の概念の説明には、Wikipediaの説明を引用しています。

プログラミング言語 Clean についての説明、および、第3回のスコープルールによる変数の再利用については、Clean Language Reportに見ることができます。