• View
• Edit
• History
• Print

Functional

Jump to the current lecture

This is a course on Functional Programming in OCaml. It focuses on functional programming ideas, rather than pragmatic OCaml programming. Lectures 1 to 6 may appear overwhelming as they introduce many concepts. In fact, the algorithmic content of lectures 1–6 is for the most part quite simple, but I wanted them to force the students to think from scratch. Concepts from lectures 7, 8, 10 are more prevalent in Haskell, because OCaml programmers can judiciously use imperative features to avoid introducing complexity. In particular, monadic programming has better optimization support in Haskell than in OCaml. Lecture 9 (and lectures 12, 14 to come) address the pragmatics of OCaml programming directly. To be a well-rounded functional programmer, you should also complete a complementary course based on the book Pearls of Functional Algorithm Design by Richard Bird. Or you can intersperse reading Pearls of Functional Algorithm Design with following this course. (Perhaps I’ll do something about it.)

Initial lectures have examples translated to F#, but then I decided to focus on OCaml.

Useful links:

• New: Type OCaml — impressive site teaching functional programming in OCaml.
• Awesome OCaml links.
• OCaml from the Very Beginning by John Whitington (book and) a couple of video lectures for extreme beginners.
• OCaml-Top editor suited for solving exercises.
• A community site for OCaml: The OCaml Programming Language.
  • I recommend OCaml comprehensive tutorial
  • In particular, practice! (99 problems)
    • The original Prolog Problems,
    • Ninety-Nine Haskell Problems,
    • and new: S-99: Ninety-Nine Scala Problems.
• Our course focuses on functional programming intuitions rather than the wider practice of programming. But:
  • Real World OCaml book.
  • To follow-up on OCaml programming, try Developing Applications with OCaml.
  • Or try Unix system programming in OCaml.
• OCaml manual
• OCaml Batteries API
• OCaml API search only standard library and ExtLib (an old precursor of Batteries)
• F# operators and basic functions
• OCaml Tutorial for functional programming beginners

Functional programming video lectures:

• Functional Programming Fundamentals in Haskell, by Erik Meijer, based on Programming in Haskell by Graham Hutton. (at Channel 9)
• Functional Programming with Ralf Laemmel, more advanced topics, in Haskell. (at Channel 9)
• Functional Programming Principles in Scala by Martin Odersky. (at Coursera)
• Introduction to Functional Programming by Philip Wadler, in Haskell. (at Edinburgh)

Lectures and assigned material

The time given is how many lecture-hours a lecture actually took us, for reference: don’t be scared that lecture 6 appears as a single lecture. One meeting is two lecture-hours.

1. Lecture 1: Logic Δ (and Types). [2 hours]
   • Examples: Lec1.ml Δ, Lec1.fs Δ.
   • For further practice, you can do lessons 1–4 of the tutorial at http://try.ocamlpro.com/, and parts “Quick Language Overview” and “The Functional World” of the tutorial at http://www.tryfsharp.org/. Skip over the parts that you do not understand or that are too time-consuming. Unfortunately the F# tutorial wouldn’t work for me under Linux, but it works under Windows.
2. Lecture 2: Algebra Δ (and Algebraic Data Types) (needs some fixes) — Lecture 2 Figure Δ. [2 hours]
   • Examples: Lec2.ml Δ, Lec2.fs Δ.
   • Exercises Δ, Lec2exs.ml Δ.
3. Lecture 3: Computation Δ. [2 hours]
   • Examples: Lec3.ml Δ, Lec3.fs Δ.
   • Exercises Δ (same as on slides plus one more).
4. Lecture 4: Functions Δ (and Lambda Calculus). Also known as Alligator Calculus. (Lecture requires OCaml.) [3 hours]
   • Examples: Lec4.ml Δ.
   • Exercises Δ (same as on slides minus one).
5. Lecture 5: Polymorphism and Abstract Data Types Δ. Type inference. Polymorphic recursion. Algebraic specifications. Maps. Red-black trees. [3 hours]
   • Red-Black trees with deletion Δ by Matt Might.
   • Exercises Δ (same as on slides plus unification algorithm).
   • Examples: Lec5.ml Δ, a bit incomplete: Lec5.fs Δ, Lec5.fsi Δ.
     • polymorphic recursion examples only in OCaml Δ.
6. Lecture 6: Generic functions, Lists. Δ Generic programming with mapping and folding. Backtracking with lists. [5 hours]
   • Examples: Lec6.ml Δ.
   • Exercises Δ.
7. Lecture 7: Laziness and Streams. Δ Lazy evaluation and stream processing. [3 hours]
   • Examples: Lec7.ml Δ.
   • Exercises Δ.
8. Lecture 8: Monads. Δ List comprehensions. Monads. The module system. Probabilistic Programming. Lightweight cooperative threads. [7 hours]
   • Examples: Lec8.ml Δ.
   • Exercises Δ.
   • Teaser for Probabilistic Programming paradigm — from cognitive science perspective.
     • For even more, see probabilistic-programming and HANSEI OCaml library.
   • Tutorial on the state monad and on monad transformers.
   • Monad syntax extension
     • pa_monad312.zip Δ, Attach:pa_monad400.zip Δ.
