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

Each abstraction that aprogramming language supports needs a translation to the target machine’sinstruction set. This chapter has explored the techniques commonly used totranslate some of these abstractions.Procedural programming was invented early in the history of programming.Some of the first procedures were debugging routines written for early computers; the availability of these prewritten routines allowed programmers tounderstand the runtime state of an errant program. Without such routines,tasks that we now take for granted, such as examining the contents of a variable or asking for a trace of the call stack, required the programmer to enterlong machine-language sequences without error.The introduction of lexical scoping in languages like Algol 60 influencedlanguage design for decades. Most modern programming languages carryforward some of Algol’s philosophy toward naming and addressability.Techniques developed to support lexical scoping, such as access links anddisplays, reduced the runtime cost of this abstraction.

These techniques arestill used today.Object-oriented languages take the scoping concepts of alls and reorientthem in data-directed ways. The compiler for an object-oriented languageuses both compile-time and runtime structures invented for lexical scopingto implement the naming discipline imposed by the inheritance hierarchy ofa specific program.Modern languages have added some new twists. By making proceduresfirst-class objects, languages like Scheme have created new controlflow paradigms. These require variations on traditional implementationtechniques—for example, heap allocation of activation records. Similarly,the growing acceptance of implicit deallocation requires occasional conservative treatment of a pointer. If the compiler can exercise a little more careand free the programmer from ever deallocating storage again, that appearsto be a good tradeoff. (Generations of experience suggest that programmersChapter Notes 323are not effective at freeing all the storage that they allocate.

They also freeobjects to which they retain pointers.)As new programming paradigms emerge, they will introduce new abstractions that require careful thought and implementation. By studying thesuccessful techniques of the past and understanding the constraints and costsinvolved in real implementations, compiler writers will develop strategiesthat decrease the runtime penalty for using higher levels of abstraction.nCHAPTER NOTESMuch of the material in this chapter comes from the accumulated experienceof the compiler-construction community. The best way to learn more aboutthe name-space structures of various languages is to consult the languagedefinitions themselves. These documents are a necessary part of a compilerwriter’s library.Procedures appeared in the earliest high-level languages—that is, languages that were more abstract than assembly language. fortran [27] andAlgol 60 [273] both had procedures with most of the features found in modern languages.

Object-oriented languages appeared in the late 1960s withsimula 67 [278] followed by Smalltalk 72 [233].Lexical scoping was introduced in Algol 60 and has persisted to the presentday. The early Algol compilers introduced most of the support mechanisms described in this chapter, including activation records, access links,and parameter-passing techniques. Much of the material from Sections 6.3through 6.5 was present in these early systems [293]. Optimizations quicklyappeared, like folding storage for a block-level scope into the containingprocedure’s activation record. The ibm 370 linkage conventions recognizedthe difference between leaf procedures and others; they avoided allocatinga register save area for leaf routines.

Murtagh took a more complete andsystematic approach to coalescing activation records [272].The classic reference on memory allocation schemes is Knuth’s Art of Computer Programming [231, § 2.5]. Modern multipool allocators appeared inthe early 1980s. Reference counting dates to the early 1960s and has beenused in many systems [95, 125].

Cohen and later Wilson, provide broad surveys of the literature on garbage collection [92, 350]. Conservative collectors were introduced by Boehm and Weiser [44, 46, 120]. Copying collectorsappeared in response to virtual memory systems [79, 144]; they led, somewhat naturally, to the generational collectors in widespread use today [247,337]. Hanson introduced the notion of arena-based allocation [179].324 CHAPTER 6 The Procedure AbstractionnSection 6.2EXERCISES1. Show the call tree and execution history for the following c program:int Sub(int i, int j) {return i - j;}int Mul(int i, int j) {return i * j;}int Delta(int a, int b, int c) {return Sub(Mul(b,b), Mul(Mul(4,a),c));}void main() {int a, b, c, delta;scanf("%d %d %d", &a, &b, &c);delta = Delta(a, b, c);if (delta == 0)puts("Two equal roots");else if (delta > 0)puts("Two different roots");elseputs("No root");}2.

