Advanced Redex Trails:
fully-fledged tracing technology for functional programs
(project proposal)

Colin Runciman
Department of Computer Science, University of York

This is a revised version of the proposal submitted to EPSRC, the research council that is funding the project. Some minor sections giving personal or financial details, or addressing issues of EPSRC policy, have been omitted.

Summary:

In many fields, high expectations of Information Technology are limited in practice mainly by current methods of developing computer software. Declarative programming systems in general, and functional languages in particular, have an important part to play in an improved software technology. These languages free programmers from the need to express specific sequences of calculation. They also provide powerful ways of directly combining component functions. They are inherently safer than programming languages now in widespread use, and dramatically more concise.

However, the very high-level nature of functional languages poses two big problems: (1) how to turn programs into efficient computations; (2) how to trace programming errors from the faults they cause. Since the mid 1980s, problem (1) has been a popular target of research, and excellent progress has been made with it: there are now optimising compilers for functional languages. But problem (2) has received less attention, and in practical terms it remains wide open. The lack of tracing and debugging tools is a long-standing gap in functional-language technology, deterring potential users.

I therefore propose a decisive attack on the tracing problem for functional programs. My aim is to advance a successful but limited prototype, recently developed with ROPA funding, to the stage of a convincing tool for practical application. Several research problems must be solved to achieve this aim: to give just two examples, efficient low-level counterparts must be found for high-level combinators with subtle properties of abstraction, and new algorithms are needed for incremental compression of heap structures to file without disturbing lazy evaluation.

Key phrases:

declarative languages; functional programming; software development; fault-tracing tools; programming environments.

1 Context

1.1 Past Projects

The broad aim of my work in recent years has been to advance the state of the art in functional programming systems, enabling wider and more effective use to be made of this technology. I have run a series of research projects in this connection, with a mixture of government and industrial funding. The most important of these for this proposal have been:

FLARE (1991--93, IEATP, GR/F 98857 C2117)

This project aimed to demonstrate that functional programming systems could be effectively applied to a range of demanding applications. It was a collaboration between industrial and academic partners, each of whom developed applications in their own field of expertise. British Telecom managed the project. I was the technical co-ordinator and co-edited a book based on the project [runcimanwakeling95]. One important conclusion from FLARE was that the availability of profiling and tracing tools can be a critical factor in the successful use of functional programming. At York we developed novel methods for profiling heap memory [runcimanwakeling93a] and parallel evaluation [RuncimanWakeling94]. There was not time to address the more complex tracing problem, but it was put high on our list of topics for future research.

Embedding Functional Programs (1994--, Canon Research Europe)

Towards the end of FLARE, a separate PhD project at York aimed to adapt a functional language implementation for the special requirements of embedded systems, including demands for memory efficiency and a richer treatment of I/O [wallacerunciman95b]. CRE has funded a continuation of this work. The current techniques used for embedding software into devices such as typewriters and copiers are a long way from purely functional programming. But there are prototype software systems developed on large workstations in declarative languages that Canon might one day wish to embed in such office products. We have been researching extensions to functional languages and their implementations to make such embedding possible. A significant part of this work has been a novel treatment of compressed binary data [WallaceRunciman98]: this could be a useful part of our tracing technology, where one of the key problems is to reduce memory demands for trace structures representing entire computational histories.

Selective tracing of functional computations using graph reduction with redex trails (1996--97, ROPA, GR/K64334)

This 18-month project aimed to demonstrate the feasibility of a particular approach to the tracing problem by building a prototype implementation. We extended a compiled graph-reduction implementation of the functional language Haskell, transforming programs so that at run-time they could build trails of contracted redexes (intermediate expressions, re-written by appeal to definitions in the program) attaching a comprehensive derivation tree to every value [sparudruncimanplilp97]. We developed a special purpose browser for the examination of trails starting from outputs or run-time faults; we experimented with partial trails and pruning rules to increase the size of applications that could be handled [SparudRuncimanIFL97]. This ROPA project convinced us that redex trails can be made the basis of an effective tracing system, useful in real applications. The goal of the project now proposed is to fulfil this potential.

1.2 Institution

