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.

Real functional programming or "Why the IO-monad is evil"

Edit: This article contains some errors and wasn't able to transport my intention correctly. So I've created a new version of this article which hopefully contains less errors and is better to read.

---

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 really be the qualifying property of a language, what else is it?

Of course it's the "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, so it's not a function anymore. It's something which is often called 'procedure': A block of code which creates a result by applying some algorithm. 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 in every language we can use procedures to create functions (just by making sure that there are no side-effects), but those languages aren't still called 'functional' only because the programmer can force himself to use them in a functional way.

If this would be enough, we could also call assembler a functional language, because we can use it to write functional code too. The same would be true for every other paradigm, Assembler would be for example an object-oriented language too (And this is of course true for every Turing-complete language, not only of Assembler).

But with this rigorous definition of the notion 'functional', there aren't many functional languages anymore. Ocaml for example is clearly non-functional now - and even Haskell isn't. So should we maybe lift this requirement a bit? I don't think so.

Why isn't Haskell a functional language? The reason is the IO-monad. To do I/O in Haskell there are functions which aren't referential transparent, because they return a different value at each invocation. If we write

   let v = getStr in ...

v is bound to a different value at each invocation. Even if this value is contained in the IO monad, it's still a different value, because we can write code which runs different on each invocation. This creates some kind of avalanche effect which can turn huge parts of the code into simple imperative code - and because of this, we can't talk of Haskell as a functional language. Even if we want to create pure functional code, it's not possible in Haskell in the moment we need I/O (and which program doesn't?).

That's the reason why I consider the IO-monad as 'evil': Haskell relies on it and thus isn't functional anymore.

But is it possible to do I/O in a really functional way? If it's not possible then the idea of functional programming would be deeply flawed and should maybe even abandoned for practical programming. What use is a concept which works only in theory and fails in the moment you want to do something as common as I/O?

But fortunately it is possible. The idea is to put all the external input of a program into a 'world'-value and then call our program with it:

   result = app(world)

If 'app' is a command-line application for example, then 'world' would represent all the input the program receives and 'result' would be all the output the program generates. This is quite an easy concept, but how would it work if we need interaction? The idea is to use lazy evaluation: Instead of reading the whole 'world' before calling 'app', 'world' is only evaluated on demand. The same is true for 'result' which is written out in the moment data becomes available and not at the end of the program. So our program could give back a partial result (for example an input prompt), before even requiring any real input.

This would work for GUI-programs too. We can for example put all the mouse/keyboard/etc-events in the 'world' object and 'result' contains all the drawing-commands the applications issues. This approach would create a very distinct structure of the program, because input and output are now clearly separated.

This works well for some problems, but often there is some 'natural' interaction between both. Your simple command-line application may for example open, read and write some data-files, based on commands issued by the user. We can not create a simple function like 'readFile(file_name)' because this 'function' could give different data at each invocation and is thus no function. So how to solve this problem?

The answer is to put all 'external data' into the 'world' object: All files, all system resources etc. Of course this also works with lazy evaluation so those data is not really read and put into a value. The 'world'-value behave just as this is the case. And if we now start our application with all those data in the argument, it would again give the same result as long as the input value is the same too. If we only change a single character in a file which is contained in the 'world', the value isn't the same anymore and so we could get a different result.

The advantage of this approach is that we can limit out 'world-value' to the parts of the system which can be accessed by our 'app'. If we don't want that 'app' can read a file for example, we simply don't put the 'file-system' into the value. This allows very strict security constraints on data access in a very natural way. And our 'app' is of course not a big monolithic function but calls other functions which in turn call again other functions etc.. So we can give those other functions limited subsets of the world-value to limit their access, too.

This approach is truly functional and also very natural: An application simply transforms one 'world-state' into another.

And there is an additional advantage of this approach compared to monads: Higher performance.

To use the plain IO-monad, the language isn't referential transparent anymore. So many of the nice and clever optimization techniques for functional programs can't be used anymore. Using the IO-monad forces a certain order of evaluation and also disallow caching of already calculated values.

But even if you use other monads to simulate state, the result isn't really as fast anymore. The result is that monads are constructors and can only 'give' some value. But how can we create and modify state, if we can only return values and have no 'input'?

With state-monads it works this way: Instead of transforming input-data (which contains the old state) into output-data (which contains the new state), a state monad returns a new program. It doesn't do transformation on the data but on the program itself! In the end this transformation does nothing else then transforming the code into 'transformer-style' code which gets the state as input and creates a new state as output. It does this by putting chunks of code into closures and chaining them together using the 'bind'-function. So if you use a state monad in Haskell, the state monad does nothing more than a code-transformation and then evaluating this code which in turn chains a state-value thru the invocations.

But this transformation and evaluation is done at runtime! Sure, sometimes it can be cached or even unrolled at compile-time, but only in rare cases. The reason is that the 'to transformed' code is dependent on the input values of a function which can (for example with a if-then-else construct) create a different kind of code every time. The Haskell compiler can't resolve this in most non-trivial cases and thus the whole code-transformation and evaluation has do be redone over and over again. This costs time and also often even kills tail recursion. So by using a state monad we often have much less efficient code than by using the transformer based approach directly

A language which does I/O by the transformer approach (but in a different way as proposed here) is Clean, and if you look the benchmarks at the shootout, it seems clear that there is really a performance advantage here.

And whats the disadvantages? Of course there are some, or else nobody had even considered to use monads instead.

The main advantage of monads is that they are in principle code transformers. With monads we can create embedded DSLs, similar to Lisp-macros (But since monads do this code transformation at runtime, it costs time and memory, while Lisps macros are evaluated by the compiler before creating the real code). Having the ability to create new 'embedded languages' has some appeal on many people. With the transformer approach this isn't possible - but of course there are still other ways to do this, if it's really wanted.

The second disadvantage is that the transformer approach requires an additional parameter in each invocation. Instead of writing

do
   a <- getStr
   b <- getStr
   putStr $ a ++ "," ++ b

we have to write

let 
   (a, state) = getStr state
   (b, state) = getStr state 
   state = putStr state (a ++ ", " ++ b) 
in
   state

