In this first part of the first week, we review some history and motivation for Functional Programming, learn about the OCaml ecosystem in general, and discover the available tools and resources.

• Greetings (video)
  
  

  Greetings from Xavier Leroy.

• Introduction to the course (video, slides)
  
  

  This sequence provides a general overview of the course, its motivation, and the overall structure of the different lectures.

• Functional Programming: history and motivation (video, slides)
  
  

  In this sequence, we review some history and motivation for Functional Programming, and find out why there is so much excitement about the addition of so-called lambdas in many programming languages.

  • Exercise: Church-Turing thesis

• The OCaml language: history and key features (video, slides)
  
  

  In this sequence, we recall the origins of the OCaml programming language, and pinpoint the key features of the language.

  OCaml is a member of the ML family of programming languages, that provide a unique combination of functional programming with strong static typing, type inference and algebraic data types.

• Why the OCaml language: meet the users (video, slides)
  
  

  In this sequence, we let the users of the OCaml programming language speak up. We will hear voices from people participating in advanced research project, and enterprises developing world-class industrial applications. It is a unique occasion to learn which features are important for them, and why.

• Tools and development environment: first steps in OCaml! (video, slides)
  
  

  In this sequence, we provide an overview of the tools and the development environment available for OCaml. Here we introduce the interactive exercise environment that you will use during the rest of the course, and provide you with a guided tour of its features.

  Unlike most of the development environment used in online course, state-of-the art technology developed around OCaml allows us to provide an environment that runs fully in your browser, using the Javascript engine of your browser. No download is needed, and no remote server is hidden behind your interactive development environment! Notice that you need a recent browser: we suggest Chrome or Firefox, possibly the latest version.

  • Exercise: Grading environment (test-bed)

• A brief showcase of some of OCaml's features (video, slides)
  
  

  In this sequence, we offer a preview of some of the amazing features of the OCaml programming language. Do not try to fully understand the precise details of the code shown: you will master them all by the end of the course. What is important to get here is the feeling of the power that can be unleashed using OCaml.

• Overview of the available resources (video, slides)
  
  

  In this sequence, we will briefly review the main available resources that are relevant for taking full advantage of the course. You will also find here pointers for reaching out to the great OCaml community.

• Survey
  
  

  Survey.

In this second part of the first week, we learn the basic features needed to write our first functions.

• Tezos (video)
  
  

  Tezos

• Basic Data Types (video, slides)
  
  

  This sequence introduces two important primitive types of OCaml: integers and booleans.

  • Exercise: Integer expressions -- quiz
  • Exercise: Boolean expressions -- quiz

• More Data Types (video, slides)
  
  

  In this sequence we introduce some more primitive types: floats, characters, and strings. We also talk about conversion functions between different types.

  • Exercise: Floating point expressions -- quiz
  • Exercise: String functions -- quiz

• Expressions (video, slides)
  
  

  Expressions compute values, they play a central role in functional programming. This sequence shows some basic constructions of expressions: conditionals and function application. We also show some examples of polymorphic operators.

  • Exercise: Conditional -- quiz
  • Exercise: Function application -- quiz

• Definitions (video, slides)
  
  

  Definitions introduce names of identifiers, and bind values to them. This sequence explains the two forms of definitions in OCaml, namely local and global definitions, and shows why simultaneous definitions are useful.

  • Exercise: Integer identifiers
  • Exercise: String identifiers

• Functions (video, slides)
  
  

  In functional programming, functions are the basic means to structure and to generalize code. This sequence shows some simple examples of function definitions in OCaml. We also discuss the fundamental principle of lexical scoping, and demonstrate that identifiers are not variables in the sense of imperative programming.

  • Exercise: Simple functions over integers
  • Exercise: Simple functions over strings

• Recursion (video, slides)
  
  

  This sequence explains how to define in OCaml recursive functions, that is functions that in their definition call themselves.

  • Exercise: Prime numbers

This week and the next one, we will learn how to structure code and data with types. Types are not only useful to document programs using type abbreviations (sequence 0) but also to inform the compiler about the shape of values so that it can statically check that they are properly used. This week will be devoted to flat data like tuples (sequence 1), records (sequence 2) or arrays (sequence 3). A toy typed database will be implemented during sequence 4.

• Greetings (video)
  
  

  Greetings from OCamlPro.

• User-defined types (video, slides)
  
  

  Types are useful to document a program because they attach an application-specific meaning to a set of values. A type abbreviation is the simplest way to introduce types in programs by binding a user-defined identifier to a type. In this sequence, we will learn the syntax of type definitions and how to write type annotations.

  • Exercise: User-defined types -- quiz

