CSCI 499: Advanced Programming Paradigms

Fall 2021


Classes: Tuesdays and Thursdays, 2–3:50pm · KAP 166 ·
Scratchpad: Click here
Instructor: Mukund Raghothaman (
Office hours: Fridays, 1–2:50pm, or by appointment ·

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.   [Syllabus], [Registration Calendar]

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



Unit 1: Functional Programming in Ocaml

Aug 24, 26 Course introduction
Aug 31, Sep 2 An introduction to types
Sep 7, 9 Abstracting computations with functions
Sep 14, 16 Processing recursive data
Sep 21, 23 Assorted topics
  • Mutable state, contd.
  • Polymorphism, modules, and programming in the large
  • Sep 21: [Recording], [Notes]
  • Sep 23: [Recording], [Notes]
  • Reading: RWO Chapter 8: Imperative Programming
  • Reading: RWO Chapter 4 and 9: Modules and Functors

Unit 2: Implementing a Language Interpreter

Sep 28, 30 Understanding syntax
  • Describing syntax with regular expressions and context-free grammars
  • Lexical analysis with finite state automata
  • Sep 28: [Recording], [Notes]
  • Sep 30: [Recording], [Notes], [L12.mll]
  • Reading: RWO Chapter 18: Parsing Data with Ocaml
Oct 5, 7 Syntax, contd.
Oct 12 Midterm released, Disambiguating grammars, understanding the lexical analyzer
Oct 14 Fall recess, no class
    Oct 19, 21 Syntax, contd. 2: Parsing algorithms for regular expressions and context-free grammars
    Oct 26, 28 An elementary understanding of types and the runtime

    Unit 3: Programming with Relations

    Nov 2, 4 Spreadsheets
    Nov 9, 11 The relational data model
    Nov 16, 18 An introduction to recursive query languages
    Nov 23, 30 More on recursive query languages
    Nov 25 Thanksgiving break, no class
      Dec 2 Conclusion and review
      • What was this course all about?
      • Reflections on the future of programming
      Dec 9 Final exam (2–4pm)


      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.

      1. Yaron Minsky, Anil Madhavapeddy, and Jason Hickey. Real World Ocaml. 2nd edition. O'Reilly, 2020.
        We will be using drafts of the second edition of the book which is currently in preparation and freely available at here.
      2. Harold Abelson, Gerald Jay Sussman, and Julie Sussman. Structure and Interpretation of Computer Programs. 2nd edition. The MIT Press, 1996.
        The book is freely available here.
      3. Leon Stirling and Ehud Shapiro. The Art of Prolog. 2nd edition. The MIT Press, 1994.
        The book is freely available here.

      Development Environment

      1. Ocaml: Please follow the instructions described here.
      2. Datalog: Obtain Souffle from here, and follow the build instructions described here.
      3. 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.


      1. Homework assignments: 4×15% = 60%
      2. Midterm exam: 20%
      3. Final exam: 20%

      On Collaboration

      You are welcome to discuss homework assignments with a partner. However, each of you will turn in your submissions separately. You will each be responsible for independently writing and physically typing the solutions in your submission. Please identify your discussion partner, if any, in your submission.


      From Dornsife's academic conduct policy: Plagiarism—presenting someone else's ideas as your own, either verbatim or recast in your own words—is a serious academic offense with serious consequences. Please familiarize yourself with the discussion of plagiarism in SCampus in Part B, Section 11, "Behavior Violating University Standards." Other forms of academic dishonesty are equally unacceptable. See additional information in SCampus and university policies on scientific misconduct, here.

      Discrimination, sexual assault, intimate partner violence, stalking, and harassment are prohibited by the university. You are encouraged to report all incidents to the Office of Equity and Diversity / Title IX Office here, and / or to the Department of Public Safety. This is important for the health and safety of the whole USC community. Faculty and staff must report any information regarding an incident to the Title IX Coordinator who will provide outreach and information to the affected party. The sexual assault resource center webpage fully describes reporting options. Relationship and Sexual Violence Services webpage provides 24/7 confidential support.

      Note on collaborative work: For collaborative projects, students are expected to have equal distribution of work. If there is any perceived imbalance in the collaborative project, the student should bring this to the attention of the instructor or the teaching assistant.

      Assistance with writing and disabilities: Several USC's schools provide support for students who need help with scholarly writing. Check with your advisor or program staff to find out more. Students whose primary language is not English should check with the American Language Institute which sponsors courses and workshops specifically for international graduate students. The Office of Disability Services and Programs provides certification for students with disabilities and helps arrange the relevant accommodations. If an officially declared emergency makes travel to campus infeasible, USC Emergency Information will provide safety and other updates, including ways in which instruction will be continued by means of Blackboard, teleconferencing, and other technology.

      Last updated: Thu Dec 2 12:58:54 PM PST 2021