Loading...
Please wait, while we are loading the content...
Similar Documents
From Recursion to Iteration: What Are the Optimizations? (2000)
| Content Provider | CiteSeerX |
|---|---|
| Author | Liu, Yanhong A. Stoller, Scott D. |
| Description | In Proceedings of the ACM SIGPLAN 2000 Workshop on Partial Evaluation and Semantics-Based Program Manipulation IN PROCEEDINGS OF THE ACM SIGPLAN 2000 WORKSHOP ON PARTIAL EVALUATION AND SEMANTICS-BASED PROGRAM MANIPULATION |
| Abstract | Transforming recursion into iteration eliminates the use of stack frames during program execution. It has been studied extensively. This paper describes a powerful and systematic method, based on incrementalization, for transforming general recursion into iteration: identify an input increment, derive an incremental version under the input increment, and form an iterative computation using the incremental version. Exploiting incrementalization yields iterative computation in a uniform way and also allows additional optimizations to be explored cleanly and applied systematically, in most cases yielding iterative programs that use constant additional space, reducing additional space usage asymptotically, and run much faster. We summarize major optimizations, complexity improvements, and performance measurements. |
| File Format | |
| Publisher Date | 2000-01-01 |
| Access Restriction | Open |
| Subject Keyword | Stack Frame Iterative Program Constant Additional Space Incremental Version Additional Optimization Complexity Improvement Incrementalization Yield Iterative Computation Additional Space Usage Uniform Way Input Increment Systematic Method Performance Measurement Program Execution General Recursion Major Optimization Iterative Computation |
| Content Type | Text |
| Resource Type | Proceeding Conference Proceedings Article |