• Tuples (video, slides)
  
  

  The simplest way to aggregate several values is to join them in a tuple. This sequence introduces the syntax for constructing and observing tuples.

  • Exercise: Enigma

• Records (video, slides)
  
  

  In a tuple, each component is referred using its position. This may be error-prone. Record types allow each component to be named. This makes code more readable because field names have more meaning than positional reference. In this sequence, we will discover how to declare record types, how to construct record values and how to observe them.

  • Exercise: Points and vectors
  • Exercise: Time on planet Shadokus

• Arrays (video, slides)
  
  

  In many situations, the number of components of a composite value cannot be determined at compile-time. Arrays are data structures which size is dynamically computed. This sequence will present the type for arrays as well as the syntax to define array values and to observe their components through indices.

  • Exercise: Finding the minimum
  • Exercise: Searching for strings in arrays

• Case study: A small typed database (video, slides)
  
  

  This sequence is a case study showing how tuples, records and arrays can be used to implement a toy typed database. The limits of this implementation will illustrate the need for more structured values. Next week is about algebraic datatypes which are an elegant remedy against these limitations.

  • Exercise: A small typed database

This week, we will continue our tour of the OCaml type system. Last week, we only defined flat data structures which are nice to aggregate values but quite limited when you try to structure values. Algebraic datatypes offer several mechanisms to attach more informative static description of values using tags (sequence 0), to define recursive data structures like lists (sequence 1) or to structure values in a hierarchical way (sequence 2). During sequence 3, we will discover how programming is type-directed in OCaml through the implementation of a story generator. Type definition can be made more generic in OCaml thanks to parameterized type definitions (sequence 4). The final sequence will present some advanced features of the type system (sequence 5).

• Tagged values (video, slides)
  
  

  In this sequence, we will focus on list, an ubiquitous data structure in functional programming. First, we will see how the type for lists simply is a recursive algebraic datatype. Second, the builtin types for list is presented.

  • Exercise: Pattern matching exhaustivity
  • Exercise: A type for array indexes
  • Exercise: The option type

• Recursive types (video, slides)
  
  

  In this sequence, we will focus on list, an ubiquitous data structure in functional programming. First, we will see how the type for lists simply is a recursive algebraic datatype. Second, the builtin types for list is presented.

  • Exercise: First In First Out
  • Exercise: Classic functions over lists

• Tree-like values (video, slides)
  
  

  In this sequence, we go further on the topic of recursive datatypes. Tree-like datastructures are also omnipresent in computer science because they allow for a hierarchical organization of data. Defining a type for trees is straightforward in OCaml using a recursive algebraic datatype. We will refactorize our typed database example by replacing arrays with such a tree-like representation.

  • Exercise: Symbolic manipulation of arithmetic expressions
  • Exercise: Tries

• Case study: a story teller (video, slides)
  
  

  This sequence is a case study about the implementation of a story generator. A story is a typical hierarchical information (it is composed of event which are themselves characterized by other values). We will show how the typechecker and type definitions can guide programming.

  • Exercise: Type directed programming

• Polymorphic algebraic datatypes (video, slides)
  
  

  We already saw that the type for list is parameterized by the type of the elements of the list. This polymorphic algebraic datatype is very convenient because it improves code reuse: the module List is written once and for all and provides functions over lists of any element type. In this sequence, you will learn the syntax to define your own parameterized types.

  • Exercise: Balanced binary trees
  • Exercise: An implementation of list with an efficient concatenation

• Advanced topics (video, slides)
  
  

  In this sequence, we will learn some advanced mechanisms related to algebraic datatypes.

  • Exercise: Advanced patterns

During this fifth week we will discuss functions in OCaml in their full generality. We will see that functions are in fact first class values in functional programming languages, and we will learn how to write useful functions on the structured data types that have been introduced in Weeks 2 and 3.

• Functional Expressions (video, slides)
  
  

  In this sequence we explain how to write expressions that denote functional values. These correspond to the so-called lambda-expressions which also exist in other programming languages like Python or Java.

  • Exercise: Lambda-expressions as values

• Functions as First-Class Values (video, slides)
  
  

  This sequence explains a distinguishing feature of Functional Programming: Functions are First-Class Values, that is they can be used in the same way as any other value.

  • Exercise: Using first class functions

• Functions with Multiple Arguments (video, slides)
  
  

  In this sequence we explain that functions in OCaml are in reality functions with one argument only, and that functions with several arguments are just an abbreviation for nested functions with one argument only.

  • Exercise: Functions returning functions

