summaryrefslogtreecommitdiff
path: root/Master/tlpkg/tlperl/lib/Memoize.pm
diff options
context:
space:
mode:
Diffstat (limited to 'Master/tlpkg/tlperl/lib/Memoize.pm')
-rw-r--r--Master/tlpkg/tlperl/lib/Memoize.pm1047
1 files changed, 1047 insertions, 0 deletions
diff --git a/Master/tlpkg/tlperl/lib/Memoize.pm b/Master/tlpkg/tlperl/lib/Memoize.pm
new file mode 100644
index 00000000000..0cecbcab0a6
--- /dev/null
+++ b/Master/tlpkg/tlperl/lib/Memoize.pm
@@ -0,0 +1,1047 @@
+# -*- mode: perl; perl-indent-level: 2; -*-
+# Memoize.pm
+#
+# Transparent memoization of idempotent functions
+#
+# Copyright 1998, 1999, 2000, 2001 M-J. Dominus.
+# You may copy and distribute this program under the
+# same terms as Perl itself. If in doubt,
+# write to mjd-perl-memoize+@plover.com for a license.
+#
+# Version 1.01 $Revision: 1.18 $ $Date: 2001/06/24 17:16:47 $
+
+package Memoize;
+$VERSION = '1.01_03';
+
+# Compile-time constants
+sub SCALAR () { 0 }
+sub LIST () { 1 }
+
+
+#
+# Usage memoize(functionname/ref,
+# { NORMALIZER => coderef, INSTALL => name,
+# LIST_CACHE => descriptor, SCALAR_CACHE => descriptor }
+#
+
+use Carp;
+use Exporter;
+use vars qw($DEBUG);
+use Config; # Dammit.
+@ISA = qw(Exporter);
+@EXPORT = qw(memoize);
+@EXPORT_OK = qw(unmemoize flush_cache);
+use strict;
+
+my %memotable;
+my %revmemotable;
+my @CONTEXT_TAGS = qw(MERGE TIE MEMORY FAULT HASH);
+my %IS_CACHE_TAG = map {($_ => 1)} @CONTEXT_TAGS;
+
+# Raise an error if the user tries to specify one of thesepackage as a
+# tie for LIST_CACHE
+
+my %scalar_only = map {($_ => 1)} qw(DB_File GDBM_File SDBM_File ODBM_File NDBM_File);
+
+sub memoize {
+ my $fn = shift;
+ my %options = @_;
+ my $options = \%options;
+
+ unless (defined($fn) &&
+ (ref $fn eq 'CODE' || ref $fn eq '')) {
+ croak "Usage: memoize 'functionname'|coderef {OPTIONS}";
+ }
+
+ my $uppack = caller; # TCL me Elmo!
+ my $cref; # Code reference to original function
+ my $name = (ref $fn ? undef : $fn);
+
+ # Convert function names to code references
+ $cref = &_make_cref($fn, $uppack);
+
+ # Locate function prototype, if any
+ my $proto = prototype $cref;
+ if (defined $proto) { $proto = "($proto)" }
+ else { $proto = "" }
+
+ # I would like to get rid of the eval, but there seems not to be any
+ # other way to set the prototype properly. The switch here for
+ # 'usethreads' works around a bug in threadperl having to do with
+ # magic goto. It would be better to fix the bug and use the magic
+ # goto version everywhere.
+ my $wrapper =
+ $Config{usethreads}
+ ? eval "sub $proto { &_memoizer(\$cref, \@_); }"
+ : eval "sub $proto { unshift \@_, \$cref; goto &_memoizer; }";
+
+ my $normalizer = $options{NORMALIZER};
+ if (defined $normalizer && ! ref $normalizer) {
+ $normalizer = _make_cref($normalizer, $uppack);
+ }
+
+ my $install_name;
+ if (defined $options->{INSTALL}) {
+ # INSTALL => name
+ $install_name = $options->{INSTALL};
+ } elsif (! exists $options->{INSTALL}) {
+ # No INSTALL option provided; use original name if possible
+ $install_name = $name;
+ } else {
+ # INSTALL => undef means don't install
+ }
+
+ if (defined $install_name) {
+ $install_name = $uppack . '::' . $install_name
+ unless $install_name =~ /::/;
+ no strict;
+ local($^W) = 0; # ``Subroutine $install_name redefined at ...''
+ *{$install_name} = $wrapper; # Install memoized version
+ }
+
+ $revmemotable{$wrapper} = "" . $cref; # Turn code ref into hash key
+
+ # These will be the caches
+ my %caches;
+ for my $context (qw(SCALAR LIST)) {
+ # suppress subsequent 'uninitialized value' warnings
+ $options{"${context}_CACHE"} ||= '';
+
+ my $cache_opt = $options{"${context}_CACHE"};
+ my @cache_opt_args;
+ if (ref $cache_opt) {
+ @cache_opt_args = @$cache_opt;
+ $cache_opt = shift @cache_opt_args;
+ }
+ if ($cache_opt eq 'FAULT') { # no cache
+ $caches{$context} = undef;
+ } elsif ($cache_opt eq 'HASH') { # user-supplied hash
+ my $cache = $cache_opt_args[0];
+ my $package = ref(tied %$cache);
+ if ($context eq 'LIST' && $scalar_only{$package}) {
+ croak("You can't use $package for LIST_CACHE because it can only store scalars");
+ }
+ $caches{$context} = $cache;
+ } elsif ($cache_opt eq '' || $IS_CACHE_TAG{$cache_opt}) {
+ # default is that we make up an in-memory hash
+ $caches{$context} = {};
+ # (this might get tied later, or MERGEd away)
+ } else {
+ croak "Unrecognized option to `${context}_CACHE': `$cache_opt' should be one of (@CONTEXT_TAGS); aborting";
+ }
+ }
+
+ # Perhaps I should check here that you didn't supply *both* merge
+ # options. But if you did, it does do something reasonable: They
+ # both get merged to the same in-memory hash.
+ if ($options{SCALAR_CACHE} eq 'MERGE') {
+ $caches{SCALAR} = $caches{LIST};
+ } elsif ($options{LIST_CACHE} eq 'MERGE') {
+ $caches{LIST} = $caches{SCALAR};
+ }
+
+ # Now deal with the TIE options
+ {
+ my $context;
+ foreach $context (qw(SCALAR LIST)) {
+ # If the relevant option wasn't `TIE', this call does nothing.
+ _my_tie($context, $caches{$context}, $options); # Croaks on failure
+ }
+ }
+
+ # We should put some more stuff in here eventually.
+ # We've been saying that for serveral versions now.
+ # And you know what? More stuff keeps going in!
+ $memotable{$cref} =
+ {
+ O => $options, # Short keys here for things we need to access frequently
+ N => $normalizer,
+ U => $cref,
+ MEMOIZED => $wrapper,
+ PACKAGE => $uppack,
+ NAME => $install_name,
+ S => $caches{SCALAR},
+ L => $caches{LIST},
+ };
+
+ $wrapper # Return just memoized version
+}
+
+# This function tries to load a tied hash class and tie the hash to it.
+sub _my_tie {
+ my ($context, $hash, $options) = @_;
+ my $fullopt = $options->{"${context}_CACHE"};
+
+ # We already checked to make sure that this works.
+ my $shortopt = (ref $fullopt) ? $fullopt->[0] : $fullopt;
+
+ return unless defined $shortopt && $shortopt eq 'TIE';
+ carp("TIE option to memoize() is deprecated; use HASH instead")
+ if $^W;
+
+ my @args = ref $fullopt ? @$fullopt : ();
+ shift @args;
+ my $module = shift @args;
+ if ($context eq 'LIST' && $scalar_only{$module}) {
+ croak("You can't use $module for LIST_CACHE because it can only store scalars");
+ }
+ my $modulefile = $module . '.pm';
+ $modulefile =~ s{::}{/}g;
+ eval { require $modulefile };
+ if ($@) {
+ croak "Memoize: Couldn't load hash tie module `$module': $@; aborting";
+ }
+ my $rc = (tie %$hash => $module, @args);
+ unless ($rc) {
+ croak "Memoize: Couldn't tie hash to `$module': $!; aborting";
+ }
+ 1;
+}
+
+sub flush_cache {
+ my $func = _make_cref($_[0], scalar caller);
+ my $info = $memotable{$revmemotable{$func}};
+ die "$func not memoized" unless defined $info;
+ for my $context (qw(S L)) {
+ my $cache = $info->{$context};
+ if (tied %$cache && ! (tied %$cache)->can('CLEAR')) {
+ my $funcname = defined($info->{NAME}) ?
+ "function $info->{NAME}" : "anonymous function $func";
+ my $context = {S => 'scalar', L => 'list'}->{$context};
+ croak "Tied cache hash for $context-context $funcname does not support flushing";
+ } else {
+ %$cache = ();
+ }
+ }
+}
+
+# This is the function that manages the memo tables.
+sub _memoizer {
+ my $orig = shift; # stringized version of ref to original func.
+ my $info = $memotable{$orig};
+ my $normalizer = $info->{N};
+
+ my $argstr;
+ my $context = (wantarray() ? LIST : SCALAR);
+
+ if (defined $normalizer) {
+ no strict;
+ if ($context == SCALAR) {
+ $argstr = &{$normalizer}(@_);
+ } elsif ($context == LIST) {
+ ($argstr) = &{$normalizer}(@_);
+ } else {
+ croak "Internal error \#41; context was neither LIST nor SCALAR\n";
+ }
+ } else { # Default normalizer
+ local $^W = 0;
+ $argstr = join chr(28),@_;
+ }
+
+ if ($context == SCALAR) {
+ my $cache = $info->{S};
+ _crap_out($info->{NAME}, 'scalar') unless $cache;
+ if (exists $cache->{$argstr}) {
+ return $cache->{$argstr};
+ } else {
+ my $val = &{$info->{U}}(@_);
+ # Scalars are considered to be lists; store appropriately
+ if ($info->{O}{SCALAR_CACHE} eq 'MERGE') {
+ $cache->{$argstr} = [$val];
+ } else {
+ $cache->{$argstr} = $val;
+ }
+ $val;
+ }
+ } elsif ($context == LIST) {
+ my $cache = $info->{L};
+ _crap_out($info->{NAME}, 'list') unless $cache;
+ if (exists $cache->{$argstr}) {
+ my $val = $cache->{$argstr};
+ # If LISTCONTEXT=>MERGE, then the function never returns lists,
+ # so we have a scalar value cached, so just return it straightaway:
+ return ($val) if $info->{O}{LIST_CACHE} eq 'MERGE';
+ # Maybe in a later version we can use a faster test.
+
+ # Otherwise, we cached an array containing the returned list:
+ return @$val;
+ } else {
+ my @q = &{$info->{U}}(@_);
+ $cache->{$argstr} = $info->{O}{LIST_CACHE} eq 'MERGE' ? $q [0] : \@q;
+ @q;
+ }
+ } else {
+ croak "Internal error \#42; context was neither LIST nor SCALAR\n";
+ }
+}
+
+sub unmemoize {
+ my $f = shift;
+ my $uppack = caller;
+ my $cref = _make_cref($f, $uppack);
+
+ unless (exists $revmemotable{$cref}) {
+ croak "Could not unmemoize function `$f', because it was not memoized to begin with";
+ }
+
+ my $tabent = $memotable{$revmemotable{$cref}};
+ unless (defined $tabent) {
+ croak "Could not figure out how to unmemoize function `$f'";
+ }
+ my $name = $tabent->{NAME};
+ if (defined $name) {
+ no strict;
+ local($^W) = 0; # ``Subroutine $install_name redefined at ...''
+ *{$name} = $tabent->{U}; # Replace with original function
+ }
+ undef $memotable{$revmemotable{$cref}};
+ undef $revmemotable{$cref};
+
+ # This removes the last reference to the (possibly tied) memo tables
+ # my ($old_function, $memotabs) = @{$tabent}{'U','S','L'};
+ # undef $tabent;
+
+# # Untie the memo tables if they were tied.
+# my $i;
+# for $i (0,1) {
+# if (tied %{$memotabs->[$i]}) {
+# warn "Untying hash #$i\n";
+# untie %{$memotabs->[$i]};
+# }
+# }
+
+ $tabent->{U};
+}
+
+sub _make_cref {
+ my $fn = shift;
+ my $uppack = shift;
+ my $cref;
+ my $name;
+
+ if (ref $fn eq 'CODE') {
+ $cref = $fn;
+ } elsif (! ref $fn) {
+ if ($fn =~ /::/) {
+ $name = $fn;
+ } else {
+ $name = $uppack . '::' . $fn;
+ }
+ no strict;
+ if (defined $name and !defined(&$name)) {
+ croak "Cannot operate on nonexistent function `$fn'";
+ }
+# $cref = \&$name;
+ $cref = *{$name}{CODE};
+ } else {
+ my $parent = (caller(1))[3]; # Function that called _make_cref
+ croak "Usage: argument 1 to `$parent' must be a function name or reference.\n";
+ }
+ $DEBUG and warn "${name}($fn) => $cref in _make_cref\n";
+ $cref;
+}
+
+sub _crap_out {
+ my ($funcname, $context) = @_;
+ if (defined $funcname) {
+ croak "Function `$funcname' called in forbidden $context context; faulting";
+ } else {
+ croak "Anonymous function called in forbidden $context context; faulting";
+ }
+}
+
+1;
+
+
+
+
+
+=head1 NAME
+
+Memoize - Make functions faster by trading space for time
+
+=head1 SYNOPSIS
+
+ # This is the documentation for Memoize 1.01
+ use Memoize;
+ memoize('slow_function');
+ slow_function(arguments); # Is faster than it was before
+
+
+This is normally all you need to know. However, many options are available:
+
+ memoize(function, options...);
+
+Options include:
+
+ NORMALIZER => function
+ INSTALL => new_name
+
+ SCALAR_CACHE => 'MEMORY'
+ SCALAR_CACHE => ['HASH', \%cache_hash ]
+ SCALAR_CACHE => 'FAULT'
+ SCALAR_CACHE => 'MERGE'
+
+ LIST_CACHE => 'MEMORY'
+ LIST_CACHE => ['HASH', \%cache_hash ]
+ LIST_CACHE => 'FAULT'
+ LIST_CACHE => 'MERGE'
+
+=head1 DESCRIPTION
+
+`Memoizing' a function makes it faster by trading space for time. It
+does this by caching the return values of the function in a table.
+If you call the function again with the same arguments, C<memoize>
+jumps in and gives you the value out of the table, instead of letting
+the function compute the value all over again.
+
+Here is an extreme example. Consider the Fibonacci sequence, defined
+by the following function:
+
+ # Compute Fibonacci numbers
+ sub fib {
+ my $n = shift;
+ return $n if $n < 2;
+ fib($n-1) + fib($n-2);
+ }
+
+This function is very slow. Why? To compute fib(14), it first wants
+to compute fib(13) and fib(12), and add the results. But to compute
+fib(13), it first has to compute fib(12) and fib(11), and then it
+comes back and computes fib(12) all over again even though the answer
+is the same. And both of the times that it wants to compute fib(12),
+it has to compute fib(11) from scratch, and then it has to do it
+again each time it wants to compute fib(13). This function does so
+much recomputing of old results that it takes a really long time to
+run---fib(14) makes 1,200 extra recursive calls to itself, to compute
+and recompute things that it already computed.
+
+This function is a good candidate for memoization. If you memoize the
+`fib' function above, it will compute fib(14) exactly once, the first
+time it needs to, and then save the result in a table. Then if you
+ask for fib(14) again, it gives you the result out of the table.
+While computing fib(14), instead of computing fib(12) twice, it does
+it once; the second time it needs the value it gets it from the table.
+It doesn't compute fib(11) four times; it computes it once, getting it
+from the table the next three times. Instead of making 1,200
+recursive calls to `fib', it makes 15. This makes the function about
+150 times faster.
+
+You could do the memoization yourself, by rewriting the function, like
+this:
+
+ # Compute Fibonacci numbers, memoized version
+ { my @fib;
+ sub fib {
+ my $n = shift;
+ return $fib[$n] if defined $fib[$n];
+ return $fib[$n] = $n if $n < 2;
+ $fib[$n] = fib($n-1) + fib($n-2);
+ }
+ }
+
+Or you could use this module, like this:
+
+ use Memoize;
+ memoize('fib');
+
+ # Rest of the fib function just like the original version.
+
+This makes it easy to turn memoizing on and off.
+
+Here's an even simpler example: I wrote a simple ray tracer; the
+program would look in a certain direction, figure out what it was
+looking at, and then convert the `color' value (typically a string
+like `red') of that object to a red, green, and blue pixel value, like
+this:
+
+ for ($direction = 0; $direction < 300; $direction++) {
+ # Figure out which object is in direction $direction
+ $color = $object->{color};
+ ($r, $g, $b) = @{&ColorToRGB($color)};
+ ...
+ }
+
+Since there are relatively few objects in a picture, there are only a
+few colors, which get looked up over and over again. Memoizing
+C<ColorToRGB> sped up the program by several percent.
+
+=head1 DETAILS
+
+This module exports exactly one function, C<memoize>. The rest of the
+functions in this package are None of Your Business.
+
+You should say
+
+ memoize(function)
+
+where C<function> is the name of the function you want to memoize, or
+a reference to it. C<memoize> returns a reference to the new,
+memoized version of the function, or C<undef> on a non-fatal error.
+At present, there are no non-fatal errors, but there might be some in
+the future.
+
+If C<function> was the name of a function, then C<memoize> hides the
+old version and installs the new memoized version under the old name,
+so that C<&function(...)> actually invokes the memoized version.
+
+=head1 OPTIONS
+
+There are some optional options you can pass to C<memoize> to change
+the way it behaves a little. To supply options, invoke C<memoize>
+like this:
+
+ memoize(function, NORMALIZER => function,
+ INSTALL => newname,
+ SCALAR_CACHE => option,
+ LIST_CACHE => option
+ );
+
+Each of these options is optional; you can include some, all, or none
+of them.
+
+=head2 INSTALL
+
+If you supply a function name with C<INSTALL>, memoize will install
+the new, memoized version of the function under the name you give.
+For example,
+
+ memoize('fib', INSTALL => 'fastfib')
+
+installs the memoized version of C<fib> as C<fastfib>; without the
+C<INSTALL> option it would have replaced the old C<fib> with the
+memoized version.
+
+To prevent C<memoize> from installing the memoized version anywhere, use
+C<INSTALL =E<gt> undef>.
+
+=head2 NORMALIZER
+
+Suppose your function looks like this:
+
+ # Typical call: f('aha!', A => 11, B => 12);
+ sub f {
+ my $a = shift;
+ my %hash = @_;
+ $hash{B} ||= 2; # B defaults to 2
+ $hash{C} ||= 7; # C defaults to 7
+
+ # Do something with $a, %hash
+ }
+
+Now, the following calls to your function are all completely equivalent:
+
+ f(OUCH);
+ f(OUCH, B => 2);
+ f(OUCH, C => 7);
+ f(OUCH, B => 2, C => 7);
+ f(OUCH, C => 7, B => 2);
+ (etc.)
+
+However, unless you tell C<Memoize> that these calls are equivalent,
+it will not know that, and it will compute the values for these
+invocations of your function separately, and store them separately.
+
+To prevent this, supply a C<NORMALIZER> function that turns the
+program arguments into a string in a way that equivalent arguments
+turn into the same string. A C<NORMALIZER> function for C<f> above
+might look like this:
+
+ sub normalize_f {
+ my $a = shift;
+ my %hash = @_;
+ $hash{B} ||= 2;
+ $hash{C} ||= 7;
+
+ join(',', $a, map ($_ => $hash{$_}) sort keys %hash);
+ }
+
+Each of the argument lists above comes out of the C<normalize_f>
+function looking exactly the same, like this:
+
+ OUCH,B,2,C,7
+
+You would tell C<Memoize> to use this normalizer this way:
+
+ memoize('f', NORMALIZER => 'normalize_f');
+
+C<memoize> knows that if the normalized version of the arguments is
+the same for two argument lists, then it can safely look up the value
+that it computed for one argument list and return it as the result of
+calling the function with the other argument list, even if the
+argument lists look different.
+
+The default normalizer just concatenates the arguments with character
+28 in between. (In ASCII, this is called FS or control-\.) This
+always works correctly for functions with only one string argument,
+and also when the arguments never contain character 28. However, it
+can confuse certain argument lists:
+
+ normalizer("a\034", "b")
+ normalizer("a", "\034b")
+ normalizer("a\034\034b")
+
+for example.
+
+Since hash keys are strings, the default normalizer will not
+distinguish between C<undef> and the empty string. It also won't work
+when the function's arguments are references. For example, consider a
+function C<g> which gets two arguments: A number, and a reference to
+an array of numbers:
+
+ g(13, [1,2,3,4,5,6,7]);
+
+The default normalizer will turn this into something like
+C<"13\034ARRAY(0x436c1f)">. That would be all right, except that a
+subsequent array of numbers might be stored at a different location
+even though it contains the same data. If this happens, C<Memoize>
+will think that the arguments are different, even though they are
+equivalent. In this case, a normalizer like this is appropriate:
+
+ sub normalize { join ' ', $_[0], @{$_[1]} }
+
+For the example above, this produces the key "13 1 2 3 4 5 6 7".
+
+Another use for normalizers is when the function depends on data other
+than those in its arguments. Suppose you have a function which
+returns a value which depends on the current hour of the day:
+
+ sub on_duty {
+ my ($problem_type) = @_;
+ my $hour = (localtime)[2];
+ open my $fh, "$DIR/$problem_type" or die...;
+ my $line;
+ while ($hour-- > 0)
+ $line = <$fh>;
+ }
+ return $line;
+ }
+
+At 10:23, this function generates the 10th line of a data file; at
+3:45 PM it generates the 15th line instead. By default, C<Memoize>
+will only see the $problem_type argument. To fix this, include the
+current hour in the normalizer:
+
+ sub normalize { join ' ', (localtime)[2], @_ }
+
+The calling context of the function (scalar or list context) is
+propagated to the normalizer. This means that if the memoized
+function will treat its arguments differently in list context than it
+would in scalar context, you can have the normalizer function select
+its behavior based on the results of C<wantarray>. Even if called in
+a list context, a normalizer should still return a single string.
+
+=head2 C<SCALAR_CACHE>, C<LIST_CACHE>
+
+Normally, C<Memoize> caches your function's return values into an
+ordinary Perl hash variable. However, you might like to have the
+values cached on the disk, so that they persist from one run of your
+program to the next, or you might like to associate some other
+interesting semantics with the cached values.
+
+There's a slight complication under the hood of C<Memoize>: There are
+actually I<two> caches, one for scalar values and one for list values.
+When your function is called in scalar context, its return value is
+cached in one hash, and when your function is called in list context,
+its value is cached in the other hash. You can control the caching
+behavior of both contexts independently with these options.
+
+The argument to C<LIST_CACHE> or C<SCALAR_CACHE> must either be one of
+the following four strings:
+
+ MEMORY
+ FAULT
+ MERGE
+ HASH
+
+or else it must be a reference to a list whose first element is one of
+these four strings, such as C<[HASH, arguments...]>.
+
+=over 4
+
+=item C<MEMORY>
+
+C<MEMORY> means that return values from the function will be cached in
+an ordinary Perl hash variable. The hash variable will not persist
+after the program exits. This is the default.
+
+=item C<HASH>
+
+C<HASH> allows you to specify that a particular hash that you supply
+will be used as the cache. You can tie this hash beforehand to give
+it any behavior you want.
+
+A tied hash can have any semantics at all. It is typically tied to an
+on-disk database, so that cached values are stored in the database and
+retrieved from it again when needed, and the disk file typically
+persists after your program has exited. See C<perltie> for more
+complete details about C<tie>.
+
+A typical example is:
+
+ use DB_File;
+ tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666;
+ memoize 'function', SCALAR_CACHE => [HASH => \%cache];
+
+This has the effect of storing the cache in a C<DB_File> database
+whose name is in C<$filename>. The cache will persist after the
+program has exited. Next time the program runs, it will find the
+cache already populated from the previous run of the program. Or you
+can forcibly populate the cache by constructing a batch program that
+runs in the background and populates the cache file. Then when you
+come to run your real program the memoized function will be fast
+because all its results have been precomputed.
+
+=item C<TIE>
+
+This option is no longer supported. It is still documented only to
+aid in the debugging of old programs that use it. Old programs should
+be converted to use the C<HASH> option instead.
+
+ memoize ... [TIE, PACKAGE, ARGS...]
+
+is merely a shortcut for
+
+ require PACKAGE;
+ { my %cache;
+ tie %cache, PACKAGE, ARGS...;
+ }
+ memoize ... [HASH => \%cache];
+
+=item C<FAULT>
+
+C<FAULT> means that you never expect to call the function in scalar
+(or list) context, and that if C<Memoize> detects such a call, it
+should abort the program. The error message is one of
+
+ `foo' function called in forbidden list context at line ...
+ `foo' function called in forbidden scalar context at line ...
+
+=item C<MERGE>
+
+C<MERGE> normally means the function does not distinguish between list
+and sclar context, and that return values in both contexts should be
+stored together. C<LIST_CACHE =E<gt> MERGE> means that list context
+return values should be stored in the same hash that is used for
+scalar context returns, and C<SCALAR_CACHE =E<gt> MERGE> means the
+same, mutatis mutandis. It is an error to specify C<MERGE> for both,
+but it probably does something useful.
+
+Consider this function:
+
+ sub pi { 3; }
+
+Normally, the following code will result in two calls to C<pi>:
+
+ $x = pi();
+ ($y) = pi();
+ $z = pi();
+
+The first call caches the value C<3> in the scalar cache; the second
+caches the list C<(3)> in the list cache. The third call doesn't call
+the real C<pi> function; it gets the value from the scalar cache.
+
+Obviously, the second call to C<pi> is a waste of time, and storing
+its return value is a waste of space. Specifying C<LIST_CACHE =E<gt>
+MERGE> will make C<memoize> use the same cache for scalar and list
+context return values, so that the second call uses the scalar cache
+that was populated by the first call. C<pi> ends up being called only
+once, and both subsequent calls return C<3> from the cache, regardless
+of the calling context.
+
+Another use for C<MERGE> is when you want both kinds of return values
+stored in the same disk file; this saves you from having to deal with
+two disk files instead of one. You can use a normalizer function to
+keep the two sets of return values separate. For example:
+
+ tie my %cache => 'MLDBM', 'DB_File', $filename, ...;
+
+ memoize 'myfunc',
+ NORMALIZER => 'n',
+ SCALAR_CACHE => [HASH => \%cache],
+ LIST_CACHE => MERGE,
+ ;
+
+ sub n {
+ my $context = wantarray() ? 'L' : 'S';
+ # ... now compute the hash key from the arguments ...
+ $hashkey = "$context:$hashkey";
+ }
+
+This normalizer function will store scalar context return values in
+the disk file under keys that begin with C<S:>, and list context
+return values under keys that begin with C<L:>.
+
+=back
+
+=head1 OTHER FACILITIES
+
+=head2 C<unmemoize>
+
+There's an C<unmemoize> function that you can import if you want to.
+Why would you want to? Here's an example: Suppose you have your cache
+tied to a DBM file, and you want to make sure that the cache is
+written out to disk if someone interrupts the program. If the program
+exits normally, this will happen anyway, but if someone types
+control-C or something then the program will terminate immediately
+without synchronizing the database. So what you can do instead is
+
+ $SIG{INT} = sub { unmemoize 'function' };
+
+C<unmemoize> accepts a reference to, or the name of a previously
+memoized function, and undoes whatever it did to provide the memoized
+version in the first place, including making the name refer to the
+unmemoized version if appropriate. It returns a reference to the
+unmemoized version of the function.
+
+If you ask it to unmemoize a function that was never memoized, it
+croaks.
+
+=head2 C<flush_cache>
+
+C<flush_cache(function)> will flush out the caches, discarding I<all>
+the cached data. The argument may be a function name or a reference
+to a function. For finer control over when data is discarded or
+expired, see the documentation for C<Memoize::Expire>, included in
+this package.
+
+Note that if the cache is a tied hash, C<flush_cache> will attempt to
+invoke the C<CLEAR> method on the hash. If there is no C<CLEAR>
+method, this will cause a run-time error.
+
+An alternative approach to cache flushing is to use the C<HASH> option
+(see above) to request that C<Memoize> use a particular hash variable
+as its cache. Then you can examine or modify the hash at any time in
+any way you desire. You may flush the cache by using C<%hash = ()>.
+
+=head1 CAVEATS
+
+Memoization is not a cure-all:
+
+=over 4
+
+=item *
+
+Do not memoize a function whose behavior depends on program
+state other than its own arguments, such as global variables, the time
+of day, or file input. These functions will not produce correct
+results when memoized. For a particularly easy example:
+
+ sub f {
+ time;
+ }
+
+This function takes no arguments, and as far as C<Memoize> is
+concerned, it always returns the same result. C<Memoize> is wrong, of
+course, and the memoized version of this function will call C<time> once
+to get the current time, and it will return that same time
+every time you call it after that.
+
+=item *
+
+Do not memoize a function with side effects.
+
+ sub f {
+ my ($a, $b) = @_;
+ my $s = $a + $b;
+ print "$a + $b = $s.\n";
+ }
+
+This function accepts two arguments, adds them, and prints their sum.
+Its return value is the numuber of characters it printed, but you
+probably didn't care about that. But C<Memoize> doesn't understand
+that. If you memoize this function, you will get the result you
+expect the first time you ask it to print the sum of 2 and 3, but
+subsequent calls will return 1 (the return value of
+C<print>) without actually printing anything.
+
+=item *
+
+Do not memoize a function that returns a data structure that is
+modified by its caller.
+
+Consider these functions: C<getusers> returns a list of users somehow,
+and then C<main> throws away the first user on the list and prints the
+rest:
+
+ sub main {
+ my $userlist = getusers();
+ shift @$userlist;
+ foreach $u (@$userlist) {
+ print "User $u\n";
+ }
+ }
+
+ sub getusers {
+ my @users;
+ # Do something to get a list of users;
+ \@users; # Return reference to list.
+ }
+
+If you memoize C<getusers> here, it will work right exactly once. The
+reference to the users list will be stored in the memo table. C<main>
+will discard the first element from the referenced list. The next
+time you invoke C<main>, C<Memoize> will not call C<getusers>; it will
+just return the same reference to the same list it got last time. But
+this time the list has already had its head removed; C<main> will
+erroneously remove another element from it. The list will get shorter
+and shorter every time you call C<main>.
+
+Similarly, this:
+
+ $u1 = getusers();
+ $u2 = getusers();
+ pop @$u1;
+
+will modify $u2 as well as $u1, because both variables are references
+to the same array. Had C<getusers> not been memoized, $u1 and $u2
+would have referred to different arrays.
+
+=item *
+
+Do not memoize a very simple function.
+
+Recently someone mentioned to me that the Memoize module made his
+program run slower instead of faster. It turned out that he was
+memoizing the following function:
+
+ sub square {
+ $_[0] * $_[0];
+ }
+
+I pointed out that C<Memoize> uses a hash, and that looking up a
+number in the hash is necessarily going to take a lot longer than a
+single multiplication. There really is no way to speed up the
+C<square> function.
+
+Memoization is not magical.
+
+=back
+
+=head1 PERSISTENT CACHE SUPPORT
+
+You can tie the cache tables to any sort of tied hash that you want
+to, as long as it supports C<TIEHASH>, C<FETCH>, C<STORE>, and
+C<EXISTS>. For example,
+
+ tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666;
+ memoize 'function', SCALAR_CACHE => [HASH => \%cache];
+
+works just fine. For some storage methods, you need a little glue.
+
+C<SDBM_File> doesn't supply an C<EXISTS> method, so included in this
+package is a glue module called C<Memoize::SDBM_File> which does
+provide one. Use this instead of plain C<SDBM_File> to store your
+cache table on disk in an C<SDBM_File> database:
+
+ tie my %cache => 'Memoize::SDBM_File', $filename, O_RDWR|O_CREAT, 0666;
+ memoize 'function', SCALAR_CACHE => [HASH => \%cache];
+
+C<NDBM_File> has the same problem and the same solution. (Use
+C<Memoize::NDBM_File instead of plain NDBM_File.>)
+
+C<Storable> isn't a tied hash class at all. You can use it to store a
+hash to disk and retrieve it again, but you can't modify the hash while
+it's on the disk. So if you want to store your cache table in a
+C<Storable> database, use C<Memoize::Storable>, which puts a hashlike
+front-end onto C<Storable>. The hash table is actually kept in
+memory, and is loaded from your C<Storable> file at the time you
+memoize the function, and stored back at the time you unmemoize the
+function (or when your program exits):
+
+ tie my %cache => 'Memoize::Storable', $filename;
+ memoize 'function', SCALAR_CACHE => [HASH => \%cache];
+
+ tie my %cache => 'Memoize::Storable', $filename, 'nstore';
+ memoize 'function', SCALAR_CACHE => [HASH => \%cache];
+
+Include the `nstore' option to have the C<Storable> database written
+in `network order'. (See L<Storable> for more details about this.)
+
+The C<flush_cache()> function will raise a run-time error unless the
+tied package provides a C<CLEAR> method.
+
+=head1 EXPIRATION SUPPORT
+
+See Memoize::Expire, which is a plug-in module that adds expiration
+functionality to Memoize. If you don't like the kinds of policies
+that Memoize::Expire implements, it is easy to write your own plug-in
+module to implement whatever policy you desire. Memoize comes with
+several examples. An expiration manager that implements a LRU policy
+is available on CPAN as Memoize::ExpireLRU.
+
+=head1 BUGS
+
+The test suite is much better, but always needs improvement.
+
+There is some problem with the way C<goto &f> works under threaded
+Perl, perhaps because of the lexical scoping of C<@_>. This is a bug
+in Perl, and until it is resolved, memoized functions will see a
+slightly different C<caller()> and will perform a little more slowly
+on threaded perls than unthreaded perls.
+
+Some versions of C<DB_File> won't let you store data under a key of
+length 0. That means that if you have a function C<f> which you
+memoized and the cache is in a C<DB_File> database, then the value of
+C<f()> (C<f> called with no arguments) will not be memoized. If this
+is a big problem, you can supply a normalizer function that prepends
+C<"x"> to every key.
+
+=head1 MAILING LIST
+
+To join a very low-traffic mailing list for announcements about
+C<Memoize>, send an empty note to C<mjd-perl-memoize-request@plover.com>.
+
+=head1 AUTHOR
+
+Mark-Jason Dominus (C<mjd-perl-memoize+@plover.com>), Plover Systems co.
+
+See the C<Memoize.pm> Page at http://www.plover.com/~mjd/perl/Memoize/
+for news and upgrades. Near this page, at
+http://www.plover.com/~mjd/perl/MiniMemoize/ there is an article about
+memoization and about the internals of Memoize that appeared in The
+Perl Journal, issue #13. (This article is also included in the
+Memoize distribution as `article.html'.)
+
+The author's book I<Higher Order Perl> (2005, ISBN 1558607013, published
+by Morgan Kaufmann) discusses memoization (and many other fascinating
+topics) in tremendous detail. It will also be available on-line for free.
+For more information, visit http://perl.plover.com/book/ .
+
+To join a mailing list for announcements about C<Memoize>, send an
+empty message to C<mjd-perl-memoize-request@plover.com>. This mailing
+list is for announcements only and has extremely low traffic---about
+two messages per year.
+
+=head1 COPYRIGHT AND LICENSE
+
+Copyright 1998, 1999, 2000, 2001 by Mark Jason Dominus
+
+This library is free software; you may redistribute it and/or modify
+it under the same terms as Perl itself.
+
+=head1 THANK YOU
+
+Many thanks to Jonathan Roy for bug reports and suggestions, to
+Michael Schwern for other bug reports and patches, to Mike Cariaso for
+helping me to figure out the Right Thing to Do About Expiration, to
+Joshua Gerth, Joshua Chamas, Jonathan Roy (again), Mark D. Anderson,
+and Andrew Johnson for more suggestions about expiration, to Brent
+Powers for the Memoize::ExpireLRU module, to Ariel Scolnicov for
+delightful messages about the Fibonacci function, to Dion Almaer for
+thought-provoking suggestions about the default normalizer, to Walt
+Mankowski and Kurt Starsinic for much help investigating problems
+under threaded Perl, to Alex Dudkevich for reporting the bug in
+prototyped functions and for checking my patch, to Tony Bass for many
+helpful suggestions, to Jonathan Roy (again) for finding a use for
+C<unmemoize()>, to Philippe Verdret for enlightening discussion of
+C<Hook::PrePostCall>, to Nat Torkington for advice I ignored, to Chris
+Nandor for portability advice, to Randal Schwartz for suggesting the
+'C<flush_cache> function, and to Jenda Krynicky for being a light in
+the world.
+
+Special thanks to Jarkko Hietaniemi, the 5.8.0 pumpking, for including
+this module in the core and for his patient and helpful guidance
+during the integration process.
+
+=cut