Sunday, May 21, 2006
strcpy() - An analysis
Back when we still taught C and C++, I always told my students that when they could pick up the C library function strcpy() and understand it without thinking about it, they were on their way to becoming C programmers. strcpy() is a deceptively simple function whose purpose is to copy data in character format from one memory location to another. Here's its source (the real source uses p1 and p2, rather than pDest and pSrc, but I've altered the code just a touch to make it a bit more understandable to any novice readers):
char* strcpy(char* pDest, char* pSrc) {There's a lot going on here that will be obscure to the beginning C programmer: pointers to start with, pointer arithmetic, the post-increment operator, a no-op statement, and the definition of true in C.
char* pRet = pDest;
while ( *pDest++ = *pSrc++);
return pRet;
}
pSrc points to the original copy of the string data the programmer wants to copy and pDest to the new copy. The real work happens in the while() "loop." Character by character and via the dereference (*) operator, the truth expression copies a byte from the source buffer to the destination buffer, until it finds a zero in the source buffer. (Since there is no string data type in C, it conceptualizes strings as arrays of ASCII encoded bytes, concluding with a value of zero, the "null terminator.")
This is downright strange-one expects a truth expression to be just that, a statement that evaluates to true or false, not an expression that performs actual work. A beginner would expect something more like this:
while ( *pSrc != 0) {Now the truth expression performs an action more recognizable as a truth test. "*pSrc != 0" says to look at the character stored at address pSrc and if it's not zero, evaluate to false. If we're not at the end of the buffer, i.e.: the current value that pSrc points to is not 0, copy the byte. Then increment both pointers and test again. Continue until we find that damn null terminator.
*pDest = *pSrc;
++pDest;
++pSrc;
}
The ++ increment operator is actually pretty amazing all by itself. Pointers are addresses. Incrementing them adds a value to the address equal to the size of the data type to which it has been declared to point, and one mechanism of pointer arithmetic. Pointer arithmetic works on addresses, not referenced values. It's what allows the programmer to smoothly traverse a buffer. And this is only possible, because C stipulates that arrays, which have highly tight integration with pointers in C, must be contiguous in memory. Now there is no physical reason why this has to be, and there are all kinds of reasons we might want to relax this linguistic constraint (less wasted buffer space being the first obvious candidate for some kind of managed memory system). But it allows pointer arithmetic.
There are two versions of the increment operator, pre and post. The student version uses the pre-increment operator. The real strpcy() uses the post-increment operator. Why? When the C compiler finds a pre-increment operator affixed to a term in an expression, it first increments that value and then evaluates the expression. When it finds a post-increment operator, it evaluates the expression and then increments the term. What the original strpcy() does is copy a byte and then advance the two pointers. Very cool. Since the student version uses only a single term for each expression, pre and post have the same effect, but students just plain prefer pre.
But what on earth is the truth expression evaluating? This too is very cool. In C, 0 is false. Anything that is not false is true (that much, at least, makes sense). So in C, any numeric value, and therefore any expression that evaluates to a numeric value (actually all expressions) other than 0 is true. Assignment (=) operations in C evaluate right to left, so the entire expression evaluates to the final result of the term on the left sign of the equals sign. *pDest = *pSrc, as a full expression assumes the final value of the dereferenced pDest. If the assignment was from a *pSrc that contained the null terminator, then pDest now also points to value of 0 and the entire expression is false (zero) and the while() loop terminates. If it contains any ASCII code at all, pDest would not be zero and would therefore be true (not false), allowing the loop to continue.
But what loop? A loop implies a body containing at least one executable statement. That's why the student version performs its assignments and increments in a block following the truth expression. The original appears not to have a body. But it does-it's that timid little semicolon following the truth expression. The semicolon is the C statement terminator. while() statements are not executable statements and so are not terminated in this way. (In fact, a semicolon in this position almost always is a bug.) But C also allows an empty statement, indicated by just the semicolon. This is a null operation, a leftover from early assembler programs where program code had a way of getting ahead of the hardware. Programmers would place null statements, mnemonically NOOP, for "no op" in critical spots to slow the program down. NOOP persists in C and C++ as the null statement.
The net result is the simple line "while ( *pDest++ = *pSrc++);" conflates work and truth test into a single syntagm. How cool is that?
A final word: Why return the original value of the destination buffer? Hasn't the work been performed already? Of what use could that be in a program? C library functions try to follow the UNIX idiom of allowing commands to be chained together and for the output of one command to be used as input to another (pipes and redirection operators are among the things that makes one suspect that UNIX thinks you are bothering it.) Return the original destination address allows the programmer to use the output of strcpy() in another C string function. E.g.: strcat(strcpy(p1,p2)," Add this to the copied array.").
So there you have it, compositional elegance in a simple function, an elegance that demands a lot it terms of reading competency from the programmer. An elegance so tight, it becomes poetic.
But in spite of all of the technical background information, writing such code is not a technical but a compositional competency. The programmer no more thinks of the history of C and its esoteric notions of truth when writing such a function than the poet writing in English thinks of the etymology of his words and the evolution of English syntax. He may stop for a moment to remember that the subject of an infinitive clause ought to be in objective case, but for the most part he just writes.
Next up: strcpy()'s dark side.
# posted by Jim @ 7:32 PM 
