Abstract
Existing algorithmic debuggers for Haskell require a transformation of all modules in a program, even libraries that the user does not want to debug and which may use language features not supported by the debugger. This is a pity, because a promising approach to debugging is therefore not applicable to many real-world programs. We use the cost centre stack from the Glasgow Haskell Compiler profiling environment together with runtime value observations as provided by the Haskell Object Observation Debugger (HOOD) to collect enough information for algorithmic debugging. Program annotations are in suspected modules only. With this technique algorithmic debugging is applicable to a much larger set of Haskell programs. This demonstrates that for functional languages in general a simple stack trace extension is useful to support tasks such as profiling and debugging.
Supplemental Material
Available for Download
This archive contains a virtual machine image with executable semantics, prototype debugger and examples of defect programs. The archive also contains a pdf that gives instructions how to set up and use the virtual machine.
- T. O. Allwood, S. Peyton Jones, and S. Eisenbach. Finding the needle: stack traces for GHC. In Proceedings of the symposium on Haskell, pages 129–140. ACM, 2009. Google ScholarDigital Library
- O. Chitil. Source-based trace exploration. In Proceedings of Implementation and Application of Functional Languages, LNCS 3474. Springer, 2005. Google ScholarDigital Library
- O. Chitil and T. Davie. Comprehending finite maps for algorithmic debugging of higher-order functional programs. In Proceedings of the Principles and practice of declarative programming. ACM, 2008. Google ScholarDigital Library
- O. Chitil, C. Runciman, and M. Wallace. Transforming Haskell for tracing. In Implementation of Functional Languages, LNCS 2670, pages 165–181. Springer, 2003. Google ScholarDigital Library
- K. Claessen and J. Hughes. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. In Proceedings of the International Conference on Functional Programming, volume 46, pages 268–279. ACM, 2000. Google ScholarDigital Library
- M. Faddegon and O. Chitil. Type Generic Observing. In Proceedings of Trends in Functional Programming, LNCS 8843. Springer, 2014.Google Scholar
- A. Gill. Debugging Haskell by Observing Intermediate Data Structures. Electronic Notes in Theoretical Computer Science, 41, 2000.Google Scholar
- ACM SIGPLAN Workshop on Haskell.Google Scholar
- J. Launchbury. A natural semantics for lazy evaluation. In Principles of programming languages, pages 144–154. ACM, 1993. Google ScholarDigital Library
- S. Marlow. Solving an old problem: How do we get a stack trace in a lazy functional language? Haskell Implementors Workshop, http://community.haskell.org/~simonmar/ Stack-traces.pdf, 2012.Google Scholar
- S. Marlow, J. Iborra, B. Pope, and A. Gill. A lightweight interactive debugger for Haskell. In Proceedings of the Haskell workshop, pages 13–24. ACM, 2007. Google ScholarDigital Library
- R. G. Morgan and S. A. Jarvis. Profiling Large-Scale Lazy Functional Programs. Journal of Functional Programming, 8(3):201–237, 1998. Google ScholarDigital Library
- L. Naish. A declarative debugging scheme. Journal of Functional and Logic Programming, 3, 1997.Google Scholar
- H. Nilsson. Declarative debugging for lazy functional languages. PhD thesis, Linköpings universitet, 1998.Google Scholar
- H. Nilsson and P. Fritzson. Algorithmic debugging for lazy functional languages. In Programming Language Implementation and Logic Programming, pp. 385–399. Springer LNCS 631, 1992. Google ScholarDigital Library
- H. Nilsson and J. Sparud. The evaluation dependence tree as a basis for lazy functional debugging. Automated Software Engineering, 4(2): 121–150, 1997. Google ScholarDigital Library
- C. Pareja, R. Pena, F. Rubio, and C. Segura. Adding traces to a lazy monadic evaluator. In Computer Aided Systems Theory—EUROCAST 2001, pages 627–641. Springer LNCS 2178, 2001. Google ScholarDigital Library
- B. Pope. Declarative Debugging with Buddha. In Advanced Functional Programming, pages 273–308. Springer LNCS 3622, 2005. Google ScholarDigital Library
- B. Pope. A Declarative Debugger for Haskell. PhD thesis, The University of Melbourne, Australia, 2006.Google Scholar
- P. M. Sansom and S. L. Peyton Jones. Formally based profiling for higher-order functional languages. ACM Transactions on Programming Languages and Systems (TOPLAS), 19(2):334–385, 1997. Google ScholarDigital Library
- P. Sestoft. Deriving a lazy abstract machine. Journal of Functional Programming, 7(3):231–264, 1997. Google ScholarDigital Library
- E. Y. Shapiro. Algorithmic program debugging. MIT press, 1983. Google ScholarDigital Library
- J. Silva. A comparative Study of Algorithmic Debugging Strategies. In Logic-Based Program Synthesis and Transformation, pp 143-159. Springer LNCS 4407, 2007. Google ScholarDigital Library
- J. Sparud and C. Runciman. Tracing lazy functional computations using redex trails. In Programming Languages: Implementations, Logics and Programs, pages 291–308. Springer LNCS 1292, 1997. Google ScholarDigital Library
- P. Wadler. Why No One Uses Functional Languages. ACM SIGPLAN Notices, 33(8):23–27, 1998. ISSN 0362-1340. doi: 10.1145/286385. Google ScholarDigital Library
- 286387. Functional programming column.Google Scholar
- M. Wallace, O. Chitil, T. Brehm, and C. Runciman. Multiple-view tracing for Haskell: a new Hat. In Proceedings of the 2001 ACM SIGPLAN Haskell Workshop, 2001.Google Scholar
- A. Zeller. Why Programs Fail, 2nd Edition. Morgan Kaufmann, 2009.Google Scholar
- T. Zielonka and the GHC Team. http://www.haskell.org/ghc/ survey2005-summary, 2005.Google Scholar
Index Terms
- Algorithmic debugging of real-world haskell programs: deriving dependencies from the cost centre stack
Recommendations
Algorithmic debugging of real-world haskell programs: deriving dependencies from the cost centre stack
PLDI '15: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and ImplementationExisting algorithmic debuggers for Haskell require a transformation of all modules in a program, even libraries that the user does not want to debug and which may use language features not supported by the debugger. This is a pity, because a promising ...
The Intel labs Haskell research compiler
Haskell '13The Glasgow Haskell Compiler (GHC) is a well supported optimizing compiler for the Haskell programming language, along with its own extensions to the language and libraries. Haskell's lazy semantics imposes a runtime model which is in general difficult ...
Strength Induction in a Haskell Program Verifier
Haskell employs a melange of strict and non-strict evaluation semantics, hence a Haskell verifier should be capable of checking assumptions that program variables may or may not denote well-defined values. The paper introduces a new strategy, called ...
Comments