Friday, February 02, 2007

Why monads are 'evil'

This is an heavily updated version of a previous article with a somehow similar name. From the comments to this article I learned where the original article was misleading and partly even wrong. So I try to correct that with this updated version.



What is functional programming? Many people tend to think that having closures in a language makes that language a functional one. But by this definition almost every modern language would qualify as 'functional'. Even Java (because of Javas anonymous inner classes which are closures too). So if this can't be the qualifying property of a language, what else is it?

Of course it's "referential transparency": A 'function' is an special kind of relation which assigns values of a domain-set to values of a result-('codomain') set. To qualify as a function this mapping has to be unambiguous: For every element of the domain-set the function always gives the single, same result.

If a 'function' isn't referential transparent, this property isn't fulfilled and it's simply not a function anymore. It's something which is often called 'procedure'. We can argue if this property really has to be fulfilled rigorously by a language to qualify as 'functional', but I would say 'Yes, it has!'. The reason is that we can use procedures to create functions in every language (just by making sure that there are no side-effects), but to really call a language 'functional' it has to be assured by the compiler that every function is really a function. BTW: we can make every procedure a function by simply including the whole 'environment' as input to the procedure. With this little trick every procedure would now be a function and every programming language would be functional. Yes, this is nonsense - remember that for later.

But with this rigorous definition of the notion 'functional', there aren't many functional languages lest. Ocaml for example is clearly non-functional now. But even Haskell isn't. The reason is the IO-monad.

Do to I/O, Haskell uses something which is called 'I/O-monad'. If we write

main = do
x <- getStr
putStr ("you entered " ++ x)

the following happens: First the 'do' statement transforms the code by using a function called '>>=' (pronounced as 'bind').

getStr >>= (\x -> putStr ("you entered " ++ x))

(If we use the name 'bind' instead of '>>=' and the prefix form of function calls this would look like this:

bind(getStr, (\x -> putStr ("you entered " ++ x)))
)

