02-unit-2.pptx

Principles of Programming Languages M.V.Durgarao Asst. Professor, CSE Dept Vishnu Institute of Technology

Vishnu Institute of technology – Website: www.vishnu.edu.in

UNIT – 2 Names, Bindings and Scopes

Vishnu Institute of technology – Website: www.vishnu.edu.in

Names (Identifiers) • Attributes of variables: – Name – Type – Value – Address – Scope – Lifetime

Vishnu Institute of technology – Website: www.vishnu.edu.in

Names – Design Issues • Design issues for names are: – Are names case sensitive? – Are the special words of the language reserved words or keywords?

Vishnu Institute of technology – Website: www.vishnu.edu.in

Names – Name Forms • A name is a string of characters used to identify some entity in a program. • Language restrictions: – Fortran 95+ allows 31 characters – C99 has no limitation on length of internal names and 31 characters limitation on external names (names used outside all functions) – C++, Java, C# and Ada have no limitation on size of names. Vishnu Institute of technology – Website: www.vishnu.edu.in

Names – Name Forms • In most of the programming languages, names have the some form, begins with a letter, followed by any no. of letters or digits or underscores. • In C, underscores are replaced with camel notation. (Ex: myStack)

• In PHP, variable names must begin with $. • In Perl, $, @ or % at the beginning of a variable name specifies different types.

• In Ruby, @ or @@ at the beginning of a variable name refer to instance variable and class variable respectively.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Names – Special Words • Special words are names which have pre-defined special actions allotted to them. • A keyword is a word of a programming language, which is special only in some contexts. In Fortran, Integer can be treated differently: Integer Apple //Here Integer is treated as keyword Integer = 4 //Here Integer is treated as a variable

• A reserved word is a special word which cannot be used as a name. Vishnu Institute of technology – Website: www.vishnu.edu.in

Names – Special Words (cont...) • Reserved words are better than keywords in terms of readability. For example in Fortran: Integer Real Real Integer is valid and may confuse programmers and users. • Too many reserved words might effect writability. For example, COBOL includes 300 reserved words. Vishnu Institute of technology – Website: www.vishnu.edu.in

Variables • A variable is an abstraction of a computer memory cell or collection of cells. • A variable can be characterized as a collection of six attributes: name, value, address, type, scope and lifetime. • Most variables have names and some do not. Vishnu Institute of technology – Website: www.vishnu.edu.in

Variables (cont...) • The address of a variable is the machine memory address with which it is associated. • The address of a variable is called its l-value in an assignment statement. • When more than one variable name can be used to access the same memory location, such variables are called as aliases.

• Aliases can be created in different ways. In C and C++ aliases are created using pointers or unions.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Variables (cont...) • The type of a variable determines the range of values that a variable can hold and the operations allowed on it. • The value of a variable is the contents of the memory cell or cells associated with the variable. • The variable’s value is sometimes called its rvalue as it is required when the name of a variable appears in the right hand side of an assignment statement. Vishnu Institute of technology – Website: www.vishnu.edu.in

Binding • A binding is an association between an entity and its attribute. – Binding between a variable and its type or value – Binding between an operator and its operation

• The time at which binding takes place is known as binding time.

• Binding can take place at language design time, language implementation time, compile time, run time, link time or load time. • Binding is said to be static if it occurs before run time and remains unchanged throughout program execution. If the binding occurs during run time, or it can change during program execution, such binding is said to be dynamic.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Binding (cont...) • Some examples of binding times: – The asterisk symbol (*) is bound to the multiplication operation at language design time. – A data type like int is bound to its range at language implementation time. – A variable is bound to its type in Java at compile time. – A variable may be bounded to a storage cell at load time. – A call to a library subprogram is bound to the subprogram code at link time. Vishnu Institute of technology – Website: www.vishnu.edu.in

Binding (cont...) Example (Java): count = count + 5; • Type of count is bound at compile time. • Range of values for count is bound at compiler design time. • Meaning of operator + is bound at compile time, when the types of its operands have been determined. • Internal representation of literal 5 is bound at compiler design time. • Value of count is bound at execution time. Vishnu Institute of technology – Website: www.vishnu.edu.in

Binding - Type • Type binding that takes place during compile time is known as static type binding. • Type can be specified through explicit declaration or through implicit declaration. • An explicit declaration declares the variables along with their types. • An implicit declaration associates variables with types through default conventions, rather through declarations. Vishnu Institute of technology – Website: www.vishnu.edu.in

Binding – Type (cont...) • Implicit variable type binding is done by the language processor, either a compiler or interpreter. • Implicit declaration examples: – In Fortran, if the identifier begins with I, J, K, L, M, or N, or their lowercase versions, it is implicitly declared to be of Integer type. Otherwise, Real type. – In Perl, a name that begins with $ is a scalar, which can store a string or a numeric value. If the name begins with @, it is an array. If the name begins with % , it is a hash structure. – Implicit declarations can also be based on context. This is sometimes called as type inference. In C#, var sum = 0 declares sum as of type int. Here, the context is the value being assigned to the variable.

• Visual Baisc 9.0+, Go, and functional languages like ML, Haskell, OCaml and F# use type inferencing. Vishnu Institute of technology – Website: www.vishnu.edu.in

Binding – Type (cont...) • Type binding that takes place at run time is known as dynamic type binding. • In dynamic type binding, a variable is bound to a type when it is assigned a value.

• The type of a variable is temporary in dynamic type binding. • Dynamic binding provides more programming flexibility. – Program to process numeric data (int, float etc...)

• Python, Ruby, JavaScript and PHP support dynamic type binding.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Binding – Type (cont...) • Option of dynamic type binding was introduced in C# (2010). A variable can be declared to use dynamic typing as follows: dynamic variable-name; • In Ruby, all variables are references and do not have any type. A variable can refer any object. • Disadvantages of dynamic type binding: – Less readability as the error-detection capability of a compiler is diminished. – Cost is high. Type checking must be done at run time.

• In general, languages supporting dynamic type binding are processed by an interpreter.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Storage Bindings and Lifetime • Process of binding a variable to a memory cell is called as allocation and unbinding a variable from its memory cell is called as deallocation. • The lifetime of a variable is the time during which the variable is bound to a specific memory location. Vishnu Institute of technology – Website: www.vishnu.edu.in

Storage Bindings and Lifetime – Static Variables • Static variables are those that are bound to a memory cell before program execution and remain bound to the same memory cell until the program terminates. • Global variables are static variables. • Subprograms can have local static variables which are history sensitive. • Advantage of static variables is efficiency. They can be addressed directly. No run time overhead for allocation and deallocation.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Storage Bindings and Lifetime – Static Variables (cont...) • One disadvantage of static variables is reduced flexibility. Static variables cannot be used for recursive subprograms. • Another disadvantage is memory cannot be shared. • C and C++ allows static specifier for variables inside functions.

