OOP and Discrete Math

Published in volume 20, issue 1, January 2010

This issue has three terrific papers. The first, Verification of real-time systems design, by M. Emilia Cambronero, Valentín Valero, and Gregorio Díaz, presents a way to verify aspects of software during design. The second, A systematic representation of path constraints for implicit path enumeration technique, by Tai Hyo Kim, Ho Jung Bang, and Sung Deok Cha, proposes to encode path constraints into "flow facts" to improve the accuracy of implicit path enumeration. The third, Fault localization using a model checker, by Andreas Griesmayer, Stefan Staber, and Roderick Bloem, gives a method for using model checking information to not just identify software failures, but to help find where the corresponding faults may be located.

I learned a new word last year. A retronym is a descriptive word that was not needed before a new word came into being. When we started writing object-oriented programs, we needed a new word for what we used to do (procedural programming). Procedural programming had the advantage of following directly from algebra; a C function is essentially an example of applied algebra. We all took algebra in high school, so learning procedural programming in college was straightforward.

But OO programming uses concepts that do not appear in algebra! My daughter took Java programming in high school last summer. She was introduced to classes, inheritance and polymorphism as follows: "These are new concepts unlike anything you've seen before. Thus they are a bit hard to swallow at first."

I gave her all kinds of examples from real life (watches and wall clocks inherit from general clocks, rocking chairs and desk chairs inherit from chairs, which inherit from furniture, ...). But it struck me that we have no mathematical context for this. Yet programming is always very mathematical!

I didn't learn OO programming until the end of graduate school in the 1980s. In fact, I didn't see information hiding until graduate school because I had undergraduate majors in math and business programming. As a math student, I took some abstract, way out, "useless," classes like logic and set theory, Boolean logic, linear algebra, abstract algebra, and number theory. At the time, I thought it helped me have fun with the Rubiks cube, and little did I know these classes were preparing me to be an OO programmer ...

When I first learned about data structures and information hiding, they were not "new concepts." They were simply non-rigorous abstract algebras: sets of values with functions. Stacks and queues are not always complete or consistent, but they are useful!

What's the point? The point is that teaching procedural programming is easy and natural because students have a solid grounding in elementary algebra. They are just applying concepts they already know. But teaching them OO is hard, because they have not studied logic and set theory, let alone Boolean and abstract algebras!

First year CS students today usually take two semesters of OO programming and two semesters of calculus. In their third semester, they take data structures and multi-variable calculus or differential equations. Finally, in their fourth semester (or later) they squeeze in a discrete math class. But by then it is too late to help them with their elementary OO programming!!

It's hard to know how much three semesters of calculus will help a CS student, but I believe an early class or two in discrete math would help them enormously. In fact, they probably need to take discrete math much earlier, before high school programming. They can certainly learn discrete math before the traditional pre-calculus, trigonometry, algebra 2, or even geometry.

Perhaps this is why high school students think our field is "boring," "hard," "useless," and "only for nerds." Perhaps this is why programming seems so hard. Perhaps if we taught discrete math before OO programming, students would start studying computing disciplines again—and we wouldn't need so much testing.

Jeff Offutt
25 January 2010