lll|||IllllllllllIllllllllllllllllllllllllllllllllllllllllllllllllIllllllll
`U3005590331A
`
`United States Patent
`
`:19]
`
`[11] Patent Number:
`
`5,590,331
`
`
`Dec. 31, 1996
`[45] Date of Patent:
`Lewis et a1.
`
`
`
`[54] METHOD AND APPARATUS FOR
`GENERATING PLATFORM-STANDARD
`OBJECT FILES CONTAINING
`MACI-DNE-INDEPENDENT CODE
`
`[75]
`
`Inventors: Brian '1‘. Lewis; Theodore C.
`Goldstein, both of Palo Alto, Calif.
`
`M. Franz, Programming Languages and System Architec—
`ture,
`Springer Verlag
`#782,
`(Mar.
`1994),
`ISBN
`068747840, pp. 1—26.
`Advertisement for Effie! Bench, by Interactive Software
`Engineering Inc.
`
`Primary firming—Kevin A. Kriess
`Assistant Exominer—Kakali Chaki
`
`[73] Assignec: Sun Microsystems, Inc., Mountain
`View, Calif.
`
`Attorney, Agent. or Finn—Blakely Sokoloff Taylor & Zaf—
`man LLP
`
`[21] Appl. No: 363,743
`
`[22]
`
`Filed:
`
`Dec. 23, 1994
`
`Int. Cl.6
`[51]
`............... GOISF 9:45
`
`[52] us. Cl.
`3951708
`[58] Field of Search
`395.500
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,672,532
`5,204,960
`5.230.617
`5.303.380
`5,339,419
`
`601987 JongeVos
`.
`411993 Smith at al.
`01994 Brender et a1.
`201994 Teeny et a1.
`8:1994 Chan eta].
`
`............... 3644000
`.. 3951700
`
`......
`395.000
`395000
`
`395n00
`
`OTHER PUBLICATIONS
`
`(Byte
`
`G. Krasner, The Smalltalk —80 Virtual Machine,
`Publications, ind, Aug. 1981), pp. 300-320.
`(CD—ROM)
`A. Padawcr, Mtcrosofi P—Code Technology,
`Microsoft Developer Network Development Library No. 8,
`Uni. 1994), pp. 1—? and 1—10.
`System V: Application Binary Interface, revised edition,
`UNIX System Laboratories, inc. (1992) pp. 4—1 to 4—33 and
`5—1 to 5~24.
`U. Holzle and D. Ungar, A Third—Generation SELF Imple—
`mentation: Reconciling Responsiveness with Perfomance,
`OOPSLA 1994 Conference Proceedings, Fenland, (Oct.
`1994), PP. 1-15.
`
`[57}
`
`ABSTRACT
`
`A method and apparatus for generating a platform-stardard
`object file containing machinedndependent abstract code.
`Source code which defines a procedure is convened into
`abstract code which makes no assumptions about the plat-
`form on which the procedure will be executed. An abstract
`code platform~standard object file is generated based on the
`abstract code. The abstract code platform-standard object
`file includes a list of definitions of any global variables
`defined in the abstract code, a list of symbol references
`indicative of any external variables or external procedures
`referenced in the abstract code, a sequence of machine
`instructions for calling an execution routine when a client
`calls the procedure, and the abstract code which defines the
`procedure. The abstract code is preferably compressed
`before it is stored in the abstract code platform-standard
`object file. When a program including the abstract code
`platform-standard object file is executed, it is dynamically
`linked to the execution routine. When the procedure is
`called,
`the execution routine is invoked. The execution
`routine executes the procedure by interpreting the abstract
`code or generating machine-code responsive to the abstract
`code. The execution routine may be an execution control
`unit which selects between various execution techniques
`based on runtime factors. such as the frequency with which
`the procedure is called.
`
`21 Claims, 9 Drawing Sheets
`
`UNABLE AESTMT CODE
`BONNER
`
`
`
`
`WSTPJCTODDE
`EXEOU‘I'IGN
`FICUI'INE
`
`213
`
`
`
`
`D‘J'HEFt CaiEC FILES
`
`Apple v. Realtime
`Proceeding No. |PR2016-01737
`APPLE 1033
`
`Apple v. Realtime
`Proceeding No. IPR2016-01737
`APPLE 1033
`
`1
`
`

`

`US. Patent
`
`Dec. 31, 1996
`
`Sheet 1 of 9
`
`5,590,331
`
`
`
`2
`
`

`

`US. Patent
`
`Dec. 31, 1996
`
`Sheet 2 of 9
`
`5,590,331
`
`SOURCE CODE
`
`200
`
`202
`
`SOURCE CODE CONVERTER (J
`
`ABSTRACT CODE
`
`204
`
`
`
`
`
`
`
`
`206
`LIN KABLE ABSTRACT CODE r’
`CONVERTER
`
`ABSTRACT CODE
`PLATFORM-SPECIFIC
`OBJECT FILE
`
`208
`
`(J
`
`
`
`
`STATIC LINKER
`
`
`
`EXECUTABLE FILE
`
`
`
`
`
`218
`
`
`ABSTRACT CODE
`EXECUTION
`ROUTINE
`
`DYNAMIC LINKER
`
`V
`
`
`
`219
`OTHER OBJECT FILES ”J
`
`PROCESS IMAGE
`
`220
`’J
`
`Fig. 2a
`
`3
`
`

`

`US. Patent
`
`Dec. 31, 1996
`
`Sheet 3 of 9
`
`5,590,331
`
`
`
`MAIN MEMORY M
`
`
`Source Code Converter
`Instructions
`I\J30
`
`Linkable Abstract Code Converter
`Instructions
`
`232
`
`Static Llnker Instructions
`
`134.
`
`Dynamic Lmker Instructions &
`
`
`
`
`
`Other Information
`
`14.9
`
`
`
`Bus
`
`
`
`
`
`
`Fig. 2b
`
`4
`
`

`

`US. Patent
`
`Dec. 31, 1996
`
`Sheet 4 of 9
`
`5,590,331
`
`SOURCE CODE
`
`ABSTRACT
`SEMANTIC
`
`ABSTRACT CODE
`
`ABSTRACT CODE
`GENERATOR
`
`Fig. 3a
`
`5
`
`

`

`US. Patent
`
`Dec. 31, 1996
`
`Sheet 5 of 9
`
`5,590,331
`
`LINKABLE ABSTRACT
`CODE CONVERTER
`
`'
`
`|
`
`GLOBAL VARIABLE
`PROCESSING UNIT
`
`EXTERNAL
`REFERENCE
`PROCESSING UNIT
`
`
`ABSTRACT CODE
`PLATFORM-SPECIFIC
`
`OBJECT FILE
`
`
`
`
`CALL ROUTINE
`GENERATION UNIT
`
`204
`
`
`
`ABSTRACT CODE
`
`
`
`
`ABSTRACT CODE
`ENCAPSULATING
`UNIT
`
`Fig. 3b
`
`6
`
`

`

`US. Patent
`
`Dec. 31, 1996
`
`Sheet 6 of 9
`
`5,590,331
`
`208
`
`/
`
`GLOBAL VARIABLE
`DEFINITIONS
`
` VARIABLE AND
`PROCEDURE REFERENCES
`
`
`
`
`
`
`MACHINE CODED
`ENTRY CODE
`
`
`
`/4
`
`
`OMFIES ED
`ABSTRACT
`
`ABSTRACT
`CODE
`PSOF
`
`MACHINE
`CODED
`PSOF
`
`MACHINE
`CODED
`PSOF
`
`ABSTRACT
`CODE
`
`MACHINE
`CODED
`PSOF
`
`
`I
`PSOF
`
`7
`
`

`

`US. Patent
`
`Dec. 31, 1996
`
`Sheet 7 of 9
`
`5,590,331
`
`EXECUHON
`ROUHNE
`
`
`
`
`
`MACHNE
`CODED
`PSOF
`
`mm
`
`
`
`EXECUNON
`CONTROL
`
`
`ROUHNE
`MACHNE
`
`CODE
`
`GENERATOR
`
`
`
`
`MACHINE
`CODED
`
`PSOF
`
`
`
`
`203
`214
`
`8
`
`

`

`US.
`
`Patent
`
`Dec. 31, 1996
`
`Sheet 8 of 9
`
`5,590,331
`
`_.
`
`CREATE EXECUTABLE
`FILE
`
`624
`
`
`STATICALLY LINK
`
`ABSTRACT CODE PSOF
`
`WITH OTHER PSOFS
`
`
`626
`
`
`
`
`RESOLVE EXTERNAL
`CALLS
`
`RESOLVE EXTERNAL
`GLOBAL REFERENCES
`
`
`
`
`
`
`DYNAMICALLY LINK
`EXECUTION ROUTINE TO
`EXECUTABLE FILE
`
`
`
`DYNAMICALLY LINK OTHER
`EXTERNALLY REFERENCED
`PROCEDURES TO EXECUTABLE
`FILE
`
`600
`
`I—CR—EATSAEST—RAC—TCCDE I
`608 I
`
`
`
`PARSE SOURCE
`
`
`CODE TO CREATE
`
`
`ABSTRACT SEMANTIC
`
`
`
`
`
`
`SENERATE ABSTRACT
`
`
`I CODE DATA STRUCTURES
`BASED ON ABSTRACT
`SEMANTIC GRAPH
`
`
`CREATE ABSTRACT
`CODE PSOF
`
`GENERATE GLOBAL
`VARIABLE DEFINITION
`SECTION
`
`
`
`GENERATE
`MACHINE-CODE!)
`ENTRY CODE
`
`GENERATE
`COMPRESSED
`ABSTRACT CODE
`SECTION
`
`COMPRESS
`ABSTRACT CODE
`
`ENCAPSULATE
`COMPRESSED
`ABSTRACT CODE IN
`
`9
`
`

`

`US. Patent
`
`Dec. 31, 1996
`
`Sheet 9 of 9
`
`5,590,331
`
`700
`
`EXECUTE
`MACHINE-CODED
`ENTRY CODE
`
`
`
`INVOKE
`EXECUTION ROUTINE
`
`701
`
`
` EXECUTED
`
`LESS THAN N
`
`
`TIMES ?
`
`
`NO
`
`DECOMPFIESS
`
`INVOKE INTERPRETEFI
`
`ROUTINE
`
`T10
`
`NO
`
`DECOMPRESS
`ABSTRACT CODE
`
`CAUSE
`EXECUTION
`T0 JUMP
`
`MACHINE CODE
`
`
`
`
`GENERATION
`ROUTINE
`
`JUMP TO PREOOMPILEO
`MACHINE CODE RESPONSIVE
`TO ABSTRACT CODE
`INSTRUCTIONS
`
`
`
`705
`
`GENERATE
`MACHINE CODE
`
`
`PROCEDURE
`
`RETURN To
`
`CALLING
`
`.
`
`F
`
`708
`
`10
`
`10
`
`

`

`1
`METHOD AND APPARATUS FOR
`GENERATING PLATFORM-STANDARD
`OBJECT FILES CONTAINING
`MACHINE-INDEPENDENT CODE
`
`FIELD OF THE INVENTION
`
`The present invention relates to software development
`tools and more particularly to an apparatus and method for
`encapsulating machine-independent software code into plat-
`form-standard object files.
`
`BACKGROUND OF THE INVENTION
`
`A computer platform consists of a computer system
`running a particular operating system. Not all computer
`platforms are compatible with each other. Specifically,
`instructions executable on one platform are often not execut-
`able on another. To allow execution on multiple platforms,
`software is often initially written in a “high level" language.
`High level
`languages include instructions (“high level
`instructions") that are more general than the instructions
`which are actually executed on a platform. Since high level
`instructions are generally not directly executable on any
`computer system, they must first be convened to machine-
`specific code that is directly executable on a specific target
`platform. Files
`containing high-level
`instructions
`are
`referred to herein as high-level software modules.
`Various programming approaches have been adopted for
`generating machine-specific programs based on high-level
`software modules. According to one approach, high—level
`software modules are first compiled into machine-specific
`object files by a compiler program. This approach is generv
`ally referred to herein as the pro-execution compilation
`approach. Typically, a given platform will have a standard
`format for machine—specific object files. Machine—specific
`object files which conform to the standard format of a given
`platform are referred to herein as platinum-standard object
`files {“PSOFs”). Because platform-standard object files for
`a particular platform have a standard format. a single pro-
`gram may combine platform-standard object files generated
`from high-level software modules originally written in more
`than one high-level programming language. For example, a
`single program may be created from a first platform-stan-
`dard object file compiled from a first high-level software
`module written in a first high-level programming language
`and a second platform-standard object file compiled from a
`second high-level software module written in a second
`high-level programming language.
`Once the platform-standard object files for a program
`have been compiled, they are linked together to create the
`program. A link between platfon'n—standard object files
`allows the platform—standard object fries to pass information
`to and invoke procedures defined within each other. The
`software modules may he linked statically (prior to program
`execution} or dynamically (during program execution).
`Since all platform-standard object files on a given platform
`have a standard format, a standard linker may be used to link
`the platform-standard object fries without regard to the
`high-level progranu‘ning language in which the correspond-
`ing high—level software modules were written.
`Software “libraries" and “Ioolkits” have been developed
`to allow programs to access particular functions. Typically,
`the functions are implemented in platfonn-standard object
`flies. Consequently,
`to access a library function within a
`program, a platform-standard object file of the program is
`
`It}
`
`15
`
`20
`
`25
`
`30
`
`35
`
`4D
`
`45
`
`50
`
`55
`
`65
`
`11
`
`5,590,331
`
`2
`
`simply linked to the toolkit platform—standard object file
`corresponding to the desired function.
`According to another approach, each instruction of a
`high-level software module is convened “on-thc-fly” into
`machine-specific code during program execution. This
`approach is generally referred to herein as the runtime
`compilation approach. Specifically, to execute a program
`represented in a high-level software module, the instructions
`contained in the high—level software module are read by a
`code—generator. The code generator converts the high-level
`instructions in the high-level software module into machine-
`specific instructions, and immediately sends the machine—
`specific instructions to a processor for execution.
`According to yet another approach, each instruction of a
`high-level software module is fed into an interpreter pro-
`gram during program execution. This approach is referred to
`herein as the interpreter approach. The interpreter program
`causes program execution to jump to a precornpiled block of
`machine-specific instructions corresponding to the current
`high-level
`instruction. Once the precompiled block of
`machine—specific instructions has been executed. the inter-
`preter program determines the next high-level instruction to
`interpret responsive to the execution of the previously
`executed machine—specific instructions.
`The execution speed, memory and resource requirements,
`error correction and maintenance ram—around time for a
`program depend in pan upon which of these program
`development approaches is used to generate the program.
`For example, code that is compiled prior to execution
`typically does not need to be linked to or distributed with
`interpreter or runtime code generation software. In addition.
`pro-compiled code generally executes faster than interpreted
`code because pre-compiled code does not have to share
`processing resources during execution with an interpreter or
`code generating process. However, code which has been
`completely compiled must be recompiled to incorporate
`even small changes. Compiled code also tends to be much
`larger than high-level instructions. Consequently, compiled
`code typically requires more storage space and more runlime
`resources.
`
`In contrast, code which is compiled or interpreted “on-
`the-fly" (“min—time converted code") is generally smaller
`and requires fewer runtime resources. In addition. when
`code which is compiled onwthe-fiy or interpreted on-the-fly
`is revised, the code does not have to be compiled prior to
`program execution. On-the-fly code conversion also allows
`additional checking code to be generated at runtime without
`recompiling the original source code. Also, nut-time con—
`vened code may be tailored for a particular execution
`environment. For example, different implementations of a
`single architecture may have slightly different instruction
`scheduling and delay properties. In one test, a sample
`program compiled for a first implementation of a given
`architecture ran 25% slower on a second implementation of
`the given architecture than the same program compiled for
`the second implementation. On-the-fiy code conversion
`allows the same pmgram representation to be used by both
`architectures with good performance properties on both. For
`another example, stub code tailored for a local object
`implementation is typically faster than generic stub code
`which handles both local and nonlocal object implementa—
`lion. However, whether an object will be locally imple~
`mented may not be known until run-time. Using on-the-fly
`code conversion.
`it may be determined that an object is
`locally implemented before the stub code is generated.
`Based on this run-time information, faster. less generic stub
`code may be generated.
`
`11
`
`

`

`3
`
`4
`
`5,590,331
`
`To realize the benefits of the various development
`approaches, hybrid programming environments have been
`developed. For example, systems have been developed
`which allow highvlevel software modules converted by
`on-the-fly code generators to call external platform—standard
`object files. The connections between the generated code
`and the external platform-standard object files are made by
`custom linkers. However, the custom linkers on some of the
`present hybrid systems do not allow external platform-
`standard object. files to “call back" to the high-level software
`module being translated. Because call-backs are not sup-
`ported,
`information only flows one way. Unfortunately,
`many platform-standard object files require two-way com-
`munication. Consequently, many platform-standard object
`files, software libraries and software toolkits are inaccessible
`to these systems.
`Other hybrid systems have specialized linkers which do
`support callbacks and references from external code to
`variables defined in the generated code. Programs generated
`by these systems are able to take advantage of platform-
`standard object files generated by other programming envi—
`ronments. However, since these systems do not generate
`platform-standard object fries themselves, programs gener-
`ated in other programming environments cannot take advan—
`tage of the functions implemented in their high-level sofi-
`ware modules.
`
`Another hybrid program development system has been
`developed by the Microsoft Corporation. Certain versions of
`the Microsoft Corporation’s C and C++ compiler allow
`program developers to compile all or selected portions of a
`source code program into platform—specific object ties which
`encapsulate “Pcode”. The Pcode object files may be linked
`with machine code object files as well as other Pcode object
`files to create a program. Pcode instructions are not directly
`executable on a computer. Therefore, an object file which
`implements a run~time Peode interpreter is also statically
`linked to the program containing the Pcode object files.
`During runtime, the Pcode interpreter interprets the Pcode
`instructions when a Pcode procedure is called.
`Pcode instructions generally take less space than their
`machine-code equivalents. Pcode achieves this size reduc-
`tion in part by making assumptions about the hardware
`which will run the program containing the Pcode. For
`example, Peode assumes the existence of certain registers.
`Pcode also assumes the size and meaning of data types, such
`as "word”. “short”, “long”, "near pointer”, “far pointer",
`“huge pointer" etc. While these assumptions allow a sig-
`nificant reduction in executable program size, they inhibit
`the portability of Pcode. For example, a Pcode routine which
`assumes that a “word" is sixteen bits of information may not
`run properly on a platform where a “wet ” constitutes
`thirty-two bits of information.
`
`Based on the foregoing, it is clearly desirable to provide
`a mechanism for encapsulating machine-independent soft-
`ware modules into platform-standard object files. It is fur—
`ther desirable to provide an on-the-fly code generation
`system which produces platfon'n-standard object files acces-
`sible by platform—standard object files generated by other
`programming environments. It is further desirable to provide
`a program development environment which defers the code
`conversion process
`selection until program run~time.
`Finally, it is desirable to provide a mechanism for selecting
`an optimal code conversion technique during run-time.
`SUMMARY OF THE INVENTION
`
`According to one aspect of the present invention, a
`method for generating a platform-standard object file from a
`
`ll]
`
`15
`
`20
`
`25
`
`3D
`
`35
`
`45
`
`50
`
`55
`
`65
`
`12
`
`machine-independent software module is provided. The
`machine-independent software module contains abstract
`code defining at least one procedure. According to the
`method, the abstract code is analyzed to determine whether
`any global variables are defined in the machine—independent
`software module. If any global variables are defined in the
`machine-independent software module, then a list of defiw
`nitions of the global variables is generated. The list of
`definitions is stored in the platform‘standard object file. The
`abstract code procedure is analyzed to determine whether
`the abstract code procedure references any external variables
`or external procedures. If the abstract code procedure ref-
`erences any external variables or external procedures, then
`a list of symbol references indicative of the external vari—
`ables or external procedures is generated. The list of symbol
`references is stored in the platforrn»standard object file. A
`sequence of machine instructions is generated for calling an
`execution routine when a client calls the abstract code
`procedure. The sequence of machine instructions is stored in
`the platform-standard object file. The abstract code is stored
`in the platform-standard object file.
`The method may optionally include a step of compressing
`the abstract code prior to storing the abstract code in the
`platfonn—standard object file. The list of symbol references
`includes a symbol reference indicative of the execution
`routine. The execution routine may take a variety of forms...
`For example, the execution routine may be a routine for
`interpreting the abstract code of the abstract code procedure.
`The execution routine may alternatively be a routine for
`generating machine code responsive to the abstract code
`procedure during execution of a program which includes the
`abstract code procedure.
`According to another aspect of the invention, a method for
`executing a computer program on a platform is provided.
`The computer program includes a first procedure imple-
`mented in a first platform~standard object file which calls a
`second procedure defined in abstract code contained in a
`machine-independent software module. The platform has a
`standard static linker. According to the method, a second
`platform—standard object
`file is generated based on the
`abstract code. The second platform-standard object
`file
`includes the abstract code. The first platform—standard object
`file is statically linked to the second platform-standard
`object file with the standard static linker. The second plat-
`fonn-standard object file is linked to an execution routine.
`The execution routine is invoked when the first procedure
`calls the second procedure. The execution routine causes the
`second procedure to be executed responsive to the abstract
`code.
`
`the second platform-
`According to one embodiment,
`standard object file is dynamically linked to the execution
`routine during execution of the program. The execution
`routine may be an interpreter, a code generator, or an
`execution control routine which executes abstract code
`according to a plurality of execution techniques.
`In an embodiment where the execution routine is an
`execution control routine which executes abstract code
`according to aplurality of execution techniques, the abstract
`code may be executed by selecting an execution technique
`from the plurality of execution techniques and executing the
`abstract code according to the selected execution technique.
`The plurality of execution techniques may include a tech-
`nique for interpreting abstract code and a technique for
`generating machine code responsive to abstract code. The
`plurality of execution techniques may alternatively include
`a first technique generating machine code responsive to
`abstract code and a second technique for generating machine
`
`12
`
`