instead. This look pretty obfuscated compared to the Haskell approach. But the reason is that Haskell has syntactic support for monads but none for the other approach. If we had to write the first example without the syntactic support the 'do' construct provides, it would look even uglier than the second one (just try it, it's also a good practice if you are new to monads).

So why not simply add syntactic support for the transform-approach too? What about this:

with state let
   a <- getStr
   b <- getStr
   putStr a ++ ", " ++ b

This is quite short too, and the 'with' syntax can be used by the compiler to use the function type to chain 'state' it thru all calls which have a parameter with a matching type and also return a value of the same type.

The last disadvantage is that the transformation approach need additional semantic support. Why? Because lazy evaluation alone isn't enough. We often need a certain order of evaluation to read and write data in a certain required order. Often this order is 'automatically correct', but sometimes it isn't.

For example (without the above proposed syntax to make the problem more clear):

let
   state = putStr state "Please enter your name: "
   (state, name) = getStr state
   state = putStr state ("hello '" ++ name ++ "', please enter your age: ")
   (state, age) = getStr state

If we evaluate this statements, the program will write

Please enter your name: hello '

and wait for input. Why? Because the 'getStr state' line isn't evaluated before 'name' is actually required. That's the funny thing with general lasy evaluation: Sometimes the evaluation-order can be quite unexpected.

How so solve this problem? There are multiple solutions. First we can replace the '++' after "hello '" by a strict variant which requires evaluation of both parameters before it continues. This would force the program to the wanted behavior, but it would also require additional thinking by the programmer.

A better way would be to create an internal dependency between data. For example 'putStr' and 'getStr' would create and check a dependency on 'state' which would force evaluation of all previous 'putStr' before a 'getStr' can occur (and vice versa). This would only fore evaluation order into a certain form, but each of the functions would remain referential transparent. But there has to be some compiler support to support this feature.

So I/O is possible, in a totally functional way and with some support from the language even in a relatively simple way. Without monads we lose the possibility to create embedded languages, but I think that this isn't really a big disadvantage. But for I/O monads aren't necessary and even harmful.

What makes a programming language 'more productive'

First: What does 'productive' mean? I would loosely define it in the context of programming as "Given two equally skilled programmers or teams of programmers, the less time they need to create and maintain a program for a given problem, the more productive is the implementation language".

This definition may have some holes in it, but I first want to make clear, that productivity for me is not an abstract thing like "code beauty" or "conciseness", its simply outcome oriented. If you're able to create a program in a consistently shorter time by using a certain language or framework compared to another, I think it's a good idea to consider it as 'more productive'.

What's the secret of productivity? In fact its utterly simple: Code reuse.

That's it? Code reuse? What about powerful abstractions, concise code or clean and powerful language design? Doesn't matter (unless it leads to better code reuse)! Let me explain:

If you have to solve a problem you have to think about it first. This takes a lot of time. You also have to think about it while you're implementing a solution and later while debugging or maintaining your solution. Thinking about the problem generally requires the most part of the time in software development. There's only one way a programming language can solve it: By providing an existing solution. Sure, there are simple cases where you only have to type a simple solution in without thinking about it much. But even then: If you don't have to write the code yourself and reuse existing code it's simply the fastest way to a working result. Existing code is

It doesn't even matter how powerful a language is: If you can build your solution on existing code with only small and easy modification, you will be faster then using the most powerful language. Also existing code is already debugged and tested. And if it's from a 3rd party developer you don't even have to maintain it.

But code reuse isn't always identical to 'using a framework' or 'importing a lib'. Sometimes it's build right into the language: When I switched from C++ to Java I experienced a huge productivity gain. A big contributor to this was garbage collection. Instead of thinking about memory allocation, when to release an object, how to write a fast custom allocator, allocating data on the stack or on the heap etc. I no could allocate objects without thinking much about it. I could simply consider the problem as 'solved' by the language.

Something like this happens on many more occasions: I can create classes in C, but by having the language do it like in C++ or Java, I can consider the problem 'solved'. In assembler I have to create function calls and local variables myself - in a higher level language this problem is again solved. All this is code reuse: Somebody has looked at common programming situations ('patterns') and created a universal solution for it. Sometimes this solution is directly incorporated into the language, more often it's put into a library. But nearly always both ways are possible, so it doesn't make sense to call code reuse which is part of a language a 'abstraction' and code reuse from a library simple 'code reuse'.

So the reason why certain languages are more 'productive' that others is code reuse. C is more productive than assembler because we don't have to think about allocating variables or building stack-frames. By having the problem solved we don't need to think about it, we don't need to implement it again and again and we don't need to search for bugs which result from making mistakes by doing it ourself.

Now we can try to identify the reasons why certain languages are more productive than others, and why sometimes even more powerful looking languages don't deliver.

Lets first look at Java. I mentioned that my productivity increased a lot after switching from C++ to Java. Besides the already mentioned garbage collection, the huge number of available libraries are another part of the reason. A interesting question is: Why are there so many libs for Java? There are other languages which had huge commercial support but never had as many reusable code as Java. Why?

If I want to reuse code, the code has to fit into my existing code. But more important: It has to fit into the code of other vendors. If I create a program which uses 5 different libs and some 1000 lines of my own code, writing my own code in a way that it fits to the libs is possible - but this doesn't solve the problem of fitting those 5 libs together if all those are written independently. To make code 'fit' it has to use the same conventions, similar interfaces and standards. This works much better if the language enforces it.

One example is garbage collection: When I used C++ there where multiple methods of doing memory allocations. Many used reference counting, but since there was no standard implementation, each lib used their own one. But how can you combine two libs which both have their own ref-counting scheme? In Java this was a non-problem because the language has solve the gc problem.

But there are other examples. Like having standard libs for most of the basic stuff. If two libs use their own array implementations you can't simply use an array from one lib in the other. But if the standard libs provide something it's unlikely that every vendors creates it's own solution.

But it continues on a higher level: If two libraries use different methodologies to solve a similar problem you will get an impedance mismatch if you try to use them together. Maybe one is written in a more procedural and the other in a more object oriented way: Now you need lots of boilerplate code to make such code work together which in turn makes reuse harder.

Java tackled this problem by removing abilities from the language to enforce a certain way of programming. If there is only one sensible way to do something (because other ways are artificially made much more difficult) the programmer may curse the language for this in the moment, but at a later time he may be happy about it because it allowed him to reuse the code in a different application. And that possible because the language enforced a certain way of solving things.

And if independent programmer creates libraries without even knowing in the moment who will use the libraries later, it can really help if they are forced to use a certain methodology, even if it may hurt at the moment.

So while Java really has it's downsides, in the regard of code reuse it really made a lot of progress compared to many earlier languages. So if we want to create better languages we always have to consider this lesson we learned from Java: Having a powerful language alone isn't enough to gain productivity if the language neglects code reuse. Even a less powerful language can fly ahead a more powerful one if it encourages and eases the creation of reusable code.

But time has moved ahead and many ask if its possible to reach the goal of better code reuse AND have a more powerful and more concise language than Java? I'm sure it is, but only as long as we have the idea of code reuse in mind. Creating a language with only 'clarity', 'conciseness' or 'power' in mind isn't enough, we always have to think about how it's possible to enforce the creation of reusable code in this language. Yes, we need to enforce it. Not because programmers are stupid or deliberately write un-reusable code, but because only by enforcing we can be sure that two teams of developers who don't know about each other can create code which will fit together later if reused by a third team of developers. We simply need rules to make their work fit together.

But this leads immediately to a conclusion: Multi-paradigm-languages won't work. While it looks as a good idea to give programmers more freedom to express their ideas, this in turn leads do code which is to different to fit together.

(I suspect that this is the prime reason why Lisp never made a real breakthrough - but also why there are some success stories with Lisp. If you don't need to reuse code (for example if you work in a new field where simply no code exists) Lisp can give you a big productivity gain and create a nice success story. But if a language like Java can play out it's code-reuse card than the gains are irrelevant because the Java programmer simply puts some libs together while the Lisp developer is still thinking about which libs there are on the market and if it's possible to integrate them into one design or do a new implementation instead).

But multi-paradigm isn't the only 'no-no'. Making languages to customizable is another one: If a language can be easily customized by macros, reflection, template meta-programming etc., this can also reduce code reuse: If we want to integrate two libraries which both use and rely on lots of those customizations, it's quite probable that those customizations won't fit together. It can work but often it won't.

This is not only true for 'real' meta-programming like macros or reflection, it can also happen with 'to flexible abstractions'. Lets take a short look at Haskell's monads: They are very powerful - but this leads to problems. If you have code which uses a A-monad and want to fit it together with code which runs in a B-monad, you get problems. And if some 'monad-free' code requires to be run into some monad later you maybe have to rewrite it completely, even if only a very small portion need access to the monad. This can be quite annoying if you have to rewrite your own code - but if you have to reuse 3rd party code it can even render it impossible.

The problem here is not the monad concept itself, its the choice you have to use it or not. The choice creates the possibility to go different way - and using the wrong way can lead to lots of rewrites or reimplementations you have to do instead of simply reusing existing code.

So the secret of successful code reuse is to "removing choice". But thats something which seems unswallowable for many programmers, especially those who consider them selfs 'hackers'.

If you are one of those, let me ask you a question: Would you like a game like chess more if there are no fixed rules and you could do everything? I doubt it, the fixed rules are just the reason why chess is interesting: You have to solve problems in the context of a fixed and rather limited set of rules. If you could simply win by hitting your opponent over the head with a club, chess would loose lots of it's appeal, wouldn't it? So just look at the 'choice problem' in a different way: If there is a limited set of ways to solve a problem, can't this not even makes it more interesting to solve it?

And to the language designers: Isn't it an interesting problem to create features which are expressive AND lead the programmer in a certain direction? Simply putting everything into a language is not difficult (think of Homer in the Simpsons Episode where he designed a car). But it's also simply just to remove things: Creating a language based on a single easy concept is simple too. And a dynamically typed language is much more simple to design than a language with a good static type system. If you really like the challenge then design something new, something different, something difficult.

A language which allows for good code reuse don't have to be simple, it has to force the user to solving problems in a certain way without limiting him to much. This sound like a contradiction and yes it is, but thats the difference between theory and practice: We always have to do compromises or we create things which are good in theory but unusable in practice.

The problem of dealing with data-structures

It seems to be a 'solved problem': How to represent and use different kinds of data in programming languages. But in fact there's lot of unnecessary complexity and lots of artificial difficulties if you really think about it.

Lets just look at an example (It would look similar if I use the Hindley-Milner type system but it's just about the basic principles not about a certain implementation. I think that Java is common knowledge today and so I'll use a Java-like syntax).

Let's start with the following basic structure:

   
class Customer {
 String first_name;
 String surname;
 
 Address[] addresses;
 Invoice[] invoices;
}

class Address {
 String postcode;
 String city;
 String street;
}

class Invoice {
 Date date;
 Date date_payed;
 Currency value;
}

This allows us to represent 'Customers' with 'Addresses' and 'Invoices' in our system. The above structure is very clean and easy to understand - but also totally useless. Why? Because we also need ways to query the structure above. For example we want to access all invoices in the system to create reminders. Or we want to access all customers to do some mailing. So we have to create some containers:

   
class Database {
 Customer[] customers;
 Invoice[] invoices;
 Address[] addresses;
}

This 'Database'-object stores the data and allows us to access them if we want. But it also creates unnecessary ('accidental') complexity. Why? Because we have a rather artificial additional data structure only to access those data we already have declared. If we now do a

c = new Customer()

somewhere we have to put c into 'Database.customers'. And if we destroy a Customer, we have to remove it from 'Database'. This creates some complexity which is very easy to handle in this simple example, but could be the source of more difficult to handle problems in big and more complex applications. But this is it's only the beginning:

Next we want to find a Customer for a certain invoice. We could simply do a search in Database.customers but that would be much to slow in a real application. So we add a back-link to each 'Invoice':

class Invoice {
 Date date;
 Date date_payed;
 Currency value;
 
 Customer customer;  // the back-link for quick access
}

This is an additional rather artificial addition to our structure. We need it only for performance reason, and it leads to new potential problems, because it has to be maintained to. But lets continue further:

Next we want to find all customers in a certain city. We could search Database.addresses to find the matching address and then Database.customers to find the customer for those addresses, but again in most situations this is simply not fast enough. So we have to extend our data structure once more:

class Address {
 String postcode;
 String city;
 String street;
 
 // back links. We use an array because we want to allow
 // multiple Customers for each address
 Customer[] customers; 
}

class Database {
 Customer[] customers;
 Invoice[] invoices;
 Address[] addresses;
 
 // a map to find all addresses for a given city
 Map city_lookup;
}

Those are only the declarations. You can easily imagine the additional code in your application to maintain those structures if you add or delete Customers, Addresses etc. Now scale this simple example to a real-world-application with hundreds of those classes, lots of different views and access-paths to you data structures and you see the problem. And I've not even talked about making the above structures persistent.

The funny thing is that all we really needed to describe our data is in the topmost data structure. It gives a complete description of the problem, but for performance and organization purposes we had to add lots of additional things which blur and complicate our once concise and self explaining structure. So all those additions create 'accidental complexity': Complexity which isn't inherent in the problem but only required for the specific implementation.

You may say that this is a contrived problem and would be handled by a SQL database anyway, instead of representing the structures in the way I did it here. But most data in programs is represented in a similar way. Let it be graphical elements of a GUI or a word-processor, the data in a 3D-modeler or the virtual world in a computer game: We always have data structures which are in principle quite simple but have lots of back links, indices, maps etc to provide access paths to the data.

In object oriented programming this kind of structuring the data is part of the paradigm: Objects have slots and those slots contain references to other data. All objects are intermingled in this way and objects without an access path are 'dead' and will be removed by the garbage collector (or spam the heap in a language without one).

This kind of structuring is so widely used, that its hard to even question it or think about a better way to representing those data. But lets give it a try.

In fact we already know another way: The above mentioned SQL database. It stores data not in structures with references but in relations. SQL is just a certain language to access and manage those relations, but it's in no way the only way to do this. A database stores data on external memory to be able to scale up to huge amounts of data, but we can also store local client data in relations. Just let me convert our example into a relational based one:

relation Customer {
 Id customer_id;
 String first_name;
 String surname;
}

relation Address {
 Id customer_id;
 String postcode;
 String city;
 String street;
}

relation Invoice {
 Id customer_id;
 Date date;
 Date date_payed;
 Currency value;
}

(The above could've been normalized a bit further to make it more flexible, but for example purposes I let it this way).

The structure looks very similar, but it allow all kinds of accesses we could do with our much more complex non-relational structure above - and lots more: We could simple create joins between those relations and query all things we want to know: For example all customers at a given city/street/postcode, all customers with open invoices in a given city, all invoices payed in a given date range. And we don't have to maintain additional back links, maps etc. because this is all done by the programming language which could use indices or other optimizations on all data which is queried often. Automatically if we use something like runtime profiling or static global optimization or by manually by giving hits to the compiler.

The reason for this is, that the above relational structure doesn't contains fixed access paths. Instead of that the access paths are created in the moment we query the structure. This is obviously much more flexible than building the query right into the data structure. And while a single data structure can only be organized in a single way, we can write arbitrary kinds of queries.

So by using a relational structure instead of a referential ones we solved lots of problems. A 'big one' is the infamous O/R-mapper problem: Everybody who tried to use a relational database with a object oriented language knows about it. The idea to simply change the way the database works and use a OODBMS hasn't worked out, RDBMS are still state of the art. And because of the reasons mentioned above I suspect that they stay there (unless we find a new 'third way' to structure data). By changing the basic model of representing data to a relational one, we have also solved the O/R-mismatch.

But is it really possible to represent ALL kinds of data in a relational way? I think it is. I looked at many problems I've worked on in the past and every problem was at least equally and often much easier representable in a relational way. But one thing have to change: The query language. SQL simply isn't up to the task anymore. It maybe never was but while there was much development in the field of object-oriented and functional programming, relational stuff was a bit neglected in the last years. So SQL stayed at the top and became something like a synonym for querying relational data structures.

But this hasn't to be this way. SQL is only a programing language designed to solve this task. And in fact it misses lots of important things. Lets have a relation

parent-of(parent-id, child-id)

Now write a SQL query which decides if a given child-id is a child of a given parent-id, even if only indirect over some 'hops'. This is called the transitive closure of a relation and isn't solvable in general SQL (only a few RDBMS seem to support recursive queries which are needed to solve the problem). This kind of problem is rather common in general algorithms, another one is to sort elements in a topological order based on a similar relation (In fact most graph algorithms are useful on relations and should be easy to express in a useful query language).

So using relations instead of objects can give real advantages but we need language support to make is possible to not only query a RDBMS more easily but also represent all structured data in a full relational way. This way we no only solve the O/R impedance mismatch and the problems with references (I've written about this here and here), we also simplify the way we are programming: Data structures are the base of every algorithm and with a more powerful way of representing data structures it should be possible to gain lots of productivity.

My Haskell experiences

I've known Haskell for some time now. The first time I've used it, it was with a system named Gofer after I read a book about the implementation of a compiler for the Miranda language (there were no Miranda system available at this time because it was a commercial system). Gofer was quite complex for the time and also quite useless for practical application (especial considering the performance of the PCs at this times, I used it on a 8MHz Atari ST). So I went back to C (and later C++) but tried out functional languages from time to time again. The one I used most was Caml (later called OCaml), but I had certain problems with it and abandoned it after some frustrating experiences.

But now Haskell seems to be en vogue and after playing around with it, doing some toy programming and trying things out, I decided that I have to do something 'real' in it. For some time now I casually work on a system for compiler creation based on a customizable parser front end, a template engine for output, an rule based language with forward inference for doing the semantic stuff and a graphical Browser to work with the system comfortably. Because I reached a point where small incremental changes weren't enough anymore, I decided to do a bigger rewrite. It's written in Java but I thought it would be a good idea to rewrite it in Haskell to learn more about the language.

So for some weeks I've done quite a bit of Haskell programming, produced about 2000 lines working code and made some experiences with Haskell I'd like to share.

Where Haskell really shines is pattern matching: Creating tree walkers or subexpression-matchers is a piece of cake, and if you're writing a compiler, this is really useful. Also the easy and powerful list-handling is quite an asset. Things which would require tens of lines in Java are done in 2-3 lines of Haskell code. No more clumsy visitor patterns, not boring List-object creation with complicated insertions etc. All this is really smooth walking and where you can use it good, it really gives a lot productivity.

Lazy evaluation is the icing on the cake because it allows you to write code in very natural way which would lead to rather bad performance in other languages because calculations could easily calculate much stuff which isn't really required there. To avoid this you often have to create quite artificial structures instead of being able to simply reuse old code. In Haskell you simply create a infinite or big finite lists, even if you require maybe only the first two elements. So in a non-lazy language it's always necessary to have some criteria to abort the evaluation while in Haskell you simply write like it is most natural and then let the function which request the data choose how much it wants to get. Caching inclusive.

Also using a fast REPL (read-eval-print-loop) to test out new code (I used Hugs, because of it's good integration into the Windows environment) can be quite nice. That's also a big plus for languages like Lisp and with Haskell it's quite the same. One bothersome thing with Hugs is that it doesn't allows you to test code out, as long as it finds a single error in one of your modules, even if the part of code your test doesn't touch. Thats a result of the compilation model and type inference and partly understandable. But in contrast to using the REPL with Lisp it's still a bit annoying.

Also in contrast with Ocaml the Haskell type system is much more powerful and allows easy overloading of functions. In Ocaml I always had to invent lots of names or use qualified names for functions because there was no overloading possible (but don't know for sure it this is still true because the last time I used Ocaml was in 2002 and maybe they made some advance since then).

Haskell has type inference and while this can really make code more compact because the lack of necessary type annotations it also has its downside: A new line somewhere in your code can easily create compiler errors somewhere else. Type inference works by creating lots of constraints and the inferencer then tries to solve them. So if an error occurs, the compiler flags this error somewhere in the dependency chain and often at places where everything is totally correct while the real error is somewhere else. If you develop code incrementally this is not as bad because you know what you have written since the last run and can look at the right spot it to figure out the error. But if you write longer parts of code without testing the program in between, it can take you quite a bit of time to find out where the error really is.

Haskell has a solution to it: Type annotations. Simply declare the type you want a function to have and things are working much more easy. So if you want to do something bigger than 20 lines in Haskell: Use type annotations, at least for all top level functions. Luckily it's easy to put annotations into your code later, because you can query the inferenced type of a function each time your code compiles and simply paste it into your program (but sometimes you should rewrite it a bit to support a bit more general typing). The code isn't as small as without annotations, but thats better than doing lots of searching around for the source of compilation errors.

The real problems with Haskell start to show up in the moment you require some kind of state. And yes, you will need it: Many things can be done in pure functional style, but I've often encountered situations where a single function deep down in the call hierarchy suddenly needed some informations from the outside. And in some cases they even needed to modify those informations. Then things starts to get ugly.

In Ocaml you can simply declare global, mutable variables and so the problem is a non issue. But in Haskell it's impossible because it don't allows mutation. Even if our small block of code only needs to read some state from the outside, it's not directly possible in Haskell anymore. In my project I often found a nice functional solutions to a problem, but later on, after I put the (tested and good working) code into action I discovered that some function 'deep-down' suddenly required access to outside data and I had to do lots of rewrites because of this.

Haskell has a solution to this 'outside context problem': Excessive use of Monads. While a bit strange in the beginning, after using monads a bit, you get quite fast accustomed to them. But with more complex situations, the usage patterns are also getting more and more complicated.

To use outside state I often used the StateT monad. This monad allows you to create your own state data, modify it like in an imperative language and it can also wrap an other monads into it (for example the IO monad). So if you use this monad you can access your state at will, even modify it and also have access to IO functionality to write out informations while your program is executing.

(This is another big issue I had with Haskell: Simply create some debugging output. In most language you can simply write to some logging-stream to see what your program has done. This is often even more useful than using a debugger, because you can examine the history of the program execution and see what lead to a certain error. But in Haskell you need access to the IO monad to write data out and this requires you to change the way you write your programs)

Also the conciseness of Haskell stops in the moment you want to access or change state. Even Java code is more concise than Haskell code which has to change things. I know that this is probably intended to force programmers to write programs in a functional style. But compared to the otherwise clear and compact syntax of Haskell its really a pain.

Monads can encapsulate state into some kind of data. In fact all monads are simply data constructors with a few required functions. So most monads work by returning itself from functions. It requires a bit backward thinking, because the state-monad for example creates a chain of closures which are executed later by evaluating the value of the monad. So to use state you don't have to give this state to a function, the monad shows up only in the result type. While this is quite clever (and also is the reason why things like backtracking and continuations can be implemented as monads) from a practical point of view, it also means you have to rewrite your code:

Lets have two simple, small functions:

giveElements :: (a -> Bool) -> [[a]] -> [[a]]
giveElements condition = filter (detectElement condition)

detectElement :: (a -> Bool) -> [a] -> Bool
detectElement = any

The above seems a bit useless but I've extracted from it's surrounding code to show the problem. The 'giveElements' function is able to extract certain elements from a list and returns the filtered list. The 'detectElement' function does the job of deciding which elements are in and which are not. It does this by checking if any element of a list fulfills a certain condition.

So short so nice, but after some work on your program you discover that your 'condition' function required access to outside state to do it's job. Maybe the function has to do some a small modification of some data or should simply write a short message into a log. To allow this, you have to rewrite the above functions to use a monad. For this example lets simply use the IO monad here. Now the functions become:

giveElements :: (a -> IO Bool) -> [[a]] -> IO [[a]]
giveElements condition = filterM (detectElement condition)

detectElement :: (a -> IO Bool) -> [a] -> IO Bool
detectElement c els = do
      r <- mapM c els
      return $ or r

The first function still looks quite similar, only the 'filter' function is replaced by 'filterM' now. 'filterM' is the monadic version of filter and gives the monad back from the condition. So without filterM the state won't get up from the detectElement function (and of course there would be a type error).

detectElement looks a bit more different. The reason is that there is no monadic version for 'any'. So I use a monadic map (the mapM function) to create a list of Bools by applying the condition to each element and then check if at least one of the results it true. This doesn't requires more evaluations of c than the first version because of lazy evaluation, but it still required a complete rewrite of my code. It's still readable, but not as much as before.

And there are some other dreadfulnesses: The '$' after the 'return' is necessary because if you simply write "return or r" it would think or and r are both parameters to return (because 'return' is no part of the Haskell syntax but an ordinary function), so we need the '$' to change this. I could also write "return (or r)" but thats a bit longer and with more complex expressions can easily look like you're programming in Lisp. And you can't easily put the 'r' into the expression below. That's because the '<-' is no assignment but a special syntax which creates a closure with r as parameter.

All this has to be considered if you start to use monads. Only because I wanted to access the IO state from my condition-function, I had to rewrite my little program substantially. And if there would be no filterM if even get even more difficult. I had for example to use a similar code with sets instead of lists - but there is no filterM for sets, only a normal filter. And you can't 'lift' (Haskell slang for 'transform a function by using a combinator') a filter function to a monadic one. Map or fold functions can be lifted to monadic forms because they take a function which returns an arbitrary value, which can be used to put the monad in. But if a filter simply returns a Bool and then there is no way to return the monad from within. So I had to convert the set to a list, filter it with filterM and then build a set again - which has worse runtime characteristics than directly filter it.

And if you have more complex functions the above translation process from a non-monadic into a monadic-one is much more difficult and IMO it also destroy the clarity of the code. Also state monads have bad runtime characteristics because of their 'inside-out' evaluation which can fill up the stack quickly. You can use IORefs instead - but then you can't simply transform your program to using continuations anymore for example. And if you put a IO monad into a state-monad, you have to lift all IO-accessing functions via liftIO.

And whats the point of having a pure functional language, going thru lots of trouble to maintain the purity, only to get things like IORef which you tried to get rid of in the first place? If you design a program to use IO monads from the beginning everywhere, then you have fewer problem maintaining and expanding it - but then you're using Haskell like a normal imperative language. Whats the point of Haskell then?

Another bad one with Haskell is documentation: While you find lots of introductions all over the net, it get quite difficult to find informations if you're beyond the basics and start do do real work. The 'official' docs are simply horrible: No examples, no real descriptions how things work or should be used. And finding tutorials for the advanced stuff becomes quite difficult. You can get lucky and find a solution to a problem buried in some of the pages of the Haskell-wiki, a newsgroup or a research paper - but it will take its time to find it and sometimes there is no such solution. And this is only about 'language stuff', not how to solve a very specific situations in some obscure framework.

In retrospective: Haskell is a nice language, but if you need state handling then it gets ugly. That even kills the language for me. Whats the use of concise and compact code if you have to rewrite it later on into a much more ugly form if you discover that you need state? This is no problem for small programs, so I've never ran into those problems with my experiments before. But with a bigger program things changed. So my program still isn't implemented completely and I will probably abandon the Haskell version and do a rewrite in Java again.

Its not a problem of functional programming in itself, its a Haskell thing: While monads are quite powerful in principle IMO they are a pain to use in practice. Because monads show up in the return type of functions, the easy composition of functions which is the prime reason for the power of functional programming only works as long as all those functions use (compatible) monads, and sadly many functions simply don't exists in this form.

With Ocaml for example you won't get this kind of problem, but there you have unlimited mutation which has it's own problems. But there are other pure concepts like for example uniqueness typing (Clean) or transparently chaining state-parameters thru calls (Mercury). And maybe with more time to get accustomed to the use of monads I would maybe see things differently. But since I have no unlimited time and need to get things done in a programming language, I consider my Haskell experiment as a failure - but only a partial one because it was nonetheless fun and brought lots of insights.

So what to do with Haskell? Maybe it would be an idea to put monads automatically in every return type. If I write something like:

func :: a -> b

then the compiler would creates internally

func :: Monad m => a -> m b

and also rewrites all bodies to do/return-syntax. I don't know, if this would really always work and would really solve all the problems but I suspect that by hiding the use of monads better and letting the compiler decide where he can drop the monad constructors safely you would get you 'clear and normal' looking programs back even if they use Monads everywhere. I'm far from a Haskell expert, so take this with a grain of salt. But since Haskell already provides some syntactic support for monads, why not go one step further? If there wasn't the problem with state (and documentation - but thats only a question of effort) Haskell could be a very nice and maybe even the 'next big' thing.

References violate the principle of encapsulation

Every language with allow the use of direct references to objects also makes encapsulation and thus code-reuse much more unlikely. And because every OOP-language has those references thats the reason why encapsulation in OOP doesn't work the way it's advertised by its promoters.

Let's elaborate on this: Any reference is a direct connection to a certain object. That's quite convenient: If we have a deep hierarchy of objects we can simple retrieve a reference to one of those 'deep' objects (lets call it 'B') to an outside object O, and now O is able to directly manipulate B without having to walk thru the hierarchy for every operation.

But what if our object O changes B directly but it's required that some other object C notice it, because it needs to reflect changes to B somehow? Think of a Gui for example: 'A' may be a Button and 'C' some container. If we change the text of 'B', 'C' has to be notified to layout its children to give 'B' enough space to display it's text.

But because 'O' can modify 'B' directly, 'C' won't notice it and our Gui won't work as expected. Sure, as seasoned programmers we already know a solution: The Observer-Pattern. Let 'B' send some notifications for any interesting change to other objects which then can do what they have to do.

But is this really a good solution? It works, but everybody who've done it on a certain scale knows how tricky it can get: We need notification-events, receivers, registration/unregistration, prevent cycles add lots of additional code for every method which has to send a notification etc. It's a real mess. They even invented aspect oriented programming because of this problem, but AOP is like trying to extinguish a fire with gasoline: Instead of solving the roots of the problem they put another layer of complexity on top of it.

So what's the root of the problem? I've outlined it above: It happens only because we have the ability to modify objects directly without its container having to notice it. And thats because of the existence of direct references.

Sure, we gain some convenience in the beginning because references allow us to talk to a object directly - but as a result we need huge amounts of additional code for notifications, observer, doc/view-patterns etc. And it also opens up lots of opportunities to make mistakes. Lots of. Also code reuse get much more difficult because we have much more dependencies on the internal structure of the problem then really necessary. And this is all because the use of references violates the principle of encapsulation.

Is there a solution to this problem? Sure: Getting rid of references altogether! They are simply to tempting.

It's like every low-level mechanism: They give you more power then needed and because of this they can and will be abused. Without references one always has to ask the container via some key for a certain contained object. And you will never get a reference to the object, you will only get the value of the object - which isn't mutable and thus can't be misused. Changing an object would always involve its container and so there would be no need for observers, notifications etc. It may be a little more difficult in the beginning but on the long run the profit would be huge. And with certain concepts build right into the programming language, most unpleasantcies can be avoided. But to solve a problem, it's necessary to first notice that it even exists.

Some people will say now: I as the programmer want all the freedom because I a able use it in the right way. Even if this is a correct way of thinking, having references in the language will in fact limit your freedom nonetheless. Why? Because if there are references in the language the compiler has to follow certain rules and can't do certain optimization which are necessary to create performant code without using references! In other words: By giving you references a language also forces you to use them because alternatives are to expensive. So your freedom is in fact limited in either way. And I for myself would rather be limited to a solid and more error-proof way of programming instead of a risky and error-prone one.

(About other problems with references and how to solve certain problems without them, I wrote about here).

Why pointers and references are a bad thing

References and pointers are quite common in the world of programming languages. References are something like the address of some data on the heap. Pointers are quite like references, but with additional operations of changing the address (by incrementing or decrementing it or even by arbitrarily creating it from some integer value). So a reference is a limited kind of pointer: One with a fixed value. Or in other words: A reference is an immutable pointer.

Pointers are especially bad, because by changing their address, they can point to invalid positions in memory and read or overwrite data which shouldn't be read or overwritten. That's quite ugly from a security point of view and it's the reason why C- and C++-programs often have security holes and allow exploits like buffer-overflows etc. (yes, In know you can prevent this by solid programming, but most programmers simply don't do this because it requires more work and would also often make a program slower).

So lets concentrate on references. First: What's the most fundamental concept in programming language? It's a 'value'. A value can be a simple integer value, a float value or, a string value or the value of a reference. A value has an identity on it's own: The value is the identity. And a value can't changed in itself, a '10' is always a '10'. Things can have a value but the value always is a value on its own, you can't change a value on itself you can only change the value of a variable or a field of a data structure. References on the other hand are a special kind of value, the value of a reference is an address of some object on the heap. It's a less fundamental concept and so we can ask: Is this concept really necessary, useful or even harmful? I suspect the latter: It does more harm then good if a language allows to have explicit references (or pointers, which are even worse).

But whats the bad thing with them? As long as you can't manipulate them and they always point to valid data - but only under an additional assumption: You have a language with automatic memory management - in other words, you have garbage collection (gc). Without gc memory could be freed and then new allocated, even when there are still references referencing it - and then you would have the same problem as with pointers: The possibility to incorrectly overwrite data. So references always require gc if you want to have their security advantages.

References can easily create cyclic structures. Just create two blocks of data, A and B, where each have a reference to the other. If you then want to iterate over this data structure you run into an infinite loop, because you're always jumping from A to B and then back from B to A. Because of this every algorithm which follows reference chains can run into a loop and this has to be examined or prevented in some way.

With gc (which is such kind of algorithm) this means that the most simple way of doing gc ('reference-counting') won't work in the general case, because you have possibly cyclic references. This means that its hard to create some kind of 'local' gc. 'Local' means that the gc should only examine structures which are used in the current situation and not having to scan the whole memory. But by allowing cyclic references this becomes impossible.

And this becomes a big problem if we have huge amounts of data, especially if this data isn't in main memory but on some external memory (on the hard-drive or somewhere on the net). But even with data in main memory there are problems: Todays memory architectures allows huge throughput (lots GB per second) but the access latencies are poor. So doing random access in main memory is a comparatively much more expensive operation compared to ten years ago.

Of course there are methods to prevent those problems to a certain degree ('generational gc') but it remains difficult: Everybody who as worked with a large Java-based desktop-application knows the pauses if the system has to do a full-gc. And if we want to scale gc up to objects in a database this problems gets much worse. Also the trend to more and more concurrency makes global general gc much more difficult and time consuming too.

So are references just bad because of gc? No. There are other problems:

(Small remark: I'm talking here about the view the programmer has on the problem via his programming language, not about the real implementation the compiler does behind the curtains. On the hardware level references are unavoidable, but that doesn't matter if the programmer doesn't see this because it's hidden by the programming language he uses)

A big problem with references is the additional identity they give every object. If you write the following (in Java):

Integer v1 = new Integer(10);
Integer v2 = new Integer(10);

and check if v1 == v2 afterwards, you will get a 'false'! Even if both v1 and v2 are Integer-objects with the same value a comparison with == returns false. To check if they have the same value, you have to write v1.equals(v2). And even if your favorite language doesn't allow the same with integers, they will probably do it too if you create a class like

class Point {
int x, y;
}

and then do the same thing as above with two identical valued Points.

You could now say: "Of course it is this way. We're comparing the objects themself and not the values of the objects". But why should there even be the possibility to have a difference? Only because we have references. Because of references we can decouple the object from its value and compare them as differently. If we don't have a reference-value we can't compare then and thus the only way to compare objects is by comparing their values.

There are many situations when this difference really don't make sense. The Integer-example from above if one of those. But also with other structures often you don't want this kind of differentiation. For example the 'Point'-class above: A point should be a position on a 2d-grid (maybe on a canvas to draw a pixel there), it simple don't makes sense to have two different points which points to the same position. Just like it doesn't makes sense to have to different Integers with identical values.

The situation will get even worse if we allow mutation (=changing). Then we could do something like this:

Integer v1 = new Integer(10);
v1.value = 20; // (not possible in Java)

On this point it becomes clear that a 'Integer' isn't a value but it's a container of a value. That's fine, but what if we don't want a container of a value but the value itself? In Java we only have a fixed number of those 'values itself': The primitive types int, float, etc. Other languages are a bit more flexible and even allow the creation of new value types, but they also allow the create of reference based 'Objects'. And this leads to the aliasing problem:

It we write

Integer v1 = new Integer(10);
Integer v2 = v1;
v1.value = 20;

then v2.value is also 20 now. v2 is only an alias for v1 and because of this every change to v1 also changes v2 and vice versa. And this is bad, because it's non-local: Things can happen at other parts of the program without direct relationship to each other. We explicitly have to prevent this:

Integer v1 = new Integer(10);
Integer v2 = v1.clone(); // now v2 isn't influenced by changes to v1 anymore
v1.value = 20;

In simple programs this isn't a problem because its easy to see what happens, but with increasing complexity it creates more and more sources for hard to find errors. And it makes it hard for the compiler to do certain kinds of optimizations because its hard to assume that some data wouldn't change under certain operations.

This behavior is possible in every language which allows mutation and has references. Only pure functional languages like Haskell are immune to this problem (Ocaml as an example for an impure functional language has the same problem too). But Haskell does two both things: Disallowing mutation and having no references. While immutability has it's advantages it's not necessary to eliminate the aliasing problem, just removing references is enough. And this alone still gives several benefits:

• There is no more need for a general gc


• We only need one simple concept of equality, so no more 10 != 10


• No more null-references (with the accompanying errors)

But can we really get rid of references? We can't write

p = new Point(2, 3)
p.x = 10

anymore, because values can't be changed (a '10' is a '10', it makes no sense to change a '10' to a '12' for example).

But thats in fact a good one. We just have to define our data in an other way: We can't modify values, but we can create new values based on the old value:

p = new Point(2, 3)
p2 = p
p = p.x <- 10

The big difference is that p2 is still Point(2, 3) even if p is Point(10, 3) at the end. The aliasing is gone.

(The new syntax 'p = p.x <- 10' means that a new Point is created by copying all values of p except for 'x' and using the new value '10' for x, returning the new Point)

If you think that this is much more expensive in terms or runtime efficiency, you're wrong: Most of those cases could be optimized internally by the compiler to the old fashioned structure-mutation. The reason simply is that the compiler hasn't to bother if there could be aliasing. Getting rid of references allows the compiler to create those references internally by himself and besides solving the aliasing problem which is hard to overview for the programmer. It's now the task for the compiler which is much more able to do it and won't makes any mistakes.

Removing references from the language would thus open lots of optimization opportunities for the compiler while making the life of the programmer more easy. But is it all really so easy? Aren't references simply required to tackle certain kinds of problems?

What's for example with a list? Can a list be implemented without having references? The answer is yes. In fact it's quite similar to the well known implementation even if each node is a value now:

value Node {
int value;
Node tail;
}

Creating a list is simple, we just create a big value where each 'tail' is another value. But how to insert a new element somewhere in between? We have to create a new list now and can't do clever (but also often dangerous and hard to read) pointer-change-tricks like in the well known double-linked-list insertion. We have to rely on the optimization abilities of the compiler instead - but we get much more clean code.

And the advantage is that it's impossible to accidentally mix two lists in a way we don't want: Because the whole list is a single value it's 'written in stone' now. Totally unchangeable. So we can be sure, that no other part of the program is able to change our list, even if we put it in some lengthy and hard to understand algorithm. This is again a huge advantage for the programmer who wants to understand a program he didn't wrote and also for the compiler to do optimizations (especially in the context of concurrent programming).

In fact most algorithms can easily been rewritten in such a way that they are only working with values. And because we still allow the mutation of variables here, we can still implement imperative algorithms directly.

But there is one thing which seems to be impossible now: Creating cyclic structures.

How to create a cyclic structure if we only have values? Such a structure would require an infinite amount of memory if we try to implement it like the list-node above: We would get infinite recursion.

In Haskell the way out is lazy evaluation. Because of this we could really create a 'virtual infinite value', the compiler would simply evaluate only the parts of the value which is currently required. But is it possible even without having lazy evaluation (which has certain other disadvantages)?

The answer is yes. It's not as easily as with a language which supports reference, but since cyclic structures are not necessary all the time, the time and effort isn't that big also. And don't forget the advantages mentioned before. The trick is to tag values with IDs:

value Node {
int id;
Value value;
int next;
}

value Graph {
Map lookup; // a array would work too, here
int act_id;
}

function (Graph, Id) createId(Graph g) {
new_id = g.act_id;
g = g.act_id <- g.act_id + 1;
return (g, Id);
}

function (Graph, Node) createNode(Graph g, Value value) {
g, new_id = createId(g)
node = new Node(new_id, value, 0)
return (g, node);
}

function Graph addLink(Graph g, Node from, Node to) {
return g.lookup <- put(g.lookup, from.id, to.id)
}

function Graph removeLink(Graph g, Node from) {
return g.lookup <- remove(g.lookup, from.id)
}

(The above syntax is very explicit and again Java-like to make it better understandable for people who aren't accustomed to the more compact syntax of other languages. But those who are shouldn't have any problems with the syntax too - even if they consider it much to laborious).

The above creates a Graph which can contain cycles. We don't use a 'next Node' anymore, but use a 'id' now to reference other nodes. Also each Node stores it's own id so it can be queried if necessary. And we need a map to store the Node for each id and to look it up later. Let's create a simple cycle between two nodes with the values '100' and '110' now:

g = new Graph
g, n1 = createNode(g, 100)
g, n2 = createNode(g, 110)
g = addLink(g, n1, n2)
g = addLink(g, n2, n1)

Now we have a cyclic structure without using any references. The chain is simply followed by using the IDs of the nodes. And the IDs are created automatically by the call to createNode. The above looks a bit ugly because I explicitly had to chain the Graph g thru all the calls, but this could be easily simplified by adding some syntactic sugar to the language. I don't wrote the above to win a code-beauty-context, it's just to show that it's still possible to create all kinds of data-structures without having references at all.

One problem remains: With the above structure we have the gc back in the game. If you use the above structure in a general way you also have to remove Nodes from the graph. As long as you only remove single ones there is still no problem, but if you have a 'start-node' and want that the graph automatically 'forgets' nodes which aren't reachable by this start-node then you need some kind of gc.

But: The gc-problem is now a local thing. Gc in the above case is totally constrained to this Graph-structure and has to be solved in the context of a certain Graph alone. We don't require a general solution anymore, which opens new windows of opportunity for better optimization. In this case we can write a simple gc-function and call it in every call to our 'removeLink' function. But we could also use a background thread to do it. Or call it based on some heuristics etc. We could also put all those linking/gc-stuff into some lib and mostly forget about it, maybe have some parameters in the constructor to choose an appropriate gc scheme. Or best to add some compiler support for this kind of problem which would allow the compiler not only to create the gc-function on its own but also to use this additional knowledge to do better optimizations. Its possible to do whatever suits the problem now instead of having only a single general gc which has to work for all use cases with the same algorithm.

So I hope I was able to give you some thought about one of the most standard features in modern programming languages and why it could be a good thing to question it's practicality. Of course there still lots to say about this topic, but I'll stop here for now.

Rich languages vs. minimal languages

A common pattern in the design of programming languages seems to be to designing languages as 'slim' as possible. The idea is to create as few abstractions as possible directly in the language and then to implement all the useful things the programmer needs in the libraries. While there are obviously some differences in how strict this design pattern is applied, I think that it has to be scrutinized. Lets look at some examples:

In Java the language only implements rather simple collection types: Array with a fixed length. So all usable collections have to be created in the language itself which leads to lots of problems, inconsistencies and performance penalties. On the other hand, Java implements some things other languages use to implement in libraries directly in the language. A good example here is the 'synchronized' directive which makes the use of a certain concurrency pattern much easier to apply.

In Common Lisp nearly all features of the language are implemented in the language itself, but many of those features are part of the standard so they are available as a base to every programmer. The problem is still that those features are designed in a way that they can be implemented in the language itself (via macros) which leads to the well known s-expr-syntax which is hard to read for most programmer and one of the main reason, Lisp is criticized often.

Languages like Ruby and Python on the other hand have a very rich feature set build in directly into the language. I suspect that this richness is the main reason why those languages are considered more expressive by many, and not other features like object orientation or dynamic typing. In those languages you have good syntactic support for many common things like collection handling, regular expressions, big integers etc.

Then there is Haskell which is based on a very restricted central idea (a pure, lazy functional language) but extends that quite cleverly with lots of syntactic sugar and allows free definable operator definition. In Haskell you can not only overload existing operators you can also create arbitrary new operators with custom binding priorities. But things like the imperative looking support syntax for monads or the compact list comprehension syntax which both greatly enhance the usability of the language still needed to be implemented as special syntax because even with those free operator creation its not possible to express it as clearly in the base language directly.

I think that we can see a pattern here: Restricting the base language to strong can lead to limited expressiveness and to the need of lots of boilerplate code. Just compare a bit of Ruby:

a = [1, 2, 3, 4, 5, 6]
b = a[2..-2]

with the similar Java code

List a = new ArrayList();
a.add(1);
... // some adds omitted
a.add(6);
List b = a.sublist(2, a.size() - 2);

The compactness and readability of the Ruby example results primarily from the rich syntax of the language concerning array use and not from the dynamic typing. Even in a statically typed language you could create something similar, for example by using type-inference. But even without someone could invent something like this:

a:[int] = [1, 2, 3, 4, 5, 6]
b:int = a[2..-2]

which is much more compact then the Java example, even with explicit type annotations.

There are lots of similar examples, so what could be the reason why language designers choose to not implement language support for something? Lets look at some possible reasons.

• Learnability. If the language has a small core someone could be proficient in it much faster.


• Clear and simple and maybe even 'provable correct' design. The language could be desigend much faster and also much easier. Also the language model may allow abstract theoretical reasoning about important things.


• Better extensibility. Because all higher-level features are implemented in the language itself they could also be implemented by a 3rd party which allows the creation of new features the designer hasn't thought of or allow to extend existing features with user defined ones.


• Better compilation. The compiler for a simple language is more simple and could thus be more sophisticated.

There are of course more reasons, but I hope I got the most mentioned here. So lets have a further look at them:

• Learnability
  
  Learning a language also means to learn the libraries. If you know Java without knowing at least the base-libs you know nothing. So if you put a feature in a lib or put it in the language itself don't really matter.
  
  You may suspect that libs have the advantage to be better searchable with some documentation facility, which can even done automatically to some extend (thing about code completion in todays IDEs). But you could also create a similar documentation facility which includes language features. For example just type 'array' and the documentation would give a short info about the supported array-syntax in the language.
  
  In fact there is no single reason why learning a languages to a degree which is necessary to do real-world-work would differ if you put more features directly in the language. In fact it may be even the opposite: Is it really more easy to know all what is necessary about Java collections then about Ruby-collections? I doubt that.
  


• Clear and simple and maybe even 'provable correct' design.
  
  While it's true, I ask: Are those properties of a language really necessary? To a certain degree and in certain domains: For sure. But in general? I doubt it. A 'industrial strength' language (i.e. a language which is created to do lots of real-world-work) has to ease the life of the programmer. It simply doesn't matter if the language has a nice, clear and simple design unless it really helps the programmer to accomplish his or her tasks.
  
  Interesting theoretical properties of a language are for sure a valid thing for research languages but thats only a very limited domain - even if it looks much bigger to language designers. But for real world programming other properties are much more important, so we really have to differentiate here.
  


• Better extensibility.
  
  This seems to be the 'killer argument' for putting stuff in the libs instead of the language. But is this really true? Can you for example really extend Javas collections so easily? The answer is of course: No. You can of course write your on list-class, but you can't use it as freely as you want because you simply can't substitute your new list-class into existing code without modifying the source. Sure, you can exchange the system-classes with your own (as long as your own classes use the same interfaces) but thats not really sensible in most cases.
  
  You may suspect that thats not a fault of the idea itself but only of a certain language (like Java). In Ruby for example you can substitute classes very easy at runtime. In Haskell it all depends on which module you import. And in Lisp you can always write a clever macro. So maybe its possible if you just use the right language? Yes, to a certain degree it is, but it comes at a price: You can introduce difficult to find bugs in already tested code, you have to design the language in a certain way to do it (which makes it harder to use) and you need dynamic typing or rather sophisticated type-systems (if you want static typing) to do it.
  
  In the end it makes the language semantics more difficult to understand - and not because of usability purposes, but only to allow somebody to create things in the language which are already part of the language (even if implemented in the libs). And do we really need this kind of extensibility? You may think that having something is better then having it not, but all things come to a price and why do we want to pay this price for something we don't really need?
  
  All the above extensibility schemes have their limitations. Even with Lisp-Macros you can't create real transparent continuation support. Even with Haskells clever type and module system they still had to create syntax to support monads in the way they have it now. And in Ruby you have to pay with slow execution and the loss of compiler-time validity checks which could lead to hard to find errors.
  
  In fact most programmers never ever have to change the system libraries. Extend them? Maybe, to a certain degree. But its always possible to add functionality to a language by writing libraries. Maybe you can't use those extensions in the same way you can use the build in features, but is this such a problem? In fact it even has the advantage to make code better maintainable because it's always easy to distinguish between 'safe' language base-stuff and 'maybe faulty' self-written-stuff.
  
  In the early days of computer science, the design of programming languages was new, new algorithms and data-structures were invented 'every day' and in those times it really seems to be risky and to prohibitive to put to much things directly into the language. So after having experienced the difficulties tointegrate new concepts in rigid languages like Fortran it's understandable that the trend went in the direction of creating better extensible languages. But the times have changed. When did you really have invented a new basic algorithm or data structure? All those basic use-cases are well known for some time now and in most domains they simply don't change this often.
  
  So we simply don't need this much extensibility today if the language provides enough features on their own.
  


• Better compilation.
  
  In fact its the opposite: A program in a rich language can be much easier compiled to an efficient native program simply because the compiler has more knowledge about the program. Sure, the compiler gets bigger, but it don't have to guesstimate what the programmer really wanted and more optimizations are possible.
  
  Fortran is still in use because the use of its array and matrix features which are build into the language allows easy vectorization and thus high-performance programs on otherwise hard-to-build-for computer architectures.
  
  Also lots of novel optimization techniques are possible. What about a collection class which isn't fixed to a certain implementation but where the compile decides which implementation to use depending on usage patterns, maybe even with the possibility to change this implementation after profiling at runtime? This would be impossible if the collection-type is implemented in a lib, because lib-code is like every-code or the compiler and it simply don't know about lots of optimization opportunities. But if the collection is part of the language the compiler is able to chose how to implement it, depending on how the collection is used. May indexed accesses? Use a array-based implementation. Many insertions and deletes? Use a linked-list one.
  

This ideas here could and should be extended to more higher-level structures. Collections are very basic but also very often used and thus crucial for efficient implementation and performance.

But also things like concurrency, component based architectures, data-base-access/persistence etc. can really benefit from being part of the language. Instead of writing something like

result = db.query("select name, value from data");
name = result["name"];
value = result["value"];

which is very error prone and inefficient to compile, we could have something like this:

select name, value from db.data;
// name,value are stored directly into variables above

This would be easier to write, the compiler could check for syntax errors at compilation time, could automatically cache queries, do optimizations etc.

I believe that the minimality principle which is applied in most of of todays languages is in fact obsolete and should be questioned by everyone who starts to design a new programming language. Many languages did this to a certain degree but why stop there? Why not try to find all the common patterns programmers are doing and reimplementing each and every day and putting them directly into the language? Instead of researching of 'domain specific' languages, why not simply invent a language suited for the domain of every-day programming?