Visualizing the Evaluation of Functional Programs for Debugging

John Whitington, Tom Ridge · 2024

Read Visualizing the Evaluation of Functional Programs for Debugging by John Whitington, Tom Ridge (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00618.txt.

Description

A 2024 arXiv research paper by John Whitington, Tom Ridge. In this position paper, we present a prototype of a visualizer for functional programs. Such programs, whose evaluation model is the reduction of an expression to a value through repeated application of rewriting rules, and which tend to make little or no use of mutable state, are amenable to visualization in the same fashion as simple mathematical expressions, with which every schoolchild is familiar.

Catalog record

CREATORJohn Whitington, Tom Ridge
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-00618

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Visualizing the Evaluation of Functional Programs for Debugging John Whitington, Tom Ridge Abstract . In this position paper, we present a prototype of a visualizer for functional programs. Such programs, whose evaluation model is the reduction of an expression to a value through repeated application of rewriting rules, and which tend to make little or no use of mutable state, are amenable to visualization in the same fashion as simple mathematical expressions, with which every schoolchild is familiar. We show how such visualizations may be produced for the strict functional language OCaml, by direct interpretation of the abstract syntax tree and appropriate pretty-printing. We describe (and begin to address) the challenges of presenting such program traces in limited space and of identifying their essential elements, so that our methods will one day be practical for more than toy programs. We consider the problems posed by the parts of modern functional programming which are not purely functional such as mutable state, input/output and exceptions. We describe initial work on the use of such visualizations to address the problem of program debugging, which is our ultimate aim. \Copyright John Whitington and Tom Ridge \serieslogo \volumeinfo Billy Editor and Bill Editors2Conference/workshop/symposium title on which this volume is based on111 \EventShortName \DOI 10.4230/OASIcs.xxx.yyy.p 1991 Mathematics Subject Classification D.2.5 Testing and Debugging 1. Introduction When we do mathematics on paper, we write an expression or equation and, through a series of legal transformations, produce a simpler one that, we hope, tells us what we want to know. It is the same with functional programming, but the semantics define more closely the order in which the expression is evaluated, choosing each transformation by inspection of the shape of the expression. Of course, this is not quite how the compiled code runs, but it is the mental model. So it is natural, when teaching students functional programming, to proceed by analogy to the mathematical model in which they are already well-practiced. Since computer languages must be more formal in their choice of evaluation order, we tend to underline the sub-expression being evaluated at each step. Given the function f for doubling a number, we might have: f 3 = 1 + 2 * 3 \displaystyle\Longrightarrow 6 = 1 + 2 * 3 \displaystyle\Longrightarrow 6 = 1 + 6 \displaystyle\Longrightarrow 6 = 7 \displaystyle\Longrightarrow false There are differences from mathematics, of course: the last step may be rather confusing to the schoolchild (our equals sign does not denote an equation as such, but a comparison operator). Such visualizations are longwinded to write on paper, for all but the least substantial programs. We should like to generate them by computer. In order to provide a tool useful to both learners and the everyday programmer, we will begin with a subset of a real language (rather than building our own toy one), extend it to work for the whole language, and integrate it properly with the toolchain as a first class citizen. We are writing, in essence, a step-by-step interpreter. What is the relevance to debugging? The dream of debugging is this: having observed a misbehaviour caused by a bug, we assemble all relevant information, both about the program source and the full trace of the program’s operation, and, describing ourselves concisely to the computer, we narrow the circumstances down, again and again reducing the search space, until we have the bug in our grasp, and understand it fully. The fix is then often easy. But we are very far from this dream, even today. In his introduction to a Special Issue of Communications of the ACM in 1997 “The Debugging Scandal and What to Do About It” [ 5 ] , Lieberman writes: “Today’s commercial programming environments provide debugging tools that are little better than the tools that came with programming environments thirty years ago. It is a sad commentary on the state of the art that many programmers name “inserting print statements” as their debugging technique of choice.” We claim this is still largely true, twenty years later. 2. Related Work Two useful surveys [ 16 ] , [ 17 ] give a general overview of recent developments in this area, the first specific to functional programming, the second with wider scope. A very broad introduction [ 8 ] gives background. A comprehensive survey [ 11 ] of education systems for program visualization is useful too. We pick out a few recent systems for further discussion. The WinHIPE system [ 7 ] is a recent incarnation of these ideas for the HOPE language. It uses a step-by-step evaluation system, and explicitly addresses the problems of scale by elision of information and a focusing mechanism. The emphasis, however, is on graphical (tree-based) representations, an approach we shall not take, being of the belief that trees can often be, in fact, harder to read than well-pretty-printed program representations. The Visual Miranda Machine [ 1 ] provides a trace of the evaluation of a lazy functional program, together with a commentary showing the reason for choosing each evaluation step. There is a discussion of granularity, taking the example of the “list comprehension” language feature. DrScheme [ 2 ] provides, amongst many other facilities, an “algebraic stepper” for the Scheme language that can print out steps of evaluation. The stepper, however, supports only a subset of the language. The implementation is interesting, though – it reuses some of the underlying Scheme implementation to ensure equivalent semantics. Touretsky describes a LISP-based system [ 14 ] that produces mainly textual traces, but with some use of graphical elements to indicate the different scoping mechanisms peculiar to LISP. The presentation of ZStep95 [ 15 ] begins by noting that debugging is, essentially, a human interface problem. The authors concentrate on the concept of immediacy (temporal, spatial, and so on), which they see as essential, and exhibit a stepping debugger for a functional language which can go back and forth through time. There is a system bolted onto Haskell [ 3 ] which is not an interpreter as such, but allows the programmer to insert observation points in the code, within the syntax of the source language. At such points, the values are printed out. This has the advantage of explicitly dealing with at least part of the problem of scale – only what we wish to be printed is printed. Another approach to this problem is as a special case of the more general concept of a calculator [ 9 ] , [ 4 ] , showing how it pertains to various logical systems with a mathematical basis, not just functional programs. Prospero [ 12 ] is a more fully-developed system, again for a lazy language. It includes methods for filtering the evaluation trace to elide information and a careful discussion of usability issues. These systems are mostly concerned with program visualization for teaching; we wish to bias ourselves towards the task of general debugging, hoping that some of the educational uses will be subsumed by it (the authors of DrScheme [ 2 ] urge caution here, choosing instead to build a “tower” of syntactically restrictive variants of Scheme specifically for educational purposes. They say that, due to the fact that so many sequences of

Read the complete text