Recursion Removal and Introduction Using Assignments

概要

論文の詳細を見る
Recurslye programs are often easy to write and reason about, while iterative ones are usually more effcient to execute. Transformation between recursire and iterative variants of a function is therefore important in order to enjoy the benefits of both programming styles. Recursion removal has been energetically researched for many years. In case of functions which consume a list and produce a list, however, recursion removal is not so straightforward without introduction of auxiliary stacks. We first define abstraction from constructors and some kinds of constructing functions, and propose a recursion removal method from constructing functions. This method produces tail-recursive programs from linear recursire functions with accumulation of abstracted expressions. With specialization using partial evaluation techniques, the interpretive overhead of constructor abstraction can be eliminated and fast execution is realized. This technique works not only for linear recursion but also for tree recursive functions or certain forms of nested functions. The idea of interpretation of abstracted construction enables not only recursion removal but also elimination of accumulating parameters. Transformed functions without accumulating parameters are executed in recursive manner, and recursion is introduced to such functions. This paper intends to present the way of these kinds of recursion removal and introduction as well as the representation of abstracted constructions which enables these program transformations.
一般社団法人情報処理学会の論文
2001-07-15

Recursion Removal and Introduction Using Assignments

スポンサーリンク

概要

著者

関連論文

スポンサーリンク