A killer novice bug

Recently I had ‘one of those moments’ in my CP1 lab. I am a little embarrassed to say that I spent the last few minutes of this session staring at a C function written by a student that wasn’t behaving the way it should. The students were asked to write a function that returns max value stored in a stack. Below is a reconstruction of the student’s code, slightly simplified:

int max(Stack *sptr) {
    int max = INT_MIN;
    Node popped;
    while (!isEmpty(sptr)){
         popped = pop(sptr);
         if(popped->data > max);{
             max = popped->data;
         }
    }
    return max;
}

The symptom of the bug was that the value of max returned was always the value of the last item popped from the stack.

A few labs later I had a similar situation. This time I spotted the bug right away (and embarrassingly felt slightly proud).

I am going to hope that at this point there are two types of people reading this:

  1. those that see the bug immediately
  2. those that don’t

For selfish reasons I hope that there are at least a few 2’s. At the time I had just written my own solution to this question, and had helped a dozen other students with their versions of their solutions. Needless to say that running up to the 90 minute mark I was suffering from code blindness. At least that’s my excuse for not seeing the error immediately.

So, for all of you 2’s out there, if there are any, the bug is the empty statement after the if condition. I have to say I sensed a mixture of relief and disappointment from the student when I pointed out the bug and her output was now as expected. The relief was coming from obvious places, but the disappointment seemed to stem from a sense of ‘Really? That’s it? You have got to be kidding me.’. I have to say I did feel for her.

A few days later in lecture I wrote the above code on the board (in China we are still using good-old-fashioned chalk and chalkboards), and asked the 100+ students to point out the problem. It took a good two minutes for the first student to do so.

gcc (4.9.3, no options) gives no warning for empty statements. I just checked Java SE 8 update 92, which gives an empty statement after if warning, which despite my unhappiness with most have compiler error messages, is quite nice.

I think next year I’ll spend a little time discussing the empty statement and NOPs, as early as possible, and see if that reduces the troubles experienced this year.

A great resource for non-native English speakers studying computing

I have been teaching this semester in Beijing. The language of instruction is English but most of my students are not fluent – improving English is part of the program here. Two of my modules are CS1 and Computer Organization. Early on in this semester in both courses I encouraged students to look up a few terms in the Free Online Dictionary of Computing (foldoc.org). Little did I know then that I would end up referring to FOLDOC almost every week.

Started in 1985 by Denis Howe, FOLDOC is an online, searchable, encyclopedic dictionary, currently containing nearly 15,000 definitions. It also includes cross-references and pointers to related resources elsewhere on the Internet, as well as bibliographical references to paper publications.

What I really like about FOLDOC is its simplicity, and that the definitions are pointedly context-based, specifically describing what words mean in the context of computing. I never really thought about it until recently, but in computing we use many words in ways that can be quite far from their ‘normal’ meanings. Take for instance the word load. Computing people happily abuse this word using it often and with several meanings. The Merriam Webster Dictionary has these ‘simple definitions’ for load:

1. something that is lifted and carried

2. an amount that can be carried at one time : an amount that fills something (such as a truck)

3. the weight that is carried or supported by something

None of the other ‘full definitions’ mention anything like those that FOLDOC gives:

load

1. To copy data (often program code to be run) into memory, possibly parsing it somehow in the process. E.g. “WordPerfect can’t load this RTF file – are you sure it didn’t get corrupted in the download?” Opposite of save.

2. The degree to which a computer, network, or other resource is used, sometimes expressed as a percentage of the maximum available. E.g. “What kind of CPU load does that program give?”, “The network’s constantly running at 100% load”. Sometimes used, by extension, to mean “to increase the level of use of a resource”. E.g. “Loading a spreadsheet really loads the CPU”. See also: load balancing.

3. To install a piece of software onto a system. E.g. “The computer guy is gonna come load Excel on my laptop for me”. This usage is widely considered to be incorrect.

FOLDOC is pretty comprehensive too. Writing this post I hit ‘random’ on the site, and it brought me to the definition of CACM:

Communications of the ACM

(publication) A monthly publication by the Association for Computing Machinery sent to all members. CACM is an influential publication that keeps computer science professionals up to date on developments. Each issue includes articles, case studies, practitioner oriented pieces, regular columns, commentary, departments, the ACM Forum, technical correspondence and advertisements.

http://acm.org/cacm/.

Then I googled CACM. The CACM we know and love is the 5th hit, and unless you know what ACM stands for,  the first page of results isn’t much help if you are looking to find what CACM means or stands for (in a computing context). I wish that someone gave me such a brief synopsis of CACM when I was starting out.