• In C++, Java, and C#, static implies that the variable is a class variable. Class variables are created before the class is instantiated. Vishnu Institute of technology – Website: www.vishnu.edu.in

Storage Bindings and Lifetime – Stack-Dynamic Variables • Stack-dynamic variables are those whose storage bindings are created when their declaration statements are elaborated, but whose types are statically bound. • Elaboration refers to the storage allocation and binding process indicated by the declaration and occurs at run time. • Variable declarations in a Java method are elaborated when the method is called and is done at run time. The variables are allocated on run time stack. Vishnu Institute of technology – Website: www.vishnu.edu.in

Storage Bindings and Lifetime – Stack-Dynamic Variables (cont...) • Advantage of stack-dynamic variables is, they are suitable for recursive sub programs. • Disadvantages: – Runtime overhead of allocation and deallocation. – Slower access due to indirect addressing. – Subprograms cannot be history sensitive. • In C++, Java, and C#, by default all the variables in a method are stackdynamic. • In Ada, all non-heap variables defined in sub programs are stack-dynamic.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Storage Bindings and Lifetime – Explicit Heap-Dynamic Variables • Explicit heap-dynamic variables are nameless (abstract) memory cells that are allocated and deallocated by explicit run time instructions. • These variables available in the heap are accessed through pointers or references. • In C++, the allocation operator, new is used to create a dynamic variable which is allocated on the heap. • Java objects are explicitly heap dynamic and are accessed through references. • Pointers are included in C# to allow C# components to interoperate with C and C++ components. Vishnu Institute of technology – Website: www.vishnu.edu.in

Storage Bindings and Lifetime – Explicit Heap-Dynamic Variables (cont...) • Explicit heap-dynamic variables are often used to create dynamic data structures like linked lists and trees. • Disadvantages: – Difficulty of using pointers and references correctly. – Aliasing issues. – Complexity of storage management implementation.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Storage Bindings and Lifetime – Implicit Heap-Dynamic Variables • Implicit heap-dynamic variables are bound to heap storage only when they are assigned values. • Consider the following example in JavaScript: heights = [74, 43, 56, 76]; • Advantage of implicit heap-dynamic variables is that they have the highest degree of flexibility in writing generic programs. • Disadvantages: – Run time overhead for maintaining all dynamic attributes. – Loss of error detection by the compiler.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope • The scope of a variable is the range of statements in which the variable is visible. • A variable is visible in a statement if it can be referenced in that statement. • The scope rules of a language determine how a particular occurrence of a name is associated with a variable or an expression.

• A variable is local in a program unit or block if it is declared in it.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Static Scope • ALGOL 60 introduced the concept of binding names to non-local variables called static scoping. • In static scoping the scope of a variable can be determined statically (before execution). • There are two categories of static-scoped languages: those in which sub programs can be nested and those in which sub programs cannot be nested.

• Ada, JavaScript, Common LISP, Scheme, Fortran 2003+, F# and Python allow nested sub programs. C-based languages do not allow nested sub programs. Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Static Scope (cont...) • In a static-scoped language, when the reader of a program finds a reference to a variable, the attributes of a variable can be found through the following process: – If a reference for variable x is found in sub program sub1, the correct declaration for variable x is searched in the definition of sub1. – If declaration for x is not found in sub1, the search continues in the parent sub program for sub1. – This continues until the declaration for x is found or all the static ancestors have been exhausted. Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Static Scope (cont...) JavaScript example:

The reference of x in sub2 is to the x declared in big. The search for x begins within sub2 and as it is not there, it is searched in its ancestor, big. Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Blocks • ALGOL 60 introduced the concept of blocks. • A block is a compound statement which contains a set of statements enclosed by matching braces. • A block can have its own local variables. Such variables are typically stack dynamic. • In case of nested bocks, the scope rules are same as for nested sub programs. Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Blocks (cont...) C example:

In the above code, count of while loop is different from count of sub function. The count variable inside while loop hides the count variable in the enclosing scope. Above code is legal in C and C++ and illegal in Java and C#. Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Global Scope • Variables defined outside functions are known as global variables. • C, C++, PHP, Python, and JavaScript support global variables. • Declaration of a variable specifies type and other attributes but not storage. • Storage is allocated when the variable is defined. • A global variable in C is implicitly visible in all subsequent functions. • A global variable that is defined after a function can be made visible in the function by declaring it to be external. Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Global Scope (cont...) • In C++, a global variable that is hidden by a local variable with same name can be accessed using the scope operator (::). • In PHP, variables declared implicitly outside functions are global variables. Global variables are not implicitly visible to functions. • Global variables in PHP can be made visible in functions using two ways: – If the function includes a local variable with the same name as the global, it can be accessed using the $GLOBALS array. – If there is no local variable, the global can be accessed by making it a part of the global declaration statement. Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Global Scope (cont...) PHP example:

Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Global Scope (cont...) • Global variables in JavaScript are same as in PHP, except there is no way to access a global if there is a local with the same name. • In Python, global variables can be accessed inside functions but cannot be assigned new values. New values can be assigned only when it is declared as global in the function. Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Global Scope (cont...) Python example:

Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Dynamic Scope • Dynamic scoping is based on the calling sequence of sub programs. • APL, SNOBOL, LISP, Perl and Common LISP support dynamic scoping. • Scope is determined at run time.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Dynamic Scope (cont...) Example:

-If the sequence of calls to sub programs is big, sub1 and sub2, x in sub2 refers to x in sub1. -If the sequence of calls to sub programs is big and sub2, x in sub2 refers x in big. Vishnu Institute of technology – Website: www.vishnu.edu.in

Scope – Dynamic Scope (cont...) • Problems with dynamic scoping: – Local variables of a sub program are visible to all other sub programs. – Inability to type check references to non-locals statically. – Makes programs less readable. – Access to non-local variables in dynamic scoped languages takes more time than in static scoped languages. Vishnu Institute of technology – Website: www.vishnu.edu.in

Referencing Environments • The referencing environment of a statement is the set of all variables that are visible in the statement. • The referencing environment of a statement in a staticscoped language is the variables declared in its local scope plus the set of variables of its ancestor scope that are visible. • In Python, the referencing environment of a statement includes all the local variables and all the variables declared in the functions in which the statement is nested. Vishnu Institute of technology – Website: www.vishnu.edu.in

Referencing Environments (cont...) Python example: g = 3; #A global def sub1( ): a = 5; b = 7; ... <------ 1 def sub2( ): global g; #Global g is accessible here c = 9; ... <-------- 2 def sub3( ): nonlocal c; #Makes non-local c visible here g = 11; ... <-------- 3 Vishnu Institute of technology – Website: www.vishnu.edu.in

Referencing Environments (cont...) Python example:

Vishnu Institute of technology – Website: www.vishnu.edu.in

Referencing Environments (cont...) • The referencing environment of a statement in dynamically scoped language is the local variables, plus the variables of all other active sub programs. • Recent sub program activations can have variables that are hidden (which have the same name as local variables). Vishnu Institute of technology – Website: www.vishnu.edu.in

