APL-to-Fortran translators

Abstract

The present invention relates to apparatus and method for translating computer programs in an application from an array source language--having attributes of APL--to a scalar target language. In particular, source language primitive functions--which can be used in different cases--are represented by archetypes having code that is selectable based on applicable case(s). In determining which case (or cases) applies, each program is re-structured into a sequence of simple source language expressions and a static analysis is performed. The static analysis, which includes a shape analysis of arrays in a program, provides information useful in determining cases for archetypes and for determining whether code generated for a particular simple expression may be beneficially merged with code generated for another simple expression. In one embodiment, the source language is translated to target language code which is, in turn, compiled by a target language compiler, thereby providing a two-step source language compiler.

We claim: 
     
       1. A machine-implemented method of translating to a target computer language an application programmed in a source computer language wherein said source language is characterized by (A) having arrays as primitive objects thereof,   (B) primitive functions which are applicable to arrays,   (C) primitive functions in which internal representations are inferred from use, and   (D) primitive functions which are applied differently in different cases depending upon differences in the rank, type, and shape information applicable to the arrays, the method comprising the steps of: (a) providing, for a subject primitive function of said source language which is applied differently in different cases, an archetype which includes (i) plural portions of code, which represent code in said target language, said portions being associated with corresponding cases in which the subject primitive function may be used, and   (ii) conditions for determining which of said plural portions of archetype code are to be used for a given occurrence of the subject primitive function in a given application program in said source language with at least some of the conditions being dependent on array shapes,       (b) storing said archetype in a machine memory, and   (c) translating said subject primitive function from said source to said target language using said stored archetype, by selecting at least one of said portions of code therefrom in accordance with said conditions applicable to said given application program, when said given application program in said source language is input to a computer as the object of translation, to produce a translated application program in said target language.   
     
     
       2. The method of claim 1 comprising the further step of: (d) unrolling expressions in an archetype to repeat operations defined thereby for array ranks.   
     
     
       3. The method of claim 1 comprising the further steps of: (d) sectioning code of said given application program in said source language into individual programs, each said individual program including a defined source language function and all functions called by said defined source language function; and   (e) determining which of said individual programs are translatable with reference to their compilability in said target language; and   (f) translating said source language with the individual program representing the unit of translation.   
     
     
       4. The method of claim 3, comprising the further steps of: pre-selecting programs the user wants translated;   and applying step (e) to only the preselected programs.   
     
     
       5. The method of claim 3 comprising the further steps of: (g) re-structuring the code of a subject program into a sequence of simple expressions in said source language; and   (h) performing a static analysis which includes the steps of deriving rank and variable storage-type information for data objects in the re-structured code and analyzing the shapes of arrays in the re-structured code, said shape analysis including the steps of: (i) for each subject array in the subject program, assigning independent variables to all elements of the shape of the subject array and to all elements of arrays containing shape information about the subject array;   (ii) evaluating expressions that perform shape calculations;   (iii) determining classes of arrays having the same shape;   (iv) selecting, for each class of arrays having the same shape, a representative variable; and   (v) constructing a simple expression associated with the representative variable.     
     
     
       6. The method of claim 5 wherein the shape analysis includes the further step of: inferring, from pairs of variables, when the shape of one variable in a given pair is always (i) equal to or (ii) less than or equal to the shape of the other variable in the given pair.   
     
     
       7. The method of claim 6 comprising the further steps of: (j) forming a program list, wherein each called program follows the respective calling program thereof; and   (k) performing the static analysis of step (h) for each program in the order of the formed list.   
     
     
       8. The method of claim 5 wherein said representative variable selecting step includes the step of selecting the variable for that array of the class which is processed first in the program. 
     
     
       9. The method of claim 3 comprising the further steps of: (g) re-structuring the code of a subject program into a sequence of simple expression in said source language; and   (h) combining expressions in the re-structured code.   
     
     
       10. The method of claim 9 comprising the further steps of: (j) if a subject program is translatable, determining the applicable case for each simple expression in the restructured code;   (k) selecting archetype portions for the simple expressions based on the determined cases thereof; and   (l) combining, as appropriate, target language code corresponding to the selected portions of respective archetypes.   
     
     
       11. The method of claim 10 wherein the archetype storing step further includes the steps of: (m) for a given piece of target language code corresponding to an archetype for a given case, inserting a first symbol to identify a first portion of said given piece and a second symbol to identify a second portion of said given piece; and   wherein said first portion is to be applied in the event of merger in accordance with the steps of   moving the code for a given expression in the restructured code to all points of use thereof subject to the conditions that the given expression (i) has no substantial computational cost, (ii) has a result which does not appear in a subroutine header or a CALL statement, (iii) is the only setting of the result variable, and (iv) all arguments remain unchanged at all points where the result is used; and   merging a temporary variable expression in a subject basic block into the first simple expression in the subject basic block that uses the temporary variable, subject to the condition that subscripts in the temporary variable expression and in the first expression of use are consistent; and said second portion is to be applied in the event of partial merger in accordance with the steps of     emerging a non-temporary non-scalar variable expression in a specific basic block into the first simple expression in the specific basic block that uses the non-temporary non-scalar variable, subject to the condition that subscripts in the non-temporary variable expression and in the first expression that uses said non-temporary variable are consistent; and   combining expressions having the same shape into a common DO loop nest.   
     
     
       12. The method of claim 9 wherein the expression combining step includes the steps of: (j) moving the code for a given expression in the restructured code to all points of use thereof subject to the conditions that the given expression (i) has no substantial computational cost, (ii) has a result which does not appear in a subroutine header or a CALL statement, (iii) is the only setting of the result variable, and (iv) all arguments remain unchanged at all points where the result is used.   
     
     
       13. The method of claim 12 wherein the expression combining step includes the further steps of: (k) forming the re-structured code into basic blocks, a basic block being a sequence of statements in said source language starting with a label or branch statement and ending with a label or branch statement with no label or branch statement therebetween; and   (l) merging a temporary variable expression in a subject basic block into the first simple expression in the subject basic block that uses the temporary variable, subject to the condition that subscripts in the temporary variable expression and in the first expression of use are consistent.   
     
     
       14. The method of claim 13 wherein the expression combining step includes the further step of: (m) merging a non-temporary non-scalar variable expression in a specific basic block into the first simple expression in the specific basic block that uses the non-temporary non-scalar variable, subject to the condition that subscripts in the non-temporary variable expression and in the first expression that uses said non-temporary variable are consistent.   
     
     
       15. The method of claim 14 wherein the expression combining step comprises the further step of: (n) combining expressions having the same shape into a common DO loop nest.   
     
     
       16. The method of claim 15 comprising the further step of: (o) setting a variable to limit the degree of expression combining.   
     
     
       17. The method of claim 16 wherein the variable setting step includes the step of: (p) selecting respective values of the number of expressions permitted to be combined in at least one of the steps (j), (l), (m), and (n).   
     
     
       18. The method of claim 17 comprising the further steps of: (q) if a subject program is translatable, determining the applicable case for each simple expression in the restructured and combined code; and   (r) representing each simple expression in the translatable program by the target language code corresponding to the determined case for the archetype thereof.   
     
     
       19. The system of claim 12 wherein said expression combining means further comprises: means for forming the re-structured code into basic blocks, a basic block being a sequence of statements in said source language starting with a label or branch statement and ending with a label or branch statement with no label or branch statement therebetween; and   means for merging a temporary variable expression in a subject basic block into the first simple expression in the subject basic block that uses the temporary variable, subject to the condition that subscripts in the temporary variable expression and in the first expression of use are consistent.   
     
     
       20. The system of claim 19 wherein said expression combining means further comprises: means for merging a non-temporary non-scalar variable expression in a specific basic block into the first simple expression in the specific basic block that uses the non-temporary non-scalar variable, subject to the condition that subscripts in the non-temporary variable expression and in the first expression that uses said non-temporary variable are consistent.   
     
     
       21. The system of claim 20 wherein said expression combining means further comprises: means for combining expressions having the same shape into a common DO loop nest.   
     
     
       22. The system of claim 21 further comprising: means for setting a variable to limit the degree of expression combining.   
     
     
       23. The system of claim 22 wherein said variable setting means comprises: means for selecting respective values for the number of expressions permitted to be combined by at least one of the means in said expression combining means.   
     
     
       24. The system of claim 23 further comprising: means for determining the applicable case for each simple expression in the re-structured and combined code, if a subject program is translatable; and   means for representing each simple expression in the translatable program by the target language code correspond to the determined case for the archetype thereof.   
     
     
       25. A system for translating to a target computer language an application programmed in a source computer language wherein said source language is characterized by: (A) having arrays as primitive objects thereof;   (B) primitive functions which are applicable to arrays;   (C) primitive functions in which internal representations are inferred from use; and   (D) primitive functions which are applied differently in different cases depending upon differences in the rank, type, and shape information applicable to the arrays, the system comprising: means for providing, for a subject primitive function of said source language which is applied differently in different cases, an archetype which includes:   (a) plural portions of code, which represent code in said target language, said portions being associated with corresponding cases in which the subject primitive function may be used; and   (b) conditions for determining which of said plural portions of archetype code are to be used for a given occurrence of the subject primitive function in a given application program in said source to said source lanuage with at least some of the conditions being dependent on array shapes; means for storing said archetypes in a machine memory; and     means for translating said subject primitive function from said source to said target language using said stored archetype, by selecting at least one of said portions of code therefrom in accordance with said conditions applicable to said given application program, when said given application program in said source language is input to a computer as the object of translation, to produce a translated application program in said target language.   
     
     
       26. The system of claim 25 further comprising: means for unrolling expressions in an archetype to repeat operations defined thereby for array ranks.   
     
     
       27. The system of claim 25 further comprising: means for sectioning code of said given application program in said source language into individual programs, each said individual program including a defined source language function and all functions called said defined source language function;   means for determining which of said individual programs are translatable with reference to their compilability in said target language; and   means for translating said source language with the individual program representing the use of translation.   
     
     
       28. The system of claim 27, further comprising: means for pre-selecting programs the user wants translated; and   means for applying said determining means to only the preselected program.   
     
     
       29. The system of claim 27 further comprising: means for re-structuring the code of a subject program into a sequence of simple expressions in said source language; and   means for performing a static analysis including:   means for deriving rank and variable storage-type information for data objects in the re-structured code; and   means for analyzing the shapes of arrays in the re-structured code, said shape analysis including: (i) for each subject array in the subject program, assigning independent variables to all elements of the shape of the subject array and to all elements of arrays containing shape information about the subject array;   (ii) evaluating expressions that perform shape calculations;   (iii) determining classes of arrays having the same shape;   (iv) selecting, for each class of arrays having the same shape, a representative variable; and   (v) constructing a simple expression associated with the representative variable.     
     
     
       30. The system of claim 29 wherein said means for analyzing the shapes of arrays in the re-structured code comprises: means for selecting said representative variables; and   means for selecting the variable for that array of the class which is processed first in the program.   
     
     
       31. The system of claim 29 wherein said shape analysis means further comprises: means for inferring, from pairs of variables, when the shape of one variable in a given pair is always (i) equal to or (ii) less than or equal to the shape of the other variable in the given pair. 
     
     
       32. The system of claim 31 further comprising: means for forming a program list, wherein each called program follows the respective calling program therefor; and   means for actuating said static analysis means to perform said static analysis for each program in the order of the formed list.   
     
     
       33. The system of claim 27 further comprising: means for re-structuring the code of a subject program into a sequence of simple expressions in said source language; and   means for combining expressions in the re-structured code.   
     
     
       34. The system of claim 33 wherein said expression combining means comprises: means for moving the code for a given expression in the restructured code to all points of use thereof subject to the conditions that the given expression (i) has no substantial computational cost, (ii) has a result which does not appear in a subroutine header or a CALL statement, (iii) is the only setting of the result variable, and (iv) all arguments remain unchanged at all points where the result is used.   
     
     
       35. The system of claim 33 further comprising: means for determining the applicable case for each simple expression in the re-structured code, if a subject program is translatable;   means for selecting archetype portions for the simple expressions based on the determined cases thereof; and   means for combining, as appropriate, target language code corresponding to the selected portions of respective archetypes.   
     
     
       36. The system of claim 35 wherein said archetype storing means further comprises: means, for a given piece of target language code corresponding to an archetype for a given case, for inserting a first symbol to identify a first portion of said given piece and a second symbol to identify a second portion of said given piece; and   means for applying said first portion in the event of merger in accordance with the operations of said moving means of claim 34 and said merging means of claim 19, and for applying said second portion in the event of partial merger in accordance with the operation of said merging means of claim 20 and said combining means of claim 21.