Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-08-03
2001-03-06
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06199201
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the technique of compiling software, particularly source code, according to the techniques known as “early evaluation” or “partial evaluation.” More specifically, the present invention relates to novel software constructs that are superimposed on source code by a programmer to facilitate efficient partial evaluation.
BACKGROUND OF THE INVENTION
In computer science, there is a well-known basic dichotomy between whether a given quantity of code in a single program is executed at compilation time or at runtime. Whether individual steps in the code are executed at runtime or compilation time will have a significant effect on the overall efficiency of the code. Speaking very generally, to have certain operations occur at runtime makes for an appealingly simple code, but code that requires too many operations, such as table look-ups, at runtime will take orders of magnitude longer than an implementation which can perform some look-ups at compilation time. This is particularly true of library or middleware, that can be seen as providing a special-purpose language for doing certain kinds of operation (i.e., an image processing library can be seen as a special language for doing image processing). Most of the relative inefficiency comes from the inability of library code to make effective use of information available to users of the library; information that could be exploited at compilation time gets repeatedly rediscovered at runtime.
In order to overcome the problem of deciding whether the particular portions of a computer program should be executed at compilation time or runtime, one technique which has been developed recently is called “partial evaluation.” An overview of partial evaluation can be found in the first three chapters of Ruf, “Topics in Online Partial Evaluation,” (Ph.D. thesis, Stanford University, 1993). The Ruf dissertation basically describes an automatic program, called a “specializer,” which operates in conjunction with a compiler: the specializer looks at codes submitted thereto, and makes an automatic inference, based on what information is known at a particular time, whether to “specialize” various portions of the program at partial evaluation time. Basically, if the specializer determines that it has enough information to specialize a particular input of the original program at partial evaluation time, and it judges that such specialization will be worthwhile, it does so. The overall output of the specializer is a new, specialized program which, when applied to any input satisfying the description, computes the same result as the original program. However, because the specialized program performed certain computations at partial evaluation time, the specialized program runs faster than the original program did.
Although a specializer as disclosed in the Ruf dissertation makes some progress in optimizing the execution of complicated programs, the practical applicability of partial evaluation has proven to be quite limited. It remains difficult to develop code that is highly efficient for purposes of partial evaluation, and all but impossible to make such code also easy to maintain.
The present invention takes an approach different from the attempt at total automation of partial evaluation, such as described in the Ruf dissertation. The present invention posits an arrangement whereby the programmer originating code has available to him certain software constructs which are read by a “partial evaluator,” which is in effect a pre-compiler, which gives the programmer direct control over the execution time of different parts of the original program. The constructs of the present invention allow a programmer authoring a program to declare at individual call sites within the original program whether the code associated with a particular construct should be executed at runtime or at partial evaluation time.
DESCRIPTION OF THE PRIOR ART
In the prior art, U.S. Pat. No. 5,535,392 discloses a system for compiling a source program using what is called “smart” recompilation. Fragments of the source code are allowed to contain “invocation specific” information, which is generated during a coded generation phase of compilation. A hint generator attempts to preserve values of the invocation specific information between successive invocations of the compiler.
U.S. Pat. No. 5,583,988 discloses a method for performing runtime checking during program execution in a compiled environment. The invention detects a number of errors during runtime that cannot be found by a compiler at the precise moment that a respective C language restriction is violated. The invention provides the human user with a direct indication of the problem, thus saving debugging time. When source code is compiled, the invention allocates special data structures for every pointer, array, and structure object in the program. An association is made between each of these objects and its special data structure in a compiler symbol table. At runtime, these data structures contain status information about their associated objects.
U.S. Pat. No. 5,625,822 discloses a system for compiling a source program using “smart recompilation.” Fragments of executable code are allowed to contain “invocation specific” information, which is generated during a code generation phase of compilation. A hint generator attempts to preserve values of the invocation specific information between successive invocations of the compiler. Generally, the technique includes generating a first global context table generated from a previous version of the source program, the first global context table being divided into a first group of fragments, and generating a second global context table from the source program to be recompiled, the second global context table being divided into a second group of fragments. A comparison function is used to search the sorted tables to identify fragments that may be equivalent.
U.S. Pat. No. 5,632,033 discloses a system for dynamic, runtime alteration of preset variable space relationships by a runtime GUI modification of object connections associated with the variable spaces. Arbitrary linkages between all variable spaces are established prior to runtime to allow initial conditions for variable resolution irrespective of anticipated or actual object connections. Thus, all variables associated with objects are prespecified and provided with initial values, so long as a value has been assigned to the variable in some object. When actual object relationships are indicated at runtime, these effect new variable space linkages. The initial and subsequent linkages are effected with pointer addresses within the respective variable spaces.
The dissertation by Ruf, “Topics in Online Partial Evaluation,” (Ph.D. Thesis Stanford University, 1993) has been described in detail above.
An annotation mechanism called “filters” is presented in the paper “New insights into partial evaluation: the Schism experiment,” by C. Consel, presented at the European Symposium on Programming, 1988, and published as volume 300 of Lecture Notes in Computer Science, pages 236-246, by Springer-Verlag. The filter mechanism allows a programmer to annotate a procedure to indicate under what circumstances it should be specialized and what arguments should be used to specialize the function.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, there is provided a method of processing a computer program, the program having a procedure therein. There is provided in the program a language construct that specifies that a specialization of the procedure should be created at a point of use of the procedure.
According to another aspect of the present invention, there is provided a method of processing a computer program. There is provided in the program a language construct that specifies that a computation associated with the language construct should be carried out before the program is run. The program is submitted to a partial evaluator before the program is compiled. The part
Dixon Michael D.
Kiczales Gregor J.
Lamping John O.
Smith Brian C.
Das Chameli C.
Hutter R.
Powell Mark R.
Xerox Corporation
LandOfFree
Software constructs that facilitate partial evaluation of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Software constructs that facilitate partial evaluation of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Software constructs that facilitate partial evaluation of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444217