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

For calls wherethey cannot discover the receiver’s class, or where the class varies at runtime,the implementations can cache search results to improve performance. Inthis scheme, the search consults a method cache before it searches the classhierarchy. If the method cache contains the mapping for the receiver’s classand the method name, the call uses the cached method pointer and avoidsthe search.Multiple InheritanceSome ools allow multiple inheritance, meaning a new class may inheritfrom several superclasses that have inconsistent object layouts. This situation poses a new problem: the compiled code for a superclass methoduses offsets based on the or layout for that superclass. Of course, different immediate superclasses may assign conflicting offsets to their fields.To reconcile these competing offsets, the compiler must adopt a slightlymore complex scheme: it must use different or pointers with methods fromdifferent superclasses.Consider a class α that inherits from multiple superclasses, β, γ , and δ.

Tolay out the or for an object of class α, the implementation must first imposean order on α’s superclasses—say β, γ , δ. It lays out the or for class α asthe entire or, including class pointer and method vector, for β, followed bythe entire or for γ , followed by the entire or for δ. To this layout, it appendsany fields declared locally in the declaration of α. It constructs the methodvector for α by appending α’s methods to the method vector for the firstsuperclass.The drawing in the margin shows the resulting or layout for class α, Weassume that α defines two local fields, α1 and α2 , and that the fields ofβ, γ , and δ are named similarly.

The or for α divides into four logicalsections: the or for β, the or for γ , the or for δ, and the space for fieldsdeclared in α. Methods declared in α are appended to the method vector forthe first section. The “shadow” class pointers and method vectors, whose296 CHAPTER 6 The Procedure Abstractionclass αmethods •β1β2class αmethods •- β methodsα methods- γ methodsγ1γ2γ3class αmethods •δ1-δ methodsα1α2Object Record for αlabels appear in gray, exist to allow those superclass methods to receivethe environment that they expect—the or layout of the correspondingsuperclass.The remaining complication involved in multiple inheritance lies in the factthat the or pointer must be adjusted when a superclass method is invokedusing one of the shadow class pointers and method vectors.

The invocationmust adjust the pointer by the distance between the class pointer at the top ofthe or and the shadow class pointer. The simplest mechanism to accomplishthis adjustment is to insert a trampoline function between the method vectorand the actual method.

The trampoline adjusts the or pointer, invokes themethod with all of the parameters, and readjusts the or pointer on return.SECTION REVIEWAlgol-like languages typically use lexical scoping, in which namesspaces are properly nested and new instances of a name obscure olderones. To hold data associated with its local scope, a procedure has anactivation record for each invocation. In contrast, while object-orientedlanguages may use lexical scopes for procedure-local names, theyalso rely on a hierarchy of scopes defined by the data—by thehierarchy of class definitions.

This dual-hierarchy name space leadsto more complex interactions among names and to more compleximplementations.Both styles of naming require runtime structures that both reflect andimplement the naming hierarchy. In an ALL, the activation recordscan capture the structure of the name space, provide the necessarystorage for most values, and preserve the state necessary for correctexecution.

In an OOL, the activation records of running code stillcapture the lexically scoped portion of the name space and the state ofexecution; however, the implementation also needs a hierarchy of objectrecords and class records to model the object-based portion of thename space.Review Questions1.

In C, setjmp and longjmp provide a mechanism for interproceduraltransfer of control. setjmp creates a data structure; invoking longjmpon the data structure created by a setjmp causes execution to continue immediately after the setjmp, with the context present whenthe setjmp executed. What information must setjmp preserve? Howdoes the implementation of setjmp change between stack-allocatedand heap-allocated ARs?6.4 Communicating Values Between Procedures 2972. Consider the example from Figure 6.7.

If the compiler encounters areference to LeftCorner with a cast to class Point, which implementation of the method draw would that cast reference invoke? Howcould the programmer refer to the other implementation of draw?6.4 COMMUNICATING VALUES BETWEENPROCEDURESThe central notion underlying the concept of a procedure is abstraction. Theprogrammer abstracts common operations relative to a small set of names,or formal parameters, and encapsulates those operations in a procedure. Touse the procedure, the programmer invokes it with an appropriate binding of values, or actual parameters, to those formal parameters. The calleeexecutes, using the formal parameter names to access the values passed asactual parameters.

