Syntactic Sugar for Monads November 2008 * Contents COPYING - License under which the present version is released (a copy of one of the 2 below) LGPL - LGPL compatible of Objective Caml MIT - Alternate license (upon request) ChangeLog - Recent changes META.in - Configuration information for findlib Makefile - GNU make build rules for the extension and the test frame README - This file cc.ml - Interface of delimited continuation monad cc.mli - Implementation of delimited continuation monad exception.ml - Implementation of exception monad exception.mli - Interface of exception monad io.ml - Implementation of I/O-monad io.mli - Interface of I/O-monad monadic_io.ml - Example of input/output with the I/O-monad pa_monad.ml - Camlp4 syntax extension for Objective Caml versions 3.10 and later pa_monad-camlp4-3.09.ml - Camlp4 syntax extension for Objective Caml version 3.09 pa_monad-custom-tuareg.el - Emacs customization for pa_monad pythagorean_triples.ml - Nondeterminism monad (backtracking) coded with "pa_monad.ml" test_cc.ml - Test of delimited continuation monad test_exception.ml - Test of the exception monad test_monad.ml - Simple test frame for "pa_monad.ml" test_rec.ml - Test of recursive-binding features test_syntax.ml - Thorough test of the syntax extension utest.ml - Implementation of the unit-test framework utest.mli - Interface of the unit-test framework * Supported Camlp4 Versions Moving from OCaml version 3.09 to 3.10 the preprocessor, Camlp4, was massively revamped. This invalidated most syntax extensions written for version 3.09 including pa_monad. The current package includes "pa_monad.ml" that works with OCaml-3.10 up to 3.11. For convenience we supply "pa_monad-camlp4-3.09.ml" that works with the older OCaml-3.09. See section "How to... Compile" for instructions to build with OCaml-3.09. * What It Does This Camlp4 parser adds some syntactic sugar to beautify monadic expressions. The name of the syntax extension is a bit misleading as it does not provide any monad nor monadic computation. The correct name would have been "pa_perform", but it was discarded because of lack of specificity. Example: A simple but realistic example of the use of a list monad looks like this bind [1; 2; 3] (fun a -> bind [3; 4; 5] (fun b -> return (a + b))) where we assume the appropriate definitions of the functions "bind" and "return". With the help of "pa_monad" this can be written as perform a <-- [1; 2; 3]; b <-- [3; 4; 5]; return (a + b) which is much clearer and thus easier to understand and maintain. By the way, the expression evaluates to [4; 5; 6; 5; 6; 7; 6; 7; 8] the sum of each pair of values of the input lists. For more examples have a look at the examples "exception.ml" or "pythagorean_triples.ml". ** Highlights - Efficient code: The generated code is as efficient as hand-coded. - Highly flexible: The "bind" and "failwith" functions can be specified in various ways (a) Binding with default names: perform ... (b) Binding with user-defined names: perform with my_bind and my_failwith in ... (c) One-of-a-kind binding: perform with fun a f -> f a and ... in ... (d) Module-based binding: perform with MyMonad in ... or with OCaml's local modules: let foo ... = let module MyMonad = ... in perform with MyMonad in ... ** Known Issues See the section "Known Issues" in the documentation. * How to... ** Compile make Note that "pa_monad.cmo" is the only interesting product file. There is no "pa_monad.cmx" for OCaml just needs the byte-code version of the syntax extension. To compile the old version of pa_monad, using a pre-3.10.0 compiler and preprocessor say for example make OCAMLC=ocamlc-3.09 \ CAMLP4=camlp4o-3.09 \ PP-EXT="-pp '\$(CAMLP4) -I . pa_extend.cmo q_MLast.cmo'" \ SYNTAX-EXTENSION=pa_monad-camlp4-3.09.cmo where OCAMLC and CAMLP4 define the name of your compiler and preprocessor. ** Test make test For OCaml-3.09: Append "test" to the command line given in sub-section "Compile". ** Generate (HTML) Documentation make doc ** Install (with findlib) make findlib-install ** Use Given the compiled extension "pa_monad.cmo" feed the source into the preprocessor by saying ocamlc -pp 'camlp4orf -I . pa_monad.cmo' -c ... Depending on where the cmo-file lives the include path needs tweaking. For OCaml-3.09 use ocamlc -pp 'camlp4o -I . pa_monad.cmo' -c ... After installation, findlib users cast the usual spell ocamlfind ocamlc -package monad -c ... * Emacs - Tuareg Mode We have included a customization for Tuareg-mode that makes "perform" a keyword with the correct indentation behavior. Include it in your ".emacs" to activate it. * Useful Literature On Monads Literature on the use of monads in OCaml is sparse at best. Most of the following articles are either language independent or use the Haskell language. A large bibliography on "Monads and Arrows: Theory and Applications" can be found at http://haskell.readscheme.org/monads.html ** Philip Wadler, "Monads for functional programming" The use of monads to structure functional programs is described. Monads provide a convenient framework for simulating effects found in other languages, such as global state, exception handling, output, or non-determinism. Three case studies are looked at in detail: how monads ease the modification of a simple evaluator; how monads act as the basis of a datatype of arrays subject to in-place update; and how monads can be used to build parsers. ** Brian Hurt and Robert Fischer, "Monad Tutorial for Ocaml" Brian Hurt and Robert Fischer wrote a comprehensive monad tutorial particularly for OCaml programmers. ** Theodore Norvel, "Monads for the Working Haskell Programmer" This short tutorial introduces monads to Haskell programmers. ** John Hughes, Magnus Carlsson, "Systematic Design of Monads" Many useful monads can be designed in a systematic way, by successively adding facilities to a trivial monad. The capabilities that can be added in this way include state, exceptions, backtracking, and output. Here we give a brief description of the trivial monad, each kind of extension, and sketches of some interesting operations that each monad supports. ** Jeff Newbern, "All About Monads" This tutorial aims to explain the concept of a monad and its application to functional programming in a way that is easy to understand and useful to beginning and intermediate Haskell programmers. Familiarity with the Haskell language is assumed, but no prior experience with monads is required. The tutorial covers a lot of material and the later sections require a thorough understanding of the earlier material. Many code examples are provided along the way to demonstrate monadic programming. It is not advisable to attempt to absorb all of the material in a single reading. ** Philip Wadler, "Comprehending Monads" Category theorists invented monads in the 1960's to concisely express certain aspects of universal algebra. Functional programmers invented list comprehensions in the 1970's to concisely express certain programs involving lists. This paper shows how list comprehensions may be generalized to an arbitrary monad, and how the resulting programming feature can concisely express in a pure functional language some programs that manipulate state, handle exceptions, parse text, or invoke continuations. A new solution to the old problem of destructive array update is also presented. No knowledge of category theory is assumed. ** Simon Peyton Jones, "Tackling the Awkward Squad" Functional programming may be beautiful, but to write real applications we must grapple with awkward real-world issues: input/output, robustness, concurrency, and interfacing to programs written in other languages. These lecture notes give an overview of the techniques that have been developed by the Haskell community to address these problems. I introduce various proposed extensions to Haskell along the way, and I offer an operational semantics that explains what these extensions mean. ** Richard Bird, "Introduction to Functional Programming using Haskell", 2nd ed. Chapter 10 of this book is dedicated solely to monads. They are introduced in a very didactic way. Chapter 11 treats writing parsers based on monads. * Authors Please report comments or suggestions to the authors. - Jacques Carette, - Lydia E. van Dijk, - Oleg Kiselyov, * LGPL The "pa_monad" extension is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License in the file "LGPL" for more details. * MIT You may also obtain this software under the MIT license upon request to the authors. In that case, see "MIT" for the details. local variables: mode: outline end: