Re: Soliciting criticism of memoize function

[Mark Hamburg <mark_hamburg@...>]

On May 17, 2008, at 10:54 AM, Norman Ramsey wrote:

> > Some issues to deal with in getting a generic memoize to work  
> > correctly:
> >
> > 1. Do you need to support memoization for f( nil )? If so, you
> > potentially need to handle this separately (but see below).
> >
> > 2. Do you handle nil results from f correctly? Efficiently?
>
> Nasty questions, both of them.  Well done!  The answers are that
>
>  1. memoize(f)(nil) causes a run-time error
>  2. For every x such that f(x) is nil,
>     memoize(f)(x) == f(x) but is more expensive than f(x).

True. You don't need to encode nil as stored as a result in the  
memoize table but it means that anything with a nil result will  
produce nil over and over again.

> I'm reluctant to add something like encode and decode, which do actual
> work, and moreover which have to be explained.

Relatively speaking, the encode and decode are probably cheaper than  
the checks being done with select. Remember that assert does not  
compile out.

Another approach to dealing with NaN as an argument is to observe that  
the behavior will be that table lookups using NaN as a key will fail  
and hence just let it force you over to the slow path.

> This is an area where I really don't understand the issues.  It sounds
> like what you're saying is that it's bad to have string keys because
> strings are not likely to be reused, yet the associations will clutter
> up the table.   But we have weak keys, so the strings and values can
> be collected, no?  What am I missing here?  Are you thinking that
> having results alive will keep the string arguments alive and in the
> table unnecessarily?

Basically weak tables are always a bit tricky and semi-weak tables are  
doubly so. Essentially weakness means that some of the keys and values  
won't be marked via the table and hence may get collected, but that  
word "some" is important to understand.

Mark