CHINA Questions and Answers

Will CHINA be released? If so, when?

Some parts of it, such as the groundness, boundedness, freeness, linearity, and sharing domains are complete and pretty stable now. Experiments are still under way on the widening of the structural information component. Then we will add domains for a couple of low-level properties (so called uninitialized variables and recursively dereferenced terms. I plan to rewrite the code dealing with magic transformation, and to reimplement from scratch the code for the handling of built-ins. A bunch of annotators will be the last bit needed for release.

Under which license will CHINA be released?

Why Don't You Make the Benchmark Suite Available?

First of all, I have received several programs confidentially directly from the respective authors and I am not allowed to redistribute them in any way.

The other programs were all fetched from public places on the Web during the last 3 years or so. Some of these programs are no longer available, perhaps by accident, perhaps because the respective authors decided they should disappear from the public places: I don't know.

Some programs have been superseded by new programs from the same authors. Making the old (possibly buggy, possibly incomplete) programs available from a source not under their control may be subject to criticism. Author of package X could blame me because people might (e.g., through the use of search engines) be mislead into downloading the archaic version 0.0.1-only-a-fool-would-use-me instead of version 4.13-latest-and-greatest.

Of course, with plenty of time at my disposal I could sort out all the above problems (e.g., I could get in touch with each author and ask for permission to redistribute the programs). But this is not my case: collecting the benchmark suite was and is a significant effort on my part and I can't spend more on it now.

Why are you listing linearity? Isn't linearity only useful during sharing analysis?

Why are you listing the results for both goal-independent and goal-dependent analysis? Isn't goal-dependent/goal-independent analysis The Right Thing ®?

Goal-independent analyses are unavoidable: if the analysis encounters a goal like call(G) such that the principal functor and/or the arity of G are unknown, a goal-dependent analysis is either unsound or it virtually becomes goal-independent, since it must assume a ``don't know'' call pattern for any procedure. This is one of the reasons why focusing only on goal-dependent analyses is, in our opinion, a mistake. The other reason being that the ability of analyzing libraries once and for all is desirable and, more generally, so is the separate analysis of different program modules, especially in very large projects.

On the other hand, focusing only on goal-independent analyses is the opposite mistake: goal-dependent analyses, when possible, are usually more precise than goal-independent ones. For these reasons, we insist in presenting experimental results for both.

Why you have less benchmarks listed in the tables about goal-dependent analyses?

Why you give analysis results also for programs where CHINA signals a possible incorrectness?

1. emit a ``dont' know'' description for the entire program, thus avoiding the incorrectness;
2. issue a warning and continue as if nothing happened.

This situation may arise because the program is self-modifying in an impredictable way (as far as the analyzer is concerned). This happens, for example, when the program calls goals like assert(C) where the principal functor of C is unknown. This fact could be mitigated when we can assume the program was written for a system trapping the assertion of static predicates (i.e., those not explicity declared as dynamic). However, this is often unclear and, moreover, several Prolog systems have changed their behavior in this respect when passing from one release to another: which release were the authors referring to when they wrote the program we use as a benchmark?

The other reason for possible incorrectness arises in programs using setarg/3, which is currently not supported by CHINA. We will certainly implement support for setarg/3, but this work has very low priority in our task list, especially because only a couple benchmarks are using it.

For the experimental part of our work we instruct CHINA to ignore these causes of potential incorrectness. We do this because our supply of benchmark programs is scarce, so we are not in a position to throw away any. Even if the final analysis results may be incorrect with respect to the intended concrete semantics (something that, as explained above, we often ignore), these programs allow us to exercise the domains and analysis techniques anyway.

The analysis results are always an implication like

if predicate p/n succeeds, then [...]

my_assert_p(X) :-
  [...]
  assert(p(X)),
  [...]

my_assert(C) :-
  [...]
  assert(C),
  [...]

Another possibility, which is the one we are pursuing, is to increase the ability of CHINA to discover, say, which procedures may be dynamically modified by assert/1 and relatives. The bottom line is: don't worry. We are not shipping a production tool yet. When we will do it we will make sure CHINA issues a plain ``don't know'' for those cases it cannot handle correctly.

Why the numbers differ from the ones I have seen on your paper XYZ?

• CHINA is continuously updated: domains are made smarter and/or combined in more effective ways, the handling of builtins is improved, widenings are made more selective.
• CHINA employs several widening operators (devices that are used to throttle the complexity of the analysis). These widenings are controlled by several parameters. Even though fine tuning of these parameters is not our main worry at the moment, we keep experimenting with them as our experience and benchmark suite grow. Changing these parameters may have subtle effects: widening may not occur where it previously did and occur instead at another analysis point. Sometimes this is a win, sometimes not. We do not care about the effect on individual programs, but, rather, on the overall effect on the entire testsuite. Moreover, the widenings may (and often do) interact with eachother, and this complicates the situation even further: a widening in the groundness component may cause a widening on the sharing component.
• CHINA, as any piece of software not made by the gods themselves, has bugs. Some are fixed, some new ones are introduced.

  Citing from the README of a mathematical subroutine package by R. Freund:

  For all intent and purpose, any description of what the codes are doing should be construed as being a note of what we thought the codes did on our machine on a particular Tuesday of last year. If you're really lucky, they might do the same for you someday. Then again, do you really feel *that* lucky?

The analysis times we report in order to assess the (relative) efficiency of analysis methods are subject to even more factors, in addition to the above mentioned ones:

• The machines, operating systems, and compilers we use for the development and gathering of experimental data change. We usually indicate the CPU employed along with the frequency with which it is clocked, the amount of physical memory installed and the version of the operating system. A handful of other important parameters are instead omitted: memory speed, amount of cache installed, bus frequency, BIOS and OS parameters, compiler version, optimization options used in the compilation, libraries used and so forth.
• The compiler has bugs. Sometimes we have to change the usual compilation switches in order to get around a particular bug in the optimizer. That's life.

Why the numbers you give for the XYZ analysis of aprogram differ from the ones given by A. N. Author in ``His Paper''?