-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
296 lines (208 loc) · 10.2 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
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, <carette AT mcmaster DOT ca>
- Lydia E. van Dijk, <lvandijk AT freenet DOT de>
- Oleg Kiselyov, <oleg AT pobox DOT com>
* 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: