CS2 — Extras

This annex collects material we cut from the main CS2 lesson because it isn't strictly required for writing working C. None of it is needed to make programs compile and do what you want. All of it makes the choices in C make more sense.

Six pieces:

How we got to function calls. A century-long story that ends at the stack frame.
Enter: Edsger Dijkstra. The man, the 1960 paper, the six pages that underlie every language on Earth.
What a stack frame actually is. The thing your function calls live inside, in mechanical detail.
Software architecture 101: boundaries and crossings. The general engineering concept of which "a C function" is one concrete instance.
Virtual vs physical memory. What's really on the other end of a pointer.
Where the most famous C bugs come from. The security-industry origin story of C strings — Morris Worm, Heartbleed, and why languages that came after C carry their string lengths with them.
Skim it. Dive into a section. Save it for a rainy day. None of it will be on a test. All of it is good to know.

How we got to function calls

It took us only about a hundred years of figuring out how to call functions. To see why something as innocent as f(x) is a small miracle, we have to drop one floor lower in the abstraction tower and look at what computing was like before "function" was even a word.

Quick recap from CS1, because the next few paragraphs lean on it. At the bottom of the abstraction tower sits machine code: the raw numbers the CPU's fetch-decode-execute loop actually eats. One floor up is assembly language — those exact same instructions, but written with short, human-readable names like LDA (load), ADD, STA (store), JMP (jump) instead of bare numbers. You already wrote assembly by hand in CS1, in the Little Man Computer simulator (LDA, ADD, STA, OUT, HLT). That was the real thing, just slowed down to human speed.

If a high-level language like C is writing a recipe in prose ("chop the onions, cook until soft"), then assembly is dictating that recipe to someone with no memory and no judgment, one micro-step at a time: pick up knife. move hand to onion. close fingers. lift. move hand to cutting board. Every assembly instruction is dumb, atomic, obvious in isolation — no if blocks, no for loops, just compare and jump. To do anything useful, you must spell out every single step.

In assembly language, the closest things to "reusable named code" — the ancestors of functions — came in two flavours: macros and procedures. Neither of them is what we'd call a function today, but understanding them is key to the motivation behind functions.

A macro, in an assembler, is basically a copy-paste shortcut. You define a chunk of code with a name, and the assembler literally substitutes the chunk in wherever you "call" it. In modern C terms, a macro is roughly what #define does. There is no real "call"; the code is just duplicated.

A procedure is closer to what we'd call a function: it lives in one place in memory, and when you "call" it, the CPU jumps to that place, runs it, and jumps back.

So far so good. But here is the catch, and it is important: in classic assembly procedures, every variable is effectively global. When the CPU calls a procedure, it jumps to that code but still has full access to all the variables, memory and registers of the rest of the program. This can backfire. A small example (don't sweat the syntax — just feel what's wrong):

mov rbx, 100        ; rbx = my loop counter; sets rbx = 100
 
loop_start:
    call math_lib_sqrt  ; somebody else's library; I have NO IDEA what registers
                        ; it uses — if it alters rbx inside, my counter is destroyed
 
    dec rbx             ; (decrements rbx). I expect rbx to go 100, 99, 98...
    jnz loop_start      ; ...but my loop now behaves completely randomly

