A gentle introduction to symbolic execution
blog.monic.co
blog.monic.co
Symbolic execution is also known as abstract interpretation. The program is being interpreted, with concrete values abstracted away, generalized to symbolic elements that often denote several or even infinitely many concrete values.
Logic programming languages like Prolog are especially amenable to abstract interpretation, since we can absorb the Prolog system's built-in binding environment for variables, and simply plug in different values for the existing variables. We only have to reify unification, i.e., implement it within the language with suitable semantics.
An impressive application of this idea is contained in the paper Meta-circular Abstract Interpretation in Prolog by Michael Codish and Harald Søndergaard:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137....
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.
In particular, they deduce that Ackermann(i,j) is odd and greater than 1 for all i 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.
These aren't the same thing! They do both use abstraction of concrete values, but abstract interpretation solves for fixpoints in a lattice of abstract values, which is a fairly different process from how symbolic execution works. The answers here go into more detail: https://cstheory.stackexchange.com/questions/19708/symbolic-...
One way of digging into abstract interpretation non-theoretically is via this recently open-sourced framework: https://code.fb.com/open-source/sparta/
For a very non-theoretical forage into that.
BTW the guy you are answering to is a prolog expert.
AI itself boils down to "Build some lattices, construct a Galois Connection between them and add some abstract transfer function on top of it" (and make sure that all the necessary correctness equations hold; this is the difficult part). For SE you then choose the appropriate lattices and construct suitable transfer functions.
BTW: SE usually also needs a fixed-point iteration to produce meaningful results. At least when considering cyclic control flow graphs (loops & recursion).
we can map each syntax tree to an interpreter
We can define a data type of expressions in our language, with addition, multiplication, etc.
data Expr = Addition Expr Expr | Multiplication Expr Expr | ...
data Interpreter = ...
interpret :: Expr -> Interpreter
interpret (Addition a b) = (+) <$> interpret a <*> interpret b
interpret (Multiplication a b) = (*) <$> interpret a <*> interpret b
Does any of this stuff work on Java, Python, or JavaScript? I want to improve the quality of real-world programs written in industry-standard languages.
This "gentle introduction" makes it seem like the first step of the process is "port your app to a homoiconic language," -- or, in other words, "you can prove the correctness of any language you want, as long as it's Haskell or Lisp."
https://news.ycombinator.com/item?id=19543995
Typically one would convert a binary executable into some other form, then analyze it to find all possible bugs. Of course one quickly slams into troubles like the halting problem, but it is still usually possible to gain useful understanding of the binary executable.
https://www.reddit.com/r/ReverseEngineering/comments/9x0v2z/...
Or we could put on a greasy old pragmatic ball cap and issue an "unbound variable in line 42" error.
A free free variable has no "possible value". If a variable has a value, it has a binding; if it has a binding, it is not a free variable.
If we suspect that the variable is not actually free, but rather its definition has not yet appeared, we can defer the processing. Perhaps capture a continuation of the symbolic execution machine, and dispatch it later.
If the expression which refers to the free variable is not actually evaluated (as our symbolic execution shows), we can squelch the warning, or change its wording.
The idea that a free variable is implicitly universally quantified works in logic, but it doesn't transfer to an ordinary programming language (i.e. not Prolog, and its ilk) very well.