pl11ch5.pdf

Concepts of Programming Languages Dr. Mohammed A. Awadallah First semester 2022/2023 Chapter 5 Names, Bindings, and Scopes ISBN 0-321-49362-1 Chapter 5 Topics Introduction Names Variables The Concept of Binding Scope...

Concepts of Programming Languages Dr. Mohammed A. Awadallah First semester 2022/2023 Chapter 5 Names, Bindings, and Scopes ISBN 0-321-49362-1 Chapter 5 Topics Introduction Names Variables The Concept of Binding Scope Scope and Lifetime Referencing Environments Named Constants Copyright © 2015 Pearson. All rights reserved. 1-3 Introduction Imperative languages are abstractions of von Neumann architecture. Architecture components: – Memory Stores both instructions and data – Processor Provides operations for modifying the contents of the memory The abstractions in a language for the memory cells of the machine are variables. Copyright © 2015 Pearson. All rights reserved. 1-4 Introduction In some cases, the characteristics of the abstractions are very close to the characteristics of the cells. – integer variable represent in 4 bytes in Java In other cases, the abstractions are far removed from the organization of the hardware memory, – three-dimensional array, which requires a software mapping function to support the abstraction. Variables are characterized by attributes – To design a type, must consider scope, lifetime, type checking, initialization, and type compatibility Copyright © 2015 Pearson. All rights reserved. 1-5 Names Design issues for names: – Are names case sensitive? – Are special words reserved words or keywords? A name is a string of characters used to identify some entity in a program. Names in most programming languages have the same form: a letter followed by a string consisting of letters, digits, and underscore characters ( _ ). Copyright © 2015 Pearson. All rights reserved. 1-6 Names (continued) Length – If too short, they cannot be connotative – Language examples: C99: no limit but only the first 63 are significant; also, external names (i.e., outside functions) are limited to a maximum of 31 C# and Java: no limit, and all are significant C++: no limit. Copyright © 2015 Pearson. All rights reserved. 1-7 Names (continued) Special characters – PHP: all variable names must begin with dollar signs – Perl: all variable names begin with special characters ($, @, or %), which specify the variable’s type – Ruby: variable names that begin with @ are instance variables; those that begin with @@ are class variables Copyright © 2015 Pearson. All rights reserved. 1-8 Names (continued) Case sensitivity – Disadvantage: readability (names that look alike are different) E.g. int X, x; Names in the C-based languages are case sensitive Names in others are not Worse in C++, Java, and C# because predefined names are mixed case (e.g. IndexOutOfBoundsException) Copyright © 2015 Pearson. All rights reserved. 1-9 Names (continued) Case sensitivity – Obviously, not everyone agrees that case sensitivity is bad for names. – In C, the problems of case sensitivity are avoided by the convention that variable names do not include uppercase letters. – In Java and C#, the problem cannot be escaped because many of the predefined names include both uppercase and lowercase letters. For example, the Java method for converting a string to an integer value is parseInt, and spellings such as ParseInt and parseint are not recognized. – This is a problem of writability rather than readability, because the need to remember specific case usage makes it more difficult to write correct programs Copyright © 2015 Pearson. All rights reserved. 1-10 Names (continued) Special words – Special words in programming languages are used to make programs more readable by naming actions to be performed. – Special words also are used to separate the syntactic parts of statements and programs. – In most languages, special words are classified as reserved words, which means they cannot be redefined by programmers. – A reserved word is a special word that cannot be used as a user-defined name. – Potential problem with reserved words: If there are too many, many collisions occur (e.g., COBOL has 300 reserved words!) Copyright © 2015 Pearson. All rights reserved. 1-11 Variables A variable is an abstraction of a memory cell or collection of cells. Variables can be characterized as a sextuple of attributes: 1. Name 2. Address 3. Type 4. Value 5. Lifetime 6. Scope Copyright © 2015 Pearson. All rights reserved. 1-12 Variables Attributes 1) Name – we talk about this previously. 2) Address - the memory address with which it is associated – A variable may have different addresses at different runs. – A variable may have different addresses at different times during execution – A variable may have different addresses at different places in a program. if a subprogram has a local variable that is allocated from the run-time stack when the subprogram is called, different calls may result in that variable having different addresses. – If two variable names can be used to access the same memory location, they are called aliases – Aliases are created via pointers, reference variables, C and C++ unions Copyright © 2015 Pearson. All rights reserved. 1-13 Variables Attributes Address (continued) – Aliases are created via array name in Java – Aliases are harmful to readability (program readers must remember all of them) 3) Type - determines the range of values of variables and the set of operations that are defined for values of that type; in the case of floating point, type also determines the precision. – For example, the int type in Java specifies a value range of −2,147,483,648 to +2,147,483,647 and arithmetic operations for addition, subtraction, multiplication, division, and modulus. Copyright © 2015 Pearson. All rights reserved. 1-14 Variables Attributes (continued) 4) Value - the contents of the location with which the variable is associated - The l-value of a variable is its address - The r-value of a variable is its value Abstract memory cell - the physical cell or collection of cells associated with a variable Copyright © 2015 Pearson. All rights reserved. 1-15 The Concept of Binding A binding is an association between an entity and an attribute, such as between a variable and its type or value, or between an operation and a symbol Binding time is the time at which a binding takes place. Copyright © 2015 Pearson. All rights reserved. 1-16 Possible Binding Times Language design time -- bind operator symbols to operations – For example, the asterisk symbol (*) is usually bound to the multiplication operation Language implementation time-- bind floating point type to a representation – A data type, such as int in C, is bound to a range of possible values Compile time -- bind a variable to a particular data type in C or Java Copyright © 2015 Pearson. All rights reserved. 1-17 Possible Binding Times Load time -- bind a C or C++ static variable to a memory cell) Runtime -- bind a nonstatic local variable to a memory cell Copyright © 2015 Pearson. All rights reserved. 1-18 Possible Binding Times Consider the following C++ assignment statement: count = count + 5; The type of count is bound at compile time. The set of possible values of count is bound at compiler design time. The meaning of the operator symbol + is bound at compile time, when the types of its operands have been determined. The internal representation of the literal 5 is bound at compiler design time. The value of count is bound at execution time with this statement. Copyright © 2015 Pearson. All rights reserved. 1-19 Static and Dynamic Binding A binding is static if it first occurs before run time and remains unchanged throughout program execution. A binding is dynamic if it first occurs during execution or can change during execution of the program Copyright © 2015 Pearson. All rights reserved. 1-20 Type Binding Before a variable can be referenced in a program, it must be bound to a data type. The two important aspects of this binding are: – How is a type specified? The variable specified by explicit or implicit declaration – When does the binding take place? If static, the type may be specified by either an explicit or an implicit declaration Copyright © 2015 Pearson. All rights reserved. 1-21 Explicit/Implicit Declaration An explicit declaration is a program statement used for declaring the types of variables An implicit declaration is a default mechanism for specifying types of variables through default conventions, rather than declaration statements Basic, Perl, Ruby, JavaScript, and PHP provide implicit declarations – Advantage: writability (a minor convenience) – Disadvantage: reliability (less trouble with Perl) Copyright © 2015 Pearson. All rights reserved. 1-22 Explicit/Implicit Declaration (continued) Problem #1: Some of the problems with implicit declarations can be avoided by requiring names for specific types to begin with particular special characters. Example, in Perl – If a name that begins with $ is a scalar, which can store either a string or a numeric value. – If a name begins with @, it is an array; – if it begins with a %, it is a hash structure. – This creates different namespaces for different type variables. – In this scenario, the names @apple and %apple are unrelated, because each is from a different namespace. – Furthermore, a program reader always knows the type of a variable when reading its name. Copyright © 2015 Pearson. All rights reserved. 1-23 Explicit/Implicit Declaration (continued) Problem #2: Some languages use type inferencing to determine types of variables (context) – C# - a variable can be declared with var and an initial value. The initial value sets the type var sum = 0; var total = 0.0; var name = "Fred"; The types of sum, total, and name are int, float, and string, respectively. – Visual Basic 9.0+, ML, Haskell, and F# use type inferencing. The context of the appearance of a variable determines its type Copyright © 2015 Pearson. All rights reserved. 1-24 Dynamic Type Binding With dynamic type binding, the type of a variable is not specified by a declaration statement, nor can it be determined by the spelling of its name. Instead, the variable is bound to a type when it is assigned a value in an assignment statement. When the assignment statement is executed, the variable being assigned is bound to the type of the value of the expression on the right side of the assignment. Copyright © 2015 Pearson. All rights reserved. 1-25 Dynamic Type Binding (continued) Dynamic Type Binding (JavaScript, Python, Ruby, PHP, and C# (limited)) Specified through an assignment statement e.g., JavaScript list = [2, 4.33, 6, 8]; list = 17.3; – Advantage: flexibility (generic program units) – Disadvantages: High cost (dynamic type checking and interpretation) Type error detection by the compiler is difficult Copyright © 2015 Pearson. All rights reserved. 1-26 Variable Attributes (continued) 5) Storage Bindings & Lifetime – Allocation - getting a cell from some pool of available cells – Deallocation - putting a cell back into the pool The lifetime of a variable is the time during which it is bound to a particular memory cell Storage Bindings kinds: I. Static II. Stack-dynamic III. Explicit heap-dynamic IV. Implicit heap-dynamic Copyright © 2015 Pearson. All rights reserved. 1-27 Categories of Variables by Lifetimes I. Static--bound to memory cells before execution begins and remains bound to the same memory cell throughout execution, – e.g., C and C++ static variables in functions – Advantages: Efficiency (direct addressing), no run-time overhead is incurred for allocation and deallocation of static variables – Disadvantage: lack of flexibility, language that has only static variables cannot support recursive subprograms The storage cannot be shared among variables Copyright © 2015 Pearson. All rights reserved. 1-28 Categories of Variables by Lifetimes The storage cannot be shared among variables: – E.g., suppose a program has two subprograms, both of which require large arrays. – Furthermore, suppose that the two subprograms are never active at the same time. – If the arrays are static, they cannot share the same storage for their arrays. Copyright © 2015 Pearson. All rights reserved. 1-29 Categories of Variables by Lifetimes II. Stack-dynamic--Storage bindings are created for variables when their declaration statements are elaborated. (A declaration is elaborated when the executable code associated with it is executed) – For example, the variable declarations that appear at the beginning of a Java method are elaborated when the method is called and the variables defined by those declarations are deallocated when the method completes its execution. Copyright © 2015 Pearson. All rights reserved. 1-30 Categories of Variables by Lifetimes Stack-dynamic (continued) If scalar, all attributes except address are statically bound – local variables in C subprograms (not declared static) and Java methods Advantage: allows recursion; conserves storage Disadvantages: – Overhead of allocation and deallocation – The time required to allocate and deallocate is not significant. – Slow of access because Indirect Addressing Copyright © 2015 Pearson. All rights reserved. 1-31  Categories of Variables by Lifetimes III. Explicit heap-dynamic -- Allocated and deallocated by explicit directives, specified by the programmer, which take effect during execution – Referenced only through pointers or references, e.g. dynamic objects in C++ (via new and delete), all objects in Java – As an example of explicit heap-dynamic variables, consider the following C++ code segment: Copyright © 2015 Pearson. All rights reserved. 1-32  Categories of Variables by Lifetimes Explicit heap-dynamic (continued) Advantage: provides for dynamic storage management – Explicit heap-dynamic variables are often used to construct dynamic structures, such as linked lists and trees, that need to grow and/or shrink during execution Disadvantage: – The difficulty of using pointer and reference variables correctly (unreliable). – The cost of references to the variables Copyright © 2015 Pearson. All rights reserved. 1-33  Categories of Variables by Lifetimes IV. Implicit heap-dynamic--Allocation and deallocation caused by assignment statements – All their attributes are bound every time they are assigned. – all variables in APL; all strings and arrays in Perl, JavaScript, and PHP – Example, JavaScript assignment statement: highs = [74, 84, 86, 90, 71]; Copyright © 2015 Pearson. All rights reserved. 1-34  Categories of Variables by Lifetimes Implicit heap-dynamic (continued) Advantage: flexibility (generic code) Disadvantages: – Inefficient, because all attributes are dynamic – Loss of error detection by compiler Copyright © 2015 Pearson. All rights reserved. 1-35  Variable Attributes: Scope 6) The variable scope. The scope of a variable is the range of statements over which it is visible A variable is visible in a statement if it can be referenced or assigned in that statement. Types of variables: – 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 Copyright © 2015 Pearson. All rights reserved. 1-36 1- Static Scope ALGOL 60 introduced the method of binding names to nonlocal variables called static scoping, which has been copied by many languages. Static scoping is so named because the scope of a variable can be statically determined— that is, prior to execution. Human program reader (and a compiler) can determine the type of every variable in the program simply by examining its source code Copyright © 2015 Pearson. All rights reserved. 1-37 1- Static Scope 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) Variables can be hidden from a unit by having a "closer" variable with the same name Copyright © 2015 Pearson. All rights reserved. 1-38 Static Scope (continued) Consider the following JavaScript function, big, in which the two functions sub1 and sub2 are nested: – Under static scoping, the reference to the variable x in sub2 is to the x declared in the procedure big. – The x declared in sub1 is ignored, because it is not in the static ancestry of sub2. Copyright © 2015 Pearson. All rights reserved. 1-39 Static Scope (continued) – The variable x is declared in both big and in sub1, which is nested inside big. – Within sub1, every simple reference to x is to the local x. Therefore, the outer x is hidden from sub1. Copyright © 2015 Pearson. All rights reserved. 1-40 2- Blocks A method of creating static scopes inside program units--from ALGOL 60 For example, if list were an integer array, one could write the following: if (list[i] < list[j]) { int temp; temp = list[i]; list[i] = list[j]; list[j] = temp; } Copyright © 2015 Pearson. All rights reserved. 1-41 Blocks (continued) – Example in C: – The reference to count in the while loop is to that loop’s local count. In this case, the count of sub is hidden from the code inside the while loop. – In general, a declaration for a variable effectively hides any declaration of a variable with the same name in a larger enclosing scope void sub() { int count; while (...) { legal in C and C++ int count; count++; but not in Java and C#... } … } Copyright © 2015 Pearson. All rights reserved. 1-42 Blocks (continued) The LET Construct 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) ) Copyright © 2015 Pearson. All rights reserved. 1-43 Blocks (continued) The LET Construct Consider the following call to LET: – This call computes and returns the value of the expression (a + b) / (c – d). Copyright © 2015 Pearson. All rights reserved. 1-44 The LET Construct (continued) 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 Copyright © 2015 Pearson. All rights reserved. 1-45 The LET Construct (continued) Consider the following code: – The scope of n1 extends over all of the code. – However, the scope of n2 and n3 ends when the indentation ends. So, the use of n3 in the last let causes an error. – The last line of the let n1 scope is the value bound to n1; it could be any expression. Copyright © 2015 Pearson. All rights reserved. 1-46 3- 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 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, a variable still must be declared before it can be used Copyright © 2015 Pearson. All rights reserved. 1-47 3- Declaration Order (continued) Example of C#: – C# does not allow the declaration of a variable in a nested block to have the same name as a variable in a nesting scope. Copyright © 2015 Pearson. All rights reserved. 1-48 3- Declaration Order (continued) In C++, Java, and C#, variables can be declared in for statements – The scope of such variables is restricted to the for construct Copyright © 2015 Pearson. All rights reserved. 1-49 4- Global Scope 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 Copyright © 2015 Pearson. All rights reserved. 1-50 Global Scope (continued) 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 Global variables can be accessed in a function through the $GLOBALS array or by declaring it global Copyright © 2015 Pearson. All rights reserved. 1-51 Global Scope (continued) – Interpretation of this code produces the following: local day is Tuesday global day is Monday global month is January Copyright © 2015 Pearson. All rights reserved. 1-52 Global Scope (continued) The global variables of JavaScript are very similar to those of PHP, except that there is no way to access a global variable in a function that has declared a local variable with the same name. Copyright © 2015 Pearson. All rights reserved. 1-53 Global Scope (continued) 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 Copyright © 2015 Pearson. All rights reserved. 1-54 Evaluation of Static Scoping 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 Copyright © 2015 Pearson. All rights reserved. 1-55 Dynamic Scope The scope of variables in APL, SNOBOL4, and the early versions of Lisp is dynamic. Dynamic scoping is based on calling sequences of program units, not their textual layout (temporal versus spatial) The scope can be determined only at run time. References to variables are connected to declarations by searching back through the chain of subprogram calls that forced execution to this point Copyright © 2015 Pearson. All rights reserved. 1-56 Scope Example function big() { function sub1() var x = 7; function sub2() { var y = x; big calls sub1 } sub1 calls sub2 var x = 3; sub2 uses x } – Static scoping Reference to x in sub2 is to big's x – Dynamic scoping Reference to x in sub2 is to sub1’s x It may reference the variable from either declaration of x, depending on the calling sequence. Copyright © 2015 Pearson. All rights reserved. 1-57  Scope Example function big() { function sub1() var x = 7; function sub2() { var y = x; } var x = 3; } Consider the two different call sequences for sub2 in the example. – First, big calls sub1, which calls sub2. In this case, the search proceeds from the local procedure, sub2, to its caller, sub1, where a declaration for x is found. So, the reference to x in sub2 in this case is to the x declared in sub1. – Next, sub2 is called directly from big. In this case, the dynamic parent of sub2 is big, and the reference is to the x declared in big. Copyright © 2015 Pearson. All rights reserved. 1-58 Evaluation of Dynamic Scoping Evaluation of Dynamic Scoping: – Advantage: convenience – Disadvantages: 1. While a subprogram is executing, its variables are visible to all subprograms it calls 2. Impossible to statically type check 3. Poor readability- it is not possible to statically determine the type of a variable 4. accesses to nonlocal variables in dynamic-scoped languages take far longer than accesses to nonlocals when static scoping is used. Copyright © 2015 Pearson. All rights reserved. 1-59 Evaluation of Dynamic Scoping Programs in static-scoped languages are easier to read, are more reliable, and execute faster than equivalent programs in dynamic-scoped languages. It was precisely for these reasons that dynamic scoping was replaced by static scoping in most current dialects of Lisp. Copyright © 2015 Pearson. All rights reserved. 1-60 Scope and Lifetime Scope and lifetime are sometimes closely related, but are different concepts The scope of such a variable is from its declaration to the end of the method. The lifetime of that variable is the period of time beginning when the method is entered and ending when execution of the method terminates. Consider a static variable in a C or C++ function Copyright © 2015 Pearson. All rights reserved. 1-61 Scope and Lifetime (continued) Consider the following C++ functions: – The scope of the variable sum is completely contained within the compute function. – It does not extend to the body of the function printheader, although printheader executes in the midst of the execution of compute. Copyright © 2015 Pearson. All rights reserved. 1-62 Scope and Lifetime (continued) – The lifetime ofsum extends over the time during which printheader executes. – Whatever storage location sum is bound to before the call to printheader, that binding will continue during and after the execution of printheader. Copyright © 2015 Pearson. All rights reserved. 1-63 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 In a dynamic-scoped language, the referencing environment is the local variables plus all visible variables in all active subprograms – A subprogram is active if its execution has begun but has not yet terminated Copyright © 2015 Pearson. All rights reserved. 1-64  Referencing Environments (continued) Consider the following Python skeletal program: local a and b (of sub1), global g for reference, but not for assignment local c (of sub2), global g for both Reference and for assignment nonlocal c (of sub2), local g (of sub3) Copyright © 2015 Pearson. All rights reserved. 1-65  Referencing Environments (continued) Consider the following example program. Assume that the only function calls are the following: main calls sub2, which calls sub1. a and b of sub1, c of sub2, d of main, (c of main and b of sub2 are hidden) b and c of sub2, d of main, (c of main is hidden) c and d of main Copyright © 2015 Pearson. All rights reserved. 1-66 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 Copyright © 2015 Pearson. All rights reserved. 1-67 Named Constants (continued) Consider the following skeletal Java program segment: Copyright © 2015 Pearson. All rights reserved. 1-68 Named Constants (continued) Now, when the length must be changed, only one line must be changed (the variable len), regardless of the number of times it is used in the program. Copyright © 2015 Pearson. All rights reserved. 1-69 Named Constants (continued) Languages: – C++ and Java: expressions of any kind, dynamically bound const int result = 2 * width + 1; – C# has two kinds, readonly and const - the values of const named constants are bound at compile time - The values of readonly named constants are dynamically bound Copyright © 2015 Pearson. All rights reserved. 1-70 Summary Case sensitivity and the relationship of names to special words represent design issues of names Variables are characterized by the sextuples: name, address, value, type, lifetime, scope Binding is the association of attributes with program entities Scalar variables are categorized as: static, stack dynamic, explicit heap dynamic, implicit heap dynamic Strong typing means detecting all type errors Copyright © 2015 Pearson. All rights reserved. 1-71