Other good entries for ‘normal’ English words whose computing definitions are not easily found on the net are iteration and volatile:

iteration

(programming)   Repetition of a sequence of instructions. A fundamental part of many algorithms. Iteration is characterised by a set of initial conditions, an iterative step and a termination condition.

A well known example of iteration in mathematics is Newton-Raphson iteration. Iteration in programs is expressed using a loop, e.g. in C:

	new_x = n/2;
	do
	{
	  x = new_x;
	  new_x = 0.5 * (x + n/x);
	} while (abs(new_x-x) > epsilon);

Iteration can be expressed in functional languages using recursion:

	solve x n = if abs(new_x-x) > epsilon
		    then solve new_x n
		    else new_x
		    where new_x = 0.5 * (x + n/x)
        solve n/2 n

volatile

1.   (programming)   volatile variable.

2.   (storage)   See non-volatile storage.

A few more clicks on random brought me to this, proof that those behind FOLDOC also have a great sense of humor:

elephant

Large, grey, four-legged mammal.

 

Update August 3 2016 – Merriam Webster have a learner’s dictionary which could be a valuable resource for those learning English.

 

Computer Science: More than just programming and telescopes

James H. Morris, former dean of Carnegie Mellon University’s School of Computer Science had a nice piece in Information Week 13 years ago now, that is as true as if ever was.

In it he argues strongly that CS is more than programming, and that students need a strong sense of empiricism.

 The ability to discern a real phenomenon and distinguish it from myth is vital. Our students learn to measure the performance of people using technology.

I couldn’t agree more. As the former head of a small CS department I oversaw a degree program that was particularly strong on networking – in fact our degree was known for this and popular as a result. (It was technically an IT degree). We had graduates go on to work for Oracle, IBM, and other companies based on their networking experience. I believe it still is the only CS/IT undergrad I know of that has a course on networking in each of all eight semesters. The program is also notable for third year group projects and fourth year individual projects. The fourth year project was equivalent to half of the final year workload! At the time this program had a conservative rank of 17/225 in compliance with the ACM 2008 IT curriculua. This ranking was done using the work of [1] as a guide. The biggest reason for this ranking was having this much project work – the ACM assigns 0.5 points per semester for a capstone experience (out of a possible 4). The inclusion of the fourth year module Principles in Professional Practice and Strategic Business IT also increased the mark relative to many of the other programs.

Morris goes on to state that good CS programs include the liberal arts, mathematics and experimental science. I particularly agree with the first since I enjoyed a liberal arts CS undergrad degree myself. Being at a liberal arts college really allowed me to flex my skills in a diverse environment. As a dual-major (CS and physics) I completed my final year physics project on variable stars, a project that was done almost entirely through a computer – I rarely held my eye to a telescope eyepiece. In fact the stars I was studying normally only became visible on the screen of a computer, too dim to see with the human eye, even through a powerful telescope. But it was the support and interest of my project in the community, many of whom were not in a science program, that made my experience so enjoyable.

I agree with the second point, particularly as I did a MSc in Computational Science where my mathematics skills were really put to the test. I also really put my mathematics skills to use in completing my PhD, which was largely done with a pencil and paper, drawing little squares over and over. My entire thesis including code would at the time fit on a floppy disk (not that I ever tried).

I agree with the third point most in my current research lines of high performance computing and computer science education, both areas where (sometimes slightly different forms of) empiricism is absolutely critical.

James’s final quote was:

As programmed digital devices continue to shrink in size and cost, many of us predict that the computer per se will disappear just as the electric motor disappeared into hundreds of niches in our homes and automobiles. Then we will have a science named after an artifact no one sees. But the essence of the science will still be there, and those who study it will be rewarded not just with riches but with understanding.

This brings me back to astronomy – studying many things we will never see. And of course that brings me to the famous ‘computers and telescopes’ quote (mis?) attributed to Edsger W. Dijkstra:

Computer Science is no more about computers than astronomy is about telescopes.

Dijkstra did say something similar for sure though (EWD 1305):

I don’t need to waste my time with a computer just because I am a computer scientist. [after all, doctors don’t infect themselves with the diseases the study]

[1] B. M., Neupane, B., Hansen, A., & Ofori, R. (2012). Identifying and Evaluating Information Technology Bachelor’s Degree Programs. Proceedings of the 1st Annual conference on Research in information technology (pp. 19-23). ACM.