doug@nixtdc.uucp (Doug Moen) (09/29/90)
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >Rather than this abstract discussion, let's examine a concrete example. >Someone just asked in comp.lang.c how to count the number of bits in a >32-bit integer. Most people would use a table of 256 or 65536 values and >shift appropriately. But one person pointed out that count-the-bits is a >single instruction on at least one machine. > >How, without making any preparations in the language specification >beforehand, could we let the programmer extend the language downwards to >take advantage of this instruction? > >... I envision a solution like this: > > quickpick > fast(define builtin_bitcount 0) > count = bitcounts[j & 65535] + bitcounts[(j >> 16) % 65535]; > fast(define builtin_bitcount 1) > unsigned long i; > for(i = j;i;i >>= 1) count += (i & 1); > endquickpick I think I see a general solution to this problem. 1. First, let's invent a new language feature which tests an identifier to see if it is defined. The compile-time expression Defined(id) is TRUE if 'id' is defined, otherwise FALSE. Let's also assume that the language allows arbitrary blocks of code to be conditionally compiled, based on the result of the Defined operator. 2. Second, let's assume that the compiler writer, knowing that his machine has a single instruction for counting the bits in a word, extends the language with a 'bitcount' operation. 3. A programmer wants to use 'bitcount', but wants to maintain backwards portability with older compilers that do not support bitcount. He therefore writes: if (Defined(bitcount)) count = bitcount(j); else count = bitcounts[j & 65535] + bitcounts[(j >> 16) % 65535]; This mechanism solves not just the problem of getting closer to the machine in a portable way, but the more general problem of writing code that ports to multiple environments, where there is divergence in the features provided by the standard libraries. As a Unix programmer, I have often wanted to write code that is conditionally compiled depending on whether vfork, or time_t, or strchr, is defined. It may be too late for C, but I think this would be a great feature to include in new language designs. -- Doug Moen {mnetor,alias,geac,torsqnt,lsuc}!nixtdc!doug 77 Carlton #1504, Toronto, Ontario, Canada M5B 2J7
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/02/90)
In article <1990Sep29.004009.11959@nixtdc.uucp> doug@nixtdc.UUCP (Doug Moen) writes: > 2. Second, let's assume that the compiler writer, knowing that his > machine has a single instruction for counting the bits in a word, > extends the language with a 'bitcount' operation. This throws you full speed into a mound of namespace sh---uh, problems. Portability isn't just whether your code will compile; it's whether it'll compile and do what you want. Centralizing the namespace is not a good solution. Also, you're guaranteeing that your code won't be optimized well for a machine you haven't seen. It's much better to avoid namespace issues by having the compiler not extend the language at all. It merely recognizes some portable sequence of code as doing the same thing as bitcount. The language just lets the programmer express alternative algorithms to the compiler. Certainly extending conditional compilation to identifiers is useful. ---Dan