5 ms·

Why monads have not taken the Common Lisp world by storm

33 points by andreyf 18y ago

lacker 18y ago
Has anything taken the Common Lisp world by storm in the past decade?
- jjs 18y ago
  SLIME, perhaps.
wingo 18y ago
I liked the article, but it was very much "in the weeds". I hack Scheme, and have never written any Haskell, though you have to know some to read the papers. But when programming in Scheme I find myself wanting monadic operations, like the seed in Oleg's SSAX parsers. But my code that rhymes with monads requires tail recursion, and the author didn't mention tail recursion at all. I prefer to see monads as fold + tail recursion -- and without the latter, it seems you need the mutation that Common Lisp encourages.
- sctb 18y ago
  "I prefer to see monads as fold + tail recursion" I don't think this is accurate, monads are orthogonal to both folding and tail recursion. Monads are types representing computation, and providing the operations `bind' and `return'. They're much simpler than many imagine at first. "... and without the latter, it seems you need the mutation that Common Lisp encourages." I agree that when using looping constructs other than recursion, it is often required that a counter or accumulator be mutated. Common Lisp does not encourage _general_ mutation, however, and the standard functions and macros illustrate that.
  - jrockway 18y ago
    > the standard functions and macros illustrate that You do know that nearly all of the standard list functions destroy at least one of their arguments, right? People like to call Lisp a functional language, and you can use it that way, but it is really just a very nice imperative language. Statements like: (loop for x in some-list sum (* 2 x)) are just more efficient in CL than the "functional" approach: (reduce #'+ (mapcar (lambda (x) (* 2 x)) some-list) In this case, the LOOP is about 10x faster than the reduce, probably because it conses about 5000 times less memory. CL is not set up the same way Haskell is, and hence you want to reuse data structures (or never create them) where possible. This is very imperative and very non-functional. (But I am not saying it's bad, LOOP (or ITERATE, which is what I use "in real life") is very easy to read and write.)
    - anamax 18y ago
      > You do know that nearly all of the standard list functions destroy at least one of their arguments, right? Cons, c*r, list, mapc, reduce, the mapping functions (mapcan/mapconc destroys the output of its inputs, but that's different). What definition of "nearly all" are we using?
    - Hexstream 18y ago
      I have a feeling you don't have much CL experience... There really aren't very many CL destructive (mutating) list functions, and I personally almost never use them except on fresh lists (like for example when I nreverse a list I just created with successive pushes) and I'm pretty sure it's standard practice. Let's see what destructive list functions I can find in CL (ref: http://www.lispworks.com/documentation/HyperSpec/Body/c_conses.htm http://www.lispworks.com/documentation/HyperSpec/Body/c_cons...) rplaca, rplacd, nsublis, nsubst*, nconc, nreconc, nbutlast, mapcan, mapcon, nintersection, nset-difference, nset-exclusive-or I took some liberties but that's about 12/58 = 20% destructive functions (push, pop, pushnew are usually used on variables, not list structure). And good style dictates to use them very sparsely... Also, (loop for x in some-list sum (* 2 x)) is pretty functional, you're just mutating x locally but who cares, this is exactly like saying (apply #'+ (mapcar (lambda (x) (* 2 x)))) which is obviously functional.
      - Hexstream 18y ago
        I knew something wasn't quite right. I forgot the sequence functions. So add this to the list: fill, map-into, nreverse, replace, nsubstitute, merge, delete, delete-duplicates So about 20/85 = 23,5%
      - jrockway 18y ago
        Point conceded. The post I replied to says "CL discourages mutation" which is not true. I said "nearly all sequence functions are destructive", which is also not true. Upon further reflection, I think we can say CL doesn't really care if you mutate or not. There's more than one way to do it :)
        18y ago
- jrockway 18y ago
  > I prefer to see monads as fold + tail recursion Are you sure you know what monadic computation is? (I would say, "are you sure you know what monads are", but I don't like to use adjectives as nouns.)
  - wingo 18y ago
    > Are you sure you know what monadic computation is? I think so, but of course I could be wrong. In my ignorance, I understand monadic computation as a functional state transfer in which a seed is threaded through some computation -- be it for purposes of I/O, or in general fold operations. Have you seen the SSAX parser? To my mind, the way that it builds its "answer" by threading seeds through the parse tree is monadic. What do you think?
sayrer 18y ago
Not knowing a lick of Haskell, these sorts of articles always make me wonder whether it makes Lisp look like Blub.
- jrockway 18y ago
  It depends on how important you find purity and strict typing. They are both useful, but the mistakes that experienced programmers make are not usually related to types. Having recently started writing "real" software with Haskell, I've noticed that the type system doesn't save me a lot of time. I still have to debug stupid errors, like calling a function with the right type signature but with the wrong effect. By the time I've debugged and written tests, I haven't gained a whole lot over Lisp or Perl. The advantage of Haskell is that it's as expressive as either of those, but executes a lot faster. (One concurrent app we ported was very quick to use 100% CPU on Perl with just a few outstanding operations. In Haskell, it gets to 10% CPU and runs out of file descriptors. Wow!) As for monadic computation in Haskell, it is very comfortable. You can create an environment where you only have exactly what you need, which makes your program easier to read and reason about. (No "IO a" signature? This function doesn't do IO.) It is not something I can't live without in other languages, but it does solve the intended problem very cleanly. (Similar abstractions like monoids and functors are also nice ways of looking at their respective problems.) The author of this article is right, though -- in a language with mutable state and without type inference (for return), monads are just not worth the bother. They won't give you anything you don't already have.
  - andreyf 18y ago
    I still have to debug stupid errors, like calling a function with the right type signature but with the wrong effect I wonder if a way of writing tests which is significantly easier (taking one or two magnitudes less time) would help here? Say for example, something like Python's doctests which run inside your IDE... it seems my standard way of development anyway - to write a piece of code, test it in the REPL, repeat.
    - jrockway 18y ago
shrughes 18y ago
Another reason monads are cumbersome in other languages is that other languages use lazy evaluation. If you consider the naively implemented function skipMany :: Parser a -> Parser () skipMany p = (p >> skipMany p) <|> return () and then consider how you might write it in some other language, you'll note that the translation, strictly evaluated, gives infinite recursion. To practically work with monadic computation requires some form of non-strict evaluation. Another, less catastrophic example would be the following. printNTimes :: Int -> String -> IO () printNTimes 0 s = return () printNTimes n s = putStrLn s >> printNTimes (n - 1) s Strictly evaluated, that would build up Theta(n) memory usage. For this reason, the more computation-oriented monads cannot be used practically in other languages without added weight to avoid strict evaluation. Ironically, it's the non-monadic uses that cause the problems -- those that don't need the full power of 'bind', i.e. uses where the monad's user doesn't pass return values from previous actions to future actions. When you pass a return value, you end up needing a lambda expression, which cuts off strict evaluation. When you only use them in ways that applicative functors can be used (which often applies for parsers), that's when you suffer. It's not the end of the world; there certainly are workarounds, but that requires adding explicit promises everywhere, which is just a pain.
- olavk 18y ago
  The bottom line is that monads are not practical without some kind of syntactic sugar like do-notation. Without that, you have to write operations as a chain of nested lambdas, which becomes very ugly very quickly. This is probably why monads haven't taken off in any language beside Haskell.
- chandler 18y ago
  The first example, naively translated to scheme, results in: (define (skip-many a) (or (and (a) (skip-many a)) (void))) This is not infinite recursion. The Parser monad used in the Haskell version is simply a stream dressed in monadic clothes (and even C has streams a-la FILE*). As for the second example, the naive translation to scheme is: (define (print-n-times n s) (cond ((zero? n) (void)) (else (put-str-ln s) (print-n-times (sub1 n) s)))) Here, both Haskell & scheme demonstrate constant memory usage; not because of Monads, or strict/lazy evaluation, but because of tail recursion. Also, in your first sentence, I think you meant "strict".
shiro 18y ago
One of the problem using monads in dynamically typed languages is, as this article suggests, the need to overload 'return' operation by the type of results, not by the type of arguments. I once tried to address this issue. http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3aExplicitMonad%3aEnglish http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3aExpli...

33 points by andreyf 18y ago

lacker 18y ago

Has anything taken the Common Lisp world by storm in the past decade?

jjs 18y ago
SLIME, perhaps.

wingo 18y ago

I liked the article, but it was very much "in the weeds". I hack Scheme, and have never written any Haskell, though you have to know some to read the papers. But when programming in Scheme I find myself wanting monadic operations, like the seed in Oleg's SSAX parsers. But my code that rhymes with monads requires tail recursion, and the author didn't mention tail recursion at all. I prefer to see monads as fold + tail recursion -- and without the latter, it seems you need the mutation that Common Lisp encourages.

sctb 18y ago
"I prefer to see monads as fold + tail recursion" I don't think this is accurate, monads are orthogonal to both folding and tail recursion. Monads are types representing computation, and providing the operations `bind' and `return'. They're much simpler than many imagine at first. "... and without the latter, it seems you need the mutation that Common Lisp encourages." I agree that when using looping constructs other than recursion, it is often required that a counter or accumulator be mutated. Common Lisp does not encourage _general_ mutation, however, and the standard functions and macros illustrate that.
- jrockway 18y ago
  > the standard functions and macros illustrate that You do know that nearly all of the standard list functions destroy at least one of their arguments, right? People like to call Lisp a functional language, and you can use it that way, but it is really just a very nice imperative language. Statements like: (loop for x in some-list sum (* 2 x)) are just more efficient in CL than the "functional" approach: (reduce #'+ (mapcar (lambda (x) (* 2 x)) some-list) In this case, the LOOP is about 10x faster than the reduce, probably because it conses about 5000 times less memory. CL is not set up the same way Haskell is, and hence you want to reuse data structures (or never create them) where possible. This is very imperative and very non-functional. (But I am not saying it's bad, LOOP (or ITERATE, which is what I use "in real life") is very easy to read and write.)
  - anamax 18y ago
    > You do know that nearly all of the standard list functions destroy at least one of their arguments, right? Cons, c*r, list, mapc, reduce, the mapping functions (mapcan/mapconc destroys the output of its inputs, but that's different). What definition of "nearly all" are we using?
  - Hexstream 18y ago
    I have a feeling you don't have much CL experience... There really aren't very many CL destructive (mutating) list functions, and I personally almost never use them except on fresh lists (like for example when I nreverse a list I just created with successive pushes) and I'm pretty sure it's standard practice. Let's see what destructive list functions I can find in CL (ref: http://www.lispworks.com/documentation/HyperSpec/Body/c_conses.htm http://www.lispworks.com/documentation/HyperSpec/Body/c_cons...) rplaca, rplacd, nsublis, nsubst*, nconc, nreconc, nbutlast, mapcan, mapcon, nintersection, nset-difference, nset-exclusive-or I took some liberties but that's about 12/58 = 20% destructive functions (push, pop, pushnew are usually used on variables, not list structure). And good style dictates to use them very sparsely... Also, (loop for x in some-list sum (* 2 x)) is pretty functional, you're just mutating x locally but who cares, this is exactly like saying (apply #'+ (mapcar (lambda (x) (* 2 x)))) which is obviously functional.
    - Hexstream 18y ago
      I knew something wasn't quite right. I forgot the sequence functions. So add this to the list: fill, map-into, nreverse, replace, nsubstitute, merge, delete, delete-duplicates So about 20/85 = 23,5%
    - jrockway 18y ago
      Point conceded. The post I replied to says "CL discourages mutation" which is not true. I said "nearly all sequence functions are destructive", which is also not true. Upon further reflection, I think we can say CL doesn't really care if you mutate or not. There's more than one way to do it :)
      - 18y ago
