Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!uunet!mcsun!ukc!newcastle.ac.uk!turing!ncmh From: Chris.Holt@newcastle.ac.uk (Chris Holt) Newsgroups: comp.lang.misc Subject: Re: How to make a language downward-extensible? Message-ID: <1990Sep26.191602.6195@newcastle.ac.uk> Date: 26 Sep 90 19:16:02 GMT References: <28750:Sep2402:58:2290@kramden.acf.nyu.edu> <1990Sep24.160705.21113@newcastle.ac.uk> <9363:Sep2521:41:1290@kramden.acf.nyu.edu> Sender: news@newcastle.ac.uk Organization: Computing Laboratory, U of Newcastle upon Tyne, UK NE1 7RU. Lines: 70 In article <9363:Sep2521:41:1290@kramden.acf.nyu.edu> 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? It seems as though you want the basic ideas of object-oriented programming, in that instructions/operations/functions should have formal specifications, libraries of objects are accessed in terms of these specifications, and when there are alternative possibilities, they can be selected without human intervention whenever possible. In this case, count-the-bits could be specified as something like output = sum(bit-to-int over int-to-array-of-bits(input)) where the basic functions of sum, over, and type conversions can be easily remembered. The trouble with actually implementing an algorithm, and hoping for the compiler to optimize, is that there are so many ways of doing it. This is (IMHO) why libraries haven't taken off yet, especially with regard to imperative languages. As soon as a library has say 10K elements in it, nobody knows how to find anything any more. Machines come in a tremendous variety of flavours, and new ones are being built every day; so unless you go to specifications, I think the compiler is going to have a *lot* of trouble matching up pieces of code to instructions. >If a compiler worked along the lines of my previous article, it would >have *some* construct that it would recognize as count-the-bits. Say it >understands { unsigned long i; for (i = j;i;i >>= 1) count += (i & 1); } >as count = count-the-bits(j). The documentation would point this out, of >course. If the compiler is to be portable, it's going to have to remember an awful lot. E.g. on a DAP, if the number is stored across an array of processors (back when they had bit processors), you'd want a different algorithm; on a Cray, you'd want a different one again. >Now the programmer wants to use this without losing portability. 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'm just claiming that there are so many alternative algorithms that you'd end up with say a hundred alternatives, and that this would happen all over the place. I'd see it as more likely that the programmer interacts with the compiler/environment by specifying what should be done at a given point; the c/e either says it doesn't know how to do that, or yes it does. If the latter, fine; trust it to optimize; if it doesn't, break it down into substeps that the c/e might recognize. There is the minor problem that this hasn't been implemented yet. :-) ----------------------------------------------------------------------------- Chris.Holt@newcastle.ac.uk Computing Lab, U of Newcastle upon Tyne, UK ----------------------------------------------------------------------------- "What two ideas are more inseparable than Beer and Virtual Reality?"