Show the call tree and execution history for the following c program:void Output(int n, int x) {printf("The value of %d! is %s.\n", n, x);}int Fat(int n) {int x;if (n > 1)x = n * Fat(n - 1);elsex = 1;Output(n, x);return x;}void main() {Fat(4);}Exercises 3253. Consider the following Pascal program, in which only procedure callsand variable declarations are shown:1234567891011121314151617181920212223242526272829303132333435program Main(input, output);var a, b, c : integer;procedure P4; forward;procedure P1;procedure P2;beginend;var b, d, f : integer;procedure P3;var a, b : integer;beginP2;end;beginP2;P4;P3;end;var d, e : integer;procedure P4;var a, c, g : integer;procedure P5;var c, d : integer;beginP1;end;var d : integer;beginP1;P5;end;beginP1;P4;end.a.

Construct a static coordinate table, similar to the one in Figure 6.3.b. Construct a graph to show the nesting relationships in the program.c. Construct a graph to show the calling relationships in the program.Section 6.3326 CHAPTER 6 The Procedure Abstraction4. Some programming languages allow the programmer to use functionsin the initialization of local variables but not in the initialization ofglobal variables.a. Is there an implementation rationale to explain this seeming quirkof the language definition?b.

What mechanisms would be needed to allow initialization of aglobal variable with the result of a function call?5. The compiler writer can optimize the allocation of ars in severalways. For example, the compiler might:a. Allocate ars for leaf procedures statically.b. Combine the ars for procedures that are always called together.(When α is called, it always calls β.)c. Use an arena-style allocator in place of heap allocation of ars.For each scheme, consider the following questions:a.

What fraction of the calls might benefit? In the best case? In theworst case?b. What is the impact on runtime space utilization?6. Draw the structures that the compiler would need to create to supportan object of type Dumbo, defined as follows:class Elephant {private int Length;private int Weight;static int type;public int GetLen();public int GetTyp();}class Dumbo extends Elephant {private int EarSize;private boolean Fly;public boolean CanFly();}7.

In a programming language with an open class structure, the numberof method invocations that need runtime name resolution, or dynamicdispatch, can be large. A method cache, as described in Section 6.3.4,can reduce the runtime cost of these lookups by short-circuiting them.As an alternative to a global method cache, the implementation mightmaintain a single entry method cache at each call site—an inlineExercises 3271234567891011121314151617procedure main;var a : array[1...3] of int;i : int;procedure p2(e : int);begine := e + 3;a[i] := 5;i := 2;e := e + 4;end;begina := [1, 10, 77];i := 1;p2(a[i]);for i := 1 to 3 doprint(a[i]);end.n FIGURE 6.13 Program for Problem 8.method cache that records record the address of the method mostrecently dispatched from that site, along with its class.Develop pseudocode to use and maintain such an inline method cache.Explain the initialization of the inline method caches and anymodifications to the general method lookup routine required tosupport inline method caches.8.

Consider the program written in Pascal-like pseudo code shown inFigure 6.13. Simulate its execution under call-by-value,call-by-reference, call-by-name, and call-by-value-result parameterbinding rules. Show the results of the print statements in each case.9. The possibility that two distinct variables refer to the same object(memory area) is considered undesirable in programming languages.Consider the following Pascal procedure, with parameters passed byreference:procedure mystery(var x, y : integer);beginx := x + y;y := x - y;x := x - y;end;Section 6.4328 CHAPTER 6 The Procedure Abstraction1234567891011121314151617181920212223242526program main(input, output);procedure P1( function g(b: integer): integer);var a: integer;begina := 3;writeln(g(2))Local Variablesend;Access Linkprocedure P2;var a: integer;ARPfunction F1(b: integer): integer;Return AddressArgument 1beginF1 := a + b···end;Argument nprocedure P3;var a:integer;(b) Activation Record Structurebegina := 7;ARPP1(F1)end;Access Link (0)Return Address (0)begina := 0;(c) Initial Activation RecordP3end;beginP2end.(a) Example Pascal Programn FIGURE 6.14 Program for Problem 10.If no overflow or underflow occurs during the arithmetic operations:a.

What result does mystery produce when it is called with twodistinct variables, a and b?b. What would be the expected result if mystery is invoked with asingle variable a passed to both parameters? What is the actualresult in this case?Section 6.510. Consider the Pascal program shown in Figure 6.14a. Suppose that theimplementation uses ars as shown in Figure 6.14b. (Some fields havebeen omitted for simplicity.) The implementation stack allocatesthe ars, with the stack growing toward the top of the page. The arp isExercises 329the only pointer to the ar, so access links are previous values of thearp.