Debugging standard ML without reverse engineering

ABSTRACT

We have built a novel and efficient replay debugger for our Standard ML compiler. Debugging facilities are provided by instrumenting the user's source code; this approach, made feasible by ML's safety property, is machine-independent and back-end independent. Replay is practical because ML is normally used functionally, and our compiler uses continuation-passing style; thus most of the program's state can be checkpointed quickly and compactly using call-with-current-continuation. Together, instrumentation and replay support a simple and elegant debugger featuring full variable display, polymorphic type resolution, stack trace-back, breakpointing, and reverse execution, even though our compiler is very highly optimizing and has no run-time stack.

REFERENCES

• Appel87a: Andrew W. Appel , David B. MacQueen, A standard ML compiler, Proc. of a conference on Functional programming languages and computer architecture, p.301-324, October 1987, Portland, Oregon, United States
• Appel87b: Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X]
• Appel88: A.W. Appet, B.F. Duba, and D.B, MacQueen, "Profiling in the presence of optimization and garbage collection," Technical Report CS-TR-197-88, Princeton University Dept. of Computer Science, 1988.
• Appel89a: A.W. Appel, "Runtime tags aren't necessary," Lisp and Symbolic Computation, vol. 2, pp. 153-162, 1989.
• Appel89b: A. W. Appel , T. Jim, Continuation-passing, closure-passing style, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.293-302, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75303]
• Aral89: Z. Aral , I. Gerther , G. Schaffer, Efficient debugging primitives for multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.87-95, April 03-06, 1989, Boston, Massachusetts, United States
• Balzer69: R.M. Balzer, "EXDAMS - EXtendable Debugging and Monitoring System," AFIPS Proc. Spring Joint Computer Conference, vol. 34, pp. 567-580, AFIPS Press, Arlington, VA, 1969.
• Bruegge85: Bernd Bruegge, Adaptability and portability of symbolic debuggers, 1985
• Cargill87: T. A. Cargill , B. N. Locanthi, Cheap hardware support for software debugging and profiling, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.82-83, October 1987, Palo Alto, California, United States
• Curtis82: R. Curtis and L. Winie, "Bugnet: A debugging system for parallel programming environments," Proc. 3rd International Conf. on Distributed Computing Systems, pp. 394-399, October 1982.
• Dybvig88: R.K. Dybvig, D.P. Friedman, and C.T. Haynes, "Expansion-Passing style: A general macro mechanism," Lisp and Symbolic Computation, vol. 1, pp. 53-75, 1988.
• Friedman84: D.P. Friedman, C.T. Haynes, and E. Kohlbecker, "Programming with continuations," in Program transformation and programming environments, ed. P. Pepper, pp. 263-274, Springer, 1984.
• Hanson78: D.R. Hanson, "Event associations in SNOBOL4 for program debugging," Software Practice and Experience, vol. 8, pp. 115-129, 1978.
• Hennessy82: John Hennessy, Symbolic Debugging of Optimized Code, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.323-344, July 1982 [doi>10.1145/357172.357173]
• Johnson88: G. F. Johnson , D. Duggan, Stores and partial continuations as first-class objects in a language and its environment, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.158-168, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73574]
• LeBlanc87: T. J. LeBlanc , J. M. Mellor-Crummey, Debugging parallel programs with instant replay, IEEE Transactions on Computers, v.36 n.4, p.471-482, April 1987 [doi>10.1109/TC.1987.1676929]
• McDowell89: Charles E. McDowell , David P. Helmbold, Debugging concurrent programs, ACM Computing Surveys (CSUR), v.21 n.4, p.593-622, Dec. 1989 [doi>10.1145/76894.76897]
• Mellor-Crummey89: J. M. Mellor-Crummey , T. J. LeBlanc, A software instruction counter, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.78-86, April 03-06, 1989, Boston, Massachusetts, United States
• Miller88: B. P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.135-144, June 20-24, 1988, Atlanta, Georgia, United States
• Milner90: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• Shaw87: Robert A. Shaw, "Improving garbage collector performance in virtual memory," STAN-TR-87-323, Stanford University Computer Science Department, 1987.
• Wilson89: P. R. Wilson , T. G. Moher, Demonic memory for process histories, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.330-343, June 19-23, 1989, Portland, Oregon, United States
• Zellweger84: P.T. Zellweger, "Interactive source-level debugging of optimized programs," CSL-84-5, Xerox Corporation Palo Alto Research Center, May 1984.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Algorithms, Design, Languages, Performance, Reliability