Programs & Geometry Theorems

In the preceding post I linked the regular expressions that define tokens in a programming language to the definitions in a formal mathematical system. Productions of the grammar that define the language, I said, were axioms. The programs we write in that language are theorems.

The definitions and axioms of Euclid's Geometry construct a formal mathematical system. The proof of theorems in geometry "stand on the shoulders" of other theorems. For any theorem there is a "tree" of theorems. The theorem to be proved is the root node of the tree. Definitions and axioms are the leaf nodes. That is how the complete system is constructed.

That is how programs should be constructed. Sure, everyone constructs programs that consist of functions. But do we check the complexity of the functions? We need to refactor till we get functions that have low complexity. Such functions are easy to inspect and easy to test (unit test). If all the functions in the call tree of a function have been "proved" - by inspection and unit test coverage - then the function itself stands on a "proven" foundation.

Programs must be "proven" with rigor approximating the rigor with which geometry theorems are proven. Tools for Complexity metrics, Refactoring, Unit Testing, & Coverage metrics are the instruments that help in doing this.

Earlier post on the subject.

Humility & Courage

Humility is not lack of confidence. Bravado is not courage.

I believe that Humility & Courage are essential traits for doing quality software work. The reality of software development teaches that. Refusal to learn this lesson is a root cause for poor software quality and dysfunctional teams.

Humility.
Humility means being aware that one could be wrong; that one's understanding has gaps. Humility leads us to always question our assumptions; to always put them to the test.

Defensive coding is humility. Assert statements check one's mental model of the state of execution of the code. It is accepting that one could be wrong.

Recognizing the primacy of unit tests that can be easily and frequently run, and provide appropriate coverage metrics, is humility. Adding tests that increase coverage metrics is humility.

Humility is a prerequisite for learning.

Courage.
Visually challenged persons are not be able to walk briskly. But they learn to progress by testing their way with the help of a cane. That is courage.

As software professionals we should realize that we are "visually challenged". Courage is "tapping" our way forward. The "tapping of the cane" are experiments that we must conduct to improve our understanding. These experiments have to be small steps.

Resolutely "tapping" our way to our objective is Courage.

Agile.
An Agile process is about Humility & Courage.

Why Did Some Dog Not Bark?

In an earlier post I had described as to how unit tests are "dogs that should not bark". Meaning that Unit tests run "All Green" as code is added, modified, refactored. When a unit test fails, prompt action is taken to get back to an "All Green" state.

One situation when "silent dogs" should be a serious concern is when the signature of a function is changed. That means unit test for the function is missing. That means TDD was not followed. That means a Defect in the Process.

Another situation is when a defect is discovered while inspecting the code. A little while back I had experience of that.

It was an expression that computed the radius of a circle given the length of a chord and the distance of the midpoint of the arc from the chord. High school stuff. The expression was correctly worked out in the explanatory documentation. But in the code I forgot to divide the expression by 2. I plugged the function into the module and merrily carried on. The defect was found by a member of the team that I was coaching. I asked for comments from the team. The best answer: "The dog did not bark". I had the satisfaction of knowing my coaching had been effective😊

I had not followed TDD. My Process Had been Defective. 😢

Lesson: No matter how simple the algebraic expression, use TDD to implement the function.

Specifications & Unit Tests

In my preceding post I said that writing requirements & specifications must precede the writing of code and they must be written in the source file. Stands to reason. If code has to be written, it must be for a purpose. The purpose must be known before writing the code that is expected to meet the purpose. Therefore, it can - and should - be recorded before coding.

But specifications, instead of being entered as documentation in source files, can be put down in far more useful form. They can be recorded as Executable Specifications. What are executable specifications? They are Unit Tests. Watch this exposition by Misko Hevery (from ~17:28 till ~ 24:00) for how to write Executable Specifications. BTW, the complete video is worth watching.

Importance Of Geometry

