Principles of Programming Languages

P. S. Suryateja

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 r-value 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 stack-dynamic.

​

• 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 static-scoped 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 – Floating-Point

• 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 – Floating-Point

• 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 – Floating-Point

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 built-in 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 five 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:

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, catenation, 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 multi-dimensional 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:

- 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.

Adopted from “Concepts of Programming Languages – Sebesta”

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