Change search
ReferencesLink to record
Permanent link

Direct link
Positive supercompilation for a higher-order call-by-value language
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
2008 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Intermediate structures such as lists and higher-order functions are very common in most styles of functional programming. While allowing the programmer to write clear and concise programs, the creation and destruction of these structures impose a run time overhead which is not negligible. Deforestation algorithms is a family of program transformations that remove these intermediate structures in an automated fashion, thereby improving program performance. While there has been plenty of work on deforestation-like transformations that remove intermediate structures for languages with call-by-name semantics, no investigations have been performed or call-by-value languages. It has been suggested that existing call-by-name algorithms could be applied to call-by-value programs, possibly introducing termination in the program. This hides looping bugs from the programmer, and changes the behaviour of a program depending on whether it is optimized or not. We present a transformation, positive supercompilation, for a higher-order call-by-value language that preserves termination properties of the programs it is applied to. We prove the algorithm correct and compare it to existing call-by-name transformations. Our results show that deforestation-like transformations are both possible and useful for call-by-value languages, with speedups up to an order of magnitude for certain benchmarks. Our algorithm is particularly important in the context of embedded systems where resources are scarce. By both removing intermediate structures and performing program specialization the footprint of programs can shrink considerably without any manual intervention by the programmer.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2008. , 67 p.
Series
Licentiate thesis / Luleå University of Technology, ISSN 1402-1757 ; 2008:22
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-18604Local ID: 964d5e20-2643-11dd-9e62-000ea68e967bOAI: oai:DiVA.org:ltu-18604DiVA: diva2:991613
Note
Godkänd; 2008; 20080520 (ysko)Available from: 2016-09-29 Created: 2016-09-29Bibliographically approved

Open Access in DiVA

fulltext(334 kB)6 downloads
File information
File name FULLTEXT01.pdfFile size 334 kBChecksum SHA-512
9fb52190f95cf920a31ae8da916ac15d48b146008d79b981664d5823265ac1bd693a66c5c619f582042c1832f632847b1270cbf6f40bad3342465ace4783a84f
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Jonsson, Peter A.
By organisation
Embedded Internet Systems Lab

Search outside of DiVA

GoogleGoogle Scholar
Total: 6 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 2 hits
ReferencesLink to record
Permanent link

Direct link