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