Imperative Programming

Imperative programming describes computation as a sequence of statements that change program state. It directly maps to how hardware executes — the von Neumann model of fetch-decode-execute.

How programming paradigms relate: imperative, OOP, functional, and logic

Core Concepts

Statements and State

A program is a sequence of commands that modify the state (values stored in memory).

x ← 5             // state: x = 5
x ← x + 1         // state: x = 6
x ← x * 2         // state: x = 12

State: The collection of all variable values at a given point in execution. Execution proceeds by transforming state step by step.

Variables and Assignment

A variable is a named location in memory. Assignment changes its value.

x = expression    // evaluate expression, store result in x

Key distinction from math: In math, x = x + 1 is a contradiction. In imperative programming, it means "compute x + 1 and store the result back in x."

Control Flow

Sequential Execution

Statements execute one after another, top to bottom.

Conditional (Selection)

IF condition
    // executed if condition is true
ELSE IF other_condition
    // executed if other_condition is true
ELSE
    // executed otherwise

Match / Switch:

MATCH value
    1:        PRINT "one"
    2 OR 3:   PRINT "two or three"
    4 TO 10:  PRINT "four to ten"
    DEFAULT:  PRINT "other"

Loops (Iteration)

While loop: Repeat while condition is true.

WHILE condition
    // body

For loop: Iterate over a range or collection.

FOR i ← 0 TO n - 1
    // body executes n times
FOR EACH item IN collection
    // iterate over collection

Do-while / loop: Execute at least once.

LOOP
    // body
    IF condition THEN BREAK

Loop control: break exits the loop. continue skips to the next iteration.

Structured Programming Theorem (Böhm-Jacopini)

Any computable function can be expressed using only three control structures:

Sequence (one statement after another)
Selection (if-else)
Iteration (while loops)

No goto needed. This was revolutionary — it established that structured programming is sufficient for all computation.

Procedures and Functions

Procedural decomposition: Break a program into named, reusable units.

FUNCTION CALCULATE_AREA(width, height)
    RETURN width * height

PROCEDURE PRINT_RECTANGLE(width, height)
    area ← CALCULATE_AREA(width, height)
    PRINT "Area: ", area

Parameters: Pass data into functions.

By value: Copy the data. Callee's changes don't affect caller.
By reference: Pass a pointer/reference. Callee can modify caller's data.
By move: Transfer ownership (Rust's default for non-Copy types).

Return values: Functions produce results.

Side effects: A function has a side effect if it modifies state outside its local scope (global variables, I/O, mutable references). Pure functions have no side effects.

Mutation and Side Effects

Mutable State

counter ← 0

PROCEDURE INCREMENT()
    counter ← counter + 1   // side effect: modifies external state

Advantages: Efficient (modify in place, no copies). Natural for some algorithms (sorting, graph traversal).

Disadvantages: Hard to reason about (what's the value of x?). Bugs from unexpected mutations. Difficult to parallelize (data races). Order-dependent.

Aliasing

Two references pointing to the same memory location.

data ← [1, 2, 3]
a ← mutable reference to data
// b ← reference to data   // ERROR: can't have mutable and immutable ref simultaneously

Aliasing + mutation = bugs. Rust's borrow checker prevents this at compile time.

Structured Programming

Dijkstra's "Go To Statement Considered Harmful" (1968)

goto creates unreadable "spaghetti code." Structured control flow (if/while/for) makes programs easier to understand and prove correct.

Modern stance: goto is rarely used but not universally banned. It's occasionally useful for error handling in C (cleanup on failure) and performance-critical inner loops. Most languages don't even have goto (Rust, Python, Java).

Block Structure

Variables have scope — they exist only within their enclosing block.

BEGIN BLOCK
    x ← 10        // x exists here
    BEGIN BLOCK
        y ← 20    // y exists here
        // x is also accessible
    END BLOCK
    // y no longer exists
END BLOCK
// x no longer exists

Lifetime: How long a variable's memory is valid. Rust makes lifetimes explicit to prevent use-after-free.

Procedural Abstraction

Hide implementation details behind a function interface. The caller doesn't need to know how — only what.

// The caller doesn't care about the sorting algorithm
PROCEDURE SORT(data)   // ... implementation hidden ...

Imperative Patterns

Accumulator Pattern

Build a result by iterating and accumulating.

FUNCTION SUM(arr)
    total ← 0
    FOR EACH x IN arr
        total ← total + x
    RETURN total

Search Pattern

Scan through data looking for a match.

FUNCTION FIND(arr, target)
    FOR i ← 0 TO length(arr) - 1
        IF arr[i] = target THEN RETURN i
    RETURN NOT_FOUND

State Machine

Track state explicitly and transition based on input.

STATES: Start, InWord, InSpace

FUNCTION COUNT_WORDS(s)
    state ← InSpace
    count ← 0
    FOR EACH c IN characters of s
        IF state = InSpace AND c is not whitespace
            state ← InWord
            count ← count + 1
        ELSE IF state = InWord AND c is whitespace
            state ← InSpace
    RETURN count

Imperative Languages

| Language | Era | Key Features | |---|---|---| | Fortran (1957) | First high-level language. Scientific computing. | | COBOL (1959) | Business data processing. Verbose, English-like. | | C (1972) | Systems programming. Close to hardware. | | Pascal (1970) | Teaching structured programming. | | Ada (1983) | Safety-critical systems. Strong typing. | | Go (2009) | Concurrent systems programming. Simple imperative core. | | Rust (2015) | Systems programming with safety guarantees. Imperative + functional. |

Applications in CS

Systems programming: OS kernels, drivers, embedded systems — imperative style maps directly to hardware.
Performance-critical code: Direct control over memory layout and mutation enables optimization.
Game development: Game loops are fundamentally imperative (update state each frame).
Scripting: Shell scripts, build scripts — sequences of commands.
State machines: Network protocols, parsers, UI controllers — naturally imperative.