3 ms·

My understanding of monads, based on the examples in this paper, is that a monad essentially takes a series of computational steps and augments then with a seco

My understanding of monads, based on the examples in this paper, is that a monad essentially takes a series of computational steps and augments then with a secondary piece of data (a value to be printed, an error, etc). So my question is this: in languages which use monads (like Haskell), is this how monads are actually implemented? Does, say, printing values in Haskell actually involve keeping track of a lazy stream of output text, or does GHC just print out values the way an imperative language would, and use the concept of monads as a way to satisfy the type-system requirements?

lobster_johnson 8y ago
It's my understanding that the IO monad is largely a type system thing. The IO monad doesn't "do" anything -- a call to the print function actually does write to a file descriptor right there and then. In a lazy, pure language like Haskell, there's the problem that since a print function doesn't actually compute anything, it doesn't return anything that makes sense functionally; it's not a function in the mathematical sense. In Haskell, a function is only evaluated when it needs to be (i.e. potentially out of order), and functions called with the same arguments can be memoized, and functions that don't return anything can conceptually be eliminated entirely. So the challenge is to somehow tag the print function as being unmemoizable. To do this, as far as I recall (it's been a while), the GHC's implementation of IO says that the monad wraps a value of a type "RealWorld". Every time you bind/return an IO function, you are sending the current RealWorld and then getting a new RealWorld back. This is hidden from the caller since it's a detail of the monad that you don't need to see. As far as I know, the world value is just a dummy value that is optimized away and doesn't exist at run time. But by forcing every IO to depend on the previous result, the "computations" will be chained in the right order. Edit: Haskell wiki has more: https://wiki.haskell.org/IO_inside https://wiki.haskell.org/IO_inside
- zenhack 8y ago
  I think you're right in that ghc's actual implementation is something like that, but it is a bit lacking in describing the semantics. To see why, imagine functions: getLine :: RealWorld -> (String, RealWorld) putLine :: RealWorld -> String -> RealWorld And some code like: Let (line, w1) = getLine w0 w2 = putLine w1 line w3 = putLine w2 "other stuff" w4 = putLine w3 line ... Now, imagine an optimization compiler for some reason decides it would be better to recompute `line`, rather than hang on to the value in the interim. It would be well within its rights to do so, because referential transparency guarantees that this is safe. IIRC ghc essentially "plays dumb" and just never duplicates a computation (which is not typically a desirable optimization at this level, though register allocators will sometimes do it). But it's arguably a hack. A better metaphor is to think of values of type IO a as fragments of a script in some other (imperative) language. The Haskell program merely computes the script, and the runtime then takes care of actually executing it. In this sense, effects in Haskell are not "side" -- they are first class citizens. What order the fragments of the imperative program are computed in (or how many times) is independent of the text of the final program. In very early versions of Haskell, main had a type roughly like [Response] -> [Request]; you computed a list of things for the runtime to do, as a function of the results of its (hopefully) previous commands. This kinda works, but it's easy to deadlock by creating a circular data dependency. What the Monad structure does for you is avoid that problem, by making it impossible to depend on a future value. It's also worth pointing out that all of this is specific to IO; understanding monads in general are neither necessary nor sufficient to understand Haskell's IO.
  - clementi128 8y ago
    Thanks to all for the answers! I want to make sure that I'm understanding this bit correctly: >A better metaphor is to think of values of type IO a as fragments of a script in some other (imperative) language. The Haskell program merely computes the script, and the runtime then takes care of actually executing it. In this sense, effects in Haskell are not "side" -- they are first class citizens. What order the fragments of the imperative program are computed in (or how many times) is independent of the text of the final program. In Wadler's paper, the monadic output example looks like this: type M a = (Output, a) type Output = String unit :: a → M a unit a = (“ ”, a) (*) :: M a → (a → M b) → M b m * k = let(x, a) = m in let(y, b) = k a in (x ++ y, b) out :: Output → M () out x = (x, ()) where each function, instead of returning a simple numeric value, returns a tuple of a string (the output to be printed) and a number (the value to be returned). If you wrote this function out in Haskell, you would have access the output text in the form of a lazy list of strings. If we can think of IO values as fragments of an imperative script that are handled at runtime, then that makes me think that the Haskell compiler doesn't use the strategy presented in Wadler's paper (in the case of printing output, returning a lazy list of strings to be printed), and instead just performs the specified side effects directly, knowing that semantics of the IO monad guarantee that things will be sequenced correctly. Do I have this right?
    - lobster_johnson 8y ago
      Right, IO does not collect the results this way. putStr for strings is declared like so: putStr :: String -> IO () Here, () is the unit type, which is similar to null/nil in other languages. In other words, I/O functions like putStr etc. don't return anything. putStr internally calls lower-level functions that actually write to a file descriptor. Some people get into Haskell thinking that functions can't have side effects because Haskell is "pure", but that's not right. Rather, as the parent commenter say, they can have all the side effects they want, and the consistency and purity of the program's execution is preserved through the use of monads. Haskell is considered a pure functional language where everything is immutable, but that's not true, either. A lot of the GHC standard library uses mutation (e.g. with IORefs) for performance reasons. For example, putStr ends up writing to an internal byte buffer that is modified directly.
