Re: Q: access to subprogram

[bobduff@world.std.com (Robert A Duff)]

In article <4rre7j$pv7@watnews1.watson.ibm.com>,
Norman H. Cohen <ncohen@watson.ibm.com> wrote:
[... stuff about closures]

Norman gave a couple of nice examples illustrating how closures work
Thank you.  But I was hoping for something more about what makes
closures so great (as opposed to how they work).  I'm still unsure why
closures are such a wonderful thing.  Some comments:

Ackermann's function isn't something I want to calculate very often.
Is there a more "practical" example?

One can represent closures explicitly using heap-allocated tagged
objects.  A closure in a language that supports full closures is
represented by the address of the function, plus some representation of
the environment in which that function is called.  And this stuff has to
be allocated in the heap, since it can live essentially forever.  One
can do the same thing *explicitly* in Ada, by putting the "environment"
stuff into an object, and allocating it on the heap.  I show a different
version of package body Ackermann_Computation below, that works this
way.

Doing this requires the data that's in the closure to be explicitly
marked as such (by being components of the tagged type(s)).  In Norm's
"true closures" solution, it's implicit -- that is, whatever Norm's
Next_Row function happens to reference is what needs to be packaged up
in the closure.  Is there some advantage to that implicitness?  Does it
make things more substantially more convenient in some way that I don't
understand?  It seems to me that it's an *advantage* to make things
explicit -- it seems nice that a local variable (or parameter) in Ada
doesn't live longer than the containing scope -- it makes it easier to
understand what the purpose of that local is.  And if you want it to
live longer, you *explicitly* put it in the heap.

The solution below explicitly creates heap objects representing
closures, whereas Norman's solution implicitly allocates some stack
frames in the heap.

The "closures by hand" solution is approximately the same size as (a
little bigger than) Norm's solution.

Norman's solution is perhaps more elegant.  But it doesn't seem that
full closures make the grass greener and the sky bluer and the birds
sing more sweetly and all the other wonderfulness that some people seem
to like so much.  And of course there's a cost -- stack frames would
have to be heap-allocated in general, and a good compiler would want to
do all kinds of fancy analysis to avoid that when possible.

So, I guess my question is, "Yeah, it's nice, but what's the big deal?"

(By the way, surely the *simplest* solution is just a direct translation
from the definition:

   function Ackermann (M, N: Unbounded_Natural) return Unbounded_Natural is
   begin
      if M = 0 then
         return N+1;
      elsif N = 0 then
         return Ackermann(M-1, 1);
      else
         return Ackermann(M-1, Ackermann(M, N-1));
      end if;
   end Ackermann;

)

What's the most *efficient* method for calculating Ackermann's?

OK, here's my "closures-by-hand" solution:

package body Ackermann_Computation is

   package Container is
      -- We need to put Ackermann_Row_Type in a package, so
      -- Invoke will be primitive.

      type Ackermann_Row_Type is abstract tagged limited null record;
      -- Six reserved words in a row!

      function Invoke(R: Ackermann_Row_Type; N: Unbounded_Natural) return Unbounded_Natural is abstract;
      -- Invokes the closure represented by R, with parameter N.

      type Ackermann_Row_Ptr is access Ackermann_Row_Type'Class;
   end Container;
   use Container;

   type Row_Zero_Type is new Ackermann_Row_Type with null record;
   function Invoke(R: Row_Zero_Type; N: Unbounded_Natural) return Unbounded_Natural;

   function Invoke(R: Row_Zero_Type; N: Unbounded_Natural) return Unbounded_Natural is
   begin
      return N + 1;
   end Invoke;

   type Successor_Row_Type(Pred: access Ackermann_Row_Type'Class;
                           Row_Num: Natural) is new Ackermann_Row_Type with null record;
   -- Pred points to the predecessor row of this row.  This is analogous
   -- to the parameter F in Norman's Successor_Row function.

   function Invoke(R: Successor_Row_Type; N: Unbounded_Natural) return Unbounded_Natural;

   function Invoke(R: Successor_Row_Type; N: Unbounded_Natural) return Unbounded_Natural is
      Counter : Unbounded_Natural := N + 1;
      Result  : Unbounded_Natural := 1;
   begin
      while Counter /= 0 loop
         Result := Invoke(R.Pred.all, Result);
         Counter := Counter - 1;
      end loop;
      return Result;
   end Invoke;

   function Ackermann (M, N: Natural) return Unbounded_Natural is
      Row: Ackermann_Row_Ptr := new Row_Zero_Type;  -- R[0]
   begin
      for I in 1 .. M loop
         Row := new Successor_Row_Type(Pred => Row, Row_Num => I);
            -- Compute R[1] from R[0], R[2] from R[1], ...
      end loop;
      return Invoke(Row.all, To_Unbounded_Natural(N));  -- i.e., R[m](n)
   end Ackermann;

end Ackermann_Computation;

And here's Norm's solution using closures, for comparison:

package body Ackermann_Computation is

   type Ackermann_Row_Type is
      access function (N: Unbounded_Natural) return Unbounded_Natural;

   function Row_Zero (N: Unbounded_Natural) return Unbounded_Natural is
   begin
      return N + 1;
   end Row_Zero;

   function Successor_Row
      (F: Ackermann_Row_Type) return Ackermann_Row_Type is

      function Next_Row (N: Unbounded_Natural) return Unbounded_Natural is
         Counter : Unbounded_Natural := N + 1;
         Result  : Unbounded_Natural := 1;
      begin
         while Counter /= 0 loop
            Result := F(Result);
               -- F is the parameter of the surrounding function
            Counter := Counter - 1;
         end loop;
         return Result;
      end Result;

   begin

      return Next_Row'Access;  -- Illegal in Ada 95

   end Successor_Row;

   function Ackermann (M, N: Integer) return Unbounded_Natural is
      Row: Ackermann_Row_Type := Row_Zero'Access;  -- R[0]
   begin
      for I in 1 .. M loop
         Row := Successor_Row(Row);
            -- Compute R[1] from R[0], R[2] from R[1], ...
      end loop;
      return Row ( To_Unbounded_Natural(N) );  -- i.e., R[m](n)
   end Ackermann;

end Ackermann_Computation;

- Bob