`

`5
`
`6
`
`5,590,331
`
`FIG. 5a is a block diagram illustrating an execution
`routine dynamically linked to an abstract code execution
`routine according to an embodiment of the invention;
`FIG. 5b is a block diagram illustrating an execution
`control
`routine dynamically linked to an abstract code
`execution routine according to an alternative embodiment of
`the invention;
`
`10
`
`FIG. 6 is a flow chart illustrating the steps for creating a
`process image from some code according to one embodi-
`ment of the invention; and
`
`FIG. 7 is a flow chart illustrating a method for executing
`an abstract code procedure at runtime.
`
`code responsive to abstract code, where the first technique
`generating code is relatively faster than the second technique
`and the second technique generates more ehicient code
`relative to the first technique. An execution technique of the
`plurality of execution techniques may be selected responsive
`to the frequency with which the second procedure is called.
`According to yet another aspect of the invention, an
`apparatus for generating a platform-standard object file from
`a machine-independent software module stored on a storage
`unit is provided. The machine—independent software module
`contains abstract code defining an abstract code procedure.
`The apparatus generally includes a global variable process—
`ing unit, an external reference processing unit, a call routine
`generation unit and an abstract code encapsulating unit.
`The global variable processing unit is coupled to the
`storage unit. The global variable processing unit analyzes
`the abstract code to determine whether any global variables
`are defined in the machine-independent software module. If
`any global variables are defined in the machine-independent
`software module, then the global variable processing unit
`generates a list of definitions of the global variables and the
`list of definitions is stored in the platfonn-standard object
`file.
`
`The external reference processing unit is coupled to the
`storage unit. The external reference processing unit analyzes
`the abstract code to determine whether the abstract code
`procedure references any external variables or external
`procedures. If the abstract code procedure references any
`external variables or external procedures, then the external
`reference processing unit generates a list of symbol refer-
`ences indicative of the any external variables or external
`procedures and the list of symbol references is stored in the
`platform—standard object file.
`The call routine generation unit is coupled to the storage
`unit. The call routine generation unit generates a sequence of
`machine instructions for calling an execution routine when
`a client calls the abstract code procedure and the sequence
`of machine instructions is stored in the platform-standard
`object file. The abstract code encapsulating unit is coupled
`to the storage unit. The abstract code processing unit stores
`the abstract code in the platform—standard object file.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`15
`
`20
`
`30
`
`35
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`A method and apparatus for generating a platform-stan-
`dard object file from a high-level software module is
`described. In the following description, for the purposes of
`explanation, numerous specific details such as software
`tools. platforms, operating systems and programming lan~
`guages are set forth in order to provide a thorough under-
`standing of the present invention. It will be apparent, how-
`ever. to one skilled in the art that the present invention may
`be practiced without
`these specific details.
`In other
`instances, well-known structures and devices are shown in
`block diagram form in order to avoid unnecessarily obseur~
`ing the present invention.
`Referring to FIG. 1, a computer system 100 upon which
`the preferred embodiment of the present invention can be
`implemented is shown. Computer system 100 comprises a
`bus or other communication means 101 for communicating
`information, and a processing means 102 coupled with bus
`101 for processing information. Computer System 100 fur-
`ther comprises a random access memory (RAM) or other
`dynamic storage device 104 {referred to as main memory),
`coupled to bus 101 for storing information and instructions
`to be executed by processor 102. Main memory 104 also
`may be used for storing temporary variables or other inter-
`mediate information during execution of instructions by
`processor 102.
`
`Furthermore, a data storage device 107 such as a magnetic
`disk or optical disk and its corresponding disk drive can be
`coupled to computer system 100. Computer system 100 can
`also be coupled via bus 101 to a display device 121, such as
`a cathode ray tube (CRT), for displaying information to a
`computer user. An alphanumeric input device 122, including
`alphanumeric and other keys, is typically coupled to bus 101
`for communicating information and command selections to
`processor 102.
`
`The present invention is related to the use of computer
`system 100 to develop executable programs. In the currently
`preferred embodiment. computer system 100 is configured
`to run the UNIX System V operating system. Computer
`system 100 creates runtirne programs from source code by
`executing a plurality of programming tools which process
`the code. The various processing phases involved in the
`creation of an executable file shall now be described in
`greater detail with reference to FIG. 2a.
`
`FIG. 24 is a data flow diagram illustrating the processing
`phases of software development according to one embodi—
`ment of the invention. In FIG. 2a. data is illustrated with
`ovals, and the programming tools which process and convert
`the data are illustrated with rectangles. Between processing
`phases, the data is preferably stored either in memory 104 or
`on storage device 107. The programming tools are initially
`
`The present invention is illustrated by way of example,
`and not by way of limitation, in the figures of the accom-
`panying drawings and in which like reference numerals refer
`to similar elements and in which:
`
`45
`
`FIG. 1 is a block diagram of a computer system upon
`which the preferred embodiment of the present invention
`can be implemented;
`FIG. 2a is a data flow diagram illustrating software
`development according to an embodiment of the invention;
`FIG. 25 is a block diagram illustrating the tools of FIG. 2a
`as software modules stored in memory, according to an
`embodiment of the invention;
`
`FIG. 3a is a block diagram illustrating the source code
`converter of FIG. 2a in greater detail;
`FIG. 3b is a block diagram illustrating the linkable
`abstract code converter of FIG. 2a in greater detail;
`FIG. 4a is a block diagram illustrating the structure of an
`abstract code platform—standard object file according to One
`embodiment of the invention;
`
`FIG. 4b is a block diagram illustrating a statically linked
`execution file containing the abstract code platform-standard
`object file of FIG. 4a;
`
`55
`
`65
`
`13
`
`13
`
`

`

`7
`
`5,590,331
`
`8
`
`stored on storage device 107, and are loaded into memory
`104 prior to execution by processor 102.
`Prior to the first stage of the conversion process, a
`software developer creates a source code file which
`describes one or more procedures in high-level language,
`such as Pascal or CH. Source code 200 generally represents
`a file containing source code instructions.
`During the first phase of the executable file creation
`process, a source code converter 202 reads the source code
`200 and converts the source code 200 to machine-indepen—
`dent code (abstract code) 204-. Typically, the source code 200
`exists as a file on storage device 107. However, the source
`code 200 may alternatively be read from memory 104, if, for
`example, the source code converter 202 is invoked directly
`from a program editor.
`Source code converter 202 is illustrated in greater detail
`in FIG. 3a. The source code converter 202 generally
`includes a parser 300 and an abstract code generator 304.
`The parser 300 reads the source code 200 and generates an
`abstract semantic graph 302 based thereon. The abstract
`semantic graph 302 is a data structure which represents the
`procedures defined in the source code 200.
`The abstract code generator 304 reads the abstract seman-
`tic graph 302 and generates abstract code 204 based on the
`abstract semantic graph 302. Abstract code generator 304
`generates abstract code 204 which conforms to a particular
`abstract code language.
`Abstract code includes both machine—independent inter-
`preted code and machine—independent descriptions of pro-
`gram components. Abstract code difl'ers front Pcode gener-
`ated by Microsoft Corporation s C and GH- compilers in that
`abstract code makes no assumptions about the platform on
`which the program will ultimately execute. For example,
`abstract code explicitly states the size of every data type
`used in the procedures it defines. Thus, even if a source code
`language assumes that an integer is four bytes long,
`the
`abstract code generated from the source code will define a
`corresponding data type which expressly states that an
`integer is four bytes long.
`Thus, abstract code is significantly more portable than
`other forms of program representation used in the prior art.
`For example, an abstract procedure which operates on an
`integer may be accurately executed without modification on
`two platforms which define “integer” differently. This
`machine independence is achieved because the abstract code
`itself explicitly defines what is meant by “integer." It does
`not rely on platform—specific type definitions or platform-
`specific hardware futures.
`
`The abstract code 204 is initially generated as a linked
`data structure in memory 104. The fields of the linked data
`structure correspond to abstract code program elements.
`Those programming elements shall now be described with
`reference to a sample portion of a machine-independent
`software module listed in Appendix I. It will be understood
`that the specific su-ucture, grammar, syntax and lexemes of
`the sample machine-independent software module conform
`to a specific abstract code language. However,-thc abstract
`code language reflected in the sample portion of a machine-
`independent software module is merely exemplary. The
`present invention is not limited to any specific abstract code
`language. Therefore, abstract code generator 304 may alter»
`natively generate abstract code 204 which conforms to any
`abstract code language (Le. any programming language
`which makes no assumptions about the hardware on which
`a program will be executed).
`Referring now to the machine-independent software mod-
`ule portion illustrated in Appendix I, the machine-indepen—
`
`10
`
`15
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`14
`
`dent software module has a type definition section which
`defines the data types used andr‘or returned by the procedures
`defined in the machine-independent software module. The
`type definition section of the abstract code module illus-
`trated in Appendix 1 begins with the word “Types:". For each
`data type listed, the abstract code explicitly states the size
`{width} of the data type and whether the data type is signed.
`For example, data type 0 is a signed integer that is 32 bits
`wide.
`
`The type definition section is followed by a global vari-
`able definition section. In the globai variable definition
`section, the variables used in the procedures defined in the
`machineindependent software module which are to be
`accessible to procedures other than those defined in the
`machine—independent
`software module {external proce-
`dures) are defined. Each global variable is of a data type
`defined in the type definition section. For example, the
`global variable “outi” is defined as a