The fare-memoization Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The fare-memoization Reference Manual

This is the fare-memoization Reference Manual, version 1.2.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed Jun 15 04:30:58 2022 GMT+0.

Table of Contents


1 Introduction

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.
Such a function is notably necessary in cases such as the function
having optional arguments or keyword arguments, wherein you might want
to canonicalize the order in which keyword arguments appear, explicitly
fill in the default values for the various arguments, coerce some arguments
to some appropriate type, possibly upcase or downcase some strings, etc.
This may allow you to reduce the size of the memoization table, but also and
most importantly to make sure two semantically equivalent lists of arguments
(according to the semantics of YOUR application) yield the very same result.


==== Other Common Lisp MEMOIZATION libraries ====

Notable precursors published for Common Lisp include the following.

Marty Hall's 1993 memoization package
	http://www.csee.umbc.edu/courses/pub/Memoization/
as notably published as part of Araneida
	http://www.common-lisp.net/project/araneida/araneida-release/memoization.lisp
It tries to do too much, yet fails in some basic cases:
it treats MEMOIZEing as if it were TRACEing, as something temporary,
done to explore existing program behavior, that can be disabled,
and is not required as part of the permanent semantics of your program
(what with allowing to mass-unmemoize all functions? what if a function's
specified memoization table is essential to its termination?).
The way to customize memoization is not very principled, and its proposed
examples and optional optimizations are invitations to writing bad programs.
At the same time, it won't handle multiple return values, and
it will fail silently in presence of inlining.

The version from Peter Norvig's book
"Principles of Artificial Intelligence Programming"
	http://norvig.com/paip/auxfns.lisp
is a nice quick proof of concept, but
not anything anyone would want to use for real.

Tim Bradshaw's memoize library based on the above,
	http://www.tfeb.org/lisp/hax.html#MEMOIZE
will also fail to handle multiple return values,
dubiously offer to clear all memoized functions,
make it hard to use your implementation's weak hash-table feature.
It has a complex memoized-labels of questionable utility;
with fare-memoization, you can use MEMOIZING or MEMOIZED-FUNCALL
to memoize whichever local function you desire without having
to memoize every function in the same labels,
at a scope you have better control upon.

Finally, there's an earlier version of MEMOIZE that I wrote
as part of my own "Fibonacci" discussion and once made part of FARE-UTILS.
	http://fare.tunes.org/files/fun/fibonacci.lisp
FARE-MEMOIZATION is a more elaborate version of it, with an improved API,
notably regarding the TABLE and NORMALIZATION arguments.


As compared to these precursors, fare-memoization tries to:
* do less, providing only what is strictly needed in real-world uses.
* have well-defined semantics in all cases (modulo documented constraints).
* be portable to all compliant CL implementations without hidden assumptions.
* give maximum control to the user in defining memoization tables.
* have a modern packaging, which these days means ASDF and quicklisp.


==== False good idea not implemented by FARE-MEMOIZATION ====

