Re: ANNOUNCE: New white paper available on www.sparkada.com

[Manuel Carro <boris@lml.ls.fi.upm.es>]

> Do you have any links to description of what Abstract Interpretation
> is - i.e. what is it based on?

    Basically it is a general means to analyze programs by mapping
them into an abstract value space.  As a simple example, all numbers
can be mapped to either 0, positive, or negative, and the builtin
operations be redefined accordingly, i.e., 

x * y = y * x,
(0) * _ = (0)
(+) * (+) = (+)
(+) * (-) = (-)
(-) * (-) = (-)
....

    The program is then run in the abstract domain, possibly several
times, until the information concerning the program does not change.
Then one might be able to infer that a variable is, e.g., always
positive at some point.  The good point is that having a finite
abtract domain (with some mathematical properties) ensures termination
of the analysis.  The bad point is that, of course, information is
lost both with respect to the actual program (I know that something is
positive, but that does not help me to get rid of a "X > 3" test), and
with respect to the abstract domain itself (i.e., I might end up with
a variable which has "any value").

    The abstract domain should be carefully chosen to reflect the
properties one wants to study.  The nice thing is that the analysis
algorithm can be made (in principle) generic and be used with any
abstract domain.

    There has been a lot of work in abstract interpretation in logic
and declarative languages.


-- 
          ||            Manuel Carro -- DLSIIS            ||
          ||           e-mail: mcarro@fi.upm.es           ||
          ||      http://lml.ls.fi.upm.es/~boris          ||
          ||    http://clip.dia.fi.upm.es/Software/Ciao   ||
          || Phone: +34 91 336-7455  FAX: +34 91 336-7412 ||