Scheme For Enlightenment Part Seven - A Little Fib

The Fibonacci function is another one of those defined recursively. The Fibonacci(0) is 0 and the Fibonacci(1) is 1. The Fibonacci(x) is Fibonacci(x - 1) + Fibonacci(x - 2) for integers more than 1. The Scheme implementation is straight forward.

(define (fib x)
  (if (= x 0)
      0
      (if (= x 1)
          1
          (+ (fib (- x 1)) (fib (- x 2))))))

Since there are two calls to itself, followed by addition, this is not tail recursive friendly. Also, since there are two calls to itself, and each of those calls calls itself, the number of total calls goes up faster than x. The time taken for fib(x + 1) is about 1.6 times as much as fib(x). Large x takes exponentially longer than smaller x.

Since addition, rather than multiplication is used, the answers don't become absurdly huge too quickly. The answers can be stored in a 32 bit unsigned integer for x up to 47, and a 64 bit integer can cope with the answers up to 93. With this in mind, a C version is more practical.

unsigned long long
fib(int x)
{
  if (x == 0) {
    return 0;
  }
  if (x == 1) {
    return 1;
  }
  return (fib(x - 1) + fib(x - 2));
}

This returns the same numbers for up to 93. However, fib(93) will take thousands of years to run. Yet, at this point, the Guile version and the C version can be used as a sort of benchmark. It turns out that the C version is about 100 times faster that Guile for the same x for this benchmark. Neither version requires huge amounts of memory. The call stack doesn't get very deep, nor does much go onto the stack.

The tail recursive friendly version of this function is instructive. A helper function is defined which does all the work. It is passed two additional parameters which allow it to accumulate intermediate answers. They are passed initial constant values to get it going. There's only one call to itself, and it really is the last thing the function does, so it's properly tail recursive. It produces the exact same answers as the above functions.

(define (fib-helper a b x)
    (if (= x 0)
        b
        (fib-helper (+ a b) a (- x 1))))

(define (fib x)
    (fib-helper 1 0 x))

One might expect a small constant speed improvement due to recursion. But this function isn't just a little faster, like four times faster. This function is amazingly fast. For example, (fib 93) requires an essentially unmeasurably small amount of time. That's much less than thousands of years. So what's going on?

The key is that the helper only calls itself once. For a given x, it calls itself that many times. It doesn't have exponential time, it has linear time. Well, it's not exactly linear. As x gets larger, the arithmetic takes longer because the numbers are bigger. Even so, (fib 1000) spits out all 209 digits basically without pause. This algorithm is so much better, that the original recursive version should just be scrapped. More than one Scheme tutorial demonstrates the slow recursive Fibonacci function. One made a cryptic remark that this algorithm computes Fibonacci numbers slowly. This new version was presented as tail recursive friendly, but totally failed to mention that it is a wildly different algorithm. As a point of fact, i have no idea why this function should return the same answers as the original.

This version is so much faster that a C version is pointless. Recall that (fib 93) with this version is essentially instant. The C version might be 100 times faster, but that's still instant, for a total time savings of essentially zero, best case. Actually, a best C version wouldn't do any calculation at all. If one is limited to 64 bit integers, the function can only answer 94 questions (starting with zero). The fastest version would have a small table of answers and just return one of them.

Scheme For Enlightenment Part Six - Recursive Language Comparison

C is a procedural language but it can also do recursion. And, it's call stack is deeper than Guile's. Isn't that odd? Maybe not. Guile is written in C. At least under Linux, sstk(2) is not implemented, so the stack size can't be changed. So Guile is limited in the same way that C is. C's stack is likely more efficiently represented, so more can go in the same sized area, and therefore feels larger. Here's the factorial in C, recursively.

int factorial(int x) {
    if (x == 0) {
 return 1;
    } else {
 return x * factorial(x - 1);
    }
}

It hasn't improved. It's still limited to x = 13. But try this rather spooky equivalent. Is it starting to look like Scheme?

int factorial(int x) { return (x == 0) ? 1 :  x * factorial(x - 1); }

If unsigned 64 bit integers can be used, then factorial(20) can be computed. Or C's double (floating point) type can be easily used. That gives you approximate answers (13 digits) and works up to factorial(170). It has the side effect that it knows when it overflows in the answer, reporting inf.

But let's say we really want exact large integers in C, as we get from Scheme. What do we do? The answer is that we link with an arbitrary precision number library, change the data type to the library's type, and use the library to do the multiplies. The structure would remain, and it would still be fast. After all, Guile's big numbers are written in, uhm, C. And, Guile is open source. At worst, one could use the Guile implementation of big numbers, and the two languages would end in a draw, more or less. It is much more likely is that a convenient package exists that doesn't use garbage collection, and is faster than Guile.

So, is the factorial example a good example? That is, is it fair to the languages involved? Perhaps. While short, it's complicated enough that there is more than one way to write it in each language. It brings up issues that each language enjoys. What's not to like?

Back to enlightenment. The question is, does one have to cope with recursion in order to gain any enlightenment from Scheme? Unfortunately the answer seems to be yes. Functional programming and other styles have their basis here. I'm not out to replace my procedural style with something new. I'm out to add flavor to the stew. However, it's clearly not gonna happen without some kicking and screaming.

Scheme For Enlightenment Part Five - Comparative Languages

The dreaded Scheme factorial example is written in C.

I'm coming most recently from the C world. What does it look like in C? C programmers usually think in loops, so something like this comes out.

int factorial(int x) {
    register int product = 1;

    do {
        product *= x;
    } while (--x);
    return product;
}

The variable product is the factorial being built. In each loop, it is multiplied by the current x. The variable x is decremented by one. When the loop counts down to zero, the result is returned.

It's wickedly fast. And it works for positive arguments all the way up to 13. On 32 bit machines, factorial(14) is larger than an integer. Also, we didn't bother to check for zero (or less), so it loops for a long time before getting the wrong answer in these cases.

The fact that it is six or seven lines instead of three or four does not bother me. All of the lines are reasonably easy to read. Besides, C is free format. All the lines can be jammed together, even if it looks strange.

int factorial(int x) { int f = 1; do f *= x; while (--x); return f; }

Scheme For Enlightenment Part Four - Even More Factorials

The dreaded Scheme factorial example is beaten over the head and shoulders recursively.

Another variant of the loop factorial. It uses a "let loop".

(define (factorial x)
  (let loop ((count x) (product 1))
    (if (= count 0)
 product
 (loop (- count 1) (* product count)))))

The loop starts, creating variables count and product. The variable count starts at x and counts down to 1. But also, product, starts at one. That's the second line. Once each loop, product is multiplied by count, and count is decremented. That's line five. When count is zero, product is returned in the forth line. One odd bit of the syntax is how the loop works. It looks recursive. If so, it's tail recursion and fully optimized. But it really doesn't matter if it's a iterative loop or recursion. Scheme can decide that. That is, unless it can't be nested. The do loop can certainly be nested. It's reasonable to assume that let loops can be nested also. The full inner loop would execute before the outer loop, and each would benefit from tail recursion optimization, at least in theory.

The original version of the above let loop factorial was more confusing. In it, the counting variable was named x. That's the same name as the parameter. One expects that the inner definition hides the outer definition. So how does Scheme know to assign the outer definition to the inner for the initialization? Apparently, it's designed to. But that doesn't make it consistent.

As an aside, in my examples, i've used a short cut syntax for defining all functions. In the Guile Reference, section 3.1.2.4, it is suggested that this form should not be used. The lambda syntax should be used instead.

It could be argued that the alternative define forms are rather confusing, especially for newcomers to the Scheme language, as they hide both the role of lambda and the fact that procedures are values that are stored in variables in the some way as any other kind of value.

Using the lambda syntax, the above example becomes this.

(define factorial
  (lambda (x)
    (let loop ((count x) (product 1))
      (if (= count 0)
   product
   (loop (- count 1) (* product count))))))