Referencing Environments (cont...) C example: void sub1( ) { int a, b; .... <---------- 1 } void sub2( ) { int b, c; .... <---------- 2 sub1( ); } void main( ) { int c, d; .... <----------- 3 sub2( ); } Vishnu Institute of technology – Website: www.vishnu.edu.in

Referencing Environments (cont...) C example: Sequence of calls is: main( ), sub2( ) and sub1( ).

Vishnu Institute of technology – Website: www.vishnu.edu.in

Named Constants • A named constant is a variable that is bound to a value only once. • Named constants aids readability: – The name pi can be used instead of the constant value 3.14159265. – Can be used to parameterize the programs (ex: processing fixed number of data values)

Vishnu Institute of technology – Website: www.vishnu.edu.in

Named Constants (cont...) Example: Before using named constant:

After using named constant len:

Vishnu Institute of technology – Website: www.vishnu.edu.in

Named Constants (cont...) • Ada and C++ allow dynamic binding of values to named constants i.e., expressions can be specified as values as shown below: const int result = 2 * width + 1; • Java also supports dynamic binding for named constants through final keyword. • C# supports two kinds of named constants: – const: These named constants are statically bound to values. – readonly: These named constants are dynamically bound to values. Vishnu Institute of technology – Website: www.vishnu.edu.in

UNIT – 2 Data Types

Vishnu Institute of technology – Website: www.vishnu.edu.in

Introduction • A data type defines a collection of data values and a set of predefined operations on those values. • It is important for a language to provide an appropriate collection of data types and data structures. • User-defined types allow modifiability. • Abstract data types hide their internal implementation and present only an interface to the users. Vishnu Institute of technology – Website: www.vishnu.edu.in

Introduction (cont...) • Uses of type system: – Error detection – Program modularization (cross module type checking) – Documentation

• Type system of a language defines how a type is associated with each expression in the language and includes rules for type equivalence and type compatibility. • A descriptor is a collection of attributes of a variable.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Primitive Data Types • Data types that are not defined in terms of other types are known as primitive data types.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Primitive Data Types – Numeric Types • Most common primitive numeric data type is integer. • Java supports four signed integer types: byte, short, int and long. • C++ and C# supports unsigned integer types also. • Negative integers are generally stored using two’s complement notation. Some computers use one’s complement notation but it has the disadvantage of two representations for zero.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Primitive Data Types – FloatingPoint • Floating-Point types are used to store real numbers, but the representations are only approximations for many real values. • Problem with floating-point types is the loss of accuracy through arithmetic operations. • On newer machines, floating-point numbers are represented using IEEE format. Vishnu Institute of technology – Website: www.vishnu.edu.in

Primitive Data Types – FloatingPoint • Most languages include two floating-point types: float and double. • Precision is the accuracy of the fractional part of a value, measured as the number of bits. • Range is a combination of the range of fractions and range of exponents. Vishnu Institute of technology – Website: www.vishnu.edu.in

Primitive Data Types – FloatingPoint

Adopted from “Concepts of Programming Languages – Sebesta” Vishnu Institute of technology – Website: www.vishnu.edu.in

Primitive Data Types – Complex and Decimal •

Some programming languages like Fortran and Python support complex data type.

•

Complex values are represented as ordered pairs of floating-point values. For example, in Python, complex number is given as (7 + 5j). ‘J’ or ‘j’ represents the imaginary part.

•

Systems that support business applications provides hardware support for decimal types.

•

COBOL, C# and F# provides decimal data types.

•

Advantage of decimal type is, the fractional parts can be stored precisely unlike floating-point types.

•

Disadvantage of decimal type is, range of values for exponent are restricted.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Primitive Data Types – Boolean Types • Boolean types are the simplest of all types. • Range of Boolean types include only two values: true and false. • ALGOL 60 introduced Boolean type. • C89 doesn’t have Boolean type. Instead it uses numeric expressions as conditionals. • C99 and C++ provides Boolean type and also allows numeric expressions as conditionals. • Java and C# does not allow numeric values as conditionals.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Primitive Data Types – Character Types • Character data are stored in computers as numeric coding. • Traditionally used coding was the 8-bit ASCII code. ASCII supports 128 different characters. • ISO 8859-1 is another 8-bit character code which allows 256 different characters. Ada 95+ uses ISO 8859-1. • In 1991, UCS-2 standard also known as Unicode was published. It is 16-bit character set. Java was the first language to support Unicode. • JavaScript, Python, Perl, C# and F# also support Unicode.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Character String Types • A character string type is one in which the value contains a collection of characters. • Design issues: – Should strings be a character array or a primitive type? – Should strings have static or dynamic length?

Vishnu Institute of technology – Website: www.vishnu.edu.in

Character String Types – String Operations • Most common string operations are assignment, concatenation, substring reference, comparison and pattern matching. • C and C++ uses char arrays to store strings.

• Most commonly used string library functions in C and C++ are strcpy, strcat, strcmp and strlen. Vishnu Institute of technology – Website: www.vishnu.edu.in

Character String Types – String Operations (cont...) • Java provides String, StringBuffer and StringBuilder classes for working with strings. • C# and Ruby include similar string classes like Java. • Python includes string as a primitive type and are immutable.

• In F#, strings are classes. • In ML, string is primitive immutable type. Vishnu Institute of technology – Website: www.vishnu.edu.in

Character String Types – String Operations (cont...) • Perl, JavaScript, Ruby and PHP include builtin pattern matching operations. Example: /[A-Za-z][A-Za-z\d]+/

Vishnu Institute of technology – Website: www.vishnu.edu.in

Character String Types – String Length • A string whose length is static and set when the string is created is called a static length string. • Strings of Python, Java’s String class, C++, Ruby’s String class, C# and F# are static length strings. • A string whose length is variable and set when the string is created is called a limited dynamic length string. • C and C++ strings are limited dynamic length strings.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Character String Types – String Length (cont...) • A string whose length is variable and not set when the string is created is called a dynamic length string. • Strings of JavaScript and Perl are dynamic length strings. • Ada 95+ supports all three types of strings. Vishnu Institute of technology – Website: www.vishnu.edu.in

Character String Types – Implementation • Left to student as an exercise.

Vishnu Institute of technology – Website: www.vishnu.edu.in

User-Defined Ordinal Types – Enumeration Types • An ordinal type is one in which the range of possible values can be easily associated with the set of positive integers. • There are two user-defined ordinal types supported by many programming languages: enumeration and subrange. • An enumeration type is one in which all of the possible values (named constants) are provided in the definition.

• The named constants in an enumeration are known as enumeration constants.

Vishnu Institute of technology – Website: www.vishnu.edu.in

User-Defined Ordinal Types – Enumeration Types (cont...) • Example of enumeration in C, C++ and C#: enum days {Mon, Tue, Wed, Thu, Fri, Sat, Sun};

