Ossa Sepia

April 17, 2019

Reading Notes on FFA Ch1 - Ch4

Filed under: Coding — Diana Coman @ 7:57 p.m.

While Stan says - and I believe him - that each chapter of FFA is meant to take one somewhere between 1 and 2 hours to grasp, I can confidently say by now that either I don't do grasping at all1 or I'm a very, very slow grasper/learner (quite possible at that). Sure, I could always *read* one FFA chapter in 1-2 hours and even with pen and paper but it took way longer to get to the point where I'm happy to sign it. And yes, it's also perfectly true that *now* it takes me about 1 hour give or take to go *again* through one of the FFA chapters I have already studied but that's the sort of "oh, 3 hours only; after how many years?" timing. While part of this "speed-up" is inevitably down to familiarity with the material, there is also a large component of pitfalls that I can avoid now, after having been in and out of them before. And while I tend to at least not fall for the same mistake twice, this is not to say that having the obtained notes written down in one place is useless - at the very least, they will serve me as a quicker way of getting back into FFA at a later stage, a bit of quicker-loading of sorts.

The structure of FFA itself is quite logical but I still kept stumbling over / forgetting bits and pieces as I went. So I made myself a map of the FFA packages, updated with every chapter and kept handy for easier reference. I found this map especially useful as a way of making sure I don't miss anything since otherwise the FFA series is (by design, I think) quite strictly presented from the bottom up and I tend to struggle to keep in memory all moving parts unless I can link them together even in the loosest of ways to some bigger picture2. So here are my FFA3 maps so far with whatever observations, comments and various nitpicks of all sorts I still have attached to each chapter.

Chapter 1

This chapter introduces the very foundation of FFA: what is a FFA number (FZ by its name), what is it made out of ("Word" components), how can one do - in constant time, of course - basic operations at Word level and very simple arithmetic operations (+ and -) with whole FZs. Crucially, this chapter introduces FFA's approach to implementing "if" without actually branching: the Mux selector. Notes and nitpicks:

  • Packages are Ada's units for structuring code, hence the units in the diagram below are exactly that: Ada packages. The ".ads" only packages happen to not have a body - this means simply that they group together a set of definitions (types, constants, variables or even imported procedures/functions) but do not require/have anything else.
  • In Words.ads I puzzled at first over why not use for Byteness both Iron.MachineBitness and Iron.ByteBits rather than using one constant from Iron and one local to the Words package, especially since the local value is defined precisely equal to the one in Iron and I still get confused over simple names like that. I suppose the idea is though that this is not necessarily true if one wants to have a Word that doesn't directly match the underlying iron (or rather the other way around: if one runs the program on whatever non-standard iron). Alternatively I suppose one can simply define "MachineByteness" in Iron as well and then simply define Words.Bytness = MachineByteness. It's just the mix of the two that pokes me in the eye even though it's just such a tiny detail.
  • In FZ_Type my inner maniac keeps asking: why Word_Index and not FZWord_Index, why Word_Count and not FZWord_Count given FZBit_Index? Sure, there is no other word_index than the one in a FZ (while there are bits in a Word too for instance) but each tiny non-standardised name adds to the number of things I need to remember and my memory for this sort of stuff is pretty much entirely absent. So for all the additional, annoying task of having to write FZWord_Index every time instead of the shorter Word_Index, I'd still rather do it and standardise the names: if it relates to a FZ, then it starts with FZ (or any other standard really, as long as it doesn't have exceptions).
  • The W_Mux is a FUNDAMENTAL mechanism of FFA: effectively it is "if" the FFA way (i.e. constant-time and without actual branching). So it's worth studying this in more detail if you are not familiar with the way a mux works.
  • The WBool type can be at times a bit ambiguous in use since it's both a true/false sort of thing by definition (1 and 0 are the only values it can take) but also the direct result of arithmetic operations. The key to this is of course the fact that the arithmetic operations in question have a 1-bit long result (or look at only 1 bit of a larger result) and so their possible range of values is restricted to 0 and 1.
  • In W_Shifts the Amount parameter is everywhere of Natural type, presumably to fit the import requirements. However, given the intended use as part of FFA, I think this should logically be one of the Index types defined and most specifically WBit_Index (from Words.ads) since those shifts are done at word level (hence any shift by more than WBit_Index'Last is just the same as a shift by WBit_Index'Last anyway).
  • A crucial observation regarding indices and counts: a FFA number (i.e. a FZ) can have by definition any range of indices for its component words (e.g. an FZ could be composed very well of 3 Words on positions 4, 5 and 6 in principle) BUT it has to have at any given time AT LEAST 1 word. This of course is perfectly sane since there is no such thing as a number of 0 length (0 itself has length!) but it's worth noting it since it comes into such wonderful contrast with previous sad "bignum" implementations that confuse 0 with "doesn't exist".

ffa_ch1_struct1

Chapter 2

