An introduction to the practice and foundation for functional programming. We first study how to program in OCaml, a language with native support of function programming (also imperative programming). We then study how to implement the underlying theory of functional programming, i.e., λ-calculus in OCaml. We finally choose and work on a non-trivial functional programming project.

Programming in a Functional Programming Language

Setup the Programming Environment

You first need to setup the programming environment, including the operating system and the compiler.

Operating Systems: I strongly recommend you to install a Linux distribution such as Ubuntu or Debian. If you have to use Windows, install Windows Subsystem for Linux (WSL) and a linux distro on it.
Setup OCaml: Follow the instructions to setup OCaml. The best way is to use OCaml's package manager Opam. The instructions for using opam can be found at here. You can also find a comprehensive guide to install opam in WSL at here.
Interprator: OCaml programs may be directly run in an read-eval-print loop (REPL). Once you have setup the opam, run opam install core to install enhancements to the REPL environment.
Editors: I strongly recommend you to learn Emacs or Vim as a programming editor. Under emacs, you may install editor modes such as tuareg and merlin to greatly facilitate your coding process.

Practice Programming in OCaml

We shall use Real World OCaml as our reference text book for this study. Read the following chapters to get an exposure to the core concepts of OCaml (they should be enough for our purpose, although you are welcome to delve into more advanced topics at your leisure):

A Guided Tour
Variables and Functions
Lists and Patterns
Files, Modules, and Programs
Records
Variants

λ-Calculus and Abstract Machines

The theoretical underpinning of functional programming is a formal system for symbolic manipulation known as the λ-calculus. We shall study the syntax and semantics of λ-calculus, develop a basic evaluator for it, and develop a series of abstract machines for it in OCaml.

Reading materials:

Introductory Notes
Lambda Calculus Encodings
Programming Languages and Lambda Calculi (by Matthias Felleisen and Matthew Flatt)
The Next 700 Programming Languages (by Peter Landin)
Mechanical Evaluation of Expressions (by Peter Landin)
From Krivine’s machine to the Caml implementations (by Xavier Leroy)

Functional Programming Projects

Some tentative topics:

Implement an abstract machine for a subset of the OCaml language
Implement an abstract machine for a subset of C/C++
Implement an abstract machine for the call-by-push-value λ-calculus
Implement a turn-based game engine in OCaml
Implement a producer consumer library in MultiCore OCaml (OCaml 5)
Student Proposed Projects

Introduction to Functional Programming

Programming in a Functional Programming Language

Setup the Programming Environment

Practice Programming in OCaml

λ-Calculus and Abstract Machines

Functional Programming Projects

Schedule