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

It makes distinctions thatare useful to the programmer. For example, a tree node with two childrenprobably should have a different type than a tree node with three children;presumably, they are used in different situations. A program that assignsa three-child node to a two-child node should generate a type error and awarning message to the programmer.From the perspective of the runtime system, however, treating each structure as a distinct type complicates the picture. With distinct structure types,the heap contains an arbitrary set of objects drawn from an arbitrary setof types.

This makes it difficult to reason about programs that deal directlywith the objects on the heap, such as a garbage collector. To simplify suchprograms, their authors sometimes take a different approach to structuretypes.This alternate model considers all structures in the program as a singletype. Individual structure declarations each create a variant form of thetype structure. The type structure, itself, is the union of all these variants.This approach lets the program view the heap as a collection of objects ofa single type, rather than a collection of many types. This view makes codethat manipulates the heap much simpler to analyze and optimize.include structures of distinct types, even when the individual structure typeshave different lengths. The language must provide a mechanism to referenceeach field unambiguously.PointersPointers are abstract memory addresses that let the programmer manipulatearbitrary data structures.

Many languages include a pointer type. Pointerslet a program save an address and later examine the object that it addresses.Pointers are created when objects are created (new in Java or malloc in c).Some languages provide an operator that returns the address of an object,such as c’s & operator.To protect programmers from using a pointer to type t to reference a structureof type s, some languages restrict pointer assignment to “equivalent” types.In these languages, the pointer on the left-hand side of an assignment musthave the same type as the expression on the right-hand side.

A program canlegally assign a pointer to integer to a variable declared as pointer to integerbut not to one declared as pointer to pointer to integer or pointer to boolean.The address operator, when applied to an objectof type t, returns a value of type pointer to t.176 CHAPTER 4 Context-Sensitive AnalysisThese latter assignments are either illegal or require an explicit conversionby the programmer.PolymorphismA function that can operate on arguments ofdifferent types is a polymorphic function.If the set of types must be specified explicitly, thefunction uses ad hoc polymorphism; if thefunction body does not specify types, it usesparametric polymorphism.Of course, the mechanism for creating new objects should return an objectof the appropriate type. Thus, Java’s new explicitly creates a typed object;other languages use a polymorphic routine that takes the return type as aparameter.

ansi c handles this in an unusual way: The standard allocationroutine malloc returns a pointer to void. This forces the programmer tocast the value returned by each call to malloc.Some languages allow direct manipulation of pointers. Arithmetic on pointers, including autoincrement and autodecrement, allow the program toconstruct new pointers. c uses the type of a pointer to determine autoincrement and decrement magnitudes. The programmer can set a pointer to thestart of an array; autoincrementing advances the pointer from one elementin the array to the next element.Type safety with pointers relies on an implicit assumption that addressescorrespond to typed objects. The ability to construct new pointers seriously reduces the ability of both the compiler and its runtime system toreason about pointer-based computations and to optimize such code. (See,for example, Section 8.4.1.)Type Equivalencestruct Tree {struct Tree *left;struct Tree *right;int value}struct STree {struct STree *left;struct STree *right;int value}A critical component of any type system is the mechanism that it uses todecide whether or not two different type declarations are equivalent.

Consider the two declarations in c shown in the margin. Are Tree and STree thesame type? Are they equivalent? Any programming language with a nontrivial type system must include an unambiguous rule to answer this question forarbitrary types.Historically, two general approaches have been tried. The first, name equivalence, asserts that two types are equivalent if and only if they have thesame name. Philosophically, this rule assumes that the programmer canselect any name for a type; if the programmer chooses different names, thelanguage and its implementation should honor that deliberate act.

Unfortunately, the difficulty of maintaining consistent names grows with the size ofthe program, the number of authors, and the number of distinct files of code.The second approach, structural equivalence, asserts that two types areequivalent if and only if they have the same structure.

Philosophically, thisrule asserts that two objects are interchangeable if they consist of the sameset of fields, in the same order, and those fields all have equivalent types.Structural equivalence examines the essential properties that define the type.4.2 An Introduction to Type Systems 177REPRESENTING TYPESAs with most objects that a compiler must manipulate, types need an internal representation. Some languages, such as FORTRAN 77, have a small fixedset of types. For these languages, a small integer tag is both efficient andsufficient.

However, many modern languages have open-ended type systems. For these languages, the compiler writer needs to design a structurethat can represent arbitrary types.If the type system is based on name equivalence, any number of simplerepresentations will suffice, as long as the compiler can use the representation to trace back to a representation of the actual structure. Ifthe type system is based on structural equivalence, the representation ofthe type must encode its structure. Most such systems build trees to represent types.

They construct a tree for each type declaration and comparetree structures to test for equivalence.Each policy has strengths and weaknesses. Name equivalence assumes thatidentical names occur as a deliberate act; in a large programming project,this requires discipline to avoid unintentional clashes. Structural equivalence assumes that interchangeable objects can be used safely in place ofone another; if some of the values have “special” meanings, this can create problems. (Imagine two hypothetical, structurally identical types.

Thefirst holds a system i/o control block, while the second holds the collectionof information about a bit-mapped image on the screen. Treating them asdistinct types would allow the compiler to detect a misuse—passing the i/ocontrol block to a screen refresh routine—while treating them as the sametype would not.)Inference RulesIn general, type inference rules specify, for each operator, the mappingbetween the operand types and the result type. For some cases, the mappingis simple.

An assignment, for example, has one operand and one result. Theresult, or left-hand side, must have a type that is compatible with the typeof the operand, or right-hand side. (In Pascal, the subrange 1..100 is compatible with the integers since any element of the subrange can be assignedsafely to an integer.) This rule allows assignment of an integer value to aninteger variable. It forbids assignment of a structure to an integer variable,without an explicit conversion that makes sense of the operation.The relationship between operand types and result types is often specifiedas a recursive function on the type of the expression tree. The functioncomputes the result type of an operation as a function of the types of its178 CHAPTER 4 Context-Sensitive Analysisoperands.