Re: Implementing Memorize

[Dmitry A. Kazakov <mailbox@dmitry-kazakov.de>]

On Wed, 22 Oct 2003 12:10:07 +0000 (UTC), Lutz Donnerhacke
<lutz@iks-jena.de> wrote:

>* Dmitry A Kazakov wrote:
>> On Wed, 22 Oct 2003 11:07:43 +0000 (UTC), Lutz Donnerhacke
>>>Calculating Fibbonacci numbers recursivly is easy but braindead. Languages
>>>with access to the symbol table at execution time are able to change the the
>>>reccuring call with a memorize wrapper which returns already computed values
>>>immediatly instead of recalculating them. In the referenced article I wrote
>>>an C-Implementation of such a wrapper. Now I'm looking for a more elegant
>>>version in Ada.
>>
>> Solution depends on how exposed should be the context used to store
>> results:
>>
>> 1. Completely hidden (allocated upon elaboration of the body)
>> 2. Partially exposed as a generic parameter of the compilation unit
>> 3. Fully exposed as a parameter of the subprogram
>
>It's more or less irrelevant.

You have to choose an abstraction first. For instance for (1), a
generic variant could be:

generic
   type Argument_Type is private;
   type Parameter_Type is private;
   with function Evaluate (X : Argument_Type; N : Parameter_Type)
      return Argument_Type;
function Evaluate_With_Side_Effects
    (X : Argument_Type; N : Parameter_Type)
      return Argument_Type;

function Evaluate_With_Side_Effects
    (X : Argument_Type; N : Parameter_Type)
      return Argument_Type is
begin
   if not <X & N already evaluated> then
      <store> Evaluate (X, N);
   end if;
   return <cached>;
end Evaluate_With_Side_Effects;

What you wrote is also (1), but on the basis of a tagged type.
Theoretically one could also use a discriminated type, to complete the
list of opportunities.

Note that (1) has problems with multi-tasking. Other problems appear
when Evaluate is not pure. For example, in a some real project, there
were values dependent from other values. When an equivalent of
Evaluate was calculated over dependent values, it could be made more
precise if the original values were known. The solution here was (3) +
keeping track of original value changes.

---
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de