extra code in pp_concat, Take 2
[p5sagit/p5-mst-13.2.git] / lib / Memoize.pm
CommitLineData
a0cb3900 1# -*- mode: perl; perl-indent-level: 2; -*-
2# Memoize.pm
3#
4# Transparent memoization of idempotent functions
5#
899dc88a 6# Copyright 1998, 1999, 2000, 2001 M-J. Dominus.
a0cb3900 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#
484fdf61 11# Version 1.01 $Revision: 1.18 $ $Date: 2001/06/24 17:16:47 $
a0cb3900 12
13package Memoize;
97b11a47 14$VERSION = '1.01_01';
a0cb3900 15
16# Compile-time constants
17sub SCALAR () { 0 }
18sub LIST () { 1 }
19
20
21#
22# Usage memoize(functionname/ref,
23# { NORMALIZER => coderef, INSTALL => name,
24# LIST_CACHE => descriptor, SCALAR_CACHE => descriptor }
25#
26
27use Carp;
28use Exporter;
29use vars qw($DEBUG);
899dc88a 30use Config; # Dammit.
a0cb3900 31@ISA = qw(Exporter);
32@EXPORT = qw(memoize);
33@EXPORT_OK = qw(unmemoize flush_cache);
34use strict;
35
36my %memotable;
37my %revmemotable;
38my @CONTEXT_TAGS = qw(MERGE TIE MEMORY FAULT HASH);
39my %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
44my %scalar_only = map {($_ => 1)} qw(DB_File GDBM_File SDBM_File ODBM_File NDBM_File);
45
46sub 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
899dc88a 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; }";
a0cb3900 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
899dc88a 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;
a0cb3900 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.
171sub _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';
5189e6fe 179 carp("TIE option to memoize() is deprecated; use HASH instead")
484fdf61 180 if $^W;
a0cb3900 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 }
a0cb3900 194 my $rc = (tie %$hash => $module, @args);
195 unless ($rc) {
899dc88a 196 croak "Memoize: Couldn't tie hash to `$module': $!; aborting";
a0cb3900 197 }
198 1;
199}
200
201sub 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.
219sub _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
899dc88a 237 local $^W = 0;
238 $argstr = join chr(28),@_;
a0cb3900 239 }
240
241 if ($context == SCALAR) {
242 my $cache = $info->{S};
899dc88a 243 _crap_out($info->{NAME}, 'scalar') unless $cache;
a0cb3900 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};
899dc88a 258 _crap_out($info->{NAME}, 'list') unless $cache;
a0cb3900 259 if (exists $cache->{$argstr}) {
260 my $val = $cache->{$argstr};
a0cb3900 261 # If LISTCONTEXT=>MERGE, then the function never returns lists,
899dc88a 262 # so we have a scalar value cached, so just return it straightaway:
a0cb3900 263 return ($val) if $info->{O}{LIST_CACHE} eq 'MERGE';
899dc88a 264 # Maybe in a later version we can use a faster test.
265
266 # Otherwise, we cached an array containing the returned list:
a0cb3900 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
277sub 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
315sub _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
343sub _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
3521;
353
354
355
356
357
358=head1 NAME
359
5189e6fe 360Memoize - Make functions faster by trading space for time
a0cb3900 361
362=head1 SYNOPSIS
363
484fdf61 364 # This is the documentation for Memoize 1.01
a0cb3900 365 use Memoize;
366 memoize('slow_function');
367 slow_function(arguments); # Is faster than it was before
368
369
370This is normally all you need to know. However, many options are available:
371
372 memoize(function, options...);
373
374Options 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
392does this by caching the return values of the function in a table.
393If you call the function again with the same arguments, C<memoize>
3d4a255c 394jumps in and gives you the value out of the table, instead of letting
a0cb3900 395the function compute the value all over again.
396
397Here is an extreme example. Consider the Fibonacci sequence, defined
398by 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
407This function is very slow. Why? To compute fib(14), it first wants
408to compute fib(13) and fib(12), and add the results. But to compute
409fib(13), it first has to compute fib(12) and fib(11), and then it
410comes back and computes fib(12) all over again even though the answer
411is the same. And both of the times that it wants to compute fib(12),
412it has to compute fib(11) from scratch, and then it has to do it
413again each time it wants to compute fib(13). This function does so
414much recomputing of old results that it takes a really long time to
415run---fib(14) makes 1,200 extra recursive calls to itself, to compute
416and recompute things that it already computed.
417
418This function is a good candidate for memoization. If you memoize the
419`fib' function above, it will compute fib(14) exactly once, the first
420time it needs to, and then save the result in a table. Then if you
421ask for fib(14) again, it gives you the result out of the table.
422While computing fib(14), instead of computing fib(12) twice, it does
423it once; the second time it needs the value it gets it from the table.
424It doesn't compute fib(11) four times; it computes it once, getting it
425from the table the next three times. Instead of making 1,200
426recursive calls to `fib', it makes 15. This makes the function about
427150 times faster.
428
429You could do the memoization yourself, by rewriting the function, like
430this:
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
442Or 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
449This makes it easy to turn memoizing on and off.
450
451Here's an even simpler example: I wrote a simple ray tracer; the
452program would look in a certain direction, figure out what it was
453looking at, and then convert the `color' value (typically a string
454like `red') of that object to a red, green, and blue pixel value, like
455this:
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
464Since there are relatively few objects in a picture, there are only a
465few colors, which get looked up over and over again. Memoizing
5189e6fe 466C<ColorToRGB> sped up the program by several percent.
a0cb3900 467
468=head1 DETAILS
469
470This module exports exactly one function, C<memoize>. The rest of the
471functions in this package are None of Your Business.
472
473You should say
474
475 memoize(function)
476
477where C<function> is the name of the function you want to memoize, or
478a reference to it. C<memoize> returns a reference to the new,
479memoized version of the function, or C<undef> on a non-fatal error.
480At present, there are no non-fatal errors, but there might be some in
481the future.
482
483If C<function> was the name of a function, then C<memoize> hides the
484old version and installs the new memoized version under the old name,
485so that C<&function(...)> actually invokes the memoized version.
486
487=head1 OPTIONS
488
489There are some optional options you can pass to C<memoize> to change
490the way it behaves a little. To supply options, invoke C<memoize>
491like this:
492
493 memoize(function, NORMALIZER => function,
494 INSTALL => newname,
495 SCALAR_CACHE => option,
496 LIST_CACHE => option
497 );
498
499Each of these options is optional; you can include some, all, or none
500of them.
501
502=head2 INSTALL
503
504If you supply a function name with C<INSTALL>, memoize will install
505the new, memoized version of the function under the name you give.
506For example,
507
508 memoize('fib', INSTALL => 'fastfib')
509
510installs the memoized version of C<fib> as C<fastfib>; without the
511C<INSTALL> option it would have replaced the old C<fib> with the
512memoized version.
513
514To prevent C<memoize> from installing the memoized version anywhere, use
515C<INSTALL =E<gt> undef>.
516
517=head2 NORMALIZER
518
519Suppose 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
531Now, 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
540However, unless you tell C<Memoize> that these calls are equivalent,
541it will not know that, and it will compute the values for these
542invocations of your function separately, and store them separately.
543
544To prevent this, supply a C<NORMALIZER> function that turns the
545program arguments into a string in a way that equivalent arguments
546turn into the same string. A C<NORMALIZER> function for C<f> above
547might look like this:
548
549 sub normalize_f {
550 my $a = shift;
551 my %hash = @_;
552 $hash{B} ||= 2;
553 $hash{C} ||= 7;
554
3d4a255c 555 join(',', $a, map ($_ => $hash{$_}) sort keys %hash);
a0cb3900 556 }
557
558Each of the argument lists above comes out of the C<normalize_f>
559function looking exactly the same, like this:
560
3d4a255c 561 OUCH,B,2,C,7
a0cb3900 562
563You would tell C<Memoize> to use this normalizer this way:
564
565 memoize('f', NORMALIZER => 'normalize_f');
566
567C<memoize> knows that if the normalized version of the arguments is
568the same for two argument lists, then it can safely look up the value
569that it computed for one argument list and return it as the result of
570calling the function with the other argument list, even if the
571argument lists look different.
572
3d4a255c 573The default normalizer just concatenates the arguments with character
57428 in between. (In ASCII, this is called FS or control-\.) This
575always works correctly for functions with only one string argument,
576and also when the arguments never contain character 28. However, it
577can confuse certain argument lists:
a0cb3900 578
579 normalizer("a\034", "b")
580 normalizer("a", "\034b")
581 normalizer("a\034\034b")
582
3d4a255c 583for example.
a0cb3900 584
899dc88a 585Since hash keys are strings, the default normalizer will not
586distinguish between C<undef> and the empty string. It also won't work
3d4a255c 587when the function's arguments are references. For example, consider a
588function C<g> which gets two arguments: A number, and a reference to
899dc88a 589an array of numbers:
a0cb3900 590
591 g(13, [1,2,3,4,5,6,7]);
592
593The default normalizer will turn this into something like
3d4a255c 594C<"13\034ARRAY(0x436c1f)">. That would be all right, except that a
a0cb3900 595subsequent array of numbers might be stored at a different location
596even though it contains the same data. If this happens, C<Memoize>
597will think that the arguments are different, even though they are
598equivalent. In this case, a normalizer like this is appropriate:
599
600 sub normalize { join ' ', $_[0], @{$_[1]} }
601
602For the example above, this produces the key "13 1 2 3 4 5 6 7".
603
604Another use for normalizers is when the function depends on data other
605than those in its arguments. Suppose you have a function which
606returns 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
3d4a255c 619At 10:23, this function generates the 10th line of a data file; at
a0cb3900 6203:45 PM it generates the 15th line instead. By default, C<Memoize>
621will only see the $problem_type argument. To fix this, include the
622current hour in the normalizer:
623
624 sub normalize { join ' ', (localtime)[2], @_ }
625
626The calling context of the function (scalar or list context) is
627propagated to the normalizer. This means that if the memoized
628function will treat its arguments differently in list context than it
629would in scalar context, you can have the normalizer function select
630its behavior based on the results of C<wantarray>. Even if called in
631a list context, a normalizer should still return a single string.
632
633=head2 C<SCALAR_CACHE>, C<LIST_CACHE>
634
635Normally, C<Memoize> caches your function's return values into an
636ordinary Perl hash variable. However, you might like to have the
637values cached on the disk, so that they persist from one run of your
638program to the next, or you might like to associate some other
3d4a255c 639interesting semantics with the cached values.
a0cb3900 640
641There's a slight complication under the hood of C<Memoize>: There are
642actually I<two> caches, one for scalar values and one for list values.
643When your function is called in scalar context, its return value is
644cached in one hash, and when your function is called in list context,
645its value is cached in the other hash. You can control the caching
646behavior of both contexts independently with these options.
647
648The argument to C<LIST_CACHE> or C<SCALAR_CACHE> must either be one of
649the following four strings:
650
651 MEMORY
652 FAULT
653 MERGE
3d4a255c 654 HASH
a0cb3900 655
656or else it must be a reference to a list whose first element is one of
657these four strings, such as C<[HASH, arguments...]>.
658
659=over 4
660
661=item C<MEMORY>
662
663C<MEMORY> means that return values from the function will be cached in
664an ordinary Perl hash variable. The hash variable will not persist
665after the program exits. This is the default.
666
667=item C<HASH>
668
669C<HASH> allows you to specify that a particular hash that you supply
670will be used as the cache. You can tie this hash beforehand to give
671it any behavior you want.
672
673A tied hash can have any semantics at all. It is typically tied to an
674on-disk database, so that cached values are stored in the database and
675retrieved from it again when needed, and the disk file typically
676persists after your program has exited. See C<perltie> for more
677complete details about C<tie>.
678
679A typical example is:
680
3d4a255c 681 use DB_File;
a0cb3900 682 tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666;
683 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
684
685This has the effect of storing the cache in a C<DB_File> database
686whose name is in C<$filename>. The cache will persist after the
687program has exited. Next time the program runs, it will find the
688cache already populated from the previous run of the program. Or you
689can forcibly populate the cache by constructing a batch program that
690runs in the background and populates the cache file. Then when you
691come to run your real program the memoized function will be fast
692because all its results have been precomputed.
693
694=item C<TIE>
695
5189e6fe 696This option is no longer supported. It is still documented only to
697aid in the debugging of old programs that use it. Old programs should
698be converted to use the C<HASH> option instead.
a0cb3900 699
3d4a255c 700 memoize ... [TIE, PACKAGE, ARGS...]
a0cb3900 701
702is merely a shortcut for
703
3d4a255c 704 require PACKAGE;
5189e6fe 705 { my %cache;
706 tie %cache, PACKAGE, ARGS...;
707 }
a0cb3900 708 memoize ... [HASH => \%cache];
709
a0cb3900 710=item C<FAULT>
711
712C<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
714should 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
721C<MERGE> normally means the function does not distinguish between list
722and sclar context, and that return values in both contexts should be
723stored together. C<LIST_CACHE =E<gt> MERGE> means that list context
724return values should be stored in the same hash that is used for
725scalar context returns, and C<SCALAR_CACHE =E<gt> MERGE> means the
726same, mutatis mutandis. It is an error to specify C<MERGE> for both,
727but it probably does something useful.
728
729Consider this function:
730
731 sub pi { 3; }
732
733Normally, the following code will result in two calls to C<pi>:
734
735 $x = pi();
736 ($y) = pi();
737 $z = pi();
738
739The first call caches the value C<3> in the scalar cache; the second
740caches the list C<(3)> in the list cache. The third call doesn't call
741the real C<pi> function; it gets the value from the scalar cache.
742
743Obviously, the second call to C<pi> is a waste of time, and storing
3d4a255c 744its return value is a waste of space. Specifying C<LIST_CACHE =E<gt>
745MERGE> will make C<memoize> use the same cache for scalar and list
746context return values, so that the second call uses the scalar cache
747that was populated by the first call. C<pi> ends up being called only
748once, and both subsequent calls return C<3> from the cache, regardless
749of the calling context.
a0cb3900 750
751Another use for C<MERGE> is when you want both kinds of return values
752stored in the same disk file; this saves you from having to deal with
753two disk files instead of one. You can use a normalizer function to
754keep 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
770This normalizer function will store scalar context return values in
771the disk file under keys that begin with C<S:>, and list context
772return values under keys that begin with C<L:>.
773
774=back
775
776=head1 OTHER FACILITIES
777
778=head2 C<unmemoize>
779
780There's an C<unmemoize> function that you can import if you want to.
781Why would you want to? Here's an example: Suppose you have your cache
782tied to a DBM file, and you want to make sure that the cache is
783written out to disk if someone interrupts the program. If the program
784exits normally, this will happen anyway, but if someone types
785control-C or something then the program will terminate immediately
786without synchronizing the database. So what you can do instead is
787
788 $SIG{INT} = sub { unmemoize 'function' };
789
a0cb3900 790C<unmemoize> accepts a reference to, or the name of a previously
791memoized function, and undoes whatever it did to provide the memoized
792version in the first place, including making the name refer to the
793unmemoized version if appropriate. It returns a reference to the
794unmemoized version of the function.
795
796If you ask it to unmemoize a function that was never memoized, it
797croaks.
798
799=head2 C<flush_cache>
800
801C<flush_cache(function)> will flush out the caches, discarding I<all>
3d4a255c 802the cached data. The argument may be a function name or a reference
a0cb3900 803to a function. For finer control over when data is discarded or
804expired, see the documentation for C<Memoize::Expire>, included in
805this package.
806
807Note that if the cache is a tied hash, C<flush_cache> will attempt to
808invoke the C<CLEAR> method on the hash. If there is no C<CLEAR>
809method, this will cause a run-time error.
810
811An 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
813as its cache. Then you can examine or modify the hash at any time in
3d4a255c 814any way you desire. You may flush the cache by using C<%hash = ()>.
a0cb3900 815
816=head1 CAVEATS
817
818Memoization is not a cure-all:
819
820=over 4
821
822=item *
823
824Do not memoize a function whose behavior depends on program
825state other than its own arguments, such as global variables, the time
826of day, or file input. These functions will not produce correct
827results when memoized. For a particularly easy example:
828
829 sub f {
830 time;
831 }
832
833This function takes no arguments, and as far as C<Memoize> is
834concerned, it always returns the same result. C<Memoize> is wrong, of
835course, and the memoized version of this function will call C<time> once
836to get the current time, and it will return that same time
837every time you call it after that.
838
839=item *
840
841Do 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
849This function accepts two arguments, adds them, and prints their sum.
850Its return value is the numuber of characters it printed, but you
851probably didn't care about that. But C<Memoize> doesn't understand
852that. If you memoize this function, you will get the result you
853expect the first time you ask it to print the sum of 2 and 3, but
854subsequent calls will return 1 (the return value of
855C<print>) without actually printing anything.
856
857=item *
858
859Do not memoize a function that returns a data structure that is
860modified by its caller.
861
862Consider these functions: C<getusers> returns a list of users somehow,
863and then C<main> throws away the first user on the list and prints the
864rest:
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
880If you memoize C<getusers> here, it will work right exactly once. The
881reference to the users list will be stored in the memo table. C<main>
882will discard the first element from the referenced list. The next
883time you invoke C<main>, C<Memoize> will not call C<getusers>; it will
884just return the same reference to the same list it got last time. But
885this time the list has already had its head removed; C<main> will
886erroneously remove another element from it. The list will get shorter
887and shorter every time you call C<main>.
888
889Similarly, this:
890
891 $u1 = getusers();
892 $u2 = getusers();
893 pop @$u1;
894
895will modify $u2 as well as $u1, because both variables are references
896to the same array. Had C<getusers> not been memoized, $u1 and $u2
897would have referred to different arrays.
898
899=item *
900
901Do not memoize a very simple function.
902
903Recently someone mentioned to me that the Memoize module made his
904program run slower instead of faster. It turned out that he was
905memoizing the following function:
906
907 sub square {
908 $_[0] * $_[0];
909 }
910
911I pointed out that C<Memoize> uses a hash, and that looking up a
912number in the hash is necessarily going to take a lot longer than a
913single multiplication. There really is no way to speed up the
914C<square> function.
915
916Memoization is not magical.
917
918=back
919
920=head1 PERSISTENT CACHE SUPPORT
921
922You can tie the cache tables to any sort of tied hash that you want
923to, as long as it supports C<TIEHASH>, C<FETCH>, C<STORE>, and
924C<EXISTS>. For example,
925
926 tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666;
927 memoize 'function', SCALAR_CACHE => [HASH => \%cache];
928
929works just fine. For some storage methods, you need a little glue.
930
931C<SDBM_File> doesn't supply an C<EXISTS> method, so included in this
932package is a glue module called C<Memoize::SDBM_File> which does
933provide one. Use this instead of plain C<SDBM_File> to store your
934cache 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
939C<NDBM_File> has the same problem and the same solution. (Use
899dc88a 940C<Memoize::NDBM_File instead of plain NDBM_File.>)
a0cb3900 941
942C<Storable> isn't a tied hash class at all. You can use it to store a
943hash to disk and retrieve it again, but you can't modify the hash while
944it's on the disk. So if you want to store your cache table in a
945C<Storable> database, use C<Memoize::Storable>, which puts a hashlike
946front-end onto C<Storable>. The hash table is actually kept in
947memory, and is loaded from your C<Storable> file at the time you
948memoize the function, and stored back at the time you unmemoize the
949function (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
957Include the `nstore' option to have the C<Storable> database written
958in `network order'. (See L<Storable> for more details about this.)
959
3d4a255c 960The C<flush_cache()> function will raise a run-time error unless the
961tied package provides a C<CLEAR> method.
962
a0cb3900 963=head1 EXPIRATION SUPPORT
964
965See Memoize::Expire, which is a plug-in module that adds expiration
966functionality to Memoize. If you don't like the kinds of policies
967that Memoize::Expire implements, it is easy to write your own plug-in
968module to implement whatever policy you desire. Memoize comes with
969several examples. An expiration manager that implements a LRU policy
970is available on CPAN as Memoize::ExpireLRU.
971
972=head1 BUGS
973
974The test suite is much better, but always needs improvement.
975
3d4a255c 976There is some problem with the way C<goto &f> works under threaded
977Perl, perhaps because of the lexical scoping of C<@_>. This is a bug
978in Perl, and until it is resolved, memoized functions will see a
979slightly different C<caller()> and will perform a little more slowly
980on threaded perls than unthreaded perls.
a0cb3900 981
5189e6fe 982Some versions of C<DB_File> won't let you store data under a key of
983length 0. That means that if you have a function C<f> which you
984memoized and the cache is in a C<DB_File> database, then the value of
985C<f()> (C<f> called with no arguments) will not be memoized. If this
986is a big problem, you can supply a normalizer function that prepends
987C<"x"> to every key.
a0cb3900 988
989=head1 MAILING LIST
990
991To join a very low-traffic mailing list for announcements about
992C<Memoize>, send an empty note to C<mjd-perl-memoize-request@plover.com>.
993
994=head1 AUTHOR
995
996Mark-Jason Dominus (C<mjd-perl-memoize+@plover.com>), Plover Systems co.
997
998See the C<Memoize.pm> Page at http://www.plover.com/~mjd/perl/Memoize/
999for news and upgrades. Near this page, at
1000http://www.plover.com/~mjd/perl/MiniMemoize/ there is an article about
1001memoization and about the internals of Memoize that appeared in The
1002Perl Journal, issue #13. (This article is also included in the
1003Memoize distribution as `article.html'.)
1004
3d4a255c 1005My upcoming book will discuss memoization (and many other fascinating
1006topics) in tremendous detail. It will be published by Morgan Kaufmann
1007in 2002, possibly under the title I<Perl Advanced Techniques
1008Handbook>. It will also be available on-line for free. For more
1009information, visit http://perl.plover.com/book/ .
1010
a0cb3900 1011To join a mailing list for announcements about C<Memoize>, send an
1012empty message to C<mjd-perl-memoize-request@plover.com>. This mailing
1013list is for announcements only and has extremely low traffic---about
3d4a255c 1014two messages per year.
a0cb3900 1015
899dc88a 1016=head1 COPYRIGHT AND LICENSE
1017
1018Copyright 1998, 1999, 2000, 2001 by Mark Jason Dominus
1019
1020This library is free software; you may redistribute it and/or modify
3d4a255c 1021it under the same terms as Perl itself.
899dc88a 1022
a0cb3900 1023=head1 THANK YOU
1024
1025Many thanks to Jonathan Roy for bug reports and suggestions, to
1026Michael Schwern for other bug reports and patches, to Mike Cariaso for
1027helping me to figure out the Right Thing to Do About Expiration, to
3d4a255c 1028Joshua Gerth, Joshua Chamas, Jonathan Roy (again), Mark D. Anderson,
1029and Andrew Johnson for more suggestions about expiration, to Brent
1030Powers for the Memoize::ExpireLRU module, to Ariel Scolnicov for
1031delightful messages about the Fibonacci function, to Dion Almaer for
a0cb3900 1032thought-provoking suggestions about the default normalizer, to Walt
1033Mankowski and Kurt Starsinic for much help investigating problems
1034under threaded Perl, to Alex Dudkevich for reporting the bug in
1035prototyped functions and for checking my patch, to Tony Bass for many
3d4a255c 1036helpful suggestions, to Jonathan Roy (again) for finding a use for
1037C<unmemoize()>, to Philippe Verdret for enlightening discussion of
1038C<Hook::PrePostCall>, to Nat Torkington for advice I ignored, to Chris
a0cb3900 1039Nandor for portability advice, to Randal Schwartz for suggesting the
1040'C<flush_cache> function, and to Jenda Krynicky for being a light in
1041the world.
1042
899dc88a 1043Special thanks to Jarkko Hietaniemi, the 5.8.0 pumpking, for including
1044this module in the core and for his patient and helpful guidance
1045during the integration process.
3d4a255c 1046
a0cb3900 1047=cut