coldtea 8y ago
>My understanding of monads, based on the examples in this paper, is that a monad essentially takes a series of computational steps and augments then with a secondary piece of data (a value to be printed, an error, etc). Not really. A monad: 1) helps translate values from one domain to another. 2) helps handle the logic in a series of operations. One use of that is to enrich data with the possibility of carrying some other information (e.g. the Optional/Maybe that can carry an error). But that's not essential to what a monad does, and monads can be used for all kinds of things. The description of a monad as a "programmable semicolon" captures that a little better. Semicolons in that phrase are meant to refer to the semicolons in C or Java, that separate different expressions. So, in a program like: do this; do that; do another thing; ... Monads helps pass values between the various steps, and help determine what happens with the sequence of operations (the program wont have actual semicolons between steps in Haskell e.g. -- it's just how we notate a number of expression in C-like style for example's sake).
pubby 8y ago
Monads are regular code. They get evaluated lazily like regular code, because they are regular code. It's really hard to explain it further.

lobster_johnson 8y ago

It's my understanding that the IO monad is largely a type system thing. The IO monad doesn't "do" anything -- a call to the print function actually does write to a file descriptor right there and then. In a lazy, pure language like Haskell, there's the problem that since a print function doesn't actually compute anything, it doesn't return anything that makes sense functionally; it's not a function in the mathematical sense. In Haskell, a function is only evaluated when it needs to be (i.e. potentially out of order), and functions called with the same arguments can be memoized, and functions that don't return anything can conceptually be eliminated entirely. So the challenge is to somehow tag the print function as being unmemoizable. To do this, as far as I recall (it's been a while), the GHC's implementation of IO says that the monad wraps a value of a type "RealWorld". Every time you bind/return an IO function, you are sending the current RealWorld and then getting a new RealWorld back. This is hidden from the caller since it's a detail of the monad that you don't need to see. As far as I know, the world value is just a dummy value that is optimized away and doesn't exist at run time. But by forcing every IO to depend on the previous result, the "computations" will be chained in the right order. Edit: Haskell wiki has more: https://wiki.haskell.org/IO_inside https://wiki.haskell.org/IO_inside

