This post isn’t really about the Maybe Monad of course. It is more focused on the State Monad, but I have a weakness for alliteration.
What do
space suits
nuclear waste containers
romantic conquests
monsters
macros
containers
conversations
have in common? They’ve all been used as metaphors for monads.
Last time I looked, the Haskell wiki listed 29 tutorials on the subject, and that is where all these allusions come from.
Such a wealth of explanatory fauna demands its own (meta-)explanation. Maybe monads are so wildly popular that there is monadic gold rush to cash in on the monad education and training market. And yet, the long-awaited landmark tome, “Category Theory for Dummies in 21 days and 1001 nights” is nowhere to be found.
Tangent: There is of course, Benjamin Pierce's delightfully slim book on the topic which is as close to a gentle introduction as one can come.
Could it just be that people just have a hard time understanding monads? If so, what are the prospects of mass adoption? Or making Just(something) out of Nothing am I?
By now you realize that if monads were a stock, I’d be shorting it. I’m going to go get myself in a huge amount of trouble now, just as I did when I took a hideously pragmatic tack on continuations some years ago.
The most important practical contribution of monads in programming is, I believe, the fact that they provide a mechanism to interface pure functional programming to the impure dysfunctional world.
The thing is, you don’t really need them for that. Just use actors. Purely functional actors can interact with the stateful world, and this has been known since before Haskell was even conceived.
Tangent: Before you crucify me for being so narrow minded, pray consider the mitigating circumstance that I have used the words "practical" and "pure functional programming" in the same sentence. There are many who regard that, rather than my disrespectful attitude toward monads, as grounds for my institutionalization.
Some kind soul will doubtless point out to me how you can view actors as monads or some such. Be that as it may, it is beside the point. You can invent, build and most importantly, use, actors without ever mentioning monads. Carl Hewitt and his students did that decades ago.
Tangent: I have to say how amazing that is. Actors were first conceived by Hewitt in 1973(!), and Gul Agha's thesis has been around for 25 years. I firmly believe actors are the best answer to our concurrency problems, but that is for another post.
You can write an actor in a purely functional language, and have it send messages to file systems, databases or any other other stateful actor. Because the messages are sent asynchronously, you never see the answer in the same activation (aka turn) of the actor, so the fact that these actors are stateful and may give different answers to the same question at different times does not stain your precious snow white referential transparency with its vulgar impurity. This is pretty much what you do with a monad as well - you bury the stateful filth in a well marked shallow grave and whistle past it.
Of course, your troubles are by no means over. Actors or monads, the state is out there and you will have to reason about it somewhere. But better you reason about it in a well bounded shallow grave than in C.
What is important to me is that the notion of actors is intuitive (a pesky property of Dijkstra’s hated anthropomorphisms, like self) for many people. Yes, there are many varieties of actors and I have my preferences - but I’ll take any one of them over a sheaf of categories.
Speaking of those preferences, look at the E programming language (I often point at Mark Miller’s PhD thesis) or on AmbientTalk. I would like to have something similar in Newspeak (and in its hypothetical functional subsets, Avarice and Sloth).
Of course, there is much to be said for a programming culture that excludes anyone without at least the potential of a PhD. Indeed, if you can surround yourself with such people, you can do amazing things with just Java, C++ and Python (though they will still be more productive if they have the good taste to use something nicer). So perhaps the true value of monads lies in their exclusionary nature.
Nevertheless, there is more work to be done than some small, celebrated priesthood can or will do all by itself. There is real value in functional programming in some contexts, and it needs to integrate with stateful programming. Actors provide a model that is much easier for most humans to relate to.
My observations lead me to think that the Actor model is far from being intuitive, just like the asynchronous model is not intuitive for most developers (these two models have a lot of characteristics in common).
ReplyDeleteWe simply do not learn programming this way: we're used to calling a method and receiving a result right away. Waiting for a future and structuring your code around this new approach takes a lot of experience and a lot of unlearning.
For all these reasons and a few more, I really don't think the Actor model is the solution to our concurrency problem because it introduces many other problems of its own.
Hi Cedric,
ReplyDeleteConcurrency is never easy. Asynchrony, however, is very common is the real world and I think people can unlearn bad habits and use it successfully.
Models that use promise pipelining go some way at easing the difficulty with asynchronous communication.
They certainly beat locks and threads. We know that is too hard for people.
Anyway, this discussion is relevant to a separate, more detailed post on actors and concurrency. I'm expecting the monad police at my door any minute.
Cedric: not sure I buy "not intuitive". Scratch uses them to teachs kids programing quite effectively using the actor model. Don't confuse your highly trained conceptual framework with intuition.
ReplyDeleteFolklore has it that Steele, et al, invented Scheme as a simplification of what Hewitt was saying in order to gain an understanding.
ReplyDeleteWhen we did Rosette/ESS, i was very much in alignment with the actors model. In one phase of that work we even had Agha in as a consultant. After working with the language and model in commercial applications from data cleaning applications to financial, scheduling and provisioning applications, i felt it was not quite right.
Actors have a principal port, their mailbox. Coordinating activity off multiple ports was a common pattern. Fork-join was common pattern. These can be encoded just as any pattern can be encoded in any other functionally complete pattern. The point is to find workable models that capture enough of the patterns in the domain that a user is empowered and enabled.
i worked with pi-calculus for several years -- again, deploying it in commercial settings. This has many things going for it. It also has many desiderata.
Monads offer another abstraction. But, it's also only the beginning of the story. i'm now tending toward a view that enables the use of a differential calculus. Specifically, i believe that the notion of location -- whether it's an actor's mailbox or a port in the pi-calculus or a cell in a list -- needs to be given a much better more first class treatment in a notion of concurrent computation.
At a certain point i believe we will see that a unification of nominal and structural notions of computing will offer a higher level of abstraction in terms of the tools we can bring to bear. Mr Newton's calculus has this wonderful feature that it allows us to reason about aggregates of an apparently continuous nature. When we think about the volume of computing in modern web applications, this feels like a better approximation.
This comment has been removed by the author.
ReplyDelete@Kav: Actually, that's pretty much the definition of "intuitive", at least in its more modern interpretation. It has long been a not-so-well-kept secret of Interface Design that there is no such thing as "intuition". "Intuitive" == "familiar".
ReplyDeleteNote how I used "==" above to mean "is equal to". That meaning is probably intuitive to anyone reading this blog. Unless, of course, they are mathematicians or Prolog or Erlang programmers, in which case it's not.
But when a couple of Lispy guys wanted to implement actors, they found that actors were just lambdas after all, and their sequel to Planner (proto-Prolog) and Conniver (the Hairy Control Structure) was plain old Lisp after all, but with a new twist.
ReplyDeleteMonads are windowless.
Isn't this something of a straw-man? You claim that monads are only useful for interfacing a pure functional language with foreign code, then say that this particular story is better served with actors.
ReplyDeleteIgnoring the fact that monads are just one abstraction among many (that is, I don't think experienced Haskellers would claim that monads are the best abstraction for every foreign code boundary, and are in many cases are too strong for the properties you need), how would you model the other non-FFI-related phenomenon for which monads are currently used? Would you model ambiguous-choice logical computations in terms of actors, for example? Wouldn't you end up implementing something that's basically a half-specified, bug-ridden instance of a monad?
Actually, I/O has been modeled by viewing a pure computation as a function from an input stream of I/O results to an output stream of I/O actions. This seems to be similar, at least at a high level, to the idea of handling I/O with actors. My understanding is that it lost out because it turned out to be quite unnatural to work with, and rather hopeless for beginners to do things with. Monadic I/O, on the other hand, pretty much works exactly as people expect.
ReplyDeleteWhere monads get a little tricky for beginners is when you want to invent your own monads to capture different aspects of the computational environment. So if the argument is that the confusion for beginners upon seeing monads is unnecessary, I'd like to see some examples using something other than I/O. I/O is the easy case; there are already plenty of sources that present monadic I/O without using the word "monad" at all, and it's pretty straight-forward.
There is no monad police.
ReplyDeleteWhat is a monad in one sentence?
ReplyDeleteI don't know what you computer science folk are talking about, but a monad in philosophy is simply: a simple object (meaning indivisible) that causally interacts with other objects by observing its environment. It is contrasted to other (more standard) views of objects that act upon other objects to make them move. Monads can't operate on other objects, they can only operate on themselves.
For more information google "Leibniz"
Thanks, Dan, that really clarifies matters!
ReplyDelete"The most important practical contribution of monads in programming is, I
ReplyDeletebelieve, the fact that they provide a mechanism to interface pure functional
programming to the impure dysfunctional world."
Nothing could be further from the truth.
First, monads have nothing to do with "interfacing pure functional programming
to the impure world." You're probably referring to Haskell here, which has a
type constructor value for doing this, named IO. The IO type constructor just
happens to be a monad, as well as many *many* other things.
The relationship between monads and IO is exactly the relationship between a
List.reverse function and a Banana data type. Note that you can reverse a list
of Bananas, but there is otherwise no other relationship -- they are completely
disconnected. This "relationship" does not permit one to say that List.reverse
is related to any specific data type, just like the fact that IO is a monad does
not invite one to do same.
Next, this IO value (not monads; remember, completely disconnected) doesn't
allow "interfacing pure functional programming to the impure world." In fact,
nothing does. Rather, it tags World->World effects and nothing more. Simply, the
type system puts a constraint on an expression just like it does for any other
expression in a statically-typed language. There is no unification of one thing
with another "world." Again, it's a type system constraint, no different to a
type system that might disallow an expression of the form 7 + "a".
Finally, even if none of the above were true, there is an enormous value of
monads well outside of everything being discussed. I am not prepared to put a
monad tutorial in this little box, but I have tried to dispel all of the myths
(including all of those you purport) before and explain in detail (without
metaphors) what this apparently-but-not-really mysterious concept is all about.
http://blog.tmorris.net/what-does-monad-mean
Please be careful.
Many people misread the post.
ReplyDeleteFor example, note that If you want to use a monad for anything else, you can still do so. I did *not* say monads were only used for IO (or effects). I do claim that is their most significant *practical* aspect wrt to programming languages. It's all in the post.
Likewise I did not say that every use of a monad should be replaced by an actor.
Chris: I'm well aware of IO being modeled as functions from streams to streams, and that can be awkward. While you could view actors doing something similar with event streams, in practice it is very different I think.
Gilad,
ReplyDeleteSure, without more details on what actor-based I/O would actually look like, it's difficult to say much. So I just mentioned a high-level similarity between the models.
If you want to get more specific, could I suggest you provide an example? For example, http://research.microsoft.com/en-us/um/people/simonpj/papers/history-of-haskell/history.pdf gives examples of a really simple I/O based task (prompt for a file name, and either print its contents, or an error message if it doesn't exist) using stream-based I/O, continuations, monads without sugar, and monads with sugar. How would you do this in your ideal language with actor-based I/O?
Chris,
ReplyDeleteI aim to do more than just examples. The goal is to implement it. However, examples would be a nice start, and might find their way into a future post (or several) focused on actors (rather than the state monad).
I fully expect IO to be asynchronous, and I would want a working GUI built around that.
On @leithaus's idea that location deserves a first-class treatment, I'd like to refresh the idea from David R. Jefferson's Virtual Time that *invocations* have both a space coordinate (the address of the procedure bein invoked) and a time coordinate (the virtual time of the invocation). Objects in the Time Warp Operating System (a mechanization of Virtual Time) are overtly stateful, with the states being also stamped with virtual times, and objects being allowed only to examine their latest, earlier state vector on an invocation. This theory was implemented and proved in practice to produce high speedups under optimistic execution, such as 60x on 84 processors for suitable applications like discrete-event simulations. The symmetries between *locations* (space coordinates) and *times* have obvious relativistic undertones and have never been fully explored theoretically. However, these intuitions are strongly in line with @leithaus's ideas and I think it would be interesting to take another look at Virtual Time in the light of monadic (or anti-monadic, actor-ish :) statefulness.
ReplyDelete> I do claim that is their most significant *practical* aspect wrt to programming languages.
ReplyDeleteIn Haskell, Monad is an abstract interface. IMHO it's a category error to judge an abstract interface with respect to a single instance of that interface. Monads, like other abstract interfaces, can only be judged by virtue of their use with respect to multiple types sharing that interface.
Haskell uses the type "IO a" to represent an I/O action returning a value of type a. IO is not terribly difficult to use. The difference between I/O actions and other values is quite similar to the distinction made in many other languages (eg. expressions vs. statements) and is quite familiar to many programmers. IO can be used with no knowledge of monads in the same way that addition can be used by people with no knowledge of group theory. IO in fact predates Monads.
Monad is a powerful multi-purpose abstract interface. Its uses are so diverse it can be tricky to see the common features, and to many that hinders understanding. That is why there are so many tutorials on the subject. If you examine some of the tutorials you mention you'll see that the metaphors you mentioned are precisely attempts to find those common features. If you're interested in one particular instance of the Monad interface, discussing the difficulty of understanding the diversity of other applications is quite simply irrelevant. That's like saying that addition is difficult because there are people who have trouble understanding what it is that all groups share.
If you wish to make a comparison wrt Haskell, say, it would be more useful to compare IO and Actors.
The most significant practical application of monads with respect to programming languages is a common interface shared by concepts such as I/O, state, non-determinism and exceptions. In Haskell this has allowed the development of a single specialised sublanguage ("do-notation") useful for all of these applications as well as a great wealth of practically useful polymorphic functions that can be applied to all of these domains. If the most significant application of Monads were to enable I/O they would have withered away long ago. They would be nothing more than clutter in the interface to the IO type.
"I do claim that is their most significant *practical* aspect wrt to programming languages. It's all in the post."
ReplyDeleteGilad,
You're missing the point, big time. I'm not sure reiterating myself is going to help.
I strongly urge you to come to understand what monad means, then apply introspection.
I hope this will help.
I think the use of monads for IO is just a small fraction of what monads are used for in Haskell. It's certainly true for my code.
ReplyDeleteHaskell used to have a request-response type IO that's more like actors. But it was done wrong, so it was very hard to use. O'Haskell does it right.
The notion of a group is a powerful abstraction to capture something essential about symmetry. To say that groups might not matter might be true for square dancers or knitters or possibly even crystallographers -- each of which has an on-going and embodied relationship to operations of symmetry. Still, the abstraction of a group is a potent idea that allows one to enter into a deep, effective and actionable relationship to symmetry. Likewise a monad is a powerful abstraction that captures an appropriately parametric form of composition. It turns out that humans -- from time immemorial -- have a blindspot regarding composition. Quantum mechanics -- not compositional. General relativity -- not compositional. i once had Leslie Lamport sit across from me and tell me compositionality was -- at the end of the day -- fundamentally not important to the design and verification of computational systems and solutions. Yet, over and over again we see that when it comes time to scale our understanding of complex systems to something effective and actionable, compositionality is the only game in town. Having a range of tools, including the notion of monad, to approach this elusive idea of compositionality is in our best interest. That it takes people a while to grasp the idea and its importance is -- in my opinion -- not a reflection of the value of the idea to human endeavor. As i said, human's have a blindspot when it comes to composition. Upon reception of his Nobel, Feynman was asked by a member of the press if he could summarize his work on QED. His response was to the effect that if he could relate it in 5 or 10 mins, it probably wasn't worth a Nobel. While i think that this might mislead us regarding the characteristics of deep simplicity, there's a grain of truth to Feynman's quip. Getting to the value of a profound and profoundly simple idea may take many a long time. That doesn't mean it's not worth the effort.
ReplyDelete@Dan: Monads in category theory and monads from Leibnizian monadology are completely unrelated.
ReplyDeleteThey just happen to grab the same name.
One was named because a category theorist wanted to replace the name 'triple' which was in use throughout the category theory community, and had a more general concept that he wanted to call 'operad', because it dealt with operations and his mother was an opera singer.
The other was basically an indivisible unit of thought in a calculus Leibniz wanted to invent to provide unambiguous political discourse in his day job as a politician. This was long before the incompleteness theorem showed this to be a rather impossible exercise to complete.
They literally have nothing to do with one another.
sigfpe & Tony:
ReplyDeleteThanks for trying to communicate. I do understand that monads have varying uses. I may be underestimating their importance. I may also have a very different notion of what "practical" means.
The mere fact that many things can be viewed as monads is not in itself practical, even if is neat or even beautiful.
The abstractions of category theory are very general and have induced waves of enthusiasm in the programming language world in the past. The question is how much leverage they give you. I am a bit skeptical on that point.
Some compelling examples of useful libraries that work on monads might help here.
Of course, what I find compelling may not be what you find compelling. But, if you convince me, than the post is worthwhile, because I'll learn something I had overlooked. And you will have found an argument that simple minded souls like myself appreciate - which might help you communicate with lots of other people.
Leithaus & Breaking Change.
ReplyDeleteI find your comments very interesting. I'm not saying that actors are the end of progress. I find them much more attractive than the alternatives.
On other points: I have no intention of slighting category theory (or any mathematical theory). But between that and practical language design lies a gap.
And finally - yes, compositionality is key. And algebra is strong on that, agreed.
I fully expect IO to be asynchronous, and I would want a working GUI built around that
ReplyDeleteHmm, sounds like Newspeak will converge upon Newsqueak!
cool.
I'm expecting the monad police at my door any minute.
Well you've repeated the word "monad" five times into a mirror at midnight, and the "monad police" sure have arrived!
"Some compelling examples of useful libraries that work on monads might help here."
ReplyDeleteI started the Scalaz project in 2007. Scala, the programming language, has a rather rare type system feature called higher-order polymorphism (aka higher-kinds). Higher-order polymorphism is required to implement the general monad interface. To demonstrate the rarity, note that no .NET languages have higher-order polymorphism and neither do any of the more "common" programming languages.
I started Scalaz because I was writing a commercial application and observed that the Scala/Java libraries were totally inadequate for anything useful at all. In particular, they were missing all the abstractions from category theory that happen to be extremely useful in practical every-day programming, so I wrote them.
Most of my work today is in Haskell, but just recently I am using Scala again. Again, this type system feature and all the abstractions it permits have come up, and as I'd expect.
They come up all the time. I would even be prepared to put a very disproportionate wager on the fact that they come up in *your* every-day programming all the time too. That is to say, they do have enormous practical application, regardless of your domain, and the only measurement you are making is simply out of your own unawareness, rather than anything concrete and comparable. This is likely due to lack of practice. At least, this is often the case when misinformation is abound.
I'm always willing to help change that.
I think you'd have a considerable shift of mind if you were to have a deeper understanding of the topic at hand.
By the way, Scalaz has an actor implementation.
ReplyDeleteSo does Functional Java (written in pure Java), which I also authored.
Note the significant additional utility provided by (you guessed it) monads (and other concepts from CT) in the Scala version.
Hi Tony,
ReplyDeleteYes, I noticed you have actors in ScalaZ.
The post noted that someone would point out the actor-monad connection, and several people have.
I like the promise pipelining; don't like the typed messages, but that is yet another religious war.
Of course promise pipelining and such have come up before without reference to CT.
You clearly see CT as a useful conceptual framework to guide your software design. In contrast, I believe that the functional community gives way too much weight to this stuff. I'm all for good compositional design, but I think that adhering strictly to these mathematical constructions does not produce the most workable designs for people to use.
The actor library would be one example where I might prefer a different design.
As another example, when I wrote my own parser combinator library, I decided that adhering to monadic laws was actually not the behavior I wanted.
All this is by way of trying to explain why I think that monads and CT are overrated as a tool for programming and programming languages.
@Gilad,
ReplyDeleteAn example of a type that makes good use of the Monad interface is the List type. The Monad interface gives an elegant way to perform, and generalise list comprehension. Among other things, it gives a nice way to implement highly readable combinatorial search code, but it's also generally useful for collecting a flat list of information from various kinds of nested data structure. The very same polymorphic functions that are useful when working with IO turn out to be useful with combinatorial search even though they have seemingly quite different semantics. This is something that is very practically useful and gives great code reusability. By insisting on working through the Monad interface, we can hide the details of exactly how the combinatorial generation takes place. This gives very nice separation of concerns allowing us to swap between depth-first, or best-first, or other types of search while leaving the consumer of search results unchanged.
Another place where monads give a big payoff is when working with embedded DSLs. ASTs for DSLs often have a natural Monad structure and the usual operations on Monads combine these ASTs in exactly the way you'd expect to chain operations in a variety of DSLs. It's no surprise that there are so many Haskell EDSL projects. In fact, IO itself can be treated as an embedded imperative DSL for I/O and the List monad gives a very simple prolog-like embedded DSL (offering backtracking, but not unification).
In each of these cases, the interface presented to the end user, via do-notation, is remarkably straightforward to use, gives readable code, and certainly requires no use of category theory.
This has been a great thread! Thanks Gilad, Dan, Brian (i spotted you!), and everyone else for edifying and enlightening me with your wisdom and experience! On the humorous side of things, i was recently rereading Rydeheard and Burstall's Computational Category Theory -- which was written before the Moggi and Wadler papers -- and was amused to see them focus almost exclusively on adjunctions and make a cursory remark that monads constituted a related way to package up the information. Talk about missed opportunities... or could it be that we really haven't understood the value of adjunctions? What is the meaning of Beck's Theorem, anyway?
ReplyDelete@sigfpe -- i like your example. i notice myself constantly impatient about the fact that the folklore that monads give an excellent presentation of algebras and hence all algebraic data types, and all EBNF-based grammars hasn't really bubbled up through the culture, yet. (i'm also impatient that the correspondence of grammars and structural equivalence with generators and relations hasn't generally been grokked; or that the penny hasn't dropped that grammars are our most practical way of specifying data types and domain equations... -- conditions have arranged themselves to give me lots of opportunity to practice patience...)
ReplyDeleteA really, really practical example i've been thinking a lot about recently is the Peyton-Jones/Dybvig/Sabry presentation of delimited continuations. Their paper is nearly perfect in construction. Everybody knows the trade-offs of CPS vs stack frame manipulation approaches to continuations. That's a practical problem and given the practical impetus behind webservers like tornada, deft and loft it's very natural to want to explore continuations frameworks. The P/D/S presentation shows you can use monads as an abstract interface for delimited continuations and then code up to the interface on one side and implement using either strategy on the other. If that's not practical, i don't know what is.
To see how this fits into a web framework, delimited continuations allow you to uniformly build "callback streams" over an incoming packet/message stream (like an HTTP request stream or a stream of AMQP messages). This allows the construction of a server using the following (compositional) code fragment
for( msg <- beginService() ) {
// msg handling code here
}
with all the session, state and concurrency hidden behind this monadic interface. Currently, my commercial clients are coding to this style and loving it. To me, that's the essence of practicality.
More generally, this extends to a join pattern
for( msg1 <- strm1; ...; msgk <- strmk if filter( msg1, ..., msgk ) ) {
// complex event handling goes here
}
Again, my clients like this style, but your mileage may vary.
"I do claim that is their most significant *practical* aspect wrt to programming languages."
ReplyDeleteYou don't seem to be referring to Monads in general, just Haskell's choice of modelling IO as a monad. One's choice of how to model IO (monadic, actors, not differentiated at all) is rather orthogonal to the whole idea of monads.
In Scala IO is not differentiated by the type system, and yet monads play a very significant part in the standard library. Lists, Options, most any operation on a structure you can think of. It's just a name for a pattern that is more likely than not present in any language. You don't have to give a name to the pattern or even be aware of it to use it.
Actors in the next version of scalaz are actually an implementation of an Observable type, modeled loosely off of the .NET reactive framework.
ReplyDeleteIn this framework, Observables are monads, Actors are monads, Futures form a monad.
This give you a coherent set of combinators for programming with all three, and I doubt you would argue that events, actors or future values are useless in "real world programming".
In Haskell (and in Scala through scalaz) large numbers of combinators merely require that you want to work with a monad. When you want to work with the contents of any 'Traversable' container you are able just use any action in any monad. This abstraction is powerful. Because I'm not writing n*m traversals, I'm writing one traversal for each container, and if the container is an ADT, the compiler can even figure it out for me.
This gives a common framework of combinators for programming with a wide array of different containers in a wide array of different contexts.
Monads are useful precisely because there are so many of them. When I'm working with things that don't remotely involve side-effects, I use monads, simply because there are a large suite of combinators for how to work with various containers that merely need the properties of a monad, or even the slightly less restrictive and hence yet more plentiful concept of an Applicative (which just happens to be the old-school concept of a context-free attribute grammar reified into functional programming form, whereas a monad is just enough to add context sensitivity).
In Haskell, they form a set of 'semantics a la carte'. Monad transformers are nice because you can extend your traversal with fair backtracking, state, logging, an environment for context, continuation capture, whether or not you are using an accumulating parameter to accumulate mappings over the container, etc. and none of your containers or other data structures need care which such extensions you think of.
This factors out a wide array of competing concerns from your code.
You could make up a name for the same concept. You could derive semantics for your newfangled name. Heck, they did it in F# with 'Workflows' trying to make them first order and purely syntactic, but the result is a poorly specified ad hoc mess. "Monads aren't important", but they are a useful tool for factoring out code, even in the absence of side-effects, and they happen to have been beaten on by large numbers of very smart mathematicians since around the time that LISP was invented, so why not piggyback on their research. Given the timeline, the alternative seems to run afoul of a mathematical analog to Greenspun's tenth rule. =)
Leif says it succinctly. Thanks.
ReplyDeleteFunctional Java includes monadic operations, but not the general interface (the type system disallows it, ergo repetition).
Grep for "bind." You'll also find other abstractions in there.
Yes, these are extremely useful.
I just checked back and noticed you'd asked for examples of practical monads. Let me give a few that are more on the "practical" side of being practical.
ReplyDeleteParsec is a Haskell library for parsing. It makes use of the monad interface, and as a result, it's a piece of cake to write parsers that collect values from subexpressions in a really obvious way. You don't have to explicitly write down all the plumbing for backtracking alternation and mix it in with the semantic part of what you're doing.
Haskell has three major web application frameworks. All three of them define monads that capture things you often want to do in a request/response framework (for example, you often want to have the request available to you without explicitly passing it around, or abort early with a redirect response, or add cookies to the eventual output even if you haven't started writing it yet; all of these are encapsulated nicely in the monad provided by the framework).
I also wrote a continuation-based framework to run on top of two of them, which makes writing short stateful interactions (for example, guided troubleshooting for users with decision trees, where a user is answering questions and trying things and providing feedback as you go) a piece of cake. That defines another monad which makes specifying interactions that span several requests look just like ordinary procedural programming, even though the logic is actually rather inverted in request handlers, and makes heavy use of continuations.
The hint package for Haskell lets you work with code at runtime through an API to the compiler, enabling a lot of really nice things (for example, one of the web application frameworks I mentioned uses it so you don't have to recompile your code to test a change). But working with the Haskell compiler requires a LOT of context that you'd have to keep around. Fortunately, hint provides a monad that handles it for you, so it's transparent, and there when you need it.
These sorts of things are commonplace, everyday tasks in the Haskell world, and all of them use monads. Monads provide an eminently practical and useful way (among other things) to replace global or shared state with less error-prone, more thread-safe, and functional alternatives, as well as letting you customize control flow, error handling, and lots more. Sure, there's more unusual and mind-bending stuff going on too; but if that seems impractical, ignore it and look at the pervasive and more mundane ways monads get used all the time.
Well, plenty of Haskell/Monad advocates have already commented, so I thought I should speak up to advocate for Actors. I don't expect to convince anyone from the Monad camp, but you are not alone in believing in the value of managing concurrency with actors.
ReplyDeleteI've been exploring various aspects of actor-based solutions for some time now. I think the Same Fringe Problem is a particularly good example. In solving "same fringe" I also explore the generation of infinite streams -- something the Haskell folks like to do with lazy evaluation.
I believe that each paradigm has it applications, and there is certainly a lot of overlap between them. However, it seems that Actors have not received as much attention as they deserve (although I suppose Actors always feel that way).
Dale,
ReplyDeleteI didn't think this post was about managing concurrency at all. It was rather about whether actors can substitute for the role Haskell's IO monad plays in managing the boundary between purely functional code and the stateful world. The answer, I think, and clearly they can; but it seems to some of us rather unpleasant to think of programming that way. But I'd be quite willing to be proven wrong.
The second point was whether monads have much use beyond the IO monad and its somewhat special role in Haskell serving as that boundary. I've tried to clarify that they do.
None of this had much to do with managing concurrency. When it comes to managing concurrency, I also think that actors and other message-passing models have a lot to recommend them. In case it wasn't clear, the conversation about monads wasn't an insult to actors as a concurrency model. It came about because this post was not about concurrency at all, but rather about what role monads play in programming.
@Dale
ReplyDeleteI too spend much of my time exploring how to effectively leverage actors, but I don't think you'll find any real world Erlang advocate that will advocate making anything that could be an actor into an actor. There comes a point at which you need to stop subdividing tasks into actors. However, there is no harm in observing that a structure is a monad and marking it as such. This pays no runtime cost.
Sending a message on a channel usually costs at least a compare-and-swap or memory fence. This limits their applicability to things above a certain granularity.
Actors carry some heavyweight baggage in the form of their message queue. This has an operational cost, because you can either live in the Erlang-style world where these things carry around potentially unbounded numbers of messages, whereupon the whole system can come crashing down upon your ears when the queues get out of whack if your consumers can't keep up with your producers or you can live in the Singularity-style world where they have to be composed out of 2-endpoint channels with some affine type system managing the endpoints. Living in a world full of erlang-style actors requires you to build up a complicated series of tools for dealing with how to kill and reset the system when things inevitably go out of whack. If you look at Erlang's OTP, much of it is devoted to this very problem. (This _can_ be perceived as a good thing. It forces you to think about how to make a distributed system robust against a wide-array of failures.)
I happen to enjoy using these abstractions quite a bit, but even in Erlang or Scala actors, you wind up passing around lists and other concrete data structures, because it isn't worth constructing those queues _everywhere_.
Actors and monads are not mutually exclusive. As I mentioned above, there happens to be a monad for talking about observing message channels. In this case the monad just provides you with the imperative-seeming block in which you are aggregating messages from different channels.
I don't see that it takes anything away from an actor to note that this relationship exists and to bolt it on top, permitting actors to take advantage of all of the machinery that monads make available elsewhere.
Saying something is a monad just helps factor out concerns.
Chris,
ReplyDeleteYour last comment summarizes things nicely. Thanks to all who have commented - even those who mistook my intent, or those who assume I'm totally ignorant or whatever :-)
If there is such a thing as monad police, they're definitely here.
ReplyDeleteIMHO, a big part of why monads are so common is that they're a particularly useful pattern for programming. That is, a monad is a calculation which exists in a context and is able branch based upon examination of intermediate results.
This pattern didn't come into existence as an application of monads, rather "monad" is a name applied to the concept. Most of the examples given didn't come about because they're monads, and I seriously doubt that anyone will create anything useful and specific by starting from "Let's invent a new monad today". However, by codifying a structure, Monads provide a generic interface and a few extremely useful tools (such as Control.Monad in Haskell)
I see the power of monads being that, as a very high-level abstraction, they allow the user to quickly gain access to any new system/feature/computation/data which meets the necessary criteria. The common notation helps too.
What's impractical is that this advantage is only available to those who really understand monads, which is probably only a small percentage of programmers. Perhaps even a minority of Haskell programmers. By the time Monads are useful, you've internalized the underlying principles to such a degree that the existence of a Monad interface hardly matters.
While we're cataloguing prior art, there is Peter Landin's 1965 paper.
ReplyDelete"If there is such a thing as monad police, they're definitely here."
ReplyDeleteMonad Misunderstanding Police :)
It seems to be a popular trend to wildly misunderstand the concept. Luckily we have the enforcers!
John:
ReplyDeleteNicely put.
Tony: That was a large part of my point - the concept is very difficult for most people to understand. This is not a feature. If you have difficulty conveying how wonderful it is to me, do you really expect to make it standard practice for most programmers?
Gilad,
ReplyDeleteI have no ambition to make monad concept available to most programmers. I only object to naive beginners being fed misinformation. The curious deserve better.
I would have no trouble explaining it to you and I explain it regularly and with success. Note that I didn't even try to explain it to you, merely pointed out the errors for the purpose of observers (who unfortunately see these same errors in other places, and so on it goes). The difficulty in teaching is understanding generalisation and abstraction, then application (pattern recognition), not the monad concept specifically.
I take it you didn't see my actual attempt to explain this specific concept, which gets far more attention than it deserves, merely because of prolific mythology.
Tony:
ReplyDeleteI will look at your tutorial, as I have looked at many others in the past. I am still searching for a good way to describe the issue.
I do agree the topic gets more attention than it deserves. Beyond that we should agree to disagree.
I think the topic has been beaten to death here, and I intend to let it rest for a while. Who knows, maybe I'll write my own monad tutorial some day -;
Dear Gilad,
ReplyDeleteI do not think monads have really seen much trouble with adoption. People use them unwittingly all the time, you could point to objects that generate random numbers or read from a file line by line, for example. The use of the name "monad" in haskell was more a consequence of having typeclasses available to talk about monads in general.
Typeclasses can be nice for polymorphism. For example, look at this.
untilM :: (Monad m) => (a -> Bool) -> m a -> m a
untilM test m = liftM test m >>= \finished -> if finished then m else untilM p m
In a sense this acts like a filter on monads. IE:
untilM (not . null . take 5) (putStr "Enter more than 5 characters: " >> getStrLn)
builds an IO action using untilM and >> out of putStr and getStrLn, even though untilM and >> were defined without having to know anything about how IO actually works.
Another example, using MonadRandom, would be:
untilM even (getRandomR(1,100))
Which would return an even random number between 1 and 100 (of course, this is contrived and there are better ways to do this, such as "liftM (*2) (getRandomR(1,50))".)
You could of course do similar things with message passing, although it strikes me it'll be harder to check that what you are doing is correct at compile time. This may or may not be a problem depending on your priorities. A lot of languages do not even make a distinction between run time and compile time.
So if you intend to work with something like typeclasses, monads make a useful typeclass, and you do not actually lose anything since you can make something a monad using an instance without breaking any of the original calling code (in other words, there is no trade-off here, you get the monads for free).
Monads really only make sense as a thing to give special treatment to when you have typeclasses to play with. If you do, you may as well, since there aren't any downsides to allowing people to think of your thing as a monad. For example, if you need unsafePerformIO or other things specific to IO that can't be explained by the IO monad, they're still available to you. The IO monad just exposes some of IO's functionality in a predictable way.
Basically, whether or not monads matter largely depends on the features of the programming language you are talking about.
Some researchers put forth the thesis that monads could help with concurrency. At this point, it looks like their thesis has failed.
ReplyDeleteThe Actor model (e.g. see ActorScript(TM) extension of C sharp (TM), Java(TM), and Objective C(TM)) is a better foundation for concurrency than monads.
@Gilad,
ReplyDeleteAside from the practical examples others have mentioned, C#'s LINQ is the Set monad. Furthermore, all query languages can be expressed as comprehension over the Set monad. And then any arbitrary query nested to any depth can be flattened/optimized using automatic rewriting rules. This paper has details: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.1175
I do not agree to disagree. I simply refuse. You are very wrong. You are invited to change this. "Agreeing to disagree" is just a plea for permission to continue talking rubbish.
ReplyDelete