scientific article; zbMATH DE number 3960968
[For the entire collection see Zbl 0578.00007.] A functional program is subject to bounded evaluation (b.e.) if it can be evaluated in a fixed amount of space. Previous work [the author, ACM Symp. on Lisp and Functional programming (Austin/Tex. 1984) and Ph. D. Diss. (Carnegie-Mellon Univ. 1984)] gives an algorithm that transforms any b.e. program into a listless program (one that uses no intermediate lists), thereby improving efficiency. The source language has lazy evaluation semantics, but the transformed program does not require lazy evaluation. In this paper, the definition of b.e. is modified to require preorder traversal. This guarantees a rule of composition: if f and g are b.e. programs, then \(f\cdot g\) is also b.e. The rule of composition makes it easy to isolate portions of a program that are b.e., and a method is given to execute such portions efficiently. Finally, the preorder traversal is characterized using domain theory.
- Possibilities and limitations of call-by-need space improvement
- Generating function versions with rational strictness patterns
- More haste, less speed: lazy versus eager evaluation
- Formal efficiency analysis for tree transducer composition
- Using circular programs to eliminate multiple traversals of data
- Rules + strategies for transforming lazy functional logic programs
- Pruning with improving sequences in lazy functional programs
- To be or not to be …lazy (In a Parallel Context)
- The HOL-CSP Refinement Toolkit
- HOL-CSP Version 2.0
- A Sound Type System for Physical Quantities, Units, and Measurements
- Using circular programs to eliminate multiple traversals of data
- Deforestation: Transforming programs to eliminate trees
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3729997)