TerminologyEnvironments and Static ScopingDynamic ScopingCompiler Symbol TablesLifetimeStatic and Dynamic TypingType EquivalenceCoercionOverloadingUnification (aka Pattern-Matching)Type inferenceOverload resolution in AdaUNIVERSITY OF CALIFORNIADepartment of Electrical Engineeringand Computer SciencesComputer Science DivisionCS 164 P. N. HilfingerSpring 2005Static Analysis: Scop e and Types1 TerminologyPrograms, in general, are simply collections of definitions of terms, which we often call decla-rations1. Each declaration may use other declarations, referring to them by the names theyintroduce. In programming languages, the scope of a declaration that introd uces some nameis the portion of the program in which the meaning (or a possible meaning) of that name isthe one given by the declaration. Many authors (from less distinguished institutions) referloosely to the scope of a name as opposed to the scope of a declaration. The term “scopeof a name,” however, is clearly an in adequate notion, since the same name may be used inmultiple declarations.2 Environments and Static ScopingIn CS61A, you saw an abstract model of both scope rules and rules about the extent orlifetime of variables. In this model, there is, at any given time, an environment consisting ofa linked sequen ce of frames. Each frame contains bindings of names to slots that can containvalues. The value contained in a slot may be a function; such a value consists of a pair ofvalues: the body (or code) of the function and the environment that gives the meaning ofnames used by the function when it executes.Figure 1 illustrates the scope of declarations in C (or Java or C++). The sections of textcontrolled by the various declarations of variables, parameters, and fun ctions are indicated bythe brackets on the right. Brackets on the left indicate declarative reg i ons—portions of thetext of a program th at bound the scopes of the declarations within. Declarations in C obeythe rule that their scope runs from the declaration to the end of the innerm ost declarativeregion that contains them. The declarative regions in C are the boundaries of the source file1C and C++ distinguish declarations, which introduce (or re-introduce) names and some information aboutthem from definitions, which provide complete information about names. A declaration of a function tells usits name, parameter types, and return type. A definition of a function tells us all this and also gives its body.In these notes, I will use th e t erm decl aration to refer to both of these functions.1Static Analysis: S cope and Types 2itself, the boundaries of each b lock ({...}), the parameter list and body of each function,and a few others.The environment diagram in Figure 1 shows a snapshot of the program during its execu-tion. To find the current meaning (binding) of any identifier, one traverses the environmentstructure from the current environment, following the pointers (links) to enclosing environ-ments, until one finds the desired identifier. Each frame corresponds to an instance of somedeclarative region in the program. When a function is called, a frame is created for thatcall that contains the variables declared in that fu nction with a static link that is set f romthe environment part of the function (the leftmost “bubbles” in the figure). Inn er blo cks aretreated like inner functions, and have static links that point to instances of their enclosingblocks2. S ince the language in the example is C, all named functions’ environments are theglobal environment, encompassing all declarations in a given source file.As it was presented in CS61A, these environments are dynamic entities, constructed duringexecution time. However, it is a property of most languages—including C, C++, Java, Pascal,Ada, Scheme, the Algol family, COBOL, PL/1, Fortran, and many others—that at any givenpoint in a program, the chain of environment frames starting at the current environment isalways the same at that point in the program, except for the actual values in the slots ofenvironment. That is, the number of f rames in the chain and the names in each of theseframes is always the same, and depends only on where in the program we are. We say thatthese languages use use static scoping (also known as lexical scoping), meaning that theirscope rules determine static regions of text that are independent of any particular executionof the program. Th e links between frames in this case are called static links.To see why this property holds (the constancy or staticness of the environment chain),consider how the links get s et in the first place. When a function value is created in a staticallyscoped language (i.e., as opposed to being called), its value is constructed from a code pointerand an environment pointer. The environment pointer, furth ermore, is always the currentframe, which is a frame containing declarations f rom the function whose text contains thedefinition of the function. The environment pointer, in other words, depends only on wherein the text of the p rogram the function is defined, and points to the same kind of frame(same names) each time. When a function is called, a new current frame is created to containdeclarations of the function’s parameters and local variables, and its link (in these languages)is copied fr om the environment pointer of the function being called. Thus, every time a framefor a given function is created, its link always points to a frame with the same structure.3 Dynamic ScopingAn alternative rule (found in L ogo, APL, SNOBOL, and early versions of Lisp, APL, amongother languages) defines the scope of a declaration as pr oceeding from the time at whichthe declaration is “executed” (or elaborated, to use Algol 68 terminology) to the time itterminates. Under dynamic scoping, the link of an environment frame for a function is equalto the current frame at the time of the call. To see the distinction, consider the following2WARNI NG: This is a conceptual description. The actual execution of a program involves different datastructures, as we will see in later lecturesStatic Analysis: S cope and Types 3 } S2; int z=13; int x=10; if (...) { S1;{void f (int y)int x=42; S3;pointersenvironmentlinks (static)current frameDeclarative RegionsBlockE3:E2:E1:E0:envglobalScopes double x=3.14;FunctionFile... } f (3);{void g ()}y: 3z: 13x: 10g: f: x: 42x: 3.14 FramesEnvironmentcode for gcode for fFigure 1: Scope
View Full Document
Unlocking...