Recent Changes · Search:

Functional Programming

• (incorporates former Speagram)

Emacs

Algorithmic Game Theory: Prediction Markets (po polsku)

# Functional

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.

Functional programming video lectures:

## 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]
3. Lecture 3: Computation Δ. [2 hours]
4. Lecture 4: Functions Δ (and Lambda Calculus). Also known as Alligator Calculus. (Lecture requires OCaml.) [3 hours]
5. Lecture 5: Polymorphism and Abstract Data Types Δ. Type inference. Polymorphic recursion. Algebraic specifications. Maps. Red-black trees. [3 hours]
6. Lecture 6: Generic functions, Lists. Δ Generic programming with mapping and folding. Backtracking with lists. [5 hours]
7. Lecture 7: Laziness and Streams. Δ Lazy evaluation and stream processing. [3 hours]
8. Lecture 8: Monads. Δ List comprehensions. Monads. The module system. Probabilistic Programming. Lightweight cooperative threads. [7 hours]
9. Lecture 9: Compilation and Parsing. Δ Working with OCaml projects. Compiling and runtime of FPLs: Garbage Collection and closures. Optimization. Writing parsers in Menhir.
10. Lecture 10: FRP. Δ Zippers. Adaptive Programming aka. Self-Adjusting Computation. Functional Reactive Programming i.e. temporal programming. GUIs.
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.
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)
• F#: Visual F#

### 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
• I use Emacs with fsharp-mode, download from http://sourceforge.net/projects/fsharp-mode/ and follow instructions in the README file.