The getStr function (which is in fact a constant and not even a function because it don't takes any parameters) is just a parameter for the 'bind'-function. It returns an 'action', a value of type 'IO String'. 'IO' is a special type here which simply encapsulates something and is parametrized with the type 'String' (in Java/C++ we would write this as IO). But if 'getStr' always gives the same value, how can it be used to input Strings from the console?

The answer is that 'getStr' doesn't do this. Its only a command to do it. And this command goes as first input into the 'bind'-function which executes it. The second paramter of the call is the 'to-do'-function. Its the code which is associated with the action and has to be called with the result of the action. The bind-function returns a value itself which is also a action. This allows us to use the result of a bind-function as first parameter in another bind-function. So those functions can be chained arbitrarily - and this is what the 'do'-syntax does (just in a more convenient way).

Back to our example: The bind-operator received the 'getStr'-action as input. This action instructs it to fetch a String from the console and call the to-do-function with it. Now this function again returns an action, this time it's a 'putStr' action. This 'putStr' action is again a constant, but it was created 'on the fly' from the putStr function which takes one parameter: The String to write out. The next bind operation is invisible, because it happens outside the main function in the REPL or compiler. But it's executed like the first bind and it uses the 'putStr' action to write the data out.

So it's the bind-function which isn't really referential transparent: If you apply it to the same action twice, it can call it's 'to-do' function with a different value. Now Haskell clever hides that because it don't allows anybody to examine the content of the actions: Because 'bind' always returns such an opaque action, its (theoretically) impossible for a program to see that two results are in fact different. And because Haskell allows no mutation, the to-do-function can't write this result somewhere outside the I/O-monad. But isn't that enough to ensure referential transparency? I would say no.

The reason is the same that I don't consider ordinary procedures as referential transparent: It's just a trick. The operational semantics of the whole mechanism are simply non-referential transparent, if Haskell hides it well or not. We can in principle write the whole program in the I/O monad and there is no difference to an ordinary imperative language anymore. So we should go with the 'duck-paradigmization': If it mutates like the imperative paradigm, is non-referential transparent like the imperative paradigm and has a fixed execution order like the imperative paradigm, I would call the it the imperative paradigm.

Lets look at an alternative approach to the functional I/O problem: We create a 'world'-value which contains the relevant data from the 'outside' (likes files, console input etc) and feed this value into a function. This function can now create some output by processing informations from this 'world'. By evaluating the 'world'-value lazily we can even create interactive programs, because the function simply stops the evaluation in the moment there are no new input values and continues evaluation in the moment we provide them (for example by typing something on the keyboard). With this concept a main function would look like this:

main :: world -> output

In a simple console application both 'world' and 'output' would simply be lists of characters. But for a more complex applications the 'world' could contain all kinds of mouse/keyboard/etc-events while the 'output' would contain for example drawing-commands.

Whats the difference to the monadic-I/O concept of Haskell? Couldn't we simply use this approach to use it to implement our I/O-monad? The interpreter of the I/O-actions would simply use such 'world'- and 'output'-values and use them by the actions the program provides. Aren't both concepts now simply identically, but easier to use in Haskell because the difficult stuff is well hidden inside the I/O-monad?

While this is true 'in principle' it's only true on the same level that all Turing-complete languages are identically 'in principle':

What the I/O monads does is creating a new sub-language with imperative semantics. Every code which runs 'in' the I/O-monad is in fact evaluated imperatively. This transformation is done by the 'bind' functions and hidden from view by the 'do'-construct. The 'do'-construct slices all the statements in the body into small pieces and feeds them into those bind-functions. Now their execution order isn't anymore in the statement-order but is the bind functions which choose to evaluate them (in any order, multiple times, or not at all). And the values those statements give and take is also controlled by those bind-functions because they provide them (as long as they are assigned with the '<-' operation).

So every code we have inside such a do-block can have nearly arbitrary semantics. It's a bit similar to Lisp macros but the transformation happens at runtime. And because of the chaining of bind-functions, semantics of such a block only depends on the type of the first statement in the do-block.

Think about this: By writing the right 'bind' functions we can create in principle every semantics we want. For example we can create a language with all the semantics of the Java language right into Haskell - we 'only' have to create the right monad. Sure, the syntax would be different from Java because the code is still parsed by the Haskell parser and needs to follow certain rules, but the semantics of this code could be identically to Java. With this 'Java-monad' we're now able to program in Haskell like we're using Java. But Java is an imperative, object-oriented language so nobody would say that we're still writing code in a functional programming language.

Using the I/O-monad is similar: It provides a new language with new semantics by doing runtime code-rewriting. It's not a functional language anymore, even if it's implemented inside a functional language. We simply have left 'functional land' if we use the I/O monad - and we can never return from it because the I/O-monad is grounded in the compiler, the outermost layer of every program. We can only call functional code from this imperative layer but this functional code can't do any I/O anymore.

But whats the difference to the explicit way of doing I/O? It's that we still have full control about what we're doing: We're working on the level of functions instead of creating actions which are somehow evaluated by an invisible interpreter. We have to supply the input values manually and we call real functions instead of building some action-values which are evaluated somehow. If we want we can slice the 'world' into pieces, supply only parts of it to functions and the result of those functions can be something arbitrary. And we can use all the normal functions instead of creating new 'monadized' ones.

Sure, we have to think more about certain things - but this is part of doing work in a certain paradigm. If we want to have the advantages of the paradigm we can't simply create a new sub-language in a different paradigm and expect to still have the advantages which are the reason why we used this paradigm in the first hand. If we want do do I/O with the I/O-monad we have to switch programming languages. We stop using to program in a shiny new functional way and are back in the boring old land of the imperative. Even worse: Because Haskell don't provides a different way of doing I/O, it's like a confession that functional programming can't do I/O. And all this only because of the 'evil' I/O-monad.

And there are other problems which apply to monads in general:

  • The performance seem to lack because of the runtime-code-translation: The translation costs time and memory and can sometimes even kill important properties like tail recursion (because the program we thought we wrote is not the program which is executed because of the monadic translation). If you compare Haskell with the Clean-language (which the direct state-chaining approach instead of monads based code-translation to do I/O), Clean wins hands down in many benchmarks.

  • Code reuse gets more difficult: This is a common problems with domain specific languages: Because we create parts of code with different language semantics, it's hard to fit those parts of code together later. We've not only to worry about different interfaces - we have to consider even different semantics! In Haskell we can put monads into other monads (and create some kind of translation-chaining) but this won't works always and so sometimes code reuse gets impossible. And after we left 'plain functional land' and entered the land of some arbitrary new semantics we need special versions of our well known functional tools and need specialized ones.

  • The real semantics are much more difficult to understand: The sheer number of 'how do monads work'-articles speak volumes. And many are still missing the real point: Monads are code transformers. Because this they can do nearly 'everything' - and to understand them you have to understand every concrete monad on each own, because each of them creates a new language! This is it what makes monads so hard to grasp.

  • It can hurt readability: A concrete monad is choosen by the return type of a function. For example a simple 'x <- get' can switch the rest of the do-block into 'state-monad'-land. This is quite easy to overlook because the type of a function isn't always obvious. In Lisp macros often have at least lengthy, descriptive names, in Haskell it's far less obvious. Explicit type annotations are a must here to see whats really happening.


As more I understand the concept of monads the more I'm becoming skeptical about them. Like Lisps macros they simply are to powerful. Instead of creating tools to build new language inside a language, why not directly create a powerful language?

I know that many people will see this differently because they like to use languages as 'construction kits' for new languages. Yes, this this is a valid reason, but only in a very limited domain. In most areas we don't need a language to create another language but to solve a certain, concrete problem: Create a web-application, a word processor, a computer-game or something else. I prefer to have a language with fixed semantics, which I only need to learn once and which don't change (at least until the next language revision). This makes code much more easy to understand and to reuse and this enhances productivity.

As Haskell being some kind of 'research language' originally, monads are surly helpful in this domain. But for a language directed to build applications we need different properties.

27 comments:

Slava Pestov said...

If Lisp and Haskell are too powerful for you and your fellow web developers, stick to Java. But don't waste your time posting ignorant tripe.

Arthur said...
This comment has been removed by the author.
Arthur said...
This comment has been removed by the author.
Arthur said...

Karsten, you seem to have completely misunderstood the definition of functional programming. Yes, you can do functional programming in an imperative language (given enough rope to hang yourself with). Yes, you can do imperative programming in a functional language. This is not news: denotational semantics already provided a functional interpretation of imperative languages. And denotational semantics have historically also been implemented in 'imperative' languages such as Algol. It is also beside the main point you seem to want to make.

You state that monads make functional languages non-functional. That is as untrue as that adding closures to an imperative language makes that language functional. Monads merely provide a structuring mechanism that also allows you to denote imperative constructs. One way of looking at them is in terms of overloading the semicolon that separates instructions in a sequence.

Take that last word into account: sequence. Monads only allow a linear sequence of monadic values to be bound together into one monadic value. Therefore monads most definitely do not allow you to generate any semantics you want.

Further on you seem to want to reclaim the functionality in the functional language, using the world as input to your program. However, any output logically has to become part of the world, therefore the program should be of type world -> world. What is more, the world cannot logically be duplicated by the program. And there exactly is the issue: with referential transparency there is no problem in duplicating any value, as the result of a program does not get changed by it. Therefore, functional programs are normally free to do so. With the world, they should not. And exactly that is what monads allow you to express: you can not diverge from the sequence of functions operating on the world. Therefore you cannot duplicate the world.

Massimiliano Gubinelli said...

Dear Karsten,
I'm quite new to Haskell so maybe I'm really missing your point. As far as I understand in the early days IO in Haskell was approached via two (equivalent) techniques (which I could consider "more" functional): streams and continuations. For example Stream IO would mean that the main function would have type main::[Responses]->[Requests] where the program would lazily read responses and outpur request to the system. Afterwards monadic IO has been accepted as more convenient (and sometimes implemented as threading of the state, e.g. in GHC). For history of Haskell see http://research.microsoft.com/~simonpj/papers/history-of-haskell/index.htm

Single threading can be guaranteed in extensions of Haskell via existential types (see the "Lazy State Monads" article by Peyton Jones and Lanchbury). If I remember correctly GHC implements monadic IO with no overhead (it just do unsafe IO since the typecheker guarantees single threading of the world state). The ST monad work the same.

It is not clear to me that Clean better performance comes form the uniqueness typing but I do not know very much the difference of the two approaches on the compiled code level.

Karsten Wagner said...

@Arthur:
The question is what we want: A language which supports a certain paradigm or a multi-paradigm language with a certain core-paradigm. It's not a problem that we can program imperatively in every language as we can program functional in every language. The question is always how much work we need to do to switch paradigms. By using monads this switching isn't just easy, it even forces you into imperative programming in the moment you want to do I/O.

What semantics are impossible to create with monads? You can transform any sequence of operations to any other sequence. As long as you're code consists of small enough parts it's hard to see the limits here. And combining sequences you can also get arbitrary tree-structures. Of course the usage may become a bit uncomfortable at one point, but for a big number of possible semantics Monads are enough.

What I wanted first was to question if the concept of monads is really the way to go. I don't like meta programming for a reason (I stated those in this article and also here elsewhere) and monads are simply a slightly limited but nonetheless quite powerful functional version of macros: C-macros work directly on text, Lisp-macros work on s-exprs and monads work on statements.

With the I/O-monad Haskell abandoned functional programming in a certain area. And with monads in general it's possible to create other non-functional semantics. This is nice if yo want to try out or play with different semantics, but in application programming (which some people really seem to look down at), simply other things are required.

Also the 'world->world' approach is only one way to do it. I see it as to general for most purposes myself. But I simply don't want to 'give it up' and fall back into imperative programming even if hidden by some clever construct like monads, and so it's necessary to work my way up from the base (where world->world is just the 'point of departure').

But you can duplicate the world. You can even roll it back it. It's quite inefficient if done naively but it's possible to optimize this further. There are still certain constraints but it's more flexible than you seem to think. Yes, the I/O monad limits this - like any imperative model. Thats the reason I consider functional programming more powerful - and thats why I think that bringing back imperative programming thru the back-door is the wrong approach.

@Massimiliano Gubinelli:
It's true that monadic I/O is more convenient. Imperative programming always looks more convenient compared to functional programming. Doing mutation and relying on a certain order of execution gives you more control and this makes programming more easy (at least in the beginning). Having something always seems better than not having it: A language with mutation AND functional evaluation seems more powerful and more convenient than a language where you removed the mutation. But additional features can also complicate things in the long run: In C I have much more control as in Java and this has lots of appeal to certain people. But in the end reduces productivity - and it can even reduce performance if used wrongly.

Now functional programming went long ways to find real functional ways doing I/O (you mentioned a few). Because of this I find it sad that in Haskell they decided to throw all this away and simply build imperative programming back in. Even if they used a clever method like monads. If I stay in the I/O-monad I can program in Haskell like in every imperative programming language out there. It's a bit more cumbersome because the constructs are a bit longer, but I have mutable values, a guaranteed order of execution and standard imperative I/O. Why is this considered a good idea suddenly if one originally wanted to depart from imperative programming?

About performance: I've run into stack overflows in simple looking programms with GHC optimization on maximum which was only solved after I added some strictness operators to the code. This was visible because it was small code for testing purposes. In a bigger program such things can easily be overlooked. If you look at the benchmarks at the shootout, the Haskell code is quite ugly in most instances because of heavy optimization (this is true for other languages too, but in Haskell it's especially obvious). And while 'build-in' monads like I/O can be optimized relatively good, thats not the case with monads like StateT which create lots of closures which won't be necessary with a direct chain-chaining approach (and yes I know, that StateT in fact uses state-chaining, but it hides it and to hide it it creates lots of intermediary data).

