Dear DDJ,
Reader Marty Leisner ("Letters," April 1992) seems to have intoxicated himself on C water. I have no quarrel with his claim that "C lets the programmer do things the computer is capable of." So also, with greater or lesser efficiency respectively, do assembler and Basic, but somehow that fact slipped by unnoticed. I want a programming language that stops me from doing the things the computer is capable of -- when they are the things I don't want the computer to do.
I have seen over the years perhaps a dozen independent benchmarks comparing some aspect of C to a better language like Pascal or Modula-2, and I find it remarkable that C was beaten without exception. Several of the benchmarks were reported by persons as biased toward C as Leisner, and these poor cheerleaders were reduced to a forlorn hope that the future would bring improvements to their favorite language sufficient to even the score.
I think C is a wonderful programming language, and I hope all my competitors make full use of it.
Tom Pittman
Spreckels, California
Dear DDJ,
Regarding Jeff Duntemann's April "Structured Programming" column about OOP and collection objects, I don't think Jeff should get so depressed about the rise of inheritance (driven by the economics of code reuse) ruining the beauty and potential of purely encapsulated/abstracted object design. In fact, I see a ray of hope emanating from an idea of using collection classes as a basis for a runtime object-oriented system.
We want a system wherein all objects are compatible and polymorphism is taken to an extreme. All objects should be able to respond to a given method invocation, either by doing something, doing nothing, passing the buck, or complaining. We also want all of our data to be objects, built on other objects solely by composition. To do this we have to avoid inheritance and extend polymorphism to a composition paradigm.
Another thing to work towards is a system that would allow us to create and use object classes at runtime. And wouldn't it be great if programs were object classes and an invocation of a program would really be an instantiation of a program object? Both an object's data and methods would then also be objects. (I once worked on a research system where even the state of the processor was a data object!)
I think one key to this system could be an extension of the collection-class concept. Essentially, a collection object is a set of pointers to differing objects. It's almost a way of performing runtime composition/encapsulation. However, the collection object and therefore its methods are written in stone by the collection-class definition at compile time.
A first step might be to create a collection class with a master list of methods applicable to its intended collection of members. At run time, the collection object could use a qualification-for-membership function that would interrogate nominated objects to see if they possessed the proper data or methods. Or it could be left up to the nominee to provide function that could prove membership qualifications. One could then use the collection object as a runtime abstraction layer, providing a form of runtime encapsulation.
Our collection object might allow a nominated member object to adopt some default generic methods or data defined in the collection class. This is almost a form of runtime inheritance. Really, the nominee would not inherit the method, but would allow the collector to provide a method for it.
For those wild collections, maybe the nominated member and the collection object together would identify which methods on the collection object's master list the nominee supports on its own, which of the collector's default methods the nominee would accept, and which ones it won't deal with at all. This extends polymorphism to the runtime arena using dynamic encapsulation (or perhaps "dynamic object overloading").
If we took this a small step further, the collection object could adopt the methods of its members. If member A had a method x, and member B had a method y, a collection object C containing A and B could have methods x(A) and y(B). This would really be runtime composition of objects. How would a program use an object that did not have defined methods at compile time? If our program was itself a collection object, it could dictate that it needs an x and y method from its member objects. Or our program that used object C could be one that does something with C's methods regardless of what the methods actually are, like placing them on a menu or running them all in some order.
All this could be tracked internally to the collection object in much the same way virtual methods are tracked today, but allowing runtime modification of the virtual method tables. Windows does this same sort of runtime processing when you define farprocs and pass them to the Windows API.
Somewhere we might need to develop a communication facility so that objects could tell each other what their methods do instead of their names. Right now, there are only two things one could use to determine what a method does: its name and its actual code. Both are unsatisfactory, as names are ambiguous and comparing pieces of code is sometimes impossible (Turing) and a bad idea (ruins abstraction). We need an interobject language that is either computed perfectly with a standard or one that could handle precise translations from different corporate dialects.
Going way out into science fiction, imagine an operating-system environment wherein everything was an object. Processors would run objects. Virtual processors would be objects. Peripherals would put interface objects into the operating-system space. Active operating-system collection objects would continuously evaluate other objects for membership. If a new printer were hooked up, it would put a services-offered object into the system environment and a system printer-collection object would collect it, providing a higher-level printer interface to other objects.
What's missing is that in current static object systems, an object class is still defined at compile time, limiting the potential for extending or modifying an instance of that class during run time. It's really not that far from a system in which objects could be created dynamically. The difference between an object-class definition and an instance of an object could just slowly disappear, as an object class will be itself an object.
In any case, the column on collection objects sure got me thinking. Thanks!
Mike Matchett
North Little Rock, Arkansas
Dear DDJ,
In the article "Fletcher's Checksum," John Kodis concluded that CRC calculation is some 20 times slower than calculating Fletcher's checksum. I disagree. One does not have to shift and XOR bit by bit to calculate CRC.
As pointed out by Mark Nelson in his article, "File Verification Using CRC" (May, 1992), one can "use a table lookup that exchanges a small increase in storage space for fast calculation."
For example, the 16-bit CRC-CCITT (X^16+X^12+X^5+1) can be calculated with the Pascal code in Example 1, using two 256-byte tables. When the code in Example 1 is optimized in assembly, I believe it can be just as fast as calculating Fletcher's checksum.
var Temp, Data, CRC_Low, CRC_High: byte;
const Table_Low: array[0..255] of byte = ...;
Table_High: array[0..255] of byte = ...;
...
Temp := Data xor CRC_Low;
CRC_Low := Table_Low[Temp] xor CRC_High;
CRC_High := Table_High[Temp];
Lichen Wang
Palo Alto, California
Dear DDJ,
John Kodis's May 1992 article, "Fletcher's Checksum," was interesting. I like to fool around with CRC and PRN algorithms. My comments fall into two major areas: misinformation on CRC computational speed and weaknesses in the "standard" CRCs.
There are several interesting ways to speed up the traditional CRC calculations. The biggest speed-up comes from the most obvious design: table lookup. You can convince yourself that the effect of adding another byte of data depends only on the prior state of the most significant eight bits of the CRC and the new byte of data. Any CRC generator can be supported, but its syndrome table must be precomputed.
From my experience, any 16-bit CRC can be calculated in seven instructions per byte--not 52, as stated. Fletcher's checksum, at seven instructions per byte is still faster; just not as much as stated.
Also, while I'm not usually an 80x86 fan, note that the lowly 8088 can calculate 16-bit CRCs in only nine instructions per 16-bit word, while the best 68020 loop I could find requires 11 instructions per word. This is because the 68000 EOR instruction is "crippled," and the 86 family can operate directly on AH, while the 68000 must use shift instructions to access upper register bytes.
On these machines, 16-bit CRC calculation appears to be modestly faster than Fletcher's checksum.
Mr. Kodis notes several properties of 16-bit CRCs. Not being the main focus, a very short summary was presented. One important property not mentioned that all standard CRCs share is that any block containing an odd number of errors is detected. This is accomplished by ensuring that G(x) is divisible by (x+2).
Unfortunately, I know of no communication or storage method which tends to make mostly odd numbers of errors. Further, differential codes tend to make errors in pairs. Thus, the property of codes is, at best, useless. Note that in a channel which pairs errors, only the 15-bit component G15 = G/(x+1) is actively detecting errors. This doubles the undetected-error rate expected with a prime generator. Also, for high error rates, some standard CRC codes degenerate: The undetected-error rate can actually climb above 2-16 (!) (In this regard, CRC-ANSI is much worse than CRC-CCITT, for some reason.)
Thus, for compatibility you should select a standard CRC, preferably CRC-CCITT. Otherwise, you should select a prime generator if detection performance is key, especially at high-link error rates.
Another important property of CRCs is that an N-bit CRC always detects blocks with a single burst of errors of length<=N. If your error-generation process tends to make bursts of errors, this fact can aid in your analysis of how well the resulting system will work with CRC.
Peter Hanson
Santa Clara, California
John responds: I would like to thank Messrs. Wang and Hanson for the feedback on my article, particularly Mr. Hanson's explanation of some additional properties of the CRC. They both make a valid point: that performing CRC generation a byte or a word at a time can provide significant speed improvements over the bit-oriented approach I referred to. I still believe that Fletcher's technique will be significantly faster than the table-driven CRC approaches cited, since Fletcher's method requires fewer instructions and no memory-fetch time for the table-lookup operations.
When selecting a data-validation method, a trade-off must be made between high data integrity and high computational effort. The main point I wanted to make in my article was that Fletcher's technique provides designers with an excellent alternative to the more common checksum and CRC methods.
Dear DDJ,
In his April 1992 "C Programming" column, Al Stevens insists that programmers will not become obsolete. He's right, but he's also wrong.
He cites doctors, accountants, and car salespeople as examples of people who could never write their own programs. All, however, will create a spreadsheet or request a report from a database. These tasks would have required a programmer to write a formal program only a few years ago. More likely, they would not have been done.
I would argue that the doctor, accountant, or auto seller is programming. Not only can accountants write programs, they do. But calling it "programming" would scare off the people who do it. Programming has become so easy it isn't called programming any more.
When Fortran was developed in the late 1950s, it was intended to eliminate programmers. This can be regarded as laughable, but in fact it succeeded -- within the context of the time. Computing meant scientific or engineering number crunching. Those programs are still being written, almost always by a scientist or engineer rather than a professional programmer.
Today much computing consists of common applications such as word processing or spreadsheets. Even very sophisticated applications can be purchased, and the people who buy them work in a user department rather than in the information services department.
Our idea of programming has changed over the last 30 years. There will probably always be programmers--but they won't always do what they do now.
Jim Caughran
Willowdale, Ontario
Copyright © 1992, Dr. Dobb's Journal