Revisiting A Classic

I finished another programming project and I think it’s my strongest yet, thanks to me finally getting serious about testing! I called my app HuffmanRevisited because it implements the classic Huffman coding algorithm from 1951, and also because I had previously tried to program this algorithm a few months ago.

This time round, I coded it in Java, not JavaScript. It probably required about a solid week of work. And unlike my earlier attempt, I made a finished app. It can:

  • load a text file, encode (compress) it and save the encoded version, or else
  • load a previously compressed file, decode it and save the original content back as a text file

(You can skim my code here if you like.)

A few aspects of my approach helped make coding this an enjoyable task: I tried to specify it rigorously, I wrote a lot of tests, and I tackled a clear, well-known problem.

Before Christmas, I read a book – well, no, I skimmed a book after reading the prologue (which took multiple attempts) – called How To Design Programs. It’s an MIT textbook, you can read it here. I recommend it.

My paraphrase of the book’s prologue is: “precisely specifying what a program does is the hardest part of making it.”

Of course, I had encountered this sentiment in my Object Oriented Software Engineering module in the National College of Ireland. But the MIT textbook avoids the familiar paraphernelia of design patterns, verbose conventions and profuse diagrams. Instead, the book’s prologue challenges you to specify a problem by answering two questions: how is the data represented (in terms of data types that the machine can understand, and at all steps of the program)? and what are the functions (in terms of operations on those types)?

I mean, when I write it out, it’s dull and obvious. Yet, time and again I’ve found myself skimping on this specification step. Because, yes, it is the hardest part and one’s brain tries to escape it.

Even after my epiphany from reading the MIT book, I still evaded it. I specified most but not all of my Huffman encoding app before I started, thinking that the remainder was “simple”. But the simple part is never simple and if you haven’t thought it through, the solution will be incoherent even if it seems to work.

I failed to specify all of HuffmanRevisited, but at least I knew that this failure was to blame when I witnessed complexity mushrooming in front of my eyes as I tried to solve new, small problems that kept cropping up.

BTW, I’ll mention a couple of those little problems to see if you spot a pattern that kind of pleased me:

  • accessing individual bits from an array of bytes
  • packing an unpredictable amount of bits into an array of bytes
  • turning Java’s int and char types into a byte representation (not just casting which truncates them)
  • saving a compact representation of a binary tree containing characters in its leaf nodes (the ‘Huffman tree’)

Yeah… the pattern I spotted is that I’m doing low-level stuff and pushing somewhat against the limitations of Java. This is nice because I’ve been looking for an excuse to study a more low-level language!

The other thing that went really well with this project was testing. I’d written tests in JUnit before, but to be honest I was doing it to fulfil obligations in school assignments. Just like with specifying rigorously, I knew that tests are a great idea but was lazy about writing them.

I totally changed my tune once I had the framework up and running. (I used JUnit 5, Maven and NetBeans 11, and I mention this combination because I had no joy with JUnit 4 or with Ant.) I realised I’ve always done a lot of testing, but amateurishly: printing variables to the console all the time. That works okay… until your program starts to have a decent amount of methods on the call stack (i.e., functions that call functions that call functions that call functions…) and you spend your time trying to remember in which method did your gnomic text originate. Plus, all those print statements mess up your code.

Not to sound too much like a new convert, but using a test framework was a delight after all that. It’s much more organised. (And with my let’s say “wide-ranging” mind, I need all the organisation I can get!) It’s just like what I was doing before, except you only see debug text if there’s a problem, you get to choose any range of values you like to test, you can test as small or as large a section of the program as you like (as long as you’ve made the program itself reasonably articulated), and all of this business lives in separate files. Oh, and you get a cheerful screen of green when you pass your tests!

It’s enough to warm anyone’s heart

Okay, so specification and testing are non-negotiable aspects of real-world software development, but the last aspect I want to discuss can be more of a luxury: a clearly defined problem.

Until I get a start in a programming job, I can’t be sure, but my impression is that even communicating what a problem is, never mind completing a rigorous specification, can be hard in a typical business context.

However, I did this project for self-study so I got to choose exactly what to work on.

(I was helped in this by a comp sci book called The Turing Omnibus that a mentor very kindly lent me! It has a chapter on Huffman coding. The hook of the book, I would say, is that it conversationally introduces topics but doesn’t take you through every nuance. For example, unlike the Wikipedia article on Huffman coding, it mentions neither the need to pad bytes with zeros, nor any scheme for storing a b-tree.)

I was so glad I chose such a an old chestnut of an algorithm to implement! When I was refactoring my way out of that mushrooming complexity I mentioned earlier, the clarity of my app’s intention was a godsend.

Even better was the lack of edge cases. I could be certain my program had worked when it took a text file, compressed it into a smaller file, and then decompressed that encoded version into the exact same data I started with!

That’s intrinsically neater than some other areas I’ve boldly attempted, for example digital audio or vector graphics, where you need good control of sampling and rounding.

When I do go back to such complex topics, I’ll have a crucial bit of extra experience with the exact weapons needed to contain the ambiguity. Testing and full specification.

So, I’ll sign off there. My app could easily absorb some more effort. The next thing to work on would be efficiency. Do some profiling, and just comb through it for wastages. I can also think of some cool ways to present it, but no point hyping work I may not get around to.

Anyway, I’m pleased with it already. Jaysusin’ thing works, and the code structure is fairly sensible.

Thanks for reading. Take care in these hard times!

The header image “Massachusetts Institute of Technology Parking Lot, Memorial Drive, Viewed from Graduate Housing” by MIT-Libraries is licensed under CC BY-NC 2.0. I chose it because David A. Huffman might have seen such a view as he wrote the term paper in which he invented his compression technique.

The Tiniest Example

Here’s a learning technique I just discovered.

I was working on video rendering on Android devices – reading through and mashing together libraries and example code I found. The task as it’s currently structured has 6 main classes interacting:

  • An extractor to present encoded frames of video from a file
  • A decoder to decode each frame
  • An animator to keep this happening regularly and check if it’s time to show a new frame
  • A view which is the interface element the video will be shown in, and which I’m using as a convenient repository for all the other action (this seems to be pretty standard approach)
  • A renderer which talks to OpenGL, the rendering API

I’ve been bodging everything together in one prototyping/sketchpad project. My approach was to keep it just-about-functional for my one test case (displaying three overlaid alpha-blended video elements) as I swapped in and out components and ported bits from Java to Kotlin.

I definitely learnt a lot from that, but today I tried a different tack.

Instead of accomplishing a fairly complete task messily and crudely, I took the single component I wanted to understand and placed it in a blank, fresh project. Then I tested it!

A boring screenshot

I got the class, TimeAnimator, to report all salient variables to GUI elements. Like debug text but organised so I can see the situation at a glance.

I realised I couldn’t make it do what I thought it had been doing, which was fire events at a steady framerate equal to the video framerate (of 30fps).

I shuffled through variants of the class and learnt what they do.

After a bit, I realised none of them did what I wanted. I went back to the library I was studying and finally twigged that the controlling framerate/timing information came from the decoded video data, which was merely being checked (at a frequency much faster than the framerate) by the TimeAnimator, which is not meant to run anywhere near as slow as 30fps.

So far, so trivial. But I might have kept playing with the original code for ages without actually challenging my assumptions, distracted by all its moving parts and the fact that it looked somewhat like the final product I wanted.

I will definitely be reusing this technique of isolating the smallest component that I don’t understand, and “prickin’ it and frickin’ it” as my favourite rapper Guru might say.

Hope to be back here soon to discuss what this video functionality is actually for!