Module 4: Overview

This module introduces the foundational concepts studied in Principles of Programming Languages (PoPL) — a field concerned with the design, analysis, and implementation of programming languages themselves. Rather than focusing on how to write programs in a specific language, PoPL asks deeper questions: Why are languages designed the way they are? What trade-offs do different design choices introduce? How do we reason formally about what a program does?

Understanding these concepts makes you a more adaptable programmer — one who can pick up new languages quickly, reason about subtle bugs (especially around scoping, typing, and memory), and make informed design decisions when building systems or DSLs. Code examples throughout this module are written in multiple languages — C, Python, Haskell, and JavaScript — to illustrate how the same concept appears differently across paradigms.

• 1Section 1: Programming Paradigms
• 2Section 2: Syntax, Grammars, and Semantics
• 3Section 3: Type Systems
• 4Section 4: Scoping and Binding
• 5Section 5: Functions and Higher-Order Programming
• 6Section 6: Memory Management Strategies

Section 1: Programming Paradigms

A programming paradigm is a fundamental style or model of programming that shapes how a programmer structures and thinks about solutions. Most modern languages support multiple paradigms, but they tend to favor one strongly. Understanding the major paradigms helps you recognise which tool fits a given problem — and why the designers of a language made the choices they did.

1.1 Imperative Programming

Imperative programming is the oldest and most directly machine-aligned paradigm. Programs are written as a sequence of statements that explicitly change program state. The programmer specifies how to compute a result, step by step. C is the canonical imperative language.

// Compute the sum of an array imperatively
int sum_array(int* arr, int n) {
    int total = 0;          // mutable state
    for (int i = 0; i < n; i++) {
        total += arr[i];    // explicit step-by-step mutation
    }
    return total;
}

1.2 Object-Oriented Programming (OOP)

OOP organises programs around objects — bundles of data (attributes) and the operations that act on that data (methods). The four core principles are encapsulation, abstraction, inheritance, and polymorphism. Java, Python, and C++ are primary examples.

class Animal:
    def __init__(self, name):
        self.name = name        # encapsulated state

    def speak(self):            # overridden by subclasses (polymorphism)
        raise NotImplementedError

class Dog(Animal):              # inheritance
    def speak(self):
        return f"{self.name} says: Woof!"

class Cat(Animal):
    def speak(self):
        return f"{self.name} says: Meow!"

animals = [Dog("Rex"), Cat("Whiskers")]
for a in animals:
    print(a.speak())            # same interface, different behaviour

1.3 Functional Programming

Functional programming treats computation as the evaluation of mathematical functions. The key ideas are immutability (data is never changed in place), pure functions (no side effects — same input always gives same output), and first-class functions (functions are values that can be passed and returned). Haskell is the purest functional language; Python and JavaScript support a functional style.

-- Pure function: no mutation, no side effects
sumList :: [Int] -> Int
sumList []     = 0
sumList (x:xs) = x + sumList xs

-- The same computation using a built-in fold
sumList' :: [Int] -> Int
sumList' = foldr (+) 0

-- Functions are first-class values
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)

1.4 Logic / Declarative Programming

In declarative programming the programmer specifies what the answer should satisfy, not how to compute it. Logic programming (Prolog) takes this furthest — programs are sets of logical facts and rules, and the runtime searches for solutions by inference. SQL is the most widely-used declarative language.

% Facts
parent(tom, bob).
parent(bob, ann).

% Rule: X is an ancestor of Y if X is a parent of Y,
%       or X is a parent of someone who is an ancestor of Y.
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

% Query: ?- ancestor(tom, ann).  => true

Paradigm Comparison

Useful Videos

Watch on YouTube

Watch on YouTube

Watch on YouTube

Section 2: Syntax, Grammars, and Semantics

Every programming language needs a precise, unambiguous definition of what constitutes a valid program. This definition is split into two layers: syntax (what sequences of characters are legal) and semantics (what those legal programs mean or do).