At some point, I wanted to provide a library function as follows:
(define-memo-function make-the (class &rest keys)
  (apply #'make-instance (find-class class) keys))
But there is no portable way to normalize initialization key list:
not only do you have to sort the keys (which can be done portably as below,
assuming they are all keywords), you first have to merge default initform's
for slots -- and because in practice make-instance and shared-initialize
methods are allowed to do things before, after and around the initform's
depending on provided keys, you cannot do that in a portable way at all.

In conclusion, if programmers want to have classes with objects that are
interned in a table that ensures that two objects are EQ if their keys
verify some equality predicate, they have to develop their own protocol.
Things get even murkier when the creation of some object is requested,
but an object already exists that has a similar keys, yet with other
properties not covered by key equality that differ from the previously
interned object. How are the two objects to be reconciled? This also
requires application-dependent semantics that the protocol must allow
the programmer to specify.


2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 fare-memoization

memoizing functions the correct, portable way

Author

Francois-Rene Rideau

License

MIT

Long Description

define memoized functions and memoize previously defined functions

Version

1.2.0

Source

fare-memoization.asd.

Child Component

memoization.lisp (file).


3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


3.1.1 fare-memoization/fare-memoization.asd

Source

fare-memoization.asd.

Parent Component

fare-memoization (system).

ASDF Systems

fare-memoization.


3.1.2 fare-memoization/memoization.lisp

Source

fare-memoization.asd.

Parent Component

fare-memoization (system).

Packages

fare-memoization.

Public Interface
Internals

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 fare-memoization

Source

memoization.lisp.

Nickname

fmemo

Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Public Interface


Next: , Previous: , Up: Public Interface   [Contents][Index]

5.1.1 Special variables

Special Variable: *memoized*
Package

fare-memoization.

Source

memoization.lisp.


5.1.2 Macros

Macro: define-memo-function (name formals &body body)

Like defun, but creates a memoized function.
Also, if the name is a CONS, then the first element is the name, and the rest is a list of keyword arguments, TABLE and NORMALIZATION as per MEMOIZE.

Package

fare-memoization.

Source

memoization.lisp.


Previous: , Up: Public Interface   [Contents][Index]

5.1.3 Ordinary functions

Function: memoize (symbol &rest keys &key table argument-normalizer call-normalizer normalization)

Memoize the function associated to given SYMBOL.

Beware that unless the function was declared NOTINLINE, callers may have inlined the original definition and will not see the memoized function.
Moreover, if the function is self-recursive,
this declaration must have happened before it was defined.

Keyword argument TABLE (default: a fresh EQUAL hash-table) lets you
specify an existing hash-table for the memoized computations;
it may have been created with appropriate options regarding equality predicate and weak pointers, initial contents, etc., and you may clear it when needed.

Keyword argument ARGUMENT-NORMALIZER (default: NIL) lets you specify a function taking a list of arguments and returning a normalized list of arguments,
so that all lists with the same normalization will share the same memoized computation. NIL means no such normalization, which is the same as #’LIST.

Keyword argument CALL-NORMALIZER (alias: NORMALIZATION, default: NIL)
lets you specify a function taking a continuation and the function arguments, e.g. with lambda-list (CONTINUATION &REST ARGUMENTS)
which 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.

If the function was already being memoized, any previous memoization arguments, i.e. TABLE and ARGUMENT-NORMALIZER, is replaced with the newly specified values (unspecified arguments are replaced by defaults rather than left as previously specified).

Package

fare-memoization.

Source

memoization.lisp.

Function: memoized-apply (function &rest arguments)
Package

fare-memoization.

Source

memoization.lisp.

Function: memoized-funcall (&rest arguments)
Package

fare-memoization.

Source

memoization.lisp.

Function: memoizing (function &rest keys &key table normalization)

Given a function, return a memoizing version of same function. Keyword arguments TABLE and NORMALIZATION are as per MEMOIZE.

Package

fare-memoization.

Source

memoization.lisp.

Function: unmemoize (symbol)

undoing the memoizing function, return the memoization-info record for the function

Package

fare-memoization.

Source

memoization.lisp.

Function: unmemoize-1 (symbol &rest arguments)

Forget the memoized result of calling SYMBOL with arguments ARGUMENTS. Do not forget memoized results of calling the function with other arguments. Returns T if a stored result was found and removed, NIL otherwise.

Package

fare-memoization.

Source

memoization.lisp.


5.2 Internals


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.1 Ordinary functions

Function: compute-memoized-function (info arguments)

the basic helper for computing with a memoized function described by INFO, being called with arguments ARGUMENTS

Package

fare-memoization.

Source

memoization.lisp.

Function: make-memoization-info (function &rest keys &key table argument-normalizer call-normalizer normalization)
Package

fare-memoization.

Source

memoization.lisp.

Function: memoization-wrapper (info)

the basic helper for computing with a memoized function described by INFO, being called with arguments ARGUMENTS

Package

fare-memoization.

Source

memoization.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.2 Generic functions

Generic Reader: memoized-argument-normalizer (object)
Package

fare-memoization.

Methods
Reader Method: memoized-argument-normalizer ((memoization-info memoization-info))

either NIL or a function to normalize arguments before memoization

Source

memoization.lisp.

Target Slot

argument-normalizer.

Generic Reader: memoized-call-normalizer (object)
Package

fare-memoization.

Methods
Reader Method: memoized-call-normalizer ((memoization-info memoization-info))

either NIL or a function to normalize arguments before memoization

Source

memoization.lisp.

Target Slot

call-normalizer.

Generic Reader: memoized-table (object)
Package

fare-memoization.

Methods
Reader Method: memoized-table ((memoization-info memoization-info))

a hash-table containing the memoized computations so far

Source

memoization.lisp.

Target Slot

table.

Generic Reader: original-function (object)
Package

fare-memoization.

Methods
Reader Method: original-function ((memoization-info memoization-info))

The original, unmemoized, function

Source

memoization.lisp.

Target Slot

function.

Generic Reader: wrapped-function (object)
Generic Writer: (setf wrapped-function) (object)
Package

fare-memoization.

Methods
Reader Method: wrapped-function ((memoization-info memoization-info))
Writer Method: (setf wrapped-function) ((memoization-info memoization-info))

The memoizing version of the function.

Source

memoization.lisp.

Target Slot

wrapped-function.


Previous: , Up: Internals   [Contents][Index]

5.2.3 Classes

Class: memoization-info

information about a function that was memoized

Package

fare-memoization.

Source

memoization.lisp.

Direct methods
Direct slots
Slot: function

The original, unmemoized, function

Package

common-lisp.

Initargs

:function

Readers

original-function.

Writers

This slot is read-only.

Slot: wrapped-function

The memoizing version of the function.

Readers

wrapped-function.

Writers

(setf wrapped-function).

Slot: table

a hash-table containing the memoized computations so far

Initform

(make-hash-table :test (quote equal))

Initargs

:table

Readers

memoized-table.

Writers

This slot is read-only.

Slot: argument-normalizer

either NIL or a function to normalize arguments before memoization

Initargs

:argument-normalizer

Readers

memoized-argument-normalizer.

Writers

This slot is read-only.

Slot: call-normalizer

either NIL or a function to normalize arguments before memoization

Initargs

:normalization, :call-normalizer

Readers

memoized-call-normalizer.

Writers

This slot is read-only.


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
C   D   F   G   M   O   U   W  
Index Entry  Section

(
(setf wrapped-function): Private generic functions
(setf wrapped-function): Private generic functions

C
compute-memoized-function: Private ordinary functions

D
define-memo-function: Public macros

F
Function, compute-memoized-function: Private ordinary functions
Function, make-memoization-info: Private ordinary functions
Function, memoization-wrapper: Private ordinary functions
Function, memoize: Public ordinary functions
Function, memoized-apply: Public ordinary functions
Function, memoized-funcall: Public ordinary functions
Function, memoizing: Public ordinary functions
Function, unmemoize: Public ordinary functions
Function, unmemoize-1: Public ordinary functions

G
Generic Function, (setf wrapped-function): Private generic functions
Generic Function, memoized-argument-normalizer: Private generic functions
Generic Function, memoized-call-normalizer: Private generic functions
Generic Function, memoized-table: Private generic functions
Generic Function, original-function: Private generic functions
Generic Function, wrapped-function: Private generic functions

M
Macro, define-memo-function: Public macros
make-memoization-info: Private ordinary functions
memoization-wrapper: Private ordinary functions
memoize: Public ordinary functions
memoized-apply: Public ordinary functions
memoized-argument-normalizer: Private generic functions
memoized-argument-normalizer: Private generic functions
memoized-call-normalizer: Private generic functions
memoized-call-normalizer: Private generic functions
memoized-funcall: Public ordinary functions
memoized-table: Private generic functions
memoized-table: Private generic functions
memoizing: Public ordinary functions
Method, (setf wrapped-function): Private generic functions
Method, memoized-argument-normalizer: Private generic functions
Method, memoized-call-normalizer: Private generic functions
Method, memoized-table: Private generic functions
Method, original-function: Private generic functions
Method, wrapped-function: Private generic functions

O
original-function: Private generic functions
original-function: Private generic functions

U
unmemoize: Public ordinary functions
unmemoize-1: Public ordinary functions

W
wrapped-function: Private generic functions
wrapped-function: Private generic functions

Jump to:   (  
C   D   F   G   M   O   U   W