<story><title>A gentle introduction to symbolic execution</title><url>https://blog.monic.co/a-gentle-introduction-to-symbolic-execution/</url></story><parent_chain></parent_chain><comment><author>triska</author><text>Very nice, thank you for sharing this!&lt;p&gt;Symbolic execution is also known as &lt;i&gt;abstract interpretation&lt;/i&gt;. The program is being interpreted, with concrete values &lt;i&gt;abstracted away&lt;/i&gt;, generalized to symbolic elements that often denote several or even infinitely many &lt;i&gt;concrete&lt;/i&gt; values.&lt;p&gt;Logic programming languages like Prolog are especially amenable to abstract interpretation, since we can &lt;i&gt;absorb&lt;/i&gt; the Prolog system&amp;#x27;s built-in binding environment for variables, and simply plug in different values for the existing variables. We only have to &lt;i&gt;reify&lt;/i&gt; unification, i.e., implement it within the language with suitable semantics.&lt;p&gt;An impressive application of this idea is contained in the paper &lt;i&gt;Meta-circular Abstract Interpretation in Prolog&lt;/i&gt; by Michael Codish and Harald Søndergaard:&lt;p&gt;&lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;citeseerx.ist.psu.edu&amp;#x2F;viewdoc&amp;#x2F;summary?doi=10.1.1.137.3604&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;citeseerx.ist.psu.edu&amp;#x2F;viewdoc&amp;#x2F;summary?doi=10.1.1.137....&lt;/a&gt;&lt;p&gt;As one of the examples, the authors show how abstract interpretation over the abstract parity domain {zero, one, even, odd} can be used to derive non-trivial facts about the Ackermann function.&lt;p&gt;In particular, they deduce that &lt;i&gt;Ackermann(i,j)&lt;/i&gt; is odd and greater than 1 for all &lt;i&gt;i&lt;/i&gt; greater than 1, by taking a Prolog implementation of the Ackermann function, and interpreting it with these abstract domain elements instead of all concrete values (which would not terminate, since there are infinitely many concrete values). This is computed by fixpoint computation, determining the deductive closure of the relation.</text></comment>
<story><title>A gentle introduction to symbolic execution</title><url>https://blog.monic.co/a-gentle-introduction-to-symbolic-execution/</url></story><parent_chain></parent_chain><comment><author>joelburget</author><text>Co-author here. We&amp;#x27;re planning to turn this into a series, with additional posts on how symbolic execution works at a lower level, how to present counterexamples to users, and ideas for future programming tools built on symbolic execution.</text></comment>