Re: Is Java useful for writing (C/C++) compiler

Kees, sorry for hijacking your thread.


Dale wrote:
> > Perhaps so, but my guess is that most Java bounds checking cannot be
> > eliminated at all. Of course, it can't be done in general. Does anyone
> > have any stats on the proportion of bounds checks which can be
> > statically eliminated in practice?
>
> It obviously depends on how much you tell the compiler. If you provide
> range information in Ada (e.g. subtype Month is Integer range 1..12)
> then you can obviously eliminate all checks in an appropriate for
> loop.


I'm not really disputing what you say, but this is really a much more
difficult problem than you imply. "Appropriate" is the key word here -
giving the compiler the index range only solves the problem in the
most trivial cases.


A trivial counter-example:
-------------------------
Reading user input - the compiler cannot possibly know what is going
to be in the file, so Month m = read_int_from_file() must involve a
range check.


A better counter-example:
------------------------
Setting the value of a variable from the result of a function...


for x=a to b
    Month m = f(x)
end


The compiler cannot (except in the most trivial cases)
bound f(x) to the appropriate range just because it knows x lies
in the range a...b. Indeed, if f is even moderately sophisticated
it can't even tell that f will ever produce a result - you don't
even need to use a halting problem construction...


int f(x)
{
      int n=0;


      while(x!=1)
      {
          if(x is even)
                x=x/2;
          else
                x=(3*x+1)/2;


          n = n+1;
      }


      return n;
}


If the compiler can prove that f returns a value for every x, it will
have succeeded where many eminent mathematicians have failed! See
http://www.cecm.sfu.ca/organics/papers/lagarias/index.html if you
are interested.


Jonathan

Return to the comp.compilers page.
Search the comp.compilers archives again.