Theory of Linear Equations Applied to Program Transformation

Abstract

In this paper is presented a technique for transforming a class of recursive equations called linear equations into iterative equations. Linear equations are characterized by involving at the most one recursive call for any invocation. In contrast to the conventional techniques, the scheme of program transformation presented here involves finding the solution of the given linear equation and transforming this solution. The solutions of linear equations can always be expressed using a construct called abstract sequence. Two classes of abstract sequence programs are identified: right-associative and left-associative sequence programs. The former are obtained by solving linear equations and the latter correspond to iterative programs. The task of transforming linear recursive programs into iterative programs is thus reduced to the task of transforming right-associative sequence programs into left associative ones. Various transformation rules are developed based on an algebra of functional programs.