# CSCI 599: An Introduction to Programming Languages

## Fall 2020

### Logistics

 Classes: Tuesdays and Thursdays, 4–5:50pm · https://usc.zoom.us/j/98960729161 Scratchpad: Click here Piazza: https://piazza.com/usc/fall2020/csci599/home Instructor: Mukund Raghothaman (raghotha@usc.edu) Office hours: Mondays, 4–5:50pm, or by appointment · https://usc.zoom.us/j/95662027167

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

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 27: You can access an Ocaml language cheatsheet here.
• Aug 25: First class! See you at 4pm! We will meet using the Zoom link above.
• Aug 10: Welcome to CSCI 599! The course website is now live!

### Schedule

#### Unit 1: Functional Programming in Ocaml

 Aug 25, 27 Course introduction Overview, motivation and logistics Elementary computations using the REPL and a tour of the programming environment Aug 25: [Recording], [Slides], [Class notes] Aug 27: [Recording], [Handwritten Notes], [Text Editor Notes] Reading: RWO (Prologue, Guided Tour, and section on Variables in the chapter titled Variables and Functions) [Cheatsheet] Sep 01, 03 An introduction to types Structuring data with pairs, tuples, variants and records Pattern matching Recursive definitions and algebraic data types Sep 1: [Recording], [Text Editor Notes] Sep 3: [Recording], [Notes], [Text Editor Notes], [Test program] Sep 08, 10 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 8: [Recording], [Text Editor Notes], [L5-test.cpp] Sep 10: [Recording], [Notes], [L6-test.cpp] Homework 1 due on September 11 Sep 15, 17 Processing recursive data Processing lists with map and fold Mutable state Sep 15: [Recording], [Notes], [Text Editor Notes] Sep 17: [Recording], [Notes], [Text Editor Notes], [L8-test.ml], [L8-test.cpp] Sep 22, 24 Assorted topics Mutable state, contd. Polymorphism, modules, and programming in the large Sep 22: [Recording], [Notes] Sep 24: [Recording], [Notes], [Text Editor Notes], [L10hw1.ml], [L10hw2.ml] Homework 2 due on Oct 02

#### Unit 2: Implementing a Language Interpreter

 Sep 29, Oct 01 Understanding syntax Describing syntax with regular expressions and context-free grammars Lexical analysis with finite state automata Sep 29: [Recording], [Text Editor Notes], [Notes] Oct 1: [Recording], [Notes], [mylexer.mll] Oct 06, 08 Syntax, contd. The CYK algorithm for parsing context free grammars Bottom-up parsing using LALR grammars Oct 6: [Recording], [expr.ml], [ourlexer.mll], [ourparser.mly] Oct 8: [Recording], [Notes], [Text Editor Notes], [l14parser.mly] Oct 13, 15 Syntax, contd. 2: Parsing algorithms for regular expressions and context-free grammars Oct 13: [Recording], [Notes], [Text Editor Notes] Oct 15: [Recording], [Notes] Oct 20, 22 An elementary understanding of types and the runtime Oct 20: [Recording], [Notes] Oct 22: [Recording], [Notes], [m1.c], [m2.c] Midterm due on October 26

#### Unit 3: Programming with Relations

 Oct 27, 29 Spreadsheets The computational model: Cells, values, formulas and dependence graphs Pivot tables, array formulas and lookups Turing-completeness of spreadsheets as a programming medium Oct 27: [Recording], [Notes], [Text Editor Notes], [L19-Test.xlsx] Oct 29: [Recording], [Notes], [L20-Test.xlsx], [Chinook_Sqlite.sqlite] Nov 03, 05 The relational data model Relational algebra: SPJ queries and set operations Non-recursive queries with SQL Nov 03: [Recording], [Notes], [Chinook Database] Nov 05: [Recording], [Notes] Nov 10, 12 An introduction to recursive query languages Querying graph data with Cypher Rule-based queries using Datalog Bottom-up query evaluation Nov 10: [Recording], [Notes], [Slides], [Paper describing Cypher], [Early paper on graph query languages], [Neo4j sandbox] Nov 12: [Recording], [Notes], [Slides], [cousins.dl], [p.facts], [path.dl] Nov 17, 19 More on recursive query languages Logic programming with Prolog Top-down query evaluation by backtracking Nov 17: [Recording], [Notes], [scc.dl], [samegen.dl], [dfa.dl], [paradox.dl] Nov 19: [Recording], [Notes], [shakespeare.pl], [gcd.pl], [animals.dl] Nov 24 Conclusion and review What was this course all about? Reflections on the future of programming Nov 24: [Recording], [Notes] Homework 4 due on Nov 27 Final due on Dec 4

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: Fri Dec 24 05:02:36 AM PST 2021