Programming Pearls Col 4 – Writing Correct Programs

This column uses a simple and almost trivial example of writing the code for a binary search algorithm. Even programmers who so confidently claim that they can write flawless code ended up writing buggy code, and it’s simply because humans are always prone to error and we need to accept that.

Two principles to verify an iterative(loop) control structure:
-Define the invariant precisely (conditions for loops)
-Maintain the invariant as we write each line of code – key to converting algorithm/pseudo code to code

How to do the second one:

  1. Initialization: invariant is true at first iteration
  2. Preservation: invariant remains true at end before next iteration
  3. Termination: set clear termination conditions

Tools Used:

  • Assertion statements to enunciate states of the program
  • Do this then that control
  • Choose from cases control

Here’s the iteration control structure discussed in this column, simplified:

Drawing.png

Reflection:

This column touched on one of the most important topics – testing and verification. I think it gave that further explanation needed of so many things that computer science students were taught in class to do when they test the programs they write but never prompted to think deeply about the reasons behind them.

You may know what assertions are for, but why use assertions instead of just print statements? You know logical proofs are good for exercising your mathematical senses but how can it be applied to programming? Why do we need to write the obvious preconditions and postconditions for every class method? Why do we want to be able to explain every single line of code, besides just for the sake of being able to explain every single line of code? Why do we always have to be so meticulous about sanity checks?

It’s such a simple principle, yet so many people have overlooked it: it all boils down to that in order to be a “lazy programmer”, one that is different from a “hardworking programmer” who writes hundreds of lines of code for a simple program and spends days debugging it. Writing messy code to save time on the spot and then debugging like you’re trying to find that one needle in the bottom of the ocean is pure suicide. We need to be aware of those tools and keep looking for the best way to be efficient and save more time and effort in the long-term, thus being “lazy” in the smartest way possible.

After reading this column, I’m convinced that every college computer science student deserves to be fed all the knowledge in this column right after they finish any kind of “fundamentals of computing” classes because I’ve already made countlessly many connections to my data structures, discrete math, and assembly classes.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s