And last and least @slava pestov:
Please stop your childish behavior and start to grow up. If you grow up you will hopefully see that your strange elitist world of black and white doesn't really exists.

Cale Gibbard said...

There are some important ways in which monadic programming is different from imperative programming though, even in the I/O monad. Most imperative languages don't give you such ability to glue actions together in new ways. Representing actions explicitly gives you the ability to write your own control structures whose definitions are expanded at runtime. The Control.Monad module is full of such things that are by no means built into the language, and will generalise across all (or wide classes of) monads.

For example, let's consider the function 'sequence', which takes a list of actions and combines them into a single action, producing a list of the results.

Despite the higher-order nature of what it's doing, we can write it in a sort of imperative way:
sequence [] = return []
sequence (x:xs) = do {v <- x; vs <- sequence xs; return (v:vs)}

Or we can avoid the do-notation:
sequence [] = return []
sequence (x:xs) = liftM2 (:) x (sequence xs)

Or even more functionally, removing the explicit recursion, highlighting the transformation replacing the list structure with program structure:
sequence = foldr (liftM2 (:)) (return [])

The ability to write higher-order devices for combining the programs you write is a major part of what functional programming is all about.

In some sense, yes, when you're working in the IO monad, you're writing an imperative program. If you choose to, you can stay on that level. However, you're also writing a program that writes an imperative program, and that's the functional part.

