Hamilton, Geoff ORCID: 0000-0001-5954-6444 (1993) Compile-time optimisation of store usage in lazy functional programs. PhD thesis, University of Stirling.
Abstract
Functional languages offer a number of advantages over their imperative counterparts. However,
a substantial amount of the time spent on processing functional programs is due to the
large amount of storage management which must be performed. Two apparent reasons for this
are that the programmer is prevented from including explicit storage management operations
in programs which have a purely functional semantics, and that more readable programs are
often far from optimal in their use of storage. Correspondingly, two alternative approaches
to the optimisation of store usage at compile-time are presented in this thesis.
The first approach is called compile-time garbage collection. This approach involves determining
at compile-time which cells are no longer required for the evaluation of a program, and
making these cells available for further use. This overcomes the problem of a programmer not
being able to indicate explicitly that a store cell can be made available for further use. Three
different methods for performing compile-time garbage collection are presented in this thesis;
compile-time garbage marking, explicit deallocation and destructive allocation. Of these three
methods, it is found that destructive allocation is the only method which is of practical use.
The second approach to the optimisation of store usage is called compile-time garbage
avoidance. This approach involves transforming programs into semantically equivalent programs
which produce less garbage at compile-time. This attempts to overcome the problem
of more readable programs being far from optimal in their use of storage. In this thesis, it is
shown how to guarantee that the process of compile-time garbage avoidance will terminate.
Both of the described approaches to the optimisation of store usage make use of the
information obtained by usage counting analysis. This involves counting the number of times
each value in a program is used. In this thesis, a reference semantics is defined against which
the correctness of usage counting analyses can be proved. A usage counting analysis is then
defined and proved to be correct with respect to this reference semantics. The information
obtained by this analysis is used to annotate programs for compile-time garbage collection,
and to guide the transformation when compile-time garbage avoidance is performed.
It is found that compile-time garbage avoidance produces greater increases in efficiency
than compile-time garbage collection, but much of the garbage which can be collected by
compile-time garbage collection cannot be avoided at compile-time. The two approaches are
therefore complementary, and the expressions resulting from compile-time garbage avoidance
transformations can be annotated for compile-time garbage collection to further optimise the
use of storage.
Metadata
Item Type: | Thesis (PhD) |
---|---|
Date of Award: | 1993 |
Refereed: | No |
Uncontrolled Keywords: | Functional languages; Store usage; Compile time |
Subjects: | Computer Science > Software engineering |
DCU Faculties and Centres: | DCU Faculties and Schools > Faculty of Engineering and Computing > School of Computing |
Use License: | This item is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 3.0 License. View License |
ID Code: | 21140 |
Deposited On: | 08 Apr 2016 13:24 by Fran Callaghan . Last Modified 06 Nov 2020 12:38 |
Documents
Full text available as:
Preview |
PDF
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
738kB |
Downloads
Downloads
Downloads per month over past year
Archive Staff Only: edit this record