I believe the subject of geometry to be the most important subject taught in schools. It is first rate preparation for the mind for any profession that that requires reasoning. Abraham Lincoln kept a copy of Euclid's Elements of Geometry in his saddlebag, and studied it late at night by lamplight; he related that he said to himself, " … you never can make a lawyer if you do not understand what demonstrate means; and I left my situation in Springfield, went home to my father's house, and stayed there till I could give any proposition in the six books of Euclid at sight. I then found out what demonstrate means, and went back to my law studies" (see The Abraham Lincoln connection.)

A very readable translation of the 13 books of Elements is available here.

Euclid built geometry on ten postulates (axioms). In addition to the axioms, each of the books contains definitions of the geometric terms used in that book and following books. No symbols (as in current geometry textbooks) are used. This make the proofs verbose. The proofs are all graphical as Euclid did not have symbolic algebra that we use today. What he had was Geometrical Algebra. The proof of Pythagoras’s Theorem is an example.

Application of Euclid’s Method to Software

Software should be provably correct. The propositions in Euclid’s books rest on propositions proved earlier. The initial propositions of Book 1 depend just on the definitions and axioms. They are like the leaf functions in a program. I believe that software constructed in the same way will result in provable software.

What a function should do (including any side-effects) should be clearly documented like a proposition. The function body itself is equivalent to a sequence of geometric constructions.

I have found that writing unit tests drives the process of re-factoring code into simpler functions. If unit tests are getting messy, the function under test is messy. The function must be re-factored.

Unit tests and re-factoring are the initial stages. These must be followed by proof of correctness of the construction. The process is not linear; it is cyclical. If the proof is difficult, decompose the function yet again.

A proof answers the question, “Why will this do what it is meant to do?” It should be part of the function documentation. Correctness of the proof must be attested to in the same manner as mathematical proofs. It must be accepted by peers who understand what is being coded.

Assertions, Preconditions, and Post-conditions are akin to lemmas. They are simpler to prove. In addition they have the added advantage of being executable.

Of course, proofs, despite peer reviews, can be defective. That does not mean they should not be attempted. We should learn from defective proofs.

Beautiful Code: Testing a Binary Search Implementation

The Binary Search algorithm has been around for quite a while. I remember doing an implementation (in Fortran) as part of course work in 1977. Hence it was a surprise to read about it in Joshua Bloch's blog post. I am  pretty sure that what I, and the rest of the course, implemented had the same defect.

Alberto Savola in his essay "Beautiful Tests" in Beautiful Code, quotes Donald Knuth as saying that though the first binary search was published in 1946, it took 12 more years for the first binary search without bugs to be published. However, defective implementations could, and did recur.

All very humbling. To quote Joshua, "The general lesson that I take away from this bug is humility".

Alberto Savola's piece uses the Binary Search program to show how tests should be developed. Here are some topics that I found educative:

• The utility of smoke tests.
• Re-factoring code to improve testability. A side-effect of this is to improve the design and the readability of the program.
• The design of tests to verify that neither a true condition is detected as false nor a false condition detected as true. What in radar theory are called failed detection and false alarm.
• Formulating theories (I think calling them hypotheses, would be more appropriate) of the forms: If A is true then B should be true; If A is not true then B should not be true. 
• Random generation of tests. This is most intriguing. I wonder if genetic algorithms could be used to generate tests.
• The use of helper tests that give an alternate way of checking. These are simple tests whose correctness are easy to verify by visual inspection. For the binary search a test using a linear search is also implemented. The linear search is used to cross check results obtained using the binary search.

A quote from Savola:
"Truly beautiful testing requires a developer to make an effort, think outside the box, explore weird scenarios, look for weaknesses, and try to break things".
(Note 1: The emphasis is mine.
Note 2: A side note: "outside the box", I think, is a more appropriate expression, in such contexts, rather than the more commonly used "out of the box".)

Bolt or Jackie?

I was in conversation with someone who said he had experience of agile methodology at one of the companies he had worked at.