• Implicit starting integer value for enumeration constants is 0. • Design issues: – Is an enumeration constant allowed to appear in more than one type definition? – Are enumeration values coerced to integers? – Are any other types coerced to an enumeration type? Vishnu Institute of technology – Website: www.vishnu.edu.in

User-Defined Ordinal Types – Subrange Types • A subrange type is a contiguous subsequence of an ordinal type. For example, 12..14 is a subrange of integer type. • Subrange types were introduced by Pascal and are included in Ada. • Subrange type example in Ada: type Days is (Mon, Tue, Wed, Thu, Fri, Sat, Sun); subtype Weekdays is Days range Mon..Fri; subtype Index is Integer range 1..100; • No existing languages other than Ada support subrange types. Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types • An array is a collection of homogeneous collection of data elements. • References to individual data elements of an array are specified using subscript expressions. • In languages like C, C++, Java, Ada and C# all of the elements of an array are of same type. • In JavaScript, Python and Ruby, arrays still consist of elements of single type, but the elements can reference objects or data values of different types.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types (cont...) • Design issues: – – – – –

What types are legal for subscripts? Are expressions for subscripts range checked? When are subscript ranges bound? When does array allocation take place? Are ragged, rectangular multidimensional arrays or both allowed? – Can arrays be initialized when they have their storage allocated? – What kind of slices are allowed, if any? Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Arrays and Indices • Elements of an array can be referenced using the array name and a subscript. • A subscript can be static (value) or dynamic (expression).

• Arrays are sometimes called as finite mappings as array name and set of subscript values are mapped to an array element. • Ada and Fortran use parentheses for subscripts. Ada chose parentheses for subscripts as functions and arrays are mappings.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Arrays and Indices (cont...) • Range checking of subscripts is essential for reliability. • Java, ML, Ada and C# does range check on subscripts. • Subscripting in Perl is a bit unusual. All arrays begin with the symbol @. But while referencing array elements, array name should begin with $.

• Perl allows negative subscripts on arrays. In case of negative subscript, elements from last are referenced. Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Subscript Bindings and Array Categories • Binding of subscript type to an array is generally static, but the binding of subscript values range is sometimes dynamic. • Arrays are divided into three categories based on: – Binding to subscript ranges – Binding to storage – From where the storage is allocated

• A static array is one in which the subscript ranges are statically bound and storage allocation is static. – Advantage is efficiency (no dynamic allocation or deallocation is required) – Disadvantage is storage is fixed and cannot be changed.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Subscript Bindings and Array Categories (cont...) • A fixed stack-dynamic array is one in which the subscript ranges are statically bound, but the allocation is done at declaration elaboration time. – Advantage is same storage can be reused. – Disadvantage is allocation and deallocation of memory.

• Example for fixed stack-dynamic arrays are the arrays which are local to functions. • A stack dynamic array is one in which both the subscript ranges and the storage allocation are dynamically bound at elaboration time. – Advantage is flexibility (size of array need not be known until the array is about to be used).

Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Subscript Bindings and Array Categories (cont...) • A fixed heap-dynamic array is one in which the both the subscript ranges and storage bindings are done at execution time and storage is allocated on heap. – Advantage is flexibility. – Disadvantage is allocation time from heap (which is longer than allocation on stack).

• A heap dynamic array is one in which the binding of subscript ranges and storage allocation is dynamic and can change any number of times. – Advantage is flexibility. – Disadvantage is allocation and deallocation several times. Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Subscript Bindings and Array Categories (cont...) Examples: Array Type

Example Languages

Static arrays

Static arrays in functions in C and C++

Fixed stack-dynamic arrays

Non-static arrays in functions in C and C++

Stack-dynamic arrays

Arrays in Ada

Fixed heap-dynamic arrays

C and C++ (using malloc and free), Java and C#

Heap-dynamic arrays

C#, Java (generic arrays)

Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types - Initialization • In C, C++, Java and C#, arrays can be initialized by providing array aggregates. Ex: int list[] = {1, 2, 3, 4};

char name[] = “ramesh”; char *names[] = {“dinesh”, “ramesh”} • Ada provides two ways to initialize arrays: List : array (1..5) of Integer := (1, 3, 5, 7, 9); Bunch : array (1..5) of Integer := (1 => 17, 3 => 34, others => 0);

Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types- Operations • Most common array operations are assignment, concatenation, comparison for equality and slices. • C-based languages doesn’t provide direct array operations. • Perl supports array assignments. • Ada allows array assignments and catenation. Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Operations (cont...) • Python’s arrays are called lists. Python allows assignment, catenation, element membership and comparison operations. • Ruby allows assignment operation. • Fortran 95+ includes a number of array operations which are elemental. • APL provides a rich set of operations on arrays which are elemental. Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Rectangular and Jagged Arrays • A rectangular array is a multi-dimensional array in which all rows and columns contain the same number of elements. • A jagged array is one which the length of the rows need not be the same. • C, C++ and Java support jagged arrays but not rectangular arrays. Example: myArray[3][5] • Fortran, Ada, C# and F# support rectangular arrays. Example: myArray[3,5]

Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Slices • A slice of an array is some substructure of an array. • Consider the following array declarations in Python: vector = [2, 4, 6, 8, 10, 12, 14, 16] mat = [[1, 2, 3],[4, 5, 6],[7, 8, 9]] vector[3:6] gives 8, 10, 12 mat[1] gives 4,5,6 mat[0][0:2] gives 1,2 vector[0:7:2] gives 2,6,10,14

Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Slices (cont...) • Example of Perl: @list[1..5] = @list2[3, 5, 7, 9, 13]; (elements with indices 3, 5, 7, 9 and 13 from list2 are stored in list1) • Example of Ruby: list = [2, 4, 6, 8, 10]

list.slice(3) gives 8 list.slice(2,2) gives 6,8 list.slice(1..3) gives 4,6,8 Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Implementation of Array Types • A one dimensional array is implemented as a list of adjacent memory cells. • For an array list, with lower bound 0 for subscript, the access function is given as: address(list[k]) = address(list[0]) + k * element_size

•

The compile-time descriptor for one-dimensional arrays looks as shown below:

Adopted from “Concepts of Programming Languages – Sebesta” Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Implementation of Array Types (cont...) • Multi-dimensional arrays can be stored either in row major order or column major order. • Fortran uses column major order. • For a two-dimensional array, the access function is as follows:

n is number of elements in the row. Vishnu Institute of technology – Website: www.vishnu.edu.in

Array Types – Implementation of Array Types (cont...) • Compile-time descriptor for multidimensional array is as follows:

Adopted from “Concepts of Programming Languages – Sebesta” Vishnu Institute of technology – Website: www.vishnu.edu.in

Associative Arrays • An associative array is an unordered collection of data elements that are indexed by keys. • In an associative array the keys must be stored along with the values unlike normal arrays. • Perl, Python, Ruby and Lua provide direct support for associative arrays. Vishnu Institute of technology – Website: www.vishnu.edu.in