2.1 Formal Grammars and BNF

Language syntax is most commonly described using a context-free grammar (CFG). The standard notation for writing these is Backus–Naur Form (BNF), introduced by John Backus and Peter Naur to define ALGOL 60. In BNF, <name> denotes a non-terminal (something to be expanded), ::= means "is defined as", and | separates alternatives.

<expr>   ::= <term> | <expr> "+" <term> | <expr> "-" <term>
<term>   ::= <factor> | <term> "*" <factor> | <term> "/" <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= <digit> | <number> <digit>
<digit>  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

This grammar encodes operator precedence: multiplication binds tighter than addition because <term> is nested more deeply than <expr>. Extended BNF (EBNF) adds shorthand for optional elements ([ ]), repetition ({ }), and grouping, making grammars more concise.

2.2 Parse Trees and ASTs

A parse tree (or concrete syntax tree) is a tree that shows every step of the grammar derivation. An Abstract Syntax Tree (AST) is a simplified version that strips away redundant structure (parentheses, keywords) and retains only the semantic content. Compilers and interpreters work almost exclusively with ASTs.

For example, parsing 3 + 4 * 2 with the grammar above produces an AST where the * node is a child of the + node, correctly reflecting that multiplication has higher precedence.

2.3 Semantics

Syntax defines form; semantics defines meaning. There are three main approaches:

• 1Operational semantics — defines meaning by specifying how a program executes on an abstract machine, step by step.
• 2Denotational semantics — maps programs to mathematical objects (usually functions). Meaning is compositional: the meaning of a compound phrase is built from the meanings of its parts.
• 3Axiomatic semantics — defines meaning using logical assertions (pre/post-conditions). The foundation of formal program verification (Hoare logic).

Useful Videos

Watch on YouTube

Watch on YouTube

Watch on YouTube

Section 3: Type Systems

A type system is a set of rules that assigns a property called a type to every term in a program — variables, expressions, functions, etc. Type systems exist to prevent a class of program errors at compile time or runtime, and to communicate intent. Understanding type systems is critical for understanding why languages behave the way they do.

3.1 Static vs. Dynamic Typing

In a statically typed language, types are checked at compile time. Type errors are caught before the program runs. C, Java, Haskell, and Rust are statically typed. In a dynamically typed language, types are checked at runtime. Python, JavaScript, and Ruby are dynamically typed.

x = "hello"
y = 42
print(x + y)   # TypeError raised only when this line executes

char* x = "hello";
int   y = 42;
// x + y would be a pointer-arithmetic expression, not a type error,
// but assigning it to a char* would warn or error at compile time.

3.2 Strong vs. Weak Typing

Strong typing means the language rarely performs implicit type coercions — you must convert types explicitly. Weak (loose) typing means the runtime will silently coerce values between types. Note that strong/weak is separate from static/dynamic: Python is dynamically but strongly typed; C is statically but relatively weakly typed; JavaScript is both dynamic and weakly typed.

console.log(1 + "2");    // "12" — number silently coerced to string
console.log(true + 1);   // 2   — boolean silently coerced to number
console.log([] + {});    // "[object Object]"

3.3 Type Inference

Type inference is the ability of a compiler to deduce the type of an expression automatically, without requiring the programmer to write explicit annotations. Haskell's Hindley–Milner type inference is the gold standard: in most cases you never need to write a type annotation and yet the program is fully statically typed.

-- No type annotations needed; GHC infers these automatically:
double x = x * 2
-- GHC infers: double :: Num a => a -> a

addPair (x, y) = x + y
-- GHC infers: addPair :: Num a => (a, a) -> a

3.4 Polymorphism

Polymorphism allows a single piece of code to work with values of different types. The three most important forms are:

• —Parametric polymorphism — a function works for any type (generics in Java/C#, type variables in Haskell). Example: identity :: a -> a.
• —Subtype polymorphism — a function that accepts a type also accepts any subtype (the basis of OOP inheritance and interface dispatch).
• —Ad-hoc polymorphism — the same function name behaves differently for different types; achieved via function overloading or type classes.

Useful Videos

Watch on YouTube

Watch on YouTube

Watch on YouTube

Watch on YouTube

Section 4: Scoping and Binding

Name binding is the association between a name (identifier) and the entity it refers to. Scope is the region of a program where a binding is visible. Scoping rules are one of the most consequential design decisions in any programming language, because they determine what a name means at any given point in the code.

4.1 Lexical (Static) Scope

In lexical scoping, the scope of a name is determined by the textual structure of the source code — specifically, by where the name is declared. A function can access names from its own body and from the enclosing blocks where it was defined, regardless of where it is called from. The vast majority of modern languages use lexical scoping.

x = "global"

def outer():
    x = "outer"          # new binding in outer's scope

    def inner():
        print(x)         # resolves to "outer" — where inner was *defined*

    inner()

outer()   # prints "outer", not "global"

4.2 Dynamic Scope

In dynamic scoping, the scope of a name is determined by the call stack at runtime — specifically, by where the function is called from, not where it was defined. Dynamic scope was common in early Lisps. Most modern languages avoid it because it makes programs hard to reason about statically.

x = "global"

define show():
    print(x)         # under dynamic scope, x resolves to the
                     # *caller's* x, not the definition site's x

define caller():
    x = "caller's x"
    show()           # dynamic scope: prints "caller's x"
                     # lexical scope: prints "global"

4.3 Closures

A closure is a function that captures bindings from its enclosing lexical scope and carries them with it, even after the enclosing scope has returned. Closures are a direct consequence of lexical scoping combined with first-class functions. They are fundamental to functional programming and are heavily used in JavaScript, Python, and Haskell.

function makeCounter(start) {
    let count = start;          // captured by the closure

    return function increment() {
        count += 1;             // reads and writes the captured `count`
        return count;
    };
}

const counter = makeCounter(0);
console.log(counter());   // 1
console.log(counter());   // 2  — `count` persists between calls
console.log(counter());   // 3

After makeCounter returns, its local variable count would normally be gone — but because increment closed over it, the binding lives on as long as counter exists.

Useful Videos

Watch on YouTube

Watch on YouTube

Watch on YouTube

Watch on YouTube

Section 5: Functions and Higher-Order Programming

In most programming languages, functions are the primary unit of abstraction. PoPL is particularly interested in how functions are defined, passed around, and called. Two concepts are central: first-class functions (functions as values) and parameter passing strategies (how arguments are evaluated and passed to functions).

5.1 Parameter Passing Strategies

When a function is called, how are the arguments evaluated and passed? The three most important strategies are:

• 1Call by value — the argument expression is evaluated before the call; the function receives a copy of the value. Changes to the parameter do not affect the caller's variable. Used by C, Python (for immutable types), Java.
• 2Call by reference — the function receives a reference (alias) to the caller's variable. Mutations inside the function affect the caller. C achieves this explicitly with pointers.
• 3Call by name / call by need — the argument expression is not evaluated until it is actually used inside the function. Haskell uses call by need (lazy evaluation), which memoises the result after first evaluation.

// Call by value: caller's x is unchanged
void double_val(int x) {
    x = x * 2;
}

// Call by reference (via pointer): caller's x is mutated
void double_ref(int* x) {
    *x = *x * 2;
}

int main() {
    int a = 5;
    double_val(a);     // a is still 5
    double_ref(&a);    // a is now 10
}

5.2 First-Class and Higher-Order Functions

Functions are first-class when they can be stored in variables, passed as arguments, and returned from other functions — just like any other value. A higher-order function (HOF) is a function that takes a function as an argument or returns one. The three canonical HOFs are map, filter, and fold (reduce).

from functools import reduce

numbers = [1, 2, 3, 4, 5, 6]

# map: apply a function to every element
squares   = list(map(lambda x: x ** 2, numbers))     # [1, 4, 9, 16, 25, 36]

# filter: keep elements satisfying a predicate
evens     = list(filter(lambda x: x % 2 == 0, numbers))  # [2, 4, 6]

# reduce: fold the list into a single value
total     = reduce(lambda acc, x: acc + x, numbers, 0)   # 21

numbers = [1..6]

squares = map (^2) numbers           -- [1, 4, 9, 16, 25, 36]
evens   = filter even numbers        -- [2, 4, 6]
total   = foldr (+) 0 numbers        -- 21

-- Composing functions with (.)
squareThenSum = foldr (+) 0 . map (^2)
-- squareThenSum [1..6] => 91

5.3 Currying and Partial Application

Currying is the transformation of a function that takes multiple arguments into a chain of functions each taking a single argument. Named after mathematician Haskell Curry, it is the default in Haskell — every function technically takes exactly one argument. Partial application means supplying fewer arguments than a function expects, producing a new function awaiting the rest.

add :: Int -> Int -> Int    -- a function returning a function
add x y = x + y

addFive :: Int -> Int
addFive = add 5             -- partial application: fix the first argument

-- addFive 3 => 8, addFive 10 => 15

Useful Videos

Watch on YouTube

Watch on YouTube

Watch on YouTube

Watch on YouTube

Section 6: Memory Management Strategies

We covered the basics of stack and heap memory in Module 1, including manual allocation with malloc and free in C. This section focuses on the higher-level strategies that different languages use to manage memory automatically — and the trade-offs each approach involves.

6.1 Manual Memory Management

C and C++ give the programmer direct control over allocation (malloc/new) and deallocation (free/delete). This offers maximum performance and predictability, but puts the burden of correctness entirely on the programmer. Common errors include memory leaks (forgetting to free), use-after-free (accessing freed memory), and double-free (freeing twice).

6.2 Garbage Collection (Tracing GC)

Most managed languages — Python, Java, Go, JavaScript — use a garbage collector that automatically reclaims memory that is no longer reachable. The most common approach is tracing garbage collection: the GC periodically identifies all reachable objects by tracing references from a set of roots (global variables, stack variables), then reclaims everything not reached.

Modern GCs use generational collection — splitting the heap into generations based on object age, since most objects die young. Short-lived objects are collected cheaply from the young generation; long-lived objects are promoted to older generations collected less frequently.

def create_garbage():
    data = [i ** 2 for i in range(1_000_000)]  # large allocation
    return None                                  # data goes out of scope; GC reclaims it

create_garbage()   # no manual free needed
# Python's GC handles deallocation automatically

6.3 Reference Counting

Reference counting is an alternative to tracing GC where each object tracks how many references point to it. When the count reaches zero, the object is immediately freed. Python uses reference counting as its primary mechanism (supplemented by a cyclic GC to handle reference cycles). Swift and Rust's Rc<T>/Arc<T> also use reference counting.

The main drawback of pure reference counting is that cycles can prevent objects from ever being freed — if object A holds a reference to B and B holds a reference to A, their counts never reach zero even if nothing else refers to them.

import sys

x = []
print(sys.getrefcount(x))   # 2 (x itself + the argument to getrefcount)

y = x                        # another reference to the same list
print(sys.getrefcount(x))   # 3

del y                        # remove one reference
print(sys.getrefcount(x))   # 2 again — object not freed yet

del x                        # count reaches 0 (minus the getrefcount arg):
                             # list is immediately freed

6.4 Ownership and Borrowing (Rust)

Rust takes a different approach entirely: no garbage collector, no reference counting by default, and no manual free. Instead, the compiler enforces an ownership system at compile time. Every value has exactly one owner; when the owner goes out of scope, the value is freed. References (borrows) are tracked by the borrow checker, which prevents use-after-free and data races statically. This gives C-level performance with memory safety guaranteed at compile time.

Useful Videos

Watch on YouTube

Watch on YouTube

Watch on YouTube

Watch on YouTube