While the lambda keyword does indicate that a function is being created, and the define keyword indicates that this function is getting bound to a name, i don't like it much. It has yet another nested set of parenthesis, which means that there is that much more i might get wrong. There's an extra line of code (though there needn't be). The indention of the body of code is deeper, at least in the emacs pretty printer style. And finally, lambda is a Greek letter that doesn't mean anything. Go ahead, look up lambda in Google. It has been assigned all kinds of meanings. Scheme and Lisp are high in the list. I think Dennis Richie got it right. The language keywords are not the important part of the language. The important part is the bits that the programmer has created in it. So, in C, structure uses one character keywords. Here, we have the opportunity to omit a whole keyword entirely. So much the better. As a recent novice, i consider lambda an advanced topic that one can safely ignore for awhile.

Scheme For Enlightenment Part Three - More Factorials

The dreaded Scheme factorial example is continued recursively.

Scheme (and Lisp) purists continue to promote recursion as the right way to do things. Scheme, or at least Guile, Lispme, mzScheme, umb-scheme and probably all others, support free tail recursion. That is, if the very last thing your function does is call itself, then no stack penalty is paid. Unfortunately, the first example has a multiply after the last call to itself, so it must use a stack. There is a solution, but it isn't as simple.

(define (factorial x)
  (letrec ((tr-factorial
     (lambda (count product)
       (if (> count x)
    product
    (tr-factorial (+ count 1)
    (* count product))))))
    (tr-factorial 1 1)))

This tail-recursion version is much more complex. The second line defines a helper function, which calls itself. This helper function takes two parameters. The first is the current number to multiply by, and the second is the current accumulated result. In the forth line, it checks if it's done by comparing with x, the original parameter. If it is done, it returns the answer. Otherwise, it multiplies the current number by the accumulated answer, adds one to the current number and calls itself with these values. The last thing it does is calls itself, so the Scheme implementation can do the tail recursion optimization, and no additional stack is used on each call. The implementation can be said to jump to the start of the function, instead of call it. The outer definition calls the inner definition in the seventh line, starting the count at one and the accumulator at one, and the result from this call is returned. And, if one feeds this version 1000, it quickly spits out all 2,568 digits of the answer.

One is expected to use recursion for loops. And this really seems to be how one is expected to do program recursion in Scheme. Enlightenment isn't going to come easy. It works, but there are some issues with it. First, there's a weird interaction between the nested function definitions. The inner definition needs access to the outer definition's parameter. One supposes that it could just be passed as a third parameter. Then it could be a standalone function, and one would always call it with two extra parameters, set to one. In fact, Guile supports optional arguments with default values. So this can be written as a single function, at least in principal. We won't go there.

Another issue is that it isn't obvious from the source that the inner function is actually tail-recursive. The self call is smack-dab in the middle of the function definition. This has implications if one is going to use this language. As a programmer or debugger, one must know. Are there tools that could quickly tell you? Well, you can (trace) your call to find out. The tutorials talk about how you can do it with inspection. Plan to get good at it.

In timing tests, the looping structure is quicker than recursion. It isn't much faster in this example, because for large factorials, most of the computer's time is spent doing the large multiplies. For one brought up with procedural languages, the loops are easier to write, to read, and to debug. In fact, having variables to watch in a Scheme debugger provides clues as to what is going on. In a pure functional program there are no variables, so the debugger can only tell you what happens in function calls. This can be less than helpful.

Apparently, at least part of incentives to use a pure functional style is that such programs are easier to prove are correct, at least in a mathematical sense. While noting that setting variables is convenient, this quote from The History of Lisp is an example: (Fans of other programming languages are challenged to write a program to concatenate lists and prove that the operation is associative). Presumably, such a proof would involve having another program use logic to make such a statement.

But one still must cope with other language issues. For example, how does one cope with the parenthesis? A good editor can tell you if your parenthesis are lined up. Vi and Emacs can do this. Some editors, like Emacs, and other external tools can pretty print functions. The pretty printing can expose some of the structure. And, after a year of beating on the language, it gets a bit easier. But there's still the problem of where the various bits of the do loop should go. The syntax is horrible. And i've gotten comfortable with the full Unix find command, and regular expressions. I grok horrible.

Scheme For Enlightenment Part Two - More Factorials

The dreaded Scheme factorial example is continued.

Consider this factorial version, which uses a do loop instead of recursion. It has two extra variables, is a little longer, and what is going on anyway? One expects the first example to be better all around. But if one feeds this version 1000, it quickly spits out all 2,568 digits of the answer. Since it works with bigger numbers, and is as quick or quicker for smaller numbers, it's better, right?

(define (factorial x)
  (do ((count 1 (+ count 1))
       (product 1 (* count product)))
      ((> count x) product)))

The second line starts the do loop. The variable count starts at one, and is incremented by one each time through the loop. In the third line, the variable product also starts at one (same loop), and is multiplied by the variable count each time through the loop. The forth line says that the loop continues until count is more than x (the parameter). When all is finished, the value of product is returned. Let's walk an example.

(factorial 3)

Count starts at 1, product starts at one multiplied by count which is also one, and so is 1. The parameter x, which is 3 is compared to count. Since count is not larger than the parameter x, the body, which doesn't have anything in it, is executed. One is added to count, resulting in 2. This is multiplied by product, and product gets the answer, (* 1 2) is 2. count, which is 2, is compared to x, which is 3. Count is still not bigger than 3, so the loop restarts again. One is added to count, and so it now has the value 3. The variable product, 2 is multiplied by count, 3, and the result, 6 is assigned to product. Count, 3, is compared with x, 3, and it isn't bigger yet, so you'd think that the loop continues. However, that's not what it does, and we know this because the answer isn't 24, it's 6. Somehow, count gets incremented so that it is greater than 3, but product is not multiplied by 4. This mystery is solved, i think, by reading the manual. From the Guile Reference, section 5.11.4, The test expression is a termination condition. Looping stops when the test is true. It's evaluated before running the body each time, so if it's true the first time then body is not run at all. So the order of operations isn't exactly the way that i've outlined it.

So, in theory, the pure recursive version is simpler and better. In practice the loop version is faster and gives correct results for a wider range of input. What's the difference between theory and practice? In theory, they are the same...

Scheme For Enlightenment Part One - Factorials

The dreaded factorial example.

This series is starting to look like a Scheme tutorial. While most Scheme tutorials start with this example, they usually gush over the language as the ultimate for expression, hackability, etc. My opinion is that if you invest enough in a language, your tendency is to advocate that others share your pain. My approach here is to expose the weaknesses when noticed, without apology. Even my current favorite language, C (or maybe English), has plenty of warts. This is my approach to sales. I say things like, Have a free bagel. It only has 500 calories. That's probably only a quarter of the calories you consume in a day. So giving away free bagels can be difficult. On the bright side, my investigations continue with the hope that something good will come of it eventually. Feel free to share my pain.

Some Scheme syntax. (First comes an open parenthesis. Then comes a verb, which is a function or a method. Then comes space separated list of all the parameters: the nouns. The list has zero or more of these nouns. The list ends with a close parenthesis.) There is a verb that performs multiplies.

(* 5 6)

The asterisk is for multiplication. The 5 and 6 are things to multiply. The expression returns 30. Since expressions return nouns, they can be used as parameters to other functions.

(+ (* 5 6) 7)

This returns 37. The 30 returned by the multiply is added to the 7. These functions can be nested arbitrarily deep. The Scheme language does not place limits, as far as i know, though implementations certainly do.

This is functional programming. Apparently, the idea that one might assign a value to a variable is not part of functional programming. Scheme allows variables, but there are pure functional languages, like j, which don't.

The factorial of an integer is the product of all the integers from 1 to that number. The factorial of 0 is 1. The factorial of 3 is 6 (3 * 2 * 1). Now the mathematician says, we know the factorial of zero is one. We know the factorial of one is one times the factorial of zero, which we already know is one. And so on - the factorial of a number x is x times the factorial of x - 1. Consider this Scheme implementation.

(define (factorial x)
  (if (zero? x) 1
      (* x (factorial (- x 1)))))

It is purely recursive, it matches the definition of the function, doesn't use any extra variables, and is short. There are a boatload of parenthesis, each one in the correct place. Get used to it. In the second line, the function checks to see if the parameter is zero, and if it is, it returns the number one. This is the factorial that we know - the base condition. In the third line, we are in the else clause of the if, so x is not zero. It subtracts one from it's parameter, calls itself with that, and multiplies the result by it's original parameter. This function works for small positive numbers. Let's step through an example.

(factorial 3)

We're going to substitute the actual numbers. In the first call, 3 is not zero, so the return is (* 3 (factorial 2)). There is still a call to do. In that call, 2 is not zero, so the return is (* 2 (factorial 1)), substituting that in above, real result is (* 3 (* 2 (factorial 1))). The number 1 is still not zero, so (* 1 (factorial 0)) is returned. In this case, 0 is equal to zero, so the number 1 is returned. Substituting that in, we get (* 3 (* 2 (* 1 1))). The inner most multiply is computed, resulting in (* 3 (* 2 1)). The next inner most multiply is computed, resulting in (* 3 2). Then finally, this multiply is computed, resulting in 6. If you type in this example into any Scheme system, the result, 6, is printed.

While it works for small positive numbers, if you feed it a thousand, Guile reports this:

ERROR: Stack overflow

Now, the factorial of 1000 is a very large number indeed. But the stack overflow has little to do with the size of the answer. Scheme supports arbitrarily large integers. Millions of digits, for example are not only supported, but practical. Computations with million digit numbers can be performed in a reasonable amount of time on modern machines.

The reason it gets a stack overflow is that it needs a stack level for each of the thousand calls to itself. The system runs out of stack space. The Earth rests on the back of a turtle. What does that turtle stand on? Another turtle! It's turtles, all the way down.

Scheme For Enlightenment Part Zero

As a part of my ongoing road to enlightenment, i've just finished reading the Guile Reference Manual. Guile is an implementation of the computer language Scheme. Scheme is a dialect of the Lisp language. A million years ago, when i was an undergrad, i managed to get credit for just one computer course, entitled Lisp/Algol. Both are relatively ancient computer languages. Lisp dates from something like 1956, and we used Algol60, the 1960 vintage standard. The seven week course spent some five weeks on Lisp, and the remaining two on Algol. Yet, two weeks in Algol seemed like luxury compared with only five weeks with Lisp.

The idea that a language as sophisticated as Lisp was invented so early came as a complete surprise. In retrospect, early computer users were taken from the pool of mathematicians. And Lisp is a language written by mathematicians for mathematicians, much as C is a language written by systems programmers for systems programmers.

Despite eight semesters of college math, i can't really say that i think like a mathematician. You see, my math was heavy in differential equations for engineering. I actually liked Boundary Value Problems. That's because there are obvious real world applications for this stuff. As a rocket launches, even if the thrust is constant, the mass decreases as fuel is consumed, the air drag decreases with altitude, but increases with speed. So where does the rocket end up?

I know how to go from home to work. I used Yahoo Maps to find out how to get to Phil's house from work. Even if i'm home, i can get to Phil's by going to work, then using my new directions to get to his house. As an engineer, that's OK. Phil happens to live pretty close to where i work, at least compared with the total distance to where i work. Dave happens to live pretty near where i live. So, if one day, i wanted to go directly to Dave's house from work, i'd look that up on Yahoo Maps, and go. But if i then wanted to go to his house from home, i'd look that up again on Yahoo Maps, because going 80 miles out of my way to get to Dave's, only 4 or 5 miles from my house is absurd. But the mathematician considers the problem solved, and optimization is irrelevant. Worse, the mathematician assigns cryptic symbols to the way points. My house is mnemonically labeled 'A', and Phil's 'B', and Dave's 'C'. So, she says, "I know how to get from 'A' to 'B', and from 'B' to 'C', so I know how to get from 'A' to 'C'". Global warming notwithstanding.

And Lisp or Scheme is, so far, like that. There are lots of examples that are very short that are also very slow. It's also not at all clear how they could be made quicker. More on this later.

For a year i plowed through a Scheme tutorial (Teach Yourself Scheme in Fixnum Days), beat on Lispme (a Scheme implementation for the Palm Pilot), and now have Guile loaded on my Nokia hand held computer (i don't care for the term 'tablet', as it seems to limit, rather than enable wide application). Guile is also loaded on my Linux desktop where there's a real editor and keyboard. A real editor is a must.

Scheme, as a language, has some unusual features. Integers can be arbitrarily large. They can be millions of digits long. That suggests certain application classes, like discovering large prime numbers. Guile's implementation of larger numbers also seems to be fast. It also has support for non-local branching, handy for error recovery. And there's this kind of odd speculative computing which seems to be able to search arbitrary decision trees. There's also an odd programming style that seems encouraged - functional programming. There might be something of value here. Who knows?

Guile is an implementation of Scheme. But the Guile developers have added capabilities to encourage certain kinds of work. It is possible to embed a Guile interpreter in an otherwise C application, perhaps as an extension language, or configuration module. Additionally, it is reasonably easy to extend Guile by using C modules, which can be plugged into Guile.

Though Guile has been used this way, i personally don't see it. Lisp has never had the ease of reading that an Algol-like language has. Sure, it has automatic memory management. But it comes at a price. Guile is between 100 and 500 times slower than C. As near as i can tell, all the Scheme implementations are. However, there is a Scheme compiler that i have not examined.

The Guile Reference Manual talks about how one should do things certain ways for speed. In some ways, this is not a shock. A factor of 100 is roughly 10 years of computer speed improvements. So, you fire up your hot new 4 GIPS computer, to get Pentium II performance. And yet everywhere in the manual, recursion is held up as the iteration device. Guile's own do loops work faster, and never suffer stack crashes because you didn't get the tail recursion right.

My guess: mathematician's proofs use indirection. Recursion is indirection, only more so, but with little extra effort, or at least syntax. This blinds them to the fact that computers naturally deal with iteration more efficiently.

Lisp has often been the preferred tool for the development of artificial intelligence. Might the field move forward 10 years with a conversion to C?

Top Ten, 18 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Fabulously awful "standard libraries"

It turns out that libraries are harder to write than C compilers. Now, designing a good language may be difficult. But implementing an already standard language is a matter of meeting the requirements. Libraries are generally not written to standards. One writes a library by one of two processes. Either one has a task to do, and builds a library to support that task while building an application. Or, one tries to guess what functions programmers might need, and provides functions that do those things. Both approaches have problems. Your application might not need something other programmers will need. Your application might need the same things, but with peculiar semantics, making the implementation difficult to use. Or, you might not have guessed what other programmers might need. C's standard library isn't worse than most. There were a few mistakes, such as scanf(3), and index(3). There were some omissions in the original version, like strstr(3). While the bugs that were designed in are still there, for backward compatibility, solutions to those problems are available. One is told to use the fixed versions. Don't use scanf(3) - use fgets(3), then sscanf(3). Don't use index(3), use the new name strchr(3). I count the standard C library as a success because i actually use it, and don't invent a new string library. At least scanf(3) has a good excuse. The idea was to allow string parsing to work on streams. It's just that scanf(3) isn't a good way to make that happen. That said, i have written a stream based parser that needed it's own version of atof(3). That's about it.

Top Ten, 17 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Signed Characters/Unsigned bytes.

There is no byte datatype in C.

Yes, integers are signed unless you say unsigned. Yes, integer arithmetic that overflows or underflows is silent. That's largely because that's how integer arithmetic works on most machines. On an x86, char is signed. However, at least on an Arm processor, char appears to be unsigned. So it's really worse than inconsistent on one machine. Behavior can change when you port to another machine. In this case, the x86 and the Arm processors are 32 bit machines. They have the same byte order within words, which is to say that they are both little endian. The same compiler, gcc, was used in both cases.

Consider a program that reads a file a character at a time:

#include <stdio.h>

int main(int argc, char *argv[]) {
  char c;
  while ((c = getchar()) != EOF) {
    putchar(c);
  }
  return 0;
}

On an Arm, gcc reports that the variable c will never equal EOF. And, indeed, if you attempt to run the program, it reads the file, then writes a bogus character (0177) forever. It does not see the End of File signal. On an x86, this program behaves like cat(2), unless the file has a 0177 character somewhere in the stream. If it does, it stops processing at that point, even if there is more data to read. If the declaration of c is changed from char to int, the problem vanishes. Now, EOF is documented to be int. It's supposed to be a value that is never a character that could be in a file. However, conceptually, the program is reading a file one character at a time. So, it's easy to forget.

By contrast, floating point overflows can generate exceptions. That's because that's how floating point hardware works.

In the Lisp language, integers never overflow. That's because if you add one to a small integer, it simply becomes a larger integer. When it becomes too big for a 32 bit integer, it magically becomes something larger than 32 bits. You always have the right answer. And yet, it turns out that this feature isn't something that i use much in Lisp. I'd be happier if integers were all small and fast. Especially fast. The good news is that you can now get the performance of a an original Pentium using the Lisp language, if you have a modern computer to work with.

Top Ten, 16 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Octal numbers.

In C, the list 007, 008, 009, 010 is interpeted in octal, not decimal, with 010 equal to 8 decimal. Fortunately, the compiler emits an error for 008 and 009, as they have non-octal digits. This is not a warning. No object code is produced.

If you are unlucky enough not to have included an 8 or a 9 in your list of numbers, there is no warning. You just don't get the numbers you might have expected. If you want to align numbers in your code virtically, use spaces.

I confess that these days, i write most of my binary constants in hex rather than octal. These constants start with a 0x prefix, and are hard to miss. Also, octal digits encode three bits. Three is not a divisor of common word lengths used in computers today. That is, we have 8 bit bytes, 16, 32, 64 and 128 bit words. But in the old days, we used to have 12, 18, 36 and 60 bit words. Octal made more sense then, especially for 18 bit machines. The 8080 microprocessor has instructions which are easier to decode in octal than hex, because the "mov" family was 01ab, where a was the destination register and b was the source register. These machines are less common now.

But if i were God, and could redesign human civilization from scratch, it would be octal, not decimal. Mental arithmetic would be easier. Circles would be divided into 01000 (which is 512) degrees, and further subdivided with a decimal-like notation. The second would exactly be 1/0100000th of the day (1/32768th), which would make it about 2.6 times longer, and the phrase "just a second" would make a little bit more sense. By the time computers and C were designed, there'd be no reason to support decimal.

This would not be a good reason to make C support octal, as it still wouldn't match word lengths. A good reason for C to support octal is that it is a systems language.

One solution, that C didn't take, is direct support for binary. There are some macros for supporting binary, and they're ugly, but they work. Real men use binary. And, There are 10 kinds of people in the world. Those that understand binary, and those that don't.

/* Binary constant generator macro
 * By Tom Torfs - donated to the public domain
 */ 
#define HEX__(n) 0x##n##LU

#define B8__(x) ((x&0x0000000FLU) ?   1 : 0) \
       + ((x&0x000000F0LU) ?   2 : 0) \
       + ((x&0x00000F00LU) ?   4 : 0) \
       + ((x&0x0000F000LU) ?   8 : 0) \
       + ((x&0x000F0000LU) ?  16 : 0) \
       + ((x&0x00F00000LU) ?  32 : 0) \
       + ((x&0x0F000000LU) ?  64 : 0) \
       + ((x&0xF0000000LU) ? 128 : 0)

/* for up to 8-bit binary constants */
#define B8(d) ((unsigned char)B8__(HEX__(d))) 

/* for up to 16-bit binary constants, MSB first */
#define B16(dmsb,dlsb) (((unsigned short)B8(dmsb)<<8) + B8(dlsb))

/* for up to 32-bit binary constants, MSB first */
#define B32(dmsb,db2,db3,dlsb) (((unsigned long)B8(dmsb)<<24) \
 + ((unsigned long)B8(db2)<<16) \
 + ((unsigned long)B8(db3)<<8) \
 + B8(dlsb))

#include <stdio.h>

main()
{
  int i;
  unsigned int a[] = {
    B8(01010101),
    B16(10101010,01010101), 
    B32(10000000,11111111,10101010,01010101)
  };
  printf("%d\n", atoi("016"));
  for (i = 0; i < 3; i++) {
    printf("entry = %u\n", a[i]);
  }

}

Top Ten, 15 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Utterly unsafe arrays.

There are uncountably many ways to walk off of the end of an array in C. And, there are only two ends of an array. C happily allows you to walk off either end with undefined results.

The reason this is true is that C is a systems language, written by systems people for building systems. By systems, it is understood that it is meant operating systems - the bits that control everything on the machine. While operating systems have been written in other languages, assembly, Lisp, Pascal, and so on, few have been as sucessful for this task as C. C was designed as a replacement for assembly language. It adds portability and some expression. But, as much as possible, it does not subtract anything. That seems to have been the goal, anyway. In practice, it doesn't subtract much. As a system's programmer, i have to say that i like C. You'll have to pry my unsafe arrays from my cold dead fingers.

What possible use do they have? I have actually used (and it worked), code like this:

    a = b[-4];

Top Ten, 14 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Under constrained fundamental types.

I learned C working on 16 bit PDP-11's in a world of mostly 32 bit Vaxen. These days, i work mostly with 32 bit machines even though 64 bit machines are commodity items. My code tends to be portable and efficient where porting to a new architecture is largely simple recompilation. In my opinion, there are no 8 bit machines. Pointers on 8080's, z80's, 6800's, 6809's, 6502's and 1800's were all 16 bits. These are 16 bit machines.

In C, an int must be at least 16 bits, but compilers can make them larger. It's reasonably easy to write code on a 16 bit machine and port it to a larger 32 bit architecture. It takes more effort to do the reverse and get it right. I've personally seen compilers that provide 16, 32, 36 and 64 bit integers when asked for an int. This was clearly a language design feature. It allows the same code to work reasonably efficiently on machines of different sizes.

I've been asked if, every time i use an int, do i really think of it as being only "at least 16 bits"? The answer is, yes, i really think about it, but no, sometimes my expectation is that this int will be able to index my largest arrays on the local machine. Since strings are arrays of single bytes, it is expected that sizeof(int) == sizeof(char *). The language does not guarantee this, however. It should. When the Digital Equipment Corp Alpha processor team announced that their C compiler had a 16 bit short, a 32 bit int, and a 64 bit long, i was disappointed. A 32 bit int only gives you four giga entries into an array, yet the machine is capable of having arrays quite a bit larger. I had also expected that int was a redundant type that could be either short or long. I doubt that i depend on this. The discipline of thinking about something every time is a real asset to programmers. It is the only known solution to the fence post problem, for example.

Now, gcc's long long int concept is great for 32 bit machines providing 64 bit integers. Here, int is 32 bits which matches pointer sizes, and is efficient on such a machine. The long long int type is strictly for larger integers. And, i've used them for computing hashes. Very efficient. It should be noted, however, that the keyword that originally meant an integer twice as big as a pointer was orginally long. The long type on the PDP-11 was 32 bits, where an int and char * was 16 bits.

Without a doubt, C needs a new integer size keyword that allows for 64 bit integers. So if i were God and could go back in time and fix this in C's design, it might look like this:

char *	char	short	word	sword	pen	long	int
16	8	16	32	64	128	32	16
32	8	16	32	64	128	64	32
64	8	16	32	64	128	128	64

In the mean time, perhaps one can #include <sys/types.h> and get typedefs for constrained integer sizes up to 64 bits. But long is largely broken.

The migration from 16 to 32 bit machines, and now from 32 to 64 bit machines represents growing pains for C. It's a hard problem, and remains painful.

Top Ten, 13 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Cluttered compile time environment.

The actual complaint is that the standard header files declare symbols that a programmer might accidently use. The example was a programmer declaring BUFFSIZE, but then accidently using BUFSIZ, which is declared in stdio.h. The programmer might accidently use BUFSIZ if the programmer is used to typing it. I'd argue that the programmer has used a BUFSIZ like symbol because stdio introduced the idea.

I've seen worse. A long time ago, i saw a library that declared the external variable line. Naturally, it was a library where the caller might use such a common word as a variable. And, it happened.

There are conventions that C library writers use to prevent this sort of thing. For example, using a common prefix for all library functions and global variables helps. While it helps, it can't make a guarantee that this problem won't come up. C is not object oriented. There is no way for C to encapsulate symbols into a module. The potential for incursion is real. Library writers must do the best they can.

I wouldn't go so far as to state that adding object oriented scoping rules would fix C. I am not of the opinion that Java's effectively infinite sized object names is a good solution to this problem. As a matter of fact, i like C's relative terseness.

Fortran allows one to simply use a variable, and the compiler will allocate space for it. This leads to the problem that a typographical error introduces a new variable when you intended to assign to an existing variable. These problems are, indeed, hard to find. I can recall scanning symbol tables for such errors.

C requires that variables be declared before they are used. Therefore, this problem that Fortran enjoyed is gone. And, indeed, the C preprocessor requires that symbols be defined before use as well. However, no warning is given. The symbol you wanted replaced is just not replaced. Generally, this leads to a compilation or link error.

Top Ten, 12 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Uninitialized local variables.

Once again, gcc's -Wall option warns with: 'B' may be used uninitialized in this function, even for the more complicated version. The only way that this is a problem is that sometimes you have a case where a variable is always set, but possibly in different places. The compiler doesn't know that at least one path will be taken, so it thinks a variable might not be initialized, and warn you. In these cases, i usually break down and provide a redundant initialization. At least it's cheap.

Initialization of a variable is probably cheap, especially if it's infrequent. So, the optimization of leaving it off, because you know it won't be used before set probably doesn't save much memory or time. Now that compilers can warn you of this condition, they could also optimize out an explicit initialization, and do it safely. Of course, if you initialize a variable with the return value of a function, the compiler would also have to compute any side effects before it could optimize it away.

Top Ten, 11 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Undefined order of side effects.

Once again, gcc's -Wall option warns with: warning: operation on 'm' may be undefined. I've never seen this error in practice. This is probably because it isn't clear to me what the result should be. As a flaming conservative, i would cautiously break such a statement into statements that could have no possibility of doing anything other than what i want to happen. Or is that the flaming control freak that i harbor way down deep? I even add extra parenthesis if there is the slightest doubt that an expression might be evaluated out of order, even when the language makes hard promises. It's easier than looking it up.

Top Ten, 10 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Unsafe returned values.

char *f() {
   char result[80];
   sprintf(result,"anything will do");
   return(result);    /* Oops! result is allocated on the stack. */
}

The issue is that the variable results is an automatic variable. It is allocated on the stack. It is not initialized, and has whatever garbage happened to be there. That's fine. The function writes to it before it is returned. However, when the function returns, the memory on the stack is free to be used by other routines. It may get overwritten before it can be used. For example, if the the caller then calls printf() to print the result, that may use enough of the stack memory to corrupt the value, with unpredictable results. If you're lucky, you get a segmentation violation. If not, you get the wrong results from a program that appears to work.

These days, gcc reports warning: function returns address of local variable even without -Wall for this code. It has been a problem in the past. Indeed, a code review of production code showed a library had this issue with essentially every function in the library. The solution was to make the buffer static in every case.

char *f() {
   static char result[80];
...

In this case, the result buffer is allocated on the heap, and will remain untouched until that routine is called again. That routine may overwrite the value. But since the static keyword has scope implications as well as storage class implications, one knows that only that routine can do anything to it. That is, the caller knows that if it avoids calling that routine again, the value won't change. There are call graph utilities that can help the programmer be sure. Of course, the caller has a pointer to the buffer and can do whatever they want with it. But surely, if the programmer does that, they'll know they're changing it.

In Andrew Koenig's book, C Traps and Pitfalls, there is a subtle variant of this issue. On the PDP-11 (a sixteen bit machine), memory was often tight. To get a few extra bytes of heap, programmers would often declare a buffer on the stack, and call setbuf(3) to tell the standard library to use it instead of one on the heap for one of the standard streams, like stdout. Since main() has scope and life for the life of the program, it sounds as if this should always work. It never failed. However, the standard library also has onexit(3), where you can register a function to be called whenever exit(3) is called. The trouble is, these functions are called with the stack unwound to the caller of main - traditionally called crt0. This was a small chunk of machine code that set up the stack and called main(). The upshot is that functions might be called after main() has exited and it's stack variables are free, and possibly corrupt. If you have enjoyed the top ten, you'll likely enjoy Andrew's book. This second reference, has a table of contents.

Top Ten, 9 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Permissive compilation.

Three examples are presented. The first has to do with the comma operator. The gcc's -Wall option at least warns about it. The second has to do with initialization of variables. The third is an incompletely specified array. I have to say that i agree that all these problems are serious language or implementation issues.


I once modified some code that called a function via a macro:

        CALLIT(functionName,(arg1,arg2,arg3));

CALLIT did more than just call the function. I didn't want to do the extra stuff so I removed the macro invocation, yielding:

        functionName,(arg1,arg2,arg3);

Oops. This does not call the function. It's a comma expression that:

• Evaluates and then discards the address of functionName
• Evaluates the parenthesized comma expression (arg1,arg2,arg3)

There are two issues here. First, C compilers are not required to complain that no code is produced. The gcc compiler's -Wall option says warning: left-hand operand of comma expression has no effect. If there is no comma operator, then warning: statement with no effect is emitted. The second problem is the comma operator. The lesson is that you should be using -Wall.

We've already seen that commas inside a function call are not order-keeping comma operators. It turns out that people really do use semicolon statement terminators, but seldom use comma operators. They are handy in the creation of macros. The comma operator can keep multiple statements executed together, without introducing additional block structure. This turns out to be important, because there are places where a statement can go that a new block can't. With the advent of compilers that can inline functions, there is at least less need for this kind of macro.

main() {
    int var = 2;
    switch (a) {
    int var = 1;    /* This initialization typically does not happen. */
    default:
        printf("var=%d\n", var);
    }
}

This is stunning. The -Wall option complains that the first var is unused. This is true enough. It complains that the second var is used uninitialized. And sure enough, it prints stack garbage. I recall vaguely that the original C standard did not allow initialization of variables after the start of a function. That is, you could declare them, but not also give them a value. What could the compiler do? The inner var could be allocated at the same time that the outer variable is declared, at the start of the function. It could be set just before the switch is executed. Given that it allows the syntax without comment, that is what it should do. However, if it isn't going to do anything, it shouldn't accept the syntax. It's a bug, perhaps in modern gcc (4.2.1). No possible good can come from this.

Why is this a problem? C has always worked this way, right? However these days, there many C like languages - C++, Java, and so on, and many do allow this syntax. Many of us program in multiple languages, so it's much more likely that this is an issue. It is NOT a bug in these other languages.

#define DEVICE_COUNT 4 
uint8 *szDevNames[DEVICE_COUNT] = {
        "SelectSet 5000",
        "SelectSet 7000"}; /* table has two entries of junk */

While it is unfortunate that two entries in the allocated table are junk, they are no more junk than if no entries were initialized. I've personally used this language feature to initialize part of an array, that is later filled in completely. Now, when i've done it, the array is allocated in the heap as static or global memory. The unused entries don't have junk, but rather have zeroes. And, of course, my program had logic that prevented misuse. So, while C let's you shoot yourself in the foot, it also lets you do things that are difficult in other languages for some benefit - perhaps some performance reason.

Top Ten, 8 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Easily changed block scope.

    if ( ... ) 
        foo(); 
    else 
        bar();

When adding a line of code to either the if or the else clause, one needs to add braces. If you add to the else clause this way:

    if ( ... ) 
        foo(); 
    else 
 i++;
        bar();

the i++ statement is in the else, but bar() gets called no matter what. One needs to add braces.

    if ( ... ) {
        foo(); 
    } else {
 i++;
        bar();
    }

OK, so the braces aren't needed for the if clause here. But since this is the way that the language works, and since braces can be placed anywhere, and since braces do not slow down the compiled code, or add anything to the code size, why not put them everywhere? It reduces the chance of error, increases consistency, and makes editing easier.

There are C programmers who skip braces for one-line if statements:

    if (...) doit();
    if (...) doit2();

but not

    if (...) { doit(); }
    if (...) { doit2(); }

despite C's terse block structure. I'm not one of them. I don't use one line if statements.

Top Ten 7

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Indefinite order of evaluation.

Be sure to also read the supplementary dialog on the subject. I personally come down mostly on the side of the Respondents, and by extension, with Dennis Ritchie's original language design decisions. This may reflect the fact that i came to C after writing a boat load of assembly language for various processors. And yet, there is still wiggle room for yet another opinion. Here it is.

I'd have expected that the order of evaluation in function arguments would be left to right, no if's, and's, or butt's. Here's why. Function arguments are separated by commas. In C, the comma operator is the left to right evaluation order guaranteed syntax. So, in the context of function arguments, the comma operator is effectively overloaded to mean that the order is not specified. That's inconsistent at best.

A related complaint of mine with the C language is the overloading of the while keyword. In my opinion, it shouldn't have been used for both do{...}while(); and while(){...} loops. My objection has to do with reading a program in a free form language that has been badly indented. It isn't a strong objection.

While it would be nice to have a tool, ideally in the compiler, that warns that undefined behavior may take place, it's hard to imagine how such a tool could work, even slowly. Certainly, a simple example like:

 foo(i++, i++);

would be easy to catch. But trivial examples like this are also pretty easy to catch by eye. It's the more complicated examples that would be worth having a tool.

And yet, in the last half million lines of C code i've written, and in the millions of lines of C code i've examined, this yawning chasm waiting for someone to fall into continues to wait. Uninitialized variables are much more common yawning chasms. Languages that provide initial values for variables even if they aren't explicitly set have fewer bugs. C is the fusion powered chain saw without safety gourds. It will happily let you hack your own legs off. At the same time, it has historically set the gold standard for speed.

Top Ten 6

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Unpredictable struct construction.

There are several issues that lead to the exact way that C structs are laid out in memory by any C compiler. Yet, it should be noted that, as a systems language, C was explicitly designed to allow one to set a structure pointer to map to a hardware device so that bits in that device can be manipulated. The first issue is that computer designers have two choices on how to lay out the bytes of a larger integer. These are Big Endian and little endian.

#include 

int
main(int argc, char *argv[])
{
  long abcd = 0x01020304;
  char *ord = (char *)&abcd;

  printf("%0x:%0x:%0x:%0x\n",
         ord[0], ord[1], ord[2], ord[3]);
  return 0;
}

Hex notation is used to set the long integer abcd. Each two characters of hex specifies eight bits, or one byte in memory. On an x86, Arm, and other machines, this prints "4:3:2:1". The character pointer points to increasing addresses. The first byte printed is 4, which is the value of the least significant byte in the long. This is little endian, meaning that the least significant byte goes into the smallest address. On a Sparc, 68000, and other machines, this program prints "1:2:3:4". That means that these machines are big endian. So if one creates a struct with a long integer (perhaps of type int32), writes it on an Arm, and reads it on a Sparc, the Sparc will read the bytes backwards from what the Arm wrote. The Sparc would have to reverse the bytes in each word read in order to be able to get the original meaning.

Some file formats allow either big endian or little endian storage. For example, the TIFF image format allows either. The file format has an indicator for which format was used. The reader program then knows if byte reversing is needed. The reason TIFF allows either is that very often, the same computer is used to read and write the image. If the computer uses the native format, then no reversing needs to be done. This is more efficient.

There are other problems with structures. One is word alignment. Consider this structure:

struct foo {
    char first;
    long second;
}

Most 32 bit machines read 4 byte long integers faster if they are aligned on an address that is divisible evenly by 4. That's because that's how the memory is physically addressed. If the word isn't aligned, then two words of memory need to be read in order to get the desired word of memory. Some computers take this farther. If an attempt to read a word is not word aligned, the computer generates a fault, and processing is halted. That way, all working programs are faster. On such machines, the C compiler makes sure that structures are always maximally aligned. Padding bytes are added to make sure any long integers are word aligned. So, the above structure is actually represented this way:

struct foo {
    char first;
    char pad[3];
    long second;
}

The pad bytes are not directly usable by the program. They are, in fact,
not named. Now, if one doesn't really care how the bytes are ordered, one can always put the word aligned parts first:

struct foo {
    int32 second;
    char first;
}

This ensures that no padding will happen. Then if the structure is written to a file, and read from a file on another machine, one can be pretty sure that everything will at least start in the right places. One still has to deal with the Big Endian or little endian issue.

In the old days, pretty much ending with the Vax, binary floating point representations were nearly as varied as the number of different machines available. One solution to this problem was to write them out as text. For example, "-123.456e-21" specifies a very small negative number. The reading program would parse that with sscanf(3) or something, and the result would be a native format number. This parsing can be slow, but having the program work is important. However, since about when the 68000 and x86 got floating point, IEEE754 floating point has been adopted by nearly all chip makers. This format is uniform at the binary level across essentially all platforms today. There is no byte ordering problem. In fact, in 1990, a company that made databases optimized to work on CDROMs used IEEE754 floating point binary as the interoperable format. It supported a large number of computer platforms, and none of these platforms had to do anything special to make it work, unlike for long integers.

Could these issues byte you? Sure. The C language has many, many nods to optimization that turn out to be issues one must think about all the time. If you don't like to think, consider learning idioms to get specific tasks done, and simply reuse them as needed. That makes C a copy and paste language for you. However, if thinking isn't something that turns you on, perhaps programming isn't the right profession for you. Or, consider that C is a poor language choice.

Top Ten 5

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Phantom returned values. The example is:

Suppose you write this

    int foo (a) {
 if (a) {
     return 1;
 }
    } /* sometimes no value is returned  */

Generally speaking, C compilers, and C runtimes either can't or don't
tell you there is anything wrong. What actually happens depends on the
particular C compiler and what trash happened to be left lying around
wherever the caller is going to look for the returned value. Depending
on how unlucky you are, the program may even appear to work for a while.

Now, imagine the havoc that can ensue if "foo" was thought to return a pointer!

Rubbish. The bit about random stuff getting returned is true enough. But C compilers can mostly tell that sometimes a value isn't returned from a function that is declared returning a value. While gcc does not report any warning by default, the -Wall option yields the following warning:

return.c: In function 'foo':
return.c:5: warning: control reaches end of non-void function

That is, if a function is declared void, it doesn't have to return a value, and therefore it can drop off the end. In C, one can't return a value by dropping off the end. One must use a return statement; So, for example

    int bar(a) {
 return 1;
 while (1) {
  ;
 }
    }

This does not produce a warning. If you remove the return statement, it still does not produce a warning, because the compiler knows that the while statement is an infinite loop. If you remove the while statement but leave the return, the compiler again knows that the end of the function is not reached. The return statement itself causes a return, and returns a value. If you change the return statement to just return;, the compiler warns this way:

return.c: In function 'bar':
return.c:2: warning: 'return' with no value, in function returning non-void

All this to say that compilation with -Wall can catch errors that might otherwise consume your time. If you fail to use the option, shame on you. If you use the option and ignore the results, shame on you. In the early days, these warnings were available from a utility called lint, which knew the language but did not actually produce an executable. Presumably, the thought was that burdening the compiler with warning reporting was too much for each iteration. But the result was that people didn't check for errors as often.

Yet, there is a common case where you have a function that is declared to return a value, but you often know that the return value isn't used. Worse, you sometimes know that this function won't need it's arguments, but it is declared with them anyway.

#include <stdio.h>

int main(int argc, char *argv[])
{
    printf("Hello, World.\n");
}
produces these warnings
hello.c:4: warning: return type defaults to 'int'
hello.c: In function 'main':
hello.c:6: warning: control reaches end of non-void function

Now, main returns a value to the environment. That is, the parent process, often the shell, gets the return value, and may use it for loop control, error reporting or whatever. But sometimes you know that it won't be used. And the same is true for the arguments. The above program does not need to know the command line arguments. If you write main without a return value, the compiler will complain at you.

hello.c:2: warning: return type of 'main' is not 'int'

What to do? Best advice is to return a value anyway.

In the original top ten, the return statement was written this way:

 return(1);

While this works, and does what is expected, the parenthesis are not needed. The return statement is a statement, not a function, and does not need parenthesis around the argument(s). I like a style where functions have the parenthesis right next to their name(s), return statements have none, and loops such as for (...) and while (...) have a space between the keyword and the parenthesis. Visually, the reader can learn to recognize functions as functions without thinking about them too much. This convention and is never enforced by compilers, so consistency, the hobgoblin of little minds, must be enforced by self discipline. As a matter of style, i'd like to think that i'm not nearly arrogant enough to think i've got no hobgoblins. And besides, it's not for me to judge if my mind is little or not. It's a job for God, if she cares.

I am, however, qualified to judge C compilers. The bar for C compilers is gcc. If the compiler you supply isn't as good as gcc in some way, you have little excuse. The gcc compiler is available for free in source form. You can download the source, find out how it behaves, examine the source code, and you can update your compiler with that knowledge. If your product isn't as good as one available for free, eventually your very smart customers will use the superior free one. That doesn't mean, for example, that gcc won't optimize some corner case slightly better than yours once in a while. gcc is, after all, very good. The bar is quite high for C compilers.

Top Ten 4

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Mismatched header files. The example is:

Suppose foo.h contains:
        struct foo { BOOL a};

file F1.c  contains
        #define BOOL char
        #include "foo.h"

file F2.c contains 
        #define BOOL int
        #include "foo.h"

now, F1. and F2 disagree about the fundamental attributes of
structure "foo". If they talk to each other, You Lose!
 

I've seen this sort of error in released commercial software. How embarrassing. Often, a library is shipped in binary form, with header files that describe the structures and calls used. For no apparent reason, these libraries often have huge numbers of header files. And the above sort of problem can happen.

My own tendency is to have a single header file that describes everything. The single header file can't be self inconsistent, as the compiler would show such errors right away. Besides, it's just easier. It's easier for the library developer, as there is less to cross check. It's easier for the library user, as there's just one header file to include.

And yet, i've written a set of four libraries that are somewhat intertwined. A low level linked list library stands on it's own. A library with routines that handle errors needs the linked list library. A library that deals with comma separated files uses both the error library and the linked list library. A library that provides interfaces needed to write CGI programs, and also access to various databases also uses all three others. As each library has non-overlapping focus, the headers are not in any danger of providing conflicting definitions. But there are still four header files. For one thing, you might want to use just the linked list library alone. I've done this.

Top Ten #3

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is 3 Unhygienic macros. The example is:

 #define assign(a,b) a=(char)b
 assign(x,y>>8)
which becomes
 x=(char)y>>8    /* probably not what you want */

If the macro were instead written this way:

 #define CHAR_ASSIGN(a,b) (a)=(char)(b)
 CHAR_ASSIGN(x,y>>8)
it becomes
 (x)=(char)(y>>8)

which might be what was desired. One wouldn't call it assign since it has a known side effect, which is the cast to the type char. One generally uses ALL UPPER CASE for macros, since that is the convention that nearly everyone uses in C for macros.

One might wonder why the original isn't what you want. In case it isn't obvious, here it is. If you cast an integer that is bigger than a byte to a one byte char, then shift it right 8 bits, you always get zero or -1. That's because a shift right of eight bits is the size of a char. Negative numbers shift right, but copy the sign bit (which is 1), positive numbers shift in zero bits. So at the end, you get 0 or -1.

Of course, since macros are text expansions, one tries to pass the simplest expressions to them. Some macros use their arguments more than once. So if you pass such macros an argument that has side effects, you could end up with the effects taking place more than once. For example,

 #define DOUBLEIT(a) ((a)+(a))
 DOUBLEIT(it++)
becomes
 (it++)+(it++)

which increments the variable it twice, even though it looks like it happens just once. And, who knows what the return value is?

Top ten #2

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is 2 Accidental assignment/Accidental Booleans. The example is:

int main(int argc, char *argv[])
{
  int a, b, c;

  if(a=b) c;      /* a always equals b, but c will be executed if b!=0 */
  return 0;
}

to which i say that gcc -Wall says this:

two.c: In function 'main':
two.c:5: warning: suggest parentheses around assignment used as truth value
two.c:5: warning: statement with no effect

Two warnings! The first suggests something like:

  if((a=b) != 0) c;

This is what is implied by the code, though probably not desired by the coder. The second warning, statement with no effect means that the evaluation of the integer 'c' does not produce any machine code. There's no usable side effect. Nothing. But hey, this is just a contrived example, and is beside the point.

As early as Borland's Turbo C 2.0 for DOS (now available for free), we had compilers that would warn about this. And, it has saved people much time and effort. These days, gcc's -Wall option is good practice.

I happen to like the feature. I use this sort of thing all the time:

 if ((p = getenv("DOCUMENT_ROOT")) != NULL) {

which says copy the return from getenv() to the pointer p, and then check if it is NULL, which is an error to handle. The parentheses are there just as gcc suggests. Without them you get the return of getenv compared to NULL, and that boolean assigned to p. Probably not what you would want.

The main problem over the years with gcc -Wall is that your distribution's header files change out from under you, and old code that compiled clean periodically needs to be cleaned up again, even though nothing is wrong, and nothing has changed. Worse, at times, the distribution header files make it impossible to get through a compile without noise. Why is that bad? If you are expecting warnings, you start ignoring them. No news is good news.

Top ten

The top ten ways to get screwed by the C language has 18 entries. I was a bit surprised that entries weren't numbered starting at zero. Entry 15 (which you might note is more than ten) talks about using an array past it's end.

Today, let's start with number one.

#1 Non-terminated comment, "accidentally" terminated by some subsequent comment, with the code in between swallowed.

        a=b; /* this is a bug
        c=d; /* c=d will never happen */

In the eighties, i wrote a small filter (in C, of course) that can do two things. First, it can show you all the comments in a C program. Second, it can remove all the comments in a C program. This basically solves the debugging of this problem. By looking at all the comments, it becomes obvious, as in the previous example, that some code has been commented out. Since about that time, i've used '#ifdef' to effectively comment out code. In the early days of C, however, before the evil C preprocessor was invented, one would use another idiom:

        if (0) {
                c=d;
        }

The optimizer would notice that the code couldn't be reached and left it out. But then, my comment filter wouldn't show it, right?

Where is this filter now? Well, i've planned releasing it, but it just hasn't happened. I might have published it here, but my home machine is down right now. I might finish repairs tonight.

This thing with comments is, of course, by design. The most memorable time that i was bitten by it was back in the 80x24 terminal days. Someone who worked for me submitted non-working code, but had run out of time to debug it. It turned out that this person used a comment block, where each line of the block had an open and close comment bit. However, the last line of the block's closing comment had a space between the '*' and the '/', so didn't close the comment. Why wasn't it obvious? The terminal didn't wrap the line (which was 81 characters long), it wrote all characters starting with the 80th in the last column. So, the space went there, and a millisecond later (9600 BAUD) the slash went there. At that point, it looked like '*/'. That may have been when i wrote the filter. But i may already have had it. Single stepping in the debugger showed that some code was missing.

Gilgamesh

In the 80's, i read Robert Silverberg's Gilgamesh the King. This is a novelization of the epic poem. I loved it. To be honest, i hadn't been turned on very much by Silverberg's other works, though my friends like him. Pick up a copy. Amazon is showing it for 2 cents. What's with that? You must have to pay shipping, at least. It's a must-read.

Author Stephen Mitchell has written a modern verse english version of the epic tale of Gilgamesh, entitled Gilgamesh. Kind of an odd thing. I'm pretty sure that i downloaded it from Librivox, but there is no sign of it there now. Perhaps it was mistakenly published there. It is available from LearnOutLoud for about $20. The book is narrated by George Guidall, who has the perfect voice for this work, and provides a competent reading of the book and Stephen's analysis and notes. It is published on four CDs, but takes a bit over three hours.

The book itself is on two CDs. When i reached the end of the book, it was announced that the rest of it was commentary by the author. I thought i'd skip it. I thought of the main book as very short. Silverberg's novel is, well, a full length novel. That should be some eight hours of audio. Yet it was about two. Though i liked it, i thought that the commentary would completely bore me. I know the story. What is he likely to add to it?

And yet, there it was. After a few days, i stuffed the first hour onto my iPod, for consumption on the way to work. If it was terrible, i could always skip to my next podcast. So, it starts out a bit slow, picking apart the details of the story. But instead of basically repeating what was already in the story, he provides insight on why the original author used the structure that was used, why the original author picked the perspective that was used, what the inuendo means and doesn't mean.

OK, so here's where i'm coming from. If you launch an application, say Microsoft Word. But, really, any application will do. Turn on context sensitive help, and point at something, and read what it says. In MS Word, it's under the Help menu, and it reads "What's This". Point it at the icon that vaguely looks like a floppy. It will say something like Saves the active file with it's current file name, location, and file format. Nothing wrong with that, right? Except that it says nothing about why you might want to do such a thing. For Save that is perhaps, not a big deal. But for many more complicated functions, it's everything, and the online help is useless. But Stephen Mitchell's commentary on Gilgamesh covers exactly the why do we care? ideas. It's really very good. It's written by someone who has really thought about it.

Ok, so the book is short, and there's an equal length commentary. It some ways, it's a Reader's Digest or Cliff's Notes version of the epic. Not that i read either Reader's Digest or Cliff's Notes. But in other ways, the work is an attempt to create a translation that captures the spirit of the original. Not easy to do for a work in a dead language. Even if one stands in the footsteps of giants.

(If I have not seen further, it is because I stand in the footsteps of giants. - a wonderful misquote of Newton.)

Extracts from Adam’s Diary

I recently listened to Extracts from Adam’s Diary, a Mark Twain piece read on Librivox, and available for free download. The work is short. There are five chapters, the longest is about six minutes. It's a good quality recording, and read competently. Twain has sharp wit, and this somewhat masks the points he also manages to insert into this short story. If Genesis read this way, more people would understand it.

I particularly liked it, partly because it happens to be a bit of Twain i'd never read before. I've read alot of Twain, so this is becoming more rare. I have read Twain's Letters from Earth, which also has a Biblical bent. But where Twain didn't release Letters, probably because he wasn't satisfied with it, he did release Extracts. Letters starts out sharper, but soon runs out of good material, and drifts from focus. Extracts maintains focus and reaches a conclusion.

It's funny. It's a very consumable sound bite. What are you waiting for?

Reading books

Ars has an article about how reading ebooks is not like reading books. The article tries to make the point that somehow paper books are better. Or at least, something is lost going to a non-paper form. I'd say we've gotten to the point where this is moot. In particular, there's an image of a book in the article. Guess what? I read the article in a browser. I could have done this on a portable browser. I get the full artwork. It's also a special case.

I have a 2002 vintage Visor Platinum. If fits in my shirt pocket. It has a monochrome LCD with backlight. It works well in full sunlight, and pitch dark. There is a twilight where the backlight isn't strong enough which is pretty awful. This situation doesn't come up often. It runs on twin AAA batteries, which last, with modern rechargables from the grocery store, about 20 hours per charge. I can carry spares, for longer life. The device life in not limited by batteries. It has 8 MB memory (RAM/file store), enough for several books. The Bible is 1.44 MB compressed. It cost $110 when new. I bought two of them. One loads new books on it via USB or serial.

Until recently, i used it to read books, using the freeware weasel reader. It reads Palm doc books, and also it's own zlib compressed text format. It's own format has bookmarks that can be prebuilt for chapters, etc. There is a utility that will create this format from Gutenberg books, for example. It has two usable fonts - small and large bold. It allows bookmarking and annotating. It remembers where you were in a book. So you can always annotate using some other Palm application, like creating a memo.

I never annotated real books - postit notes hadn't been invented, and i never got into that habit. I don't write in books. But with electronic books, i'll spot an error, and put together a 'diff file' and send it to Gutenberg. My changes tend to make it into the archive, and i'm encouraged to continue doing this. Electronic books are interactive for me in a seriously real way.

There are only a few books i've read more than once. The Harry Potter series, and The Lord of the Rings, for example. But also, from Gutenberg, Reddy Fox. I've read this one maybe five times, out loud. It's incredibly hard to proof read, and i found errors even in the 5th reading (using a text will all my previous corrections applied). Most errors will go unnoticed, but i hope i've helped improve the quality of the work.

I read about 50 books a year. I read about 35, and listen to another 15. It takes a long time to get through 1,000 books. Having alot of books makes sense primarily for reference.

The Visor is an excellent book reader for me. The battery life is long. The device is highly portable. It's main drawbacks are that it is no longer sold - so it can't be replaced, the digitizer is fragile, and it will eventually break, it was basically incapable of showing pictures, it was limited to plain text - no bold, italics, etc.

Now, I have a a Nokia 770. It was about $150 new (sort of closeout). It is the same physical size as the Palm. It has an internal (but replacable) rechargable battery which lasts about 5 hours. That's enough for a commute. One loads data on it via USB or WiFi. The screen is high resolution color. I have 2 GB of file store, enough for a small library. FBReader is available for it, which can read plain text, html (but it is NOT a web browser, in particular, it doesn't seem to let you follow links, so books should be one huge file). FBReader can read compressed files. But with 2 GB of space, this isn't much of an issue. FBReader lets me pick colors for text and background, as well as font and size, so i can customize the experience to the lighting conditions. I read alot in the dark. HTML books, such as A Christmas Carol on Gutenberg, have a few images, and FBReader displays them extraordinarily well on the 770. FBReader also lets you flip between books easily.

The 770 also has a real web browser (Opera) which allows me to read some web based books better. It also allows me to surf the web, read web comics, etc.

The 770 also has a PDF reader. I don't like PDF for online books. I much prefer a format where i can increase (or decrease) the font size, and have the machine rewrap the text to match the screen size. The PDF format is not very flexible. PDF's which have been formatted for two columns on 8.5x11 paper work better than those with one wide chunk of text. But on the 770, i'll make it work if the content is worth it.

With several book readers available, i find that i'm reading several books at a time. Two or three in FBReader, three or four in a web browser, and typically one or two in PDF.

The 770 can play music. I don't generally listen while reading. If it turns out that playing music consumes the reader's batteries, one could use an appropriate dedicated mp3 player. My iPod lasts about 18 hours on a charge. Other mp3 players use AAA batteries, and a pocketful will last weeks of continuous use.

I don't currently commute to work hands free. When i did, it was about an hour each way. I have used a laptop during the commute, and four hours endurance was fine. I could (but didn't) recharge at work.

Sony book reader

Ars Technica has a review of the Sony PRS-505 electronic book reader. Very strange. $300. It can read books, and play audio (badly). No downloadable software. So if this isn't exactly what you need, then that's it. Move on.

The screen is grey scale. 8 greys. It has alot of dots - 800x600. The screen does not consume power when displaying - just when you turn pages. But, it takes 2 seconds to turn a page. If there's no backlight, then it's game over for me, however. What i really like to do is read in the dark. The batteries last a long time, unless you play audio. There's a memory stick - and, yes, it's Sony's proprietary format. It syncs to Windows computers only. I don't run Windows.

I've read tons of books on my 2002 vintage Palm OS Visor Platinum. It's 8 MB RAM holds tons of books. At one point, i had the entire Bible, and several other books on it. There are at least half a dozen free book readers (software) to pick from for it. One of the book readers was pretty slow turning pages. Not as slow as two seconds, just not very fast. Fortunately, other readers are quicker. The Visor Platinum has an LCD screen, which works fine in bright sunlight, and has a backlight for reading in the dark. If you aren't using the backlight, the batteries last for days. And, since the batteries are just AAA's, you can always bring spares, or stop in at 7/11.

OK, so my new Nokia 770's color screen is nicer. Even very tiny text is very sharp. However, the rechargable battery only lasts 4 or 5 hours. It handles text and PDF's and web pages. FBReader is totally awesome on the Nokia. It's better than the best of the Palm readers. For reading in the dark, i like to set the page to black, and the text to a dark red. Very nice. No screaming white light around the edges - just red text. The Nokia was $150 (on sale). The770 uses an MMC memory card. Can't get it at your local store, but it is an industry standard, available on the net.

Ipod Vs My Musix

For various reasons, i have two mp3 players. I've had both units for more than a year. In fact, both units are no longer sold as new. Even though they both have excellent sound, I really only use one of them. Try to guess which one it is after the descriptions below.

One is the original Apple iPod Shuffle. It looks like a white pack of gum with a rounded rectangle look. It has a button in a ring. The button is the play/stop button. The ring has forward a track and (hold it down) fast forward, back a track and (hold it down) rewind, volume up and volume down. There's a blinking light indicating it's on, etc. I mostly ignore it. On the back, it has a three position switch which gives you power off, sequential play and shuffle mode. There's a button which lets you check the state of the internal battery. The light shows green, amber or red.

The unit has a USB connection. You mount it on some computer, add tracks, and delete tracks. You need software which knows how to update the database on the device, otherwise, the device won't play it. I use gnupod, since other software for the iPod doesn't really work for Linux. This software works on the command line, has awful syntax, but this can be fixed with aliases and such in your shell's startup file. The key is that it works. I could say that again, but you'd get bored. You can store things on it that aren't music, for example to copy things from one place to another. Inside, there is half a GB of flash. That's enough for 12 to 20 hours of content, depending on encoding, quality, etc. While you're connected, the battery charges. I don't think about the battery unless i'm going on a long trip. It usually works. But for long trips, the limit is 18 hours of use on a full charge. I haven't tested this lately.

If you pause the unit, it will eventually turn itself off. When you turn it on, it sometimes remembers where you were in a track, and sometimes it skips to the beginning of the track. Sometimes it forgets the track, and skips to the "first track". This is the same as the first track your computer reports is on the device. Sometimes, the software records that you deleted a track, but the track isn't actually deleted. It takes up space, but isn't accessible. It can be hard to figure out which track it is, or even notice that it has happened. The tracks are always renamed with a "1_" prefix added. Sometimes, part of the file names are removed. It might have something to do with the DOS FAT 32 filesystem, and name length limitations or name mangling. Hey, blame it on Micros~1.

The other unit was on sale at Radio Shack, and is called My Musix. It is black, rounded everywhere, slightly fatter than the Shuffle, but otherwise comparable in size. On the front is a fairly large dot matrix display, which tells you what you're doing. There is a big play/stop button. There is a forward track and reverse track rocker, and if you hold them, you get fast forward/reverse. There is a volume up and volume down rocker. There is a record button. There is device lock slider switch. Lock it, and other controls will not respond. Handy for preventing error.

Turn the unit on by pressing the Play button. Turn it off by pressing (and holding) the Play button. Play by pressing Play, right? Well, that depends on what mode you're in. Mostly, i press the Record button first, which puts it into a mode menu. Modes let you change folders, each which might have different content, like a book in one, and space music in another, and podcasts in a third. Have as many as you like. Another is Play mode, where you can opt for sequential or random play. Another mode is Delete. You can delete tracks from the interface. Another mode is Repeat - including none, one track, one folder. Another mode is FM Radio. You can tune in FM stations. You can even record FM. Play the FM later, or download it to your main computer. Another mode is Record. You can record ambient audio. The sound is recorded with 8 bit samples at 8 KHz. Not very high quality. There are two levels of menu. The settings menu has a mode for setting the screen backlight. You can use a red backlight - which is good for astronomy, as it doesn't ruin your night vision.

The unit has a USB connection. You mount it on some computer, add tracks, and delete tracks. No special software. When the device turns on, it figures out what it has, and lets you play it. You can store things on it that aren't music, for example to copy things from one place to another. It ignores things it doesn't understand. Inside, there is one GB of flash. That's enough for 24 to 60 hours of content. That's enough that you can stuff content in a folder for reference. It uses a AAA battery. I use rechargeable batteries. It gets about 8 hours on a charge, but you can bring more batteries with you, so you get infinite duration with minimal preplanning. If you don't preplan, there's always 7/11. And if your rechargeable battery dies a final death, you can always pick up more at the grocery store. The design of the battery cover door suggests that you'll misplace it sometime. So far, i've been careful, and though i've lost it twice, i've also quickly found it again. It's a nuisance when you have to pull off the road to fish under the seat. Probably should have pulled over to change the battery. Think safety first.

If you pause the unit, it will eventually turn itself off. When you turn it on, it sometimes remembers where you were in a track, but always skips to the beginning of the track. Sometimes it forgets the track, folder and everything. You usually get to the first track in a random folder. Well, it's random to me. It even forgets the track when you actually turn it off gracefully, sometimes. It sometimes suffers from the Micros~1 problem. However, it doesn't, in general, rename files. Though long folder names sometimes get renamed to eight characters. This summer, i loaded Lord of the Rings audio book tracks on it, and the unit was bricked. I called customer support, and got software that let me reflash it. The new software fixed the unusual characters in the filenames can brick the unit problem, and cleaned up some display bugs too. I now have the software, and can use it any time to unbrick the unit. Since the unit behaves so much better, i'm actually glad i had to reflash it. In fact, if they had a registration system, and could, for example, send you email when new operating software was available, it would be worth signing up for spam. In any case, the customer support rocked. It's hard to remember when i've dealt with good customer support before.

Note that both units have their faults. The Apple Shuffle needed to keep the form factor, fix rewind so that it can hack into the end of the previous track, fix it so that it remembers where it is in a track when it is turned off, and remove the "off" position, letting it toggle between sequential and shuffle mode only. The form factor is fine - it didn't need to be made smaller. I'd offer it in multiple colors, not just white. Of course, then i'd buy the unpopular polka dot version at discount.

The My Musix needs to have a single menu, not two nested menus. It needs to remember where it was when turned off. If it's going to record, it needs to be high quality 16 bit sound with at least 22 KHz samples, preferably CD rate samples. Mono is OK. The battery cover design needs fixing. The display shows the current track. But if the track title doesn't fit in the display, it scrolls. It starts scrolling instantly, which doesn't give you time to consume the first few characters. Just a couple second pause before scrolling would fix this. It should be offered in multiple colors, not just black. Of course, then i'd buy the unpopular polka dot version at discount.

OK, so which one do i use? Simple interface, half storage? Or complicated interface, replaceable batteries? The answer is that i nearly never use the My Musix. But one day the battery in the Shuffle will die, and i'll switch to the My Musix, and use it for twenty years. And i'll likely pine for the good old days when life was simple.

speling

I've used a spell checker ever since they became available. For me that was about 1980, on a DecSystem 20. That's when i first got access to a spell checker that could quickly offer good guesses as to what i probably intended. These spell checkers improved my spelling skill dramatically. At first, my essays were filled with errors. But, the spell checker would catch them, and usually offer the right word. I'd study how the word was really supposed to be spelled, and after being corrected twenty or thirty times, i'd start getting it right the first time. Spell checkers improved my typing as well.

One must still proofread. That's because spell checkers will not save you form every mistake.