Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 47

The functions might be specified in tabular form, similar to thetable in Figure 4.1. Sometimes, the relationship between operand types andresult types is specified by a simple rule. In Java, for example, adding twointeger types of different precision produces a result of the more precise(longer) type.The inference rules point out type errors. Mixed-type expressions may beillegal. In fortran 77, a program cannot add a double and a complex.In Java, a program cannot assign a number to a character. These combinations should produce a type error at compile time, along with a messagethat indicates how the program is ill formed.Some languages require the compiler to perform implicit conversions.

Thecompiler must recognize certain combinations of mixed-type expressionsand handle them by inserting the appropriate conversions. In fortran,adding an integer and a floating-point number forces conversion of theinteger to floating-point form before the addition. Similarly, Java mandatesimplicit conversions for integer addition of values with different precision.The compiler must coerce the less precise value to the form of the moreprecise value before addition. A similar situation arises in Java with integerassignment.

If the right-hand side is less precise, it is converted to the moreprecise type of the left-hand side. If, however, the left-hand side is less precise than the right-hand side, the assignment produces a type error unless theprogrammer inserts an explicit cast operation to change its type and coerceits value.Declarations and InferenceThis scheme overloads 2 with different meaningsin different contexts.

Experience suggests thatprogrammers are good at understanding thiskind of overloading.As previously mentioned, many programming languages include a “declarebefore use” rule. With mandatory declarations, each variable has a welldefined type. The compiler needs a way to assign types to constants. Twoapproaches are common. Either a constant’s form implies a specific type—for example, 2 is an integer and 2.0 is a floating-point number—or thecompiler infers a constant’s type from its usage—for example, sin(2)implies that 2 is a floating-point number, while x ← 2, for integer x,implies that 2 is an integer. With declared types for variables, implied typesfor constants, and a complete set of type-inference rules, the compiler canassign types to any expression over variables and constants. Function callscomplicate the picture, as we shall see.Some languages absolve the programmer from writing any declarations.

Inthese languages, the problem of type inference becomes substantially moreintricate. Section 4.5 describes some of the problems that this creates andsome of the techniques that compilers use to address them.4.2 An Introduction to Type Systems 179CLASSIFYING TYPE SYSTEMSMany terms are used to describe type systems. In the text, we haveintroduced the terms strongly typed, untyped, and weakly typed languages.Other distinctions between type systems and their implementations areimportant.Checked versus Unchecked Implementations The implementation of a programming language may elect to perform enough checking to detectand to prevent all runtime errors that result from misuse of a type.

(Thismay actually exclude some value-specific errors, such as division by zero.)Such an implementation is called strongly checked. The opposite of astrongly checked implementation is an unchecked implementation—onethat assumes a well-formed program.

Between these poles lies a spectrumof weakly checked implementations that perform partial checking.Compile Time versus Runtime Activity A strongly typed language may havethe property that all inference and all checking can be done at compile time. An implementation that actually does all this work at compiletime is called statically typed and statically checked. Some languages haveconstructs that must be typed and checked at runtime. We term theselanguages dynamically typed and dynamically checked. To confuse mattersfurther, of course, a compiler writer can implement a strongly typed, statically typed language with dynamic checking.

Java is an example of alanguage that could be statically typed and checked, except for an execution model that keeps the compiler from seeing all the source code atonce. This forces it to perform type inference as classes are loaded and toperform some of the checking at runtime.Inferring Types for ExpressionsThe goal of type inference is to assign a type to each expression that occursin a program. The simplest case for type inference occurs when the compilercan assign a type to each base element in an expression—that is, to eachleaf in the parse tree for an expression. This requires declarations for allvariables, inferred types for all constants, and type information about allfunctions.Conceptually, the compiler can assign a type to each value in the expressionduring a simple postorder tree walk.

This should let the compiler detect everyviolation of an inference rule, and report it at compile time. If the languagelacks one or more of the features that make this simple style of inferencepossible, the compiler will need to use more sophisticated techniques. If180 CHAPTER 4 Context-Sensitive Analysiscompile time type inference becomes too difficult, the compiler writer mayneed to move some of the analysis and checking to runtime.Type inference for expressions, in this simple case, directly follows theexpression’s structure. The inference rules describe the problem in termsof the source language.

The evaluation strategy operates bottom up on theparse tree. For these reasons, type inference for expressions has become aclassic example problem to illustrate context-sensitive analysis.Interprocedural Aspects of Type InferenceType inference for expressions depends, inherently, on the other proceduresthat form the executable program.

Even in the simplest type systems, expressions contain function calls. The compiler must check each of those calls. Itmust ensure that each actual parameter is type compatible with the corresponding formal parameter. It must determine the type of any returned valuefor use in further inference.Type signaturea specification of the types of the formalparameters and return value(s) of a functionFunction prototypeThe C language includes a provision that lets theprogrammer declare functions that are notpresent. The programmer includes a skeletondeclaration, called a function prototype.To analyze and understand procedure calls, the compiler needs a type signature for each function. For example, the strlen function in c’s standardlibrary takes an operand of type char * and returns an int that contains itslength in bytes, excluding the terminating character.

In c, the programmercan record this fact with a function prototype that looks like:unsigned int strlen(const char *s);This prototype asserts that strlen takes an argument of type char *, whichit does not modify, as indicated by the const attribute. The function returnsa nonnegative integer. Writing this in a more abstract notation, we mightsay thatstrlen : const char * → unsigned intwhich we read as “strlen is a function that takes a constant-valued character string and returns an unsigned integer.” As a second example, the classicScheme function filter has the type signaturefilter: (α →boolean) × list of α → list of αThat is, filter is a function that takes two arguments. The first should bea function that maps some type α into a boolean, written (α →boolean), andthe second should be a list whose elements are of the same type α. Givenarguments of those types, filter returns a list whose elements have type α.The function filter exhibits parametric polymorphism: its result type is afunction of its argument types.4.2 An Introduction to Type Systems 181To perform accurate type inference, the compiler needs a type signature forevery function.

It can obtain that information in several ways. The compilercan eliminate separate compilation, requiring that the entire program be presented for compilation as a unit. The compiler can require the programmerto provide a type signature for each function; this usually takes the form ofmandatory function prototypes. The compiler can defer type checking untileither link time or runtime, when all such information is available.

Finally,the compiler writer can embed the compiler in a program-development system that gathers the requisite information and makes it available to thecompiler on demand. All of these approaches have been used in real systems.SECTION REVIEWA type system associates with each value in the program some textualname, a type, that represents a set of common properties held by allvalues of that type. The definition of a programming language specifiesinteractions between objects of the same type, such as legal operationson values of a type, and between objects of different type, such as mixedtype arithmetic operations.

A well-designed type system can increase theexpressiveness of a programming language, allowing safe use of featuressuch as overloading. It can expose subtle errors in a program long beforethey become puzzling runtime errors or wrong answers. It can let thecompiler avoid runtime checks that waste time and space.A type system consists of a set of base types, rules for constructingnew types from existing ones, a method for determining equivalenceof two types, and rules for inferring the types of each expression ina program.

The notions of base types, constructed types, and typeequivalence should be familiar to anyone who has programmed in ahigh-level language. Type inference plays a critical role in compilerimplementation.Review Questions1. For your favorite programming language, write down the base typesin its type system. What rules and constructs does the language allowto build aggregate types? Does it provide a mechanism for creating aprocedure that takes a variable number of arguments, such as printfin the C standard I/O library?2. What kinds of information must the compiler have to ensure typesafety at procedure calls? Sketch a scheme based on the use of function prototypes.