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

"Jonathan Barker" <jandk@easynet.co.uk>
25 Apr 2000 02:26:49 -0400

          From comp.compilers

Related articles
[4 earlier articles]
Re: Is Java useful for writing (C/C++) compiler gram@ull.mjolner.dk (Flemming Gram Christensen) (2000-04-20)
Re: Is Java useful for writing (C/C++) compiler iank@bearcave.com (2000-04-20)
Re: Is Java useful for writing (C/C++) compiler jandk@easynet.co.uk (Jonathan Barker) (2000-04-20)
Re: Is Java useful for writing (C/C++) compiler dale@cs.rmit.edu.au (dale) (2000-04-21)
Re: Is Java useful for writing (C/C++) compiler dvdeug@x8b4e53cd.dhcp.okstate.edu (2000-04-21)
Re: Is Java useful for writing (C/C++) compiler nr@labrador.eecs.harvard.edu (2000-04-25)
Re: Is Java useful for writing (C/C++) compiler jandk@easynet.co.uk (Jonathan Barker) (2000-04-25)
Re: Is Java useful for writing (C/C++) compiler bobduff@world.std.com (Robert A Duff) (2000-04-25)
Re: Is Java useful for writing (C/C++) compiler guerby@acm.org (Laurent Guerby) (2000-04-26)
Re: Is Java useful for writing (C/C++) compiler dale@cs.rmit.edu.au (dale) (2000-04-27)
| List of all articles for this month |

From: "Jonathan Barker" <jandk@easynet.co.uk>
Newsgroups: comp.compilers
Date: 25 Apr 2000 02:26:49 -0400
Organization: [posted via Easynet Ltd]
References: 00-04-125 00-04-128 00-04-134 00-04-141 00-04-151
Keywords: OOP, design

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


Post a followup to this message

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