Monads and Intensionality – Lucid is not an aberration
billwadge.wordpress.com
billwadge.wordpress.com
> This is my best shot. What I don’t understand is where the side effect comes in. The other monads I’ve discussed don’t produce side effects.
This is putting the cart before the horse. The goal is to have a sensible way of modelling computations that have side effects, to be able to talk even slightly denotationally about (side-effecting) computations. An element of D* is a side-effecting computation that produces a value that's an element of D; this isn't something that comes out of the monad model but something we put into it, because the point of the exercise is to talk about side-effecting computations that produce values.
The point is that such computations are monads in a very natural way: d* is the value d (or, equivalently - in a very concrete sense in Haskell, since it's a lazy language - a computation without side effects that produces the value d), f* is composition with the pure computation f (so f* (x) has the same side effects as x: it's the computation that consists of executing x and then applying f to its result). The sum of two elements in D* x + y is executing x, then executing y, then summing their results (and thus its side effects are the side effects of x followed by the side effects of y), and the collapse from D* * to D* is that we execute a computation and then execute the resulting computation.
The advantage of this is the same as the advantage of modelling anything else as a monad: we get a formal representation of side-effecting computations that has some useful algebraic properties. The monad is a means for working with the effect we want to work with, whether that effect is partiality, nondeterminism, streaming, or general side effects. We shouldn't be surprised that side effects come out of using a monadic model of side effects, any more than we should be surprised that nondeterminism comes out of using a monadic model of nondeterminism.
I personally fall into the (a) camp, since I work on compilers and formal verification. Monads are mathematically useful when trying to define the semantics of a programming language. This mathematical usefulness translates into useful API design [which I personally see as the hallmark of all functional programming techniques].
On the other hand, if one does not care about or want to abstract over a very generic notion of a side-effect, yes, monads are useless. You can go your entire life without needing to know what one is. And that's okay.
Why does side (a) side feel the need to pressure side (b) into learning all of their mathematical tools? Why does side (b) see side (a) as "being difficult" or "being obtuse on purpose"?
As far as I can tell, the two groups do not even share the same axioms about how we should build and reason about programs. Monads are a red herring.
- Real world example of where monads are used to reason about programs: Inside the VE-LLVM codebase, which provides a formal model of LLVM in Coq to prove certain properties of certain algorithms used with LLVM corred, a monad is used: https://github.com/vellvm/vellvm-legacy/blob/e4c22d795974ba7.... Much of the reasoning around sequential side-effecting semantics is phrased in this language.
From our side of the fence, FP concepts appear dense and obtuse the way they're currently explained. Until that changes, we'll remain divided.
Here's the first sentence in the documentation for Java's Comparable interface: "This interface imposes a total ordering on the objects of each class that implements it."
This assumes people know what a total ordering is. Total ordering is an abstract mathematical concept, not really more or less abstract than a monad. Clearly then, people don't have problems grasping abstract concepts. They just learn the definition and possibly bunch of examples and they're done.
I think the real divide happens because people in programming praxis are simply skeptical to the claim that monads are a useful abstract concept to learn and use in programming. Many years ago, some of them probably thought they don't need to know what a total ordering is.
I don't think anything can be done with the skepticism other than either take the claim at a face value, and accept that monads are a useful concept, or verify that claim by learning Haskell for instance.
"If you can't explain it simply, you don't know it well enough"
- Albert Einstein
I think the crux is explaining how the abstraction is useful. The Comparable interface doc explains it in the very next sentence: Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort). Every Java programmer can understand this and see its purpose
The difference is that in Java and most other languages abstract mathematical concepts are treated as means to an end, not a goal in itself.
> So what is the IO monad, the most famous of them all?
IO is the State monad where the state is the entire universe.
Maybe in the early days, but that doesn't really describe how it works these days (in particular, async exceptions). In practice it's been used as a "sin bin" type for any side effect that we don't know how to model nicely.
I do have a bit of a negative attitude towards evangelists who expect people to be impressed by ideas whose significance they routinely fail to communicate. Functional programming enthusiasts seem to really want the rest of us to care about monads but never quite get around to telling us why, and that's on them.
I get that, say, Result types and List types both can wrap objects and both compose with themselves in some nice ways when they do. And as a mathematically curious person, I think this is a fun observation. But since there is very little overlap in their practical use cases I don't understand why having a formal model for that commonality is so important.
Since you said it comes up often, do you have an example of a time where you reached a solution faster by recognizing that it should be monad-shaped?
* Gathering statistics (multiple different cases)
* Authentication
* Async pipelines (I found iteratees much easier to learn than "reactive streams" because they're just monads)
Essentially any time you find yourself with a "cross-cutting concern", something you'd be tempted to use an "aspect" or "decorator" for, you probably want to use a monad. And there's a lot of complicated language features that you can just remove (or reduce to syntax sugar) if your language has monads instead: https://philipnilsson.github.io/Badness10k/escaping-hell-wit...
Note, I'm not claiming that these problems are not solved by monads. I'm arguing that the article you showed gives me no information on how really complicated problems are actually solved, it just shows a neat bit of syntax sugars that works on a few toy problems (again, that's what's shown, not claiming that this is all that 'do' is).
It's not just syntactic - the different cases genuinely do implement a common interface.
> Partial because it does not handle errors in the continuation example
Nor does the non-monad version, so it's a fair comparison.
> simplistic because it only works at the function level, it's not clear how this would look like when 'distributed' through a large code base, like cross-cutting concerns typically are. Not to mention, it's not clear how to compose all of these separate solutions - how will the do notation work if you have a list of continuations that can each return optional values that return errors if something is not authenticated?
Sure, but again, a problem that exists even more strongly if these are implemented as (non-monad) language features (e.g. if my language has both continuations and exceptions, what happens when some continuation-based code throws an exception).
The point is that you can get rid of a whole bunch of complex language features and language keywords, and write everything in terms of plain functions and values (in particular, the result is that you can refactor fearlessly because everything follows the normal rules of the language). You don't have to look at anything large scale to see the benefit of that.
Do notation is a syntactic solution, it is not an object of the runtime.
> Nor does the non-monad version, so it's a fair comparison.
The initial version does explicitly handle errors. The async/await based version also handles errors (any exceptions thrown by intermediate functions will be thrown by whoever is trying to use the results). What will the do-notation continuation version do with any errors returned by the intermediate functions?
> Sure, but again, a problem that exists even more strongly if these are implemented as (non-monad) language features (e.g. if my language has both continuations and exceptions, what happens when some continuation-based code throws an exception).
Not really - it is usually very clear how exceptions integrate with other control flow features such as continuations or, much more easily, promises or async/await (full continuations a la scheme call/cc happen to not work with exceptions, but they break any other control flow feature anyway, so that's not very surprising).
> The point is that you can get rid of a whole bunch of complex language features and language keywords, and write everything in terms of plain functions and values (in particular, the result is that you can refactor fearlessly because everything follows the normal rules of the language). You don't have to look at anything large scale to see the benefit of that.
I completely disagree with the idea that language keywords make refactoring difficult in any way, or that a language with less syntax is always easier to work with. Even the designers of Haskell disagree with this, as they have included both do-notation and list comprehensions, instead of letting programmers simply use bind and return. Even in Lisp, which doesn't have any syntax sugar in the base language, designers always add DSLs and Reader macros to add syntax back into the language.
But it's coupled to a monad interface in the language (or equivalent concept e.g. a typeclass in Haskell). It's not just a superficial similarity of syntax, you can write reusable functions that work for any monad, and the monad abstraction is very useful even if you prefer to write https://fsharpforfunandprofit.com/rop/ - style code that doesn't make use of do notation at all. The syntax looks the same because the values its working on implement a common interface - do notation itself is a very lightweight sugar that translates directly into interface methods.
> The initial version does explicitly handle errors. The async/await based version also handles errors (any exceptions thrown by intermediate functions will be thrown by whoever is trying to use the results). What will the do-notation continuation version do with any errors returned by the intermediate functions?
Neither the async/await nor the promise-based version includes any explicit error handling. So you're applying a real double standard; how is it any more or less clear what the monadic version will do versus what those versions will do?
> Not really - it is usually very clear how exceptions integrate with other control flow features such as continuations or, much more easily, promises or async/await
Having had to deal with some exceptions in sequence-continuation and async/await-based Kotlin code only last week, I have to disagree. Often there is more than one possible way to combine two effects, but if those effects are language features then the language designer will have picked one and you have to hope it's the behaviour you wanted. (E.g. if a parallel loop throws an exception, does this fail the other cases or just that one result? If an async function throws an exception before the first await, does the exception happen immediately or get suspended? There's no right answer, there are use cases where each behaviour is what you want).
> I completely disagree with the idea that language keywords make refactoring difficult in any way, or that a language with less syntax is always easier to work with.
It's not the syntax that's the issue, it's the semantics. In my experience the majority of production regressions caused by code changes (most production bugs tend to be caused by config changes, but that's a separate rant) come down to a particular category of language feature: things that can't be understood as plain old functions or values (to use the FP jargon, things that violate referential transparency). E.g. hoisting a value out of a loop changes the behaviour because the method that computes the constant was actually throwing an exception. E.g. inlining a method means a transaction decorator isn't applied. E.g. pulling out a common expression into its own function means it gets executed on a different thread. So replacing a language feature with a function that I can read the source code of (and, even more importantly, can be confident will follow the normal rules for functions in the language) is the best way I've found to eliminate whole categories of bugs at a stroke.
> Even the designers of Haskell disagree with this, as they have included both do-notation and list comprehensions, instead of letting programmers simply use bind and return.
What I'm arguing is that dedicated language constructs have a cost - of course that cost is sometimes outweighed by the benefits. But if you can replace five different special cases with a general case that covers all of them (and isn't five times more complicated to understand), that's a huge win.
Also, for what it's worth you can get rid of a lot of those same language features with good old OO methods. See Crystal's each[1] and try[2] methods, for example.
I don't mean this to be a tit-for-tat and do appreciate the response. You've inspired me to try and make use of a state monad in some Ocaml I've been playing with. Cheers.
[1]https://crystal-lang.org/api/0.35.1/Indexable.html#each(&)-i... [2]https://crystal-lang.org/api/0.35.1/Object.html#try(&)-insta...
This is like saying that a generic list type makes no sense because you can't tell what the values in the list actually are. The whole point of using monads is so that you can separate the generic structure of what you're doing (composing together effectful functions) from the specific details of what those effects are, and there are a bunch of useful generic functions that you can write (analogy: sorting the list, or combining together two lists) and reuse for any kind of effect.
> Also, for what it's worth you can get rid of a lot of those same language features with good old OO methods. See Crystal's each[1] and try[2] methods, for example.
Sure. I think if you actually really follow through on OO principles like SOLID and separation of concerns then you end up in much the same place as functional programming. If you replace that "each" and "try" with versions that return a "transformed" value (more composable and testable than just executing a function for side effects) then you more-or-less have the "map" function.
(Unfortunately most languages aren't sophisticated enough to let you pull out that common interface: I'm sure you can see that a function List<Int> -> List<String> has something in common with a function Set<Int> -> Set<String> or a function Future<Int> -> Future<String>, but programming languages that let you express what that common part is are surprisingly rare).
edit: to expand on that last sentence, the example under "Ad hoc solution: Promises" is more expressive to me than the author's monadic code, because a) it's more explicit about what depends on what, and b) the ".then" method name gives you a hint about what sort of computation is actually going on. Replacing "then" with "try" or "each" makes the code work just as well for the null-checking and for-loop examples.
I'm not convinced. Imagine a tutorial for the foreach construct: it would show code for iterating over a list, code for iterating over a set, and code for iterating over an array, and then a foreach loop. Would you say that obviously the iteration code is still hiding somewhere and your indirection has only increased complexity? Introducing a common interface - which is proven by the use of a common syntax - is something that we recognise as valuable, I think.
> You have to show that using functions to extract patterns from around the program improves elegance or expressiveness overall (e.g. by reducing total lines of code). I've never read a monad tutorial that does this in a way that (comparatively) simple higher-order functions wouldn't do just as well.
FWIW my own effort is https://m50d.github.io/2013/01/16/generic-contexts
However, there are lots of situations where one may want to substitute one enumerable type for another, and thus lots of opportunities to recoup that complexity. The first time the interface lets me write one function instead of two (say, a batch processing function that can deal with objects in an Array or those being streamed from an IO, because they both implement foreach), that's a win.
I have to think a lot harder to come up with a situation where I have an object that might be an Option and might be a Future, and I don't care which type I have. It doesn't seem like it would ever come up in business logic, so we're probably looking at some sort of mid-level abstraction that depends a lot on the code on both sides of it. Maybe that's why writing a decent, concise tutorial is so hard.
I like your article. You make explicit that being able to use Options and Futures interchangeably is the objective, and your example code actually depends on all the monad behaviors instead of just flatMap (I think - Scala is a foreign language to me). I still don't know how often those circumstances come up in practice, but maybe with experience I'll start seeing the patterns more often. Thanks again.
> I have to think a lot harder to come up with a situation where I have an object that might be an Option and might be a Future, and I don't care which type I have. It doesn't seem like it would ever come up in business logic, so we're probably looking at some sort of mid-level abstraction that depends a lot on the code on both sides of it. Maybe that's why writing a decent, concise tutorial is so hard.
I see where you're coming from. Monads are parametricity rather than substitutability: an Option and a Future are similar to each other in the same sense that a List<Int> and a List<String> are similar to each other. You'd never have a situation where you didn't care if you had a List<Int> or a List<String>, but there are still functions like sort() or find() or foreach() that are useful at the generic level.
And it's hard to do a good concise monad tutorial because they're an abstraction over an abstraction. Really a good tutorial would probably need three different examples - say Option, Future, and Writer - but then you'd probably need three examples for each of those to show why they're a worthwhile thing to be using in the first place.
> your example code actually depends on all the monad behaviors instead of just flatMap (I think - Scala is a foreign language to me).
flatMap/bind is the most important part - if you have a well-behaved (i.e. associative) flatMap you're 90% of the way to being a monad. I did use "wrap" for the base case (empty list), which is the kind of place it usually comes up. Don't get me wrong, it is important, but you can go a long way with just flatMap.
> I still don't know how often those circumstances come up in practice, but maybe with experience I'll start seeing the patterns more often.
Once you're used to them you see them everywhere - it's such a simple and general interface. I said anywhere you'd have a cross-cutting concern; another heuristic might be anywhere that you'd like to use the command pattern if you were "doing it properly", but there would be so much overhead to actually defining a command type. Simple things like authorisation - http://blog.sigfpe.com/2007/04/homeland-security-threat-leve... is slightly a joke, but it's something you can apply genuinely in an application that has some concept of being logged in at different privilege levels.
So generic libraries can be built and abstracting frequently used operations over many different data types. I've never implemented a monad myself outside of a toy project and am by no means an expert, but it's quite nice to be able to transfer certain knowledge on lists to options or futures. Similar to generic interfaces like a collection interface, so whether you are working on a set or a list you know that 'get' or 'exists' can be used.
If you want fancy examples, things like generic data structure traversals (I use a cataM like https://github.com/ekmett/recursion-schemes/issues/3 all the time). Another good example is iteratees - you can define an effectful source, an effectful sink, or an effectful transformation stage in a stream pipeline, which makes it very practical to have very small reusable pieces. Since it's using the generic monad interface you can define an intermediate stream transformer even for some custom effect that you wrote yourself, but be confident that everything will be plumbed together correctly.
Certainly not all of these are useful in every case - eg. `forever` needs your action to do something or you're just hanging forever.
But it's a toolbox that's easy to reach for, and which applies to a large pile of things. And when you can structure a new function only in terms of things in that toolbox, you've added another thing to the toolbox. See, for instance, `monad-loops` for more.
Exploring pairs of utility function and Monad instance can be interesting, asking (eg.) "what does `unfoldM` mean when I use it with `State`?"
It is a really weird idea which goes back to Simon Peyton Jones himself. Quote: Our biggest mistake was using the scary term “monad” rather than “warm fuzzy thing”.
I love Haskell, but the condescending attitude of some of it's adherents are off-putting. If some programmers don't grasp the wonder of monads, surely it can only be because they are scared of the word.
I'm still waiting for THE article that actually explains how this stuff works in an accessible way, without resorting to a bunch of haskell code (for which you need to already know FP - catch-22), an assumed proficiency in category theory, heavy maths, esoteric toy problems that don't touch the real world, or technically correct yet unapproachable jargon ("A monad is just a monoid in the category of endofunctors, what's the problem?").
Could you imagine teaching BASIC with "A variable is a container for values, which are themselves elements of a set of constrained possibilities. You assign to variables by collapsing the set into one possibility." That's what most FP articles feel like.
To have success in communication, you need to speak to your audience where they are; not where you wish they'd be.
Feynman was able to do this for physics; hopefully someday someone will do it for FP, and then you'll find us MUCH more receptive to the message.
The "output monad" described is usually called the Writer monad - you can append to a log, but you can't do anything based on what was in it. It can be generalised from strings to any monoid - a domain that has an empty value and an associative concatenation function.
The IO monad, as another commenter said, is a kind of state monad where the state is something ineffable from within the computing environment: it's the state of the world outside the program. But there's no need to rush to trying to fit the IO monad to this model - we can start with the "reader monad".
An element of D* for the reader monad is a function from an element of some specified domain R to an element of D. The mapping from D to D* is a constant function that produces D no matter what the argument to the function in D* is. D's elements are functions from R to D* so the collapse is function composition and therefore associative. Likewise, f* from D* to E* is function composition, which composes, obeys the embedding of D into D* and since both collapse and embedding functions is function composition f* * (s')V == f* (s'V).
The reader monad is sometimes called the environment monad, because there's some environment (the value from R) that is available to all computation. The key thing it gives us for this article's model of monads is that elements of D* don't have to just be pairs, they can be functions.
Sort of combining the Reader and Writer monads gives us a monad where an element of D* is a function from an element of the domain S to a pair from (D, S). The embedding from D to D* is the function that copies its input state to its output pair. The collapse from D is composition with application. An element of D* * is a function S -> (D* , S), or S -> (S -> (D, S), S); apply the function in the pair to the state in the pair and you get S -> (D, S). D* * * is the further nesting of this structure, S -> (S -> (S -> (D, S), S), S). Evaluating this is associative: either way you will pass the initial state through each function in the same order to get the final output state. Embedding a function also satisfies the laws; effectively it will transform the final output D and leave the state S alone.
The collapsing of State to ensure its functions are always evaluated in the same order is how the IO monad provides sequentiality of effects. The state is "everything outside the program" - the user, the keyboard, the network, the operating system, even parts of the interpreter state that are not typically open to program inspection, perhaps allocations or bit-level representations.
An element of D* for the IO monad can read from the state of "everything outside", seeing whether the operating system has a character in its console input buffer perhaps. It can modify the state of "everything outside" by writing a character to the OS console buffer. And it preserves the order of these things because of how collapse is defined.
It also needs a magic interpreter that can provide the initial state of the world and maintain it as the program updates that state, along with magic primitives that can make changes to an ineffable "real world" state.