×

Adapting combinator and SECD machines to display snapshots of functional computations. (English) Zbl 0603.68003

A functional computation involves substituting for function applications in an expression until that expression is reduced to normal form. The views of computations presented by the sequence- and state-oriented debugging tools of imperative systems are inappropriate for use with functional computations. New debugging tools are needed to aid the development of functional programs, especially in the context of lazy evaluation.
After surveying previously reported debugging tools, we discuss a new debugging tool. Its implementation involves changing the reduction rules of the machine. The new reduction rules are applied to an interrupted computation to give a snapshot of that computation in source-level terms.
We have implemented tools to produce snapshots for eager SECD and lazy combinator reduction machines. Example snapshots are shown from each. The implementation for an eager SECD machine is relatively straightforward, so we confine discussion of this to a brief sketch. A more detailed account is given of the implementation for a lazy combinator reduction machine; as this offers one solution to well-known problems with debugging functional programs in the context of lazy evaluation and combinator code.

MSC:

68N01 General topics in the theory of software
68Q60 Specification and verification (program logics, model checking, etc.)

Software:

Miranda
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hall, C. V. and O’Donnell, J. T., ”Debugging in a Side Effect Free Programming Environment”,ACM SIGPLAN Notices, Vol. 20, No. 7, pp. 60–68, 1985.
[2] Henderson, P.,Functional Programming: Application and Implementation, Prentice-Hall, London, 1980. · Zbl 0426.68059
[3] Hughes, R. J. M., ”Super-Combinators: A New Implementation Method for Applicative Languages”,ACM Symposium on LISP and Functional Programming, pp. 1–10, August, 1982.
[4] Kieburtz, R. B.,A Proposal for Interactive Debugging of ML Programs, Oregon Graduate Center, February, 1985.
[5] Landin, P. J., ”The Next 700 Programming Languages”,Communications of the ACM, 9, pp. 157–166, 1966. · Zbl 0149.12505
[6] Lieberman, H., ”Steps Toward Better Debugging Tools for Lisp”,ACM Symposium on LISP and Functional Programming, pp. 247–255, August, 1984.
[7] Meira, S. L., ”Optimized Combinatoric Code for Applicative Language Implementation”,Proceedings 6th International Symposium on Programming, Springer-Verlag, pp. 206–216, April, 1984. · Zbl 0568.68011
[8] Morris, J. H., ”Real Programming in Functional Languages”, inFunctional Programming and its Applications (J. Darlington, P. Henderson, and D. A. Turner, eds.), Cambridge University Press, 1982.
[9] Mycroft, A., ”Abstract Interpretation and Optimising Transformations for Applicative Programs”,Ph. D. Thesis CST-15-81, Dept. of Computer Science, University of Edinburgh, December, 1981.
[10] Peyton Jones, S. L., ”Yacc in Sasl – an Exercise in Functional Programming”,Software – Practice and Experience, Vol. 15, No. 8, pp. 807–820, 1985. · Zbl 0566.68006
[11] Toyn, I. and Runciman, C.,Adapting SECD and Combinator Reduction Machines to Display Snapshots of Functional Computations, YCS. 79 Department of Computer Science, University of York, 1985. · Zbl 0603.68003
[12] Turner, D. A., ”A New Implementation Technique for Applicative Languages”,Software – Practice and Experience, Vol. 9, No. 1, pp. 31–49, 1979. · Zbl 0386.68009
[13] Turner, D. A., ”Miranda: A Non-Strict Functional Language with Polymorphic Types”,Lecture Notes in Computer Science, 201 Springer-Verlag, Nancy, France, pp. 1–16, September, 1985. · Zbl 0592.68014
[14] Wadler, P.,A Splitting Headache–and its Cure! Strict vs. Lazy Semantics for Pattern Matching in Lazy Languages, Programming Research Group, Oxford University, January, 1985.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.