This chapter adds logical operations (i.e. "predicates") at Word level and new operations with FFA numbers (FZs), most notably logical operations, bit operations and comparisons. A crucial part to get here correctly is the convention used throughout FFA for the order of words and bits. While "endianness doesn't matter", nevertheless "set_head", "get_head", "shift_left" and "shift_right" do imply a direction and messing with *that* turns out to be for me a lot of pain. After quite a few times tripping over this in various places, I found I'd rather NOT use Stan's convention that "most junior bits on the left" as that just doesn't work for me: the "FZ_Get_Head" returns "lowest, bottom-most word" wtf head is bottom!!; the directions for shift_right and shift_left are inversed (since their names fit the "most senior bits first" representation) and moreover one is sort-of having to think of the whole number in reverse representation all the time. The ONLY reason I can see for this is so that indices increase from left to right but honestly, it's way, way easier for me to count from right to left (or in decreasing order!) and keep everything else in place than to keep the counting direction in place at the cost of having to remember repeatedly that the "direction" of all sorts is the opposite to what is written down. So I go with the following approach instead:

  • FZ for me are represented with most senior words and bits on the left. If you prefer, call it big-endian. I'll just call it human-convention. The machine doesn't care either way but it helps me tremendously to understand what goes on (see below).
  • Given the above, all bit-level and word-level operations actually fit the direction given in the name: a shift_left moves numbers to the left and therefore to higher positions, increasing the value of the FZ (i.e. it's a multiplication by 2^Amount); a right_shift moves to the right, to more junior/lower positions, decreasing the value (a division by 2^Amount).
  • The index (if it starts at 0 anyway) neatly matches in fact the power of the base corresponding to that position if one was to convert to denary. So it's no additional load for me at least to look at it as increasing from the right to the left.
  • I think Get_Head/Set_Head would be better named at the very least Get_Bottom/Set_Bottom or, even better, Get_Junior/Set_Junior or similar. I don't want to... turn the left-right convention on its head just to have in there also the head/bottom convention. Instead, I think it's best to stick ideally to the *role* of the Word/bit retrieved (i.e. most junior) rather than marrying it to the position in any given representation and if this ideal is too much to ask for then at least as the next-best keep it within the already imposed convention of left-right and NOT add yet another convention to the mix4.

ffa_ch2_struct

  • Most of the procedures involving 2 FZ have as precondition that the lengths of the 2 are the same since otherwise comparisons and copies hardly make sense. While this makes sense in itself each and every time, it seems to me that FZ_Mux for instance *also* relies on the FZ having the same *range* of indices. While I'm sure that the later FFA use of FZ_Mux does not end up feeding it FZ with different ranges, I wonder whether there is any significant penalty to making FZ_Mux NOT rely on the FZ having the same range? Or is there some reason that I'm missing for requiring the same range?
  • What is exactly the need for FZ_Get_Head and FZ_Set_Head anyway? I could see the idea that it's a way to ensure that everything remains as it is even if one decides to move the head somewhere else (to the end) but for one thing I find them confusing (perhaps my fault, sure) and for the other FZ_And_W for instance still uses N(N'First) rather than FZ_Get_Head(N)/FZ_Set_Head so changing the position of the head would still require some changes in other code.
  • Why is fz_cmp a separate package? As far as I can see, the contents of this one are still FZ predicates so I'd put them totally fine into FZ_Pred. I'm not sure that the distinction unary (fz_pred) vs binary (fz_cmp) predicates really requires a different package or that FZ_Pred is growing way too big if it swallows up FZ_Cmp.
  • Perhaps make all the packages related to Words start with W_ so that there isn't a Word_Ops but a W_Pred and W_Shifts?

Chapter 3
This chapter adds the shifts for whole FZs. Once I remembered to stick to "most senior words/bits to the left", the rest is quite straightforward to understand. And I don't even have any nitpicks left for it, can you believe that?
ffa_ch3_struct

Chapter 4
This chapter focuses on introducing FFACalc and as a result the changes/additions to FFA lib itself are minimal: a new subtype "Nibble" in words.ads; FZ_NZeroP in fz_pred; WBool_To_FZ in fz_basic; a new package for enforcing/checking valid bitness, fz_lim. The difficulty of this chapter is mainly in getting used to FFACalc. As with the rest of the FFA series, the best way I found was simply to sit down and try and write myself the code that would do one or another thing - it turns out that there aren't all that many significantly different approaches given the existing building blocks and moreover, any differences are informative, usually of one's own mistakes/current lack of understanding. So without further nitpicks, the updated diagram looks like this:
ffa_ch4_struct

Update 18 April 2019 - the diagrams above are made with Dia so here are the .dia files if you want to tinker/change them for your own use: ffa_ch1_struct.dia ; ch2.dia; ch3.dia; ch4.dia.


  1. Perhaps I do only bulldog-style vicious hold-and-never-let-go. It goes with attention to detail and various other traits in my inventory. 

  2. A bottom-up approach has its advantages and it's not in itself a problem at all, of course, except that one needs to keep going for quite a while without really knowing where they are going. It's not even a matter of trust - I certainly trust Stan that he knows where he's going and he even drops clear hints on the way. It's simply that I find it easier to follow and retain the detail if I can also place it even vaguely in some bigger picture. On the bright side, I can say I have *plenty* of practice with the strictly bottom-up approach since my Romanian education followed precisely this approach and nothing else to the point that it took more than 10 years of school for some things to finally click as belonging *somewhere*. So yes, by comparison to that, FFA is far, far less demanding of the learner's trust and patience. But my overall learning experience has always shown that it helps - me at least - to have a more balanced approach. 

  3. I focus on the FFA lib itself so the Demo/Peh are so far not included. 

  4. I'm aware that there are and can be as many conventions as there are mouths to emit them. Still, every new convention added to the mix has a cost and I'd much rather keep this down as much as possible. First of all for myself, yes. 

No Comments »

No comments yet.

RSS feed for comments on this post. TrackBack URL

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <pre> <q cite=""> <strike> <strong>

Theme and content by Diana Coman