9. Lecture 9: Compilation and Parsing. Δ Working with OCaml projects. Compiling and runtime of FPLs: Garbage Collection and closures. Optimization. Writing parsers in Menhir.
   • This lecture is OCaml-specific, and least functional-programming-ish in the course.
   • Examples:
     • Lec9b.zip Δ — compiling multifile projects.
     • Lec9o.zip Δ — optimization experiments.
     • Lec9m.zip Δ — extracting email addresses by an ocamllex program.
     • Lec9-calc-param.zip Δ — calculator.
     • Lec9e.zip Δ — toy English grammar.
     • Lec9c.zip Δ — phrase search experiments.
   • Exercises Δ.
   • Reading the generated assembly — compiling with ocamlopt -S.
   • Writing Performance Sensitive OCaml Code
   • New: capnp-ocaml 2.0: The Road to Unembarrassing Performance — a blog post about optimizing an OCaml serialization plugin.
10. Lecture 10: FRP. Δ Zippers. Adaptive Programming aka. Self-Adjusting Computation. Functional Reactive Programming i.e. temporal programming. GUIs.
    • Zippers at Haskell Wikibook
    • How Froc works
    • Examples: Lec10.zip Δ.
    • Exercises Δ.
    • Using LablTk, LablTk tutorial, LablTk older tutorial, using LablGtk, LablGtk tutorial, LablGtk-2 tutorial.
    • Self-Adjusting Computation at Umut Acar’s website.
    • NEW: Incremental: a library for incremental computations.
11. Lecture 11: the Expression Problem. Δ Type system concepts for solving the Expression Problem with introduction to OCaml’s objects and classes. Monadic parsing and dynamic code loading.
    • Examples: Lec11.zip Δ.
    • Exercises Δ.
    • Ralf Laemmel lectures on MSDN’s Channel 9: The Expression Problem, Haskell’s Type Classes.
    • Developing Applications With Objective Caml. Chapter 15: Object-Oriented Programming, Chapter 16: Comparison of the Models of Organisation.
    • Real World OCaml. Chapter 11: Objects, Chapter 12: Classes.
    • Jacques Garrigue: Code Reuse Through Polymorphic Variants, Structural Types, Recursive Modules, and the Expression Problem.
    • Graham Hutton and Erik Meijer: Monadic Parser Combinators.
12. Lecture 12: Standard Libraries. Haskell’s type classes. OCaml’s alternatives Batteries and Core, and Haskell Hierarchical Libraries.
13. Lecture 13: Category Theory for Functional Programmer. Invitation to Category Theory.
14. Lecture 14: Parallelism. Sharing memory across processes, MPI, and more.

Contact me if you would like to receive our exam exercise sets. They are based in half on 99 problems.

Working in the browser:

• Tutorial OCaml toplevel running on client-side in JavaScript (compiled from OCaml bytecode by js_of_ocaml).
• OCaml toplevel with the same js_of_ocaml-based engine.
• OCaml toplevel running on client-side in Java plugin (compiled from OCaml sources by ocamljava).
• http://codepad.org/ online compiler/interpreter for several languages, running on server-side.

Installing on a desktop:

The instructions below are outdated. Go to ocaml.org / Install OCaml if you do not have OCaml working yet.

Installing on Windows:

• OCaml student-friendly: OCaml Installer
  • The installer will also install Emacs. We will have several ways to use OCaml:
    • using the graphical toplevel OCamlWin.exe,
    • using any editor, e.g. OCamlBrowser, copying to the toplevel ocaml.exe and using the compiler ocamlc.exe,
    • using Emacs as we do under Linux.
  • Save common.ml Δ as .ocamlinit in a directory which OCaml will recognize (either “home” or where you start OCaml); or just # #use “path\to\common.ml”;; in the toplevel (where path\to is the directory in which you saved common.ml Δ).
• OCaml developer-friendly: Wodi (based on GODI)
• See also OCaml 4.0 Win readme.
• F#: Visual F#
  • InstallFSharp.msi on the page linked
  • (Right now I have problems using Visual Studio :p but F# Console works just fine.)

Installing on Debian-derived systems (e.g. Ubuntu):

• OCaml:
  • $ sudo apt-get install ocaml
  • $ sudo apt-get install tcl8.5-dev tk8.5-dev (as suggested)
  • We do not need Batteries, so instead, save common.ml Δ as .ocamlinit in your home directory.
    • But if you really want Batteries, do: $ sudo apt-get install ocaml-batteries-included
    • and save ocamlinit.ml Δ as .ocamlinit in your home directory, for OCaml Batteries Included to start automatically in the toplevel.
  • $ ocaml starts the toplevel.
  • Instal other tools and libraries as needed, in similar manner.
• F#:
  • $ sudo apt-get install mono-devel mono-tools-devel libmono-winforms2.0-cil libmono-system-runtime2.0-cil
  • Download fsharp2.0-1all.deb (this is just one possibility…)
  • $ sudo dpkg -i fsharp2.0–1all.deb
  • $ fsharpi starts the toplevel.
  • If the toplevel fails, we try to install from sources:
    • $ sudo apt-get purge fsharp
    • $ git clone https://github.com/fsharp/fsharp.git
    • $ cd fsharp
    • $ autoreconf
    • $ ./configure —prefix=/usr
    • $ make
    • $ sudo make install
    • $ fsharpi
      • (thanks to instructions at F# on Ubuntu 11.10)
  • I use Emacs with fsharp-mode, download from http://sourceforge.net/projects/fsharp-mode/ and follow instructions in the README file.