Re: Implementing Memorize

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

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

>In this case I have reference Evaluate_With_Side_Effects from Evaluate. How
>can I implement this?

You cannot without modifying Evaluate if it has to be recursive and
should take an advantage of knowing cached values at nested steps.

>> 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.
>
>This does not solve the problem of recursion.

Yep, you have to expose the context and to make Fib aware of it.

>> precise if the original values were known. The solution here was (3) +
>> keeping track of original value changes.
>
>Understood, but I didn't grasp how to prepare the Evaluate function for this
>usage.

You already did it. It could be sort of:

package Fibonacci is
   type Context_Type is tagged limited private;

   function Fib (N : Natural; Context : access Context_Type'Class)
      return Natural;
   function Is_In (N : Natural; Context : access Context_Type)
      return Boolean;
   function Load (N : Natural; Context : access Context_Type)
      return Natural;
   procedure Store
      (N, Result : Natural; Context : access Context_Type);

private
   type Context_Type is tagged limited null record;

end Fibonacci;
-------------------
package Fibonacci.Cached is
   type Memory is new Context_Type with private;

   function Is_In (N : Natural; Context : access Memory)
      return Boolean;
   function Load (N : Natural; Context : access Memory)
      return Natural;
   procedure Store (N, Result : Natural; Context : access Memory);

private
   type Results is array (Natural range <>) of Natural;
   type Memory is new Context_Type with record
      Data : Results (1..100) := (others => 0);
   end record;

end Fibonacci.Cached;
-----------------
package body Fibonacci is
   function Is_In (N : Natural; Context : access Context_Type)
      return Boolean is
   begin
      return False;
   end Is_In;
   
   function Load (N : Natural; Context : access Context_Type)
      return Natural is
   begin
      raise Program_Error;
      return 0;
   end Load;

   procedure Store
      (N, Result : Natural; Context : access Context_Type) is
   begin
      null;
   end Store;

   function Fib (N : Natural; Context : access Context_Type'Class)
      return Natural is
   begin
      if N < 2 then
         return 1;
      end if;
      if Is_In (N, Context) then
         return Load (N, Context);
      else
         declare
            Result : constant Natural := 
               Fib (N - 1, Context) + Fib (N - 2, Context);
         begin
            Store (N, Result, Context);
            return Result;
         end;
      end if;
   end Fib;

end Fibonacci;
---------------
package body Fibonacci.Cached is
   function Is_In (N : Natural; Context : access Memory)
      return Boolean is
   begin
      return N in Context.Data'Range and then 0 /= Context.Data (N);
   end Is_In;

   function Load (N : Natural; Context : access Memory)
      return Natural is
   begin
      return Context.Data (N);
   end Load;

   procedure Store (N, Result : Natural; Context : access Memory) is
   begin
      if N in Context.Data'Range then
         Context.Data (N) := Result;
      end if;
   end Store;

end Fibonacci.Cached;

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