lazy-talk-code

lazy_talk_code.py

"""
$ qipython -i ~/projects/tmp/lazy_talk_code.py 
Python 3.4.6 (default, Feb 16 2017, 15:43:12) 
Type "copyright", "credits" or "license" for more information.

IPython 5.3.0 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

IPython profile: daisy

In [1]: %time lazy_fib(100)()
CPU times: user 1.9 ms, sys: 6.88 ms, total: 8.78 ms
Wall time: 7.93 ms
Out[1]: 354224848179261915075

In [2]: %time lazy_fib(100)()
CPU times: user 53 µs, sys: 4 µs, total: 57 µs
Wall time: 69.1 µs
Out[2]: 354224848179261915075
"""
from abc import ABCMeta, abstractmethod
import operator as op


class Thunk(metaclass=ABCMeta):
    @abstractmethod
    def __call__(self):
        raise NotImplementedError()


def evaluate(expr):
    while isinstance(expr, Thunk):
        expr = expr()
    return expr


class CellThunk(Thunk):
    not_evaluated = object()

    def __init__(self, code, *args, **kwargs):
        self.code = code
        self.args = args
        self.kwargs = kwargs
        self.value = self.not_evaluated

    def __call__(self):
        if self.value is self.not_evaluated:
            self.value = self.code(
                *(evaluate(arg) for arg in self.args),
                **{
                    key: evaluate(value)
                    for key, value in self.kwargs.items()
                }
            )
            del self.code
            del self.args
            del self.kwargs

        return self.value


thunk_cache = {}


def memoized_thunk(code, *args, **kwargs):
    key = (code, args, frozenset(kwargs.items()))
    try:
        thunk = thunk_cache[key]
    except KeyError:
        thunk = CellThunk(code, *args, **kwargs)
        thunk_cache[key] = thunk

    return thunk


def lazy_fib(n):
    if n <= 2:
        return 1

    return memoized_thunk(
        op.add,
        memoized_thunk(lazy_fib, n - 1),
        memoized_thunk(lazy_fib, n - 2),
    )