module Pa_monad:sig
..end
This module extends OCaml's syntax by a Haskell-like "do
"-notation
particularly suited for the work with monads.
By the nature of the translation process (at pre-processing time, before compilation) it cannot be guaranteed that the result code actually obeys the three fundamental laws for all monads:
bind (return x) f
is identical to f x
bind m return
is identical to m
bind (bind m f) g
is identical to bind m (fun x -> bind (f x) g)
bind
and return
are user defined functions. Incidentally,
in Haskell, too, it is entirely the responsibility of the programmer
to make sure that bind
and return
are implemented for a particular
Monad do indeed obey the above laws.
Conversion Rules
Grammar informally
We support four different constructs to introduce monadic
expressions.
perform exp
perform exp1; exp2
perform x <-- exp1; exp2
perform let x = foo in exp
do
"-notation, with the differences that Haskell uses "do
" and
"<-
" where we use "perform
" and "<--
".
We support not only let x = foo in ...
expressions but arbitrarily
complex let
-expressions, including let rec
and let module
.
Extended Forms
The actual bind function of the monad defaults to "bind
" and the
match-failure function to "failwith
". The latter is only used for
refutable patterns; see below. To select different functions, use the
extended forms of "perform
".
Expression: Use the given expression as "bind
"-function and
apply the default match-failure function (failwith
) where necessary.
perform with exp1 in exp2
perform with exp1 in exp3; exp4
perform with exp1 in x <-- exp2; exp3
perform with exp in let x = foo in exp
Use the first given expression (exp1
) as "bind
"-function and the
second (exp2
) as match-failure function.
perform with exp1 and exp2 in exp3
perform with exp1 and exp2 in exp3; exp4
perform with exp1 and exp2 in x <-- exp3; exp4
perform with exp1 and exp2 in let x = foo in exp1
Module: Use the function named "bind
" from module "Mod
". In
addition use the module's "failwith
"-function in refutable patterns.
perform with module Mod in exp2
perform with module Mod in exp3; exp4
perform with module Mod in x <-- exp2; exp3
perform with module Mod in let x = foo in exp
Refutable Patterns
An irrefutable pattern is either:
_
",()
",Why do we need this distinction? Well, the expression
perform x <-- exp1; exp2
expands to
bind exp2 (fun x -> exp1)
where pattern match can never fail as "x
" can take any value. This
is an example of an irrefutable pattern. No catch-all branch is
required here. Compare this with
perform 1 <-- exp1; exp2
which expands to
bind exp2 (fun 1 -> exp1 | _ -> failwith "pattern match")
As the match can fail -- "1
" being a refutable pattern in this
position -- we must add a second branch that catches the remaining
values. The user is free to override the "failwith
" function with
her own version.
Refer to the thread on the Haskell mailing list concerning the topic of refutable patterns and an excerpt from an earlier discussion on the same issue.
Grammar formally
Formally the grammar of pa_monad
can be specified as follows.
"perform" ["with" <user-function-spec> "in"] <perform-body>
<user-function-spec> ::=
EXPR ["and" EXPR]
| "module" MODULE-NAME
<perform-body> ::=
<LET-FORM> <perform-body>
| EXPR
| <binding> ";" <perform-body>
| "rec" <binding> ["and" <binding> [...]] ";" <perform-body>
<binding> ::= PATTERN "<--" EXPR
whereEXPR
is an OCaml expression expr as defined in
Section 6.7, "Expressions",
of the OCaml manual,MODULE-NAME
a module-name
( Sec. 6.3, "Names"),LET-FORM
is any of the let
, let rec
, or let module
let-forms
( Sec. 6.7, "Expressions"), andPATTERN
a pattern
( Sec. 6.6, "Patterns").rec
" keyword allows for a recursive binding in
"rec" PATTERN "<--" EXPR
"and" PATTERN "<--" EXPR
...
"and" PATTERN "<--" EXPR ";"
The syntax extension groups all bindings in a "rec
"-"and
", but
it does not group consecutive "rec
"-bindings. This grouping is
sometimes called segmentation.
Example: Define a recursive group of bindings consisting of three
patterns (PATTERN1
-PATTERN3
) and expressions (EXPR1
-EXPR3
), a
non-recursive binding PATTERN4
/EXPR4
, and finally a single
recursive binding PATTERN5
/EXPR5
:
"rec" PATTERN1 "<--" EXPR1
"and" PATTERN2 "<--" EXPR2
"and" PATTERN3 "<--" EXPR3 ";"
PATTERN4 "<--" EXPR4 ";"
"rec" PATTERN5 "<--" EXPR5 ";"
Please consult
Section
7.3, "Recursive definitions of values" of the Manual for valid
recursive definitions of values, as the only allowed PATTERN
in the
recursive case is a NAME
. Similarly stringent restrictions apply to
EXPR
.
The theoretical aspects of recursive monadic bindings can be found in: Levent Erkök and John Launchbury, "A Recursive do for Haskell".
Formal Types of bind
and failwith
For any 'a monad
the expansion uses the functions "bind
" and
"failwith
" with the signatures
val bind: 'a monad -> ('a -> 'b monad) -> 'b monad
val failwith: string -> 'a monad
unless overridden by the user. Analogously, the signatures of modules
used in the "with module
"-form must enclose
sig
type 'a monad
val bind: 'a monad -> ('a -> 'b monad) -> 'b monad
val failwith: string -> 'a monad
end
Note that although a proper monad requires a return
function, the
translation itself does not need it.
Semantics (as re-writing into the core language)
In this section, we abbreviate irrefutable patterns with ipat
and
refutable patterns with rpat
.
perform exp1 ===> exp1
perform ipat <-- exp; rest ===> bind exp (fun ipat -> perform rest)
perform rpat <-- exp; rest ===> bind exp (fun rpat -> perform rest
| _ -> failwith "pattern match")
perform let ... in rest ===> let ... in perform rest
perform exp; rest ===> bind exp (fun _ -> perform rest)
perform with bexp in body
===> perform body
where bind is substituted with bexp
perform with bexp and fexp in body
===> perform body
where bind is substituted with bexp and
failwith is substituted with fexp
perform with module Mod in body
===> perform body
where bind is substituted with Mod.bind and
failwith with Mod.failwith
Implementation Notes And Design Decisions
It is be possible to use "<-
" instead of "<--
". In that case, the
similarity to the "do
" notation of Haskell will be complete.
However, if the program has _ <- exp
outside of perform
, this will
be accepted by the parser (and create an incomprehensible error later
on). It is better to use a dedicated symbol "<--
", so if the user
abuses it, the error should be clear right away.
The major difficulty with the perform
notation is that it cannot
truly be parsed by an LR-grammar. Indeed, to figure out if we should
start parsing <perform-body> as an expression or a pattern, we have to
parse it as a pattern and check for the "<--
" delimiter. If it is
not there, we should backtrack and parse it again as an
expression. Furthermore, a <-- b
(or a <- b
) can also be parsed
as an expression. However, some patterns, for example _ <-- exp
,
cannot be parsed as an expression.
It is possible (via some kind of flag) to avoid parsing _ <-- exp
outside of perform
. But this becomes quite complex and unreliable.
To record a particular expression patt <-- exp
in the AST, we use
the node
<:expr< let [(patt, exp)] in $lid:"<--"$ >>
If the construction _ <-- exp
is used by mistake, we get an error
message about an unbound identifier "<--
", which is our intention.
Known Issues
type t = T
and later use
perform T <-- T; ...
you get "Warning U: this match case is unused." which is not deserved. perform
((x, y, z) as tuple) <-- 1, 2, 3;
...
blows the extension out of the water. As a matter of fact, it is
not clear that this should be supported at all: patterns with
aliases are not "simple patterns" (see pa_o.ml). For example,
patterns with aliases cannot be used in fun pattern -> ...
. Thus,
at present monadic bindings should include only those patterns that
are permissible in fun
. And perhaps this is the optimal decision.rec ... <-- ...
" is not implemented completely.
It lacks support for a (user-specified) fix-point function. See
for example Erkök and Launchbury's "A Recursive do for Haskell".val failure_text : string
failure_text
This is the text that accompanies a match failure of a refutable
pattern.
val default_bind_expr : Camlp4.PreCast.Syntax.Ast.Loc.t -> Camlp4.PreCast.Syntax.Ast.expr
default_bind_expr _loc
This is the default expression for the "bind" function.
val default_failure_fun_expr : Camlp4.PreCast.Syntax.Ast.Loc.t -> Camlp4.PreCast.Syntax.Ast.expr
default_failure_fun_expr _loc
This is the expression for the default "failwith" function.
val default_failure_expr : Camlp4.PreCast.Syntax.Ast.Loc.t -> Camlp4.PreCast.Syntax.Ast.expr
default_failure_expr _loc
This is the expression for the default "failwith" function
(Pa_monad.default_failure_fun_expr
) after the
Pa_monad.failure_text
has been applied.
val exp_to_patt : Camlp4.PreCast.Syntax.Ast.Loc.t ->
Camlp4.PreCast.Syntax.Ast.expr -> Camlp4.PreCast.Syntax.Ast.patt
exp_to_patt _loc an_expression
Convert an_expression
to a (simple) pattern, if we "accidentally" parse
a pattern as an expression.
val recbinding_to_patt : Camlp4.PreCast.Syntax.Ast.Loc.t ->
Camlp4.PreCast.Syntax.Ast.rec_binding -> Camlp4.PreCast.Syntax.Ast.patt
recbinding_to_pattrec _loc an_exp_record
Convert an_exp_record
to a pattern matching a record.
val patt_to_exp : Camlp4.PreCast.Syntax.Ast.Loc.t ->
Camlp4.PreCast.Syntax.Ast.patt -> Camlp4.PreCast.Syntax.Ast.expr
patt_to_exp _loc a_pattern
Convert a_pattern
to an expression, if we must reuse it in a
different semantic position.
val patt_to_recbinding : Camlp4.PreCast.Syntax.Ast.Loc.t ->
Camlp4.PreCast.Syntax.Ast.patt -> Camlp4.PreCast.Syntax.Ast.rec_binding
patt_to_recbinding _loc a_pattern
Convert a_pattern
to a recursive binding.
val is_irrefutable_pattern : Camlp4.PreCast.Syntax.Ast.patt -> bool
is_irrefutable_pattern a_pattern
Answer whether a_pattern
is irrefutable.
Implementation Note: In OCaml 3.10.0 the function
Ast.is_irrefut_patt
is buggy. Thus, we must use our own
implementation.
val tuplify_expr : Camlp4.PreCast.Syntax.Ast.Loc.t ->
Camlp4.PreCast.Syntax.Ast.expr list -> Camlp4.PreCast.Syntax.Ast.expr
tuplify_expr _loc an_expression_list
Convert an_expression_list
to a tuple of expressions.
val tuplify_patt : Camlp4.PreCast.Syntax.Ast.Loc.t ->
Camlp4.PreCast.Syntax.Ast.patt list -> Camlp4.PreCast.Syntax.Ast.patt
tuplify_patt _loc a_pattern_list
Convert a_pattern_list
to a tuple of patterns.
val convert : Camlp4.PreCast.Syntax.Ast.Loc.t ->
Camlp4.PreCast.Syntax.Ast.expr ->
Camlp4.PreCast.Syntax.Ast.expr ->
Camlp4.PreCast.Syntax.Ast.expr -> Camlp4.PreCast.Syntax.Ast.expr
convert _loc a_perform_body a_bind_function a_fail_function
Convert all expressions of a_perform_body
inside perform
into
core OCaml. Use a_bind_function
as the monad's "bind"-function,
and a_fail_function
as the "failure"-function.
val qualify : Camlp4.PreCast.Syntax.Ast.Loc.t ->
Camlp4.PreCast.Syntax.Ast.ident ->
Camlp4.PreCast.Syntax.Ast.expr -> Camlp4.PreCast.Syntax.Ast.expr
qualify _loc a_module_ident a_function_expression
Append a_function_expression
to the module name given in
a_module_ident
, this is, qualify a_function_expression
by
a_module_ident
. Fail if a_module_ident
is not a valid
module name.