Lazy call-by-value evaluation

ABSTRACT

Designing debugging tools for lazy functional programming languages is a complex task which is often solved by expensive tracing of lazy computations. We present a new approach in which the information collected as a trace is reduced considerably (kilobytes instead of megabytes). The idea is to collect a kind of step information for a call-by-value interpreter, which can then efficiently reconstruct the computation for debugging/viewing tools, like declarative debugging. We show the correctness of the approach, discuss a proof-of-concept implementation with a declarative debugger as back end and present some benchmarks comparing our new approach with the Haskell debugger Hat.

REFERENCES

• 1: B. Braßel, S. Fischer, M. Hanus, F. Huch, and G. Vidal. Lazy Call-By-Value Evaluation. Technical report, CAU Kiel, 2007, esp. the Appendix.
• 2: A. Gill. Debugging Haskell by Observing Intermediate Data Structures. In Proc. of the 4th Haskell Workshop. Technical report of the University of Nottingham, 2000.
• 3: John Launchbury, A natural semantics for lazy evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.144-154, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158618]
• 4: 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
• 5: Henrik Nilsson, How to look busy while being as lazy as ever: the Implementation of a lazy functional debugger, Journal of Functional Programming, v.11 n.6, p.629-671, November 2001 [doi>10.1017/S095679680100418X]
• 6: 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]
• 7: S. L. Peyton Jones, editor. Haskell 98 Language and Libraries - The Revised Report. Cambridge University Press, 2003.
• 8: B. Pope. Declarative Debugging with Buddha. In V. Vene and T. Uustalu, editors, Advanced Functional Programming, 5th International School, AFP 2004, volume 3622 of Lecture Notes in Computer Science, pages 273--308. Springer Verlag, September 2005. ISBN 3-540-28540-7.
• 9: Bernard Pope , Lee Naish, Practical aspects of declarative debugging in Haskell 98, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.230-240, August 27-29, 2003, Uppsala, Sweden [doi>10.1145/888251.888273]
• 10: Patrick M. Sansom , Simon L. Peyton Jones, Formally based profiling for higher-order functional languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.2, p.334-385, March 1997 [doi>10.1145/244795.244802]
• 11: Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
• 12: Jan Sparud , Colin Runciman, Complete and Partial Redex Trails of Functional Computations, Selected Papers from the 9th International Workshop on Implementation of Functional Languages, p.160-177, September 10-12, 1997
• 13: Jan Sparud , Colin Runciman, Tracing Lazy Functional Computations Using Redex Trails, Proceedings of the9th International Symposium on Programming Languages: Implementations, Logics, and Programs: Including a Special Trach on Declarative Programming Languages in Education, p.291-308, September 03-05, 1997
• 14: M. Wallace, O. Chitil, T. Brehm, and C. Runciman. Multiple-View Tracing for Haskell: a New Hat. In Proc. of the 2001 ACM SIGPLAN Haskell Workshop. Universiteit Utrecht UU-CS-2001-23, 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Languages, Theory

Keywords:
debugging techniques, laziness