• Partial Function Application (video, slides)
  
  

  This sequence explores a consequence of what we have learned in Sequence 2: a function with several arguments may be applied to some of its arguments only. We show at hand of an example how to put this so-called Partial Application into use.

  • Exercise: Optimizing partial applications
  • Exercise: A small arithmetic interpreter

• Mapping Functions on Lists (video, slides)
  
  

  This sequence introduces the function Map which allows you to transform a list by applying the same function to all elements of the list.

  • Exercise: Using and writing the map function

• Folding Functions on Lists (video, slides)
  
  

  This sequence introduces two different folding functions on lists. Both allow us to combine the elements of a list using a binary operator.

  • Exercise: Using fold to produce lists
  • Exercise: Using fold to check predicates

Exploring the imperative features offered by the OCaml language.

• Imperative features in OCaml (video, slides)
  
  

  In this sequence, we remark that sometimes imperative features are useful, and dress a list of the ones we see this week.

• Getting and handling your Exceptions (video, slides)
  
  

  Exceptions are useful to alter the flow of control, capture all kinds of errors, and handling them.

  In this sequence, we meet the exception mechanism offered by OCaml, and learn to use it at our advantage.

  • Exercise: Unraveling the automatic grader

• Getting information in and out (video, slides)
  
  

  Reading from the input and writing to the output can be performed easily by using some other very useful imperative features.

  • Exercise: Printing lists
  • Exercise: Displaying a Filesystem Hierarchy

• Sequences and iterations (video, slides)
  
  

  Once we have imperative constructs at hand, executing them one after the other is a must. We learn here the special syntax we have at hand in OCaml for this task.

  • Exercise: Printing with loops
  • Exercise: Producing fine ASCII art

• Mutable arrays (video, slides)
  
  

  Now we meet data structures that are modifiable in place. We will start from the arrays, as we find out that thay can actually be modified, like arrays in most other programming languages.

  • Exercise: Rotating the contents of an array
  • Exercise: Implementing a stack with an array

• Mutable record fields (video, slides)
  
  

  In OCaml, it is possible to have a fine control on which part of a data structure can be modified in place, in the imperative style, and which cannot. Time to meet the mutable record fields!

  • Exercise: Implementing mutable lists

• Variables, aka References (video, slides)
  
  

  Variables? You want variables? Yes, you can have them! One can simulate the usual imperative variables by using identifiers and a record with mutable fields.

  • Exercise: Simple uses of references
  • Exercise: Reading lines from the standard input

This last installment of the course is about programming-in-the-large using the module system of OCaml. When a piece of software reaches a level of complexity that requires several programmers to develop together, new mechanisms are needed to structure programming. Module implementations must be organized hierarchically and hidden behind interfaces (sequence 0). Information hiding must be enforced by the type abstraction (sequence 1). A case study will put these mechanisms at work through the developement of a module for dictionaries (sequence 2). Functors are a powerful mechanism to a parameterize module with respect to a family of modules described by a signature (sequence 3). Finally, the final sequence will present the compilation process of OCaml and the tools that ease the creation of software made of compiled modules and libraries (sequence 4).

• Guests (videos)
  
  

  A word from professional OCaml users.

• Structuring software with modules (video, slides)
  
  

  Value and type definitions can be regrouped into modules. A module is a software component which has an internal consistency and provides some services through an interface. OCaml takes modules seriously: not only it provides syntax to define module implementations and interfaces, but the typechecker statically checks that that modules are properly used. In this sequence, we present the syntax of module implementations and interfaces.

  • Exercise: Opening modules
  • Exercise: Accessing modules and submodules
  • Exercise: Wrapping functions in a module

• Information hiding (video, slides)
  
  

  The purpose of an interface is to publish the minimal amount of definitions needed to use a module. Hiding everything that is not necessary to the module client is very important to reduce the interdependencies between modules. Type abstraction is a powerful mechanism to enforce information hiding.

  • Exercise: Type abstraction using a signature
  • Exercise: Multiset

• Case study: A module for dictionaries (video, slides)
  
  

  In this sequence, we discuss the design of a module for dictionaries.

  • Exercise: Remove elements from dictionaries

• Functors (video, slides)
  
  

  Functors are functions from modules to modules. In other words, a functor is a module parameterized by another module. In this sequence, the syntax for functors is explained.

  • Exercise: Char indexed hashtables

• Modules as compilation units (video, slides)
  
  

  In this final sequence, we present the compilation tools of the OCaml ecosystem.

• Survey
  
  

  Survey.