Comprehending finite maps for algorithmic debugging of higher-order functional programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Comprehending finite maps for algorithmic debugging of higher-order functional programs

Full text

Pdf (235 KB)

Source

International Conference on Principles and Practice of Declarative Programming archive
Proceedings of the 10th international ACM SIGPLAN conference on Principles and practice of declarative programming table of contents

Valencia, Spain

SESSION: Debugging and checking table of contents

Pages 205-216

Year of Publication: 2008

ISBN:978-1-60558-117-0

Authors

Olaf Chitil	University of Kent, UK
Thomas Davie	University of Kent, UK

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 26, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1389449.1389475 What is a DOI?

ABSTRACT

Algorithmic debuggers for higher-order functional languages have to display functional values. Originally functional values had been represented as partial applications of function and constructor symbols, but a recent approach represents functional values as finite maps. The two representations require the computation tree that is central to algorithmic debugging to be structured rather differently. In this paper we present a unifying framework that formally defines algorithmic debugging for both representations in an implementation-independent way for both strict and non-strict functional languages. On this basis we prove the soundness of algorithmic debugging with finite maps. Our framework shows how a single implementation can support both forms of algorithmic debugging. The proof exposed that algorithmic debugging with finite maps does not handle arbitrary functional programs, but in current practice the problematic ones are excluded by the type system. Both framework and proof suggest variations of algorithmic debugging with finite maps and thus are tools for further improvement of this form of debugging

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bernd Braßel , Michael Hanus , Sebastian Fischer , Frank Huch , Germán Vidal, Lazy call-by-value evaluation, Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, October 01-03, 2007, Freiburg, Germany
	2	Rafael Caballero , Francisco Javier López-Fraguas , Mario Rodríguez-Artalejo, Theoretical Foundations for the Declarative Debugging of Lazy Functional Logic Programs, Proceedings of the 5th International Symposium on Functional and Logic Programming, p.170-184, March 07-09, 2001
	3	Olaf Chitil , Yong Luo, Structure and Properties of Traces for Functional Programs, Electronic Notes in Theoretical Computer Science (ENTCS), v.176 n.1, p.39-63, May, 2007 [doi>10.1016/j.entcs.2006.10.032]
	4	Olaf Chitil, Colin Runciman, and Malcolm Wallace. Transforming Haskell for tracing. In Proceedings of the 14th International Workshop on Implementation of Functional Languages (IFL 2002), LNCS 2670, pages 165--181, 2003.
	5	Thomas Davie and Olaf Chitil. Display of functional values for debugging. In Draft Proceedings of the 18th International Symposium on Implementation and Application of Functional Languages, IFL 2006, pages 326--337. Eötvös Loránd University, September 2006. Technical Report No 2006-SO1.
	6	Yong Luo and Olaf Chitil. Proving the correctness of algorithmic debugging for functional programs. In Trends in Functional Programming, volume 7, pages 19--34. Intellect Books, 2007.
	7	Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348--375, December 1978.
	8	Lee Naish. A declarative debugging scheme. Journal of Functional and Logic Programming, 1997(3), 1997.
	9	Henrik Nilsson, Tracing piece by piece: affordable debugging for lazy functional languages, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.36-47, September 27-29, 1999, Paris, France
	10	Henrik Nilsson , Jan Sparud, The Evaluation Dependence Tree as a Basis for Lazy FunctionalDebugging, Automated Software Engineering, v.4 n.2, p.121-150, April 1997 [doi>10.1023/A:1008681016679]
	11	Bernie Pope. Declarative debugging with Buddha. In Advanced Functional Programming, 5th International School, AFP 2004, LNCS 3622, pages 273--308. Springer Verlag, September 2005.
	12	Bernie Pope. A Declarative Debugger for Haskell. PhD thesis, The University of Melbourne, Australia, 2006.
	13	Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
	14	Malcolm Wallace, Olaf Chitil, Thorsten Brehm, and Colin Runciman. Multiple-view tracing for Haskell: a new Hat. In Proceedings of the 2001 ACM SIGPLAN Haskell Workshop, UU-CS-2001-23. Universiteit Utrecht, 2001.