## Fall 2021

### Logistics

 Classes: Tuesdays and Thursdays, 2–3:50pm · KAP 166 · https://usc.zoom.us/j/94314036860 Scratchpad: Click here Piazza: https://piazza.com/usc/fall2021/csci499 Instructor: Mukund Raghothaman (raghotha@usc.edu) Office hours: Fridays, 1–2:50pm, or by appointment · https://usc.zoom.us/j/93270102560

### 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!

### Annonucements

• Aug 20: Welcome to CSCI 499! The course website is now live!

### Schedule

#### Unit 1: Functional Programming in Ocaml

 Aug 24, 26 Course introduction Overview, motivation and logistics Elementary computations using the REPL and a tour of the programming environment Aug 24: [Recording], [Slides], [L01.ml] Aug 26: [Recording], [Notes] Reading: Richard Bird. Functional Pearl: A Program to Solve Sudoku. JFP 2006. [Link] [Cheatsheet] Aug 31, Sep 2 An introduction to types Structuring data with pairs, tuples, variants and records Pattern matching Recursive definitions and algebraic data types Aug 31: [Recording], [Notes] Sep 2: [Recording], [Notes], [L04-ds.cpp] Reading: [Yaron Minsky's talk on types] Reading: RWO Chapters 5, 6: Records and Variants Sep 7, 9 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 Sep 7: [Recording]. [Notes], [L05-ds.c], [L05-ss.c], [L05-even.ml] Sep 9: [Recording], [Notes], [L06.java] Reading: RWO Chapter 2: Variables and Types Sep 14, 16 Processing recursive data Processing lists with map and fold Mutable state Sep 14: [Recording], [Notes] Sep 16: [Recording], [Notes], [L08.cpp] Reading: RWO Chapter 3: Lists and Patterns 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. The CYK algorithm for parsing context free grammars Bottom-up parsing using LALR grammars Oct 5: [Recording], [Notes], [L13-expr.ml], [L13-lexer.mll], [L13-parser.mly] Oct 7: [Recording], [Notes], [L14-lexer.mll], [L13-parser.mly] Oct 12 Midterm released, Disambiguating grammars, understanding the lexical analyzer [Recording], [Notes], [L15-expr.ml], [L15-lexer.mll], [L15-parser.mly] Oct 14 Fall recess, no class Oct 19, 21 Syntax, contd. 2: Parsing algorithms for regular expressions and context-free grammars Oct 19: [Recording], [Notes], [L16-regex.ml] Oct 21: [Recording], [Notes] Oct 26, 28 An elementary understanding of types and the runtime Oct 26: [Recording], [Notes] Oct 28: [Recording], [Notes]

#### Unit 3: Programming with Relations

 Nov 2, 4 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 2: [Recording], [Notes], [L20.c] Nov 4: [Recording], [Notes], [L21.ods] Nov 9, 11 The relational data model Relational algebra: SPJ queries and set operations Non-recursive queries with SQL Nov 9: [Recording], [Notes], [Chinook_Sqlite.sqlite] Nov 11: [Recording], [Notes] Nov 16, 18 An introduction to recursive query languages Querying graph data with Cypher Rule-based queries using Datalog Bottom-up query evaluation Nov 16: [Recording], [Notes] Nov 18: [Recording], [Notes] Nov 23, 30 More on recursive query languages Logic programming with Prolog Top-down query evaluation by backtracking Nov 23: [Recording], [Notes], [cousins.dl], [parent.facts], [path.dl] Nov 30: [Recording], [Notes], [scc.dl], [sgen.dl], [paradox.dl], [nopath.dl] 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

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.

### Policies

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