Chapter 3: Basic concepts of Program
Variables and scopes: Introduction, names, variables, concept of binding, scope, scope and lifetime, referencing
environments, named constants, Operators.
Data types: Introduction, primitive, character, string types, user defined ordinal types,
Array, associative arrays, record, tuple types, list types, union types, pointer and
Reference types, type checking, strong typing and type equivalence.
Introduction to Variables and scopes:
Variables: Variables can also be considered as 'containers' which are used to hold more than one value
Scopes: The scope of a variable in a program is the lines of code in the program where the variable can be
accessed.
Scope and Variable names:
Global Scope: Variables declared outside procedures/functions.
Local Scope: Variables declared within procedures/functions.
Block Scope: Variables declared within blocks (e.g., if, loop).
Parameter Scope: Variables passed as procedure/function parameters.
Module Scope: Variables declared within modules.
Variable:
Static Variables: Retain value between procedure calls.
Dynamic Variables: Allocated on the heap.
Automatic Variables: Local variables automatically allocated/deallocated.
External Variables: Global variables accessed from other modules.
Concept of binding:
Binding: binding refers to the process of associating a name with an entity, such as a variable, function, or label.
Types of Binding:
Static Binding: Binding occurs at compile-time.
Dynamic Binding: Binding occurs at runtime.
Lexical Binding: Binding based on lexical scope.
Dynamic Scope Binding: Binding based on dynamic scope.
Binding Concepts:
Name Binding: Associating a name with an entity.
Variable Binding: Associating a variable with a value.
Function Binding: Associating a function with its definition.
Label Binding: Associating a label with a location.
Binding Techniques:
Declaration: Explicitly declaring variables, functions, or labels.
Definition: Defining functions or variables.
Assignment: Assigning values to variables.
Reference: Referencing entities through names or pointers.
Binding Scope:
Global Binding: Entities accessible globally.
Local Binding: Entities accessible within a procedure or function.
Block Binding: Entities accessible within a block.
Parameter Binding: Entities passed as parameters.
Binding Lifetime:
Static Lifetime: Entities exist for the entire program execution.
Dynamic Lifetime: Entities exist for a limited time.
Automatic Lifetime: Entities automatically created/destroyed.
Naveen Kumar H N MCA, BEd, KSET,NET Faculty Dept of BCA GFGCE Tumkur. 1
Binding Examples:
var x: Int; // Static binding of variable x
function add(a: Int, b: Int): Int { ... } // Static binding of function add
x := 5; // Dynamic binding of variable x
label loop: // Static binding of label loop.
Referencing environments: a referencing environment refers to the context in which references to variables,
functions, or labels are resolved.
Referencing Environment Concepts:
Scope: Region of the program where a reference is valid.
Binding: Association between a name and an entity.
Resolution: Process of finding the bound entity.
Context: Surrounding code influencing reference resolution.
Types of Referencing Environments:
Lexical Environment: Resolves references based on lexical scope.
Dynamic Environment: Resolves references based on dynamic scope.
Static Environment: Resolves references at compile-time.
Dynamic-Static Environment: Combines dynamic and static resolution.
Referencing Environment Components:
Symbol Table: Maps names to bound entities.
Scope Stack: Tracks active scopes.
Binding Table: Records bindings.
Reference Counting: Manages entity references.
Referencing Environment Operations:
Lookup: Finds bound entity.
Insert: Adds new binding.
Update: Modifies existing binding.
Delete: Removes binding.
Referencing Environment Examples:
x := 5; // Lexical environment resolves x
function add(a: Int, b: Int): Int { ... } // Dynamic environment resolves add
label loop: // Static environment resolves loop
Named constants: a named constant is a value that is assigned to a name and remains unchanged throughout the
program's execution.
Characteristics of Named Constants:
Immutable: Value cannot be changed.
Unique name: Each constant has a distinct name.
Global or local scope: Constants can be accessed within their scope.
Compile-time evaluation: Constants are evaluated at compile-time.
Types of Named Constants:
Integer constants (e.g., MAX_SIZE = 100)
Floating-point constants (e.g., PI = 3.14)
Character constants (e.g., NEWLINE = '\n')
String constants (e.g., GREETING = "Hello, World!")
Boolean constants (e.g., DEBUG_MODE = true)
Enumerated constants (e.g., COLOR_RED = 1, COLOR_GREEN = 2).
Operators: In the Principles of Programming Language (PPL), an operator is a symbol or keyword that performs a specific
operation on one or more operands.
Types of Operators:
1. Arithmetic Operators: +, -, *, /, %, etc.
2. Assignment Operators: =, +=, -=, *=, /=, etc.
Naveen Kumar H N MCA, BEd, KSET,NET Faculty Dept of BCA GFGCE Tumkur. 2
3. Comparison Operators: ==, !=, >, <, >= , <=
4. Logical Operators: &&, ||, !
5. Bitwise Operators: &, |, ^, ~, <<, >>
6. Unary Operators: +, -, !, ~
7. Ternary Operators: ?:
Introduction to Data Type: Data types in programming languages define the type of value a variable can hold, the
operations that can be performed on it, and the amount of memory allocated to store it.
Primitive Data Types:
Integer (int): whole numbers, e.g., 1, 2, 3
Floating Point (float): decimal numbers, e.g., 3.14, -0.5
Character (char): single characters, e.g., 'a', 'B'
Boolean (bool): true or false values
Void: no value or undefined value.
Character data types: It represents single characters, typically stored in a single byte.
Character Data Types:
Char (Character): 8-bit unsigned integer, e.g., 'a', 'B'
Unsigned Char (UCHAR): 8-bit unsigned integer, e.g., 'a', 'B'
Signed Char (SCHAR): 8-bit signed integer, e.g., 'a', 'B'
String types: It represents sequences of characters enclosed within double quote.
Character Array (C-style string): char str[] = "hello";
Null-terminated String (NTS): char str[] = "hello\0";
String Object (e.g., Java String, Python str): String str = "hello";
User-defined ordinal types : are the data types that allow users to define their own ordered sets of values.
Types of User-defined Ordinal Types:
Enumerations (Enums): define a set of named values. Example: enum Color { Red, Green, Blue }.
Subranges: define a subset of values from an existing type. Example: subtype Age is Integer range 0..120
User-defined integer types: define custom integer types. Example: type Age is range 0..120.
Definition of an Array : An array is a collection of elements of the same data type stored in contiguous memory
locations.
Characteristics:
Homogeneous: all elements have the same data type.
Fixed size: array size is determined at compile-time.
Indexed: elements are accessed using an index.
Contiguous memory: elements are stored in adjacent memory locations.
Types of Arrays:
One-dimensional array (1D): A one-dimensional array is a single list of elements, all of which share the same data
type.
Example: int arr[5]={a,b,c,d,e} 1 2 3 4
Two Dimensional Array(2D): A two-dimensional array is an array of arrays. Example : int arr[2][4]; 1.a b c d
2. f g h i
Multi-dimensional array (3D, etc.): A multi-dimensional array is an array with more than one level or
[Link]: int[][] myNumbers = { {1, 2, 3, 4}, {5, 6, 7} };
Array Advantages:
Efficient memory usage
Fast access and modification
Simple implementation
Array Disadvantages:
Fixed size (static arrays)
Difficult to insert/delete elements
Prone to indexing errors
Associative arrays: An associative array is a data structure that stores key-value pairs, where each key is unique and
maps to a specific value.
Naveen Kumar H N MCA, BEd, KSET,NET Faculty Dept of BCA GFGCE Tumkur. 3
Types of Associative Arrays:
Hash Table: Uses a hash function to map keys to indices.
Binary Search Tree: Uses a tree structure to store key-value pairs.
Linked List: Uses a linked list to store key-value pairs.
Advantages:
Fast lookup: Average case O(1) time complexity.
Flexible data structure: Can store various types of data.
Efficient insertion/deletion: Average case O(1) time complexity.
Disadvantages:
Space overhead: Requires additional memory for key-value pairs.
Collision resolution: Hash tables require collision resolution mechanisms.
Record: A record (also known as a struct or tuple) is a composite data type that stores multiple values of different types
in a single unit.
Properties:
Composite: Stores multiple values.
Heterogeneous: Values can be of different types.
Named fields: Each value is associated with a field name.
Fixed structure: Field names and types are defined at compile-time.
Record Advantages:
Grouping related data: Improves code organization.
Improved readability: Field names provide context.
Efficient memory usage: Compact storage.
Record Disadvantages:
Fixed structure: Limited flexibility.
Inheritance limitations: Records don't support inheritance.
Tuple : A tuple is a composite data type that stores multiple values of different types in a single unit, typically enclosed in
parentheses.
Types of Tuples:
Homogeneous tuple: All elements have the same type.
Heterogeneous tuple: Elements have different types.
Empty tuple: Zero elements.
Singleton tuple: One element.
Tuple Advantages:
Concise syntax: Simple and expressive notation.
Immutable: Ensures data integrity.
Flexible: Supports various data types.
Efficient: Compact memory representation.
Tuple Disadvantages:
Limited mutability: Cannot modify elements.
Fixed length: Cannot add/remove elements.
Less expressive: Than records or structs.
List: A list is a data structure that stores a collection of elements, allowing dynamic insertion, deletion, and modification.
Types of Lists:
Linear List: Elements are stored in contiguous memory locations.
Linked List: Elements are stored in non-contiguous memory locations, connected by pointers.
Circular List: Last element points to the first element.
Doubly Linked List: Each element has two pointers (previous and next).
Stack: Last-In-First-Out (LIFO) data structure.
Queue: First-In-First-Out (FIFO) data structure.
Dynamic Array: Resizable array-like data structure.
Advantages of Lists:
Dynamic Size: Lists can grow or shrink dynamically as elements are added or removed.
Flexible Data Structure: Lists can store elements of different data types.
Efficient Insertion/Deletion: Lists allow efficient insertion and deletion of elements at any position.
Naveen Kumar H N MCA, BEd, KSET,NET Faculty Dept of BCA GFGCE Tumkur. 4
Order Preservation: Lists maintain the order of elements.
Easy Traversal: Lists can be easily traversed using iterators or indexes.
Disadvantages of Lists:
Slow Search: Searching for an element in a list can be slow (O(n) time complexity).
Memory Overhead: Lists require additional memory for pointers or indexes.
Complexity: Lists can be complex to implement, especially for large datasets.
Random Access: Lists do not support random access as efficiently as arrays.
Cache Misses: Lists can suffer from cache misses due to non-contiguous memory.
Union: A union type is a data type that can hold values of different types, but only one type at a time.
Types of Union:
Tagged Union: Explicitly tagged with type information.
Untagged Union: No explicit type information.
Variant Record: Combination of union and record.
Advantages:
Memory efficiency: Reduced memory usage.
Flexibility: Can handle multiple types.
Type safety: Ensures correct type usage.
Improved code readability: Explicit type information.
Disadvantages:
Complexity: Requires runtime type checking.
Performance overhead: Additional checks and tagging.
Limited support: Not all languages support union types.
Pointer and Reference types
Pointers: A pointer is a variable that holds the memory address of another variable.
Types of Pointers:
Raw pointer: Unchecked, direct access to memory.
Smart pointer: Managed, automatic memory deallocation.
Null pointer: Represents invalid or non-existent memory address.
Reference : A reference is an alias for an existing variable.
Types of References:
L-value reference: References variable with identity.
R-value reference: References temporary value.
Constant reference: References constant value.
Type checking: Type checking is the process of verifying that the data type of a value matches the expected
type of a variable, function, or expression.
Types of Type Checking:
Static Type Checking: Performed at compile-time.
Dynamic Type Checking: Performed at runtime.
Statically-Typed: Languages with static type checking (e.g., C, Java).
Dynamically-Typed: Languages with dynamic type checking (e.g., Python, JavaScript).
Strong typing and Type equivalence
Strong Type Checking: Strong type checking ensures that the type system prevents type errors at compile-time or runtime.
Characteristics:
Statically-typed: Types are known at compile-time.
Type safety: Prevents type-related errors.
No implicit conversions: Explicit type conversions required.
No null or undefined values: Optional types or null safety.
Type equivalence: Equivalence in type systems ensures that two types are considered equal if they have the same
structure and properties.
Types of Equivalence:
Structural Equivalence: Based on the structure of the entities.
Nominal Equivalence: Based on the names or identifiers of the entities.
Behavioral Equivalence: Based on the behavior or semantics of the entities.
Extensional Equivalence: Based on the extension or values of the entities.
Intensional Equivalence: Based on the intension or meaning of the entities.
Naveen Kumar H N MCA, BEd, KSET,NET Faculty Dept of BCA GFGCE Tumkur. 5