OddThinking

I wrote earlier about the frustration on being taught the C programming language.

I was taught C in a very straight-forward way. My Programming Language Concepts lecturer warned us that the next assignment, which was going to be due in a few short weeks, would have to be written in C, so you might like to go and learn it.

We rushed out to buy some text-books to get us started. Without any advice or recommendations from the lecturer, the quality of the text-books I bought was pretty poor. In fact, one was so bad, I have mentioned it obliquely before.

We were then briefly introduced to the Ackermann function. This function has quite a history behind it, and is important to the some of the fundamental Theory of Computing concepts, but we weren’t told any of that. Instead, we were given some simple skeleton code that implemented it.

The Ackermann function is recursive in an interesting way. It is doubly recursive; each evaluation needs to recurse twice to work out its value. If I understand correctly, that means it cannot be computed iteratively. It also means it can degenerate into a very slow evaluation very quickly.

Having reminded us about the way that call stacks work in a run-time environment, the lecturer tried to interest us in a little trick. I can’t quite remember exactly how it worked, but the basic idea was this: When you needed to evaluate a deep nesting of the Ackerman’s function, it just so happened that your calling function had already worked out part of the result you needed. The standard response to this might be “let’s pass this partial solution in as a parameter, and save a lot of computation.” However, that wouldn’t have interested the lecturer.

Instead, he took advantage of one of the most dangerous part of the evillest corner of the C programming language – using pointer arithmetic to manipulate pointers on the stack.

He made us write code that took the current address of a variable on the stack, subtract exactly the right amount to represent the size of a stack frame, and look at the calling function’s value for that same variable, and pinch the result.

How did you know how big the stack frame was? The suggestion was to keep trying different values until it worked. In practice, someone managed to work out it was 27 bytes, and the number passed around like wildfire amongst the students.

Some of my readers might not understand enough about C to understand how disgusting this concept is. It is such a horrid hack, even writing about this now still makes me feel dirty. As an undergraduate, I knew what we were doing was unconscionable, and I couldn’t believe it was being included as part of a university course.

So, to this day, I don’t believe my dislike towards my C lecturer was unreasonable.