Adding memoized functions

appengine/findit/libs/math/functions.py

Index: appengine/findit/libs/math/functions.py
diff --git a/appengine/findit/libs/math/functions.py b/appengine/findit/libs/math/functions.py
new file mode 100644
index 0000000000000000000000000000000000000000..9684929a7e7e9f8a0cafebffa6e64cc1ac17274d
--- /dev/null
+++ b/appengine/findit/libs/math/functions.py
@@ -0,0 +1,58 @@
+# Copyright 2016 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+
+class Function(object):
+  """Base class for mathematical functions.
+
+  The ``callable`` interface is sufficient for when you only ever need to
+  invoke a function. But many times we want to have more information about
+  the function, such as getting its domain or range or knowing whether
+  it's sparse. In addition, we often want to adjust the computational
+  representation of functions (e.g., adding memoization). So this class
+  provides a base class for functions supporting all these sorts of
+  operations in addition to being callable.
+  """
+  def __init__(self, f):
+    self._f = f
+
+  def __call__(self, x):
+    return self._f(x)
+
+  def map(self, g):
+    """Return a new function that applies ``g`` after ``self``.
+
+    Args:
+      g (callable): the function to post-compose.
+
+    Returns:
+      An object of the same type as ``self`` which computes ``lambda x:
+      g(self(x))``. N.B., although mathematically we have the equivalence:
+      ``SomeFunction(f).map(g) == SomeFunction(lambda x: g(f(x)))``;
+      operationally the left- and right-hand sides may differ. For
+      example, with the ``MemoizedFunction`` class, the left-hand side
+      will memoize the intermediate ``f(x)`` values whereas the right-hand
+      side will not. If that's not desired, be sure to call ``Unmemoize``
+      (or similar type coercions) before mapping.
+    """
+    return self.__class__(lambda x: g(self(x)))
+
+
+class MemoizedFunction(Function):

[stgao, 2016/12/05 19:30:56]

Do we want the memoization work across different instances of this class?

In this implementation, it seems that the cached computation results is
available in the same instance of this class, but not in anther instance.
It depends on the real usage to decide whether this is what we expect.

[wrengr, 2016/12/05 21:23:51]

Storing the memos with the instance is fine for our purposes. The ultimate
design (see https://codereview.chromium.org/2517383005/) is that we have an
object for the loglinear model itself with some methods mapping X to functions
from Y to whatever. We want to memoize both the X to function map, and the Y to
whatever maps. With one exception, we don't really pass these functions around,
we just call them. (The one exception is when computing expectations, since we
want to compute the expectation of one of these methods.
https://codereview.chromium.org/2544493004/)

The benefit of storing the memos with the instance is that it makes it easy for
us to clear the memos, which is helpful when training the loglinear model since
(a) we want to memoize things, but (b) the memos are invalidated whenever the
weights change.

+  """A function which memoizes its value for all arguments."""
+  def __init__(self, f):
+    super(MemoizedFunction, self).__init__(f)
+    self._memos = {}
+
+  def _ClearMemos(self):
+    """Discard all memoized results of this function."""
+    self._memos = {}
+
+  def __call__(self, x):

[stgao, 2016/12/05 19:30:56]

Here, we support one parameter only. Do the usecases have only one input
paramter?

[wrengr, 2016/12/05 21:23:52]

Yep. The use cases all take a single argument, and it doesn't seem worth the
complexity to handle the more general case.

+    try:
+      return self._memos[x]
+    except KeyError:
+      fx = self._f(x)
+      self._memos[x] = fx
+      return fx