1-8-scope.pdf

Department of Computer Science CS 3304 Comparative Languages Module 1 Scope ©...

Department of Computer Science CS 3304 Comparative Languages Module 1 Scope © 2024 Denis Gracanin 1 Department of Computer Science Join the College of Engineering & VT’s Innovation Campus You will have the opportunity to learn more about completing the Masters of Engineering in Computer Science and Computer Engineering program in as little as 2-3 semesters. Free Pizza and VT SWAG will be provided! All participants will be eligible for an application fee waiver. Options To Register: Scan the QR Code Visit: https://applyto.graduateschool.vt.edu/register/ MEngSept24 Text “Register”: 540-835-4957 © 2024 Denis Gracanin 2 1  Department of Computer Science Introduction Recap Homework 2 Scope CS 3304 Module 1: Scope 3 3 Department of Computer Science Recap Symbol table: a data abstraction, a dictionary, used for compiling statically scoped programs (keeps track of names) § Insert a new mapping: a name-to-object mapping § Look up the information that is already present for a given name Static scope: increased complexity since a given name corresponds to different objects The visibility handled by augmenting the symbol table with enter_scope and leave_scope operations Dynamic scope: a symbol table also can be used as an association list or a central reference table CS 3304 Module 1: Scope 4 4 2  Department of Computer Science Implementation Cost Implementation complexity or run-time cost can cause that a feature is not included in a language Simple features can have surprising implications Tradeoffs between semantic utility and ease of implementation CS 3304 Module 1: Scope 5 5 Department of Computer Science Homework 2 6 3  Department of Computer Science Homework 2 Discussion: Concepts 1. Compute the weakest precondition for each of the following constructs and their postconditions: (15 points, 5 points each) 2. Perform the pairwise disjointness test for the following grammar rule: (15 points, 5 points each) 3. Show a trace of the recursive descent parser given in Section 4.4.1 for the string: (15 points) 4. Consider the following program: (15 points) § What is the output for static scope and deep binding? Explain (5 points) § What is the output for static scope and shallow binding? Explain (5 points) § What is the output for dynamic scope and shallow binding? Explain (5 points) CS 3304 Module 1: Scope 7 7 Department of Computer Science Homework 2 Discussion: ANTLR Review the provided examples 1. Implement the semantic for the ANTLR grammar solution for Homework 1 ANTLR Problem 2: (20 points) § Use floating point arithmetic (handle division by zero) § In each statement the value of a variable is 0 § When the input is correct, the program must print within square brackets a comma separated array of values for each assignment statement 2. Modify the ANTLR grammar and code in ANTLR Problem 1 as follows: (20 points) § Support negative numbers. § Use integer and floating point arithmetic § A variable used in an expression must be defined in previous statements § Process input lines by line rather than all at once CS 3304 Module 1: Scope 8 8 4  Department of Computer Science ANTLR Project Start (using Visitor) Create a new folder Open the folder in VS Code In the root project folder create empty files: § grammar file, e.g., HW2.g4 (start with Homework 1 ANTLR Problem 2 solution) § main Java class file, e.g., HW2.java (lecture 1.7 example code) § visitor class, e.g., HW2FullVisitor.java (by extending the base visitor class) Add ANTLR jar file to Java Projects Referenced Libraries Modify settings.json in.vscode folder to include: "antlr4.generation.mode": "external", "antlr4.generation.visitors": true, "antlr4.generation.listeners": false, "antlr4.generation.outputDir": ".", Start populating the files CS 3304 Module 1: Scope 9 9 Department of Computer Science Scope 10 5  Department of Computer Science Name, Scope, and Binding A name is a mnemonic character string used to represent something else: § Most names are identifiers § Symbols (like '+') can also be names A binding is an association between two things, such as a name and the thing it names The scope of a binding is the part of the program (textually) in which the binding is active CS 3304 Module 1: Scope 11 11 Department of Computer Science Name, Scope, and Binding A name is a mnemonic character string used to represent something else: § Most names are identifiers § Symbols (like '+') can also be names A binding is an association between two things, such as a name and the thing it names The scope of a binding is the part of the program (textually) in which the binding is active CS 3304 Module 1: Scope 12 12 6  Department of Computer Science Variable Attributes: Scope The scope of a variable is the range of statements over which it is visible The local variables of a program unit are those that are declared in that unit The nonlocal variables of a program unit are those that are visible in the unit but not declared there Global variables are a special category of nonlocal variables The scope rules of a language determine how references to names are associated with variables CS 3304 Module 1: Scope 13 13 Department of Computer Science Scope Rules Scope: a program section of maximal size in which no bindings change, or at least no re-declarations permitted In most languages with subroutines, we open a new scope on subroutine entry: § Create bindings for new local variables § Deactivate bindings for global variables that are re-declared (these variable are said to have a “hole” in their scope) § Make references to variables § On subroutine exit destroy bindings for local variables and reactivate bindings for the deactivated global variables Statically scoped: bindings based on purely textual rules (most languages, e.g., C, Java, C++) Dynamically scoped: bindings depend on the flow of execution during run time (APL, Snobol, Tcl, early Lisp) CS 3304 Module 1: Scope 14 14 7  Department of Computer Science Elaboration Elaboration is 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 Ada: storage may be allocated, tasks started, or exceptions propagated as a result of the elaboration of declarations CS 3304 Module 1: Scope 15 15 Department of Computer Science Static Scope Based on program text To connect a name reference to a variable, you (or the compiler) must find the declaration Search process: search declarations, first locally, then in increasingly larger enclosing scopes, until one is found for the given name Enclosing static scopes (to a specific scope) are called its static ancestors; the nearest static ancestor is called a static parent Some languages allow nested subprogram definitions, which create nested static scopes (e.g., Ada, JavaScript, Common Lisp, Scheme, Fortran 2003+, F#, and Python) CS 3304 Module 1: Scope 16 16 8  Department of Computer Science Scope: Hiding Variables can be hidden from a unit by having a “closer” variable with the same name CS 3304 Module 1: Scope 17 17 Department of Computer Science Blocks A method of creating static scopes inside program units: from ALGOL 60 Example in C: void sub() { int count; while (…) { int count; count++; … } … } Note: legal in C and C++, but not in Java and C#, too error-prone CS 3304 Module 1: Scope 18 18 9  Department of Computer Science The LET Construct: Scheme Most functional languages include some form of let construct A let construct has two parts: § The first part binds names to values § The second part uses the names defined in the first part In Scheme: (LET ( (name1 expression1) … (namen expressionn) ) CS 3304 Module 1: Scope 19 19 Department of Computer Science The LET Construct: ML and F# In ML: let val name1 = expression1 … val namen = expressionn in expression end; In F#: § First part: let left_side = expression § (left_side is either a name or a tuple pattern) § All that follows is the second part CS 3304 Module 1: Scope 20 20 10  Department of Computer Science Declaration Order C99, C++, Java, and C# allow variable declarations to appear anywhere a statement can appear In C99, C++, and Java, the scope of all local variables is from the declaration to the end of the block In the official documentation of C#, the scope of any variable declared in a block is the whole block, regardless of the position of the declaration in the block: § However, that is misleading, because a variable still must be declared before it can be used In C++, Java, and C#, variables can be declared in for statements: § The scope of such variables is restricted to the for construct CS 3304 Module 1: Scope 21 21 Department of Computer Science Global Scope 1/2 C, C++, PHP, and Python support a program structure that consists of a sequence of function definitions in a file: § These languages allow variable declarations to appear outside function definitions C and C++have both declarations (just attributes) and definitions (attributes and storage): § A declaration outside a function definition specifies that it is defined in another file CS 3304 Module 1: Scope 22 22 11  Department of Computer Science Global Scope 2/2 PHP: § Programs are embedded in HTML markup documents, in any number of fragments, some statements and some function definitions § The scope of a variable (implicitly) declared in a function is local to the function § The scope of a variable implicitly declared outside functions is from the declaration to the end of the program, but skips over any intervening functions o Global variables can be accessed in a function through the $GLOBALS array or by declaring it global Python: § A global variable can be referenced in functions, but can be assigned in a function only if it has been declared to be global in the function CS 3304 Module 1: Scope 23 23 Department of Computer Science Static Scoping Static (lexical) scope rules: a scope is defined in terms of the physical (lexical) structure of the program: § The determination of scopes can be made by the compiler § All bindings for identifiers resolved by examining the program § Typically, we choose the most recent, active binding made at compile time § Most compiled languages, C and Pascal included, employ static scope rules Examples: § Early Basic: single, global scope and few hundred possible names § Pre-Fortran 90: global and local scope o If variable not declared, implicit declaration based on name § Static (own, save-ed): variable has a lifetime spanning the entire execution of the program CS 3304 Module 1: Scope 24 24 12  Department of Computer Science Nested Subroutines The classical example of static scope rules is the most closely nested rule used in block structured languages such as Algol 60 and Pascal (nested subroutines). An identifier is known in the scope in which it is declared and in each enclosed scope, unless it is re-declared in an enclosed scope. To resolve a reference to an identifier, we examine the local scope and statically enclosing scopes until a binding is found. 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. § Accessing the outer meaning of a name by applying a qualifier or scope resolution operator. CS 3304 Module 1: Scope 25 25 Department of Computer Science Nonlocal Objects & Static Chains Access to non-local variables static links: § Each frame points to the frame of the (correct instance of) the routine inside which it was declared § In the absence of formal subroutines, correct means closest to the top of the stack § You access a variable in a scope k levels out by following k static links and then using the known offset within the frame thus found CS 3304 Module 1: Scope 26 26 13  Department of Computer Science Declaration Order All declarations appear at the beginning of the scope: some early languages such as Algol-60, Lisp The names must be declared before the use: Pascal Relaxing declare before the use: C++ and Java The scope of a declaration is the entire block in which it appears: Modula-3 No declarations within a block: Python Recursive types and subroutines: names have to be declared before they can be used. If declaration is not complete enough to be a definition, a separate definition must appear Nested blocks: local variables also can be defined at the top of any block CS 3304 Module 1: Scope 27 27 Department of Computer Science Examples Whole block scope in C#: class A { const int N = 10; void foo() { const int M = N; // inner N before declared const int N = 20; Declaration order in Scheme: (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 Declarations vs definitions in C: § Recursive types and subroutines struct manager; struct employee { struct manager *boss; struct employee *next_employee; …}; struct manager { struct employee *first_employee; …}; CS 3304 Module 1: Scope 28 28 14  Department of Computer Science Static Scoping Evaluation Works well in many situations Problems: § In most cases, too much access is possible § As a program evolves, the initial structure is destroyed and local variables often become global; subprograms also gravitate toward become global, rather than nested CS 3304 Module 1: Scope 29 29 Department of Computer Science Dynamic Scoping Rules The key idea in static scope rules is that bindings are defined by the physical (lexical) structure of the program With dynamic scope rules, bindings depend on the current state of program execution: § They cannot always be resolved by examining the program because they are dependent on calling sequences § To resolve a reference, we use the most recent, active binding made at run time Dynamic scope rules are usually encountered in interpreted languages: § Early LISP dialects assumed dynamic scope rules Such languages do not normally have type checking at compile time because type determination isn’t always possible when dynamic scope rules are in effect CS 3304 Module 1: Scope 30 30 15  Department of Computer Science Dynamic Scope Evaluation Based on calling sequences of program units, not their textual layout (temporal versus spatial) References to variables are connected to declarations by searching back through the chain of subprogram calls that forced execution to this point CS 3304 Module 1: Scope 31 31 Department of Computer Science Example: Static vs. Dynamic program scopes (input, output); var a : integer; procedure first; begin a := 1; end; procedure second; var a : integer; begin first; end; begin a := 2; second; write(a); end. If static scope rules are in effect (as would be the case in Pascal), the program prints 1 If dynamic scope rules are in effect, the program prints 2 The issue is whether the assignment to the variable a in procedure first changes the variable a declared in the main program or the variable a declared in procedure second CS 3304 Module 1: Scope 32 32 16  Department of Computer Science Using Scoping Rules Static scope rules require that the reference resolve to the most recent, compile- time binding, i.e., global variable a Dynamic scope rules, on the other hand, require that we choose the most recent, active binding at run time: § Perhaps the most common use of dynamic scope rules is to provide implicit parameters to subroutines § This is generally considered bad programming practice nowadays: o Alternative mechanisms exist: static variables that can be modified by auxiliary routines or default and optional parameters § At run time a binding for a when in main program § Another binding for a when in procedure second: o The most recent, active binding when executing procedure first o Modify variable local to procedure second, not global variable o However, we write the global variable because the variable a local to procedure second is no longer active CS 3304 Module 1: Scope 33 33 Department of Computer Science Scope Example Static scoping: § Reference to x in sub2 is to big's x Dynamic scoping: § Reference to x in sub2 is to sub1’s x function big() { function sub1() { var x = 7; sub2(); } function sub2() { var y = x; var z = 3; } var x = 3; sub1(); } CS 3304 Module 1: Scope 34 34 17  Department of Computer Science Scope Example Evaluation of Dynamic Scoping: § Advantage: convenience § Disadvantages: o While a subprogram is executing, its variables are visible to all subprograms it calls o Impossible to statically type check o Poor readability: it is not possible to statically determine the type of a variable CS 3304 Module 1: Scope 35 35 Department of Computer Science Scope and Lifetime Scope and lifetime are sometimes closely related, but are different concepts Consider a static variable in a C or C++ function CS 3304 Module 1: Scope 36 36 18  Department of Computer Science Referencing Environments The referencing environment of a statement is the collection of all names that are visible in the statement In a static-scoped language, it is the local variables plus all of the visible variables in all of the enclosing scopes A subprogram is active if its execution has begun but has not yet terminated In a dynamic-scoped language, the referencing environment is the local variables plus all visible variables in all active subprograms CS 3304 Module 1: Scope 37 37 Department of Computer Science Named Constants A named constant is a variable that is bound to a value only when it is bound to storage Advantages: readability and modifiability Used to parameterize programs The binding of values to named constants can be either static (called manifest constants) or dynamic Languages: § C++ and Java: expressions of any kind, dynamically bound § C# has two kinds, readonly and const: o The values of const named constants are bound at compile time o The values of readonly named constants are dynamically bound CS 3304 Module 1: Scope 38 38 19  Department of Computer Science Parameters that are Subprogram Names: Referencing Environment Shallow binding: § The environment of the call statement that enacts the passed subprogram § Most natural for dynamic-scoped languages Deep binding: § The environment of the definition of the passed subprogram § Most natural for static-scoped languages Ad hoc binding: § The environment of the call statement that passed the subprogram CS 3304 Module 1: Scope 39 39 Department of Computer Science Summary Strong typing means detecting all type errors Scope rules can be static (lexical) or dynamic (runtime) Implementation complexity or run-time cost can cause that a feature is not included in a language CS 3304 Module 1: Scope 40 40 20