This ability is in no way diminished by the abstraction provided by the I/O monad. The only difference between the I/O monad, and what you'd designed is that the I/O monad prevents you from making a mistake in threading the world parameter (and there essentially is no option there in the case of the I/O monad, because duplication of that parameter would mean that you'd have to duplicate all the resources which the I/O monad has access to, including the network, disk, user, etc.).

I don't really like viewing the I/O monad that way though. It's far better to reason about it in terms of abstract programs which when run will produce values and the monad operations as various concatenative operations on those programs, or else in terms of its Kleisli category: thinking of functions of type s -> IO t as side-effecting functions from s to t.

Anonymous said...

@Slava Pestov: I've long held you in high esteem, but more and more often I see you post insulting crap.

Just because somebody does not like some things about functional programming (and hey, it's all opinion and taste!), does not mean he's an idiot.

I've learned and used many languages, including Common Lisp, SML, Assembler. Now I'm a Java guy who's done with FP + Lisp. Yes, probably that's just more ignorant tripe to you. How could an intelligent person not do FP?

wellsed said...

Karsten, I do not know your background, but it is clear you have misunderstood a few things.

First and foremost, it appears you do not understand evaluation in a Haskell program.
The non-strict (aka "lazy") semantics of Haskell mean that a program does not have an
a priori evaluation order. It is an undecideable problem to determine a Haskell program's
evaluation order without actually evaluating the program. This is a consequence of the
non-strict semantics of Haskell; Haskell is the "standard non-strict, pure, functional language".
The decision for Haskell to be pure forces the necessity of its non-strict nature.

One consequence of this is that a non-strict program is free to ignore its input. It has to nothing
until output is requested from it; this request (by evaluation, of course) may happen very far away from
the place of definition for the function.

You've also not defined "imperative programming". I think we can assume why you (and much of the
functional programming community) feel this paradigm has problems. But what is it?
There is not real general definition for this, but I think we can both agree that it has something
to do with a sequence of program instructions (not definitions) and mutation of state.

However, there seem to be some things which are imperative in nature. You use the example of IO.
I would argue that IO is, by its very nature, imperative. Input is acceptance of data and output
is the IRREVERSIBLE modification of data.

You assert that all operations are reversible. This is DEMONSTRATABLY
untrue. My program cannot return the CPU time it uses and it must reserve memory resources if it
wishes to execute. My program cannot send a packet across a network and then suddenly decide to
recall the packet. My program cannot bring to life a thread it closes. A program based on graph
reduction--like Haskell--cannot be efficient unless it UPDATES its call graph with the values
of its expression. This last one is pretty intersting to me: a pure functional language
depends upon imperative mutation of state to execute.

Some imperative operations
are necessary. You seem to feel this is not so, but it is inescapable. Haskell (even without
Monads) cannot execute with imperative mutation of state.
This is the admission that pure functional languages cannot model all forms of computation.
There is nothing embarrassing about such an admission. However, we can measure languages (on some esoteric
scale) by how they treat this "problem". All of them have to model imperative computations in some fashion.

Most functional languages (and most are strictly evaluated) simply give the user the capability to
change the world at their own whim. The supply weak wrappers around primitive IO (and other) facilities.

Haskell, by way of some very heavy-duty mathematics, models these interactions differently.
It RESTRICTS what the programer can do. You insist this restriction is evil and wrong and to be
removed for its inconvenience. However, with the restriction comes the possibility of COMPOSITION.
We can sequence our operations and we can pass a value from one computation to another. THAT IS IT.
Now, the weak wrappers around OS system calls used by Haskell can be purely strung together and lazily
evaluate. And all of this is hidden so that a program cannot do these things haphazardly.

Monads do not simply hide imperative features. They control two things: sequencing and passing results
(which can still be pure functions or their values). Some things have to happen in a specific order.
Its certainly possible to do this with lazy lists or continuations and many people do such things.
However, monads allows one to hide the tedious operations so that the "meat" of the problem is easier
to express. For instance, how about every time to used a list comprehension you had to explicitly declare
the next computation or how to reconstruct the list. Also, since lazy lists enforce senquencing its easy to
see how they can form a monad.

Now, I've written quite a lot. If I cannot convince you to take a step back and reevaluate your position,
then at least consider one last thing. The minds who put together this language and the monadic constructs
did not do so lightly. The decisions were made based on sound concepts and principles and to give
great flexibility for pure functional programming. It is flippant to declare these people wrong simply because
the concept is "difficult" (though I do not share that view). It is also flippant to claim your "idea" is
better without providing a working model that matches the exisiting model in expressiveness, effectiveness, and
ease-of-use.

Karsten Wagner said...

@Cale Gibbard:

I've just read this document written by two of the Clean developers. On page 26 there is a paragraph which I want to quote (typing errors and the part in [] are from me):

"This system [monadic I/O] is simple but has the disadvantage that all objects to be destructively updated must be maintained by the system in a single state which is kept hidden for the programmer. Clean does not have this restriction. One can have arbitrary states which can be passed around explicitly. Such a state can be fracture into independent parts (e.g. distinct variables for the file system an the event queue)."