Associative Arrays – Structure and Operations • In Perl, associative arrays are called as hashes, as they are implemented using hash functions. • Example in Perl: %salaries = ("Gary" => 75000, "Perry" => 57000, "Mary" => 55750, "Cedric" => 47850); • Individual elements in Perl are referenced as: $salaries{"Perry"} = 58850; • An element can be removed using delete operator: delete $salaries{"Gary"}; • Entire hash can be emptied as follows: @salaries = (); Vishnu Institute of technology – Website: www.vishnu.edu.in

Associative Arrays – Structure and Operations (cont...) • Python’s associative arrays are known as dictionaries, are similar to those of Perl. • Ruby’s associative arrays are similar to Python, except that the keys can be any object.

• In PHP, keys of associative arrays can be integers or strings. • PHP supports both normal and associative arrays. • Lua’s table data structure is an associative array in which both the keys and values can be any type. • C# and F# support associative arrays through pre-defined classes. Vishnu Institute of technology – Website: www.vishnu.edu.in

Record Types • A record is an aggregate of data elements in which the individual elements are identified by names and accessed through offsets from the beginning of the structure.

• A record is used to group relevant data of different types. Ex: Student details. • Contents of a record or stored in adjacent memory locations. • Records are introduced in COBOL. • In C, C++ and C#, records are supported with the struct type.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Record Types (cont...) • Design issues: – What is the syntactic form of references to fields? – Are elliptical references allowed?

Vishnu Institute of technology – Website: www.vishnu.edu.in

Record Types – Definitions of Records • Difference between record and an array: – Unlike arrays, record elements (fields) have names and referenced using those names. – In Some languages records are allowed to include unions.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Record Types – Definitions of Records (cont...) Records in COBOL:

Adopted from “Concepts of Programming Languages – Sebesta” - Employee-Record and Employee-name are records and FIRST, MIDDLE, LAST, HOURLY-RATE are fields. -PICTURE clause is used to specify the data type. - X specifies alphanumeric type. - 99V99 specifies decimal value of 4 digits and decimal point is in the middle.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Record Types – Definitions of Records (cont...) Records in Ada:

Adopted from “Concepts of Programming Languages – Sebesta” Vishnu Institute of technology – Website: www.vishnu.edu.in

Record Types – References to Record Fields In COBOL: Syntax: field_name OF record_name_1 OF . . . OF record_name_n

Example: MIDDLE OF EMPLOYEE-NAME OF EMPLOYEE-RECORD

In Ada: Employee_Record.Employee_Name.Middle Vishnu Institute of technology – Website: www.vishnu.edu.in

Record Types – References to Record Fields (cont...) • A fully qualified reference to a record field is one in which all intermediate record names, from the largest enclosing record to the specific field, are named in the reference.

• An elliptical reference to a record field can contain only name of the field or field name and any or all of the enclosing record names. • Example of fully qualified references are: 1. MIDDLE OF EMPLOYEE-NAME OF EMPLOYEE-RECORD 2. Employee_Record.Employee_Name.Middle

Vishnu Institute of technology – Website: www.vishnu.edu.in

Record Types – Implementation • Structure elements are stored in adjacent memory locations. • Compile-time descriptor for record types is as follows:

Adopted from “Concepts of Programming Languages – Sebesta” Vishnu Institute of technology – Website: www.vishnu.edu.in

Tuple Types • Tuples are same as records, except that the elements are not named. • In Python, tuples are immutable. Ex: myTuple = (3, 5.8, 'apple') myTuple[1] gives 3 as first index of a tuple is 1

• ML includes a tuple data type. An ML tuple must at least contain two elements, whereas in Python, a tuple can be empty. • ML example: val myTuple = (3, 5.8, 'apple'); #1 (myTuple) gives 3

Vishnu Institute of technology – Website: www.vishnu.edu.in

Tuple Types (cont...) • F# also supports tuples. Ex: let tup = (3, 5, 7);; let a, b, c = tup;; In the above statement, 3 is assigned to a, 5 is assigned to b and 7 is assigned to c.

Vishnu Institute of technology – Website: www.vishnu.edu.in

List Types • Lists were introduced in the functional language LISP. • Lists are immutable, and elements of a list must be of same type.

• Example of a list in Scheme and LISP: (A B C D) Nested List: (A (B C) D) • In LISP, (A B C) is interpreted as a call to function A with B and C as parameters. Vishnu Institute of technology – Website: www.vishnu.edu.in

List Types (cont...) • In Scheme, CAR function returns the first element in the list. Ex: (CAR ‘(A B C)) returns A The quote tells the interpreter that (A B C) is not a call to the function A. CDR function returns the rest of the list elements except the first element. Ex: (CDR ‘(A B C)) gives (B, C) • Common LISP contains functions FIRST, SECOND, ..., TENTH for returning the corresponding elements in the list. Vishnu Institute of technology – Website: www.vishnu.edu.in

