Using circular programs to eliminate multiple traversals of data

DOI10.1007/BF00264249MaRDI QIDQ800713zbMATH OpenOpenAlexWikidataFDO

Authors Richard S. Bird

Publication date 1984

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00264249

zbMATH Keywords

lazy evaluationlocal recursiontransforming functional programs

Mathematics Subject Classification ID

Data structures (68P05) Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

This paper describes a technique for transforming functional programs that repeatedly traverse a data structure into more efficient alternatives that do not. The transformation makes essential use of lazy evaluation and local recursion (such as provided by letrec, or its equivalent) to build a circular program that, on one pass over the structure, determines the effects of the individual traversals and then combines them.

Recommendations

• Using circular programs to deforest in accumulating parameters
• Shortcut fusion rules for the derivation of circular and higher-order programs
• Partial parametrization eliminates multiple traversals of data structures
• Tupling calculation eliminates multiple data traversals
• scientific article; zbMATH DE number 3982557

Cites work

• A System for Assisting Program Transformation
• A Transformation System for Developing Recursive Programs
• DTL: A language for the design and implementation of concurrent programs as structured networks
• scientific article; zbMATH DE number 3960968 (Why is no real title available?)
• scientific article; zbMATH DE number 3664393 (Why is no real title available?)
• scientific article; zbMATH DE number 3557186 (Why is no real title available?)
• scientific article; zbMATH DE number 3631906 (Why is no real title available?)

Cited in

(21)

• Partial parametrization eliminates multiple traversals of data structures
• Efficient handling of data structures in definitional languages
• Lazy dynamic-programming can be eager
• A strict functional language with cyclic recursive data
• Using circular programs to deforest in accumulating parameters
• A transformation method for dynamic-sized tabulation
• Shortcut fusion rules for the derivation of circular and higher-order programs
• scientific article; zbMATH DE number 3960968 (Why is no real title available?)
• scientific article; zbMATH DE number 3982557 (Why is no real title available?)
• Attribute grammars as tree transducers over cyclic representations of infinite trees and their descriptional composition
• A positive supercompiler
• Traced Premonoidal Categories
• scientific article; zbMATH DE number 1738292 (Why is no real title available?)
• The resource constrained shortest path problem implemented in a lazy functional language
• scientific article; zbMATH DE number 7453187 (Why is no real title available?)
• Attribute grammars as recursion schemes over cyclic representations of zippers
• Linear, bounded, functional pretty-printing
• Tupling calculation eliminates multiple data traversals
• Manipulating accumulative functions by swapping call-time and return-time computations
• There and back again
• Breadth-first traversal via staging

This page was built for publication: Using circular programs to eliminate multiple traversals of data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800713)