Implementing Memorize

Implementing Memorize

[Lutz Donnerhacke]

In order to implement a generic memorize, I tried the following
  (see <slrnbpajhj.ns.lutz@taranis.iks-jena.de> for the context)

   generic
      with function Callback (n : Natural) return Natural;
   function Action (n : Natural) return Natural;
   
   function Action (n : Natural) return Natural is
   begin
      case n is
         when 0 | 1  => return 1;
         when others => return Callback(n-1) + Callback(n-2);
      end case;
   end Action;
   
   function Fib_Direct is new Action (Fib_Direct); -- won't compile

Re: Implementing Memorize

[christoph.grein]

>    generic
>       with function Callback (n : Natural) return Natural;
>    function Action (n : Natural) return Natural;
>    
>    function Action (n : Natural) return Natural is
>    begin
>       case n is
>          when 0 | 1  => return 1;
>          when others => return Callback(n-1) + Callback(n-2);
>       end case;
>    end Action;
>    
>    function Fib_Direct is new Action (Fib_Direct); -- won't compile
              ~~~~~~~~~~
              This hides the other homonyme from all visibility until the end of 
the declaration.

Re: Implementing Memorize

[Lutz Donnerhacke]

* christoph.grein@eurocopter.com wrote:
>>    generic
>>       with function Callback (n : Natural) return Natural;
>>    function Action (n : Natural) return Natural;
>>    
>>    function Action (n : Natural) return Natural is
>>    begin
>>       case n is
>>          when 0 | 1  => return 1;
>>          when others => return Callback(n-1) + Callback(n-2);
>>       end case;
>>    end Action;
>>    
>>    function Fib_Direct is new Action (Fib_Direct); -- won't compile
>               ~~~~~~~~~~
> This hides the other homonyme from all visibility until the end of
> the declaration.

What's the correct way to implement it?

Re: Implementing Memorize

[Marius Amado Alves]

On Wed, 2003-10-22 at 10:32, Lutz Donnerhacke wrote:
> * christoph.grein@eurocopter.com wrote:
> >>    generic
> >>       with function Callback (n : Natural) return Natural;
> >>    function Action (n : Natural) return Natural;
> >>    
> >>    function Action (n : Natural) return Natural is
> >>    begin
> >>       case n is
> >>          when 0 | 1  => return 1;
> >>          when others => return Callback(n-1) + Callback(n-2);
> >>       end case;
> >>    end Action;
> >>    
> >>    function Fib_Direct is new Action (Fib_Direct); -- won't compile
> >               ~~~~~~~~~~
> > This hides the other homonyme from all visibility until the end of
> > the declaration.
> 
> What's the correct way to implement it?

Maybe with an access-to-subprogram type. What problem are your trying to
solve?

Re: Implementing Memorize

[Lutz Donnerhacke]

* Marius Amado Alves wrote:
>> What's the correct way to implement it?
>
> Maybe with an access-to-subprogram type.

Of course this works. But I'm looking for a generic version.

> What problem are your trying to solve?

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.

Re: Implementing Memorize

[Lutz Donnerhacke]

* Lutz Donnerhacke wrote:
> 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.

The following version does not the job:
with Ada.Text_IO, Ada.Calendar;


