When I was in my undergrad, I had the pleasure of reading, and to be honest, writing, countless lines of confusing code written in a variety of languages. To be fair, I had inherited some pretty bad habits from when I taught myself BASIC as a kid, but it seems like college courses never did a really great job of pushing clean coding style. Sure, heavy emphasis was always placed on designing scalable, efficient programs, but algorithmic complexity is quite distinct from code complexity, and generally a quality coding style was almost always left as an exercise to the student.
That is until my senior year—Introduction to Artificial Intelligence. Building on a foundation in Discrete Math, where students are educated in the laws and techniques of formal logic, this course sought to remove from our minds the baggage of sequential programming (C, FORTRAN, Python, etc.) and instead see the computer as an executor of logic—returning a decision from a single logical function.
As it turns out, thinking about programs this way has profound effects on the way we write our code: specifically, it enforces a logical structure. Let's take a look at a very simple function in C that computes the length of a linked list:
int length_of_list(t_linked_list *some_list) { int length = 0; while(some_list != NULL) { some_list = some_list->next; length++; } return length; }
Efficient? Sure. Straightforward? Eh. Honestly, with an algorithm so simple, it would be hard to get lost in this code. But the point here is to think about the result we're trying to achieve and to question whether the structure of the code is representative of that goal. Is it?
We'll come back to that thought in a moment. But for now, let's look at an equivalent function in Lisp:
(defun length-of-list (some-list) (if (null some-list) 0 (+ 1 (length-of-list (rest some-list)))))
Pay attention to the way this code is structured (like a logical proof):
- Base case: Does the list have any elements?
- Inductive step: What is the length of the list if we remove an element?
While this is a pretty simple function, thinking about our code this way—as a set of "propositions," if you will—can deeply shape the way we plan and organize our code.
"But wait!" says the code-savvy reader. "That's not fair! You're comparing an iterative algorithm in one language to a recursive (and less efficient) algorithm in another!"
Guilty. The truth is that while recursion can result in some truly beautiful programs, it seldom results in the most space- or time-efficient program. And the truth is that Lisp is designed to work with lists, so I've intentionally chosen an unfair example.
But the point here is not to start a language war or, as I said earlier, discuss algorithmic complexity; the point is to demonstrate what we can learn from a (less-than-popular) language that tends to enforce good behavior.
For kicks, here is the recursive variant of the original C function:
int length_of_list(t_linked_list *some_list) { if(some_list == NULL) { return 0; } else { return (1 + length_of_list(some_list->next)); } }
Alright, so again (as I often ask myself at the end of these posts), what's the point? All I see are two versions of the same function, and the one style that I'm supposedly pushing is actually the least efficient of the two.
Well, the key here is to break out of the algorithm design box and instead think of our code like an expository essay. We've got a lot to say; we can choose a thousand different ways to say it; and we want to find the most effective way to make our point.
So when I begin writing a function, like writing an essay, I develop a plan. I ask myself, "What are we trying to achieve here? What are the possible cases? What are the possible results?" What I've found is that thinking of my programs at this higher organizational level yields a body of code that is easier to follow and perhaps more importantly, easier to update.
Give it a shot sometime; I think you'll like what you see.