The architectural name for this behaviour is a weak boundary. The procedure isn't really isolated from the rest of the program — its locals leak out, and the outside world leaks in. As long as the only person writing code is you, and your program is small, weak boundaries are manageable. The moment you have other people's code in your program (a math library, a sensor driver, anything you didn't personally write), weak boundaries become a point of failure. You'd have to read every line of every dependency to know which registers and variables are safe to use, and when. Multiply by a hundred programmers on a real project, all of whom call their loop counter i, and watch your whole codebase become unlit TNT. Change one variable by mistake and it blows up. Add concurrency on top, and it gets way, way worse.

Let's see a real-world example where the lack of isolation broke down at scale: the original IBM PC (1981) ran on the Intel 8088, which had only what is now called real mode — and real mode has, drumroll, zero memory protection. Any program could read or write any address in the machine's 1 MB of memory. Including the operating system's own data, another program's data, or — why not — even the BIOS. DOS (the dominant OS of the era) sat on top of this with no isolation between programs and itself. A bug in your spreadsheet could silently corrupt the file system. A typo in a pointer could crash the entire computer. No virtual memory, no separate address space per app, no MMU (Memory Management Unit) between you and the bare metal — just one big shared 1 MB sandbox where every program hoped the others wouldn't scribble on its code. Intel introduced protected mode with the 80286 in 1982 to fix this, but for compatibility reasons DOS spent the next decade and a half mostly not using it, and home users learned to live with the consequences. Weak boundaries, planet scale.

This was the world that needed fixing. The problem was clear enough by the late 1950s — programs needed real isolation between function calls — but how to actually implement that on a real CPU was an unsolved engineering problem. The fix took until 1960, and it came from one short paper.

The idea that fixes this — giving each function call its own private scratch space that gets created on entry and thrown away on exit — dates back to Alan Turing, in his 1945 report on the proposed ACE computer, where he described "burying" and later "unburying" return addresses to handle nested subroutine calls — a stack in everything but name. But the idea then sat on a shelf for nearly fifteen years. Through the late 1950s, computers handled subroutines extremely inefficiently: every subroutine in your program got its own permanent, fixed block of memory reserved for its variables. Thirty subroutines? Thirty reserved blocks, all eating up memory whether the subroutine was running or not. And there was one more big issue with this: functions could not call themselves.

The act of a function calling itself is called recursion. Recursive procedures are a science of their own, but more importantly they were already an incredibly powerful mathematical tool. By 1960, countless algorithms had been designed as recursions — on paper. And yet we had no way to execute them.

Enter: Edsger Dijkstra

The fix arrives in 1960, in a six-page paper by Edsger Dijkstra — a young, obsessively rigorous, slightly terrifying Dutch programmer whose name you should learn because it returns over and over again in this field. The paper is called "Recursive Programming", and its key idea is exactly what you are about to see: don't give each subroutine its own fixed memory area. Instead, share one big dynamic area — call it the stack — and have each call claim a fresh chunk on entry (push a new frame) and release it on exit (pop the frame). Three things fall out of this:

One: every active call gets its own private workspace, so variables don't collide.
Two: only currently-running routines consume memory, so the same memory gets reused for whichever call is live right now.
Three: a function calling itself just produces a second frame, independent of the first one, which means recursion becomes possible by construction.
That single insight is the entire foundation of how every modern programming language handles function calls. Six. Pages.

What a stack frame actually is

When your program starts running, the operating system hands it a chunk of memory called the stack. (There are other regions too — the heap, the data segment, and so on — but for this annex we only care about the stack.) Think of the stack as a tall pile of trays in a cafeteria: you can only put a new tray on the top, and you can only take a tray off the top. Last in, first out (LIFO).

Every time you call a function, a new tray slides onto the top of the stack. That tray is the function's stack frame, and it contains:

The function's parameters (the inputs it was called with — copies of them).
The function's local variables (everything you declare inside the function body).
A bit of bookkeeping (e.g. where to jump back to when the function returns).
When the function returns, the tray gets thrown out — its locals vanish, its memory is reclaimed. The program continues from wherever it called the function from.

So when main calls a function average5(r1, r2, r3, r4, r5):

A new stack frame slides on for average5.
The frame is populated with average5's own r1, r2, r3, r4, r5 — copies of the values from main's r1, r2, r3, r4, r5. Same names, different mailboxes. This is the whole point.
average5 does its work, computing (r1 + r2 + r3 + r4 + r5) / 5.0 inside its frame, operating on its own copies.
The result, a single double, is handed back through return.
The frame for average5 is thrown away — its r1, r2, r3, r4, r5 no longer exist.
main's frame is back on top; its r1, r2, r3, r4, r5 are still sitting there, untouched.

This is exactly what makes the boundary strong. average5 literally cannot see main's r1...r5 — it has its own r1...r5 instead, holding copies of those values at the moment of the call. And main literally cannot see average5's copies — they live in a frame that is later destroyed.

All of that mechanism — the frame pushed on entry, the parameters copied across the boundary, the frame thrown away on exit, the caller's variables sitting safe and untouched in their own frame — is what Dijkstra invented in those six pages in 1960. And one small linguistic delight to round it off: the word "stack" itself is also Dijkstra's coinage. He was working in Dutch, reached for stapel (a pile, a heap-of-things), and translated it as "stack" when writing in English; within a few years the term had taken over the global vocabulary of computing. Every language on Earth now uses the same per-call stack frame Dijkstra pioneered — including C, and therefore every line of code you have ever written.

A bonus, since we're here. Besides the stack, the whole modern way a program is organised — the if/else statements, the while loops, the fact that we don't have random jumps across the program — falls under a concept called structured programming, a movement that Dijkstra led and named. Read his short paper "Go To Statement Considered Harmful" — it's less than two pages, no mathematics, just sentences and reasoning, and it changed programming forever.

Software architecture 101: boundaries and crossings

An architectural boundary in a program is just a line you've drawn that says "stuff on this side is separate from stuff on that side." Boundaries come in two flavours:

A weak boundary is one you can step over without anyone checking. Locals leak. Globals are shared. Mistakes in one zone corrupt the other zone. Assembly procedures are weak boundaries.
A strong boundary is one that's enforced. Stuff on the inside cannot be seen or touched from the outside, and vice versa — except through a deliberately-designed gate. The gate is the only crossing, and it checks everything that passes through it.

A C function (or, more precisely, anything that has its own stack frame) is a strong boundary. Locals stay local. The caller can't accidentally read the function's variables; the function can't accidentally write the caller's. The only legal crossing is the call itself — arguments going in, a return value coming out.

And that crossing itself can come in two flavours too:

A tight boundary crossing is controlled and explicit — passage through a defined gate, with rules about what passes and how. Calling a C function is one: arguments declared by type, values copied across, scoped frames maintained.
A weak boundary crossing is uncontrolled — you step across without any check, accidentally reading or writing things on the other side. Classic assembly procedures gave you exactly this: no check, no record, no protection.
So a C function call is a tight crossing of a strong boundary — and that double-tightness is what makes functions safe to compose at scale.

The customs analogy. Picture a function as a sovereign country with its own laws inside. Values pass through customs (call) and get a return stamp (return); the inside is opaque from the outside. That's a tight boundary crossing. The opposite — wandering across an unguarded line in the woods, no checks, no record — is the weak boundary crossing that classic assembly gave you, and it's how things break.

Virtual vs physical memory

A small honest moment about pointers and memory. Throughout the main lesson we've been saying things like "a pointer holds the address of a variable in memory" and printing addresses with %p. There's a quiet lie hiding in that wording, and it deserves a section.

The address p prints is not where your variable sits on the RAM chip on your motherboard. It's a virtual address (sometimes called a logical address), and there is one more layer of indirection sitting between it and physical RAM — managed by your operating system, with help from a hardware unit on every modern CPU called the MMU (memory management unit). Every running program gets its own private imagined address space. When your code does *p and reaches for address 0x7ffd1234, the MMU intercepts that access, looks up "where does this program's 0x7ffd1234 actually live in physical RAM right now?", and routes the read or write to the real chip accordingly. Different programs can all use "the same" virtual addresses without colliding, because each program has its own translation table. You have been programming through two layers of indirection this whole lesson — the pointer's *p that you control, and the OS's silent translation underneath it that you don't even see. You just didn't know the second one was there.

Take "direct memory access" with a grain of salt. The address you printf with %p is meaningful inside your program and largely useless outside it; in fact, the OS deliberately randomises addresses across runs for security (look up ASLR — Address Space Layout Randomization — if you're curious). This whole layer is also why *NULL crashes cleanly on modern systems: the OS marks virtual address 0 as "no mapping exists," the MMU traps any access to it, and the kernel kills your program with a segfault. Contrast the IBM PC sidebar from the history section above — no MMU, no virtual addresses, addresses were physical and *NULL could silently corrupt anything (often the interrupt vector table, leading to the famous "Abort, Retry, Fail?" prompt that haunted DOS users). For 99% of the C you'll write on a desktop or server, you can think of pointers as "real direct memory access" and be fine. For the other 1% — debugging weird crashes, writing kernel code, doing serious embedded work — the distinction is everything. On the AirBox microcontroller you'll be programming later in this bootcamp, in fact, there is no MMU, and the address you see in %p really is the physical RAM location. The grown-up rule: addresses are virtual on big systems, physical on tiny ones, and a good engineer knows which world they're in.

Where the most famous C bugs come from

C strings, as you saw in the main lesson, don't carry a length field — the length is implicit in where the null terminator sits. Almost every catastrophic memory-safety bug in the history of computing — buffer overflows, the Morris Worm, Heartbleed, Code Red, countless CVEs — comes from that one design decision. Two patterns dominate:

Buffer overflow on write. A function copies a string into a fixed-size buffer without checking the source length. The source is longer than the buffer, so the function happily writes past the end of the buffer, overwriting whatever's next in memory, often function return addresses, leading to arbitrary code execution.
Read past the end. A function returns a buffer along with a length, and the caller trusts the length without checking. If the length is wrong (missing null terminator, off-by-one, attacker-controlled), the caller reads past the end of the buffer into adjacent memory which often contains sensitive data the caller wasn't supposed to see.
Two named examples worth knowing:

The Morris Worm (1988). The first internet worm. It used a buffer overflow in gets(), a C function that reads a line of input into a buffer with NO bounds checking, to take over Unix machines across the early internet. gets was so dangerous it was officially removed from the C language in 2011, only about twenty-three years later.
Heartbleed (2014). A bug in OpenSSL where a server would return up to 64 KB of memory adjacent to a small buffer, because of a length field the attacker controlled. Leaked private keys, passwords, session tokens from millions of websites. Cost the industry an estimated billions to remediate.
Same root cause both times: a function reading past the end of an array because the size information lived somewhere other than the array itself. C doesn't enforce the boundary; you do, or you don't.

Languages designed after C (Rust, Go, Python, Java, Swift) all carry their length with the string. C doesn't. This is the single biggest reason most new systems software is being written in other languages like Rust and the new C++ today.