jrockway 18y ago
> I prefer to see monads as fold + tail recursion Are you sure you know what monadic computation is? (I would say, "are you sure you know what monads are", but I don't like to use adjectives as nouns.)
- wingo 18y ago
  > Are you sure you know what monadic computation is? I think so, but of course I could be wrong. In my ignorance, I understand monadic computation as a functional state transfer in which a seed is threaded through some computation -- be it for purposes of I/O, or in general fold operations. Have you seen the SSAX parser? To my mind, the way that it builds its "answer" by threading seeds through the parse tree is monadic. What do you think?

sayrer 18y ago

Not knowing a lick of Haskell, these sorts of articles always make me wonder whether it makes Lisp look like Blub.

jrockway 18y ago
It depends on how important you find purity and strict typing. They are both useful, but the mistakes that experienced programmers make are not usually related to types. Having recently started writing "real" software with Haskell, I've noticed that the type system doesn't save me a lot of time. I still have to debug stupid errors, like calling a function with the right type signature but with the wrong effect. By the time I've debugged and written tests, I haven't gained a whole lot over Lisp or Perl. The advantage of Haskell is that it's as expressive as either of those, but executes a lot faster. (One concurrent app we ported was very quick to use 100% CPU on Perl with just a few outstanding operations. In Haskell, it gets to 10% CPU and runs out of file descriptors. Wow!) As for monadic computation in Haskell, it is very comfortable. You can create an environment where you only have exactly what you need, which makes your program easier to read and reason about. (No "IO a" signature? This function doesn't do IO.) It is not something I can't live without in other languages, but it does solve the intended problem very cleanly. (Similar abstractions like monoids and functors are also nice ways of looking at their respective problems.) The author of this article is right, though -- in a language with mutable state and without type inference (for return), monads are just not worth the bother. They won't give you anything you don't already have.
- andreyf 18y ago
  I still have to debug stupid errors, like calling a function with the right type signature but with the wrong effect I wonder if a way of writing tests which is significantly easier (taking one or two magnitudes less time) would help here? Say for example, something like Python's doctests which run inside your IDE... it seems my standard way of development anyway - to write a piece of code, test it in the REPL, repeat.
  - jrockway 18y ago