This is a big disadvantage because it reduces abstraction: Instead of being able to write code which works on certain parts of the 'world', with monadic I/O it's an 'all or nothing'.

And if you read Wadlers "How to Declare an Imperative" (available here) where he compares different methods of doing I/O in a functional way you see another problem: While the monadic I/O approach is quite simple to use, it has the disadvantage that it can't emulate the other approaches while those can be used to implement monadic I/O.

So monadic I/O is easy to use but also quite limited. Now I'm in principle a 'fan' of certain kinds of limitations and higher abstractions in programming languages, but things are different here: Monadic I/O simply is no 'higher abstraction'! It nothing else but the imperative model of computation implemented by the concept of monads. So it's a step back and no step forward. I would like to see advances in the other direction.

The reason why I see problems with monads in general is a different one: They allow meta-programming and I don't think that meta-programming is a good thing for application development. It's a different thing for certain other domains, but I'm primarily interested in languages for application development (because this makes up the major part of programming).

Karsten Wagner said...

@wellsed:
Haskell is lazy, but of course you can also force strictness (by using the seq-operator). And if you would write a program which returns some value the compiler would enforce that this value is really computed - or the whole program would end completely unevaluated. And of course I know about all this - if not then I wouldn't wrote about how interaction could be done by lazy evaluating input and output. So I have to ask you: Have you really read my article?

The reason why imperative programming has problems is concurrency. It's a kind of overspecification: If you say that a program has to be evaluated in a certain way, the compiler has to do this. But if a program don't really need this order then our code in overly specific and this reduces opportunities for optimization - including automatic multi-threading.

I/O may be imperative by nature, but software isn't 'physically', it's conceptual. And so it can do things which are impossible in 'real'. Of course there are limitations. You're right that in general it's impossible to undo the sending of a packed over a network. But if you use the right software on both ends of the net it is possible: Simply put a 'undo-command' in the protocol.

Everybody who've used software knows that undo/redo is a quite common facility of software: I can for example undo the state of my
software projects to an earlier version and work with two different versions in parallel and later merge both versions. Something like this would be impossible in the 'real world', but with software it's no real problem. And because of this it would make sense to build in something like this directly into the evaluation paradigm of a language instead of simulating it by difficult to use patterns like necessary in OOP. Functional programming can really shine in those situations - unless someone destroys it by building imperative sub-languages into the language.

And as long as functional languages are executed on an imperative processor, it's no wonder that they need imperative operations for their implementation.

I don't think that restriction is evil. I've even posted articles which praise certain kinds of restrictions because they improve productivity. The whole idea of functional programming is restriction: The removal of mutable state.

Monadic I/O is simply a wrong way of restriction: It don't creates a higher-level abstraction, it simply ensures that the programmer can't break out of its simple imperative model. Every imperative language does this! It's nothing new, nothing 'high-level'!

If you're still not convinced that my position has at least some validity, look at different languages with do I/O without monads (like Clean or Mercury). If it's really so simple, why don't have the creators of those languages chosen to use monads too.

I'm not promoting 'my' idea here, I only wanted to have an example how to do I/O without monads. Only saying 'monads are evil' without providing a way to do I/O without them is a bit easy. But in the moment I've concentrated primarily on the disadvantages of monads while I had not much time to present real alternatives. You can look into the mentioned paper from Wadler for some possibilities, but I think there are more.

nmessenger said...

Karsten, don't mind Slava too much. People are likely frustrated because of the numerous completely false assertions you make about Haskell, so it's very difficult to take your post seriously. The most egregious is the repeated assertion that the IO monad breaks Haskell's referential transparency. This is false. The existence of IO doesn't break referential transparency, it in fact enforces it. The existence of a nonstandard function 'unsafePerformIO :: IO a -> a' is what breaks it.

Consider the following:

main = x >>= y >>= z

When this program is executed, a dummy value that represents the state of the World, which I'll call world0, is created and passed to 'x'. 'x' then can call impure code, which from a functional standpoint is equivalent to creating a new value of the World type, world1. 'world1' is passed to y, creating 'world2', 'world2' to z, creating 'world3'. Thus, this program is a transformation from world0 to world3. Given the same world0, it will always produce the same world3. This is referential transparency.

From your replies, I gather that you don't want the IO monad to abstract away your World-passing. You want more control over this World, to get access to it, to split it, to re-use old copies whenever you please. This would require either: time-travel (an unsolved problem), or an actual representation of the state of the universe (an infinitely recursive task, not to mention memory-hogging). If you send a character to stdout, it's not terribly difficult to simulate the old copy of the World in which you didn't, but if you send the LaunchMissle or NuclearMeltdown hardware signals, it gets more difficult.

(an small aside, to back my assertion about unsafePerformIO:) The reason unsafePerformIO is not referentially transparent is that it destructively updates whichever World value is currently in the main action chain, while posing as an ordinary function.

wellsed said...

Karsten,

Its fair enough to have your own opinions, we all do. Its very fair to criticize language features.

What's not fair is that your arguements for such criticism are grossly incorrect. However, I had not really taken time to understand Clean's IO system (to much to do as it is), but I'm doing so now.

In the meantime, I've found a lovely paper detailing an attempt to port Clean's Object-IO library to Haskell back in 2000. This was soon after the "great monadic revolution" in Haskell. I've not yet finished the paper, but it promises a good discussion about the differences between Clean's uniqueness typing and Haskell's monadic IO (new at the time).

If you also like to read along, it can be found:

http://citeseer.ist.psu.edu/330823.html

