Browse Prior Art Database

THE IRVINE PROGRAM TRANSFORMATION CATALOGUE: A Stock of Ideas for Improving Programs Using Source-to-Source Transformations

IP.com Disclosure Number: IPCOM000128331D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 37 page(s) / 76K

Publishing Venue

Software Patent Institute

Related People

T.A.Standish: AUTHOR [+6]

Abstract

The Irvine Program Transformation Catalogue is basically a source book of ideas for improving programs. By casual-browsing, the reader may discover a number of useful techniques for transforming programs into better ones. When the moment comes to apply a particular technique, the Catalogue can be referenced for details. The ideas are presented in the.form of source-to-source transformations. These transformations show how to change source language programs in a given form into improved source language programs. Many of the transformations are given as rules of exchange of the form P = Q. This is intended to follow conventional usage in mathematics. For example,.in algebra, we might find the distributive law given in a form such as x ( y + z xy + xz, in logic, we might find a simplification law given as b A(b v c) = b, and in a table of integrals, we might find a rule such as f u dv = uv - fv du Each of these exchange laws,can be used to replace a given expression with an equivalent one. In a similar vein, we can specify exchange rules for expressions used in computer programs. For instance, we might give a distributive rule involving conditional expressions, such as [Equation ommitted] To specify that a given exchange rule is intended for use in a preferred direction, we write [Equation ommitted] For example, writing [Equation ommitted] signifies our preference for replacing the more complex expression [Equation ommitted] with the simpler expression b, where possible.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 37

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE IRVINE PROGRAM TRANSFORMATION CATALOGUE: A Stock of Ideas for Improving Programs Using Source-to-Source Transformations

T.A.Standish., D.C.Harriman, D.F.KibZer, and J.M.Neighbors Department of Information and Conputer Science University of CaZifornia at Irvine Irvine, CaZifornia 92717

:Research Supported by

THE NATIONAL SCIENCE FOUNDATION

under Grant DCR75-13875

January 7, 1976

4.5 Loop-Form Transformations [3-3-37]-

4.5.1 Loop Fusion [331

4.5.2 Loop Doubling [34]

4.5.3 Loop Case Splitting [341

4.5.4 Loop Unrolling [34-35)

4.5.5 Removal of Invariants [35]

4.5.6 Reduction in Operator Strength [35-36]

4.5.7 Test Replacement and Removals 136]

4.5.8 Nested Loop Simplifications [36-371

5. Compound Statements and Blocks [37-391 5.1 Eliminating Redundant Begin.-End Pairs [37]
5.2 Statement Fusions [38-391 5.2.1 Forward Fusions with Conditionals 1381 5.2.2 Backward Fusions with Conditionals [38] 5.2.3 Fusion of Conditionals without Else Clauses [38] 5.2.4 Nested Conditional Introduction 138] 5..3 Using Block Structure to Save Temporary Space [39]

6. Declarations [40-43] 6.1 Eliminating Useless Declarations 1401 6.2 Shifting Array Bounds f40-411 6.3 Reduction in Array Dimension'by Change of Declaration and Accessing [41-431 6.4 Fusion of Independent Modules into a Common Program with Suitable Sytematic Renaming
[43]

7. Procedures [44-53] 7.1 Eliminating Calls 144~-53] 7.1.1 Suitable Sytematic Renaming [44-50]
7.1.2 Partial Evaluation [51-53]

8. The Mechanics of the Empty and Undefined Program Forms [53-57] 8.1 Empty Introduction and Elimination [53-55] 8.2 Undefined Introduction and Elimination 155-57]

University of California, Irvine Page 1 Dec 31, 1976

Page 2 of 37

THE IRVINE PROGRAM TRANSFORMATION CATALOGUE: A Stock of Ideas for Improving Programs Using Source-to-Source

Transformations

9. High-Level Forms [58-631 9.1 Reduction versus Recognition [58-59] 9.2 Reductions for 9.2.1 Parallel Assignments ['59-60] 9.2.2 Iterators [60-621 9.2.3 Zahn and Dahl Loops [62-631

10. High Level Transforms [64

10.1 Eliminating Search Exhaustion Tests by Data Structure Extension [64]

10.2 Recursion Removal 164-66]

10.3 Refinement of Abstract Data Structures [66-691

10.4 Replacing Loops that Sum Polynomials with Polynomials of Higher Degree [69-701 ]0.5 Procedural Abstraction [70-71]

11. Manipulation of Expressions [71-77]

11.1 Arithmetic Expressions [71-74]

11,2 Relational Expressions 174-75]

11.3 Boolean Expressions [75-77]

12, Appendices [78-811

12.1 Notational Conventions 178-79]

12.2 Programming Language Forms [79-811

13. References 182]

Introduction

The Irvine Program Transformation Catalogue is basically a source book of ideas for improving programs. By casual-browsing, the reader may discover a number of useful techniques for transforming programs into better ones. When the moment comes to apply a particular technique, the Catalogue can be referenced for details.

The ideas are pr...