To be specific:
"Finite Field Arithmetic." Chapter 1: Genesis.
Chapter 1 starts with a background on the FFA code and a list of the files you need to start out with. It contains a link to FSF GNAT, but a gnat like this will not work as either the ADA part is broken (gcc < 5) or the gcc itself is tampered with (gcc > 5). You will need a GNAT from adacore1.
Next comes the unpacking and building description, following this part is straightforward.
For building the code, the gprbuild
tool is used. This is a typical alternative build system, this one has superior support for ADA. I do not recommend it for anything else. If you do not trust this tool, it is not hard to write a makefile or a simple bash script based on the few command line parameters given in this script. Of the flags used, I still have one -fdump-scos2 that seems unnecessary, apparently it creates coverage information.
After the description of the build we get this line;
Do not run the demo yet. (you read programs before running, don’t you?)
No, I do not!. I have not read gcc or this previously unknown 'gprbuild'. And those where unsigned!
The code starts with a file that did not readily fit in my head; restrict.adc. The only way to get to grips with this file was reading the gnat documentation and the ada reference manual. I made a list of all restrictions according to the GNAT documentation and then checked which where used. To summarise; everything that touches any tasking (ada term for multi-threading) is off limits, everything that does dynamic allocation is off limits, everything that depends on a clock is off limits (delay and Calendar), plus some more to make the code as static as possible. A lot of these pragmas are specific for GNAT. One, I could not find documentation for: "No_Fixed_IO". This is the list of restrictions available in GNAT but not used by FFA3.
No_Anonymous_Allocators Max_Storage_At_Blocking Max_Entry_Queue_Length No_Access_Subprograms No_Dependence No_Direct_Boolean_Operators No_Exception_Handlers No_Exceptions No_Fixed_Point No_IO No_Local_Allocators No_Long_Long_Integers No_Recursion No_Reentrancy No_Specification_of_Aspect No_Use_Of_Entity No_Obsolescent_Features SPARK_05 No_Implementation_Pragmas
The implementation is split up over different ADA modules, you can read the code on the site but make sure to study the copy created in the V-press.
The first module is defined in 'iron.ads', it is specified to be a Pure module, meaning the package will not have an internal state4. In 'iron.ads', we get to define the size of a word expressed as a number of bits per word, this is called MachineBitness. And a ByteBits, which is needed for communicating the ffa words as this will be on a per byte basis. Unfortunately, it also defines a MachineBitnessLog2, to be explained in another chapter5.
The next module words.ads.This is a fun paragraph, try to parse it
.. of FFA, the machine Word. A Word, from this point on, is simply a single machine word on your particular machine.
Or a little bit less self-referential; Word is the smallest unit used for the arithmetic in FFA, values of type Word can range from 0 (inclusive) up to 2 to power of the Bitness (exclusive). Remarkably, 'WBit_Index' is also defined here and maybe the bit is the smallest unit in FFA6
I could not determine the reason of this line; for Word'Size use Bitness;. The standard, does not help7.
The 'w_shifts.ads' is a module to include the shifts, ask yourself, why not use the pragma Provide_Shift_Operators?
The 'word_ops.ads' file is an irritating Ada necessity, all important information is in 'word_ops.adb'. This last file must be inspected in depth. The carry and borrow functions are brilliant inventions so pay close attention, some extra comments and hints are provided (
The W_Mux function will be used for all selections and it needs a lot of attention too. Ask yourself; "If WBool is defined as subtype WBool is Word range 0 .. 1;, what is the result of (Sel-1) if Sel is 0?", plus "In how many ways can Mux be defined?"
W_Mux and W_Swap are both unused in this chapter.
The module 'fz_type.ads'; "Gaze upon the combination of abstract mathematical concepts and low level bit fiddling, all in one small library!". Ask yourself; "Do we need Word_Index or Indices?8".
In 'fz_arith.ads', the Precondition pragma is used twice. An array Words with unspecified length is denoted by FZ, addition and subtraction are defined for values of FZ of equal length, hence preconditions are needed to check the lengths for all instantiations of these functions.
The code in 'fz_arith.adb', is not very complex but does close need attention9. Look at the summation, the sum is (A+B) + Carry, but the next carry is determined by just A, B and the Sum. Are we lucky this is correct?. The whole comment starting with The alert reader might ask why the iteration schemes differ... could have been avoided by making the FZ_Add iteration scheme follow the FZ_Sub scheme. This would increase the usefulness of FZ_Add.
I will skip commenting on the input/output and demo
The comments section is interesting, especially seeing how the only non-used function (W_Swap) gets all the attention
- specifically 2015 or 2016, not earlier and also not later. [↩]
- see GNAT User's Guide [↩]
- Why not use No_Fixed_Point or No_Reentrancy? [↩]
- Ada has a complex module system all kinds of silly rules. [↩]
- I recommend to remove this, when you implement this promised chapter it will then quickly fail and you can see if it is explained. [↩]
- This is another unexplained constant, probably "to be used later". So a good algorithm for understanding the FFA code would be to remove every statement / definition that is not used in the same defining chapter, to be added if and when needed. [↩]
- First let's read the "Static Semantics", it mentions 2 situation where this matters, one is about packed records, I would set the size for a Word in packed records on a case by case basis. The other situation is for "untyped conversions" and these should never happen in FFA code. For fun, let's read "Implementation Advice", this is typical Ada language reference manual language. [↩]
- This is a serious question, as each new type/subtype definition introduces an extra concept to be dealt with an understood. [↩]
- For example; from the fact that this code compiles, we can conclude that Ada is case insensitive. [↩]
Tags: Review
Some of these questions are answered in today's log..
Re: the restrictions: aside from the "No_Recursion" item (prohibited on account of Karatsuba), the bulk of the unused ones were simply not present in my particular GNAT. (Every GNAT I've used, barfs on encounter with any restriction it doesn't know about; try it yourself.)
"No_Exception_Handlers" and "No_Exceptions" are absent for the obvious reason. Ditto re: "No_Long_Long_Integers".
Theoretically 2017 GNAT ought to work, but you will have to fiddle with the Restrictions.
The general idea is to build under the tightest possible (but not tighter... see above) set of Restrictions for any particular GNAT.
Dear Stanislav,
As for: "Do we need Word_Index or Indices?". I'm all for constraining a type, so defining a custom (and different) index type for words and bits etc. But why not derive these directly from Natural and have an extra Indices. (BTW It is only a small point)
As for: "Are we lucky this is correct?", I'm sorry this comes over as an accusation that it was not worked out in detail by you (I've followed the development, and know and appreciate your thoroughness!). I hoped to motivate the reader to work this out in head or on paper. My original analysis of the Carry / Borrow code did not take into account an extra possible carry from an earlier summation / subtraction.
As for the restrictions: I like the use of as many restrictions as possible (creating a list of the restrictions that were not used was mainly an exercise to understand the list itself). I only find them hard to "fit in head" (consequences including).
Yours,
-A.
> But why not derive these directly from Natural and have an extra Indices
On certain platforms, we would want Indices to be, e.g., a 16-bit word, rather than a 32-bit Natural; and at any rate on ~no~ platform do you actually ~require~ a full "maxint" range for indexing arrays of Word (think about it.) The formulation given in Ch. 1 makes for a clear type hierarchy. (Really, anywhere you see "Natural" is simply a placeholder for a narrowly machine-specific type, if such were available.)
> I only find them hard to "fit in head"
The clearest, IMHO, way to think about this: the restrictions, properly speaking, are not part of the program; they are statements ~about~ the program, which certain compilers are able to mechanically verify.
To put it another way: the behaviour of the program should not change upon a removal of any or all of the restrictions, supposing that the compiler (e.g. my copy of GNAT) on which the same program was able to build ~with~ the restrictions is not buggy/malicious and did not lie regarding having enforced them upon that successful build.
Thank you Stan for these explanations!
I understand, the Indices type is defined so it can (optionally and/or later) be re-defined for different platforms. And we have then one place to do so.
As for restrictions, I get it (and re-reading the GNAT documentation with your explaination in mind, makes it clear)
Yours,
-A.