zenhack 8y ago
I think you're right in that ghc's actual implementation is something like that, but it is a bit lacking in describing the semantics. To see why, imagine functions: getLine :: RealWorld -> (String, RealWorld) putLine :: RealWorld -> String -> RealWorld And some code like: Let (line, w1) = getLine w0 w2 = putLine w1 line w3 = putLine w2 "other stuff" w4 = putLine w3 line ... Now, imagine an optimization compiler for some reason decides it would be better to recompute `line`, rather than hang on to the value in the interim. It would be well within its rights to do so, because referential transparency guarantees that this is safe. IIRC ghc essentially "plays dumb" and just never duplicates a computation (which is not typically a desirable optimization at this level, though register allocators will sometimes do it). But it's arguably a hack. A better metaphor is to think of values of type IO a as fragments of a script in some other (imperative) language. The Haskell program merely computes the script, and the runtime then takes care of actually executing it. In this sense, effects in Haskell are not "side" -- they are first class citizens. What order the fragments of the imperative program are computed in (or how many times) is independent of the text of the final program. In very early versions of Haskell, main had a type roughly like [Response] -> [Request]; you computed a list of things for the runtime to do, as a function of the results of its (hopefully) previous commands. This kinda works, but it's easy to deadlock by creating a circular data dependency. What the Monad structure does for you is avoid that problem, by making it impossible to depend on a future value. It's also worth pointing out that all of this is specific to IO; understanding monads in general are neither necessary nor sufficient to understand Haskell's IO.
- clementi128 8y ago
  Thanks to all for the answers! I want to make sure that I'm understanding this bit correctly: >A better metaphor is to think of values of type IO a as fragments of a script in some other (imperative) language. The Haskell program merely computes the script, and the runtime then takes care of actually executing it. In this sense, effects in Haskell are not "side" -- they are first class citizens. What order the fragments of the imperative program are computed in (or how many times) is independent of the text of the final program. In Wadler's paper, the monadic output example looks like this: type M a = (Output, a) type Output = String unit :: a → M a unit a = (“ ”, a) (*) :: M a → (a → M b) → M b m * k = let(x, a) = m in let(y, b) = k a in (x ++ y, b) out :: Output → M () out x = (x, ()) where each function, instead of returning a simple numeric value, returns a tuple of a string (the output to be printed) and a number (the value to be returned). If you wrote this function out in Haskell, you would have access the output text in the form of a lazy list of strings. If we can think of IO values as fragments of an imperative script that are handled at runtime, then that makes me think that the Haskell compiler doesn't use the strategy presented in Wadler's paper (in the case of printing output, returning a lazy list of strings to be printed), and instead just performs the specified side effects directly, knowing that semantics of the IO monad guarantee that things will be sequenced correctly. Do I have this right?
  - lobster_johnson 8y ago
    Right, IO does not collect the results this way. putStr for strings is declared like so: putStr :: String -> IO () Here, () is the unit type, which is similar to null/nil in other languages. In other words, I/O functions like putStr etc. don't return anything. putStr internally calls lower-level functions that actually write to a file descriptor. Some people get into Haskell thinking that functions can't have side effects because Haskell is "pure", but that's not right. Rather, as the parent commenter say, they can have all the side effects they want, and the consistency and purity of the program's execution is preserved through the use of monads. Haskell is considered a pure functional language where everything is immutable, but that's not true, either. A lot of the GHC standard library uses mutation (e.g. with IORefs) for performance reasons. For example, putStr ends up writing to an internal byte buffer that is modified directly.

coldtea 8y ago

>My understanding of monads, based on the examples in this paper, is that a monad essentially takes a series of computational steps and augments then with a secondary piece of data (a value to be printed, an error, etc). Not really. A monad: 1) helps translate values from one domain to another. 2) helps handle the logic in a series of operations. One use of that is to enrich data with the possibility of carrying some other information (e.g. the Optional/Maybe that can carry an error). But that's not essential to what a monad does, and monads can be used for all kinds of things. The description of a monad as a "programmable semicolon" captures that a little better. Semicolons in that phrase are meant to refer to the semicolons in C or Java, that separate different expressions. So, in a program like: do this; do that; do another thing; ... Monads helps pass values between the various steps, and help determine what happens with the sequence of operations (the program wont have actual semicolons between steps in Haskell e.g. -- it's just how we notate a number of expression in C-like style for example's sake).

pubby 8y ago

Monads are regular code. They get evaluated lazily like regular code, because they are regular code. It's really hard to explain it further.