scientific article; zbMATH DE number 3960968

From MaRDI portal
Publication:3729997





[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.











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)