Module Pa_monad


module Pa_monad: sig .. end

Syntax Extension to Support Monads

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:

  1. bind (return x) f is identical to f x
  2. bind m return is identical to m
  3. bind (bind m f) g is identical to bind m (fun x -> bind (f x) g)
where 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. which is almost literally the grammar of the Haskell's "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: Any other pattern is refutable.

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
where The "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



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.