procedure t is
   package Fibs is
      type Direct is tagged null record;
      
      function Fib (c1 : Direct; c2 : Direct'Class; n : Natural) return Natural;
   end Fibs;
   
   package body Fibs is
      function Fib (c1 : Direct; c2 : Direct'Class; n : Natural) return Natural is
      begin
         case n is
            when 0 | 1  => return 1;
            when others => return Fib (c2, c2, n-1) + Fib (c2, c2, n-2);
         end case;
      end Fib;
   end Fibs;
   
   use Fibs;
   
   package Memorizes is
      type Memorize is new Fibs.Direct with null record;
      function Fib (c1 : Memorize; c2 : Fibs.Direct'Class; n : Natural) return Natural;
   end Memorizes;
   
   package body Memorizes is
      type Item is record
         value : Natural;
         valid : Boolean := False;
      end record;
      
      hash : array(0 .. 100) of Item;
      
      function Fib (c1 : Memorize; c2 : Fibs.Direct'Class; n : Natural) return Natural is
      begin
         if n not in hash'Range then
            return Fib(Direct(c1), c2, n);
         else
            declare
               x : Natural renames hash(n).value;
            begin
               if not hash(n).valid then
                  x := Fib(Direct(c1), c2, n);
               end if;
               return x;
            end;
         end if;
      end Fib;
   end Memorizes;

   use Memorizes;
   
   procedure Time_It (ctx : Direct'Class; n : Natural) is
      use Ada.Text_IO, Ada.Calendar;
      start, ende : Time;
      result : Natural;
   begin
      start := Clock;
      result := Fib (ctx, ctx, n);
      ende := Clock;
      Put_Line ("Result =" & Natural'Image(result) &
        " in" & Duration'Image(ende-start) & " seconds.");
   end Time_It;

   d : Direct;
   m : Memorize;
begin
   Time_It (d, 30);
   Time_It (m, 30);
end t;

Re: Implementing Memorize

[Lutz Donnerhacke]

* Lutz Donnerhacke wrote:
> The following version does not the job:

Simple logic error:

> with Ada.Text_IO, Ada.Calendar;
> 
> 
> procedure t is
>    package Fibs is
>       type Direct is tagged null record;
>       
>       function Fib (c1 : Direct; c2 : Direct'Class; n : Natural) return Natural;
>    end Fibs;
>    
>    package body Fibs is
>       function Fib (c1 : Direct; c2 : Direct'Class; n : Natural) return Natural is
>       begin
>          case n is
>             when 0 | 1  => return 1;
>             when others => return Fib (c2, c2, n-1) + Fib (c2, c2, n-2);
>          end case;
>       end Fib;
>    end Fibs;
>    
>    use Fibs;
>    
>    package Memorizes is
>       type Memorize is new Fibs.Direct with null record;
>       function Fib (c1 : Memorize; c2 : Fibs.Direct'Class; n : Natural) return Natural;
>    end Memorizes;
>    
>    package body Memorizes is
>       type Item is record
>          value : Natural;
>          valid : Boolean := False;
>       end record;
>       
>       hash : array(0 .. 100) of Item;
>       
>       function Fib (c1 : Memorize; c2 : Fibs.Direct'Class; n : Natural) return Natural is
>       begin
>          if n not in hash'Range then
>             return Fib(Direct(c1), c2, n);
>          else
>             declare
>                x : Natural renames hash(n).value;
>             begin
>                if not hash(n).valid then
>                   x := Fib(Direct(c1), c2, n);
                    hash(n).valid := True;
>                end if;
>                return x;
>             end;
>          end if;
>       end Fib;
>    end Memorizes;
> 
>    use Memorizes;
>    
>    procedure Time_It (ctx : Direct'Class; n : Natural) is
>       use Ada.Text_IO, Ada.Calendar;
>       start, ende : Time;
>       result : Natural;
>    begin
>       start := Clock;
>       result := Fib (ctx, ctx, n);
>       ende := Clock;
>       Put_Line ("Result =" & Natural'Image(result) &
>         " in" & Duration'Image(ende-start) & " seconds.");
>    end Time_It;
> 
>    d : Direct;
>    m : Memorize;
> begin
>    Time_It (d, 30);
>    Time_It (m, 30);
> end t;

Does the job.

Re: Implementing Memorize

[Dmitry A. Kazakov]

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

>* Marius Amado Alves wrote:
>>> What's the correct way to implement it?
>>
>> Maybe with an access-to-subprogram type.
>
>Of course this works. But I'm looking for a generic version.
>
>> What problem are your trying to solve?
>
>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

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

Re: Implementing Memorize

[Lutz Donnerhacke]

* 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. A full generic module would fine.
The following might be a useful start. (Unnecessary copies removed.)

with Ada.Text_IO, Ada.Calendar;

procedure t is
   package Fibs is
      type Direct is tagged null record;
      
      function Fib (c : Direct; n : Natural) return Natural;
   end Fibs;
   
   package body Fibs is
      function Fib (c : Direct; n : Natural) return Natural is
      begin
         case n is
            when 0 | 1  => return 1;
            when others => return Fib (Direct'Class(c), n-1) + Fib (Direct'Class(c), n-2);
         end case;
      end Fib;
   end Fibs;
   
   use Fibs;
   
   package Memorizes is
      type Memorize is new Fibs.Direct with null record;
      function Fib (c : Memorize; n : Natural) return Natural;
   end Memorizes;
   
   package body Memorizes is
      type Item is record
         value : Natural;
         valid : Boolean := False;
      end record;
      
      hash : array(0 .. 100) of Item;
      
      function Fib (c : Memorize; n : Natural) return Natural is
      begin
         if n not in hash'Range then
            return Fib(Direct(c), n);
         else
            declare
               x : Natural renames hash(n).value;
               v : Boolean renames hash(n).valid;
            begin
               if not v then
                  x := Fib(Direct(c), n);
                  v := True;
               end if;
               return x;
            end;
         end if;
      end Fib;
   end Memorizes;

   use Memorizes;
   
   procedure Time_It (ctx : Direct'Class; n : Natural) is
      use Ada.Text_IO, Ada.Calendar;
      start, ende : Time;
      result : Natural;
   begin
      start := Clock;
      result := Fib (ctx, n);
      ende := Clock;
      Put_Line ("Result =" & Natural'Image(result) &
        " in" & Duration'Image(ende-start) & " seconds.");
   end Time_It;

   d : Direct;
   m : Memorize;
begin
   Time_It (d, 30);
   Time_It (m, 30);
end t;

Re: Implementing Memorize

[Marius Amado Alves]

On Wed, 2003-10-22 at 11:33, Lutz Donnerhacke wrote:
> * Lutz Donnerhacke wrote:
> > 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.

So your problem is generating the Fibonaci number of a given natural N.

I would not use recursive calls here because call stack space is usually
shorter than the range of naturals. I would use increments in a loop.
And I think I would use a precomputed table of values for N = 100,
200... (say). And it is clear that Fib (Natural'Last) is much bigger
than Natural'Last so I would look for the M such that Fib (M) <=
Natural'Last and Fib (M + 1) > Natural'Last and then constrain the input
type to 0 .. M. Or else use a big numbers package for the output type.

> ...

Took a look at your code. I think you're failing to set the Valid
component.

Re: Implementing Memorize

[Lutz Donnerhacke]

* Marius Amado Alves wrote:
> On Wed, 2003-10-22 at 11:33, Lutz Donnerhacke wrote:
>> * Lutz Donnerhacke wrote:
>> > 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.
> 
> So your problem is generating the Fibonaci number of a given natural N.

No. Fib is only an application for the more general pattern Memorize.

> I would not use recursive calls here because call stack space is usually
> shorter than the range of naturals. I would use increments in a loop.

The Memorize package should get the function to be computed as a generic
parameter. So you can't assume anything about the parameters used.

> Took a look at your code. I think you're failing to set the Valid
> component.

Yep. Code in progress.

Re: Implementing Memorize

[Marius Amado Alves]

On Wed, 2003-10-22 at 12:52, Lutz Donnerhacke wrote:
> > So your problem is generating the Fibonaci number of a given natural N.
> No. Fib is only an application for the more general pattern Memorize.

I see. I remember an application I had that required this: computing the
editing distance between two strings. I also did it with a hash table. I
did not do a generic version. What is your "referenced article"?

Re: Implementing Memorize

[Frank J. Lhota]

"Lutz Donnerhacke" <lutz@iks-jena.de> wrote in message
news:slrnbpch9n.oa.lutz@taranis.iks-jena.de...
> In order to implement a generic memorize, I tried the following
>   (see <slrnbpajhj.ns.lutz@taranis.iks-jena.de> for the context)
>
>    generic
>       with function Callback (n : Natural) return Natural;
>    function Action (n : Natural) return Natural;
>
>    function Action (n : Natural) return Natural is
>    begin
>       case n is
>          when 0 | 1  => return 1;
>          when others => return Callback(n-1) + Callback(n-2);
>       end case;
>    end Action;
>
>    function Fib_Direct is new Action (Fib_Direct); -- won't compile

I can see why this doesn't compile: you are using Fib_Direct to define
Fib_Direct. We could avoid this bit of circularity by declaring another
function to serve as the generic parameter, then implement this other
function as a simple call to the generic instantiation, as follows:

    function Fib_Indirect(n : Natural) return Natural;

    function Fib_Direct is new Action( Fib_Indirect );

    function Fib_Indirect(n : Natural) return Natural is
    begin
       return Fib_Direct(n);
    end Fib_Indirect;

Of course, for the particular problem you posted, I would not use generics
at all. This implementation works quite nicely:

    function Fib_Direct(n : Natural) return Natural is
    begin
       case n is
          when 0 | 1  => return 1;
          when others => return Fib_Direct(n-1) + Fib_Direct(n-2);
       end case;
    end Fib_Direct;

Re: Implementing Memorize

[Dmitry A. Kazakov]

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

Re: Implementing Memorize

[tmoran]

>  function Fib_Direct is new Action (Fib_Direct); -- won't compile
  Considering that generics are like macros, what code would you
expect this to produce?

Re: Implementing Memorize

[Robert I. Eachus]

Lutz Donnerhacke wrote:
> * Marius Amado Alves wrote:
> 
>>>What's the correct way to implement it?
>>
>>Maybe with an access-to-subprogram type.
> 
> 
> Of course this works. But I'm looking for a generic version.
> 
> 
>>What problem are your trying to solve?
> 
> 
> 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.

Calculating Fibonacci numbers recursively is definitely braindead.  Try 
this approach instead.  (Since I use Long_Float to represent values > 
Integer'Last, on GNAT you get an infinity above 1474. ;-)  Since GNAT 
apparently does the powers of two approach for computing X**N, you can 
try timing this but it is really a waste of (your) time.

==============================================================================

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Ada.Long_Float_Text_IO; use Ada.Long_Float_Text_IO;
procedure Fib is -- a program to compute Fibonacci numbers.

    Temp: Long_Float;
    Value: Integer;

    function Fibonacci(N: Natural) return Long_Float is
      Phi: constant := 
1.61803_39887_49894_84820_45868_34365_63811_77203_09179_80576;
      Sqrt_5: constant := 2*Phi-1.0; -- 2.23606_79774_99789_6964...
    begin  return Long_Float'Rounding(Phi**N/Sqrt_5); end Fibonacci;

begin
   Put_Line("Enter a number, negative to exit.  Above 46 returns 
Long_Float, above 1474, infinity.");
   loop
     Get(Value);
     if Value < 0 then return; end if;
     Temp := Fibonacci(Value);
     Put(" Fibonacci (");
     Put(Value, 1);
     if Temp > Long_Float(Integer'Last)
     then
       Put(") is ");
       if Value > 73 then Put (" approximately"); end if;
       Put(Temp,2,14,2);
     else
       Put(") is ");
       Put(Integer(Temp), 1);
     end if;
     Put_Line(".");
   end loop;
end Fib;

-- 
                                                     Robert I. Eachus

"Quality is the Buddha. Quality is scientific reality. Quality is the 
goal of Art. It remains to work these concepts into a practical, 
down-to-earth context, and for this there is nothing more practical or 
down-to-earth than what I have been talking about all along...the repair 
of an old motorcycle."  -- from Zen and the Art of Motorcycle 
Maintenance by Robert Pirsig

Re: Implementing Memorize

[Lutz Donnerhacke]

* Dmitry A Kazakov wrote:
><lutz@iks-jena.de> wrote:
>>* Dmitry A Kazakov wrote:
>>> 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;

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

> 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.

> 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.

Re: Implementing Memorize

[Lutz Donnerhacke]

* Robert I. Eachus wrote:
> Lutz Donnerhacke wrote:
>> 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.
>
> Calculating Fibonacci numbers recursively is definitely braindead.  Try
> this approach instead.

I'd like to abstract the problem from fib to an arbitary external provided
recursive function. So I'm looking for an elegant way to define the generic
memorize.

Re: Implementing Memorize

[Georg Bauhaus]

Lutz Donnerhacke <lutz@iks-jena.de> wrote:
: In order to implement a generic memorize, I tried the following
:  (see <slrnbpajhj.ns.lutz@taranis.iks-jena.de> for the context)

To mention some more context, this has come up in a language war
in de.comp.lang.misc where someone presented:

;;;; -*- Mode: Lisp; Syntax: Common-Lisp -*-
;;;; Code from Paradigms of AI Programming
;;;; Copyright (c) 1991 Peter Norvig
;;; ==============================

;;;; The Memoization facility:

(defun memo (fn &key (key #'first) (test #'eql) name)
  "Return a memo-function of fn."
  (let ((table (make-hash-table :test test)))
    (setf (get name :memo) table)
    #'(lambda (&rest args)
        (let ((k (funcall key args)))
          (multiple-value-bind (val found-p)
              (gethash k table)
            (if found-p val
                (setf (gethash k table) (apply fn args))))))))

(defun memoize (fn-name &key (key #'first) (test #'eql))
  "Replace fn-name's global definition with a memoized version."
  (clear-memoize fn-name)
  (setf (symbol-function fn-name)
        (memo (symbol-function fn-name)
              :name fn-name :key key :test test)))

Re: Implementing Memorize

[Dmitry A. Kazakov]

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