The Computer Science department at York has internationally known research groups and attracted the highest possible rating (5*) in the most recent national Research Assessment Exercise. Software technology, including compilers and related tools, is a long-standing theme in the department's work.

2 Proposed Research

2.1 Background

The tracing problem

Functional programming systems offer significant advantages over more conventional alternatives, particularly for complex symbolic applications. The abstracting power and declarative nature of functional languages, largely free from low-level concerns such as sequence of evaluation and memory management, enable computational ideas to be expressed very directly and concisely, with fewer possibilities for error.

However, this property of being abstract is two-edged. Though there are fewer classes of possible mistakes in functional programs, errors do still occur, and programmers need to trace their causes. Time and again the lack of tools for tracing and debugging has deterred software developers from using functional languages [Wadler98]. This is not simple neglect on the part of implementors; a high level of abstraction separating language from machine makes tools genuinely hard to build. A computation of a conventional imperative program is comparatively easy to trace, step by step, but a functional computation performed using a sophisticated evaluation strategy such as normal order graph reduction involves a sequence of events not explicit in the program, and often baffling to the intuition. Hence the research challenges: What is an appropriate form of trace for functional computations? How best can such traces be constructed and applied in practice?

Approaches to the problem

In the 1980s, little work was done on profiling and tracing functional computations. In the 1990s, work at York and elsewhere has delivered effective profiling techniques, leading to marked reductions in the time and space costs of many applications [RuncimanRojemoSchool96, sansompeytonjonestoplas97]. Success with the tracing problem has not come so easily: a review in a recent Australian thesis [watsonphd] notes some twenty different attempts at a solution, none of them conclusive!

Approaches broadly divide into those that base traces on a linear sequence of events, and those that represent computational history using some sort of dependency graph. Methods based on a sequence of events have had some success for `mostly functional' languages with a strictly applicative evaluation sequence; Tolmach and Appel's system for the ML language is a notable example [tolmachappeljfp95]. The benefits of the sequential approach are that a trace can be displayed as computation proceeds, and that it is easy to trade time for space: given a few check-point states stored at well-chosen intervals, any past state of computational history can be reached by re-execution.

However, the more ideal purely functional languages permit the definition of non-strict functions, implemented using the lazy evaluation strategy of call-by-need. Despite some valiant attempts [watsonphd], the evidence to date is that for such programs linear traces of the sequence of reductions are ineffective. Rather, to track faults in realistic computations, it is necessary to record a non-linear structure of dependencies between expressions.

Redex trails prototype

In our work, a network of redex trails [sparudruncimanplilp97, SparudRuncimanIFL97] represents these dependencies. Functional expressions can be viewed as trees or --- since sub-expressions can be shared and may recursively reference enclosing expressions --- as graphs. Evaluation repeatedly replaces one subgraph by another, where the reduction rules used to define replacements are derived from equations that constitute the program. At each reduction step, a redex matching the left-hand side of an equation is replaced by the corresponding instance of the right-hand side. To construct redex trails, at each reduction during the computation we arrange that from every node n of the resulting subgraph there is a link to the parent redex whose reduction caused n to be introduced. Using a special-purpose browser which reconstructs expressions in source form, the programmer can proceed backwards along the relevant trails from a fragment of output, from a run-time error, or from a point at which an apparently unproductive computation has been interrupted. Our ROPA project has shown the viability of this approach, as outlined in §1; but despite its promising results, our ROPA prototype is limited in a variety of ways, each prompting lines of further research:

Performance: A program transformed to generate redex trails can run 10--20 times more slowly than the original. Research questions: Could new abstract-machine instructions provide low-level replacements for current high-level combinators to manipulate trails? How can normally compiled functions be mixed with trail-generating ones, when trail generation alters type-structure at all levels?
Capacity: Trails are constructed as data structures in heap memory. Even partial redex trails are very large and current pruning strategies may discard needed information. Research questions: Could our heap compression techniques be used to good effect here? Could some form of meta-programming be used to give greater control over pruning?
Transience: Because trails are built in heap memory, when a functional computation is closed the trail is lost. Research question: How can trails be archived to file incrementally as computation proceeds? (This is a delicate problem because of the relationship between trails and lazy evaluation, and the need to avoid revising the archive.)
Scope: Important classes of Haskell programs cannot yet be traced. For example, I/O is very restricted, and comprehensions are traced in terms of their low-level translations. Research questions: What extensions to the current definition of redex trails best represent these forms of computation? What form of access and display are most effective for these extensions?
Host: The prototype is implemented as an extension of the nhc compiler and run-time system. It cannot be used in conjunction with other implementations (eg. the optimising compiler ghc). Research questions: How can the current machinery for redex trails be re-expressed in a portable tracer? If source-to-source translation is used, could a low-level library with an interface defined in Green Card [GreenCard97] or H/Direct [HDirect98] provide the necessary extension of primitives? If so, assuming what interface to the local run-time system?
User interface: The prototype trail browser was developed ad hoc. It is quite complex and using it successfully sometimes requires an implementor's insight. Research questions: How can fault-tracing be modelled as a problem-solving activity? How well do the resources provided by the trail browser fit the task? How can these and other insights be reflected in improved design, including greater support for fault-finding strategies?

One consequence of these limitations and outstanding research questions is that the prototype has had few users --- mainly the developers and their students. The obstacles to wider practical use do not seem insurmountable, but there is a lot of work to be done, requiring various skills.

Other alternatives

Though we have developed redex trails as the basis for tracing, we are aware of alternatives. Perhaps the most advanced of these is Nilsson's Freja system, based on Evaluation Dependence Trees (EDTs) [NilssonPhd98]. His EDT nodes record equivalences between expressions, where each parent equivalence is a direct consequence of the child equivalences and an equation in the program. The starting point in an EDT is not a final reduction leading to an output or point of error but the root equivalence between an original main expression and its entire computed result. Two drawbacks of the EDT approach in comparison with redex trails are that incremental archiving to file is even more difficult (Nilsson rules it out in favour of repeated execution to obtain new fragments of the EDT) and that the user has to reason about larger displayed expressions.

2.2 Programme and Methodology

Overall aim:

a solution to the problem of tracing higher-order lazy functional computations that is effective in practice, based on tools for the construction and examination of redex trails.

Primary objectives

a tracing system for Haskell 98 (the nearest thing there is to a standard lazy functional language) hosted in the freely available nhc compiler;
a system that incorporates a method for incremental archiving of traces to file, alleviating pressure on heap memory and increasing the returns from the overhead of generating trails;
a portable variant of the tracer, based on source-to-source transformation and a support library, with a clearly-defined interface to supporting operations that any host implementation must provide; (In particular, we aim to provide a version of our tracer that works in conjunction with the widely-used ghc and hugs systems, currently being integrated with EPSRC support --- GR/L 34297.)
a trace-browser designed to be an effective tool for locating faults based on a thorough analysis of the tracing task as a problem-solving activity, and of the browser display as a resource; the browser will also be equipped to record how it is used, so that data can be gathered from use in practice.

Secondary objectives

to improve the speed of computations generating trails, for example by transferring the operations of trail-level function abstraction and application to a lower layer of implementation;
to obtain results from a wide range of practical tests using the tracer, and hence to improve the design --- eg. to determine what strategies users choose to adopt when examining traces, and to extend the tracer with explicit support for the strategies that seem most successful;
to exploit the representation of redex trails as functional data structures by devising a system for meta-programming search and display routines specific to an application.

Timeliness and novelty

The need for a tracing tool that can cope with lazy higher-order functional programs has been recognised for almost twenty years. The lack of a tracer has been a key reason for the surprisingly limited use of a programming technology with so many advantages [Wadler98]. There are now optimising compilers for languages like Haskell, and tools for the integration of functional components into larger systems. A solution to the tracing problem is overdue. It is a difficult problem to tackle comprehensively, but the redex trails approach is distinctive, and with the results already obtained in the ROPA project we are well-placed to succeed.

Methodology

A lot of work has gone into our ROPA prototype, with promising results. We should advance from the given position, not restart from scratch. The principles of the compile-time transformation, the functional representation of redex trails, and the message-passing architecture of the tracer (browser communicating with functional computation) should all be preserved. We shall also continue to work with the nhc compiler, but reducing dependencies on its internal world to increase portability. Java was used for the prototype browser, and proved quite satisfactory. Though we plan to re-think the browser design, implementation will again be in Java --- a browser that works well over the internet could prove useful when we want to support external users.

So far as practical evaluation is concerned, we do not intend to set up rigorous laboratory experiments scrutinising tracing `micro-tasks'. Such experiments would absorb too much effort. Results from actual use in practice are preferable for our purpose, but general feedback from casual use might be too vague or sparse. One kind of evaluation exercise we intend to use requires two programmers. A explains to B a correctly working program of moderate size (around 500 lines) that A wrote some time ago. B now secretly introduces several deliberate errors into the program, of a kind undetected by the compiler. Given the faulty program, A uses the tracer to locate and fix all the errors, thinking aloud as they do so. B takes notes throughout, and afterwards A and B review the exercise, recording the main issues arising.

