Type Checking: Rules, Errors & Semantic Analysis

TAKEAWAYS:

• Type checking ensures type safety by validating operations (e.g., int + string fails) before runtime.
• Static typing (compile-time) catches errors early (e.g., Java), while dynamic typing (runtime) allows flexibility (e.g., Python).
• Type compatibility rules determine if two types can interact (e.g., int → float is allowed, but not vice versa).
• Type errors (e.g., mismatched declarations, invalid conversions) must be reported with descriptive messages (e.g., "Cannot convert string to int").
• Type inference (e.g., in ML or Rust) deduces types automatically from usage.
• Overloading and inheritance complicate type checking but enable polymorphism.

1. Introduction to Type Checking

Type checking is a semantic analysis phase in compilers that verifies:

• Type declarations match usage (e.g., int x = 5;).
• Operands in expressions are compatible (e.g., x + y where x is int and y is float).
• Function arguments match parameter types.
• Return types align with function declarations.

Why Type Checking Matters

• Prevents runtime crashes (e.g., dividing a string by 2).
• Improves code reliability (e.g., catching null pointer dereferences early).
• Enables optimizations (e.g., knowing a variable is int allows faster arithmetic).

2. Static vs. Dynamic Type Checking

Example in Nepalese Context:

• eSewa (static typing in backend services like Java/Spring) ensures secure financial transactions by validating types before processing payments.
• Python-based tools (dynamic typing) in NTC’s network monitoring allow quick scripting but require runtime checks.

3. Type Rules and Compatibility

A. Basic Type Rules

1. Assignment Compatibility:

   • A variable’s type must match its declaration.

     int x = 10;      // Valid
     int x = "hello"; // Error: Cannot convert string to int
     

2. Expression Compatibility:

   • Operands in an expression must be compatible types.
     • int + float → float (widening conversion allowed).
     • int + string → Error (incompatible types).

3. Function Call Compatibility:

   • Argument types must match parameter types.

     void greet(String name) { ... }
     greet(123); // Error: int cannot be converted to String
     

B. Type Conversion Rules

Example: Type Casting in C

float f = 3.14;
int i = (int)f; // Explicit narrowing: f = 3 (truncated)

Trace Table:

4. Type Errors and Recovery

flowchart TD
    A["Parse: `int x = 'hello';`"]
    B{"Type Check: `string` → `int`?"}
    B -->|"No"| C["Error: Incompatible Types"]
    C --> D["Recovery: Skip Token"]
    D --> E["Continue Parsing"]
    E --> F["Output: `int x = 5;` (if corrected)"]

Compiler recovery for invalid type assignment (string → int).

Common Type Errors

1. Type Mismatch:

   x = "10" + 5  # Error: str + int unsupported
   

2. Invalid Conversion:

   int y = (int)"hello"; // Error: Cannot cast String to int
   

3. Undefined Types:

   typedef int myInt;
   myInt x = 5.5; // Error: float cannot be assigned to myInt
   

Error Recovery Strategies

• Insert Implicit Conversions (e.g., int x = "10"; → int x = 10;).
• Skip the Invalid Token (e.g., ignore + in "hello" + 5).
• Report and Halt (for critical errors like missing semicolons).

Example: Error Recovery in a Compiler

flowchart TD
    A["Parse Expression"] --> B{"Types Compatible?"}
    B -->|"Yes"| C["Proceed"]
    B -->|"No"| D["Attempt Implicit Conversion"]
    D --> E{"Success?"}
    E -->|"Yes"| C
    E -->|"No"| F["Report Error<br/>Skip Token"]
    F --> C

5. Type Checking in Real-World Compilers

A. Java (Static Typing)

• Strict type checking catches errors at compile-time.
• Example: ArrayIndexOutOfBoundsException is prevented by bounds checking.

  int[] arr = {1, 2, 3};
  int x = arr[3]; // Compile-time error: Array index out of bounds
  

B. Python (Dynamic Typing)

• Flexible but runtime-checked.
• Example: TypeError if operations are invalid.

  x = "10"
  y = x + 5  # Runtime Error: can only concatenate str (not "int") to str
  

C. Rust (Advanced Static Typing)

• Ownership and borrowing enforce memory safety.
• Example: Compile-time borrow checker prevents dangling pointers.

  let x = 5;
  let y = &x; // Valid: y borrows x
  let z = &x; // Valid: multiple immutable borrows
  // let w = &mut x; // Error: cannot borrow x as mutable while y and z exist
  

In the Real World

1. eSewa (Nepal):

   • Uses static typing (Java/Spring Boot) for financial transactions.
   • Type checking ensures amount is BigDecimal (not String) before processing payments, preventing fraud.

2. Khalti API (Nepal):

   • Dynamic typing (Node.js/Python) allows quick integration but requires runtime type validation.
   • Example: A merchant’s order_id must be a UUID (not a String like "123").

3. NTC’s Network Monitoring (Python Scripts):

   • Dynamic typing helps parse logs quickly, but type errors (e.g., int vs. str in bandwidth data) crash scripts.
   • Solution: Use try-except blocks for graceful error handling.

4. NEPSE Stock Trading Platform:

   • Static typing (C#/.NET) ensures share_price is decimal (not string) to avoid calculation errors.

6. Worked Example: Type Checking in a Simple Language

Problem: Check the following C-like code for type errors:

int x = 5;
float y = x + 3.14;
char z = y + 'A';
printf("%c", z);

Solution:

1. Step 1: int x = 5; → Valid.
2. Step 2: float y = x + 3.14;
   • x (int) + 3.14 (float) → float (widening allowed).
   • State After Step 2:

     flowchart TD
         A["x: int = 5"] --> B["y: float = 8.14"]

3. Step 3: char z = y + 'A';
   • y (float) + 'A' (char/int) → Error: Cannot implicitly convert float to char.
   • Fix: Cast y to int:

     char z = (int)y + 'A'; // Valid: z = 8 + 65 = 73 ('I')
     

Trace Table:

7. Advanced Topics

A. Type Inference

• Example: ML (Functional Language)

  let x = 5;      (* Inferred as int *)
  let y = 3.14;   (* Inferred as float *)
  let z = x + y;  (* Error: int + float *)
  

• Solution: Explicit types or widening:

  let z = float x + y; (* z inferred as float *)
  

B. Overloading and Polymorphism

• Method Overloading (same name, different parameters):

  void print(int x) { ... }
  void print(String s) { ... } // Overloaded
  

• Type Checking: Ensures correct overload is called.

  print(5);    // Calls print(int)
  print("hi"); // Calls print(String)
  

C. Generic Programming (Templates in C++)

• Type Parameters allow reusable code:

  template<typename T>
  T max(T a, T b) { return (a > b) ? a : b; }
  

• Type Checking: Ensures a and b are the same type.

8. Exam Tip

What to Expect in TU/PU Exams

1. Short Questions (2-5 marks):

   • Define static vs. dynamic typing.
   • List 3 type errors and their fixes.
   • Explain type compatibility rules with examples.

2. Long Questions (10-15 marks):

   • Trace type checking for a given code snippet (like the worked example above).
   • Design a type checker for a subset of a language (e.g., arithmetic expressions).
   • Compare static and dynamic typing with pros/cons (use the table above).

3. Programming (5-10 marks):

   • Write a type checker for assignments/expressions (pseudocode or Python).
   • Example:

     def check_type_assign(lhs_type, rhs_type):
         if lhs_type == rhs_type:
             return True
         elif (lhs_type == "int" and rhs_type == "float"):
             return True  # Widening allowed
         else:
             return False
     

4. Application-Based Questions:

   • How does eSewa use type checking to prevent fraud?
   • Why does Python use dynamic typing for scripting?

Key Formulas/Concepts to Remember

9. Summary Checklist

Before the exam, ensure you can: ✅ Differentiate static vs. dynamic typing with examples. ✅ List 3 type errors and their fixes. ✅ Trace type checking for a given code snippet. ✅ Explain type compatibility rules (widening/narrowing). ✅ Describe real-world applications (eSewa, Khalti, NTC). ✅ Write a simple type checker in pseudocode.

In the real world

• eSewa (Nepal) uses static typing (Java/Spring Boot) to validate PaymentRequest objects before processing. The amount field must be a BigDecimal (not String), preventing fraudulent transactions like amount = "₹1000".
• Khalti API (Node.js/Python) dynamically checks types at runtime (e.g., order_id must be a UUID object, not a String like "123").
• NTC’s Python scripts for network monitoring fail if bandwidth data is miscast (e.g., int(512) vs. str("512")), requiring try-except blocks to handle ValueError gracefully.