Multiple intermediate structure deforestation by shortcut fusion

Alberto Pardo; João Paulo Fernandes; João Saraiva

doi:10.1007/978-3-642-40922-6_9

Multiple intermediate structure deforestation by shortcut fusion

Alberto Pardo, João Paulo Fernandes, João Saraiva

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Shortcut fusion is a well-known optimization technique for functional programs. Its aim is to transform multi-pass algorithms into single pass ones, achieving deforestation of the intermediate structures that multi-pass algorithms need to construct. Shortcut fusion has already been extended in several ways. It can be applied to monadic programs, maintaining the global effects, and also to obtain circular and higher-order programs. The techniques proposed so far, however, only consider programs defined as the composition of a single producer with a single consumer. In this paper, we analyse shortcut fusion laws to deal with programs consisting of an arbitrary number of function compositions.

Original language	English (US)
Title of host publication	Programming Languages - 17th Brazilian Symposium, SBLP 2013, Proceedings
Publisher	Springer Verlag
Pages	120-134
Number of pages	15
ISBN (Print)	9783642409219
DOIs	https://doi.org/10.1007/978-3-642-40922-6_9
State	Published - 2013
Event	17th Brazilian Symposium on Programming Languages, SBLP 2013 - Brasilia, Brazil Duration: Oct 3 2013 → Oct 4 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8129 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th Brazilian Symposium on Programming Languages, SBLP 2013
Country/Territory	Brazil
City	Brasilia
Period	10/3/13 → 10/4/13

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-40922-6_9

Cite this

Pardo, A., Fernandes, J. P., & Saraiva, J. (2013). Multiple intermediate structure deforestation by shortcut fusion. In Programming Languages - 17th Brazilian Symposium, SBLP 2013, Proceedings (pp. 120-134). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8129 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-40922-6_9

Multiple intermediate structure deforestation by shortcut fusion. / Pardo, Alberto; Fernandes, João Paulo; Saraiva, João.
Programming Languages - 17th Brazilian Symposium, SBLP 2013, Proceedings. Springer Verlag, 2013. p. 120-134 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8129 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Pardo, A, Fernandes, JP & Saraiva, J 2013, Multiple intermediate structure deforestation by shortcut fusion. in Programming Languages - 17th Brazilian Symposium, SBLP 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8129 LNCS, Springer Verlag, pp. 120-134, 17th Brazilian Symposium on Programming Languages, SBLP 2013, Brasilia, Brazil, 10/3/13. https://doi.org/10.1007/978-3-642-40922-6_9

Pardo A, Fernandes JP, Saraiva J. Multiple intermediate structure deforestation by shortcut fusion. In Programming Languages - 17th Brazilian Symposium, SBLP 2013, Proceedings. Springer Verlag. 2013. p. 120-134. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40922-6_9

Pardo, Alberto ; Fernandes, João Paulo ; Saraiva, João. / Multiple intermediate structure deforestation by shortcut fusion. Programming Languages - 17th Brazilian Symposium, SBLP 2013, Proceedings. Springer Verlag, 2013. pp. 120-134 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ca4e0008862549aba1977dd47accf4f7,

title = "Multiple intermediate structure deforestation by shortcut fusion",

abstract = "Shortcut fusion is a well-known optimization technique for functional programs. Its aim is to transform multi-pass algorithms into single pass ones, achieving deforestation of the intermediate structures that multi-pass algorithms need to construct. Shortcut fusion has already been extended in several ways. It can be applied to monadic programs, maintaining the global effects, and also to obtain circular and higher-order programs. The techniques proposed so far, however, only consider programs defined as the composition of a single producer with a single consumer. In this paper, we analyse shortcut fusion laws to deal with programs consisting of an arbitrary number of function compositions.",

author = "Alberto Pardo and Fernandes, {Jo{\~a}o Paulo} and Jo{\~a}o Saraiva",

year = "2013",

doi = "10.1007/978-3-642-40922-6_9",

language = "English (US)",

isbn = "9783642409219",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "120--134",

booktitle = "Programming Languages - 17th Brazilian Symposium, SBLP 2013, Proceedings",

note = "17th Brazilian Symposium on Programming Languages, SBLP 2013 ; Conference date: 03-10-2013 Through 04-10-2013",

}

TY - GEN

T1 - Multiple intermediate structure deforestation by shortcut fusion

AU - Pardo, Alberto

AU - Fernandes, João Paulo

AU - Saraiva, João

PY - 2013

Y1 - 2013

N2 - Shortcut fusion is a well-known optimization technique for functional programs. Its aim is to transform multi-pass algorithms into single pass ones, achieving deforestation of the intermediate structures that multi-pass algorithms need to construct. Shortcut fusion has already been extended in several ways. It can be applied to monadic programs, maintaining the global effects, and also to obtain circular and higher-order programs. The techniques proposed so far, however, only consider programs defined as the composition of a single producer with a single consumer. In this paper, we analyse shortcut fusion laws to deal with programs consisting of an arbitrary number of function compositions.

AB - Shortcut fusion is a well-known optimization technique for functional programs. Its aim is to transform multi-pass algorithms into single pass ones, achieving deforestation of the intermediate structures that multi-pass algorithms need to construct. Shortcut fusion has already been extended in several ways. It can be applied to monadic programs, maintaining the global effects, and also to obtain circular and higher-order programs. The techniques proposed so far, however, only consider programs defined as the composition of a single producer with a single consumer. In this paper, we analyse shortcut fusion laws to deal with programs consisting of an arbitrary number of function compositions.

UR - http://www.scopus.com/inward/record.url?scp=84887440528&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887440528&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40922-6_9

DO - 10.1007/978-3-642-40922-6_9

M3 - Conference contribution

AN - SCOPUS:84887440528

SN - 9783642409219

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 120

EP - 134

BT - Programming Languages - 17th Brazilian Symposium, SBLP 2013, Proceedings

PB - Springer Verlag

T2 - 17th Brazilian Symposium on Programming Languages, SBLP 2013

Y2 - 3 October 2013 through 4 October 2013

ER -

Multiple intermediate structure deforestation by shortcut fusion

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this