Programme of work

Figure 1 summarises the workplan in diagrammatic form. From the start, the two researchers will engage in joint tasks combining their skills as well as solo tasks demanding their individual expertise. Brief descriptions follow for each activity.

Figure 1:

Acquire skill with prototype: Both RAs need to become expert users of the prototype tracer to inform their work developing its successor. Each will also need to become familiar with components of the implementation for which they will be responsible.
Tracing as a problem-solving task: Newell and Simon [NewellSimon72] pioneered ways of analysing the human information processing required to solve a variety of problems, such as chess puzzles. We will similarly analyse the activity of using the tracer to locate faults in programs. The purpose is to gain understanding of tasks that must be supported by an improved browser for redex trails, including strategies that users might in principle choose to adopt.
Display as resource: The display provided by the browser is a critical resource, as typical redex trails are complex and very large. Using techniques previously applied to theorem-proving systems, we shall model display information as a resource for reasoning about programs [FieldsWrightHarrison97]. The results will inform the redesign of the browser.
Lift language restrictions: The top priorities are list comprehensions and file I/O. Comprehensions require new transformation rules; file I/O requires special support from the run-time system; both require extensions to the browser interface.
Incremental archiving: We hope to achieve incremental archiving by extending trail-pruning routines applied by the prototype during garbage collection. Information in sections of trail deleted from heap memory will be archived to file, with the continuing stump in the main memory trail recording an archival reference. Care will be needed to avoid any costly revision of archived values or undesirable change in the degree of evaluation. Archived trails must also be properly linked to all the other information that may be required by the browser (eg. program sources, indexed I/O transcript).
Faster trail generation: Trail-manipulating combinators are introduced by transformation to replace each function abstraction and each application in the original program. In the prototype, these combinators are defined in Haskell as part of a redex-trail library. We aim to define new primitive operations, perhaps new G-machine instructions in nhc, to make reduction of these combinators much faster. However, degree of evaluation is extremely delicate, particularly in the way that saturation of function applications is handled, and some likely-looking primitives fail at this point. The ability to mix traced and untraced modules could give another route to faster generation of selective trails.
Redesign browser: Based on experience using the prototype, and the results of the problem-solving and resource analyses, the trail browser will be redesigned. We shall try to minimise changes to the message-passing interface with the Haskell world. The browser will also be extended to record information about how it is used.
Devise experiments and instructions: Writing instructions for the use of the tracer, including information about how to carry out systematic experiments, will be an essential prelude to external use and feedback. The exercise of writing about use of the tracer should also provoke further insights into what is needed, and ideas for development.
Interim release of tracer: an important milestone. All effort will focus at this stage on pulling together the different strands of development in the first year, to provide a reliable distribution of the tracer hosted by a version of nhc. This will also be a good time to visit likely users.
Concerted trials of tracer: We shall test the effectiveness of the tracer ourselves using exercises of the kind noted under `methodology'. Trials by external users will be promoted and supported by mailing lists, visits and a workshop.
Analyse usage and revise models: Study of the data automatically collected by the browser, alongside reports and requests from users, will confirm or alter our design assumptions and priorities. The problem-solving and resource models will be revised, and improvements made to the trail browsing interface.
Portability interface: A portable variant of the tracer must be detached from nhc in two respects. Compile-time transformations working on internal representations must be adapted to generate a fresh source. Extra run-time routines required by the tracer should be isolated, specified and defined in portable libraries (Haskell 98, Green Card or H/Direct). The portable version of the tracer must forfeit some sources of efficiency that depend on internal properties of nhc, but an optimising compiler such as ghc might amply compensate for such losses.
Develop support for strategies: Typical redex trails involve a large number of interconnecting paths, and there are various plausible strategies for investigating faults of different kinds. Some of these could be directly supported by the tracer --- for example, reducing display information by blocking off parts of a trail irrelevant to a specific line of enquiry, and automatically following any unique continuations. The choice of strategies to support will be informed by discussion with experienced users, and examination of usage logs.
Metaprogramming display and search: Redex trails are functional data structures so there is scope for trace-time computation over them. For example, displays of some large data structures could be vastly improved by application-specific rules --- though care must be taken to avoid forcing evaluation unnaturally. We also plan to investigate ways of encoding specialised searches over trails.
Final release and documentation: A Haskell implementation incorporating the new tracer, with explanatory papers, will be made available on the internet. Another task in the closing stages will be to finish writing up results of our work for refereed publication.

Project management

A weekly project meeting will provide a regular occasion to review current progress and confirm immediate plans. With a small team, working closely together, these meetings will naturally be informal. However, written records will be kept to avoid misunderstandings or things being forgotten. Interested visitors may be invited to join these meetings, and regular meetings of the Programming Languages and Systems research group will give further opportunity for brief reports and discussion.

Once a quarter we shall review progress on the project as a whole, revising plans if necessary to secure the most important objectives. We shall also issue a short quarterly bulletin to our academic and industrial contacts, and any other interested parties.

2.3 Dissemination and exploitation

We shall seek in various ways to encourage both academic and industrial Haskell users to try our new tracer, and to participate in its further development. The plan is to release an experimental version of the tracer at the end of the first year, as the common platform for a concerted period of trial use. We shall make suitable advance announcements on the internet, seek opportunities to present our work on the tracer at recognised conferences, and also hold a one-day workshop at York. Within the UK, we may visit users to get them started. Besides establishing a mailing list for general feedback and discussion, we shall publish details of suggested forms of tracing experiment on the web.

There are several archival FTP sites for public domain implementations of functional languages. We plan to make the final results of our work freely available by placing copies of software at these sites, in addition to publishing papers.

2.4 Resources

The appropriate scale for this project has been determined by comparison with the 18-month ROPA project during which the prototype redex-trail system was developed.

People

If we are to push this tracing technology far enough to make it really effective in practice, there is a lot of work to be done on several fronts. Hence the proposal to hire a team of two post-doctoral RAs for two years.

Infrastructure and equipment

The department of Computer Science at York provides computing facilities including networking and file-service, with technician support.

Each of the RAs will need a workstation. The two most common platforms for developers and users of research languages are Suns and PCs. Of these, PCs offer better performance for the price --- and we have access to an UltraSparc compute server if a Sun platform is needed. At the time of writing £2000 buys a PC system including a 400MHz Pentium II processor, 128Mb RAM, 8.4Gb disk, 17"--19" monitor, CDROM, network and graphics cards. Suitable components will be chosen and purchased separately, and assembled by our departmental technicians.

Travel

We request funds to participate in relevant conferences. ICFP is the premier international conference in functional programming; INTERACT is an international conference with user interface design as a central interest. IFL is an established European workshop emphasising new implementation methods and practical experiments in functional programming. The costing assumes that we all attend ICFP but only two of us attend each of IFL and INTERACT.

We hope to maintain close working links with researchers in Sweden. Jan Sparud (Gothenburg) worked on the ROPA project, and we value continuing collaboration with him. Henrik Nilsson (Linköping) has developed a rival approach to functional tracing, based on Evaluation Dependence Trees. We propose to visit Sweden twice a year.

Within the UK, we have links with relevant research groups at several other universities, from Exeter to St Andrews, and with industrial R&D sites, mainly in the South. We request funds for visits to discuss the development of the tracer, and to promote its experimental use.

References

[FieldsWrightHarrison97]: B. Fields, P. Wright, and M. Harrison. Objectives, strategies and resources as design drivers. In S. Howard, J. Hammond, and G. Lindgaard, editors, Human-Computer Interaction INTERACT'97, pages 164--171. Chapman and Hall, July 1997.
[FieldsMerriam98]: R. E. Fields and N. A. Merriam. Inference and information resources: A design case study. In P. Johnson and P. Markopoulos, editors, Eurographics Workshop on Design, Specification and Verification of Interactive Systems. Springer, 1998. In press.
[HDirect98]: S. Finne, D. Leijen, E. Meijer, and S. L. Peyton Jones. H/Direct: a binary foreign language interface for Haskell. In Proc. 3rd ACM International Conference on Functional Programming (ICFP'98), pages 153--162. ACM Press, September 1998.
[NewellSimon72]: A Newell and H. A. Simon. Human Problem Solving. Prentice-Hall, 1972.
[NilssonPhd98]: H. Nilsson. Declarative debugging for lazy functional languages. PhD thesis, Linköping, Sweden, 1998.
[GreenCard97]: S. L. Peyton Jones, T. Nordin, and A. Reid. Green Card: a foreign language interface for Haskell. In Proc. ACM SIGPLAN Haskell Workshop, Amsterdam, June 1997.
[rojemofpca95]: N. Röjemo. Highlights from nhc --- a space-efficient Haskell compiler. In Proc. 7th Intl. Conf. on Functional Programming Languages and Computer Architecture (FPCA'95), pages 282--292. ACM Press, June 1995.
[RuncimanRojemoSchool96]: C. Runciman and N. Röjemo. Heap profiling for space efficiency. In J. Launchbury, E. Meijer, and T. Sheard, editors, 2nd Intl. School on Advanced Functional Programming, pages 159--183, Olympia, WA, August 1996. Springer LNCS Vol. 1129.
[runcimanwakeling93a]: C. Runciman and D. Wakeling. Heap profiling of lazy functional programs. Journal of Functional Programming, 3(2):217--245, April 1993.
[RuncimanWakeling94]: C. Runciman and D. Wakeling. Profiling parallel functional computations (without parallel machines). In J.T. O'Donnell and K. Hammond, editors, Proc. 1993 Glasgow Workshop on Functional Programming, pages 236--251. Springer-Verlag Workshops in Computing, 1994.
[runcimanwakeling95]: C. Runciman and D. Wakeling, editors. Applications of functional programming. UCL Press, 1995.
[sansompeytonjonestoplas97]: P. M. Sansom and S. L. Peyton Jones. Formally based profiling for higher-order functional languages. ACM Transactions on Programming Languages and Systems, 19(2):334--85, March 1997.
[SparudRuncimanIFL97]: J. Sparud and C. Runciman. Complete and partial redex trails of functional computations. In C. Clack, K. Hammond, and T. Davie, editors, Selected papers from 9th Intl. Workshop on the Implementation of Functional Languages (IFL'97), pages 160--177. Springer LNCS Vol. 1467, September 1997.
[sparudruncimanplilp97]: J. Sparud and C. Runciman. Tracing lazy functional computations using redex trails. In H. Glaser, P. Hartel, and H. Kuchen, editors, Proc. 9th Intl. Symposium on Programming Languages, Implementations, Logics and Programs (PLILP'97), pages 291--308. Springer LNCS Vol. 1292, September 1997.
[tolmachappeljfp95]: A. Tolmach and A. W. Appel. A debugger for Standard ML. Journal of Functional Programming, 5(2):155--200, April 1995.
[Wadler98]: P. Wadler. Why no one uses functional languages. ACM SIGPLAN Notices, 33(8):23--27, August 1998.
[wallacerunciman95b]: M. Wallace and C. Runciman. Lambdas in the Liftshaft --- functional programming and an embedded architecture. In Proc. 7th Intl. Conf. on Functional Programming Languages and Computer Architecture (FPCA'95), pages 249--258, La Jolla, June 1995. ACM Press.
[WallaceRunciman98]: M. Wallace and C. Runciman. The bits between the lambdas: Binary data in a lazy functional language. In Proc. Intl. Symp. on Memory Management, pages 107--117, Vancouver, Canada, October 1998. ACM Press.
[watsonphd]: R. D. Watson. Tracing Lazy Evaluation by Program Transformation. PhD thesis, Southern Cross, Australia, October 1996.

This document was translated from L^AT_EX by H^EV^EA.