List Types (cont...) • Scheme and Common LISP contains CONS and LIST functions to build lists. • CONS function accepts two parameters and returns a list combining both the parameters. Ex: (CONS 'A '(B C)) gives (A B C) • LIST accepts any number of parameters and returns a list combining all the parameters. Ex: (LIST 'A 'B '(C D)) returns (A B (C D)) Vishnu Institute of technology – Website: www.vishnu.edu.in

List Types (cont...) • ML lists are delimited by square brackets. Ex: [5, 7, 9] • In ML, the CONS function of Scheme is implemented as a binary operator represented using ::. Ex: 3 :: [5, 7, 9] gives [3, 5, 7, 9] • In ML: hd [5, 7, 9] gives 5 tl [5, 7, 9] gives [7, 9] • In F#, a list looks like: [5; 7; 9]

Vishnu Institute of technology – Website: www.vishnu.edu.in

List Types (cont...) • In Python, lists are mutable and can contain elements of different types. Ex: myList = [3, 5.8, "grape"] myList[1] gives 5.8 as list index starts with 0 in Python.

del myList[1] removes the second element in the list. Vishnu Institute of technology – Website: www.vishnu.edu.in

List Types (cont...) • Python includes a powerful mechanism for creating arrays known as list comprehensions which was first introduced in the functional programming language Haskell. • In list comprehension, a function is applied to each of the elements of a given array and a new array is created from the results. • Syntax of list comprehension in Python is as follows: [x * x for x in range(12) if x % 3 == 0] range(12) creates an array with values 0 to 11 and square all the numbers which are exactly divisible by 3. The result list is: [0, 9, 36, 81]

Vishnu Institute of technology – Website: www.vishnu.edu.in

List Types (cont...) • List comprehension in Haskell: [n * n | n <- [1..10]] • List comprehension in F#: let myArray = [|for i in 1 .. 5 -> (i * i) |];;

Vishnu Institute of technology – Website: www.vishnu.edu.in

Union Types •

A union is a type whose variables may store different type values at different times during program execution.

•

Design Issues: – –

Should type checking be required? Should unions be embedded in records?

•

In C and C++, unions are called as free unions as they are not type checked.

•

Type checking of unions requires that each union construct include a type indicator. Such an indicator is called a tag or discriminant and a union with discriminant is called a discriminated union.

•

ALGOL 68 introduced discriminated unions and are supported by Ada, ML, Haskell and F#.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Union Types – Ada Union Types • In Ada, the user is allowed to specify variables of a variant record (union) type that will store only one of the possible type values in the variant. Such a restricted variable is called a constraint variant variable.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Union Types – Ada Union Types (cont...) Example:

Form is tag or discriminant

Vishnu Institute of technology – Website: www.vishnu.edu.in

Union Types – Ada Union Types (cont...) Consider the following varaibles:

Figure_1 is unconstrained variable Figure_2 is constraint variant variable

Type of Figure_1 can change based on the assignment shown above.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Union Types – Ada Union Types (cont...)

Adopted from “Concepts of Programming Languages – Sebesta” Vishnu Institute of technology – Website: www.vishnu.edu.in

Union Types – F# Union Types Example:

intReal is the union type. IntValue and RealValue are constructors. Values of type intReal can be created using the constructors as if they were a function as show below:

Vishnu Institute of technology – Website: www.vishnu.edu.in

Union Types – F# Union Types (cont...) To display the type of the intReal union, the following function could be used:

The following lines show calls to this function and the output:

Vishnu Institute of technology – Website: www.vishnu.edu.in

Union Types – Implementation • Unions are implemented by simply using the same address for every possible variant. • Sufficient storage for the largest variant is allocated. • The tag of a discriminated union is stored with the variant in a record like structure. Vishnu Institute of technology – Website: www.vishnu.edu.in

Union Types – Implementation (cont...) Compile-time Descriptor:

Adopted from “Concepts of Programming Languages – Sebesta” Vishnu Institute of technology – Website: www.vishnu.edu.in

Pointer and Reference Types • A pointer is a type in which the variables have a range of values that consists of memory addresses and a special value nil (null). • Uses of pointers: – Power of indirect addressing (assembly lang.) – Dynamic memory management (heap) Vishnu Institute of technology – Website: www.vishnu.edu.in

Pointer and Reference Types (cont...) • Design issues: – What are the scope and lifetime of a pointer variable? – What is the lifetime of a heap dynamic variable? – Are pointers restricted by the type of value they point? – Are pointers used for dynamic storage management, indirect addressing or both? – Should the language support pointer types, reference types, or both? Vishnu Institute of technology – Website: www.vishnu.edu.in

Pointer and Reference Types – Pointer Operations • Fundamental pointer operations are assignment and dereferencing. • Accessing the value pointed by the pointer is called dereferencing. (Ex: * in C and C++) • In C and C++ there are two ways a pointer can be used to reference a field of a record (structure): – Using * (Ex: (*s).age) – Using -> (Ex: s->age)

• Language which support dynamic memory management (heap) should provide explicit operations for allocation. – C provides dynamic memory management functions – C++ and Java provides new operator

Vishnu Institute of technology – Website: www.vishnu.edu.in

Pointer and Reference Types – Pointer Problems • First high-level programming language to include pointers is PL/I. • A reference type is a pointer with restricted operations. • A dangling pointer is a pointer that contains the address of a heap-dynamic variable that has been deallocated. Vishnu Institute of technology – Website: www.vishnu.edu.in

Pointer and Reference Types – Pointer Problems (cont...) • A lost heap-dynamic variable is an allocated heap-dynamic variable which is no longer accessible to the user program. (Ex: garbage) • Lost heap-dynamic variable scenario is also called as memory leakage.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Pointers in Ada • Ada’s pointers are called access types. • The dangling pointer problem is partially alleviated by Ada’s design. • The lost heap-dynamic variable problem is not eliminated as Ada supports explicit deallocation using Unchecked_Deallocation. Vishnu Institute of technology – Website: www.vishnu.edu.in

Pointers in C and C++ • C and C++ supports pointer arithmetic which makes them special. • C and C++ pointers can point to any variable (of any type) or any memory location which makes them dangerous. • In C and C++ the operator * denotes the dereferencing operation and the & operator is used for grabbing the address of a variable.

• C and C++ supports void pointers which can point to variables of any type.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Reference Types • A reference type is similar to a pointer except that unlike pointers which refers memory address, a reference refers to an object or value in memory. • Unlike pointers, there is no reference arithmetic. • C++ supports reference types as formal parameters in functions. These provide two-way communication between the caller and callee. • For safety reasons, Java removed pointers altogether.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Type Checking • Type checking is the activity of ensuring that the operands of an operation are of compatible types. • Automatic type conversion done by the compiler is called as coercion. • Explicit type conversion is known as type casting. • Dynamic type binding requires type checking at run time, which is called as dynamic type checking. Vishnu Institute of technology – Website: www.vishnu.edu.in

Arithmetic Expressions • In programming languages, arithmetic expressions consist of operators, operands, parentheses, and function calls. • An operator can be unary, meaning it has a single operand, binary, meaning it has two operands, or ternary, meaning it has three operands. • In most programming languages, binary operators are infix, prefix.

• The purpose of an arithmetic expression is to specify an arithmetic computation. Vishnu Institute of technology – Website: www.vishnu.edu.in

Arithmetic Expressions (cont..) Design issues are : • What are the operator precedence rules? • What are the operator associativity rules? • What is the order of operand evaluation? • Are there restrictions on operand evaluation side effects? • Does the language allow user-defined operator overloading? • What type mixing is allowed in expressions? Vishnu Institute of technology – Website: www.vishnu.edu.in

Operator Evaluation Order • The operator precedence and associativity rules of a language dictate the order of evaluation of its operators.

Precedence: • The value of an expression depends at least in part on the order of evaluation of the operators in the expression. Consider the following expression: a+b*c • Suppose the variables a, b, and c have the values 3, 4, and 5, respectively. If evaluated left to right. Vishnu Institute of technology – Website: www.vishnu.edu.in

• The operator precedence rules for expression evaluation partially define the order in which the operators of different precedence levels are evaluated.

• The precedence's of the arithmetic operators of Ruby and the C-based languages are as follows: Ruby C-Based Languages • Highest • unary • Lowest binary

** +, *, /, % +, -

postfix ++, -prefix ++, --, unary +, *, /, % binary +, -

Vishnu Institute of technology – Website: www.vishnu.edu.in

Associativity • An operator can have either left or right associativity, meaning that when there are two adjacent operators with the same precedence. • Consider the following expression: a-b+c–d • Associativity in common languages is left to right, except that the exponentiation operator (**) sometimes associates right to left. In the Java expression a-b+c here the left operator is evaluated first

Vishnu Institute of technology – Website: www.vishnu.edu.in

Associativity (cont..) • Exponentiation in Fortran and Ruby is right associative, so in the expression. A ** B ** C here the right operator is evaluated first. • In Ada, exponentiation is non associative, which means that the expression A ** B ** C is illegal. • Such an expression must be parenthesized to show the desired order, as in either (A ** B) ** C or A ** (B ** C) • In Visual Basic, the exponentiation operator, ^, is left associative.

Vishnu Institute of technology – Website: www.vishnu.edu.in

• The associativity rules for a few common languages are given here: Language • Ruby

• C-based languages • Ada

Associativity Rule Left: *, /, +, Right: ** Left: *, /, %, binary +, binary Right: ++, --, unary -, unary + Left: all except ** Nonassociative: **

Vishnu Institute of technology – Website: www.vishnu.edu.in

Conditional Expressions • if-then-else statements can be used to perform a conditional expression assignment. For example, consider if (count == 0) average = 0; else average = sum / count; • In the C-based languages, this code can be specified more conveniently in an assignment statement using a conditional expression, which has the form expression_1 ? expression_2 : expression_3 • where expression_1 is interpreted as a Boolean expression. If expression_1 evaluates to true, the value of the whole expression is the value of expression_2; otherwise, it is the value of expression_3.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Type Conversions • Type conversions can be either explicit or implicit.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Relational and Boolean Expressions Relational Expressions • Use relational operators and operands of various types. • Evaluate to some Boolean representation. • Operator symbols used vary somewhat among languages (!=, /=, .NE., <>, #)

Vishnu Institute of technology – Website: www.vishnu.edu.in

• The syntax of the relational operators for equality and inequality differs among some programming languages. • For example ,for inequality : The C-based languages use !=, Ada uses/=, Lua uses ~=, Fortran 95+ uses .NE. or <>, and ML and F# use <>. • JavaScript and PHP have two additional relational operators, === and !==. These are similar to their relatives, == and !=. • For example, the expression "7" == 7 is true in JavaScript, because when a string and a number are the operands of a relational operator, the string is coerced to a number.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Boolean Expressions • Operands are Boolean and the result is Boolean. • The operators usually include those for the AND, OR, and NOT operations, and sometimes for exclusive OR and equivalence.

• Example operators FORTRAN 77 .AND. .OR. . NOT.

FORTRAN 90 and or not

Vishnu Institute of technology – Website: www.vishnu.edu.in

C && || !

Ada and or not xor

• The precedence of the arithmetic, relational, and Boolean operators in the C-based languages is as follows: Highest postfix ++, -unary +, -, prefix ++, --, ! *, /, % binary +, <, >, <=, >= =, != && Lowest || • Perl, Ruby provides two sets of the binary logical operators ie; AND(&&),OR(||) Vishnu Institute of technology – Website: www.vishnu.edu.in

Short-Circuit Evaluation • short-circuit evaluation of an expression is one in which the result is determined without evaluating all of the operands and/or operators. • For example, the value of the arithmetic expression (13 * a) * (b / 13 - 1) if a is 0, there is no need to evaluate (b / 13 - 1) or perform the second multiplication. Example: (a>=0) && (b<10) if the first condition is false then the result will be false.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Assignment Statements Simple Assignments :

• ALGOL 60 pioneered the use of := as the assignment operator, which avoids the confusion of assignment with equality. Ada also uses this assignment operator. Conditional Targets : • Perl allows conditional targets on assignment statements. For example, consider ($flag ? $count1 : $count2) = 0; which is equivalent to if ($flag) { $count1 = 0; } else { $count2 = 0; } Vishnu Institute of technology – Website: www.vishnu.edu.in

Assignment Statements (cont..) Compound Assignment Operators: • A compound assignment operator is a shorthand method of specifying a commonly needed form of assignment. • Compound assignment operators were introduced by ALGOL 68, were later adopted in a slightly different form by C, and are part of the other C-based languages, as well as Perl, JavaScript, Python, and Ruby. • For example, sum += value; is equivalent to sum = sum + value; Vishnu Institute of technology – Website: www.vishnu.edu.in

Assignment Statements (cont..) Unary Assignment Operators: • The C-based languages, Perl, and JavaScript include two special unary arithmetic operators. Example: sum = ++ count;

Assignment as an Expression: • C-based languages, Perl, and JavaScript, the assignment statement produces a result, which is the same as the value assigned to the target. Example1: while ((ch = getchar()) != Example2: a = b + (c = d / b) - 1 Vishnu Institute of technology – Website: www.vishnu.edu.in

EOF) { ... }

Mixed-Mode Assignment • Assignment statements can also be mixed-mode, for example int a = 2, b = 3; float c; c = a / b; • C allows mixed-mode assignments; The coercion takes place only after the right side expression has been evaluated. • Java and C# allow only widening assignment coercions. • In Ada, there is no assignment coercion. Vishnu Institute of technology – Website: www.vishnu.edu.in

Control Structures Control Statements: Evolution • FORTRAN I control statements were based directly on IBM 704 hardware. • Much research and argument in the 1960s about the issue. • One important result: It was proven that all algorithms represented by flowcharts can be coded with only two-way selection and logically controlled iterations.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Control Structures (cont..) • A control structure is a control statement and the statements whose execution it controls • Design issue – Should a control structure have multiple entries?

Vishnu Institute of technology – Website: www.vishnu.edu.in

Selection Statements • A selection statement provides the means of choosing between two or more execution paths in a program • Two general categories: Two-way selectors Multiple-way selectors

Vishnu Institute of technology – Website: www.vishnu.edu.in

Two-Way Selection Statements • General form:

Design Issues: –What is the form and type of the control expression? – How are the then and else clauses specified? – How should the meaning of nested selectors be specified? Vishnu Institute of technology – Website: www.vishnu.edu.in

The Control Expression • If the then reserved word is not used. – control expressions are specified in parentheses. • If the then reserved word is used. – Less need for parentheses. • In C89, arithmetic expressions were used as control expressions. • In Ada, Java, Ruby, and C#, only Boolean expressions can be used.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Nesting Selectors • Java example

• Which

if gets the else? • Java's static semantics rule: else matches with the nearest if

Vishnu Institute of technology – Website: www.vishnu.edu.in

Nesting Selectors (cont..) • To force an alternative semantics, compound statements may be used:

• The above solution is used in C, C++, and C#

Vishnu Institute of technology – Website: www.vishnu.edu.in

Nesting Selectors in Perl • Perl requires that all then and else clauses to be compound, so it does not have the problem.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Using a Special Word Also Resolves the Problem…

• In Ruby outer if

• Here the end reserved word closes the nested if , it is clear that the else clause is matched to the inner then clause.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Multiple-Way Selection Statements • Allow the selection of one of any number of statements or statement groups. • Design Issues: 1. What is the form and type of the control expression? 2. How are the selectable segments specified? 3. Is execution flow through the structure restricted to include just a single selectable segment? 4. How are the case values specified? 5. What is done about unrepresented expression values?

Vishnu Institute of technology – Website: www.vishnu.edu.in

Multiple-Way Selection: Examples • C’s switch statement

• Design Choices for C’s switch 1. Control expression and constant expressions are some integer type 2. Selectable segments can be statement sequences, blocks, or compound statements 3. Any number of segments can be executed in one execution of the construct (there is no implicit branch at the end of selectable segments) 4. default clause is for unrepresented values (if there is no default, the whole statement does nothing)

Vishnu Institute of technology – Website: www.vishnu.edu.in

In C, Control May Flow More Than One Selectable Codes…

Vishnu Institute of technology – Website: www.vishnu.edu.in

The Ada case Statement

• once a stmt_sequence execution is completed, control is passed to the first statement after the case statement. • More reliable than C’s switch . Vishnu Institute of technology – Website: www.vishnu.edu.in

More On The Ada case Statement • choice list can include: – Sub ranges e.g., 10..15 – Boolean OR operators. e.g., 1..5 | 7 | 15..20 • The choice lists must be exhaustive – Often accomplished with when others clause – This makes it more reliable

Vishnu Institute of technology – Website: www.vishnu.edu.in

Multiple-Way Selection Using else-if • Multiple Selectors can appear as direct extensions to two-way selectors, using else-if clauses, for example in Ada: if ... then ... elsif ... then ... elsif ... then ... else ... end if Vishnu Institute of technology – Website: www.vishnu.edu.in

Iterative Statements • The repeated execution of a statement or compound statement is accomplished either by iteration or recursion • General design issues for iteration control statements: 1. How is iteration controlled? 2. Where is the control mechanism in the loop?

Vishnu Institute of technology – Website: www.vishnu.edu.in

Counter-Controlled Loops • A counting iterative statement has a loop variable, and a means of specifying the initial and terminal, and stepsize values. • The initial and terminal, and stepsize specifications of a loop are called the loop parameters.

Vishnu Institute of technology – Website: www.vishnu.edu.in

Design Issues of Counter-Controlled Loops 1. What are the type and scope of the loop variable? 2. What is the value of the loop variable at loop termination? 3. Should it be legal for the loop variable or loop parameters to be changed in the loop body, and if so, does the change affect loop control? 4. Should the loop parameters be evaluated only once, or once for every iteration?

Vishnu Institute of technology – Website: www.vishnu.edu.in

Iterative Statements: FORTRAN 95

• Stepsize can be any value but zero. • Parameters can be expressions. • Design choices: 1. Loop variable must be INTEGER 2. Loop variable always has its last value 3. Loop parameters are evaluated only once 4. The loop variable cannot be changed in the loop, but the parameters can; because they are evaluated only once, it does not affect loop control Vishnu Institute of technology – Website: www.vishnu.edu.in

FORTRAN 95’s Do Example

Vishnu Institute of technology – Website: www.vishnu.edu.in

Iterative Statements: FORTRAN 95 • FORTRAN 95 : a second form:

Vishnu Institute of technology – Website: www.vishnu.edu.in

Iterative Statements: Ada

• discrete_range is a sub-range of an integer or enumeration type. • Scope of the loop variable is the range of the loop . • Loop variable is implicitly undeclared after loop termination. Vishnu Institute of technology – Website: www.vishnu.edu.in

Ada’s for Example

Vishnu Institute of technology – Website: www.vishnu.edu.in

Iterative Statements: C • The expressions can be whole statements, or even statement sequences, with the statements separated by commas. – The value of a multiple-statement expression is the value of the last statement in the expression. • There is no explicit loop variable. • Everything can be changed in the loop. • The first expression is evaluated once, but the other two are evaluated with each iteration. Vishnu Institute of technology – Website: www.vishnu.edu.in

Iterative Statements: Examples • C++ differs from C in two ways: 1. The control expression can also be Boolean 2. The initial expression can include variable definitions (scope is from the definition to the end of the loop body)

• Java and C# – Differs from C++ in that the control expression must be Boolean Vishnu Institute of technology – Website: www.vishnu.edu.in

Iterative Statements: Logically Controlled Loops • Repetition control is based on a Boolean • Design issues: – Pre-test or post-test? – Should the logically controlled loop be a special form of a counting loop or a separate statement?

Vishnu Institute of technology – Website: www.vishnu.edu.in

Logically-Controlled Loops: Examples • C and C++ have both pre-test and posttest logical loop statements. • Java is like C, except the control expression must be Boolean. • Ada has a pretest version, but no post-test . • FORTRAN 77 and 90 have neither. • Perl has two pre-test logical loops, while and until, but no post-test logical loop.

Vishnu Institute of technology – Website: www.vishnu.edu.in

User-Located Loop Control Mechanisms break and continue • C , C++, Ruby, and C# have unconditional unlabeled exits (break). • Unconditional; for any loop or switch; one level only. • Java and Perl have unconditional labeled break statement: control transfers to the label. • An alternative: continue statement; it skips the remainder of this iteration, but does not exit the loop. Vishnu Institute of technology – Website: www.vishnu.edu.in

break and continue

Vishnu Institute of technology – Website: www.vishnu.edu.in

A break to the Outer Loop in Java

Vishnu Institute of technology – Website: www.vishnu.edu.in

Iterative Statements: Iteration Based on Data Structures • Number of elements of in a data structure control loop iteration • Control mechanism is a call to an iterator function that returns the next element in some chosen order, if there is one; else loop is terminated • C's for can be used to build a user-defined iterator:

Vishnu Institute of technology – Website: www.vishnu.edu.in

Unconditional Branching • Transfers execution control to a specified place in the program. • Represented one of the most heated debates in 1960’s and 1970’s. • Well-known mechanism: goto statement. • Major concern: Readability. • Some languages do not support goto statement (e.g., Module2 and Java). • C# offers goto statement (can be used in switch statements). • Loop exit statements are restricted and somewhat camouflaged goto’s. Vishnu Institute of technology – Website: www.vishnu.edu.in

Guarded Commands • Suggested by Dijkstra. • Purpose: to support a new programming methodology that supports verification (correctness) during development . • Basis for two linguistic mechanisms for concurrent programming (in CSP and Ada). • Basic Idea: if the order of evaluation is not important, the program should not specify one

Vishnu Institute of technology – Website: www.vishnu.edu.in

Selection Guarded Command • Form

• Semantics: when construct is reached, – Evaluate all Boolean expressions – If more than one are true, choose one non deterministically – If none are true, it is a runtime error

Vishnu Institute of technology – Website: www.vishnu.edu.in

Loop Guarded Command • Form

• Semantics: for each iteration – Evaluate all Boolean expressions – If more than one are true, choose one non deterministically; then start loop again – If none are true, exit loop Vishnu Institute of technology – Website: www.vishnu.edu.in