FARE-MEMOIZATION

This library builds on an age-old idea: dynamically memoizing Lisp functions.
A memoized function remembers results from previous computations, and
returns cached results when called with the same arguments again,
rather than re-do the computation. This library allows you
to focus on the computation logic and handles the caching part for you.
It also allows you to memoize a function after the fact when you need it.
Obviously, you should only use memoization for functions where it is meaningful:
pure functions that are expensive to compute,

non-deterministic functions for which it matters that choices be consistent,
hash-consing constructors that need return the same result when called with
the same arguments, user-visible constructors for singleton classes, etc.

This file first documents the interface of this library, then
compares fare-memoization to previous memoization libraries,
and finally discusses a false good idea of feature I had.


==== Exported Functionality ====

The fare-memoization library creates a package FARE-MEMOIZATION,
with nickname FMEMO, that exports the following macros and functions:

MEMOIZE SYMBOL &KEY TABLE NORMALIZATION
  This function memoizes the function associated to given SYMBOL.
  If the function was already memoized, it resets
  the associated memoization TABLE and NORMALIZATION function
  to those explicitly specified by this latter call to MEMOIZE, or
  to their implicit defaults (respectively a fresh EQUAL hash-table and NIL).
  Beware that function was declared NOTINLINE, callers are not guaranteed
  to see the memoized function rather than have inlined the original one.
  Moreover, if the function is self-recursive, this
  (declaim (notinline SYMBOL)) must have happened before it was defined.
  Keyword arguments TABLE and NORMALIZATION are as usual (see below).

UNMEMOIZE SYMBOL
  This function undoes what MEMOIZE did to the given SYMBOL.

UNMEMOIZE-1 SYMBOL &REST ARGUMENTS
  This function removes one entry from the memoization cache of SYMBOL.
  It returns T if an entry was found and removed corresponding to ARGUMENTS,
  and NIL if none was found.

DEFINE-MEMO-FUNCTION NAME FORMALS &BODY BODY
  This macro is like DEFUN, but its the defined function will be memoized.
  If NAME is a CONS rather than a symbol,
  the actual name for DEFUN will be its first element, and
  the rest will be a list with keyword arguments TABLE and NORMALIZATION
  as usual (see below).

MEMOIZING FUNCTION &KEY TABLE NORMALIZATION
  This takes a function as argument, and returns a new function that
  calls the given FUNCTION when provided arguments for which
  a result wasn't previously memoized.
  Keyword arguments are as usual (see below).
  Note that if function is self-recursive,
  only the toplevel call will be memoized.

MEMOIZED-FUNCALL FUNCTION &REST ARGUMENTS
  This is a generic way to memoize arbitrary functions on a per-call basis:
  all calls to MEMOIZED-FUNCALL share the same cache, which uses
  the EQUAL hash-table *MEMOIZED* below, and no normalization function.

MEMOIZED-APPLY FUNCTION &REST ARGUMENTS
  This function is to MEMOIZED-FUNCALL as APPLY is to FUNCALL.

*MEMOIZED*
  An EQUAL hash-table, the memoized computation cache for MEMOIZED-FUNCALL.
  You may thus easily (clr-hash *memoized*) to clear the cache of all
  such generic memoized function calls.


The keyword arguments TABLE and NORMALIZATION allow users to customize
the behavior of normalization.

TABLE is the hash-table in which to store the memoized computations.
Its keys will be lists of arguments passed to the function, and
its values will be remembered lists of values returned by the function
when previously called with the respective arguments.
The default value if not specified will be a fresh EQUAL hash-table.
The main uses for explicitly specifying such a table is to be able to
clear the table when the computations are somehow invalidated,
or pre-fill the table with seed values,
so the computations terminate when they reach the edge cases.
You'll usually want any such explicitly given table to be otherwise
reachable, for instance by binding a special variable to it.
The hash-table is an EQUAL hash-table by default, but
you can explicitly pass an EQUALP hash-table if you want.
Since the keys are lists (of arguments),
it is inappropriate to use an EQ or EQL hash-table.
If your implementation allows it and it is meaningful,
you may somehow create a hash-table wherein the keys are weak pointers;
how to achieve such an effect is not portable,
see your implementation's documentation.

NORMALIZATION when non-NIL is a function that normalizes argument lists;
the function is called with a continuation and the function arguments,
e.g. with lambda-list (CONTINUATION &REST ARGUMENTS);
it may transform the argument list before to call the continuation with
a normalized argument list that will be used to query the computation cache
and invoke the actual computation function. NIL means no such transformation,
which has the same effect as specifying #'APPLY as a transformation.