From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,99ab4bb580fc34cd X-Google-Attributes: gid103376,public From: ncohen@watson.ibm.com (Norman H. Cohen) Subject: Re: Q: access to subprogram Date: 1996/07/08 Message-ID: <4rre7j$pv7@watnews1.watson.ibm.com> X-Deja-AN: 167214010 distribution: world references: <4rb9dp$qe6@news1.delphi.com> <4re2ng$t7u@wdl1.wdl.loral.com> organization: IBM T.J. Watson Research Center reply-to: ncohen@watson.ibm.com newsgroups: comp.lang.ada Date: 1996-07-08T00:00:00+00:00 List-Id: In article , 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