Using Circular Programs to Deforest in Accumulating Parameters Export

@article{voi04a, abstract = {This paper presents a functional program transformation that removes intermediate data structures in compositions of two members of a class of recursive functions with accumulating parameters. To avoid multiple traversals of the input data structure, the composition algorithm produces circular programs that make essential use of lazy evaluation and local recursion. The resulting programs are simplified using a post-processing phase sketched in the paper. The presented transformation, called lazy composition, is compared with related transformation techniques both on a qualitative level and based on runtime measurements. An alternative use of higher-orderedness instead of circularity is also briefly explored.}, author = {Voigtl\"{a}nder, Janis}, citeulike-article-id = {314116}, citeulike-linkout-0 = {http://www.metapress.com/content/T84439560Q771451}, citeulike-linkout-1 = {http://dx.doi.org/10.1023/B:LISP.0000029450.36668.cb}, citeulike-linkout-2 = {http://wwwtcs.inf.tu-dresden.de/~voigt/HOSC.pdf}, doi = {10.1023/B:LISP.0000029450.36668.cb}, journal = {Higher-Order and Symbolic Computation}, keywords = {accumulating-parameters, circular-programs, deforestation, functional-programming, haskell, laziness, lazy-evaluation, multiple-traversals, optimization, program-transformation, tree-transducers, tupling}, month = {March}, number = {1 - 2}, pages = {129--163}, posted-at = {2005-09-09 09:59:46}, priority = {0}, title = {Using Circular Programs to Deforest in Accumulating Parameters}, url = {http://dx.doi.org/10.1023/B:LISP.0000029450.36668.cb}, volume = {17}, year = {2004} }

TY - JOUR ID - voi04a L3 - citeulike-article-id:314116 N2 - This paper presents a functional program transformation that removes intermediate data structures in compositions of two members of a class of recursive functions with accumulating parameters. To avoid multiple traversals of the input data structure, the composition algorithm produces circular programs that make essential use of lazy evaluation and local recursion. The resulting programs are simplified using a post-processing phase sketched in the paper. The presented transformation, called lazy composition, is compared with related transformation techniques both on a qualitative level and based on runtime measurements. An alternative use of higher-orderedness instead of circularity is also briefly explored. IS - 1 - 2 JF - Higher-Order and Symbolic Computation EP - 163 TI - Using Circular Programs to Deforest in Accumulating Parameters VL - 17 SP - 129 KW - accumulating-parameters KW - circular-programs KW - deforestation KW - functional-programming KW - haskell KW - laziness KW - lazy-evaluation KW - multiple-traversals KW - optimization KW - program-transformation KW - tree-transducers KW - tupling AU - Voigtländer, Janis PY - 2004/03// UR - http://dx.doi.org/10.1023/B:LISP.0000029450.36668.cb ER -