CVS difference for 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