15312 Foundations: Of Programming Languages

Problem: Define a small language of Boolean expressions with and (short-circuiting) and or.

Solution Sketch:

Perhaps the most profound philosophical depth plumbed by the course is the Curry-Howard Correspondence. This is the moment where computer science collides with mathematical logic. 15312 foundations of programming languages

The correspondence states that there is a one-to-one mapping between computer programs and mathematical proofs.

When a student writes a function in 15-312 that takes an input of type $A$ and returns an output of type $B$, they are effectively proving the logical implication $A \implies B$. The act of writing a function that type-checks is the act of constructing a valid mathematical proof. Problem: Define a small language of Boolean expressions

This transforms the student's relationship with their code. The red squiggly lines in their editor are no longer syntax errors; they are holes in a logical argument. The course demands that students stop thinking of programming as "telling the computer what to do" and start thinking of it as "constructing a logical argument that the computer can verify."

Every language needs a form. The first foundation is syntax: the rules that determine which strings of characters are valid programs. Solution Sketch:

Imagine a sentence in English: “Colorless green ideas sleep furiously.” It’s grammatically correct but meaningless. Similarly, a program can be syntactically correct but nonsensical.

In the 1950s, Noam Chomsky’s work on formal grammars was adapted to computing. BNF (Backus-Naur Form) became the standard way to describe syntax. For example, a simple arithmetic expression:

<expr> ::= <expr> + <term> | <term>
<term> ::= <term> * <factor> | <factor>
<factor> ::= number | ( <expr> )

With BNF, we could now generate all valid programs and reject the invalid ones. Parsers—tools that check syntax—became the first gatekeepers of every programming language.

But syntax alone is just a shell. The real story begins with meaning.