If the programmer desires, the procedure can return aresult.6.4.1 Passing ParametersParameter binding maps the actual parameters at a call site to the callee’sformal parameters. It lets the programmer write a procedure without knowledge of the contexts in which it will be called.

It lets the programmer invokethe procedure from many distinct contexts without exposing details of theprocedure’s internal operation in each caller. Thus, parameter binding playsa critical role in our ability to write abstract, modular code.Most modern programming languages use one of two conventions for mapping actual parameters to formal parameters: call-by-value binding andcall-by-reference binding.

These techniques differ in their behavior. Thedistinction between them may be best explained by understanding theirimplementations.Call by ValueConsider the following procedure, written in c, and several call sites thatinvoke it:int fee(int x, int y) {}c = fee(2,3);x = 2 * x;y = x + y;a = 2;return y;c = fee(a,b);b = 3;a = 2;b = 3;c = fee(a,a);Call by valuea convention where the caller evaluates theactual parameters and passes their values to thecalleeAny modification of a value parameter in thecallee is not visible in the caller.298 CHAPTER 6 The Procedure AbstractionCALL-BY-NAME PARAMETER BINDINGAlgol introduced another parameter-binding mechanism, call by name. Incall-by-name binding, a reference to a formal parameter behaves exactlyas if the actual parameter had been textually substituted in its place, withappropriate renaming.

This simple rule can lead to complex behavior.Consider the following artificial example in Algol 60:begin comment Simple array example;procedure zero(Arr,i,j,u1,u2);integer Arr;integer i,j,u1,u2;begin;for i := 1 step 1 until u1 dofor j := 1 step 1 until u2 doArr := 0;end;integer array Work[1:100,1:200];integer p, q, x, y, z;x := 100;y := 200;zero(Work[p,q],p,q,x,y);endThe call to zero assigns zero to every element of the array Work.

To seethis, rewrite zero with the text of the actual parameters.While call-by-name binding was easy to define, it was difficult to implement and to understand. In general, the compiler must produce, foreach formal parameter, a function that evaluates the actual parameterto return a pointer. These functions are called thunks. Generating competent thunks was complex; evaluating a thunk for each parameter accesswas expensive.

In the end, these disadvantages overcame any advantagesthat call-by-name parameter binding offered.The R programming language, a domain-specific tool for statistical analysis, implements a lazy form of call-by-value binding. The implementationcreates and passes thunks that are invoked the first time that the parameter value is actually referenced. The thunk, or promise, stores its result forsubsequent references.With call-by-value parameter passing, as in c, the caller copies the valueof an actual parameter into the appropriate location for the correspondingformal parameter—either a register or a parameter slot in the callee’s ar.Only one name refers to that value—the name of the formal parameter.

Itsvalue is an initial condition, determined by evaluating the actual parameter6.4 Communicating Values Between Procedures 299at the time of the call. If the callee changes its value, that change is visibleinside the callee, but not in the caller.The three invocations produce the following results when invoked usingcall-by-value parameter binding:Call byaReturnbValueinoutinoutValuefee(2,3)fee(a,b)fee(a,a)22223333776With call by value, the binding is simple and intuitive.One variation on call-by-value binding is call-by-value-result binding.

In thevalue-result scheme, the values of formal parameters are copied back into thecorresponding actual parameters as part of the process of returning controlfrom the callee to the caller. The programming language Ada includes valueresult parameters. The value-result mechanism also satisfies the rules of thefortran 77 language definition.Call by ReferenceWith call-by-reference parameter passing, the caller stores a pointer in thear slot for each parameter. If the actual parameter is a variable, it storesthe variable’s address in memory. If the actual parameter is an expression,the caller evaluates the expression, stores the result in the local data area ofits own ar, and then stores a pointer to that result in the appropriate parameter slot in the callee’s ar. Constants should be treated as expressions to avoidany possibility of the callee changing the value of a constant.