* Bruno Le Floch <[log in to unmask]> [2012-02-06 04:26:24 -0500]:

Hi Bruno,

I'm starting to understand the problem with expandable caching.
Still I may not understand your solution:

: \DeclareDocumentCommand{\f}{om}
:   {
:     <compute f(#2) using assignments, store the result in
: \l_recurrence_result_int>
:     \IfValue{#1}
:       { \tl_set:NV #1 \l_recurrence_result_int }
:       { \int_use:N \l_recurrence_result_int }
:   }
: 
: Then,
: 
:    \f{4} % typesets 5
:    \f[\tmp]{4} % stores 5 in \tmp.

Are you saying that you can cache _one_ result? Please explain if you
have the time.

I think there's a general expandable solution to this. Let's assume we want
to compute f( n ). We compute is by computing f2( {}, n ). The first argument
is the cache of f2. The value that's returned by f2 is a pair (c,r), where c
is the last cache of f2 and r the result of f( n ).

This seems very doable and I think it's possible to do it in a time complexity
that is at most O( c^2 ), where c is the number of things that have to be cached.

It's also possible to optimise the cache, in the sense that lookups for
frequently looked up items are more efficient.

I'll try and implement this for a toy example. If it proves successful,
I'll incorporate it in the module I sent earlier on. BTW, there were a
few minor errors in the module, which I've fixed. Please let me know if
you want the module.

Regards,


Marc