Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: How to make a language downward-extensible?
Message-ID: <9363:Sep2521:41:1290@kramden.acf.nyu.edu>
Date: 25 Sep 90 21:41:12 GMT
References: <PCG.90Sep23181145@teachc.cs.aber.ac.uk> <28750:Sep2402:58:2290@kramden.acf.nyu.edu> <1990Sep24.160705.21113@newcastle.ac.uk>
Organization: IR
Lines: 49

In article <1990Sep24.160705.21113@newcastle.ac.uk> Chris.Holt@newcastle.ac.uk (Chris Holt) writes:
> In article <28750:Sep2402:58:2290@kramden.acf.nyu.edu>
>  brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> >I'd like to focus on this point. Upward extensibility through macros and
> >functions is pretty well understood. Its syntax may not be as well
> >understood, but that's not a serious problem. What would it take to make
> >a realistic language downward-extensible?
> You'd want the components of an abstract machine model to be described
> in the high-level notation, with an obvious, efficient implementation

Not necessarily. I'm trying to get at the lower levels, not at the
abstract levels. Your TimeFor*(*Machine) idea is interesting, but it
wouldn't be portable, would be painful to use if there are lots of
machines, may not have a fixed answer (times depend on context), and
doesn't have a good semantic match with compiler-choose-one-of-these.

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?

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.

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

If the compiler recognized the second construct, it would define
builtin_bitcount as 1 and use that code. If not, it would probably
choose the first construct. The bitcounts table would be defined if
builtin_bitcount was set. In any case, the code is perfectly portable.

---Dan