CVS difference for ai12s/ai12-0312-1.txt

Differences between 1.11 and version 1.12
Log of other versions for file ai12s/ai12-0312-1.txt

--- ai12s/ai12-0312-1.txt	2019/10/02 00:14:31	1.11
+++ ai12s/ai12-0312-1.txt	2019/10/30 04:30:15	1.12
@@ -1,4 +1,4 @@
-!standard 5.5.2(2/3)                                  19-10-01  AI12-0312-1/06
+!standard 5.5.2(2/3)                                  19-10-06  AI12-0312-1/07
 !class presentation 19-02-07
 !status work item 19-02-07
 !status received 19-02-07
@@ -21,6 +21,17 @@
 
 !wording
 
+Append after 3.5.2(11)  [or perhaps 13.4(14) instead?]
+
+   -- See 3.5.2 [if placed in 13.4]
+   for Roman_Digit use ('I' => 1,
+                        'V' => 5,
+                        'X' => 10,
+                        'L' => 50,
+                        'C' => 100,
+                        'D' => 500,
+                        'M' => 1000);
+
 Modify 3.10.1(23)
 
 My_Car, Your_Car, Next_Car : Car_Name := new Car;  -- see 4.8
@@ -52,16 +63,7 @@
 
    function To_Roman_Number (S : String) return Roman_Number is
      (declare R : constant array (Integer range <>) of Integer :=
-        (for D of S =>
-             (case D is
-                 when 'I' => 1,
-                 when 'V' => 5,
-                 when 'X' => 10,
-                 when 'L' => 50,
-                 when 'C' => 100,
-                 when 'D' => 500,
-                 when 'M' => 1000,
-                 when others => raise Program_Error with "Impossible")) [<= Author's note: This is needed because S is of type String, even though precondition makes this impossible?]
+        (for D in S'Range => Roman_Digit'Enum_Rep (Roman_Digit'Value (S (D..D)))) --  See 3.5.2 [(and 13.4 ???)]
       begin
         [for I in R'Range =>
           (if I < R'Last and then R(I) < R(I + 1) then -1 else 1) * R(I))]
@@ -86,16 +88,15 @@
 
 Examples
    Put_Line ("Casey is " & (if Casey.Sex = M then "Male" else "Female")); -- See 3.10.1
+
+   function Card_Color (Card : Suit) return Color is --  See 3.5.2
+     (case Card is
+         when Clubs  | Spades   => Black,
+         when Hearts | Diamonds => Red);
+
+Modify after 4.5.8 (13/3)
 
-   function Value (Digit : Roman_Digit) return Natural is --  See 3.5.2
-     (case Digit is
-         when 'I' => 1,
-         when 'V' => 5,
-         when 'X' => 10,
-         when 'L' => 50,
-         when 'C' => 100,
-         when 'D' => 500,
-         when 'M' => 1000);
+pragma Assert (for some X in 2 .. N {when X * X <= N}[/ 2] => N mod X = 0);  --  See iterator_filter in 5.5
 
 Append after 4.5.10 (53/5):
 
@@ -119,23 +120,6 @@
       begin
         Acc.Sum / Real(Acc.Count));
 
-    A parallel reduction expression used to determine the set of prime
-    numbers within a range of values:
-
-   package Integer_Sets is new
-     Ada.Containers.Ordered_Sets (Element_Type => Integer);
-
-    function Is_Prime (Value : Integer) return Boolean is
-    begin
-       ...
-    end Is_Prime;
-
-    All_Primes : constant Integer_Sets.Set :=
-       [parallel for I in 1 .. 1_000_000
-          when Is_Prime (I) => I]'Reduce (Integer_Sets.Include,
-                                          [],
-                                          Integer_Sets.Union);
-
 Modify 5.5(22/5):
 "Example{s} of [a] parallel loop{s}: "
 
@@ -167,6 +151,8 @@
             ", Max=" & Partial_Max'Reduce(Natural'Max, 0));
 end;
 
+For an example of an iterator_filter, see 4.5.8
+
 Append after 6.1.1(42/3):
 
 6 For an example of the use of these aspects and attributes, see the Streams
@@ -185,49 +171,61 @@
 
    --  A work scheduler where only urgent work can be scheduled for weekends
 
-   package Work_Orders is
+with See_RM_3_5_1; use See_RM_3_5_1;
 
-      type Work_Order is private with
-        Type_Invariant => Day_Scheduled (Work_Order) in Weekday or else Priority (Work_Order) = Urgent; -- See 3.5.1
+package Work_Orders is
 
-      function Schedule_Work (Urgency : in Level;
-                              When    : in Day) return Work_Order
-         with Pre => Urgency = Urgent or else When in Weekday;
-
-      function Day_Scheduled (Order : in Work_Order) return Day; -- See 3.5.1
-      function Priority (Order : in Work_Order) return Level;    -- See 3.5.1
-      procedure Change_Priority (Order        : in out Work_Order;
-                                 New_Priority : in     Level;
-                                 Changed      : out    Boolean);
-
-   private
-
-      type Work_Order is record
-         Scheduled : Day;
-         Urgency   : Level;
-      end record;
-
-      function Schedule_Work (Urgency : in Level;
-                              When    : in Day) return Work_Order is
-         (Scheduled => When, Urgency => Urgency);
-
-      function Day_Scheduled (Order : in Work_Order) return Day is (Order.Scheduled);
-      function Priority (Order : in Work_Order) return Level is (Order.Urgency);
-      procedure Change_Priority (Order    : in out Work_Order;
-                                 Priority : in     Level;
-                                 Changed  : out    Boolean) is
-      begin
-         --  Ensure type invariant is not violated
-         if Priority = Urgent or else Order.Scheduled in Weekday then
-            Changed := True;
-            Order.Urgency := Priority;
-         else
-            Changed := False;
-         end if;
-      end Change_Priority;
+   --  See 3.5.1 for type declarations of Level, Day, and Weekday
+
+   type Work_Order is private with
+     Type_Invariant => Day_Scheduled (Work_Order) in Weekday
+                       or else Priority (Work_Order) = Urgent;
+
+   function Schedule_Work (Urgency  : in Level;
+                           To_Occur : in Day) return Work_Order
+     with Pre => Urgency = Urgent or else To_Occur in Weekday;
+
+   function Day_Scheduled (Order : in Work_Order) return Day;
+
+   function Priority (Order : in Work_Order) return Level;
+
+   procedure Change_Priority (Order        : in out Work_Order;
+                              New_Priority : in     Level;
+                              Changed      : out    Boolean)
+      with Post => Changed = (Day_Scheduled(Order) in Weekday
+                              or else Priority(Order) = Urgent);
+private
+
+   type Work_Order is record
+      Scheduled : Day;
+      Urgency   : Level;
+   end record;
 
-   end Work_Orders;
+end Work_Orders;
 
+package body Work_Orders is
+
+   function Schedule_Work (Urgency  : in Level;
+                           To_Occur : in Day) return Work_Order is
+     (Scheduled => To_Occur, Urgency => Urgency);
+
+   function Day_Scheduled (Order : in Work_Order) return Day is (Order.Scheduled);
+   function Priority (Order : in Work_Order) return Level is (Order.Urgency);
+   procedure Change_Priority (Order        : in out Work_Order;
+                              New_Priority : in     Level;
+                              Changed      : out    Boolean) is
+   begin
+      --  Ensure type invariant is not violated
+      if Order.Urgency = Urgent or else (Order.Scheduled in Weekday) then
+         Changed := True;
+         Order.Urgency := New_Priority;
+      else
+         Changed := False;
+      end if;
+   end Change_Priority;
+
+end Work_Orders;
+
 Append after 7.3.3(9.a/5):
 
 NOTES
@@ -240,6 +238,10 @@
 For an example of a raise expression, see the Streams Subsytem definitions in
 13.13.1.
 
+Append after 13.4(14)
+
+For an example of the use of 'Enum_Rep, see 4.2.1
+
 Modify B.3(78/3):
 --Calling the C Library Function{s} strcpy{, and printf}
 with Interfaces.C;
@@ -1497,5 +1499,325 @@
 
 I added a reduction example that uses a combiner function. (The prime number
 example)
+
+
+****************************************************************
+
+From: Ed Schonberg
+Sent: Thursday, October 3, 2019  5:15 PM
+
+The new examples are expressive, but the primes constructor using Reduce is
+incomplete (Is_Prime is incomplete) and both hard to read and much more
+inefficient than known algorithms. Of course, the good ones are sieves that are
+intrinsically sequential. I would prefer the following, as an example of
+iterator filters:
+
+ primes :=
+     (for I in 2 .. N
+          when (for all J in 2 ..I => J * J <= I and then I mod J /= 0) =>  I));
+
+****************************************************************
+
+From: Ed Schonberg
+Sent: Friday, October 4, 2019  10:15 AM
+
+Steve pointed out that the quantified expression as written is bound to fail,
+and in fact the upper bound should also be handled by means of a filter,
+so the proper code is:
+
+    primes :=  (for I in 2 .. N when
+         (for all J in 2 ..I when J * J <= I => I mod J /= 0)
+            => I);
+
+****************************************************************
+
+From: Brad Moore
+Sent: Friday, October 4, 2019  10:52 AM
+
+I found the same problem with the logic when I tried to implement this in
+Ada 2012.
+
+I agree that is a nice tidy way to express the primes, but I disagree that it
+is more efficient.
+
+In fact, I have implemented (in Ada 2012 this logic), as well as using an
+Is_Prime function, and the execution times are pretty much equivalent.
+
+But when I apply parallelism, as in my example, using the Paraffin libraries,
+I see that I get about 4 times faster results on my quadcore computer.
+
+The source code follows, as well as the output showing the execution times:
+
+with Ada.Command_Line;
+with Ada.Text_IO; use Ada.Text_IO;
+with Ada.Containers.Ordered_Sets; use Ada;
+with Ada.Real_Time;
+with Ada.Float_Text_IO; use Ada.Float_Text_IO;
+with Paraffin.Loops.Generic_Work_Seeking_Functional_Reduction;
+
+procedure Find_All_Primes is
+
+   Start : constant Integer :=
+     (if Command_Line.Argument_Count >= 1 then
+         Integer'Value (Command_Line.Argument (1)) else 2);
+
+   N : constant Integer :=
+     (if Command_Line.Argument_Count >= 2 then
+         Integer'Value (Command_Line.Argument (2)) else 1_000_000);
+
+   package Integer_Sets is new
+     Ada.Containers.Ordered_Sets (Element_Type => Integer);
+
+   Start_Time : Real_Time.Time;
+   Elapsed    : Duration;
+   use type Real_Time.Time;
+
+begin
+
+   --  Should be Equivalent to Ed's example
+   declare
+      --        Primes : Integer_Sets.Set :=
+      --          (for I in Start .. N
+      --              when (for all J in 2 ..I =>
+      --                        J * J <= I and then I mod J /= 0) =>  I));
+      Primes : Integer_Sets.Set;
+   begin
+      Start_Time := Real_Time.Clock;
+
+      for I in Start .. N loop
+         Inner_Loop :
+         for J in 2 .. I loop
+            if I mod J = 0 then
+               goto Next_I;
+            end if;
+            exit Inner_Loop when J * J > I;
+         end loop Inner_Loop;
+         Primes.Include (I);
+         <<Next_I>>
+      end loop;
+
+      Elapsed := Real_Time.To_Duration (Real_Time.Clock - Start_Time);
+
+      Put_Line ("Eds approach: " &
+                  Containers.Count_Type'Image (Primes.Length) &
+                  " primes found");
+
+      Put ("Elapsed = ");
+
+      Float_Text_IO.Put (Item => Float (Elapsed),
+                         Fore => 2,
+                         Aft  => 2,
+                         Exp  => 0);
+      New_Line;
+
+   end;
+
+   -- Should be equivalent to my example, but using sequential processing
+   declare
+
+
+      function Is_Prime (Number : Integer) return Boolean is
+      begin
+         for J in 2 .. Number loop
+            if Number mod J = 0 then
+               return False;
+            end if;
+            exit when J * J > Number;
+         end loop;
+
+         return True;
+
+      end Is_Prime;
+
+
+      Primes : Integer_Sets.Set;
+   begin
+      Start_Time := Real_Time.Clock;
+
+      for I in 1 .. N loop
+         if Is_Prime (I) then
+            Primes.Include (I);
+         end if;
+      end loop;
+
+      Elapsed := Real_Time.To_Duration (Real_Time.Clock - Start_Time);
+
+      Put_Line ("Brad's approach sequentially: " &
+                  Containers.Count_Type'Image (Primes.Length) &
+                  " primes found");
+
+      Put ("Elapsed = ");
+
+      Float_Text_IO.Put (Item => Float (Elapsed),
+                         Fore => 2,
+                         Aft  => 2,
+                         Exp  => 0);
+      New_Line;
+   end;
+
+   -- Should be equivalent to my example, but using parallel processing
+   declare
+
+      subtype Iteration is Integer range Start .. N;
+
+      package Integer_Loops is new
+        Paraffin.Loops.Generic_Work_Seeking_Functional_Reduction
+          (Loop_Index     => Iteration,
+           Result_Type    => Integer_Sets.Set,
+           Reducer        => Integer_Sets.Union,
+           Identity       => Integer_Sets.Empty_Set);
+
+      function Is_Prime (Number : Integer) return Boolean is
+      begin
+         for J in 2 .. Number loop
+            if Number mod J = 0 then
+               return False;
+            end if;
+            exit when J * J > Number;
+         end loop;
+
+         return True;
+
+      end Is_Prime;
+
+      procedure Process (Start, Finish : Iteration;
+                         Result : in out Integer_Sets.Set) is
+      begin
+         for I in Start .. Finish loop
+            if Is_Prime (I) then
+               Result.Include (I);
+            end if;
+         end loop;
+      end Process;
+
+      Start_Time : Real_Time.Time := Real_Time.Clock;
+
+      Primes : Integer_Sets.Set :=
+        Integer_Loops.Parallel_Loop (Process => Process'Access);
+
+   begin
+
+      Elapsed := Real_Time.To_Duration (Real_Time.Clock - Start_Time);
+
+      Put_Line ("Brad's approach in parallel: " &
+                  Containers.Count_Type'Image (Primes.Length) & " primes found");
+
+      Put ("Elapsed = ");
+
+      Float_Text_IO.Put (Item => Float (Elapsed),
+                         Fore => 2,
+                         Aft  => 2,
+                         Exp  => 0);
+      New_Line;
+   end;
+
+   --  All_Primes := [for I in 1 .. 2_000_000 => I]'Reduce(Integer_Sets.Include, [], Integer_Sets.Union);
+
+end Find_All_Primes;
+
+
+Output:
+
+Eds approach:  348513 primes found
+Elapsed = 13.01
+Brad's approach sequentially:  348513 primes found
+Elapsed = 12.88
+Brad's approach in parallel:  348513 primes found
+Elapsed =  4.49
+
+****************************************************************
+
+From: Brad Moore
+Sent: Friday, October 4, 2019  11:03 AM
+
+Also, I should mention, the inputs to the program that provided the results below were:
+
+./find_all_primes 1 5_000_000
+
+
+And the Is_Prime function if we wanted to include it in full in the RM could
+be written as;
+
+     function Is_Prime (Number : Integer) return Boolean is
+        (for all J in 2 ..Number when J * J <= Number => Number mod J /= 0);
+
+Which still provides the same filter example, and perhaps is a bit more
+readable due to being a simpler expression.
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Friday, October 4, 2019  11:16 AM
+
+This does seem simpler and easier to understand.
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Friday, October 4, 2019  11:27 AM
+
+By the way, whenever I have seen something written like this, the high bound
+has always been N/2 rather than N since we know Floor(Sqrt(N)) <= Floor(N/2),
+presuming N > 1.  So perhaps:
+
+   function Is_Prime (Number : Integer) return Boolean is
+      (Number >= 2 and then
+         (for all J in 2 .. Number/2 when J * J <= Number => Number mod J /= 0));
+
+With your original Is_Prime(1) = True ;-)
+
+****************************************************************
+
+From: Ed Schonberg
+Sent: Friday, October 4, 2019   2:56 PM
+
+> And the Is_Prime function if we wanted to include it in full in the RM
+> could be written as;
+>
+>     function Is_Prime (Number : Integer) return Boolean is
+>        (for all J in 2 ..Number when J * J <= Number => Number mod J
+> /= 0);
+>
+> Which still provides the same filter example, and perhaps is a bit
+> more readable due to being a simpler expression.
+
+the parallel code is a nice example. but in terms of performance this is still
+quadratic in the number of divisions. The standard sieve is not easily
+parallelizable but it's linear and only uses additions.  by the way, can the
+quantified expression be marked parallel?
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Friday, October 4, 2019  7:39 PM
+
+We have not proposed allowing "parallel" in a quantified expression, though a
+quantified expression is essentially a special case of a reduction (universal
+is a reduction over "and" with identity "True" while existential is a
+reduction over "or" with identity "False"), so it would certainly make sense
+to allow "parallel."  I have argued in the past that these constructs are
+simple enough and self-contained enough that the compiler could probably
+decide on its own whether a parallel evaluation would be safe and would
+produce any savings.  But since that argument didn't "fly" for explicit
+reduction expressions, it seems like it probably wouldn't fly for these
+"implicit" reductions.
+
+****************************************************************
+
+From: Brad Moore
+Sent: Sunday, October 6, 2019  1:32 PM
+
+Here is an update to the RM Examples, which hopefully addresses all comments
+from yesterday. [This is version /07 of the AI - Editor.]
+
+I removed the example with of a reduction expression with a combiner function,
+as we said we wanted to create a new AI to include such an example, once we
+come up with one.
+
+I changed the Roman numeral conversion example to make use of the existing
+Roman_Digit type. I also defined an enumeration rep clause for that, and use
+the 'Enum_Rep attribute to do the conversion.
+
+Also the Work_Order example we reworked so that it could actually compile.
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent