Run-Time Profiling of Functional Logic Programms

Bernd Brassel, Michael Hanus, Frank Huch, Josep Silva, Germán Vidal
International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR'04), Verona (Italy).

In this work, we introduce a profiling scheme for modern functional logic languages covering notions like laziness, sharing, and non-determinism. Firstly, we instrument a natural (big-step) semantics in order to associate a symbolic cost to each basic operation (e.g., variable updates, function unfoldings, case evaluations). While this cost semantics provides a formal basis to analyze the cost of a computation, the implementation of a cost-augmented interpreter based on it would introduce a huge overhead. Therefore, we also introduce a sound transformation that instruments a program such that its execution (under the standard semantics) yields not only the corresponding results but also the associated costs. Finally, we describe a prototype implementation of a profiler based on the developments in this paper.

Available: PDF Extended version (with proofs) BibTeX-Entry

Germán Vidal