CSCI 431 · Principles of Functional Programming

Course Description

This course will introduce you to a range of advanced programming paradigms. We will assume an elementary knowledge of programming, such as that covered in CSCI 103 and CSCI 104, and study powerful ways of structuring code with higher-order functions, of providing strong guarantees with static type systems, and ways to liberate the programmer from low-level resource management. By blurring the distinction between programs and data, and widening the gap between a program and its execution, our goal is to blow your mind about what it means to program a machine, and to reinforce your developing sense of computational thinking. The first half of the course can alternatively be seen as an introduction to functional programming with Ocaml, while the second half of the course can be regarded as an introduction to logic programming.

Note: The syllabus and schedule listed on this webpage are tentative, and may be updated as the course progresses. Please check back regularly!

Schedule

Unit 1: Functional Programming in Ocaml

Aug 26, 28	Course introduction Motivation, overview, and logistics Elementary computations using the REPL and a tour of the programming environment Reading: Radiolab on Linguistic Relativity: Why Isn't the Sky Blue? John Backus's Turing Award Lecture: Can Programming be Liberated from the von Neumann Style?. CS3110, Chapters 1 and 2 RWO, Chapter 1 [Cheatsheet] Aug 26: [Slides], [Recording] Aug 28: [Recording]
Sep 2, 4	An introduction to types Structuring data with pairs, tuples, variants and records Pattern matching Recursive definitions and algebraic data types Reading: [Yaron Minsky's talk on types] Reading: CS3110, Chapter 3 RWO Chapters 5, 6: Records and Variants [Tail Call Optimization: The Musical]
Sep 9, 11	Abstracting computations with functions Recursive definitions Higher-order functions: Functions as arguments, as return values, and those of the anonymous kind; arrow types Execution model: Evaluation order and scoping rules Reading: RWO Chapter 2: Variables and Types
Sep 16, 18	Processing recursive data Processing lists with map and fold Mutable state Reading: RWO Chapter 3: Lists and Patterns
Sep 23, 25	Assorted topics Mutable state, contd. Polymorphism, modules, and programming in the large Reading: RWO Chapter 8: Imperative Programming Reading: RWO Chapter 4 and 9: Modules and Functors

Unit 2: Implementing a Language Interpreter

Sep 30, Oct 2	Understanding syntax Describing syntax with regular expressions and context-free grammars Lexical analysis with finite state automata Reading: RWO Chapter 19: Parsing Data with Ocamllex and Menhir
Oct 7, 14, 16	Syntax, contd. Understanding the lexical analyzer The CYK algorithm for parsing context free grammars Oct 9: Fall recess, no class
Oct 21, 23	*Syntax, contd. 2: Parsing algorithms for regular expressions and context-free grammars*
Oct 28, 30	An elementary understanding of types and the runtime

Unit 3: Programming with Relations

Nov 4, 6	Spreadsheets The computational model: Cells, values, formulas and dependence graphs Pivot tables, array formulas and lookups Turing-completeness of spreadsheets as a programming medium
Nov 7, 12	The relational data model Relational algebra: SPJ queries and set operations Non-recursive queries with SQL Reading: [SQL Murder Mystery]
Nov 13, 18	An introduction to recursive query languages Nov 11: Veterans Day, no class Querying graph data with Cypher Rule-based queries using Datalog Bottom-up query evaluation
Nov 20, 25, Dec 2	More on recursive query languages The problem of negation Logic programming with Prolog Top-down query evaluation by backtracking Nov 27: Happy Thanksgiving! No class
Dec 4	Course conclusion and review What was this course all about? Reflections on the future of programming
Dec 11	Final exam (4:30pm–6:30pm) Good luck!

Readings

The first half of the course will follow the Real World Ocaml textbook. This is the only required textbook for this course. We will assign additional supplementary readings as appropriate.

Yaron Minsky, Anil Madhavapeddy, and Jason Hickey. Real World Ocaml. 2nd edition. O'Reilly, 2021. [Link]
Michael Clarkson. Ocaml Programming: Correct + Efficient + Beautiful. 2022. Course notes from CS3110, a somewhat similar course offered at Cornell. [Link]
Harold Abelson, Gerald Jay Sussman, and Julie Sussman. Structure and Interpretation of Computer Programs. 2nd edition. The MIT Press, 1996. [Link]
Leon Stirling and Ehud Shapiro. The Art of Prolog. 2nd edition. The MIT Press, 1994. An open-access copy may be freely downloaded from [here].

Development Environment

Ocaml: Please follow the instructions described here.
Datalog: Obtain Souffle from here, and follow the build instructions described here.
Prolog: Install SWI Prolog either from your operating system package manager (sudo dnf install pl, brew install swi-prolog, sudo apt install swi-prolog, or similar), or directly from its website.

Classes:	Tuesdays and Thursdays, 4:00–5:50pm · GFS 223 · [Zoom]
Piazza:	https://piazza.com/usc/fall2025/csci431
Instructor:	Mukund Raghothaman (raghotha@usc.edu)
Office hours:	Thursdays, 1:30–3:30pm, or by appointment

CSCI 431: Principles of Functional Programming

Fall 2025

Logistics