Chapter 3 Names, Scopes, and Bindings PDF

116 Chapter 3 Names, Scopes, and Bindings the lifetime of an object and the lifetime of a binding of a name to that object.1 Most name-to-object bindings are usable only within a limited region of a given high-level program. Section 3.3 exp...

116 Chapter 3 Names, Scopes, and Bindings the lifetime of an object and the lifetime of a binding of a name to that object.1 Most name-to-object bindings are usable only within a limited region of a given high-level program. Section 3.3 explores the scope rules that define this region; Section 3.4 (mostly on the companion site) considers their implementation. The complete set of bindings in effect at a given point in a program is known as the current referencing environment. Section 3.5 discusses aliasing, in which more than one name may refer to a given object in a given scope, and overloading, in which a name may refer to more than one object in a given scope, depending on the context of the reference. Section 3.6 expands on the notion of scope rules by considering the ways in which a referencing environment may be bound to a subroutine that is passed as a parameter, returned from a function, or stored in a variable. Section 3.7 discusses macro expansion, which can introduce new names via textual substitution, sometimes in ways that are at odds with the rest of the language. Finally, Section 3.8 (mostly on the companion site) discusses separate compilation. 3.1 The Notion of Binding Time A binding is an association between two things, such as a name and the thing it names. Binding time is the time at which a binding is created or, more generally, the time at which any implementation decision is made (we can think of this as binding an answer to a question). There are many different times at which decisions may be bound: Language design time: In most languages, the control-flow constructs, the set of fundamental (primitive) types, the available constructors for creating complex types, and many other aspects of language semantics are chosen when the lan- guage is designed. Language implementation time: Most language manuals leave a variety of issues to the discretion of the language implementor. Typical (though by no means universal) examples include the precision (number of bits) of the fundamental types, the coupling of I/O to the operating system’s notion of files, and the organization and maximum sizes of the stack and heap. Program writing time: Programmers, of course, choose algorithms, data struc- tures, and names. Compile time: Compilers choose the mapping of high-level constructs to ma- chine code, including the layout of statically defined data in memory. 1 For want of a better term, we will use the term “object” throughout Chapters 3–9 to refer to anything that might have a name: variables, constants, types, subroutines, modules, and oth- ers. In many modern languages “object” has a more formal meaning, which we will consider in Chapter 10.  3.1 The Notion of Binding Time 117 Link time: Since most compilers support separate compilation—compiling dif- ferent modules of a program at different times—and depend on the availability of a library of standard subroutines, a program is usually not complete until the various modules are joined together by a linker. The linker chooses the overall layout of the modules with respect to one another, and resolves inter- module references. When a name in one module refers to an object in another module, the binding between the two is not finalized until link time. Load time: Load time refers to the point at which the operating system loads the program into memory so that it can run. In primitive operating systems, the choice of machine addresses for objects within the program was not finalized until load time. Most modern operating systems distinguish between virtual and physical addresses. Virtual addresses are chosen at link time; physical ad- dresses can actually change at run time. The processor’s memory management hardware translates virtual addresses into physical addresses during each indi- vidual instruction at run time. Run time: Run time is actually a very broad term that covers the entire span from the beginning to the end of execution. Bindings of values to variables occur at run time, as do a host of other decisions that vary from language to language. Run time subsumes program start-up time, module entry time, elaboration time (the point at which a declaration is first “seen”), subroutine call time, block entry time, and expression evaluation time/statement execution. The terms static and dynamic are generally used to refer to things bound before run time and at run time, respectively. Clearly “static” is a coarse term. So is “dynamic.” Compiler-based language implementations tend to be more efficient than interpreter-based implementations because they make earlier decisions. For ex- ample, a compiler analyzes the syntax and semantics of global variable declara- tions once, before the program ever runs. It decides on a layout for those variables in memory and generates efficient code to access them wherever they appear in the program. A pure interpreter, by contrast, must analyze the declarations every time the program begins execution. In the worst case, an interpreter may reana- lyze the local declarations within a subroutine each time that subroutine is called. If a call appears in a deeply nested loop, the savings achieved by a compiler that is able to analyze the declarations only once may be very large. As we shall see in D E S I G N & I M P L E M E N TAT I O N 3.1 Binding time It is difficult to overemphasize the importance of binding times in the design and implementation of programming languages. In general, early binding times are associated with greater efficiency, while later binding times are as- sociated with greater flexibility. The tension between these goals provides a recurring theme for later chapters of this book. 118 Chapter 3 Names, Scopes, and Bindings the following section, a compiler will not usually be able to predict the address of a local variable at compile time, since space for the variable will be allocated dy- namically on a stack, but it can arrange for the variable to appear at a fixed offset from the location pointed to by a certain register at run time. Some languages are difficult to compile because their semantics require funda- mental decisions to be postponed until run time, generally in order to increase the flexibility or expressiveness of the language. Most scripting languages, for exam- ple, delay all type checking until run time. References to objects of arbitrary types (classes) can be assigned into arbitrary named variables, as long as the program never ends up applying an operator to (invoking a method of) an object that is not prepared to handle it. This form of polymorphism—applicability to objects or expressions of multiple types—allows the programmer to write unusually flexi- ble and general-purpose code. We will mention polymorphism again in several future sections, including 7.1.2, 7.3, 10.1.1, and 14.4.4. 3.2 Object Lifetime and Storage Management In any discussion of names and bindings, it is important to distinguish between names and the objects to which they refer, and to identify several key events: Creation and destruction of objects Creation and destruction of bindings Deactivation and reactivation of bindings that may be temporarily unusable References to variables, subroutines, types, and so on, all of which use bindings The period of time between the creation and the destruction of a name-to- object binding is called the binding’s lifetime. Similarly, the time between the creation and destruction of an object is the object’s lifetime. These lifetimes need not necessarily coincide. In particular, an object may retain its value and the po- tential to be accessed even when a given name can no longer be used to access it. When a variable is passed to a subroutine by reference, for example (as it typically is in Fortran or with ‘ & ’ parameters in C++), the binding between the parame- ter name and the variable that was passed has a lifetime shorter than that of the variable itself. It is also possible, though generally a sign of a program bug, for a name-to-object binding to have a lifetime longer than that of the object. This can happen, for example, if an object created via the C++ new operator is passed as a & parameter and then deallocated ( delete -ed) before the subroutine returns. A binding to an object that is no longer live is called a dangling reference. Dangling references will be discussed further in Sections 3.6 and 8.5.2. Object lifetimes generally correspond to one of three principal storage alloca- tion mechanisms, used to manage the object’s space: 1. Static objects are given an absolute address that is retained throughout the program’s execution.  3.2 Object Lifetime and Storage Management 119 2. Stack objects are allocated and deallocated in last-in, first-out order, usually in conjunction with subroutine calls and returns. 3. Heap objects may be allocated and deallocated at arbitrary times. They require a more general (and expensive) storage management algorithm. 3.2.1 Static Allocation Global variables are the obvious example of static objects, but not the only one. The instructions that constitute a program’s machine code can also be thought of as statically allocated objects. We shall see examples in Section 3.3.1 of vari- ables that are local to a single subroutine, but retain their values from one invo- cation to the next; their space is statically allocated. Numeric and string-valued constant literals are also statically allocated, for statements such as A = B/14.7 or printf("hello, world\n"). (Small constants are often stored within the instruction itself; larger ones are assigned a separate location.) Finally, most compilers produce a variety of tables that are used by run-time support routines for debugging, dynamic type checking, garbage collection, exception handling, and other purposes; these are also statically allocated. Statically allocated ob- jects whose value should not change during program execution (e.g., instructions, constants, and certain run-time tables) are often allocated in protected, read-only memory, so that any inadvertent attempt to write to them will cause a processor interrupt, allowing the operating system to announce a run-time error. Logically speaking, local variables are created when their subroutine is called, and destroyed when it returns. If the subroutine is called repeatedly, each invo- cation is said to create and destroy a separate instance of each local variable. It is not always the case, however, that a language implementation must perform work EXAMP L E 3.1 at run time corresponding to these create and destroy operations. Recursion was Static allocation of local not originally supported in Fortran (it was added in Fortran 90). As a result, there variables can never be more than one invocation of a subroutine active in an older Fortran program at any given time, and a compiler may choose to use static allocation for local variables, effectively arranging for the variables of different invocations to share the same locations, and thereby avoiding any run-time overhead for cre- ation and destruction.  D E S I G N & I M P L E M E N TAT I O N 3.2 Recursion in Fortran The lack of recursion in (pre-Fortran 90) Fortran is generally attributed to the expense of stack manipulation on the IBM 704, on which the language was first implemented. Many (perhaps most) Fortran implementations choose to use a stack for local variables, but because the language definition permits the use of static allocation instead, Fortran programmers were denied the benefits of language-supported recursion for over 30 years. 120 Chapter 3 Names, Scopes, and Bindings In many languages a named constant is required to have a value that can be determined at compile time. Usually the expression that specifies the constant’s value is permitted to include only other known constants and built-in functions and arithmetic operators. Named constants of this sort, together with constant literals, are sometimes called manifest constants or compile-time constants. Mani- fest constants can always be allocated statically, even if they are local to a recursive subroutine: multiple instances can share the same location. In other languages (e.g., C and Ada), constants are simply variables that cannot be changed after elaboration (initialization) time. Their values, though unchang- ing, can sometimes depend on other values that are not known until run time. Such elaboration-time constants, when local to a recursive subroutine, must be allocated on the stack. C# distinguishes between compile-time and elaboration- time constants using the const and readonly keywords, respectively. 3.2.2 Stack-Based Allocation If a language permits recursion, static allocation of local variables is no longer an option, since the number of instances of a variable that may need to exist at the same time is conceptually unbounded. Fortunately, the natural nesting of sub- EXAMP L E 3.2 routine calls makes it easy to allocate space for locals on a stack. A simplified Layout of the run-time picture of a typical stack appears in Figure 3.1. Each instance of a subroutine at stack run time has its own frame (also called an activation record) on the stack, contain- ing arguments and return values, local variables, temporaries, and bookkeeping information. Temporaries are typically intermediate values produced in complex calculations. Bookkeeping information typically includes the subroutine’s return address, a reference to the stack frame of the caller (also called the dynamic link), saved values of registers needed by both the caller and the callee, and various other values that we will study later. Arguments to be passed to subsequent routines lie at the top of the frame, where the callee can easily find them. The organization of the remaining information is implementation-dependent: it varies from one language, machine, and compiler to another.  Maintenance of the stack is the responsibility of the subroutine calling se- quence—the code executed by the caller immediately before and after the call— and of the prologue (code executed at the beginning) and epilogue (code executed at the end) of the subroutine itself. Sometimes the term “calling sequence” is used to refer to the combined operations of the caller, the prologue, and the epilogue. We will study calling sequences in more detail in Section 9.2. While the location of a stack frame cannot be predicted at compile time (the compiler cannot in general tell what other frames may already be on the stack), the offsets of objects within a frame usually can be statically determined. More- over, the compiler can arrange (in the calling sequence or prologue) for a par- ticular register, known as the frame pointer to always point to a known location within the frame of the current subroutine. Code that needs to access a local vari- able within the current frame, or an argument near the top of the calling frame,  3.2 Object Lifetime and Storage Management 121 sp procedure C D; E Subroutine D Arguments to called procedure B fp if... then B else C routines procedure A Temporaries B −− main program Subroutine C A Local variables Direction of stack growth (usually Miscellaneous lower addresses) Subroutine B bookkeeping fp (when subroutine Return address C is running) Subroutine B Subroutine A Figure 3.1 Stack-based allocation of space for subroutines. We assume here that subroutines have been called as shown in the upper right. In particular, B has called itself once, recursively, before calling C. If D returns and C calls E , E ’s frame (activation record) will occupy the same space previously used for D ’s frame. At any given time, the stack pointer ( sp ) register points to the first unused location on the stack (or the last used location on some machines), and the frame pointer ( fp ) register points to a known location within the frame of the current subroutine. The relative order of fields within a frame may vary from machine to machine and compiler to compiler. can do so by adding a predetermined offset to the value in the frame pointer. As we discuss in Section C 5.3.1, almost every processor provides a displacement addressing mechanism that allows this addition to be specified implicitly as part of an ordinary load or store instruction. The stack grows “downward” toward lower addresses in most language implementations. Some machines provide spe- cial push and pop instructions that assume this direction of growth. Local vari- ables, temporaries, and bookkeeping information typically have negative offsets from the frame pointer. Arguments and returns typically have positive offsets; they reside in the caller’s frame. Even in a language without recursion, it can be advantageous to use a stack for local variables, rather than allocating them statically. In most programs the pat- tern of potential calls among subroutines does not permit all of those subroutines to be active at the same time. As a result, the total space needed for local vari- ables of currently active subroutines is seldom as large as the total space across all 122 Chapter 3 Names, Scopes, and Bindings Heap Allocation request Figure 3.2 Fragmentation. The shaded blocks are in use; the clear blocks are free. Cross- hatched space at the ends of in-use blocks represents internal fragmentation. The discontiguous free blocks indicate external fragmentation. While there is more than enough total free space remaining to satisfy an allocation request of the illustrated size, no single remaining block is large enough. subroutines, active or not. A stack may therefore require substantially less mem- ory at run time than would be required for static allocation. 3.2.3 Heap-Based Allocation A heap is a region of storage in which subblocks can be allocated and deallocated at arbitrary times.2 Heaps are required for the dynamically allocated pieces of linked data structures, and for objects such as fully general character strings, lists, and sets, whose size may change as a result of an assignment statement or other update operation. There are many possible strategies to manage space in a heap. We review the major alternatives here; details can be found in any data-structures textbook. The principal concerns are speed and space, and as usual there are tradeoffs between them. Space concerns can be further subdivided into issues of internal and ex- ternal fragmentation. Internal fragmentation occurs when a storage-management algorithm allocates a block that is larger than required to hold a given object; the EXAMP L E 3.3 extra space is then unused. External fragmentation occurs when the blocks that External fragmentation in have been assigned to active objects are scattered through the heap in such a way the heap that the remaining, unused space is composed of multiple blocks: there may be quite a lot of free space, but no one piece of it may be large enough to satisfy some future request (see Figure 3.2).  Many storage-management algorithms maintain a single linked list—the free list—of heap blocks not currently in use. Initially the list consists of a single block comprising the entire heap. At each allocation request the algorithm searches the list for a block of appropriate size. With a first fit algorithm we select the first block on the list that is large enough to satisfy the request. With a best fit algorithm we search the entire list to find the smallest block that is large enough to satisfy the 2 Unfortunately, the term “heap” is also used for the common tree-based implementation of a priority queue. These two uses of the term have nothing to do with one another.  3.2 Object Lifetime and Storage Management 123 request. In either case, if the chosen block is significantly larger than required, then we divide it into two and return the unneeded portion to the free list as a smaller block. (If the unneeded portion is below some minimum threshold in size, we may leave it in the allocated block as internal fragmentation.) When a block is deallocated and returned to the free list, we check to see whether either or both of the physically adjacent blocks are free; if so, we coalesce them. Intuitively, one would expect a best fit algorithm to do a better job of reserving large blocks for large requests. At the same time, it has higher allocation cost than a first fit algorithm, because it must always search the entire list, and it tends to result in a larger number of very small “left-over” blocks. Which approach—first fit or best fit—results in lower external fragmentation depends on the distribution of size requests. In any algorithm that maintains a single free list, the cost of allocation is lin- ear in the number of free blocks. To reduce this cost to a constant, some stor- age management algorithms maintain separate free lists for blocks of different sizes. Each request is rounded up to the next standard size (at the cost of inter- nal fragmentation) and allocated from the appropriate list. In effect, the heap is divided into “pools,” one for each standard size. The division may be static or dynamic. Two common mechanisms for dynamic pool adjustment are known as the buddy system and the Fibonacci heap. In the buddy system, the standard block sizes are powers of two. If a block of size 2k is needed, but none is available, a block of size 2k+1 is split in two. One of the halves is used to satisfy the request; the other is placed on the kth free list. When a block is deallocated, it is coa- lesced with its “buddy”—the other half of the split that created it—if that buddy is free. Fibonacci heaps are similar, but use Fibonacci numbers for the standard sizes, instead of powers of two. The algorithm is slightly more complex, but leads to slightly lower internal fragmentation, because the Fibonacci sequence grows more slowly than 2k. The problem with external fragmentation is that the ability of the heap to sat- isfy requests may degrade over time. Multiple free lists may help, by clustering small blocks in relatively close physical proximity, but they do not eliminate the problem. It is always possible to devise a sequence of requests that cannot be satisfied, even though the total space required is less than the size of the heap. If memory is partitioned among size pools statically, one need only exceed the maxi- mum number of requests of a given size. If pools are dynamically readjusted, one can “checkerboard” the heap by allocating a large number of small blocks and then deallocating every other one, in order of physical address, leaving an alter- nating pattern of small free and allocated blocks. To eliminate external fragmen- tation, we must be prepared to compact the heap, by moving already-allocated blocks. This task is complicated by the need to find and update all outstanding references to a block that is being moved. We will discuss compaction further in Section 8.5.3. 124 Chapter 3 Names, Scopes, and Bindings 3.2.4 Garbage Collection Allocation of heap-based objects is always triggered by some specific operation in a program: instantiating an object, appending to the end of a list, assigning a long value into a previously short string, and so on. Deallocation is also explicit in some languages (e.g., C, C++, and Rust). As we shall see in Section 8.5, however, many languages specify that objects are to be deallocated implicitly when it is no longer possible to reach them from any program variable. The run-time library for such a language must then provide a garbage collection mechanism to identify and reclaim unreachable objects. Most functional and scripting languages require garbage collection, as do many more recent imperative languages, including Java and C#. The traditional arguments in favor of explicit deallocation are implementa- tion simplicity and execution speed. Even naive implementations of automatic garbage collection add significant complexity to the implementation of a lan- guage with a rich type system, and even the most sophisticated garbage collector can consume nontrivial amounts of time in certain programs. If the programmer can correctly identify the end of an object’s lifetime, without too much run-time bookkeeping, the result is likely to be faster execution. The argument in favor of automatic garbage collection, however, is compel- ling: manual deallocation errors are among the most common and costly bugs in real-world programs. If an object is deallocated too soon, the program may follow a dangling reference, accessing memory now used by another object. If an object is not deallocated at the end of its lifetime, then the program may “leak memory,” eventually running out of heap space. Deallocation errors are notoriously diffi- cult to identify and fix. Over time, many language designers and programmers have come to consider automatic garbage collection an essential language feature. Garbage-collection algorithms have improved, reducing their run-time overhead; language implementations have become more complex in general, reducing the marginal complexity of automatic collection; and leading-edge applications have become larger and more complex, making the benefits of automatic collection ever more compelling. 3C H E C K YO U R U N D E R S TA N D I N G 1. What is binding time? 2. Explain the distinction between decisions that are bound statically and those that are bound dynamically. 3. What is the advantage of binding things as early as possible? What is the advantage of delaying bindings? 4. Explain the distinction between the lifetime of a name-to-object binding and its visibility.  3.3 Scope Rules 125 5. What determines whether an object is allocated statically, on the stack, or in the heap? 6. List the objects and information commonly found in a stack frame. 7. What is a frame pointer? What is it used for? 8. What is a calling sequence? 9. What are internal and external fragmentation? 10. What is garbage collection? 11. What is a dangling reference? 3.3 Scope Rules The textual region of the program in which a binding is active is its scope. In most modern languages, the scope of a binding is determined statically, that is, at compile time. In C, for example, we introduce a new scope upon entry to a subroutine. We create bindings for local objects and deactivate bindings for global objects that are hidden (made invisible) by local objects of the same name. On subroutine exit, we destroy bindings for local variables and reactivate bindings for any global objects that were hidden. These manipulations of bindings may at first glance appear to be run-time operations, but they do not require the execution of any code: the portions of the program in which a binding is active are completely determined at compile time. We can look at a C program and know which names refer to which objects at which points in the program based on purely textual rules. For this reason, C is said to be statically scoped (some authors say lexically scoped 3 ). Other languages, including APL, Snobol, Tcl, and early dialects of Lisp, are dynamically scoped: their bindings depend on the flow of execution at run time. We will examine static and dynamic scoping in more detail in Sections 3.3.1 and 3.3.6. In addition to talking about the “scope of a binding,” we sometimes use the word “scope” as a noun all by itself, without a specific binding in mind. Infor- mally, a scope is a program region of maximal size in which no bindings change (or at least none are destroyed—more on this in Section 3.3.3). Typically, a scope is the body of a module, class, subroutine, or structured control-flow statement, sometimes called a block. In C family languages it would be delimited with {...} braces. 3 Lexical scope is actually a better term than static scope, because scope rules based on nesting can be enforced at run time instead of compile time if desired. In fact, in Common Lisp and Scheme it is possible to pass the unevaluated text of a subroutine declaration into some other subroutine as a parameter, and then use the text to create a lexically nested declaration at run time. 126 Chapter 3 Names, Scopes, and Bindings Algol 68 and Ada use the term elaboration to refer to the process by which declarations become active when control first enters a scope. Elaboration entails the creation of bindings. In many languages, it also entails the allocation of stack space for local objects, and possibly the assignment of initial values. In Ada it can entail a host of other things, including the execution of error-checking or heap-space-allocating code, the propagation of exceptions, and the creation of concurrently executing tasks (to be discussed in Chapter 13). At any given point in a program’s execution, the set of active bindings is called the current referencing environment. The set is principally determined by static or dynamic scope rules. We shall see that a referencing environment generally corresponds to a sequence of scopes that can be examined (in order) to find the current binding for a given name. In some cases, referencing environments also depend on what are (in a con- fusing use of terminology) called binding rules. Specifically, when a reference to a subroutine S is stored in a variable, passed as a parameter to another subroutine, or returned as a function value, one needs to determine when the referencing en- vironment for S is chosen—that is, when the binding between the reference to S and the referencing environment of S is made. The two principal options are deep binding, in which the choice is made when the reference is first created, and shallow binding, in which the choice is made when the reference is finally used. We will examine these options in more detail in Section 3.6. 3.3.1 Static Scoping In a language with static (lexical) scoping, the bindings between names and ob- jects can be determined at compile time by examining the text of the program, without consideration of the flow of control at run time. Typically, the “current” binding for a given name is found in the matching declaration whose block most closely surrounds a given point in the program, though as we shall see there are many variants on this basic theme. The simplest static scope rule is probably that of early versions of Basic, in which there was only a single, global scope. In fact, there were only a few hundred possible names, each of which consisted of a letter optionally followed by a digit. There were no explicit declarations; variables were declared implicitly by virtue of being used. Scope rules are somewhat more complex in (pre-Fortran 90) Fortran, though not much more. Fortran distinguishes between global and local variables. The scope of a local variable is limited to the subroutine in which it appears; it is not visible elsewhere. Variable declarations are optional. If a variable is not declared, it is assumed to be local to the current subroutine and to be of type integer if its name begins with the letters I–N, or real otherwise. (Different conventions for implicit declarations can be specified by the programmer. In Fortran 90 and its successors, the programmer can also turn off implicit declarations, so that use of an undeclared variable becomes a compile-time error.)  3.3 Scope Rules 127 void label_name (char *s) { static short int n; sprintf (s, "L%d\0", ++n); } Figure 3.3 C code to illustrate the use of static variables. Semantically, the lifetime of a local Fortran variable (both the object itself and the name-to-object binding) encompasses a single execution of the variable’s sub- routine. Programmers can override this rule by using an explicit save statement. (Similar mechanisms appear in many other languages: in C one declares the vari- able static ; in Algol one declares it own.) A save -ed ( static , own ) variable has a lifetime that encompasses the entire execution of the program. Instead of a log- ically separate object for every invocation of the subroutine, the compiler creates a single object that retains its value from one invocation of the subroutine to the next. (The name-to-variable binding, of course, is inactive when the subroutine is not executing, because the name is out of scope.) EXAMP L E 3.4 As an example of the use of static variables, consider the code in Figure 3.3. Static variables in C The subroutine label_name can be used to generate a series of distinct character- string names: L1 , L2 ,.... A compiler might use these names in its assembly language output.  3.3.2 Nested Subroutines The ability to nest subroutines inside each other, introduced in Algol 60, is a fea- ture of many subsequent languages, including Ada, ML, Common Lisp, Python, Scheme, Swift, and (to a limited extent) Fortran 90. Other languages, including C and its descendants, allow classes or other scopes to nest. Just as the local variables of a Fortran subroutine are not visible to other subroutines, any constants, types, variables, or subroutines declared within a scope are not visible outside that scope in Algol-family languages. More formally, Algol-style nesting gives rise to the clos- est nested scope rule for bindings from names to objects: a name that is introduced in a declaration is known in the scope in which it is declared, and in each inter- nally nested scope, unless it is hidden by another declaration of the same name in one or more nested scopes. To find the object corresponding to a given use of a name, we look for a declaration with that name in the current, innermost scope. If there is one, it defines the active binding for the name. Otherwise, we look for a declaration in the immediately surrounding scope. We continue outward, 128 Chapter 3 Names, Scopes, and Bindings examining successively surrounding scopes, until we reach the outer nesting level of the program, where global objects are declared. If no declaration is found at any level, then the program is in error. Many languages provide a collection of built-in, or predefined objects, such as I/O routines, mathematical functions, and in some cases types such as integer and char. It is common to consider these to be declared in an extra, invisible, outermost scope, which surrounds the scope in which global objects are declared. The search for bindings described in the previous paragraph terminates at this ex- tra, outermost scope, if it exists, rather than at the scope in which global objects are declared. This outermost scope convention makes it possible for a program- mer to define a global object whose name is the same as that of some predefined object (whose “declaration” is thereby hidden, making it invisible). EXAMP L E 3.5 An example of nested scopes appears in Figure 3.4.4 In this example, procedure Nested scopes P2 is called only by P1 , and need not be visible outside. It is therefore declared inside P1 , limiting its scope (its region of visibility) to the portion of the program shown here. In a similar fashion, P4 is visible only within P1 , P3 is visible only within P2 , and F1 is visible only within P4. Under the standard rules for nested scopes, F1 could call P2 and P4 could call F1 , but P2 could not call F1. Though they are hidden from the rest of the program, nested subroutines are able to access the parameters and local variables (and other local objects) of the surrounding scope(s). In our example, P3 can name (and modify) A1 , X , and A2 , in addition to A3. Because P1 and F1 both declare local variables named X , the inner declaration hides the outer one within a portion of its scope. Uses of X in F1 refer to the inner X ; uses of X in other regions of the code refer to the outer X.  A name-to-object binding that is hidden by a nested declaration of the same name is said to have a hole in its scope. In some languages, the object whose name is hidden is simply inaccessible in the nested scope (unless it has more than one name). In others, the programmer can access the outer meaning of a name by applying a qualifier or scope resolution operator. In Ada, for example, a name may be prefixed by the name of the scope in which it is declared, using syntax that resembles the specification of fields in a record. My_proc.X , for example, refers to the declaration of X in subroutine My_proc , regardless of whether some other X has been declared in a lexically closer scope. In C++, which does not allow subroutines to nest, ::X refers to a global declaration of X , regardless of whether the current subroutine also has an X.5 Access to Nonlocal Objects We have already seen (Section 3.2.2) that the compiler can arrange for a frame pointer register to point to the frame of the currently executing subroutine at run 4 This code is not contrived; it was extracted from an implementation (originally in Pascal) of the FMQ error repair algorithm described in Section C 2.3.5. 5 The C++ :: operator is also used to name members (fields or methods) of a base class that are hidden by members of a derived class; we will consider this use in Section 10.2.2.  3.3 Scope Rules 129 procedure P1(A1) A1 X P2 P4 var X −− local to P1... procedure P2(A2) A2 P3... procedure P3(A3) A3... begin... −− body of P3 end... begin... −− body of P2 end... procedure P4(A4) A4 F1... function F1(A5) A5 X var X −− local to F1... begin... −− body of F1 end... begin... −− body of P4 end... begin... −− body of P1 end Figure 3.4 Example of nested subroutines, shown in pseudocode. Vertical bars indicate the scope of each name, for a language in which declarations are visible throughout their subroutine. Note the hole in the scope of the outer X. time. Using this register as a base for displacement (register plus offset) address- ing, target code can access objects within the current subroutine. But what about objects in lexically surrounding subroutines? To find these we need a way to find the frames corresponding to those scopes at run time. Since a nested subroutine may call a routine in an outer scope, the order of stack frames at run time may not necessarily correspond to the order of lexical nesting. Nonetheless, we can be sure that there is some frame for the surrounding scope already in the stack, since the current subroutine could not have been called unless it was visible, and it could not have been visible unless the surrounding scope was active. (It is actually pos- sible in some languages to save a reference to a nested subroutine, and then call it when the surrounding scope is no longer active. We defer this possibility to Section 3.6.2.) The simplest way in which to find the frames of surrounding scopes is to main- tain a static link in each frame that points to the “parent” frame: the frame of the 130 Chapter 3 Names, Scopes, and Bindings A B C C fp D D B E E A Figure 3.5 Static chains. Subroutines A , B , C , D , and E are nested as shown on the left. If the sequence of nested calls at run time is A , E , B , D , and C , then the static links in the stack will look as shown on the right. The code for subroutine C can find local objects at known offsets from the frame pointer. It can find local objects of the surrounding scope, B , by dereferencing its static chain once and then applying an offset. It can find local objects in B ’s surrounding scope, A , by dereferencing its static chain twice and then applying an offset. most recent invocation of the lexically surrounding subroutine. If a subroutine is declared at the outermost nesting level of the program, then its frame will have a null static link at run time. If a subroutine is nested k levels deep, then its frame’s static link, and those of its parent, grandparent, and so on, will form a static chain of length k at run time. To find a variable or parameter declared j subroutine scopes outward, target code at run time can dereference the static chain j times, EXAMP L E 3.6 and then add the appropriate offset. Static chains are illustrated in Figure 3.5. We Static chains will discuss the code required to maintain them in Section 9.2.  3.3.3 Declaration Order In our discussion so far we have glossed over an important subtlety: suppose an object x is declared somewhere within block B. Does the scope of x include the portion of B before the declaration, and if so can x actually be used in that portion of the code? Put another way, can an expression E refer to any name declared in the current scope, or only to names that are declared before E in the scope? Several early languages, including Algol 60 and Lisp, required that all declara- tions appear at the beginning of their scope. One might at first think that this rule  3.3 Scope Rules 131 would avoid the questions in the preceding paragraph, but it does not, because declarations may refer to one another.6 EXAMP L E 3.7 In an apparent attempt to simplify the implementation of the compiler, Pas- A “gotcha” in cal modified the requirement to say that names must be declared before they are declare-before-use used. There are special mechanisms to accommodate recursive types and sub- routines, but in general, a forward reference (an attempt to use a name before its declaration) is a static semantic error. At the same time, however, Pascal retained the notion that the scope of a declaration is the entire surrounding block. Taken together, whole-block scope and declare-before-use rules can interact in surpris- ing ways: 1. const N = 10; 2.... 3. procedure foo; 4. const 5. M = N; (* static semantic error! *) 6.... 7. N = 20; (* local constant declaration; hides the outer N *) Pascal says that the second declaration of N covers all of foo , so the semantic analyzer should complain on line 5 that N is being used before its declaration. The error has the potential to be highly confusing, particularly if the programmer meant to use the outer N : const N = 10;... procedure foo; const M = N; (* static semantic error! *) var A : array [1..M] of integer; N : real; (* hiding declaration *) Here the pair of messages “ N used before declaration” and “ N is not a constant” are almost certainly not helpful. D E S I G N & I M P L E M E N TAT I O N 3.3 Mutual recursion Some Algol 60 compilers were known to process the declarations of a scope in program order. This strategy had the unfortunate effect of implicitly outlawing mutually recursive subroutines and types, something the language designers clearly did not intend [Atk73]. 6 We saw an example of mutually recursive subroutines in the recursive descent parsing of Sec- tion 2.3.1. Mutually recursive types frequently arise in linked data structures, where nodes of two types may need to point to each other. 132 Chapter 3 Names, Scopes, and Bindings In order to determine the validity of any declaration that appears to use a name from a surrounding scope, a Pascal compiler must scan the remainder of the scope’s declarations to see if the name is hidden. To avoid this complication, most Pascal successors (and some dialects of Pascal itself) specify that the scope of an identifier is not the entire block in which it is declared (excluding holes), but rather the portion of that block from the declaration to the end (again excluding holes). If our program fragment had been written in Ada, for example, or in C, C++, or Java, no semantic errors would be reported. The declaration of M would refer to the first (outer) declaration of N.  C++ and Java further relax the rules by dispensing with the define-before-use requirement in many cases. In both languages, members of a class (including those that are not defined until later in the program text) are visible inside all of the class’s methods. In Java, classes themselves can be declared in any order. EXAMP L E 3.8 Interestingly, while C# echos Java in requiring declaration before use for local Whole-block scope in C# variables (but not for classes and members), it returns to the Pascal notion of whole-block scope. Thus the following is invalid in C#: class A { const int N = 10; void foo() { const int M = N; // uses inner N before it is declared const int N = 20;  Perhaps the simplest approach to declaration order, from a conceptual point of view, is that of Modula-3, which says that the scope of a declaration is the en- tire block in which it appears (minus any holes created by nested declarations), and that the order of declarations doesn’t matter. The principal objection to this approach is that programmers may find it counterintuitive to use a local variable EXAMP L E 3.9 before it is declared. Python takes the “whole block” scope rule one step further “Local if written” in Python by dispensing with variable declarations altogether. In their place it adopts the unusual convention that the local variables of subroutine S are precisely those variables that are written by some statement in the (static) body of S. If S is nested inside of T , and the name x appears on the left-hand side of assignment statements in both S and T , then the x ’s are distinct: there is one in S and one in T. Non-local variables are read-only unless explicitly imported (using Python’s global statement). We will consider these conventions in more detail in Sec- tion 14.4.1, as part of a general discussion of scoping in scripting languages.  EXAMP L E 3.10 In the interest of flexibility, modern Lisp dialects tend to provide several op- Declaration order in tions for declaration order. In Scheme, for example, the letrec and let* con- Scheme structs define scopes with, respectively, whole-block and declaration-to-end-of- block semantics. The most frequently used construct, let , provides yet another option: (let ((A 1)) ; outer scope, with A defined to be 1 (let ((A 2) ; inner scope, with A defined to be 2 (B A)) ; and B defined to be A B)) ; return the value of B  3.3 Scope Rules 133 Here the nested declarations of A and B don’t take effect until after the end of the declaration list. Thus when B is defined, the redefinition of A has not yet taken effect. B is defined to be the outer A , and the code as a whole returns 1.  Declarations and Definitions Recursive types and subroutines introduce a problem for languages that require names to be declared before they can be used: how can two declarations each appear before the other? C and C++ handle the problem by distinguishing be- tween the declaration of an object and its definition. A declaration introduces a name and indicates its scope, but may omit certain implementation details. A definition describes the object in sufficient detail for the compiler to determine its implementation. If a declaration is not complete enough to be a definition, EXAMP L E 3.11 then a separate definition must appear somewhere else in the scope. In C we can Declarations vs definitions write in C struct manager; struct employee { struct manager *boss; struct employee *next_employee;... }; struct manager { struct employee *first_employee;... }; and void list_tail(follow_set fs); void list(follow_set fs) { switch (input_token) { case id : match(id); list_tail(fs);... } void list_tail(follow_set fs) { switch (input_token) { case comma : match(comma); list(fs);... } The initial declaration of manager needed only to introduce a name: since point- ers are generally all the same size, the compiler can determine the implementa- tion of employee without knowing any manager details. The initial declaration of list_tail , however, must include the return type and parameter list, so the compiler can tell that the call in list is correct.  134 Chapter 3 Names, Scopes, and Bindings Nested Blocks In many languages, including Algol 60, C89, and Ada, local variables can be de- clared not only at the beginning of any subroutine, but also at the top of any begin... end ( {...} ) block. Other languages, including Algol 68, C, and all of C’s descendants, are even more flexible, allowing declarations wherever a state- ment may appear. In most languages a nested declaration hides any outer dec- laration with the same name (Java and C# make it a static semantic error if the outer declaration is local to the current subroutine). D E S I G N & I M P L E M E N TAT I O N 3.4 Redeclarations Some languages, particularly those that are intended for interactive use, permit the programmer to redeclare an object: to create a new binding for a given name in a given scope. Interactive programmers commonly use redeclarations to experiment with alternative implementations or to fix bugs during early development. In most interactive languages, the new meaning of the name replaces the old in all contexts. In ML dialects, however, the old meaning of the name may remain accessible to functions that were elaborated before the name was redeclared. This design choice can sometimes be counterintuitive. Here’s an example in OCaml (the lines beginning with # are user input; the others are printed by the interpreter): # let x = 1;; val x : int = 1 # let f y = x + y;; val f : int -> int = # let x = 2;; val x : int = 2 # f 3;; - : int = 4 The second line of user input defines f to be a function of one argument ( y ) that returns the sum of that argument and the previously defined value x. When we redefine x to be 2, however, the function does not notice: it still returns y plus 1. This behavior reflects the fact that OCaml is usually com- piled, bit by bit on the fly, rather than interpreted. When x is redefined, f has already been compiled into a form (bytecode or machine code) that ac- cesses the old meaning of x directly. By comparison, a language like Scheme, which is lexically scoped but usually interpreted, stores the bindings for names in known locations. Programs always access the meanings of names indirectly through those locations: if the meaning of a name changes, all accesses to the name will use the new meaning.  3.3 Scope Rules 135 EXAMP L E 3.12 Variables declared in nested blocks can be very useful, as for example in the Inner declarations in C following C code: { int temp = a; a = b; b = temp; } Keeping the declaration of temp lexically adjacent to the code that uses it makes the program easier to read, and eliminates any possibility that this code will in- terfere with another variable named temp.  No run-time work is needed to allocate or deallocate space for variables de- clared in nested blocks; their space can be included in the total space for local variables allocated in the subroutine prologue and deallocated in the epilogue. Exercise 3.9 considers how to minimize the total space required. 3C H E C K YO U R U N D E R S TA N D I N G 12. What do we mean by the scope of a name-to-object binding? 13. Describe the difference between static and dynamic scoping. 14. What is elaboration? 15. What is a referencing environment? 16. Explain the closest nested scope rule. 17. What is the purpose of a scope resolution operator? 18. What is a static chain? What is it used for? 19. What are forward references? Why are they prohibited or restricted in many programming languages? 20. Explain the difference between a declaration and a definition. Why is the dis- tinction important? 3.3.4 Modules An important challenge in the construction of any large body of software is to divide the effort among programmers in such a way that work can proceed on multiple fronts simultaneously. This modularization of effort depends critically on the notion of information hiding, which makes objects and algorithms invisi- ble, whenever possible, to portions of the system that do not need them. Properly modularized code reduces the “cognitive load” on the programmer by minimiz- ing the amount of information required to understand any given portion of the 136 Chapter 3 Names, Scopes, and Bindings system. In a well-designed program the interfaces among modules are as “nar- row” (i.e., simple) as possible, and any design decision that is likely to change is hidden inside a single module. Information hiding is crucial for software maintenance (bug fixes and en- hancement), which tends to significantly outweigh the cost of initial development for most commercial software. In addition to reducing cognitive load, hiding re- duces the risk of name conflicts: with fewer visible names, there is less chance that a newly introduced name will be the same as one already in use. It also safe- guards the integrity of data abstractions: any attempt to access an object outside of the module to which it belongs will cause the compiler to issue an “undefined symbol” error message. Finally, it helps to compartmentalize run-time errors: if a variable takes on an unexpected value, we can generally be sure that the code that modified it is in the variable’s scope. Encapsulating Data and Subroutines Unfortunately, the information hiding provided by nested subroutines is limited to objects whose lifetime is the same as that of the subroutine in which they are hidden. When control returns from a subroutine, its local variables will no longer be live: their values will be discarded. We have seen a partial solution to this problem in the form of the save statement in Fortran and the static and own variables of C and Algol. Static variables allow a subroutine to have “memory”—to retain information from one invocation to the next—while protecting that memory from acciden- tal access or modification by other parts of the program. Put another way, static variables allow programmers to build single-subroutine abstractions. Unfortu- nately, they do not allow the construction of abstractions whose interface needs EXAMP L E 3.13 to consist of more than one subroutine. Consider, for example, a simple pseudo- Pseudorandom numbers as random number generator. In addition to the main rand_int routine, we might a motivation for modules want a set_seed routine that primes the generator for a specific pseudorandom sequence (e.g., for deterministic testing). We should like to make the state of the generator, which determines the next pseudorandom number, visible to both rand_int and set_seed , but hide it from the rest of the program. We can achieve this goal in many languages through use of a module construct.  Modules as Abstractions A module allows a collection of objects—subroutines, variables, types, and so on—to be encapsulated in such a way that (1) objects inside are visible to each other, but (2) objects on the inside may not be visible on the outside unless they are exported, and (3) objects on the outside may not be visible on the inside un- less they are imported. Import and export conventions vary significantly from one language to another, but in all cases, only the visibility of objects is affected; modules do not affect the lifetime of the objects they contain.  3.3 Scope Rules 137 #include namespace rand_mod { unsigned int seed = time(0); // initialize from current time of day const unsigned int a = 48271; const unsigned int m = 0x7fffffff; void set_seed(unsigned int s) { seed = s; } unsigned int rand_int() { return seed = (a * seed) % m; } } Figure 3.6 Pseudorandom number generator module in C++. Uses the linear congruential method, with a default seed taken from the current time of day. While there exist much better (more random) generators, this one is simple, and acceptable for many purposes. Modules were one of the principal language innovations of the late 1970s and early 1980s; they appeared in Clu7 (which called them clusters), Modula (1, 2, and 3), Turing, and Ada 83, among others. In more modern form, they also appear in Haskell, C++, Java, C#, and all the major scripting languages. Several languages, including Ada, Java, and Perl, use the term package instead of module. Others, including C++, C#, and PHP, use namespace. Modules can be emulated to some degree through use of the separate compilation facilities of C; we discuss this possibility in Section C 3.8. EXAMP L E 3.14 As an example of the use of modules, consider the pseudorandom number Pseudorandom number generator shown in Figure 3.6. As discussed in Sidebar 3.5, this module (names- generator in C++ pace) would typically be placed in its own file, and then imported wherever it is needed in a C++ program. Bindings of names made inside the namespace may be partially or totally hid- den (inactive) on the outside—but not destroyed. In C++, where namespaces can appear only at the outermost level of lexical nesting, integer seed would retain its value throughout the execution of the program, even though it is visible only to set_seed and rand_int. Outside the rand_mod namespace, C++ allows set_seed and rand_int to be accessed as rand_mod::set_seed and rand_mod::rand_int. The seed variable could also be accessed as rand_mod::seed , but this is probably not a good idea, and the need for the rand_mod prefix means it’s unlikely to happen by accident. 7 Barbara Liskov (1939–), the principal designer of Clu, is one of the leading figures in the history of abstraction mechanisms. A faculty member at MIT since 1971, she was also the principal de- signer of the Argus programming language, which combined language and database technology to improve the reliability and programmability of distributed systems. She received the ACM Turing Award in 2008. 138 Chapter 3 Names, Scopes, and Bindings The need for the prefix can be eliminated, on a name-by-name basis, with a using directive: using rand_mod::rand_int;... int r = rand_int(); Alternatively, the full set of names declared in a namespace can be made available at once: using namespace rand_mod;... set_seed(12345); int r = rand_int(); Unfortunately, such wholesale exposure of a module’s names increases both the likelihood of conflict with names in the importing context and the likelihood that objects like seed , which are logically private to the module, will be accessed accidentally.  Imports and Exports Some languages allow the programmer to specify that names exported from mod- ules be usable only in restricted ways. Variables may be exported read-only, for example, or types may be exported opaquely, meaning that variables of that type may be declared, passed as arguments to the module’s subroutines, and possibly compared or assigned to one another, but not manipulated in any other way. Modules into which names must be explicitly imported are said to be closed scopes. By extension, modules that do not require imports are said to be open scopes. Imports serve to document the program: they increase modularity by requiring a module to specify the ways in which it depends on the rest of the pro- gram. They also reduce name conflicts by refraining from importing anything that isn’t needed. Modules are closed in Modula (1, 2, and 3) and Haskell. C++ is representative of an increasingly common option, in which names are auto- matically exported, but are available on the outside only when qualified with the module name—unless they are explicitly “imported” by another scope (e.g., with the C++ using directive), at which point they are available unqualified. This op- tion, which we might call selectively open modules, also appears in Ada, Java, C#, and Python, among others. Modules as Managers Modules facilitate the construction of abstractions by allowing data to be made private to the subroutines that use them. When used as in Figure 3.6, however, EXAMP L E 3.15 each module defines a single abstraction. Continuing our previous example, there Module as “manager” for a are times when it may be desirable to have more than one pseudorandom num- type ber generator. When debugging a game, for example, we might want to obtain deterministic (repeatable) behavior in one particular game module (a particular  3.3 Scope Rules 139 #include namespace rand_mgr { const unsigned int a = 48271; const unsigned int m = 0x7fffffff; typedef struct { unsigned int seed; } generator; generator* create() { generator* g = new generator; g->seed = time(0); return g; } void set_seed(generator* g, unsigned int s) { g->seed = s; } unsigned int rand_int(generator* g) { return g->seed = (a * g->seed) % m; } } Figure 3.7 Manager module for pseudorandom numbers in C++. character, perhaps), regardless of uses of pseudorandom numbers elsewhere in the program. If we want to have several generators, we can make our namespace a “manager” for instances of a generator type, which is then exported from the module, as shown in Figure 3.7. The manager idiom requires additional subrou- tines to create/initialize and possibly destroy generator instances, and it requires that every subroutine ( set_seed , rand_int , create ) take an extra parameter, to specify the generator in question. Given the declarations in Figure 3.7, we could create and use an arbitrary num- ber of generators: using rand_mgr::generator; generator *g1 = rand_mgr::create(); generator *g2 = rand_mgr::create();... using rand_mgr::rand_int; int r1 = rand_int(g1); int r2 = rand_int(g2); In more complex programs, it may make sense for a module to export several related types, instances of which can then be passed to its subroutines.  3.3.5 Module Types and Classes An alternative solution to the multiple instance problem appeared in Eu- clid, which treated each module as a type, rather than a simple encapsulation 140 Chapter 3 Names, Scopes, and Bindings construct. Given a module type, the programmer could declare an arbitrary number of similar module objects. As it turns out, the classes of modern object- oriented languages are an extension of module types. Access to a module instance typically looks like access to an object, and we can illustrate the ideas in any EXAMP L E 3.16 object-oriented language. For our C++ pseudorandom number example, the A pseudorandom number syntax generator type generator *g = rand_mgr::create();... int r = rand_int(g); might be replaced by rand_gen *g = new rand_gen();... int r = g->rand_int(); where the rand_gen class is declared as in Figure 3.8. Module types or classes allow the programmer to think of the rand_int routine as “belonging to” the generator, rather than as a separate entity to which the generator must be passed D E S I G N & I M P L E M E N TAT I O N 3.5 Modules and separate compilation One of the hallmarks of a good abstraction is that it tends to be useful in multi- ple contexts. To facilitate code reuse, many languages make modules the basis of separate compilation. Modula-2 actually provided two different kinds of modules: one (external modules) for separate compilation, the other (internal modules) for textual nesting within a larger scope. Experience with these op- tions eventually led Niklaus Wirth, the designer of Modula-2, to conclude that external modules were by far the more useful variety; he omitted the internal version from his subsequent language, Oberon. Many would argue, however, that internal modules find their real utility only when extended with instan- tiation and inheritance. Indeed, as noted near the end of this section, many object-oriented languages provide both modules and classes. The former sup- port separate compilation and serve to minimize name conflicts; the latter are for data abstraction. To facilitate separate compilation, modules in many languages (Modula-2 and Oberon among them) can be divided into a declaration part (header) and an implementation part (body), each of which occupies a separate file. Code that uses the exports of a given module can be compiled as soon as the header exists; it is not dependent on the body. In particular, work on the bodies of cooperating modules can proceed concurrently once the headers exist. We will return to the subjects of separate compilation and code reuse in Sections C 3.8 and 10.1, respectively.  3.3 Scope Rules 141 class rand_gen { unsigned int seed = time(0); const unsigned int a = 48271; const unsigned int m = 0x7fffffff; public: void set_seed(unsigned int s) { seed = s; } unsigned int rand_int() { return seed = (a * seed) % m; } }; Figure 3.8 Pseudorandom number generator class in C++. as an argument. Conceptually, there is a dedicated rand_int routine for every generator ( rand_gen object). In practice, of course, it would be highly wasteful to create multiple copies of the code. As we shall see in Chapter 10, rand_gen instances really share a single pair of set_seed and rand_int routines, and the compiler arranges for a pointer to the relevant instance to be passed to the routine as an extra, hidden parameter. The implementation turns out to be very similar to that of Figure 3.7, but the programmer need not think of it that way.  Object Orientation The difference between module types and classes is a powerful pair of features found together in the latter but not the former—namely, inheritance and dynamic method dispatch.8 Inheritance allows new classes to be defined as extensions or refinements of existing classes. Dynamic method dispatch allows a refined class to override the definition of an operation in its parent class, and for the choice among definitions to be made at run time, on the basis of whether a particular object belongs to the child class or merely to the parent. Inheritance facilitates a programming style in which all or most operations are thought of as belonging to objects, and in which new objects can inherit many of their operations from existing objects, without the need to rewrite code. Classes have their roots in Simula-67, and were further developed in Smalltalk. They ap- pear in many modern languages, including Eiffel, OCaml, C++, Java, C#, and sev- eral scripting languages, notably Python and Ruby. Inheritance mechanisms can also be found in certain languages that are not usually considered object-oriented, including Modula-3, Ada 95, and Oberon. We will examine inheritance, dynamic dispatch, and their impact on scope rules in Chapter 10 and in Section 14.4.4. 8 A few languages—notably members of the ML family—have module types with inheritance—but still without dynamic method dispatch. Modules in most languages are missing both features. 142 Chapter 3 Names, Scopes, and Bindings Module types and classes (ignoring issues related to inheritance) require only simple changes to the scope rules defined for modules in Section 3.3.4. Every instance A of a module type or class (e.g., every rand_gen ) has a separate copy of the module or class’s variables. These variables are then visible when executing one of A ’s operations. They may also be indirectly visible to the operations of some other instance B if A is passed as a parameter to one of those operations. This rule makes it possible in most object-oriented languages to construct binary (or more-ary) operations that can manipulate the variables (fields) of more than one instance of a class. Modules Containing Classes While there is a clear progression from modules to module types to classes, it is not necessarily the case that classes are an adequate replacement for modules in EXAMP L E 3.17 all cases. Suppose we are developing an interactive “first person” game. Class Modules and classes in a hierarchies may be just what we need to represent characters, possessions, build- large application ings, goals, and a host of other data abstractions. At the same time, especially on a project with a large team of programmers, we will probably want to divide the functionality of the game into large-scale subsystems such as graphics and ren- dering, physics, and strategy. These subsystems are really not data abstractions, and we probably don’t want the option to create multiple instances of them. They are naturally captured with traditional modules, particularly if those modules are designed for separate compilation (Section 3.8). Recognizing the need for both multi-instance abstractions and functional subdivision, many languages, includ- ing C++, Java, C#, Python, and Ruby, provide separate class and module mecha- nisms.  3.3.6 Dynamic Scoping In a language with dynamic scoping, the bindings between names and objects depend on the flow of control at run time, and in particular on the order in which subroutines are called. In comparison to the static scope rules discussed in the previous section, dynamic scope rules are generally quite simple: the “current” binding for a given name is the one encountered most recently during execution, and not yet destroyed by returning from its scope. Languages with dynamic scoping include APL, Snobol, Tcl, TEX (the type- setting language with which this book was created), and early dialects of Lisp [MAE+ 65, Moo78, TM81] and Perl.9 Because the flow of control cannot in gen- eral be predicted in advance, the bindings between names and objects in a lan- guage with dynamic scoping cannot in general be determined by a compiler. As a 9 Scheme and Common Lisp are statically scoped, though the latter allows the programmer to specify dynamic scoping for individual variables. Static scoping was added to Perl in version 5; the programmer now chooses static or dynamic scoping explicitly in each variable declaration. (We consider this choice in more detail in Section 14.4.1.)  3.3 Scope Rules 143 1. n : integer – – global declaration 2. procedure first( ) 3. n := 1 4. procedure second( ) 5. n : integer – – local declaration 6. first( ) 7. n := 2 8. if read integer( ) > 0 9. second( ) 10. else 11. first( ) 12. write integer(n) Figure 3.9 Static versus dynamic scoping. Program output depends on both scope rules and, in the case of dynamic scoping, a value read at run time. result, many semantic rules in a language with dynamic scoping become a matter of dynamic semantics rather than static semantics. Type checking in expressions and argument checking in subroutine calls, for example, must in general be de- ferred until run time. To accommodate all these checks, languages with dynamic scoping tend to be interpreted, rather than compiled. EXAMP L E 3.18 Consider the program in Figure 3.9. If static scoping is in effect, this program Static vs dynamic scoping prints a 1. If dynamic scoping is in effect, the output depends on the value read at line 8 at run time: if the input is positive, the program prints a 2; otherwise it prints a 1. Why the difference? At issue is whether the assignment to the variable n at line 3 refers to the global variable declared at line 1 or to the local variable declared at line 5. Static scope rules require that the reference resolve to the closest lexically enclosing declaration, namely the global n. Procedure first changes n to 1, and line 12 prints this value. Dynamic scope rules, on the other hand, require that we choose the most recent, active binding for n at run time. D E S I G N & I M P L E M E N TAT I O N 3.6 Dynamic scoping It is not entirely clear whether the use of dynamic scoping in Lisp and other early interpreted languages was deliberate or accidental. One reason to think that it may have been deliberate is that it makes it very easy for an interpreter to look up the meaning of a name: all that is required is a stack of declarations (we examine this stack more closely in Section C 3.4.2). Unfortunately, this simple implementation has a very high run-time cost, and experience indicates that dynamic scoping makes programs harder to understand. The modern consen- sus seems to be that dynamic scoping is usually a bad idea (see Exercise 3.17 and Exploration 3.36 for two exceptions). 144 Chapter 3 Names, Scopes, and Bindings We create a binding for n when we enter the main program. We create another when and if we enter procedure second. When we execute the assignment state- ment at line 3, the n to which we are referring will depend on whether we entered first through second or directly from the main program. If we entered through second , we will assign the value 1 to second ’s local n. If we entered from the main program, we will assign the value 1 to the global n. In either case, the write at line 12 will refer to the global n , since second ’s local n will be destroyed, along with its binding, when control returns to the main program.  EXAMP L E 3.19 With dynamic scoping, errors associated with the referencing environment Run-time errors with may not be detected until run time. In Figure 3.10, for example, the declara- dynamic scoping tion of local variable max score in procedure foo accidentally redefines a global variable used by function scaled score , which is then called from foo. Since the global max score is an integer, while the local max score is a floating-point num- ber, dynamic semantic checks in at least some languages will result in a type clash message at run time. If the local max score had been an integer, no error would have been detected, but the program would almost certainly have produced in- correct results. This sort of error can be