If you're not familiar with it, CiteSeer is a great site for finding computer science journal papers.

wellsed said...

Karsten,

As a separate note: you seem convinced that all actions in the world can have undo/redo semantics.

This is observably untrue. Some things cannot be undone.

High-level languages depend upon garbage collectors to free memory from unreferenced data structures. This is a destructive action that cannot be undone. If garbage collection could be undone without limit the program would quickly overfill its heap allocation. Even if we allow the program to access the computer system's memory to capacity, eventually a program would run out.

A second example. If I create a game that draws graphics on a computer screen what I'm realling doing is changing the state of a framebuffer. If I intend my computer to ever display something, I must accept that most of my actions cannot be undone when I draw to the framebuffer. Some actions, in theory, can be undone by rewriting the relevant parts of the framebuffer without the effects of my actions. However, this cannot happen indefinitely, else the computer screen will not display an updated scene and the user will quit playing my game.

We can keep going on with such examples. They are easy and trivial and they demonstrate that not everything can be modeled as a undo/redo.

Karsten Wagner said...

If I make a false assertion (which is totally possible, has happened and will happen again - like with every human) I'm happy to be corrected. If somebody can't stand this, he shouldn't read any blog anymore.

I'm totally convinced that functional programming is a very powerful thing with big promise in the future. But I also think that not everything in the area is a good idea. Everybody who is interested that functional programming can be the paradigm of the future, should help to find and to solve those remaining problems.

So please excuse if I continue to write about this - and if I made a mistake please point it out.

About the topic:

First: I wrote that the I/O-monad is 'evil'. Sometimes there are necessary evils, but even then they remain evils. The article had the intention to ask if there are really no better ways than accepting a certain one of those evils as necessary. I'm not really sure about this yet myself, because it is a difficult topic - but one thing is for sure: If we accept it, we won't even search for a better solution. And without searching first, chances to find something are very small.

The IO monad breaks r.t. in Haskell because you can't specify the 'world': It's hidden somewhere in the compiler. This is totally similar to an imperative language where you can also say: "There's an invisible 'world' somewhere which is fed into the program as a hidden variable and than modified in a r.t. way.". But thats as equally nonsense as talking about code in the I/O-monad as r.t. As long as you are in the IO-monad you have a non-r.t. language! If it is simulated on top a a pure functional one or if it is implemented non-functionally simply doesn't matter - like it doesn't matter how you evaluate any other imperative language in the end. What counts is the semantic model of the language and inside the IO-monad it's for sure an imperative (and thus non-r.t.) one.

Now we could ask if there are better ways to do it. Some years ago this question seem to be a much more discussed, but since the invention of monads (in the functional-programming-sense) this discussion seem to have disappeared. Because most people in the field seem to acknowledge that the 'awkward squad' remains a problem for function programming and by using monads to hide this under the carpet it seemed a good idea to stop thinking about it.

But a big problem is the monolithic structure of the Haskell-'world' which captures everything in one object. If it would be possible to split it up, then in many cases I/O would be easily undoable: If a program reads a file and writes to another the system could simply create a hidden-copy of the output file and copy it to the real file in the moment when it's sure that no 'undo' is possible anymore. And it would be a good idea to reason about all this. For example if its statically decidable if an output stream can securely written to the terminal because no undo is possible and if this creates deadlocks in a certain interactive situation (which should be flagged as an error then).

But instead of doing this, certain people seem to find it more adequate to shot the messenger instead of tackling the real problem and search for a solution. Even worse: They seem to close their eyes and deny that the problem even exists.

Karsten Wagner said...

@wellsed:

> What's not fair is that your arguements for such criticism are grossly incorrect.

Then please show where they are incorrect. If I'm so obviously wrong, then this should be simple.

And of course I know about CiteSeer. Do you want to insult me?

Btw: Have you read Wadlers "How to Declare an Imperative" (can be found here)?

> This is observably untrue. Some things cannot be undone.

Sure. But this also not all things which have to do with I/O fall into this category. Lets isolate those which do and which do not and create different abstractions for both, because they both are different.

> High-level languages depend upon garbage collectors to free memory from unreferenced data structures. This is a destructive action that cannot be undone.

That's the reason why data is not freed until it can be proved that the data is unreachable. This works well together with backtracking/undo/ etc. because the gc considers these informations too.

> If I create a game that draws graphics on a computer screen what I'm realling doing is changing the state of a framebuffer.

Yes, and if you choose to undo it, you simple redraw the old graphics. Just think about the right abstraction. A simple solution would be to store the frame-buffer somewhere - but the program would run out of memory soon. So we need to create data-structures which contains the drawing actions and by applying such an action in the right sequence, we create our graphics. To undo a certain part of this sequence, we simply replay it to the new state.

So while there are real example which can't be undone, your examples are both very easy to represent way which allows to undo them. But first you have to get rid of the imperative program model you seem to have in your mind.

Ed said...

>And of course I know about CiteSeer. Do you want to insult me?

No insult intended. We are both relatively anonymous people, so we have no a priori experience of each other's knowledge.

>That's the reason why data is not freed until it can be proved that the data is unreachable. This works well together with backtracking/undo/ etc. because the gc considers these informations too.

If you keep an undo/backtrack action attached to information to be garbage collected, it cannot be freed. There are still references to it. Additionally, if there is no other reference to it other than some "backtrack" info, there may be nothing to backtrack as the relevant operations could have mutated farther along. Of course, we keep "backtrack" info on those operations . . . until we run out of memory. So, somewhere along the way we have to free memory or run out. That is irreversible.

>Yes, and if you choose to undo it, you simple redraw the old graphics. Just think about the right abstraction. A simple solution would be to store the frame-buffer somewhere - but the program would run out of memory soon. So we need to create data-structures which contains the drawing actions and by applying such an action in the right sequence, we create our graphics. To undo a certain part of this sequence, we simply replay it to the new state.

You've missed my point. If I intend someone to be entertained by this game, it must display new information on some regular basis. Even if I wanted to keep a compete record of every frame displayed to the user I would probably run out of memory to store such information. Much like the garbage collector, it must be released.

>Sure. But this also not all things which have to do with I/O fall into this category. Lets isolate those which do and which do not and create different abstractions for both, because they both are different.

Fair enough criticism, and has been directly implemented in Haskell libraries. Many things are in the IO Monad, but not everything.

For instance, the STM monad duplicates a lot of things inside the IO monad, but its implemented separately for just the reasons you mention. They (SPJ and crew) wanted to make sure that IO cannot happen in the midst of a transaction, thus the STM monad is not built using the IO monad.

I think you've stumbled in the old Haskell arguement about the IO monad being the language's "sin bucket". Its where things get thrown when there doesn't seem to be a better place for them. Its an old arguement and fair, but there do not seem to (yet) be clean solutions.

Karsten Wagner said...

> If you keep an undo/backtrack action attached to information to be garbage collected, it cannot be freed.

Like in every application which uses undo/redo. Nonetheless most applications use it. So it's obviously a solvable problem.

> as the relevant operations could have mutated farther along.

With r.t. there is no mutation, so this can't happen.

> So, somewhere along the way we have to free memory or run out. That is irreversible.

Yes, but not in principle but in practice. And even then we can write those data out to external storage and increase the amount of backtrack informations tremendously.

But most often it's not necessary to store the whole information. Look at Parsec for example. It uses input and has nonetheless full backtracking. And in the most cases it don't have to store the whole file if parses in the moment. The reason is that the gc can free those data in the moment it's for sure that there can't be backtracking to a certain earlier state. This is simply implemented by the try operation which stores a reference to the data. No 'try', no need to store it. So by specifying parsers in a reasonable way, we have the 'illusion' of arbitrary backtracking without needing to much memory.

In the end there has to be mutation somewhere. As long CPUs are working in an imperative way, the code has eventually executed imperatively and of course on this level we have all those nasty things like mutation and irreversibility. But I'm talking about the 'virtual world' a functional languages shows the programmer, not the nitty-gritty of the implementation on assembler level.

With the right abstractions, the compiler can decide when it's safe to throw data away, because it's visible from the structure of the program it's impossible to need those data. This decision should be made preferable statically, but it's often made dynamically (like in gc) which is less efficient. There are solutions to the problem which work statically but there's much work to do on the field. One reason that it don't work well with todays languages simply are the languages itself. Like it's impossible to determine at compile time which function to call in most dynamically typed languages is a result of the language definition. Add the right type system and the compiler can decide it. The same can work for memory allocation and freeing. And with the right type system it also can determine if there is the possibility of backtracking.

In Haskell they solved the 'function call' problem quite nice with a rather powerful and still flexible type-system. But the problem of memory allocation and evaluation order is still decided mostly dynamically. This has to change.

> You've missed my point. If I intend someone to be entertained by this game, it must display new information on some regular basis.

And you missed mine: You can put Informations on display and still undo it, as long a the computation which lead to the display is undoable. You don't need to safe the content of every frame. Many of todays games have a 'demo-record' mode which works this way: It only stores a minimum amount of informations while the graphics engine still calculates the whole display again and again. Otherwise it couldn't store an hour replay of a game with hundreds of simulated entities on screen in a few MB.

Of course all data have to be released at some time, but thats not the point: If I can program in a way that computation is referential transparent this don't mean that I can always go back by storing certain informations somewhere. If I have for example a r.t. computer-game-engine, I simply need to memorize the user-input and can always create the same game from it, because this input is the 'world' on which the game works. Which data to store and which not is still in the realm of the programmer. But compared to imperative programming, it's much more easy to do. But this choice doesn't exists with the I/O-monad (but you can implement it by yourself on top of it) and the reason is simply that it's not a functional but an imperative language.

The STM is only to provide mutable state, nothing more. And it's quite slow and uses up lots of memory. So many performance critical applications don't uses the state monad. Chaining state thru functions calls is for example much cheaper (yes, I know that the STM does this in the end too, but the machinery required to do this costs a lot, just look at the implementation and follow the evaluation chain).

And in the end you seem to admit that the I/O-monad is really only a necessary evil. This is what I wanted to express with the article.

wojtekk said...

Karsten, I'm afraid you've mistaken STM monad with ST monad in your last comment. They are different things for different purposes.

Alberto said...

My experience with monads is limited, but, as far as I know, the "do" transformation into >>= operator sequence and the operator transformation into standard function call notation is done at compile time, not at runtime. There is no difference in performance and lazines with pure functional notation. The code generated in fact stays functional.

