INTERACTIVE WEB SERVICES WITH JAVA

Static Analysis

All interesting properties of the behavior of programs are (sadly) undecidable (this is Rice's Theorem):

does my program terminate (the Halting Problem)?
how much heap space does my program need?
can my program ever dereference a null pointer?
will my program correctly sort this list?
can my program only generate valid XHTML documents?
which input fields are defined in this dynamically generated XHTML document?

Instead of giving up, compiler writers resort to static analysis:

don't try to decide the question exactly
settle for an approximative answer
only use safe answers

For the Halting Problem, the answers would be:

Yes, your program definitely terminates
I don't think your program terminates, but I'm not really sure

The engineering challenge is to give useful answers as often as possible.

Static analysis is a standard technique involving:

defining an abstraction of the properties we are interested in (a lattice)
extracting a control flow graph for the program
defining dataflow equations for all program constructions
obtaining a minimal solution using fixed-point iteration

This is enough to provide reasonable accuracy for analyzing JWIG programs.

COPYRIGHT © 2002-2003 ANDERS MØLLER & MICHAEL I. SCHWARTZBACH