Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Time- and size-efficient supercompilation
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
2011 (English)Doctoral 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. Supercompilation 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 supercompilation algorithms that remove intermediate structures for languages with call-by-name semantics, no investigations have been performed for 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 positive supercompilation algorithms for higher-order call-by-value and callby-name languages that preserves termination properties of the programs they optimize. We prove the call-by-value 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.We also suggest to speculatively supercompile expressions and discard the result if it turned out bad. To test this approach we implemented the call-by-name algorithm in GHC and performed measurements on the standard nofib benchmark suite. We manage to supercompile large parts of the imaginary and spectral parts of nofib in a matter of seconds while keeping the binary size increase below 5%.Our algorithms are 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, 2011. , 104 p.
Series
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-26651Local ID: f5b79e9f-9a0d-4f34-8a25-7060e4f37856ISBN: 978-91-7439-241-8 (print)OAI: oai:DiVA.org:ltu-26651DiVA: diva2:999818
Projects
ESIS
Note
Godkänd; 2011; 20110330 (pj); DISPUTATION Opponent: Professor Taha Walid, Sektionen för Informationsvetenskap, data- och elektroteknik, Högskolan i Halmstad Ordförande: Professor Per Lindgren, Institutionen för system- och rymdteknik, Luleå tekniska universitet Tid: Onsdag den 27 april 2011, kl 13.00 Plats: E243, Luleå tekniska universitetAvailable from: 2016-09-30 Created: 2016-09-30 Last updated: 2017-11-24Bibliographically approved

Open Access in DiVA

fulltext(524 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 524 kBChecksum SHA-512
e9ef0bd1281f2c5ebb71f72cca851c2afd5209526c7045b437588127b45d057891cc049a49392db776ad3b094992080be133849f6892fd39dfdbfaa4aaade1b0
Type fulltextMimetype application/pdf

Authority records BETA

Jonsson, Peter A.

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 47 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf