Type system for representing and checking consistency of heterogeneous program components during the process of compilation

• US 7,685,581 B2
• Filed: 06/27/2003
• Issued: 03/23/2010
• Est. Priority Date: 06/27/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tarditi, David Read Jr., Plesko, Mark Ronald
• Primary Examiner(s): Dam; Tuan Q
• Assistant Examiner(s): DAO, THUY CHAN
• Application Number:
  US10/607,591
• Publication Number:
  US 20050015673A1
• Time in Patent Office: 2,461 Days
• Field of Search: None
• US Class Current: 717/146
• CPC Class Codes: G06F 8/20 Software design
• CPC Class Codes: G06F 8/437 Type checking

Abstract

A representation of types, type-checker, method and compiler are provided for checking consistency in various forms of an intermediate language. Specifically, the typed intermediate language is suitable for use in representing programs written in multiple (heterogeneous) source languages including typed and untyped languages, loosely and strongly typed languages, and languages with and without garbage collection. An unknown type representation indicates that an element of the intermediate language is associated with an unknown type. A method of type-checking a code segment written in a programming language is provided using a rule set that contains rules for type-checking an unknown type. The unknown type allows for selectively retaining type information as the compilation process continues and allows multiple programming languages to be type-checked by the same type system.

Claims

1. A method of type-checking a code segment written in a programming language comprising:

translating the code segment from the programming language to one or more representations of a typed intermediate language, wherein the one or more representations of the typed intermediate language are capable of representing programs written in a plurality of different source languages, and wherein the one or more representations comprise a first object having a known type, and wherein the translating comprises;

determining that the first object will be type-checked as an unknown type, and

based on the determining, designating the first object as having the unknown type by dropping the known type of the first object and replacing the known type with the unknown type; and

type-checking the one or more representations based on a rule set, wherein;

the rule set comprises rules for type-checking the type designated as the unknown type,

the unknown type indicates that an element of the representation is of a type that is not known, and

the first object is type-checked as having an unknown type, based on the designating.

2. The method of claim 1 wherein the rule set is selected from a plurality of rule sets.

3. The method of claim 2 wherein only a fraction of the plurality of rule sets contain rules for type-checking a type designated as an unknown type, wherein the unknown type indicates that an element of the representation is of a type that is not known.

4. The method of claim 1 wherein the rule set further comprises rules for type-checking types representing categories of types found in a plurality of programming languages.

5. The method of claim 1, wherein the plurality of different source languages comprise at least one typed language and at least one assembly language.

6. The method of claim 1, wherein the rule set comprises a rule that causes the type-checking to not type-check the first object.

7. The method of claim 1, wherein the one or more representations further comprise a second object having the first object'"'"'s known type, and further comprising:

determining that the second object will not be type-checked as an unknown type, and wherein the rule set comprises rules for type-checking types not designated as the unknown type, and wherein the type-checking comprises type-checking the second object using rules the rules for type-checking types not designated as the unknown type.

8. A computer-readable storage medium containing computer-executable instructions for implementing the method of claim 1.

9. A method of selectively retaining type information during compilation in a code segment written in a programming language, the method comprising:

translating the code segment from the programming language to one or more intermediate language representations;

for each intermediate language representation, determining whether to retain type information for one or more elements of the intermediate language representation, wherein the one or more intermediate language representations include one or more elements having a known type;

based on the determination, associating at least one of the one or more elements of the intermediate language representation with a type, designated as an unknown type, indicating the element can be of any type; and

type-checking the one or more intermediate language representations based on a rule set, wherein the rule set comprises rules for type-checking the type designated as the unknown type.

10. The method of claim 9 wherein the determination is based on a current stage of compilation, a characteristic of each representation, or the programming language.

11. The method of claim 9 wherein the type, designated as the unknown type, indicating the element can be of any type has size information associated with it.

12. The method of claim 11 further comprising generating code from at least elements associated with the type, designated as the unknown type, indicating the element can be of any type based on the size information.

13. The method of claim 9 wherein at least one of the one or more representations of the intermediate language supports dropping type information by designating a type as an unknown type.

14. The method of claim 9, wherein the translating further comprises:

identifying a virtual function call in the code segment;

translating the virtual function call to an intermediate representation that when converted to computer-executable instructions and executed on a computer cause the computer to perform a method including, fetching a pointer associated with a virtual table, wherein the translating assigns a temporary variable to store the result of the fetching; and

wherein the determining further comprises not retaining type information for the temporary variable assigned to store the result of the fetching, because the type of the temporary variable is designated as the unknown type.

15. The method of claim 9, wherein the type information for the one or more elements of the representation designated as an unknown type comprises a primitive type.

16. A method of translating types associated with a plurality of programming languages to types of an intermediate language, the method comprising:

replacing the types associated with the plurality of programming languages with the types of the intermediate language, wherein;

at least one of the plurality of programming languages is non-type-safe,

the types of the intermediate language comprise plural programming language specific primitive types associated with the plurality of programming languages and a type designated as an unknown type,

the type designated as the unknown type has size information associated with it,

at least one of the plural programming language specific primitive types is replaced with the unknown type, and

the size information comprises size information of a machine representation of the type designated as the unknown type.

17. A computer system for type-checking an intermediate representation of source code in a compiler comprising:

a computer-readable storage medium containing one or more types associated with elements of the intermediate representation, wherein at least one of the types, designated as an unknown type, indicates an element can be of any type;

a computer-readable storage medium containing one or more rule sets comprising rules associated with the type, designated as the unknown type, indicating an element can be of any type; and

a type-checker module, wherein the type-checker is configured for applying the one or more rule sets to the elements of the intermediate representation, wherein the type-checker module selectively retains type information for some elements of the intermediate representation and selectively does not retain type information for at least one element of the intermediate representation by replacing a known type associated with the at least one element with the type, designated as the unknown type, indicating the at least one element can be of any type, wherein the type-checker is configured to apply the one or more rule sets after the replacing the known type with the unknown type.

18. The system of claim 17 wherein the type, designated as the unknown type, indicating the element can be of any type has size information associated with it.

19. The system of claim 18 wherein the size information comprises size information of a machine representation of the type designated as the unknown type.

20. The system of claim 17 wherein the one or more rule sets applied to the elements of the intermediate representation are selected based on the stage of compilation.

21. The system of claim 17 wherein the one or more rule sets applied to the elements of the intermediate representation are selected based on a characteristic of the source code.

22. The system of claim 17 wherein the one or more rule sets applied to the elements of the intermediate representation are selected based on the intermediate representation.

23. The system of claim 17 wherein only a fraction of the one or more rule sets contain rules for type-checking a type, designated as an unknown type, that indicates an element can be of any type.

24. The system of claim 17 wherein the one or more rule sets further comprise rules for type-checking types representing categories of types found in a plurality of programming languages.

25. A method of representing types in an intermediate language comprising:

defining a plurality of types to be associated with elements of the intermediate language, wherein one of the plurality of types indicates that an element of the intermediate language is associated with a type designated as an unknown type;

wherein the type indicating that an element of the intermediate language is associated with the type designated as the unknown type has a size associated with it, wherein the size represents size of a machine representation of the type designated as the unknown type;

wherein an element of the intermediate language that was previously associated with a known type is associated with the type designated as the unknown type;

wherein the rule set further comprises rules for dropping type information for one or more elements of the representation by changing the known type of the one or more elements to the type designated as an unknown type.

26. The method of claim 25 wherein the plurality of types further comprises types representing categories of types found in a plurality of programming languages.

27. A computer-readable storage medium containing computer-executable instructions for implementing the method of claim 25.