DI: an interactive debugging interpreter for applicative languages

ABSTRACT

The DI interpreter is both a debugger and interpreter of SISAL programs. Its use as a program interpreter is only a small part of its role; it is designed to be a tool for studying compilation techniques for applicative languages. DI interprets dataflow graphs expressed in the IF1 and IF2 languages, and is heavily instrumented to report the activity of dynamic storage activity, reference counting, copying and updating of structured data values. It also aids the SISAL language evaluation by providing an interim execution vehicle for SISAL programs. DI provides determinate, sequential interpretation of graph nodes for sequential and parallel operations in a canonical order. As a debugging aid, DI allows tracing, breakpointing, and interactive display of program data values. DI handles creation of SISAL and IF1 error values for each data type and propagates them according to a well-defined algebra. We have begun to implement IF1 optimizers and have measured the improvements with DI.

REFERENCES

• 1: W. B. Acherman , J. B. Dennis , William B Ackerman, VAL- ORIENTED ALGORITHMIC LANGUAGE, PRELIMINARY REFERENCE MANUAL, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 2: [Cann, 1984] D. C. Cann, S. J. Allan and R. R. Oldehoeft, An IF1 Driven Portable Code Generator , Colorado State University, Computer Science Department, Fort Collins, CO, Technical Report CS-84-15 (December 1984).
• 3: [Cann, 1985] D. C. Cann, S. J. Allan and R. R. Oldehoeft, "Implementing Programming Languages on the HEP," in Proceedings of the Workshop on Parallel Processing using the HEP (March 1985), pp. 15-30.
• 4: [Feo, 1987] J. T. Feo, "Evaluating the Expressive Power of Sisal Using the Livermore Loops," in preparation.
• 5: Gene L. Fisher , Kenneth I. Joy, A control panel interface for graphics and image processing applications, Proceedings of the SIGCHI/GI conference on Human factors in computing systems and graphics interface, p.285-290, April 05-09, 1987, Toronto, Ontario, Canada
• 6: Jean-Luc Gaudiot , Michel Dubois , Liang-Teh Lee , Nadim G Tohme, The TX16: A highly programmable multi-microprocessor architecture, IEEE Micro, v.6 n.5, p.18-31, Oct. 1986 [doi>10.1109/MM.1986.304709]
• 7: J. R Gurd , C. C Kirkham , I. Watson, The Manchester prototype dataflow computer, Communications of the ACM, v.28 n.1, p.34-52, Jan. 1985 [doi>10.1145/2465.2468]
• 8: S. C. Johnson, A portable compiler: theory and practice, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-104, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512771]
• 9: [Kernighan, 1984] B. W. Kernighan and D. M. Ritchie, "The M4 Macro Processor," in UNIX Programmer's Manual-Supplementary Documents , USENIX Association (March 1984).
• 10: [McGraw, 1985] J. R. McGraw, et. al., SISAL: Streams and Iteration in a Single Assignment Language: Reference manual. Lawrence Livermore National Laboratory, Livermore, CA, M- 146 Revision 1 (March 1985).
• 11: [Mycroft, 1981] A. Mycroft, "Abstract Interpretation and Optimising Transformations for Applicative Programs," Ph.D. dissertation, University of Edinburgh, December 1981.
• 12: Rodney R. Oldehoeft , Stephen J. Allan, Adaptive exact-fit storage management, Communications of the ACM, v.28 n.5, p.506-511, May 1985 [doi>10.1145/3532.3536]
• 13: Vivek Sarkar , John Hennessy, Partitioning parallel programs for macro-dataflow, Proceedings of the 1986 ACM conference on LISP and functional programming, p.202-211, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319863]
• 14: Vivek Sarkar , John Hennessy, Compile-time partitioning and scheduling of parallel programs, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.17-26, June 25-27, 1986, Palo Alto, California, United States
• 15: [Simpson, 1986] R. Simpson, SISAL Compiler User Manual, Lawrence Livermore National Laboratory, Livermore, CA, M-191 (September 1986).
• 16: [Skedzielewski, 1985a] S. K. Skedzielewski and R. K. Yates, Fibre: An External Format for SISAL and IF1 Data Objects, Lawrence Livermore National Laboratory, Livermore, CA, M-154 Version 1.0 (January 1985).
• 17: [Skedzielewski, 1985b] S. K. Skedzielewski, M. L. Welcome and R. K. Yates, SISAL/IF1 User's Guide, Lawrence Livermore National Laboratory, Livermore, CA, M-163 (April 1985).
• 18: [Skedzielewski, 1985c] S. K. Skedzielewski and J. Glaucrt, IF1 - An Intermediate Form for Applicative Languages, Lawrence Livermore National Laboratory, Livermore, CA, M-170 (July 1985).
• 19: S. K. Skedzielewski , M. L. Welcome, Data flow graph optimization in ifi, Proc. of a conference on Functional programming languages and computer architecture, p.17-34, January 1985, Nancy, France
• 20: [Welcome, 1986] M. L. Welcome, S. K. Skedzielewski, R. K. Yates and J. E. Ranelletti, IF2: An Applicative Language Intermediate Form with Explicit Memory Management. Lawrence Livermore National Laboratory, Livermore, CA, M-195 (November 1986).

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages
      D.3.4 Processors
          Subjects: Interpreters

General Terms:
Design, Languages, Performance, Verification