Strictification of circular programs

João Paulo Fernandes; João Saraiva; Daniel Seidel; Janis Voigtländer

doi:10.1145/1929501.1929526

Strictification of circular programs

João Paulo Fernandes, João Saraiva, Daniel Seidel, Janis Voigtländer

Computer Science

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

Abstract

Circular functional programs (necessarily evaluated lazily) have been used as algorithmic tools, as attribute grammar implementations, and as target for program transformation techniques. Classically, Richard Bird [1984] showed how to transform certain multi-traversal programs (which could be evaluated strictly or lazily) into one-traversal ones using circular bindings. Can we go the other way, even for programs that are not in the image of his technique? That is the question we pursue in this paper. We develop an approach that on the one hand lets us deal with typical examples corresponding to attribute grammars, but on the other hand also helps to derive new algorithms for problems not previously in reach.

Original language	English (US)
Title of host publication	PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation
Pages	131-140
Number of pages	10
DOIs	https://doi.org/10.1145/1929501.1929526
State	Published - 2011
Event	20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM'11 - Austin, TX, United States Duration: Jan 24 2011 → Jan 24 2011

Publication series

Name	PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

Conference

Conference	20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM'11
Country/Territory	United States
City	Austin, TX
Period	1/24/11 → 1/24/11

Keywords

Program transformation

ASJC Scopus subject areas

Computer Graphics and Computer-Aided Design
Computer Science Applications

Access to Document

10.1145/1929501.1929526

Cite this

Fernandes, J. P., Saraiva, J., Seidel, D., & Voigtländer, J. (2011). Strictification of circular programs. In PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (pp. 131-140). (PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation). https://doi.org/10.1145/1929501.1929526

Strictification of circular programs. / Fernandes, João Paulo; Saraiva, João; Seidel, Daniel et al.
PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. 2011. p. 131-140 (PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation).

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

Fernandes, JP, Saraiva, J, Seidel, D & Voigtländer, J 2011, Strictification of circular programs. in PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, pp. 131-140, 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM'11, Austin, TX, United States, 1/24/11. https://doi.org/10.1145/1929501.1929526

@inproceedings{774898d414894115adda4915b4c68749,

title = "Strictification of circular programs",

abstract = "Circular functional programs (necessarily evaluated lazily) have been used as algorithmic tools, as attribute grammar implementations, and as target for program transformation techniques. Classically, Richard Bird [1984] showed how to transform certain multi-traversal programs (which could be evaluated strictly or lazily) into one-traversal ones using circular bindings. Can we go the other way, even for programs that are not in the image of his technique? That is the question we pursue in this paper. We develop an approach that on the one hand lets us deal with typical examples corresponding to attribute grammars, but on the other hand also helps to derive new algorithms for problems not previously in reach.",

keywords = "Program transformation",

author = "Fernandes, {Jo{\~a}o Paulo} and Jo{\~a}o Saraiva and Daniel Seidel and Janis Voigtl{\"a}nder",

year = "2011",

doi = "10.1145/1929501.1929526",

language = "English (US)",

isbn = "9781450304856",

series = "PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation",

pages = "131--140",

booktitle = "PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation",

note = "20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM'11 ; Conference date: 24-01-2011 Through 24-01-2011",

}

TY - GEN

T1 - Strictification of circular programs

AU - Fernandes, João Paulo

AU - Saraiva, João

AU - Seidel, Daniel

AU - Voigtländer, Janis

PY - 2011

Y1 - 2011

N2 - Circular functional programs (necessarily evaluated lazily) have been used as algorithmic tools, as attribute grammar implementations, and as target for program transformation techniques. Classically, Richard Bird [1984] showed how to transform certain multi-traversal programs (which could be evaluated strictly or lazily) into one-traversal ones using circular bindings. Can we go the other way, even for programs that are not in the image of his technique? That is the question we pursue in this paper. We develop an approach that on the one hand lets us deal with typical examples corresponding to attribute grammars, but on the other hand also helps to derive new algorithms for problems not previously in reach.

AB - Circular functional programs (necessarily evaluated lazily) have been used as algorithmic tools, as attribute grammar implementations, and as target for program transformation techniques. Classically, Richard Bird [1984] showed how to transform certain multi-traversal programs (which could be evaluated strictly or lazily) into one-traversal ones using circular bindings. Can we go the other way, even for programs that are not in the image of his technique? That is the question we pursue in this paper. We develop an approach that on the one hand lets us deal with typical examples corresponding to attribute grammars, but on the other hand also helps to derive new algorithms for problems not previously in reach.

KW - Program transformation

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

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

U2 - 10.1145/1929501.1929526

DO - 10.1145/1929501.1929526

M3 - Conference contribution

AN - SCOPUS:79952128136

SN - 9781450304856

T3 - PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

SP - 131

EP - 140

BT - PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation

T2 - 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM'11

Y2 - 24 January 2011 through 24 January 2011

ER -

Strictification of circular programs

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this