Stackless Pythonで関数呼び出しの深さ制限を突破する

PythonでLISPっぽい何かを作ってみた - ラシウラでは、evalメソッドではfuncオブジェクト内でも再帰的に呼び出されるため、例中のfactでも引数を100程度にしてしまうと、"RuntimeError: maximum recursion depth exceeded"が発生してしまいます。

再帰にしないよう、eval(やそれを呼び出してる部分)のコード自体を書き換えることも可能ですが、それをやるとコードが複雑になります。

そこで、Stackless Pythonを使って、なるべく元のコードのままで、深さ制限をはずしてみることにします。

• http://www.stackless.com/

Stackless Python自体は、自動的には深さ制限が外れません。stacklessモジュールを使うことで、関数呼び出しをフラットにすることができます。

元コードでの変更部分はScopeクラスのevalのみで、以下のようなcall経由で呼び出すようにするだけです

class Scope(Atom):
    ...
    def eval(self, obj):
        return call(self._eval, obj)
    def _eval(self, obj):
        if isinstance(obj, Symbol): return self.get(obj.name)
        if isinstance(obj, Cons):
            func = self.eval(obj.head)
            return func.call(obj.tail, self)
        return obj

このcallは以下のようなになります。stackless pythonのtaskletを使う実装です

import stackless
def call(f, *args, **kargs):
    ch = stackless.channel()
    stackless.tasklet(lambda:ch.send(f(*args,**kargs)))()
    return ch.receive()

これによって、(fact 100)でも(fact 1000)でも実行可能になりました。

軽量でないthreadでは

このtaskletはstackless pythonの特徴である軽量スレッド呼び出しで、以下のような標準ライブラリのthreadを使った呼び出しと等価です

from thread import start_new_thread
from Queue import Queue
def call(f, *args, **kargs):
    ch = Queue()
    start_new_thread(lambda:ch.put(f(*args,**kargs)), ())
    return ch.get()

再帰段数以上に厳しいthread数制限があるので、この実装では呼び出し深さ問題解決にはなりません。深さが低い場合には、このcallでも同様に稼動します。

上のcall実装はマルチスレッドコードであるけれど、呼び出し側ではスレッドを作ってすぐにch.getで待ち状態に入っていて、スレッド側もch.putの後即終了するため、平行で動くコード部分は存在しない実装になってます。普通に以下のcall実装と同じ呼び出し順になります。

def call(f, *args, **kargs):
    return f(*args, **kargs)

以下のように、上記二つをミックスすることで、深さ制限を標準より少し緩めることは可能です。

import threading
from thread import start_new_thread
from Queue import Queue
reccount = threading.local()
def call(f, *args, **kargs):
    if hasattr(reccount, "count"): reccount.count += 1
    else: reccount.count = 1
    try:
        if reccount.count > 100:
            ch = Queue()
            start_new_thread(lambda:ch.put(f(*args,**kargs)), ())
            return ch.get()
        else:
            return f(*args, **kargs)
        pass
    finally:
        reccount.count -= 1
        pass
    pass

この実装であれば、(fact 1000)程度は実行可能です

put it together

try:
    # for stackless-python
    import stackless
    def call(f, *args, **kargs):
        ch = stackless.channel()
        stackless.tasklet(lambda:ch.send(f(*args,**kargs)))()
        return ch.receive()
    pass
except:
    # for standard python
    import threading
    from thread import start_new_thread
    from Queue import Queue
    reccount = threading.local()
    def call(f, *args, **kargs):
        if hasattr(reccount, "count"): reccount.count += 1
        else: reccount.count = 1
        try:
            if reccount.count > 100:
                ch = Queue()
                start_new_thread(lambda:ch.put(f(*args,**kargs)), ())
                return ch.get()
            else:
                return f(*args, **kargs)
            pass
        finally:
            reccount.count -= 1
            pass
        pass
    pass

Python2.5ならdecoratorにしてもいいかも

def rec(f):
    def wrapper(*args, **kargs):
        return call(f, *args, **kargs)
    return wrapper

class Scope(Atom):
    ...
    @rec
    def eval(self, obj):
        if isinstance(obj, Symbol): return self.get(obj.name)
        if isinstance(obj, Cons):
            func = self.eval(obj.head)
            return func.call(obj.tail, self)
        return obj