🚀 go-pugleaf

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?"