Searching for deadlocks while debugging concurrent haskell programs

ABSTRACT

This paper presents an approach to searching for deadlocks in Concurrent Haskell programs. The search is based on a redefinition of the IO monad which allows the reversal of Concurrent Haskells concurrency primitives. Hence, it is possible to implement this search by a backtracking algorithm checking all possible schedules of the system. It is integrated in the Concurrent Haskell Debugger (CHD), and automatically searches for deadlocks in the background while debugging. The tool is easy to use and the small modifications of the source program are done by a preprocessor. In the tool we use iterative deepening as search strategy which quickly detects deadlocks close to the actual system configuration and utilizes idle time during debugging at the best.

REFERENCES

• 1: Koushik Sen , Grigore Rosu , Gul Agha, Runtime safety analysis of multithreaded programs, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 2: T. Böttcher and F. Huch. A Debugger for Concurrent Haskell. In Proceedings of the 14th International Workshop on the Implementation of Functional Languages, Madrid, Spain, September 2002.
• 3: Olaf Chitil , Colin Runciman , Malcolm Wallace, Freja, Hat and Hood - A Comparative Evaluation of Three Systems for Tracing and Debugging Lazy Functional Programs, Selected Papers from the 12th International Workshop on Implementation of Functional Languages, p.176-193, September 04-07, 2000
• 4: Koen Claessen, A poor man's concurrency monad, Journal of Functional Programming, v.9 n.3, p.313-323, May 1999 [doi>10.1017/S0956796899003342]
• 5: Edmund M. Clarke, Orna Grumberg, Marius Minea, and Doron Peled. State space reduction using partial order techniques. Software Tools for Technology Transfer, 2, 1998.
• 6: James C. Corbett , Matthew B. Dwyer , John Hatcliff , Shawn Laubach , Corina S. Păsăreanu , Robby , Hongjun Zheng, Bandera: extracting finite-state models from Java source code, Proceedings of the 22nd international conference on Software engineering, p.439-448, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337234]
• 7: The Glasgow Haskell compiler. http://www.haskell.org/ghc/.
• 8: Andy Gill. Debugging Haskell by observing intermediate data structures. In Proceedings of the 2000 ACM SIGPLAN Haskell Workshop, volume 41-1 of ENTCS. Elsevier, September 2000.
• 9: K. Havelund and G. Rosu. Java PathExplorer - A runtime verification tool. In In Proceedings 6th International Symposium on Artificial Intelligence, Robotics and Automation in Space, ISAIRAS'01, Montreal, Canada, June 18-22, 2001., 2001.
• 10: Klaus Havelund and Thomas Pressburger. Model checking Java programs using Java PathFinder. International Journal on Software Tools for Technology Transfer, 2(4), April 1998.
• 11: Ralf Hinze, Deriving backtracking monad transformers, ACM SIGPLAN Notices, v.35 n.9, p.186-197, Sept. 2000
• 12: Gerard J. Holzmann, Tutorial: Proving Properties of Concurrent System with SPIN, Proceedings of the 6th International Conference on Concurrency Theory, p.453-455, August 21-24, 1995
• 13: F. Huch and V. Stolz. Runtime verification of Concurrent Haskell programs. In Proceedings of the Fourth Workshop on Runtime Verification, to appear in ENTCS. Elsevier Science Publishers, 2004.
• 14: The Haskell interpreter Hugs. http://www.haskell.org/hugs/.
• 15: Klaus Havelund, Using Runtime Analysis to Guide Model Checking of Java Programs, Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification, p.245-264, August 30-September 01, 2000
• 16: K. Läufer. Type classes with existential types. J. of Functional Programming, 6(3):485--517, May 1996.
• 17: 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 ]
• 18: Simon Peyton Jones et al. Haskell 98 report. Technical report, http://www.haskell.org, 1998.
• 19: Simon Peyton Jones , Andrew Gordon , Sigbjorn Finne, Concurrent Haskell, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.295-308, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237794]
• 20: Grigore Rosu and Koushik Sen. An instrumentation technique for online analysis of multithreaded programs. In to appear as invited Paper at Parallel and Distributed Systems: Testing and Debugging (PADTAD-2), 2004.
• 21: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

General Terms:
Languages

Keywords:
concurrent haskell, deadlock, debugging, detecting deadlocks