Non-Deterministic Symbolic Analysis using Free Monads for Test Data Generation

Abstract

Constraint logic programming (CLP) is a combination of two programming paradigms: constraint programming and logic programming. This combination allows us to write programs in a concise way and still be executed efficiently. CLP is commonly used for many domains, such as test data generation. A commonly used technique for doing this is by performing symbolic analysis on a program, and determine which values will cause which branches of the program to be executed. The problem however is that these symbolic execution algorithms normally analyze the program in a depth-first manner and do not treat non-determinism fairly. We will be investigating how we could improve this using the free monad and how we can use this in order to perform a breadth-first search, rather than depth-first. We will give a basic sample interpreter, which we will convert into a symbolically executable interpreter. The language will be described and represented as an interpreter written in Scala.