Re: Q: access to subprogram

[ncohen@watson.ibm.com (Norman H. Cohen)]

In article <Du4tvx.13s@world.std.com>, bobduff@world.std.com (Robert A Duff)
writes: 

|> Ignore efficiency and implementation difficulty, for the moment.  Show
|> me an example or two illustrating the tremendous expressive power, using
|> some imagined syntax for expressing full closures.  (I know there's some
|> expressive power there, but it's not clear to me how tremendous it is.
|> I'm wondering if I've just not had enough experience in Lisp, etc.  I've
|> done some Lisp programming, and used closures, but don't miss them *all*
|> that much in Ada-like languages.)

Full closures are what LISP programmers call FUNARGs.

First, a simple example: 

   type Integer_Map_Type is access function (N: Integer) return Integer;

   function Add_M_To (M: Integer) return Integer_Map_Type is
      -- A function that returns M more than its formal parameter: 
      function Result_Function (N: Integer) return Integer is
      begin
         return N + M;
      end Result_Function;
   begin
      return Result_Function'Access;  -- illegal in Ada 95
   end Add_M_To;

   Add_1_To : Integer_Map_Type := Add_M_To(M => 1);
   Add_5_To : Integer_Map_Type := Add_M_To(M => 5);
   X        : Integer := Add_1_To(10); -- returns 11
   Y        : Integer := Add_5_To(10); -- returns 15

Add_M_To returns a pointer to a function more deeply nested than the
access type Integer_Map_Type, in violation of Ada-95 rules.  Note that
the function pointed to, Result_Function, refers to M, which is a formal
parameter of Add_M_To and thus, in Ada 95, goes out of existence when
Add_M_To returns.  In a language supporting full closures, the value of M
is not obliterated when Add_M_To returns.  What Add_M_To returns is a
value designating not only the function Result_Function, but also the
environment in which that function is to be executed, in this case an
environment in which M is bound to 1 or to 5.  The state of the
environment during the call on Add_M_To is retained as part of this
result value even after Add_M_To returns.

Now for a more intricate example.  Robert Dewar mentioned that
Ackermann's function can be programmed out of straightforward loops if
full closures are supported.  The classic definition of Ackermann's
function is: 

   A(0,n) = n+1
   A(m,0) = A(m-1,1)        for m>0
   A(m,n) = A(m-1,A(m,n-1)) for m>0, n>0

If we view A as an unbounded array and let R[m] be the function
corresponding to the m\th "row" of this array, so that A(m,n) = R[m](n),
these equations become: 

   R[0](n) = n+1
   R[m](0) = R[m-1](1)          for m>0
   R[m](n) = R[m-1] o R[m](n-1) for m>0, n>0
      (where o represents functional composition)

By repeatedly replacing R[m](...) in the third equation by the definition
for R[m] given in the third equation, we get, for m>0: 

   R[m](n) = R[m-1] o R[m](n-1)
           = R[m-1] o R[m-1] o R[m](n-2)
           = R[m-1] o R[m-1] o R[m-1] o R[m](n-3)
              ...
           = R[m-1] o ... o R[m-1] o R[m](0)
             \                   /
              \-----------------/
                    n times

Then, by replacing R[m](0) according to the second equation, we get

   R[m](n) = R[m-1] o ... o R[m-1] (1)
             \                   /
              \-----------------/
                   n+1 times

In other words,

   R[0] = the successor function (from the first equation)
   For m>0, the function R[m] is derived from the function R[m-1] as follows: 
      Given an argument n, R[m] returns the result of starting with 1 and
      applying R[m-1] repeatedly, n+1 times.

Here's a formulation using Ada plus full closures: 


package Unbounded_Naturals is
   type Unbounded_Natural is private;
      -- a type representing arbitrarily large nonnegative integers
   ...
   function "+"
      (Left: Unbounded_Natural; Right: Natural) return Unbounded_Natural;
   function "-"
      (Left: Unbounded_Natural; Right: Natural) return Unbounded_Natural;
   function "="
      (Left: Unbounded_Natural; Right: Natural) return Boolean;
   function To_Unbounded_Natural (N: Natural) return Unbounded_Natural;
   ...
private
   ...
end Unbounded_Naturals;


with Unbounded_Naturals; use Unbounded_Naturals;
package Ackermann_Computation is
   function Ackermann (M, N: Integer) return Unbounded_Natural;
end Ackermann_Computation;


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;


The magic is inside Successor_Row, which returns a pointer to a function
more deeply nested than the access type Ackermann_Row_Type, in violation
of Ada-95 rules.  The function pointed to, Next_Row, refers to F, which
is a formal parameter of Successor_Row.  Successor_Row returns a value
designating both the function Next_Row and the environment in which that
function is to be executed, in which F is bound to a particular
Ackermann_Row_Type value.  (After each iteration of the for-loop, Row
designates the function Next_Row and an environment in which F is bound
to whatever the value of Row was at the BEGINNING of that iteration.)

--
Norman H. Cohen    ncohen@watson.ibm.com