In Monads, the sequencing of operations is guaranteed by the evident rule that even in lazy pure functional languages, f(g(h x) implies a sequence in with h is evaluated before g and g before f. This sequencing is used to perform IO sequences while assigning a "impure" type-mark to the result, so that this piece of code can interact coherently with the non-IO code.

But also this sequence can be used for "pure" purposes, like state handling in sequential processes. So laziness and "pureless" are not necessaryly lost in monadic code by the inherent nature of monads, but in the laziness, impureless of the code executed inside. Monads only provides a elegant notation for sequencing that can be done also with much more ugly non monadic notation. With no loss of performance.

Referring to stack usage, I believe, but I can not demonstrate, the monadic code is similar to recursive code in some ways; It has nested function calls. Depending on the nature of the monad, it may be tail "recursive" like IO monad, where each action is completed before passing the value to the next in te sequence, or (I have no example of this yet). Then, the first action may need data from the last one, maybe. In this case the stack may grow dangerously. Anyway,even if this last is possible, the stack usage is not inherent to the monad concept but the code inside the monad.

Am I wrong?

agcorona

Raoul Duke said...

@Karsten, I don't have anything concrete to add, but want to say I appreciate you thinking out loud and questioning things. Please keep doing that, we don't need everyone to be complacent.

@Helpful others, I also appreciate you being willing to engage with Karsten to figure out what the middle ground is (apparently namely that IO is the sin bucket).

Both of you help folks like me think a little wider and maybe learn something, even if you aren't 100% right to begin with.

sincerely.

uncial said...

Hi, Karsten,

I am certainly a Haskell newbie, but I've always understood the monadic IO issue in this way:

1. Impure (side-effectful) behavior is inevitable; we use computer programs because we want something to happen in the real world (e.g. my resume to be printed on my laser printer).

2. Pure functional programming (whenever possible) is good because RT allows me to reason effectively about my design.

3. Monadic IO is a device which uses the type system to enforce one-way separation of impure actions from pure functions (actions can evaluate functions but functions cannot invoke actions).

I chose my example in item 1 deliberately. While we might debate the reversibility of displaying data on an LCD or committing a transaction to a database, once we enter the real world the second law of theormodynamics (at least! ;-) takes over.

In practice, it is not possible to recover the toner from the paper coming out of my laser printer, to un-burn the fossil fuel consumed to deliver the book I ordered on-line, or to reverse the medical effects of increasing my reader's blood pressure if I post my argument too stridently!

My comments above were strictly about the IO Monad. I'm still pondering some of the other consequences of the monadic style. I'm sure you're familiar with Wadler's paper which uses the monadic style to encapsulate changes to a simple interpreter in an interesting way. I wonder if you would regard that kind of encapsulation of "partial world state" in the same negative way. It seems to me that he uses monadic style in that example as a powerful tool to encapsulate code which could otherwise be written in a purely functional fashion.

Peaker said...

I think you will identify with Conal Eliott's work, which shares some ideas about I/O's and Monads.

For example, this piece trying to use satire in order to explain that using the IO type is indeed not "purely functional programming":

http://conal.net/blog/posts/the-c-language-is-purely-functional/

And of course, his work on FRP (http://conal.net/blog/posts/simply-efficient-functional-reactivity)

Russell said...

IO is no less pure than your world-passing alternative. Bind /is/ referentially transparent. In your first example, bind simply chains the actions together. It doesn't execute anything. These actions are passed around without ever losing any purity. The second bind you mention doesn't exist. Monads are no "trick"- the runtime takes the evaluated main action and executes it, not bind. You couldn't just create a "Java-monad" either. Monads won't give you classes or while loops, and you'd still need to use pure functions to get any real work done.

Look at Writer. runWriter takes a Writer action and returns the result and the written log, and it's referentially transparent. The only difference is that IO's "runIO" function is the runtime, part of the compiler, which /your approach needs anyway/- at some point, your returned world needs to be applied, which is most definitely a side effect, even at the high level of the functional paradigm. This is a true intrusion of mutable state, not just the fact that the CPU is imperative.

On the other hand, Clean is /less/ pure than Haskell because of its uniquness typing. This requires some kind of state (which values have been used?). Monads are a natural solution to IO that keeps side effects in exactly one place- the "runIO" procedure. Your version of world-transformation is exactly what the IO monad encapsulates. It's state-chaining, and it's referentially transparent. You claim to want a purely functional language but then you say you dislike metaprogramming, even though higher-order functions are a huge part of the functional paradigm.

You say monads are hard to understand. They are definitely tricky to grasp at first, but once you do understand them they are far more useful than explicit state-chaining. They are state chainers implemented as functions. The Writer monad, the STM monad and even list comprehensions (even List is a monad) speak loads about how powerful monads are. Monads may appear to create different semantics, but it's all the bind function. You can't create while-loops or classes, you just chain state and sometimes transform it. Monads simply encapsulate a common pattern that you would have to use anyway- your imaginary world -> world functional language would eventually grow monads.

ShowPony said...

I agree with the main point of this post. You see many times I see clever programmers sacrificing readability for by using monads to save a few lines of code. Like the author says, monads like lisp macros can result in elegant code but at the expense of a reader who is not familiar with the given macro or monad. However, no one can deny the sheer beauty and elegance of a well designed monad and the ease in which they are created once you understand how to use them.

shelby said...

I agree with Karsten about IO monad, and I explained it in a different way in a post which followed this one:

http://apocalisp.wordpress.com/2011/05/30/imperative-vs-functional-programming/#comment-4561

It was censored, but I have a copy here:

http://goldwetrust.up-with.com/t112p180-computers#4434

shelby said...

I have refined my understand, which is explained at the following link:

http://goldwetrust.up-with.com/t112p180-computers#4434

As Peyton-Jones elucidates in "Tackling the Awkward Squad", IO Monad is simply (one of) Haskell's way(s) of mixing impure, imperative code with pure, declarative code. To the extent that you can make your interface to the world declarative, i.e. pure functional (reactive), then you don't use IO Monad. But at least until the world (i.e. the OS) becomes pure functional, then we need a "wrapper" on our pure functional core-- which is IO Monad.

I gained clarity in the summary of my current open source project, which goes into more detail on this issue:

http://Copute.com