summaryrefslogtreecommitdiff
path: root/Master/tlpkg/tlperl/lib/Memoize.pm
diff options
context:
space:
mode:
authorSiep Kroonenberg <siepo@cybercomm.nl>2011-02-17 12:20:49 +0000
committerSiep Kroonenberg <siepo@cybercomm.nl>2011-02-17 12:20:49 +0000
commit316ee97c621496b0fe3267f57cce81bee44ca1e6 (patch)
treecb2cab1192b4f58a7971af19b213e980bceda4b4 /Master/tlpkg/tlperl/lib/Memoize.pm
parentcd0f87b5d39480d85ad9bd4ee37f520f75bed560 (diff)
Moving old tlperl prior to committing new one
git-svn-id: svn://tug.org/texlive/trunk@21422 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/tlpkg/tlperl/lib/Memoize.pm')
-rwxr-xr-xMaster/tlpkg/tlperl/lib/Memoize.pm1047
1 files changed, 0 insertions, 1047 deletions
diff --git a/Master/tlpkg/tlperl/lib/Memoize.pm b/Master/tlpkg/tlperl/lib/Memoize.pm
deleted file mode 100755
index 0cecbcab0a6..00000000000
--- a/Master/tlpkg/tlperl/lib/Memoize.pm
+++ /dev/null
@@ -1,1047 +0,0 @@
-# -*- 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