Some reordering and one new address for St├ęphane Payrard
[perl.git] / lib / Memoize.pm
1 # -*- mode: perl; perl-indent-level: 2; -*-
2 # Memoize.pm
3 #
4 # Transparent memoization of idempotent functions
5 #
6 # Copyright 1998, 1999, 2000, 2001 M-J. Dominus.
7 # You may copy and distribute this program under the
8 # same terms as Perl itself.  If in doubt, 
9 # write to mjd-perl-memoize+@plover.com for a license.
10 #
11 # Version 1.01 $Revision: 1.18 $ $Date: 2001/06/24 17:16:47 $
12
13 package Memoize;
14 $VERSION = '1.01_01';
15
16 # Compile-time constants
17 sub SCALAR () { 0 } 
18 sub LIST () { 1 } 
19
20
21 #
22 # Usage memoize(functionname/ref,
23 #               { NORMALIZER => coderef, INSTALL => name,
24 #                 LIST_CACHE => descriptor, SCALAR_CACHE => descriptor }
25 #
26
27 use Carp;
28 use Exporter;
29 use vars qw($DEBUG);
30 use Config;                     # Dammit.
31 @ISA = qw(Exporter);
32 @EXPORT = qw(memoize);
33 @EXPORT_OK = qw(unmemoize flush_cache);
34 use strict;
35
36 my %memotable;
37 my %revmemotable;
38 my @CONTEXT_TAGS = qw(MERGE TIE MEMORY FAULT HASH);
39 my %IS_CACHE_TAG = map {($_ => 1)} @CONTEXT_TAGS;
40
41 # Raise an error if the user tries to specify one of thesepackage as a
42 # tie for LIST_CACHE
43
44 my %scalar_only = map {($_ => 1)} qw(DB_File GDBM_File SDBM_File ODBM_File NDBM_File);
45
46 sub memoize {
47   my $fn = shift;
48   my %options = @_;
49   my $options = \%options;
50   
51   unless (defined($fn) && 
52           (ref $fn eq 'CODE' || ref $fn eq '')) {
53     croak "Usage: memoize 'functionname'|coderef {OPTIONS}";
54   }
55
56   my $uppack = caller;          # TCL me Elmo!
57   my $cref;                     # Code reference to original function
58   my $name = (ref $fn ? undef : $fn);
59
60   # Convert function names to code references
61   $cref = &_make_cref($fn, $uppack);
62
63   # Locate function prototype, if any
64   my $proto = prototype $cref;
65   if (defined $proto) { $proto = "($proto)" }
66   else { $proto = "" }
67
68   # I would like to get rid of the eval, but there seems not to be any
69   # other way to set the prototype properly.  The switch here for
70   # 'usethreads' works around a bug in threadperl having to do with
71   # magic goto.  It would be better to fix the bug and use the magic
72   # goto version everywhere.
73   my $wrapper = 
74       $Config{usethreads} 
75         ? eval "sub $proto { &_memoizer(\$cref, \@_); }" 
76         : eval "sub $proto { unshift \@_, \$cref; goto &_memoizer; }";
77
78   my $normalizer = $options{NORMALIZER};
79   if (defined $normalizer  && ! ref $normalizer) {
80     $normalizer = _make_cref($normalizer, $uppack);
81   }
82   
83   my $install_name;
84   if (defined $options->{INSTALL}) {
85     # INSTALL => name
86     $install_name = $options->{INSTALL};
87   } elsif (! exists $options->{INSTALL}) {
88     # No INSTALL option provided; use original name if possible
89     $install_name = $name;
90   } else {
91     # INSTALL => undef  means don't install
92   }
93
94   if (defined $install_name) {
95     $install_name = $uppack . '::' . $install_name
96         unless $install_name =~ /::/;
97     no strict;
98     local($^W) = 0;            # ``Subroutine $install_name redefined at ...''
99     *{$install_name} = $wrapper; # Install memoized version
100   }
101
102   $revmemotable{$wrapper} = "" . $cref; # Turn code ref into hash key
103
104   # These will be the caches
105   my %caches;
106   for my $context (qw(SCALAR LIST)) {
107     # suppress subsequent 'uninitialized value' warnings
108     $options{"${context}_CACHE"} ||= ''; 
109
110     my $cache_opt = $options{"${context}_CACHE"};
111     my @cache_opt_args;
112     if (ref $cache_opt) {
113       @cache_opt_args = @$cache_opt;
114       $cache_opt = shift @cache_opt_args;
115     }
116     if ($cache_opt eq 'FAULT') { # no cache
117       $caches{$context} = undef;
118     } elsif ($cache_opt eq 'HASH') { # user-supplied hash
119       my $cache = $cache_opt_args[0];
120       my $package = ref(tied %$cache);
121       if ($context eq 'LIST' && $scalar_only{$package}) {
122         croak("You can't use $package for LIST_CACHE because it can only store scalars");
123       }
124       $caches{$context} = $cache;
125     } elsif ($cache_opt eq '' ||  $IS_CACHE_TAG{$cache_opt}) {
126       # default is that we make up an in-memory hash
127       $caches{$context} = {};
128       # (this might get tied later, or MERGEd away)
129     } else {
130       croak "Unrecognized option to `${context}_CACHE': `$cache_opt' should be one of (@CONTEXT_TAGS); aborting";
131     }
132   }
133
134   # Perhaps I should check here that you didn't supply *both* merge
135   # options.  But if you did, it does do something reasonable: They
136   # both get merged to the same in-memory hash.
137   if ($options{SCALAR_CACHE} eq 'MERGE') {
138     $caches{SCALAR} = $caches{LIST};
139   } elsif ($options{LIST_CACHE} eq 'MERGE') {
140     $caches{LIST} = $caches{SCALAR};
141   }
142
143   # Now deal with the TIE options
144   {
145     my $context;
146     foreach $context (qw(SCALAR LIST)) {
147       # If the relevant option wasn't `TIE', this call does nothing.
148       _my_tie($context, $caches{$context}, $options);  # Croaks on failure
149     }
150   }
151   
152   # We should put some more stuff in here eventually.
153   # We've been saying that for serveral versions now.
154   # And you know what?  More stuff keeps going in!
155   $memotable{$cref} = 
156   {
157     O => $options,  # Short keys here for things we need to access frequently
158     N => $normalizer,
159     U => $cref,
160     MEMOIZED => $wrapper,
161     PACKAGE => $uppack,
162     NAME => $install_name,
163     S => $caches{SCALAR},
164     L => $caches{LIST},
165   };
166
167   $wrapper                      # Return just memoized version
168 }
169
170 # This function tries to load a tied hash class and tie the hash to it.
171 sub _my_tie {
172   my ($context, $hash, $options) = @_;
173   my $fullopt = $options->{"${context}_CACHE"};
174
175   # We already checked to make sure that this works.
176   my $shortopt = (ref $fullopt) ? $fullopt->[0] : $fullopt;
177   
178   return unless defined $shortopt && $shortopt eq 'TIE';
179   carp("TIE option to memoize() is deprecated; use HASH instead")
180       if $^W;
181
182   my @args = ref $fullopt ? @$fullopt : ();
183   shift @args;
184   my $module = shift @args;
185   if ($context eq 'LIST' && $scalar_only{$module}) {
186     croak("You can't use $module for LIST_CACHE because it can only store scalars");
187   }
188   my $modulefile = $module . '.pm';
189   $modulefile =~ s{::}{/}g;
190   eval { require $modulefile };
191   if ($@) {
192     croak "Memoize: Couldn't load hash tie module `$module': $@; aborting";
193   }
194   my $rc = (tie %$hash => $module, @args);
195   unless ($rc) {
196     croak "Memoize: Couldn't tie hash to `$module': $!; aborting";
197   }
198   1;
199 }
200
201 sub flush_cache {
202   my $func = _make_cref($_[0], scalar caller);
203   my $info = $memotable{$revmemotable{$func}};
204   die "$func not memoized" unless defined $info;
205   for my $context (qw(S L)) {
206     my $cache = $info->{$context};
207     if (tied %$cache && ! (tied %$cache)->can('CLEAR')) {
208       my $funcname = defined($info->{NAME}) ? 
209           "function $info->{NAME}" : "anonymous function $func";
210       my $context = {S => 'scalar', L => 'list'}->{$context};
211       croak "Tied cache hash for $context-context $funcname does not support flushing";
212     } else {
213       %$cache = ();
214     }
215   }
216 }
217
218 # This is the function that manages the memo tables.
219 sub _memoizer {
220   my $orig = shift;             # stringized version of ref to original func.
221   my $info = $memotable{$orig};
222   my $normalizer = $info->{N};
223   
224   my $argstr;
225   my $context = (wantarray() ? LIST : SCALAR);
226
227   if (defined $normalizer) { 
228     no strict;
229     if ($context == SCALAR) {
230       $argstr = &{$normalizer}(@_);
231     } elsif ($context == LIST) {
232       ($argstr) = &{$normalizer}(@_);
233     } else {
234       croak "Internal error \#41; context was neither LIST nor SCALAR\n";
235     }
236   } else {                      # Default normalizer
237     local $^W = 0;
238     $argstr = join chr(28),@_;  
239   }
240
241   if ($context == SCALAR) {
242     my $cache = $info->{S};
243     _crap_out($info->{NAME}, 'scalar') unless $cache;
244     if (exists $cache->{$argstr}) { 
245       return $cache->{$argstr};
246     } else {
247       my $val = &{$info->{U}}(@_);
248       # Scalars are considered to be lists; store appropriately
249       if ($info->{O}{SCALAR_CACHE} eq 'MERGE') {
250         $cache->{$argstr} = [$val];
251       } else {
252         $cache->{$argstr} = $val;
253       }
254       $val;
255     }
256   } elsif ($context == LIST) {
257     my $cache = $info->{L};
258     _crap_out($info->{NAME}, 'list') unless $cache;
259     if (exists $cache->{$argstr}) {
260       my $val = $cache->{$argstr};
261       # If LISTCONTEXT=>MERGE, then the function never returns lists,
262       # so we have a scalar value cached, so just return it straightaway:
263       return ($val) if $info->{O}{LIST_CACHE} eq 'MERGE';
264       # Maybe in a later version we can use a faster test.
265
266       # Otherwise, we cached an array containing the returned list:
267       return @$val;
268     } else {
269       my $q = $cache->{$argstr} = [&{$info->{U}}(@_)];
270       @$q;
271     }
272   } else {
273     croak "Internal error \#42; context was neither LIST nor SCALAR\n";
274   }
275 }
276
277 sub unmemoize {
278   my $f = shift;
279   my $uppack = caller;
280   my $cref = _make_cref($f, $uppack);
281
282   unless (exists $revmemotable{$cref}) {
283     croak "Could not unmemoize function `$f', because it was not memoized to begin with";
284   }
285   
286   my $tabent = $memotable{$revmemotable{$cref}};
287   unless (defined $tabent) {
288     croak "Could not figure out how to unmemoize function `$f'";
289   }
290   my $name = $tabent->{NAME};
291   if (defined $name) {
292     no strict;
293     local($^W) = 0;            # ``Subroutine $install_name redefined at ...''
294     *{$name} = $tabent->{U}; # Replace with original function
295   }
296   undef $memotable{$revmemotable{$cref}};
297   undef $revmemotable{$cref};
298
299   # This removes the last reference to the (possibly tied) memo tables
300   # my ($old_function, $memotabs) = @{$tabent}{'U','S','L'};
301   # undef $tabent; 
302
303 #  # Untie the memo tables if they were tied.
304 #  my $i;
305 #  for $i (0,1) {
306 #    if (tied %{$memotabs->[$i]}) {
307 #      warn "Untying hash #$i\n";
308 #      untie %{$memotabs->[$i]};
309 #    }
310 #  }
311
312   $tabent->{U};
313 }
314
315 sub _make_cref {
316   my $fn = shift;
317   my $uppack = shift;
318   my $cref;
319   my $name;
320
321   if (ref $fn eq 'CODE') {
322     $cref = $fn;
323   } elsif (! ref $fn) {
324     if ($fn =~ /::/) {
325       $name = $fn;
326     } else {
327       $name = $uppack . '::' . $fn;
328     }
329     no strict;
330     if (defined $name and !defined(&$name)) {
331       croak "Cannot operate on nonexistent function `$fn'";
332     }
333 #    $cref = \&$name;
334     $cref = *{$name}{CODE};
335   } else {
336     my $parent = (caller(1))[3]; # Function that called _make_cref
337     croak "Usage: argument 1 to `$parent' must be a function name or reference.\n";
338   }
339   $DEBUG and warn "${name}($fn) => $cref in _make_cref\n";
340   $cref;
341 }
342
343 sub _crap_out {
344   my ($funcname, $context) = @_;
345   if (defined $funcname) {
346     croak "Function `$funcname' called in forbidden $context context; faulting";
347   } else {
348     croak "Anonymous function called in forbidden $context context; faulting";
349   }
350 }
351
352 1;
353
354
355
356
357
358 =head1 NAME
359
360 Memoize - Make functions faster by trading space for time
361
362 =head1 SYNOPSIS
363
364         # This is the documentation for Memoize 1.01
365         use Memoize;
366         memoize('slow_function');
367         slow_function(arguments);    # Is faster than it was before
368
369
370 This is normally all you need to know.  However, many options are available:
371
372         memoize(function, options...);
373
374 Options include:
375
376         NORMALIZER => function
377         INSTALL => new_name
378
379         SCALAR_CACHE => 'MEMORY'
380         SCALAR_CACHE => ['HASH', \%cache_hash ]
381         SCALAR_CACHE => 'FAULT'
382         SCALAR_CACHE => 'MERGE'
383
384         LIST_CACHE => 'MEMORY'
385         LIST_CACHE => ['HASH', \%cache_hash ]
386         LIST_CACHE => 'FAULT'
387         LIST_CACHE => 'MERGE'
388
389 =head1 DESCRIPTION
390
391 `Memoizing' a function makes it faster by trading space for time.  It
392 does this by caching the return values of the function in a table.
393 If you call the function again with the same arguments, C<memoize>
394 jumps in and gives you the value out of the table, instead of letting
395 the function compute the value all over again.
396
397 Here is an extreme example.  Consider the Fibonacci sequence, defined
398 by the following function:
399
400         # Compute Fibonacci numbers
401         sub fib {
402           my $n = shift;
403           return $n if $n < 2;
404           fib($n-1) + fib($n-2);
405         }
406
407 This function is very slow.  Why?  To compute fib(14), it first wants
408 to compute fib(13) and fib(12), and add the results.  But to compute
409 fib(13), it first has to compute fib(12) and fib(11), and then it
410 comes back and computes fib(12) all over again even though the answer
411 is the same.  And both of the times that it wants to compute fib(12),
412 it has to compute fib(11) from scratch, and then it has to do it
413 again each time it wants to compute fib(13).  This function does so
414 much recomputing of old results that it takes a really long time to
415 run---fib(14) makes 1,200 extra recursive calls to itself, to compute
416 and recompute things that it already computed.
417
418 This function is a good candidate for memoization.  If you memoize the
419 `fib' function above, it will compute fib(14) exactly once, the first
420 time it needs to, and then save the result in a table.  Then if you
421 ask for fib(14) again, it gives you the result out of the table.
422 While computing fib(14), instead of computing fib(12) twice, it does
423 it once; the second time it needs the value it gets it from the table.
424 It doesn't compute fib(11) four times; it computes it once, getting it
425 from the table the next three times.  Instead of making 1,200
426 recursive calls to `fib', it makes 15.  This makes the function about
427 150 times faster.
428
429 You could do the memoization yourself, by rewriting the function, like
430 this:
431
432         # Compute Fibonacci numbers, memoized version
433         { my @fib;
434           sub fib {
435             my $n = shift;
436             return $fib[$n] if defined $fib[$n];
437             return $fib[$n] = $n if $n < 2;
438             $fib[$n] = fib($n-1) + fib($n-2);
439           }
440         }
441
442 Or you could use this module, like this:
443
444         use Memoize;
445         memoize('fib');
446
447         # Rest of the fib function just like the original version.
448
449 This makes it easy to turn memoizing on and off.
450
451 Here's an even simpler example: I wrote a simple ray tracer; the
452 program would look in a certain direction, figure out what it was
453 looking at, and then convert the `color' value (typically a string
454 like `red') of that object to a red, green, and blue pixel value, like
455 this:
456
457     for ($direction = 0; $direction < 300; $direction++) {
458       # Figure out which object is in direction $direction
459       $color = $object->{color};
460       ($r, $g, $b) = @{&ColorToRGB($color)};
461       ...
462     }
463
464 Since there are relatively few objects in a picture, there are only a
465 few colors, which get looked up over and over again.  Memoizing
466 C<ColorToRGB> sped up the program by several percent.
467
468 =head1 DETAILS
469
470 This module exports exactly one function, C<memoize>.  The rest of the
471 functions in this package are None of Your Business.
472
473 You should say
474
475         memoize(function)
476
477 where C<function> is the name of the function you want to memoize, or
478 a reference to it.  C<memoize> returns a reference to the new,
479 memoized version of the function, or C<undef> on a non-fatal error.
480 At present, there are no non-fatal errors, but there might be some in
481 the future.
482
483 If C<function> was the name of a function, then C<memoize> hides the
484 old version and installs the new memoized version under the old name,
485 so that C<&function(...)> actually invokes the memoized version.
486
487 =head1 OPTIONS
488
489 There are some optional options you can pass to C<memoize> to change
490 the way it behaves a little.  To supply options, invoke C<memoize>
491 like this:
492
493         memoize(function, NORMALIZER => function,
494                           INSTALL => newname,
495                           SCALAR_CACHE => option,
496                           LIST_CACHE => option
497                          );
498
499 Each of these options is optional; you can include some, all, or none
500 of them.
501
502 =head2 INSTALL
503
504 If you supply a function name with C<INSTALL>, memoize will install
505 the new, memoized version of the function under the name you give.
506 For example, 
507
508         memoize('fib', INSTALL => 'fastfib')
509
510 installs the memoized version of C<fib> as C<fastfib>; without the
511 C<INSTALL> option it would have replaced the old C<fib> with the
512 memoized version.  
513
514 To prevent C<memoize> from installing the memoized version anywhere, use
515 C<INSTALL =E<gt> undef>.
516
517 =head2 NORMALIZER
518
519 Suppose your function looks like this:
520
521         # Typical call: f('aha!', A => 11, B => 12);
522         sub f {
523           my $a = shift;
524           my %hash = @_;
525           $hash{B} ||= 2;  # B defaults to 2
526           $hash{C} ||= 7;  # C defaults to 7
527
528           # Do something with $a, %hash
529         }
530
531 Now, the following calls to your function are all completely equivalent:
532
533         f(OUCH);
534         f(OUCH, B => 2);
535         f(OUCH, C => 7);
536         f(OUCH, B => 2, C => 7);
537         f(OUCH, C => 7, B => 2);
538         (etc.)
539
540 However, unless you tell C<Memoize> that these calls are equivalent,
541 it will not know that, and it will compute the values for these
542 invocations of your function separately, and store them separately.
543
544 To prevent this, supply a C<NORMALIZER> function that turns the
545 program arguments into a string in a way that equivalent arguments
546 turn into the same string.  A C<NORMALIZER> function for C<f> above
547 might look like this:
548
549         sub normalize_f {
550           my $a = shift;
551           my %hash = @_;
552           $hash{B} ||= 2;
553           $hash{C} ||= 7;
554
555           join(',', $a, map ($_ => $hash{$_}) sort keys %hash);
556         }
557
558 Each of the argument lists above comes out of the C<normalize_f>
559 function looking exactly the same, like this:
560
561         OUCH,B,2,C,7
562
563 You would tell C<Memoize> to use this normalizer this way:
564
565         memoize('f', NORMALIZER => 'normalize_f');
566
567 C<memoize> knows that if the normalized version of the arguments is
568 the same for two argument lists, then it can safely look up the value
569 that it computed for one argument list and return it as the result of
570 calling the function with the other argument list, even if the
571 argument lists look different.
572
573 The default normalizer just concatenates the arguments with character
574 28 in between.  (In ASCII, this is called FS or control-\.)  This
575 always works correctly for functions with only one string argument,
576 and also when the arguments never contain character 28.  However, it
577 can confuse certain argument lists:
578
579         normalizer("a\034", "b")
580         normalizer("a", "\034b")
581         normalizer("a\034\034b")
582
583 for example.
584
585 Since hash keys are strings, the default normalizer will not
586 distinguish between C<undef> and the empty string.  It also won't work
587 when the function's arguments are references.  For example, consider a
588 function C<g> which gets two arguments: A number, and a reference to
589 an array of numbers:
590
591         g(13, [1,2,3,4,5,6,7]);
592
593 The default normalizer will turn this into something like
594 C<"13\034ARRAY(0x436c1f)">.  That would be all right, except that a
595 subsequent array of numbers might be stored at a different location
596 even though it contains the same data.  If this happens, C<Memoize>
597 will think that the arguments are different, even though they are
598 equivalent.  In this case, a normalizer like this is appropriate:
599
600         sub normalize { join ' ', $_[0], @{$_[1]} }
601
602 For the example above, this produces the key "13 1 2 3 4 5 6 7".
603
604 Another use for normalizers is when the function depends on data other
605 than those in its arguments.  Suppose you have a function which
606 returns a value which depends on the current hour of the day:
607
608         sub on_duty {
609           my ($problem_type) = @_;
610           my $hour = (localtime)[2];
611           open my $fh, "$DIR/$problem_type" or die...;
612           my $line;
613           while ($hour-- > 0)
614             $line = <$fh>;
615           } 
616           return $line;
617         }
618
619 At 10:23, this function generates the 10th line of a data file; at
620 3:45 PM it generates the 15th line instead.  By default, C<Memoize>
621 will only see the $problem_type argument.  To fix this, include the
622 current hour in the normalizer:
623
624         sub normalize { join ' ', (localtime)[2], @_ }
625
626 The calling context of the function (scalar or list context) is
627 propagated to the normalizer.  This means that if the memoized
628 function will treat its arguments differently in list context than it
629 would in scalar context, you can have the normalizer function select
630 its behavior based on the results of C<wantarray>.  Even if called in
631 a list context, a normalizer should still return a single string.
632
633 =head2 C<SCALAR_CACHE>, C<LIST_CACHE>
634
635 Normally, C<Memoize> caches your function's return values into an
636 ordinary Perl hash variable.  However, you might like to have the
637 values cached on the disk, so that they persist from one run of your
638 program to the next, or you might like to associate some other
639 interesting semantics with the cached values.
640
641 There's a slight complication under the hood of C<Memoize>: There are
642 actually I<two> caches, one for scalar values and one for list values.
643 When your function is called in scalar context, its return value is
644 cached in one hash, and when your function is called in list context,
645 its value is cached in the other hash.  You can control the caching
646 behavior of both contexts independently with these options.
647
648 The argument to C<LIST_CACHE> or C<SCALAR_CACHE> must either be one of
649 the following four strings:
650
651         MEMORY
652         FAULT
653         MERGE
654         HASH
655
656 or else it must be a reference to a list whose first element is one of
657 these four strings, such as C<[HASH, arguments...]>.
658
659 =over 4
660
661 =item C<MEMORY>
662
663 C<MEMORY> means that return values from the function will be cached in
664 an ordinary Perl hash variable.  The hash variable will not persist
665 after the program exits.  This is the default.
666
667 =item C<HASH>
668
669 C<HASH> allows you to specify that a particular hash that you supply
670 will be used as the cache.  You can tie this hash beforehand to give
671 it any behavior you want.
672
673 A tied hash can have any semantics at all.  It is typically tied to an
674 on-disk database, so that cached values are stored in the database and
675 retrieved from it again when needed, and the disk file typically
676 persists after your program has exited.  See C<perltie> for more
677 complete details about C<tie>.
678
679 A typical example is:
680
681         use DB_File;
682         tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666;
683         memoize 'function', SCALAR_CACHE => [HASH => \%cache];
684
685 This has the effect of storing the cache in a C<DB_File> database
686 whose name is in C<$filename>.  The cache will persist after the
687 program has exited.  Next time the program runs, it will find the
688 cache already populated from the previous run of the program.  Or you
689 can forcibly populate the cache by constructing a batch program that
690 runs in the background and populates the cache file.  Then when you
691 come to run your real program the memoized function will be fast
692 because all its results have been precomputed.
693
694 =item C<TIE>
695
696 This option is no longer supported.  It is still documented only to
697 aid in the debugging of old programs that use it.  Old programs should
698 be converted to use the C<HASH> option instead.
699
700         memoize ... [TIE, PACKAGE, ARGS...]
701
702 is merely a shortcut for
703
704         require PACKAGE;
705         { my %cache;
706           tie %cache, PACKAGE, ARGS...;
707         }
708         memoize ... [HASH => \%cache];
709
710 =item C<FAULT>
711
712 C<FAULT> means that you never expect to call the function in scalar
713 (or list) context, and that if C<Memoize> detects such a call, it
714 should abort the program.  The error message is one of
715
716         `foo' function called in forbidden list context at line ...
717         `foo' function called in forbidden scalar context at line ...
718
719 =item C<MERGE>
720
721 C<MERGE> normally means the function does not distinguish between list
722 and sclar context, and that return values in both contexts should be
723 stored together.  C<LIST_CACHE =E<gt> MERGE> means that list context
724 return values should be stored in the same hash that is used for
725 scalar context returns, and C<SCALAR_CACHE =E<gt> MERGE> means the
726 same, mutatis mutandis.  It is an error to specify C<MERGE> for both,
727 but it probably does something useful.
728
729 Consider this function:
730
731         sub pi { 3; }
732
733 Normally, the following code will result in two calls to C<pi>:
734
735     $x = pi();
736     ($y) = pi();
737     $z = pi();
738
739 The first call caches the value C<3> in the scalar cache; the second
740 caches the list C<(3)> in the list cache.  The third call doesn't call
741 the real C<pi> function; it gets the value from the scalar cache.
742
743 Obviously, the second call to C<pi> is a waste of time, and storing
744 its return value is a waste of space.  Specifying C<LIST_CACHE =E<gt>
745 MERGE> will make C<memoize> use the same cache for scalar and list
746 context return values, so that the second call uses the scalar cache
747 that was populated by the first call.  C<pi> ends up being called only
748 once, and both subsequent calls return C<3> from the cache, regardless
749 of the calling context.
750
751 Another use for C<MERGE> is when you want both kinds of return values
752 stored in the same disk file; this saves you from having to deal with
753 two disk files instead of one.  You can use a normalizer function to
754 keep the two sets of return values separate.  For example:
755
756         tie my %cache => 'MLDBM', 'DB_File', $filename, ...;
757
758         memoize 'myfunc',
759           NORMALIZER => 'n',
760           SCALAR_CACHE => [HASH => \%cache],
761           LIST_CACHE => MERGE,
762         ;
763
764         sub n {
765           my $context = wantarray() ? 'L' : 'S';
766           # ... now compute the hash key from the arguments ...
767           $hashkey = "$context:$hashkey";
768         }
769
770 This normalizer function will store scalar context return values in
771 the disk file under keys that begin with C<S:>, and list context
772 return values under keys that begin with C<L:>.
773
774 =back
775
776 =head1 OTHER FACILITIES
777
778 =head2 C<unmemoize>
779
780 There's an C<unmemoize> function that you can import if you want to.
781 Why would you want to?  Here's an example: Suppose you have your cache
782 tied to a DBM file, and you want to make sure that the cache is
783 written out to disk if someone interrupts the program.  If the program
784 exits normally, this will happen anyway, but if someone types
785 control-C or something then the program will terminate immediately
786 without synchronizing the database.  So what you can do instead is
787
788     $SIG{INT} = sub { unmemoize 'function' };
789
790 C<unmemoize> accepts a reference to, or the name of a previously
791 memoized function, and undoes whatever it did to provide the memoized
792 version in the first place, including making the name refer to the
793 unmemoized version if appropriate.  It returns a reference to the
794 unmemoized version of the function.
795
796 If you ask it to unmemoize a function that was never memoized, it
797 croaks.
798
799 =head2 C<flush_cache>
800
801 C<flush_cache(function)> will flush out the caches, discarding I<all>
802 the cached data.  The argument may be a function name or a reference
803 to a function.  For finer control over when data is discarded or
804 expired, see the documentation for C<Memoize::Expire>, included in
805 this package.
806
807 Note that if the cache is a tied hash, C<flush_cache> will attempt to
808 invoke the C<CLEAR> method on the hash.  If there is no C<CLEAR>
809 method, this will cause a run-time error.
810
811 An alternative approach to cache flushing is to use the C<HASH> option
812 (see above) to request that C<Memoize> use a particular hash variable
813 as its cache.  Then you can examine or modify the hash at any time in
814 any way you desire.  You may flush the cache by using C<%hash = ()>. 
815
816 =head1 CAVEATS
817
818 Memoization is not a cure-all:
819
820 =over 4
821
822 =item *
823
824 Do not memoize a function whose behavior depends on program
825 state other than its own arguments, such as global variables, the time
826 of day, or file input.  These functions will not produce correct
827 results when memoized.  For a particularly easy example:
828
829         sub f {
830           time;
831         }
832
833 This function takes no arguments, and as far as C<Memoize> is
834 concerned, it always returns the same result.  C<Memoize> is wrong, of
835 course, and the memoized version of this function will call C<time> once
836 to get the current time, and it will return that same time
837 every time you call it after that.
838
839 =item *
840
841 Do not memoize a function with side effects.
842
843         sub f {
844           my ($a, $b) = @_;
845           my $s = $a + $b;
846           print "$a + $b = $s.\n";
847         }
848
849 This function accepts two arguments, adds them, and prints their sum.
850 Its return value is the numuber of characters it printed, but you
851 probably didn't care about that.  But C<Memoize> doesn't understand
852 that.  If you memoize this function, you will get the result you
853 expect the first time you ask it to print the sum of 2 and 3, but
854 subsequent calls will return 1 (the return value of
855 C<print>) without actually printing anything.
856
857 =item *
858
859 Do not memoize a function that returns a data structure that is
860 modified by its caller.
861
862 Consider these functions:  C<getusers> returns a list of users somehow,
863 and then C<main> throws away the first user on the list and prints the
864 rest:
865
866         sub main {
867           my $userlist = getusers();
868           shift @$userlist;
869           foreach $u (@$userlist) {
870             print "User $u\n";
871           }
872         }
873
874         sub getusers {
875           my @users;
876           # Do something to get a list of users;
877           \@users;  # Return reference to list.
878         }
879
880 If you memoize C<getusers> here, it will work right exactly once.  The
881 reference to the users list will be stored in the memo table.  C<main>
882 will discard the first element from the referenced list.  The next
883 time you invoke C<main>, C<Memoize> will not call C<getusers>; it will
884 just return the same reference to the same list it got last time.  But
885 this time the list has already had its head removed; C<main> will
886 erroneously remove another element from it.  The list will get shorter
887 and shorter every time you call C<main>.
888
889 Similarly, this:
890
891         $u1 = getusers();    
892         $u2 = getusers();    
893         pop @$u1;
894
895 will modify $u2 as well as $u1, because both variables are references
896 to the same array.  Had C<getusers> not been memoized, $u1 and $u2
897 would have referred to different arrays.
898
899 =item * 
900
901 Do not memoize a very simple function.
902
903 Recently someone mentioned to me that the Memoize module made his
904 program run slower instead of faster.  It turned out that he was
905 memoizing the following function:
906
907     sub square {
908       $_[0] * $_[0];
909     }
910
911 I pointed out that C<Memoize> uses a hash, and that looking up a
912 number in the hash is necessarily going to take a lot longer than a
913 single multiplication.  There really is no way to speed up the
914 C<square> function.
915
916 Memoization is not magical.
917
918 =back
919
920 =head1 PERSISTENT CACHE SUPPORT
921
922 You can tie the cache tables to any sort of tied hash that you want
923 to, as long as it supports C<TIEHASH>, C<FETCH>, C<STORE>, and
924 C<EXISTS>.  For example,
925
926         tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666;
927         memoize 'function', SCALAR_CACHE => [HASH => \%cache];
928
929 works just fine.  For some storage methods, you need a little glue.
930
931 C<SDBM_File> doesn't supply an C<EXISTS> method, so included in this
932 package is a glue module called C<Memoize::SDBM_File> which does
933 provide one.  Use this instead of plain C<SDBM_File> to store your
934 cache table on disk in an C<SDBM_File> database:
935
936         tie my %cache => 'Memoize::SDBM_File', $filename, O_RDWR|O_CREAT, 0666;
937         memoize 'function', SCALAR_CACHE => [HASH => \%cache];
938
939 C<NDBM_File> has the same problem and the same solution.  (Use
940 C<Memoize::NDBM_File instead of plain NDBM_File.>)
941
942 C<Storable> isn't a tied hash class at all.  You can use it to store a
943 hash to disk and retrieve it again, but you can't modify the hash while
944 it's on the disk.  So if you want to store your cache table in a
945 C<Storable> database, use C<Memoize::Storable>, which puts a hashlike
946 front-end onto C<Storable>.  The hash table is actually kept in
947 memory, and is loaded from your C<Storable> file at the time you
948 memoize the function, and stored back at the time you unmemoize the
949 function (or when your program exits):
950
951         tie my %cache => 'Memoize::Storable', $filename;
952         memoize 'function', SCALAR_CACHE => [HASH => \%cache];
953
954         tie my %cache => 'Memoize::Storable', $filename, 'nstore';
955         memoize 'function', SCALAR_CACHE => [HASH => \%cache];
956
957 Include the `nstore' option to have the C<Storable> database written
958 in `network order'.  (See L<Storable> for more details about this.)
959
960 The C<flush_cache()> function will raise a run-time error unless the
961 tied package provides a C<CLEAR> method.
962
963 =head1 EXPIRATION SUPPORT
964
965 See Memoize::Expire, which is a plug-in module that adds expiration
966 functionality to Memoize.  If you don't like the kinds of policies
967 that Memoize::Expire implements, it is easy to write your own plug-in
968 module to implement whatever policy you desire.  Memoize comes with
969 several examples.  An expiration manager that implements a LRU policy
970 is available on CPAN as Memoize::ExpireLRU.
971
972 =head1 BUGS
973
974 The test suite is much better, but always needs improvement.
975
976 There is some problem with the way C<goto &f> works under threaded
977 Perl, perhaps because of the lexical scoping of C<@_>.  This is a bug
978 in Perl, and until it is resolved, memoized functions will see a
979 slightly different C<caller()> and will perform a little more slowly
980 on threaded perls than unthreaded perls.
981
982 Some versions of C<DB_File> won't let you store data under a key of
983 length 0.  That means that if you have a function C<f> which you
984 memoized and the cache is in a C<DB_File> database, then the value of
985 C<f()> (C<f> called with no arguments) will not be memoized.  If this
986 is a big problem, you can supply a normalizer function that prepends
987 C<"x"> to every key.
988
989 =head1 MAILING LIST
990
991 To join a very low-traffic mailing list for announcements about
992 C<Memoize>, send an empty note to C<mjd-perl-memoize-request@plover.com>.
993
994 =head1 AUTHOR
995
996 Mark-Jason Dominus (C<mjd-perl-memoize+@plover.com>), Plover Systems co.
997
998 See the C<Memoize.pm> Page at http://www.plover.com/~mjd/perl/Memoize/
999 for news and upgrades.  Near this page, at
1000 http://www.plover.com/~mjd/perl/MiniMemoize/ there is an article about
1001 memoization and about the internals of Memoize that appeared in The
1002 Perl Journal, issue #13.  (This article is also included in the
1003 Memoize distribution as `article.html'.)
1004
1005 My upcoming book will discuss memoization (and many other fascinating
1006 topics) in tremendous detail.  It will be published by Morgan Kaufmann
1007 in 2002, possibly under the title I<Perl Advanced Techniques
1008 Handbook>.  It will also be available on-line for free.  For more
1009 information, visit http://perl.plover.com/book/ .
1010
1011 To join a mailing list for announcements about C<Memoize>, send an
1012 empty message to C<mjd-perl-memoize-request@plover.com>.  This mailing
1013 list is for announcements only and has extremely low traffic---about
1014 two messages per year.
1015
1016 =head1 COPYRIGHT AND LICENSE
1017
1018 Copyright 1998, 1999, 2000, 2001  by Mark Jason Dominus
1019
1020 This library is free software; you may redistribute it and/or modify
1021 it under the same terms as Perl itself.
1022
1023 =head1 THANK YOU
1024
1025 Many thanks to Jonathan Roy for bug reports and suggestions, to
1026 Michael Schwern for other bug reports and patches, to Mike Cariaso for
1027 helping me to figure out the Right Thing to Do About Expiration, to
1028 Joshua Gerth, Joshua Chamas, Jonathan Roy (again), Mark D. Anderson,
1029 and Andrew Johnson for more suggestions about expiration, to Brent
1030 Powers for the Memoize::ExpireLRU module, to Ariel Scolnicov for
1031 delightful messages about the Fibonacci function, to Dion Almaer for
1032 thought-provoking suggestions about the default normalizer, to Walt
1033 Mankowski and Kurt Starsinic for much help investigating problems
1034 under threaded Perl, to Alex Dudkevich for reporting the bug in
1035 prototyped functions and for checking my patch, to Tony Bass for many
1036 helpful suggestions, to Jonathan Roy (again) for finding a use for
1037 C<unmemoize()>, to Philippe Verdret for enlightening discussion of
1038 C<Hook::PrePostCall>, to Nat Torkington for advice I ignored, to Chris
1039 Nandor for portability advice, to Randal Schwartz for suggesting the
1040 'C<flush_cache> function, and to Jenda Krynicky for being a light in
1041 the world.
1042
1043 Special thanks to Jarkko Hietaniemi, the 5.8.0 pumpking, for including
1044 this module in the core and for his patient and helpful guidance
1045 during the integration process.
1046
1047 =cut