7 ms·

Why monads have not taken the Common Lisp world by storm (2008)

67 points by momo-reina 13y ago

marijn 13y ago
I [author] must say I'm slightly embarrassed to see this turn up here now. This is not a terribly deep or interesting post. Read http://marijnhaverbeke.nl/blog/tern.html http://marijnhaverbeke.nl/blog/tern.html or http://marijnhaverbeke.nl/blog/acorn.html http://marijnhaverbeke.nl/blog/acorn.html or http://marijnhaverbeke.nl/blog/browser-input-reading.html http://marijnhaverbeke.nl/blog/browser-input-reading.html instead.
- momo-reina 13y ago
  I enjoyed reading the code =)
- moomin 13y ago
  Don't be. The fundamental observation that monad's usability is tied closely to Haskell's features is important, and still hasn't been taken on board elsewhere. There's always someone trying to do monads in Clojure...
  - octo_t 13y ago
    Scala has plenty of monads and they work fine.
    - rtpg 13y ago
      Scala also has some pretty powerful syntax to go with
    - marijn 13y ago
      Scala has a much more powerful type system than Clojure
      - moomin 13y ago
        100% true, but not as powerful as Haskell's. Not sure you can usefully have inheritance and return type overloading.
        samth 13y ago
        The Scala and Haskell type systems are incomparable, and the typeclass aspects that are most relevant to monad usability are doable with implicits.
    - fusiongyro 13y ago
      Yes, but doesn't it also have the three requirements mentioned by the article: ML-style function foo, something akin to type classes, and polymorphic return types?
      - yohanatan 13y ago
        In Scala, currying is not all-pervasive. You have to be explicit about it (and it's a definite pain point).
  - bunderbunder 13y ago
    Yup. If I had read this article when it was first written instead of now, I probably would have produced a fair bit less unnecessarily complicated and difficult-to-maintain code over the past several years. Instead, I had to figure out why I was having such a hard time coming up with a satisfactory implementation of the pattern in C# - and why I maybe shouldn't have wanted one in the first place - the hard way.
    - alipang 13y ago
      Just curious, why would you argue that you shouldn't have wanted it the first place? Monads are one thing, which you can approximate somewhat via LINQ, but there are other simpler patterns such as Monoid, that really makes sense to use as programming construct, that just somehow never works in C#.
      - bunderbunder 13y ago
        Because it seems like there always turns out to be some other approach that works better and is more idiomatic in C#. Usually something really forehead-smackingly obvious like mutation or a callback.
- mightybyte 13y ago
  Don't be embarrassed about this. I think it's a very important point. I've heard monads getting buzz outside the Haskell community and it almost always misses the point. I gave a presentation at the NYC Haskell meetup that made essentially the same point as you, but came at it from a different angle. You wrote this post quite awhile earlier, but it's nice to know that we independently came to the same conclusions.
Peaker 13y ago
> It appears that in the presence of mutable state, a lot of the advantages of monads become moot. In the simpler cases where use of monads can be replaced by simple mutable state -- you still lose out on the explicit types of the mutating vs. pure code. For example, STM is possible because mutating effects are typed, and so can be ruled out of STM transactions. And in the more complex monads (e.g: transformer stacks), mutable state is just not good enough. You can compose transformers to build things that mutable state simply cannot express, and you'd have to CPS transform your code and avoid mutable state to express those things. For example, these two monads: ListT (ParsecT m) ParsecT (ListT m) Have no corresponding "mutable state" representations.
- tel 13y ago
  That's a really great point that I rarely see come up. Yes, Haskell makes you "recreate" the RWST monad stack that imitates impure languages... but the same tools also let you build other "language domains" which are fiendishly difficult to implement in non-pure settings (on par with CPS transforming yourself into the mother monad and then working backwards from there). On Lisp has a chapter devoted to making a leaky macro-based CPS transformer for Common List. ContT adds CPS to any monad stack as quickly as newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }
  - jeremyjh 13y ago
    >Yes, Haskell makes you "recreate" the RWST monad stack that imitates impure languages This is really a point that seems to get lost in most of learning materials on the web. LYAH doesn't even acknowledge transformers. I am pretty new to Haskell but it seems to me that transformer stack decisions are a pretty significant design decision for your application. What has happened to me is almost all the code in my application has wound up inside this stack; the only pure functions are trivial helpers. I'm not aware of what has been written on this topic in terms of guidance or advice. But it seems like it is definitely one of the later-stage humps for a new Haskell developer like me.
    - tel 13y ago
emiljbs 13y ago
>That's a little too blatantly useless to be interesting though. But note how ugly CL's multiple namespaces make liftmaybe and its uses. Oh yeah, incredibly ugly \s OP, you may be interested in checking out LiL, the Lisp interface Library. https://github.com/fare/lisp-interface-library https://github.com/fare/lisp-interface-library
asgard1024 13y ago
Incidentally, I am just reading through All About Monads (http://www.haskell.org/haskellwiki/All_About_Monads http://www.haskell.org/haskellwiki/All_About_Monads) and his point 3 ("Allow polymorphism on return types") is what confused me in this example: getAny :: (Random a) => State StdGen a getAny = do g <- get (x,g') <- return $ random g put g' return x I was like.. how on Earth Haskell knows which function "get" should it call? I think this is a point which should be more stressed in the tutorials (I read Learn yourself a Haskell and glanced at couple of others..)
- tel 13y ago
  It's easy for a Haskell expert to sweep typeclass resolution under the rug, but it's definitely some pretty black magic at first no matter how "simple" its implementation is. The reality is that the compiler works really hard to ensure that it can guess the right "get" and it's pretty possible for it to fail. Of course, when it fails you know immediately and can remedy it by type annotations, but that can still be challenging. To answer the question, `get` has its principle type resolved by the type inference engine. In this case, `get`'s most general type is `MonadState s m => m s` and it can resolve what `m` is by unifying it with the type annotation of `getAny`, so we know that we need `get :: MonadState s (State StdGen) => State StdGen s`. From here, the compiler searches through the type class instances in a Prolog-like style to find that `MonadState s (State StdGen)` occurs when `s ~ StdGen`. This resolves more type information and also tells us which definition of `get` is needed—the one that was defined as `instance MonadState s (State s) where`! The end result is that get ends up with the type `get :: State StdGen StdGen` and is the function defined as `get = State $ \s -> (s, s)`.
  - alipang 13y ago
    It's also quite possible for this type of functions to get a polymorphic type, in which case the compiler generate code that will pass along essentially a virtual table object for the particular instance of the call site. Hardly black magic.
    - 13y ago
tonetheman 13y ago
I came here to make a joke about the real reason why was that no one understands them... but apparently everyone here does. Off to google monads for idiots...
- gernotk 13y ago
  This talk by Douglas Crockford is quite informative: http://www.youtube.com/watch?v=dkZFtimgAcM http://www.youtube.com/watch?v=dkZFtimgAcM
  - recursive 13y ago
    As a connoisseur of monad explanations (if not monad understanding) Crockford's talk sounds rushed. It spends a fair amount of time on setup, but when it gets to the meaty bits, it has the feeling of glossing over the details. It could be that all the essential elements are there, but they're covered to quickly to impart any comprehension.
    - runT1ME 13y ago
      Actually, Crockford is completely wrong in his definition. He is confusing them for functors.
  - tonetheman 13y ago
    Cool thanks!
    - chongli 13y ago
      I actually prefer Brian Beckman's explanation: http://www.youtube.com/watch?v=ZhuHCtR3xq8 http://www.youtube.com/watch?v=ZhuHCtR3xq8
- gtani 13y ago
  I think the proper presentation of this material is as how Learn you a haskell[1] does it: functors, applicatives, monoids ... then monads but I don't think i've seen this done for other languages. Each of those structures should be learned as a set of properties, rather than something concrete (container, wrapper, sequencer, programmable semicolon) and then you see how important the applicative vs monadic style decision is for library design in haskell [1]http://learnyouahaskell.com/functors-applicative-functors-and-monoids http://learnyouahaskell.com/functors-applicative-functors-an...
quarterto 13y ago
* Try to quickly write the whole thing as a single recursive descent parser. Note the exploding amount of ugliness. Give up. * Separate out the tokenizer (novel idea, huh?) to keep parser complexity down. Parser is still a mess. Ugh! * Play around with some CL parser frameworks. This helps a bit, but none of the systems I tried produce errors with enough information. * Remember the breeze it was to write a parser with the Haskell Parsec library. Mess around with monads for a while, learn a few things, but not how to write elegant parsers in Common Lisp. I've been going through these exact steps but in JavaScript. Writing languages is fun! And makes me want to kill things!
- spacemanaki 13y ago
  I have no idea what you're working on, but I spent a few weeks this summer writing parsers and trying to figure out how to tackle the ugliness that seems to be inherent in hand-written recursive descent parsers. While I learned a lot, I am not an expert by a long shot. However I did find an interesting technique that is not well covered elsewhere. I came across this* article, which uses JavaScript as the implementation language, and found it very interesting, in large part because this approach (Top down operator precedence) sort of pulls the precedence hierarchy out of the call graph of a recursive descent parser and into a table, but also because it's an approach that OOP (and JavaScript in particular) is well suited to. I've used it (in combination with traditional recursive descent) in a functional setting (Standard ML) as well, and would use it again, especially for parsing infix expressions (arithmetic expressions, type annotation expressions). This is a bit of a tangent, but I thought you might be interested given the intersection of parsing and JavaScript. I've been meaning to write this up in a short blog post... * http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html There's another article on this using Java as the implementation language: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...
  - anaphor 13y ago
    I like the precedence climbing algorithm since you can easily fit it into a normal recursive descent parser and it allows you to easily add new operators just by putting them in a table. See: http://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing/ http://eli.thegreenplace.net/2012/08/02/parsing-expressions-...
ggchappell 13y ago
There is a point made here about how Haskell's namespace handling makes monads easy, while CL's makes them ugly. I don't know enough about CL's namespaces to understand this. Can someone explain?
- emiljbs 13y ago
  Functions and other values are stored in separate namespaces so when you want to call a function that is stored in a "regular" variable you must write (funcall (function variable) arg1 arg2 ... argn) Or shorthand (funcall #'variable arg1 arg2 ... argn) Basically, some people find this ugly, I mostly find it to say "HEY!! We're doing this specific thing right here". To me it's more helpful than ugly.
dustingetz 13y ago
Nah, I think its just because they result in really nested types which is hard to keep track of without a really good type system. Using a single monad by itself like error or continuation is straightforward in Clojure; there are smart & vocal people who do this. But the super awesome OMFG of monads is that they can be combined (e.g. parser = error + state), and this more or less requires abstracting in the type system to keep track of all the lambdas.

67 points by momo-reina 13y ago

I [author] must say I'm slightly embarrassed to see this turn up here now. This is not a terribly deep or interesting post. Read http://marijnhaverbeke.nl/blog/tern.html http://marijnhaverbeke.nl/blog/tern.html or http://marijnhaverbeke.nl/blog/acorn.html http://marijnhaverbeke.nl/blog/acorn.html or http://marijnhaverbeke.nl/blog/browser-input-reading.html http://marijnhaverbeke.nl/blog/browser-input-reading.html instead.

momo-reina 13y ago
I enjoyed reading the code =)
moomin 13y ago
Don't be. The fundamental observation that monad's usability is tied closely to Haskell's features is important, and still hasn't been taken on board elsewhere. There's always someone trying to do monads in Clojure...
- octo_t 13y ago
  Scala has plenty of monads and they work fine.
  - rtpg 13y ago
    Scala also has some pretty powerful syntax to go with
  - marijn 13y ago
    Scala has a much more powerful type system than Clojure
    - moomin 13y ago
      100% true, but not as powerful as Haskell's. Not sure you can usefully have inheritance and return type overloading.
      - samth 13y ago
        The Scala and Haskell type systems are incomparable, and the typeclass aspects that are most relevant to monad usability are doable with implicits.
  - fusiongyro 13y ago
    Yes, but doesn't it also have the three requirements mentioned by the article: ML-style function foo, something akin to type classes, and polymorphic return types?
    - yohanatan 13y ago
      In Scala, currying is not all-pervasive. You have to be explicit about it (and it's a definite pain point).
- bunderbunder 13y ago
  Yup. If I had read this article when it was first written instead of now, I probably would have produced a fair bit less unnecessarily complicated and difficult-to-maintain code over the past several years. Instead, I had to figure out why I was having such a hard time coming up with a satisfactory implementation of the pattern in C# - and why I maybe shouldn't have wanted one in the first place - the hard way.
  - alipang 13y ago
    Just curious, why would you argue that you shouldn't have wanted it the first place? Monads are one thing, which you can approximate somewhat via LINQ, but there are other simpler patterns such as Monoid, that really makes sense to use as programming construct, that just somehow never works in C#.
    - bunderbunder 13y ago
      Because it seems like there always turns out to be some other approach that works better and is more idiomatic in C#. Usually something really forehead-smackingly obvious like mutation or a callback.
mightybyte 13y ago
Don't be embarrassed about this. I think it's a very important point. I've heard monads getting buzz outside the Haskell community and it almost always misses the point. I gave a presentation at the NYC Haskell meetup that made essentially the same point as you, but came at it from a different angle. You wrote this post quite awhile earlier, but it's nice to know that we independently came to the same conclusions.

Peaker 13y ago

> It appears that in the presence of mutable state, a lot of the advantages of monads become moot. In the simpler cases where use of monads can be replaced by simple mutable state -- you still lose out on the explicit types of the mutating vs. pure code. For example, STM is possible because mutating effects are typed, and so can be ruled out of STM transactions. And in the more complex monads (e.g: transformer stacks), mutable state is just not good enough. You can compose transformers to build things that mutable state simply cannot express, and you'd have to CPS transform your code and avoid mutable state to express those things. For example, these two monads: ListT (ParsecT m) ParsecT (ListT m) Have no corresponding "mutable state" representations.

tel 13y ago
That's a really great point that I rarely see come up. Yes, Haskell makes you "recreate" the RWST monad stack that imitates impure languages... but the same tools also let you build other "language domains" which are fiendishly difficult to implement in non-pure settings (on par with CPS transforming yourself into the mother monad and then working backwards from there). On Lisp has a chapter devoted to making a leaky macro-based CPS transformer for Common List. ContT adds CPS to any monad stack as quickly as newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }
- jeremyjh 13y ago
  >Yes, Haskell makes you "recreate" the RWST monad stack that imitates impure languages This is really a point that seems to get lost in most of learning materials on the web. LYAH doesn't even acknowledge transformers. I am pretty new to Haskell but it seems to me that transformer stack decisions are a pretty significant design decision for your application. What has happened to me is almost all the code in my application has wound up inside this stack; the only pure functions are trivial helpers. I'm not aware of what has been written on this topic in terms of guidance or advice. But it seems like it is definitely one of the later-stage humps for a new Haskell developer like me.
  - tel 13y ago

emiljbs 13y ago

>That's a little too blatantly useless to be interesting though. But note how ugly CL's multiple namespaces make liftmaybe and its uses. Oh yeah, incredibly ugly \s OP, you may be interested in checking out LiL, the Lisp interface Library. https://github.com/fare/lisp-interface-library https://github.com/fare/lisp-interface-library

asgard1024 13y ago

Incidentally, I am just reading through All About Monads (http://www.haskell.org/haskellwiki/All_About_Monads http://www.haskell.org/haskellwiki/All_About_Monads) and his point 3 ("Allow polymorphism on return types") is what confused me in this example: getAny :: (Random a) => State StdGen a getAny = do g <- get (x,g') <- return $ random g put g' return x I was like.. how on Earth Haskell knows which function "get" should it call? I think this is a point which should be more stressed in the tutorials (I read Learn yourself a Haskell and glanced at couple of others..)

tel 13y ago
It's easy for a Haskell expert to sweep typeclass resolution under the rug, but it's definitely some pretty black magic at first no matter how "simple" its implementation is. The reality is that the compiler works really hard to ensure that it can guess the right "get" and it's pretty possible for it to fail. Of course, when it fails you know immediately and can remedy it by type annotations, but that can still be challenging. To answer the question, `get` has its principle type resolved by the type inference engine. In this case, `get`'s most general type is `MonadState s m => m s` and it can resolve what `m` is by unifying it with the type annotation of `getAny`, so we know that we need `get :: MonadState s (State StdGen) => State StdGen s`. From here, the compiler searches through the type class instances in a Prolog-like style to find that `MonadState s (State StdGen)` occurs when `s ~ StdGen`. This resolves more type information and also tells us which definition of `get` is needed—the one that was defined as `instance MonadState s (State s) where`! The end result is that get ends up with the type `get :: State StdGen StdGen` and is the function defined as `get = State $ \s -> (s, s)`.
- alipang 13y ago
  It's also quite possible for this type of functions to get a polymorphic type, in which case the compiler generate code that will pass along essentially a virtual table object for the particular instance of the call site. Hardly black magic.
  - 13y ago

tonetheman 13y ago

I came here to make a joke about the real reason why was that no one understands them... but apparently everyone here does. Off to google monads for idiots...

gernotk 13y ago
This talk by Douglas Crockford is quite informative: http://www.youtube.com/watch?v=dkZFtimgAcM http://www.youtube.com/watch?v=dkZFtimgAcM
- recursive 13y ago
  As a connoisseur of monad explanations (if not monad understanding) Crockford's talk sounds rushed. It spends a fair amount of time on setup, but when it gets to the meaty bits, it has the feeling of glossing over the details. It could be that all the essential elements are there, but they're covered to quickly to impart any comprehension.
  - runT1ME 13y ago
    Actually, Crockford is completely wrong in his definition. He is confusing them for functors.
- tonetheman 13y ago
  Cool thanks!
  - chongli 13y ago
    I actually prefer Brian Beckman's explanation: http://www.youtube.com/watch?v=ZhuHCtR3xq8 http://www.youtube.com/watch?v=ZhuHCtR3xq8
gtani 13y ago
I think the proper presentation of this material is as how Learn you a haskell[1] does it: functors, applicatives, monoids ... then monads but I don't think i've seen this done for other languages. Each of those structures should be learned as a set of properties, rather than something concrete (container, wrapper, sequencer, programmable semicolon) and then you see how important the applicative vs monadic style decision is for library design in haskell [1]http://learnyouahaskell.com/functors-applicative-functors-and-monoids http://learnyouahaskell.com/functors-applicative-functors-an...

quarterto 13y ago

* Try to quickly write the whole thing as a single recursive descent parser. Note the exploding amount of ugliness. Give up. * Separate out the tokenizer (novel idea, huh?) to keep parser complexity down. Parser is still a mess. Ugh! * Play around with some CL parser frameworks. This helps a bit, but none of the systems I tried produce errors with enough information. * Remember the breeze it was to write a parser with the Haskell Parsec library. Mess around with monads for a while, learn a few things, but not how to write elegant parsers in Common Lisp. I've been going through these exact steps but in JavaScript. Writing languages is fun! And makes me want to kill things!

spacemanaki 13y ago
I have no idea what you're working on, but I spent a few weeks this summer writing parsers and trying to figure out how to tackle the ugliness that seems to be inherent in hand-written recursive descent parsers. While I learned a lot, I am not an expert by a long shot. However I did find an interesting technique that is not well covered elsewhere. I came across this* article, which uses JavaScript as the implementation language, and found it very interesting, in large part because this approach (Top down operator precedence) sort of pulls the precedence hierarchy out of the call graph of a recursive descent parser and into a table, but also because it's an approach that OOP (and JavaScript in particular) is well suited to. I've used it (in combination with traditional recursive descent) in a functional setting (Standard ML) as well, and would use it again, especially for parsing infix expressions (arithmetic expressions, type annotation expressions). This is a bit of a tangent, but I thought you might be interested given the intersection of parsing and JavaScript. I've been meaning to write this up in a short blog post... * http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html There's another article on this using Java as the implementation language: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...
- anaphor 13y ago
  I like the precedence climbing algorithm since you can easily fit it into a normal recursive descent parser and it allows you to easily add new operators just by putting them in a table. See: http://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing/ http://eli.thegreenplace.net/2012/08/02/parsing-expressions-...

ggchappell 13y ago

There is a point made here about how Haskell's namespace handling makes monads easy, while CL's makes them ugly. I don't know enough about CL's namespaces to understand this. Can someone explain?

emiljbs 13y ago
Functions and other values are stored in separate namespaces so when you want to call a function that is stored in a "regular" variable you must write (funcall (function variable) arg1 arg2 ... argn) Or shorthand (funcall #'variable arg1 arg2 ... argn) Basically, some people find this ugly, I mostly find it to say "HEY!! We're doing this specific thing right here". To me it's more helpful than ugly.

dustingetz 13y ago

Nah, I think its just because they result in really nested types which is hard to keep track of without a really good type system. Using a single monad by itself like error or continuation is straightforward in Clojure; there are smart & vocal people who do this. But the super awesome OMFG of monads is that they can be combined (e.g. parser = error + state), and this more or less requires abstracting in the type system to keep track of all the lambdas.