Scope Rules (Section 3.3)Binding Time (Review)Binding Time ExampleSlide 4ScopeReferencing EnvironmentScope RulesStatic ScopeNested Subroutines Closest Nested Subroutine RuleStorage Management (revisited)Stack-based AllocationStatic LinksNested Subroutines Determining ScopeAn ExampleStatic Scope VariantsOther Static Scope VariantsEvolution of Data Abstraction FacilitiesDynamic Scope RulesDynamic ScopeWhy Dynamic ScopeAccessing Variables with Dynamic ScopeImplementation of Dynamic Scoping11Scope RulesScope Rules(Section 3.3)(Section 3.3)CSCI 431 Programming LanguagesCSCI 431 Programming LanguagesFall 2003Fall 2003A compilation of material developed by Felix A compilation of material developed by Felix Hernandez-Campos and Michael ScottHernandez-Campos and Michael Scott22Binding Time (Review)Binding Time (Review)•A A bindingbinding is an association between two things is an association between two things–E.g. Name of an object and the objectE.g. Name of an object and the object•Binding timeBinding time is the time at which a binding is is the time at which a binding is createdcreated–Language design timeLanguage design time–Language implementationLanguage implementation–Program writing timeProgram writing time–Compile TimeCompile Time–Link TimeLink Time–Load TimeLoad Time–Run TimeRun Time33Binding Time ExampleBinding Time Example•Java programJava program•What is the binding time ofWhat is the binding time of–Value of argument x?Value of argument x?–Set of values of argument x?Set of values of argument x?–Type of argument x?Type of argument x?–Set of types of argument x?Set of types of argument x?–Properties of operator +?Properties of operator +?publicpublic staticstatic intint increment( increment(intint x) { x) {returnreturn x + 1; x + 1;}}44Binding Time ExampleBinding Time Example•Perl programPerl program•What is the binding time ofWhat is the binding time of–Value of argument @_?Value of argument @_?–Set of values of argument @_?Set of values of argument @_?–Type of argument @_?Type of argument @_?–Set of types of argument @_?Set of types of argument @_?–Properties of operator +?Properties of operator +?subsub increment { increment {returnreturn shift @_ + 1; shift @_ + 1;}}55ScopeScope•ScopeScope is the textual region of a program in which a is the textual region of a program in which a binding is activebinding is active•The word 'scope' used as a noun is a program section The word 'scope' used as a noun is a program section of maximal size in which no bindings change.of maximal size in which no bindings change.–In most languages with subroutines, we OPEN a new In most languages with subroutines, we OPEN a new scope on subroutine entry.scope on subroutine entry.•Algol 68 introduced the term Algol 68 introduced the term elaborationelaboration for the for the process of creating bindings when entering a scope. process of creating bindings when entering a scope. Elaboration time is a useful concept.Elaboration time is a useful concept.66Referencing EnvironmentReferencing Environment•The referencing environment (of a statement or The referencing environment (of a statement or expression) is the set of active bindings. expression) is the set of active bindings. •A referencing environment corresponds to a A referencing environment corresponds to a collection of scopes that are examined (in order) to collection of scopes that are examined (in order) to find a binding. find a binding.77Scope RulesScope Rules•Programming languages implementProgramming languages implement–StaticStatic Scoping Scoping: active bindings are determined using the : active bindings are determined using the text of the program. The determination of scopes can be text of the program. The determination of scopes can be made by the compiler.made by the compiler.»Most recent scan of the program from top to bottomMost recent scan of the program from top to bottom»Closest nested subroutine ruleClosest nested subroutine rule»Most compiled languages employ static scope rulesMost compiled languages employ static scope rules–DynamicDynamic Scoping Scoping: active bindings are determined by the : active bindings are determined by the flow of execution at run time (i.e., the call sequence).flow of execution at run time (i.e., the call sequence).»The determination of scopes can NOT be made by the compiler.The determination of scopes can NOT be made by the compiler.»Dynamic scope rules are usually encountered in interpreted Dynamic scope rules are usually encountered in interpreted languages; in particular, early LISP dialects assumed dynamic languages; in particular, early LISP dialects assumed dynamic scope rules. scope rules.88Static ScopeStatic Scope•The classical example of static scope rules is the The classical example of static scope rules is the most closely nested rule used in block structured most closely nested rule used in block structured languages such as Algol 60 and Pascal. languages such as Algol 60 and Pascal. •An identifier is known in the scope in which it is An identifier is known in the scope in which it is declared and in each enclosed scope, unless it is declared and in each enclosed scope, unless it is redeclared in an enclosed scope. redeclared in an enclosed scope. •To resolve a reference to an identifier, we examine the To resolve a reference to an identifier, we examine the local scope and statically enclosing scopes until a local scope and statically enclosing scopes until a binding is found.binding is found.99Nested SubroutinesNested SubroutinesClosest Nested Subroutine RuleClosest Nested Subroutine Rule1010Storage Management (revisited)Storage Management (revisited)• Static allocation for:Static allocation for:– code, globals, "own" variables, explicit constants code, globals, "own" variables, explicit constants – scalars may be stored in the instructions themselvesscalars may be stored in the instructions themselves• Central stack for:Central stack for:– parameters, local variables, temporaries, bookkeeping informationparameters, local variables, temporaries, bookkeeping information• Why a stack?Why a stack?– allocate space for recursive routinesallocate space for recursive routines» (not necessary in FORTRAN, etc)(not necessary in FORTRAN, etc)– reuse spacereuse space» (useful in any language)(useful in any language)•Heap for:Heap for:– dynamic