shrughes 18y ago

Another reason monads are cumbersome in other languages is that other languages use lazy evaluation. If you consider the naively implemented function skipMany :: Parser a -> Parser () skipMany p = (p >> skipMany p) <|> return () and then consider how you might write it in some other language, you'll note that the translation, strictly evaluated, gives infinite recursion. To practically work with monadic computation requires some form of non-strict evaluation. Another, less catastrophic example would be the following. printNTimes :: Int -> String -> IO () printNTimes 0 s = return () printNTimes n s = putStrLn s >> printNTimes (n - 1) s Strictly evaluated, that would build up Theta(n) memory usage. For this reason, the more computation-oriented monads cannot be used practically in other languages without added weight to avoid strict evaluation. Ironically, it's the non-monadic uses that cause the problems -- those that don't need the full power of 'bind', i.e. uses where the monad's user doesn't pass return values from previous actions to future actions. When you pass a return value, you end up needing a lambda expression, which cuts off strict evaluation. When you only use them in ways that applicative functors can be used (which often applies for parsers), that's when you suffer. It's not the end of the world; there certainly are workarounds, but that requires adding explicit promises everywhere, which is just a pain.

olavk 18y ago
The bottom line is that monads are not practical without some kind of syntactic sugar like do-notation. Without that, you have to write operations as a chain of nested lambdas, which becomes very ugly very quickly. This is probably why monads haven't taken off in any language beside Haskell.
chandler 18y ago
The first example, naively translated to scheme, results in: (define (skip-many a) (or (and (a) (skip-many a)) (void))) This is not infinite recursion. The Parser monad used in the Haskell version is simply a stream dressed in monadic clothes (and even C has streams a-la FILE*). As for the second example, the naive translation to scheme is: (define (print-n-times n s) (cond ((zero? n) (void)) (else (put-str-ln s) (print-n-times (sub1 n) s)))) Here, both Haskell & scheme demonstrate constant memory usage; not because of Monads, or strict/lazy evaluation, but because of tail recursion. Also, in your first sentence, I think you meant "strict".

shiro 18y ago

One of the problem using monads in dynamically typed languages is, as this article suggests, the need to overload 'return' operation by the type of results, not by the type of arguments. I once tried to address this issue. http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3aExplicitMonad%3aEnglish http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3aExpli...