The Birth of Programming Languages

Computation and Turing Machines · v1.4.1

2026-09-13 14:38:49

Where we are

Two abstractions, no hardware

The previous unit ended with Turing’s machine and Church’s calculus.

Neither built from anything physical.

This unit does two things

One machine, in detail.

Then four decades of languages, at speed.

Learning outcomes

  1. explain-von-neumann-architecture — Explain how EDVAC turned Turing’s abstract machine into a physical one.
  2. trace-language-paradigm-lineage — Trace the FORTRAN-to-C paradigm lineage.
  3. place-lisp-and-functional-lineage — Place Lisp and its functional lineage.
  4. place-oop-lineage — Place Kay’s OOP and its extension into C++.
  5. describe-industrial-era-languages — Describe what problem each 1990s language solved.
  6. explain-sql-as-dsl — Explain SQL as a domain-specific language.
  7. recognize-recurring-paradigms — Recognize the paradigms studied later in the course.

From theory to hardware

EDVAC, 1946

John von Neumann.

Vacuum tubes.

A physical implementation of the universal Turing machine.

The von Neumann architecture

CPU. Executes instructions.

Memory. Holds data and instructions.

Data bus. Connects them.

What else it established

Binary data encoding.

The first machine code instruction set.

The blueprint for nearly every processor since.

FORTRAN: the first high-level language

John Backus, IBM Research

John Backus.

Drafted FORTRAN in 1953.

First compiler: 1957.

1977 Turing Award, for practical high-level programming systems.

What FORTRAN proved

Compiled abstraction could be fast enough to matter.

Ancestor of BASIC, C, C++, Java, Python.

Lisp and the functional thread

John McCarthy, 1958

John McCarthy.

Second-oldest high-level language still in use.

Also invented garbage collection. Contributed to ALGOL, time-sharing.

What Lisp introduced

Dynamic memory allocation.

Dynamic typing.

Macros. Concurrency.

The line forward

Gerald Sussman.

Sussman and Steele, 1975 — Scheme.

An industrial-scale Lisp implementation.

Steele later invented Java, in 1995.

Forward again, to this course

Two modules from now: Clojure, a modern Lisp.

Studied in depth.

C and the systems thread

Brian Kernighan

Brian Kernighan.

University of Toronto, then Princeton PhD.

Contributed to inventing C, 1972.

Later co-authored a book on Go, 2015.

Where C sits

Continues FORTRAN’s imperative, compiled lineage.

Direct ancestor of C++. By influence, of Java.

Object-oriented programming and C++

Alan Kay, Xerox PARC

Alan Kay.

  1. Pioneered object-oriented programming.

Developed Smalltalk.

Software organized around objects, not functions and logic.

Bjarne Stroustrup

Bjarne Stroustrup.

Aarhus, then Cambridge PhD, 1979.

Invented C++ that same year.

OOP abstractions, with C’s systems performance.

Haskell and pure functional programming

Simon Peyton Jones

Simon Peyton Jones.

Co-invented Haskell, 1990.

Led the Glasgow Haskell Compiler.

Later, Engineering Fellow at Epic Games.

The functional thread’s other endpoint

Lisp: dynamically typed, permits side effects.

Haskell: statically typed, pure by default.

The industrial era

A burst of new languages

The 1990s. Not coincidence.

The web and cheap computing created problems older languages weren’t built for.

Guido van Rossum

Guido van Rossum.

Python, 1991.

Now the leading language for data science and machine learning.

Brendan Eich

Brendan Eich.

Netscape, 1995. Scheme-like programming, in the browser.

First called LiveScript.

Co-founded Mozilla, 1998.

Yukihiro Matsumoto

Yukihiro Matsumoto.

Ruby, December 1995.

Designed around programmer happiness.

Rasmus Lerdorf

Rasmus Lerdorf.

PHP, 1995.

Started as a personal tool for his own home page.

Grew into the first major web-centric language.

SQL as a domain-specific language

Donald Chamberlin, IBM Research

Donald Chamberlin.

Stanford PhD.

Co-invented SQL, 1974–2016.

The first widely successful DSL for relational databases.

Why the narrowness is a feature

A DSL gives up generality.

For being unusually good at one domain.

Fifty years, no general-purpose challenger.

The map you now have

Four decades of language design

Every language in this unit, on one axis.

The functional thread

Church’s calculus, carried forward. Haskell is the thread’s pure, statically typed endpoint.

The object-oriented thread

Objects and message passing, then the same abstractions at systems-level performance.

Where next

The Limits of Computation.

The boundary Gödel and Church located, given a precise definition: decision problems, decidability, and what a proof of undecidability requires.