Home » forums » LtU Forum

Monads in C++

I have posted a blog about monads in C++. This is not just a proof of the concept that it's possible to implement monads in C++ -- that's been done before. This is the result of some actual C++ work on the Boost Proto library -- a library for implementating embedded domain-specific languages.

By Bartosz Milewski at 2011-07-11 21:00 | LtU Forum | previous forum topic | next forum topic | other blogs | 9917 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

"Great things come out of abusing C++."

Indeed! Thanks for the excellent essay.

By Charles Torre at Tue, 2011-07-12 01:05 | login or register to post comments

Monad is not the point

This blog article explains how to evaluate the AST of a simple language in the context of C++ metaprogramming: the AST is statically know, and we use template tricks to statically transform it to an objet that will dynamically compute the intended result.

As the AST may contain free variables, an environment needs to be passed at some point. It is not passed statically to the evaluation function, the evaluation returns function objects that dynamically accept an environment before computing the result.

In essence, what we have here is a denotational semantics for the static AST, given in term of C++ function objects (instead of the standard mathematical domains).

The author insists that what we have here is "a monad". Indeed, the passing around of the environment in an interpreter for a language for terms with free variables can be described as an instance of the Reader, or Environment, monad. But this passing around has been well-known since before the concept of monad was brought to functional programming, and I don't think the idea of monad has very much to do or to clarify here that wasn't already folklore.

For example, it has long been remarked that the "function objects" returned during the evaluation of a term are exactly the SKI combinators: K being used for constants (ignore the env.), I for variables (take the env. as a function and return it directly, so that the variable is applied to it), and S for applications (take the environment and apply to both appliands).

Of course, I understand that we all come with different point of views, and the knowledge of monads may very well have been enlightening to the author. However, I'm not sure this is the best way to explain the code to other people. I would expect the presentation of a simple evaluation parametrized by an environment, and then the remark that we can "currify" by evaluating to a environment-expecting function, to be enough and more to the point.

By gasche at Tue, 2011-07-12 05:40 | login or register to post comments

Proto is the point

I think you're missing the C++ aspect of the story. Runtime C++ is an imperative language and it hardly needs monads. Compile-time C++, in particular template metaprogramming (TMP), is a purely functional language with deep similarities to Haskell. But there is this boundary area where one part of the calculation can be done at compile-time while the other must be done at runtime. The Proto library was written this way and it's extremely difficult to understand. Casting it in terms of the Reader monad explains a lot of its complexity and provides theoretical foundations for its continued development. So I wasn't so much trying to explain monads to C++ programmers as trying to explain Proto to them and in the process found out that I can't do it without monads.

By Bartosz Milewski at Tue, 2011-07-12 22:52 | login or register to post comments

Reformulation

I tried to adapt the code given in your post to a simpler presentation inspired by the usual denotational semantics:

  ⟦Const c⟧ := λρ. c
  ⟦Var x⟧ := λρ. ρ(x)
  ⟦Plus e₁ e₂⟧ := λρ. ⟦e₁⟧ρ + ⟦e₂⟧ρ

Here is the core part:

template<class L, class R>
struct Compile<Plus<L, R>> {
    struct Compile<L> e1;
    struct Compile<R> e2;
    int operator()(Args args)
    {
        return (e1(args) + e2(args));
    }
};

(You can see the full code on hpaste.)

I'm under the impression that this way to present things is as simple as the Monad-based explanation, that is, that monads are actually not needed here. Is this solution in any way less satisfying that your monad-based metaprogram?

By gasche at Thu, 2011-07-14 07:53 | login or register to post comments

Monads vs Denotational Semantics

This approach looks very interesting and it definitely works for this example. I'd have to see if it can be generalized beyond it. In general, in Proto there is also a runtime representation of the parse tree that contains, for instance, the values of constants. I guess this tree would be passed as part of the environment.

Sometimes different semantics has to be provided for compound expressions, for instance [[Plus e (Times e e)]] (e.g., to effectively use a vector processor that can do three-operand calculations). How would that fit into denotational framework?

By Bartosz Milewski at Fri, 2011-07-15 23:24 | login or register to post comments