Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Abstract interpretation
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, abstract interpretation is a theory of <a href="/facts/Soundness/ndpamd2A">sound approximation</a> of the <a href="/facts/Semantics_of_programming_languages/JEP1zyBv">semantics of computer programs</a>, based on <a href="/facts/Monotonic_function/MjQK0YL2">monotonic functions</a> over <a href="/facts/Ordered_set/qb4a3FAX">ordered sets</a>, especially <a href="/facts/Lattice_(order)/5ak6ufky">lattices</a>. It can be viewed as a partial <a href="/facts/Execution_(computers)/1fyfGMFm">execution</a> of a <a href="/facts/Computer_program/e38jH9N9">computer program</a> which gains information about its semantics (e.g., <a href="/facts/Control-flow_analysis/qCACUl3E">control-flow</a>, <a href="/facts/Data-flow_analysis/jz2oI6sX">data-flow</a>) without performing all the <a href="/facts/Calculation/MHq42Sjw">calculations</a>. </p><p>Its main concrete application is formal <a href="/facts/Static_code_analysis/b56nr6QM">static analysis</a>, the automatic <a href="/facts/Information_extraction/DL9nMD2X">extraction of information</a> about the possible executions of computer programs; such analyses have two main usages: </p> <ul><li>inside <a href="/facts/Compiler/WNfCDFJe">compilers</a>, to analyse programs to decide whether certain <a href="/facts/Optimization_(computer_science)/nXz6RpRM">optimizations</a> or <a href="/facts/Program_transformation/lfNb25cd">transformations</a> are applicable;</li> <li>for <a href="/facts/Debugging/QtdpPJT0">debugging</a> or even the certification of programs against classes of bugs.</li></ul> <p>Abstract interpretation was formalized by the French computer scientist working couple <a href="/facts/Patrick_Cousot/4FeJuA9V">Patrick Cousot</a> and <a href="/facts/Radhia_Cousot/c2qTHTnr">Radhia Cousot</a> in the late 1970s. </p>