A Semantics for Tracing Declarative Multi-Paradigm Programs

by Bernd Bra├čel, Michael Hanus, Frank Huch, Germán Vidal

Proc. of the 6th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'04), ACM Press, pp. 179-190, 2004
© ACM Press

We introduce the theoretical basis for tracing lazy functional logic computations in a declarative multi-paradigm language like Curry. Tracing computations is a difficult task due to the subtleties of the underlying operational semantics, which combines laziness and non-determinism. In this work, we define an instrumented operational semantics that generates not only the computed values and bindings but also an appropriate data structure - a sort of redex trail - which can be used to trace computations at an adequate level of abstraction. In contrast to previous approaches, which rely solely on a transformation to instrument source programs, the formal definition of a tracing semantics improves the understanding of the tracing process. Furthermore, it allows us to formally prove the correctness of the computed trail. Preliminary experiments with a prototype implementation of a tracer based on the instrumented semantics demonstrates the usefulness of our approach.

PDF (150 KB) BibTeX-Entry