CODEWITHSUNDEEP
perl
Jonathan Swartz
Jonathan Swartz

Reputation: 1983

How to normalize Perl function arguments for memoization?

How can I normalize a list of function arguments to a string, such that two argument lists convert to the same string iff they are effectively equivalent? The algorithm should

  1. Compare embedded hashes and lists deeply, rather than by reference
  2. Ignore hash key order
  3. Ignore difference between 3 and "3"
  4. Generate a relatively readable string (not required, but nice-to-have for debugging)
  5. Perform well (XS preferred over Perl)

This is necessary for memoization, i.e. caching the result of the function based on its arguments.

As a strawman example, Memoize uses this as a default normalizer, which fails #1 and #3:

$argstr = join chr(28),@_;

For a while my go-to normalizer was

JSON::XS->new->utf8->canonical

However it treats the number 3 and the string "3" differently, based on how the scalar was used recently. This can generate different strings for essentially equivalent argument lists and reduce the memoization benefit. (The vast majority of functions won't know or care if they get 3 or "3".)

For fun I looked at a bunch of serializers to see which ones differentiate 3 and "3":

Data::Dump   : equal - [3] vs [3]
Data::Dumper : not equal - [3] vs ['3']
FreezeThaw   : equal - FrT;@1|@1|$1|3 vs FrT;@1|@1|$1|3
JSON::PP     : not equal - [3] vs ["3"]
JSON::XS     : not equal - [3] vs ["3"]
Storable     : not equal - <unprintable>
YAML         : equal - ---\n- 3\n vs ---\n- 3\n
YAML::Syck   : equal - --- \n- 3\n vs --- \n- 3\n
YAML::XS     : not equal - ---\n- 3\n vs ---\n- '3'\n

Of the ones that report "equal", not sure how to get them to ignore hash key order.

I could walk the argument list beforehand and stringify all numbers, but this would require making a deep copy and would violate #5.

Thanks!

Upvotes: 10

Views: 891

Answers (2)

mob
mob

Reputation: 118665

YAML and its progeny sort hash keys by default. Set $YAML::SortKeys = 2 to get sorting on deep hashes.

Setting $YAML::Stringify to a true value and setting $YAML::XS::QuoteNumericStrings to a false value will help you normalize numeric values. The latter setting will "unquote" a string value that looks like a number.

Also, you can use $Data::Dumper::Sortkeys = 1 to normalize the output order with Data::Dumper. Setting $Data::Dumper::Useqq = 1 will unquote strings that look like numbers.

Upvotes: 2

Oleg V. Volkov
Oleg V. Volkov

Reputation: 22461

Pretty much any serializer will treat 3 and "3" differently, because it doesn't have knowledge that number and stringified number are same for you and this assumption is false for general data. You must normalize either input or output yourself.

For input, deep scan with replacing any stringified number with its value+0 will do. If you know where exactly numbers may be in input, you can shorten this scan considerably.

For output, some simple state machine or even regexp (yes, I know that output is not regular) will be most likely enough to strip number-only string values to numbers.

Upvotes: 2

Related Questions