Thesis
Tracing lazy evaluation by program transformation
Southern Cross University, School of Multimedia and Information Technology
Doctor of Philosophy (PhD), Southern Cross University
1997
Metrics
93 Record Views
Abstract
This thesis presents research into tracing the evaluation of lazy functional languages. The work is composed of two independent components:
• the development of a portable trace generation mechanism, and
• the description of appropriate source level trace representations, and investigation of the requirements for a browsing tool to enable a user to navigate over such traces.
The thesis focuses on transformational approaches to trace generation: the original program is transformed (instrumented) so that, on evaluation, the result of an expression is yielded together with a trace of its evaluation. This is a low level trace containing a description of each reduction carried out during expression evaluation. The technique does not necessarily mirror the evaluation mechanism adopted by the language's implementors; rather it simulates the reduction mechanism defined by a formal model of lazy evaluation which we describe.
Four different but related instrumentation schemes are described. Performance tests are carried out to measure the efficacy of the schemes. The performance of another portable tracing scheme, namely a special interpreter for the formal semantic model, is measured as a comparison.
The redex trace produced by an instrumented program is considered to be not generally useful as it describes lo-w level or "microscopic" events. Suitable higher level trace forms are investigated and - continuing the transformational theme of the thesis - means of generating these from the redex trace are described. The high level traces described are characterised by being textual in nature (expressions described by text strings rather than graphs) which reflects the form of the source language. Furthermore, the trace considered to be the most appropriate for describing lazy evaluation is sequential in structure: such a trace is a list of successively simplified expressions.
As traces are large artifacts it is essential that trace size is minimised and that tools are provided to enable a user to view and to navigate over the trace. A technique to reduce the size of the higher level trace by suppressing display of the evaluation of "trusted" functions is described. A set of possible user requirements of a browsing tool is defined and a subset of these implemented in a prototype browser. The implementation is used to explore issues of browser construction and user interface design.
Details
- Title
- Tracing lazy evaluation by program transformation
- Creators
- Richard Douglas Watson
- Contributors
- Bruce Lo (Supervisor) - Southern Cross UniversityEric Salzman (Supervisor)
- Awarding Institution
- Southern Cross University; Doctor of Philosophy (PhD)
- Theses
- Doctor of Philosophy (PhD), Southern Cross University
- Publisher
- Southern Cross University, School of Multimedia and Information Technology
- Number of pages
- x, 217
- Identifiers
- 991012958498602368
- Copyright
- © Richard D. Watson 1997
- Academic Unit
- Faculty of Business, Law and Arts
- Resource Type
- Thesis