Abstract

Program slicing is a well-known program analysis technique that extracts the elements of a program related to a particular sub-computation. Current slicing methods, however, are specialised to program dependence graphs (PDG), and lack good composability and parallelizability. Therefore, we present a novel formalism for program slicing—monadic program slicing—which abstracts the computation of program slicing as a slice monad transformer, and applies it to semantic descriptions of the program in a modular way.

Monadic slicing algorithms allow program slices to be computed directly on abstract syntax, with no need to explicitly construct intermediate structures such as dependence graphs or to record any execution history. The monadic abstraction mechanism ensures that our monadic slicing methods have excellent flexibility, composability and parallelizability.