I asked him to describe agile development. The first statement that he made was, "It is for fast development."

Not quite correct. Agility is not the same as speed. Usain Bolt is the fastest human. I doubt if he is anywhere near the most agile. Arguably the most agile would be Jackie Chan. Though Mr. Chan would undoubtedly be quick, I doubt if he is a world class sprinter. I doubt if Mr. Bolt would qualify for the Jamaican acrobatics team.

Agility is the ability to respond to surprises. It needs muscular coordination, quick reflexes, flexibility, excellent sense of balance, and sixth sense.

A software process that focuses on speed wants to anticipate all surprises. It is about risk minimization. It invests in up-front detailed design and the associated processes to ensure that the plan is followed. It needs a clearly marked standard track to sprint down.

A software process that focuses on agility acknowledges that the only thing that can be said in advance about surprises is that they will occur. It is not about speed of development but speed of response to surprises. Speed of response to surprises needs leadership with a mindset that is willing to accept surprises - not sweep them under the carpet. It needs leadership with a mindset willing to invest time in keeping the code malleable at all times.

When I asked my interlocutor to name some of the agile practices, the only one he mentioned was morning ten minute stand-up meetings. Questioned as to how it was determined if the day's commitment was achieved, or not, there was no answer. (Expected Answer: unit tests that pass.)

Malleability

Malleability is that property of a material that allows it to be easily shaped. Gold is malleable. Stone is not.

Code should be malleable.

Polymorphism (from the Greek poly meaning "many", and morphe meaning "form, shape") adds to malleability. So do unit tests. Coupling destroys malleability. Cohesion enhances it.

Reluctance to modify code is a sure sign that malleability is being degraded. Attend to it. If it is hard to do now, it is not going to easier on its own.

Code that is not malleable become "Bhoot Banglas". Code that is not malleable is code that is petrified (from the Greek petro for stone). Petrified code leads to petrified code maintainers.

Pre-Conditions, Post-Conditions & Unit Tests

Recently I wrote a class for program flow-graphs. Writing unit tests, it turned out, required more effort than the unit tests that I had written for other classes .

I was aware that when writing functions one must document the pre-conditions and the post-conditions. These I implemented as asserts. I usually felt that these were adequate. But when it came to the program flow-graph methods, the set of asserts was turning up to be just too messy

As I mentioned, the development of unit tests was turning out to be more difficult. The program flow-graph object to be used for the test had to be decided. What it would be transformed to was to be worked out. I found myself putting these down, in the test case file, as a file comment block. While doing that, I realized I was effectively specifying Pre-Conditions and Post-Conditions. I was saying, "Given this program graph object as the input, some set of attributes should change, and some set of attributes should remain invariant".

Light-Bulb event: Unit tests are statements of Pre-Conditions and Post-conditions.

What about asserts? I now regard these as micro unit tests that are embedded in the code.

PS: I hope to be more frequent in my posts in 2014:-)
Happy New Year.

Test Driven Development

For the past few months I have had to write C code. As some readers of this blog would know, for the past decade I have been preaching, or to use a more polite term - evangelizing, a great deal about software process and about coding practices. All of what I preached was from books that I read. What I read had enlightened me as to the mistakes I had when I was coding over the preceding decade.

The code has to be in C. I wanted to do test driven development. When I had tried to introduce unit testing in our compiler work at acmet, a major problem was the non-availability of a suitable C unit testing tool. This time around I came across the book Test Driven Development for Embedded C. It describes the use of CppUTest. I have gone through about half the book. That is sufficient for my present requirement. All the code that I am now writing is test driven.

A few weeks ago, I had to provide code for a small problem posed by one of our development teams. I found refactoring my code to create the needed modules much less of a problem than I had imagined. I could not have done it quite that easily had I not had the units tests. The discipline of TDD I found leads to far easier and better modularization. I could with full confidence hand over the modules to the concerned team.

For those doing embedded systems programming in C, I strongly recommend adopting the methods described in the book