Functional Programming in OCaml, CSCI 49201

General information

Mon, Wed, 3:20 - 5:25 pm. Hunter North 1516.
Office hours: after the class or by appointment.

Instructor: Alexey Nikolaev
Website: https://a-nikolaev.github.io/fp/
Syllabus: PDF
Email: a(my last name)@gradcenter.cuny.edu
Office: HN 1000C

Lecture notes

• Expressions. Functions. Recursion (Reading: 2.1 - 2.9).
• Lists. Pattern matching. Local name binding (Reading: 3.1 - 3.5, 2.13).
• Common built-in types. Printing. Semicolon. Tuples. Accumulators (Reading: 2.15, 3.15)
• Option type. Tail call optimization. Map, filter, iter (Reading: 3.21, 3.5, 4.1-4.4)
• Variant types. Reading a file. MiniMake (Reading: 3.12, 3.23, 3.24)
• Currying. Pipeline operator. Fold (Reading: 2.11, 4.13, 4.12, 2.12, 4.5-4.9)
• Records and modules (Reading: 3.14, 5.1-5.6)
• Recursive variant types. Binary search trees (Reading: 3.32, 3.31, 8.5)
• More binary trees. S-expressions. Examples with Opal and Cairo
• Module signatures. Functors. Map and Set (Reading: 5.5, 5.22-5.25)
• Monads. Memoization. Delayed computation. Sequences. Lambda calculus (Reading: 8.22 - 8.27)

Projects

Information about projects

Overview

This is a practical hands-on course on functional programming using OCaml. The goals of the course are: to help you learn the functional programming paradigm, and more broadly, to improve your ability to learn any new technology or programming language, which will make you a better programmer and computer scientist.

We will be solving programming problems in class, in groups and individually. Small homework assigned every class for better material retention. A project in the second half of the semester, in which you will be implementing a program or tool of your choice using functional programming principles. A final exam at the end of the semester.

Grading

• 25% attendance and work in class
• 15% homework
• 40% project
• 20% final exam

Literature

Main text:
– Functional Programming in OCaml, Cornell CS 3110 textbook (2019)

Supplementary reading on OCaml:
– Jason Hickey, Introduction to OCaml (2008)
– Real World OCaml 2nd Edition (in progress)

Online documentation for OCaml:
– OCaml.org, the official community website
– Module Pervasives of the standard library
– Reference manual
– Github/Awesome-OCaml, a curated collection of OCaml tools and libraries

Functional programming:
– Structure and Interpretation of Computer Programs, video lectures of the classical course on functional programming from MIT (the text of the book) (1986)

Theoretical background, lambda calculus:
– Introduction to Functional Programming, John Harrison (1999)
– Foundations of Functional Programming, Lawrence C Paulson (2000)
– Video lectures by Frank Pfenning on Basic Proof Theory, discussing the relation between programs and proofs (2015)

Tentative schedule

• May 29. Expressions. Functions. Recursion.
• Jun 3. Lists. Pattern matching. Local name binding.
• Jun 5. Common built-in types. Printing. Semicolon. Tuples. Accumulators.
• Jun 10. Tail call optimization. Option type. Map, filter, iter.
• Jun 12. Variant types. Reading files.
• Jun 17. Currying. Pipeline operator. Fold.
• Jun 19. Records and modules
• Jun 24. Recursive variant types. Binary search trees. S-expressions. Examples with Opal and Cairo.
• Jun 26. Module signatures. Functors. Map and Set.
• Jul 1. Monads. Memoization. Delayed computation. Sequences. Lambda calculus.
• Jul 3. Final Exam.
• Jul 8. Project presentations.