Theory of Linear Equations Applied to Program Transformation

Abstract

In this pap er is presented a tec hniqu e for transforming a class of recursive equations ca lled linear equations into iterativ e 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 lin ea r equations can always be expressed using a construct called abstract sequence. Two classe s of abstract sequence programs a re identified: right-associative and left-a ssociative sequence programs. The former are obtained by solving linear equations and the latter correspond to it e rative programs . The task of transforming linear recursive programs into iterative programs is thus reduced to the task of transforming right-associativ e se quence programs into left-associative ones. Variou s tran sfo rmation rules are developed based on an algebra of functional programs.