2 ms·
Basically the traditional way to do I/O is to just call I/O functions (like printing to the terminal and reading keyboard input) in the middle of the program.
by devit 9y ago
Basically the traditional way to do I/O is to just call I/O functions (like printing to the terminal and reading keyboard input) in the middle of the program.
There is another way, which consists of having the program only consist of a pure function that returns the kind of an I/O function to call, its parameters, plus a closure that takes the result of the I/O function, and returns again a pair of I/O function kind, parameters and closure.
Then, an external "executor" can just perform the I/O, call the closure with the result, perform the I/O again, etc.
The result of this is the program can be executed to do I/O, but all functions are side effect free (they just compute a result based on the arguments).
The tuple of I/O function kind to call plus parameters plus closure is called an "I/O monad" (or equivalently it can be just the closure).
Now in this model if you want to have subroutines you need them to return an I/O monad, and need to be able to "chain" the rest of the computation to it, which is done by adding a method to the I/O monad called "bind".
These subroutines might not do any I/O, but it's still convenient to return an I/O monad, so an operation called "return" is added, which returns an I/O monad whose I/O function simply returns the parameter to return.
This interface with those "bind" and "return" functions is called a "monad", of which the I/O monad is an instance (along with some obvious properties, like that calling bind twice is the same as calling it once with the composition of the two functions, and that return and bind also commute in the same obvious way).
Another example is the "state monad", which is like the I/O monad except the operations are "read variable #i" and "write variable #i" (Haskell uses STRef objects instead of variable indices, but it's essentially the same).
While the I/O monad can only be executed "externally" to the program, the state monad can be executed internally: a pure function can be written that takes an array of initial values of the variables, a state monad instance and executes the state monad instance and gives back the final variable values.
So this gives a more complicated way of expressing imperative programming that has the advantage of only involving pure functions and thus being usable in pure languages like Haskell.
Now, why isn't this the best thing since sliced bread?
The obvious problem is that a naive implementation is massively inefficient, since every time you want to perform a memory write you need to stuff the stack of the program into the heap and return it as a closure.
Furthermore, monads for normal I/O and state are just not very useful: isolating the computation can be done with Rust's model of lifetimes and linear types, the ability to execute it in different ways can be achieved by providing a dynamically-dispatched set of I/O functions, and stopping the computation can be performed with unwinding.
The only practical advantage of monads is that you can pause the computation and have the state on the heap instead of the stack. This is why efficiently implemented languages like Rust (and in this case Java/C#/JavaScript) only use monads to implement futures/promises, where this ability is exactly what is wanted, and don't use state monads or I/O monads for synchronous I/O.
As an aside, the reason futures/promises are the best way to do I/O is that when the computation is paused, the state is stored on a heap in a compact layout (as a future/promise monad instance), while with either threads or coroutines it consists of an inefficiently laid out machine stack in userspace (that also takes a lot of virtual address space since it must be able to grow arbitrarily) and in case of native threads a machine stack and thread structure in kernel space as well.
The async/await and future/promise support in Java, C# and JavaScript is essentially a direct implementation of the Haskell monad model, with the downside of requiring an allocation for each await.
However, there's also way to have a monad-like style while preserving near-optimal performance, which is used in Rust's async/await generators.
The idea is that instead of having monads be closures that return closures, they instead become generic "objects" with a method that, upon being called, updates the state of the object and returns a description of the I/O operation to perform (or even just performs it with parameters provided by the caller), and is called again and again until it signals that the computation is done (this of course involves mutable state, but the mutation can be restricted with ownership).
"bind" can then be performed by simply defining a larger object that embeds the inner "monad" and the whole thing can be monomorphized, thus removing any dynamic dispatch and having a program that behaves as normal, except that instead of storing variables in the stack, it stores them in a single variable that needs to be immovable, either by heap allocating or ensure it's not moved on the stack. Note however that you need further allocations for recursion and in general for any dynamic calls whose state does not have a bounded size.
TLDR: monads primarily exists because Haskell must be pure and doesn't care about performance, but also because they are the only way to do memory-efficient async I/O