Brent Yorgey has published a first draft of what looks to be a fantastic resource for the Haskell programmer who wants to understand what all those strange type classes like Applicative, Monoid and Functor actually mean.

I am in the process of reading though it and the quote

Hmm, it doesn’t compile … maybe I’ll stick in an fmap here… nope, let’s see… maybe I need another (.) somewhere? … umm …

describes me all too well at times.

While it may not yet be complete, it is still quite a meaty piece of work, weighing in at 48 pages, including a full 111 useful references.

Read it now: The Typeclassopedia. Alternatively, the announcement.

All it needs now is a name which I can type successfully on the first attempt.

Related posts:

1. XML parsing with Haskell Although I have been aware of the existence of XML,...
2. Creating a minimal HTTP server in Haskell I have been spending quite a lot of time lately...

Although I have been aware of the existence of XML, I have never had any real experience of working with it. It looks like that is changing.

It all started when, on a whim, I purchased XSLT by Doug Tidwell. As I began reading it, typing in various bits and pieces of XML, I came to the conclusion that that I really needed to sit down and learn what XML is actually all about.

Up until that point my idea of XML was as a relatively simple format with tags, and so long as the tags match, everything is ok. How hard could it be to create an XML parser? It surely  must be pretty straightforward, and could be achieved in a few dozen lines of code.

And so began journey into the depths of the XML 1.0 specification. My code is currently just creeping over 2000 lines and has yet to pass my initial test suite, although it is getting closer.

I used the parsec library to do the parsing of the file together with the compact-string library to deal with encodings and they worked pretty smoothly once I figured out what I was trying to achieve with them. In fact, getting the initial XML parser was relatively straightforward – just some grunt work to implement it all. The problems mainly occurred with various well-formedness constraints and (something I have yet to tackle at all) the validity constraints. Additionally, since there are some nice tests to go with the specification, my focus is currently on getting them to pass, and in particular writing out my parsed XML document in canonical form.

My development of the XML parser has (will have!) the following stages:

• Read the file as UTF16
• Preprocess to get rid of carriage returns
• Parse the basic structure
• Expand various entities and make sure they also parse correctly
• Ensure the various well-formedness constraints are satisfied
• Ensure the various validity constraints are satisfied
• Completion!

I am currently in the middle of stage 5 partly because I keep getting distracted by making the canonical export work (it is needed for checking results of some tests). Unfortunately, I believe I am still doing the easy stuff and that the most difficult stage is the next one where the validity constraints have to be enforced.

Nonetheless, it has been a valuable learning experience – my knowledge of XML has increased many-fold as has my familiarity with parsec and compact-string libraries.

One thing I have noticed with parsec is that I probably over-use the “try” combinator. I took a very lazy approach and basically implemented my own version of the parsec combinators which scatter “try”s like there is no tomorrow, to ensure I didn’t have to do any hard thinking about when they are actually required. While this means that parsing successfully is easy, it does seem to mean that if there is a parse error, I get almost no clue where the error was, which is somewhat unfortunate. Still, hopefully as time goes on, I can start to remove the “try”s bit by bit and gain some performance improvements along the way.

I did come up with a perhaps-useful combinator of my own during the process of implementing the XML specification. At several stages, there is a rule of the form

NotVowel = Char - [aeiou]

which should match any character except a vowel. My first attempt to implement this used “manyTill” like so

notVowel = do
   manyTill char vowel

but this has the unfortunate effect of “eating” the first vowel encountered. Instead, it should be implemented something like this:

notVowel = do
   m <- optionMaybe $ C.lookAhead vowel
   case m of
      Just _ -> P.unexpected "Vowel encountered"
      Nothing -> char

or, in its more general form:

type Parser = P.Parsec Input XmlState
butNot :: (Parser a) -> (Parser b) -> (Parser a)
butNot p e = do
   m <- optionMaybe $ C.lookAhead e
   case m of
      Just _ -> P.unexpected "butNot failure"
      Nothing -> p

This seems to do the job marvellously well. Basically, it looks for the “bad” input and if it finds it, fails. If it doesn’t find the “bad” input, then it happily parses “good” input.

Related posts:

1. Creating a minimal HTTP server in Haskell I have been spending quite a lot of time lately...

Jeff Atwood asks the question “What’s the difference between a programming language and a scripting language?“. Although he doesn’t seem to come to a conclusion about that, he does decide that he is a scripter rather than a programmer. This is based on his experiences with BASIC (a scripting language) and C (a programming language). So what is the essential difference?

As with all such questions, there are many possible answers. As many commenters noted on Jeff’s blog, this is not black and white territory – there is a continuum between scripting languages and programming languages. But this also avoids the essential question, which is trying to find the difference between the two varieties.

By definition, a scripting language lets you do scripting. And a programming language lets you do programming. So is there an inherent difference between scripting and programming? Superficially, I would say no – both involve typing some instructions into an editor in order to be executed later and perform some action.

Where I think the difference lies is in the timescales of the time of execution. When scripting, we expect the action to happen once we are finished coding. Indeed, this may well be the purpose of doing the scripting in the first place – to get some task completed, whether that be some database manipulation or file system tidy up or whatever. However, when programming, I get the sense there is a more long-term purpose. Maybe we are coding a library for others to use. Maybe we are creating a product to sell. When programming, we are not after a quick fix, we are seeking to create something more enduring. As such, programming languages tend to be stricter about what they accept so that less can go wrong later on.

So, what is the difference between a programming language and a scripting language? Well, given the previous paragraph, a scripting language is one that provides sufficient flexibility and functionality to get things done. This will probably be in the form of libraries that come packaged with the implementation, in some sort of  ”batteries included” way as Python’s standard libraries are described. Because results are to be obtained quickly, the functionality needs to be readily available with a minimum of fuss. When programming on the other hand, with the longer-term view in mind, there is more time to look around for the right library, or even to write it yourself if need be. C is like this – you don’t get much with C except for the basics. You want to do something fancy, you need to go and find it.

Of course the interesting thing is that while few would argue that C is a scripting language, even if it came with a variety of libraries,  it is quite credible to treat scripting languages as programming languages. If what you write with Python, or Perl, or Ruby etc. is actually a library for future use by others, then arguably you are programming rather than scripting. And if you are programming with a language, that suggests that the language itself is a programming language.

Haskell, my current language has a foot in both camps. Fundamentally, I think it is a programming language, but the beauty of it is that it can be treated for scripting. There is a move to make this more explicit with the Haskell Platform which is a project to create what is effectively a Haskell standard library to provide all the common functionality necessary to be productive with Haskell. When this is ready (hopefully sometime this year) there should be less need to poke about among the various Haskell packages looking for an appropriate database package (for example). Instead, there will be one provided which should be good enough until proven otherwise.

Eventually, it all boils down to preconceptions. There is no fundamental difference between a programming language and a scripting language, and it doesn’t make sense to try and make that distinction. Instead, the real question is “What is the difference between programming and scripting”, and the answer to that is one of attitude. Personally, I don’t particularly like either, and when working in Haskell I swing wildly between one extreme and the other – prototyping quickly (scripting) and then tidying up and modularising (programming). Instead I would just describe what I do as “coding”. Haskell is, then, a coding language, and I like it.

No related posts.

As I have been watching the Masters snooker, there has been a great deal of discussion about Ronnie O’Sullivan breaking his cue before the tournament and then managing to play exceptionally well with a replacement which he has never used before.  The majority of commentators seem to believe that this shows O’Sullivan’s natural prowess and flair for the game of snooker.  I tend to agree.

At the same time, I have been following a discussion about Haskell at Integer Overflow where there has been a bit of a discussion in the comments about there not being an IDE for Haskell and that this is holding back the adoption of Haskell as a mainstream software engineering language. The argument goes that once the code base gets beyond a certain size, an IDE is necessary to simply get any work done. I tend to disagree.

The two situations are somewhat related.

For O’Sullivan, the cue is simply a conduit for getting the snooker skills inherent in his arm and brain onto the table. For other, mere mortal, snooker players, the cue is more than that. For them, the cue is an essential ingredient in their success.

Programmers tend to act similarly with regard to IDEs. On the one hand, there are those than can use an IDE, but it is simply a way of getting the code written. On the other hand are those that cannot function without their IDE. Put the latter breed of programmer in front of a basic text editor and command prompt and they are lost. They need the support and comfort that the IDE they know and love provides.

Imagine if a new breed of snooker cue  was invented – the steadi-cue. This cue had the uncanny ability to remain completely steady so that even a rank amateur could make much more accurate shots. It is not inconceivable that a player using such a cue could beat the natural ability of O’Sullivan. However, the snooker purist would be aghast – snooker tournaments would no longer be about who is the best player; after all, you would barely have to practise.

When a programmer uses an IDE the same thing occurs. However, because programmers are not generally judged on their ability but rather on what they produce, nobody has a problem with using the equivalent of the steadi-cue; the IDE. They may not win a best-programmer competition, but getting a product out that works is more important.

Which is all well and good if that is how you want to regard yourself – as a cog in a machine, albeit an important cog. However, if you want to actually excel in what you do, try casting that IDE away once in a while at least. It can be liberating. For starters, you gain a far greater understanding of what is actually going on when you click the “Build” button for example. All those compilation flags you never worry about suddenly become a lot more interesting when you have to figure them out for yourself.

There is also a sense of liberation when the shackles of the IDE are cast off – programming can then occur almost anywhere at any time and a text editor can start up a lot quicker than a fully-featured IDE. Having tasted the freedom, I don’t want to go back.

Still… sometimes I wish I had intellisense.

No related posts.

Haskell, and GHC in particular never cease to amaze me.  While thinking about writing an infinite sorted list data type, I was playing around with ghci and discovered that it allows you to find a member of a list which is infinitely far from the beginning.  Then I discovered it didn’t.

An initial misunderstanding

The expression I used was

elem 2 ([1..] ++ [2..])

since this would appear to construct an infinite list by adding an infinite list of 2s to the end of an infinite list of 1s, I was fully expecting to have to interrupt the calculation as ghci happily chewed through all the 1s.

Instead, the answer True popped up immediately.  Impressive.

Then I realised my mistake.

I had created my lists incorrectly – the correct code is in fact:

elem 2 ([1,1..] ++ [2,2..])

and ‘lo and behold, the expected chewing does indeed occur.  It did get me thinking though.

From misunderstanding to thoughtfulness

In theory, a clever enough data structure would be able to return True for a suitable equivalent of this expression.

The question is just finding what that data structure should be.  I have been thinking about infinite lists recently, after my previous post on finite lists, and in particular which of the functions defined in Data.List could be guaranteed to complete when the list is infinite.

It turns out that almost all can be converted to infinite lists, but many of the functions will require additional constraints on the elements in the list in order to ensure that they return.

Consider the elem function.  With an arbitrary infinite list, there is no guarantee that a call to elem will return.  An example of a list where it wouldn’t return is

elem 0 [1..]

We can resolve this problem by requiring that all the elements of the list are greater than or equal to some value.  In this case, we know that all elements are at least 1, so we can immediately return False.

However, how do we then deal with the following:

elem 2 $ [1,3..]

Here, the infinite list consists of all the positive odd integers.  Again, it is clear that 2 is not a member, but the current implementation of elem does not terminate.  We can get around the problem by using the knowledge that the elements of the list are sorted.  In which case we can use

head (takeWhile (<2) [1,3..]) == 2

which gets us the correct answer of True.  It also allows us to discard our previous condition – since being sorted means that the minimum element will be the head of the list.  But all is not well.

Consider now, the problem

elem 2 $ [1, 1 + 1/2, 1 + 3/4, 1 + 7/8, 1 + 15/16 etc.]

(which isn’t valid Haskell, but you get the idea).  In this case, every element of the list is less than the element we are searching for, so neither elem nor takeWhile would ever terminate.  Instead, we need to impose another constraint on the list, namely that the list is unbounded – so that we will be guaranteed that takeWhile will return.

Or will we?

Consider now the list formed in the following way:

[1,1..] ++ [2..]

This monstrosity satisfies the sorted, minimum element and unbounded constraints, but still would not return.  There are two possible remedies to this.  First, and most severe, is to require that all the elements of the list be unique.  This will resolve this problem as the [1,1..] would then be invalid.  The other is to require that there is only a finite number of each element.  This second constraint is less severe than the first, and so is preferred.

So, given that the list satisfies the following:

• is sorted
• is unbounded
• has a finite number of all elements

I believe we can be guaranteed to find any given element in finite time.

From thoughtfulness to enlightenment

Assuming that we are now in a position to find whether an element is a member of a suitable constrained list, are there any ways in which we can  relax the constraints?

Well, firstly there is nothing particularly special about the ascending order – we could easily change that to descending order provided we correspondingly alter the minimum element condition to instead be a maximum element condition.

Having done this, a more general approach now presents itself – we can find a given element in an infinite list provided the following conditions hold on the list l with ordering function f :: a -> a -> Ordering

• unbounded: there exists m such that all (==GT) $ map (f m) l
• sorted: all (/=GT) $ zipWith f l (tail l)
• finite counts: not $ any (isInfinite.genericLength) $ group l

where I have tried to use Haskell notation as far as possible, even though actually trying to execute the code on infinite lists would probably cause non-termination.

All that is needed now is an implementation, so that is the next step.

Related posts:

1. Notes on working with finite sorted lists In a previous post, I wrote some information on ways...
2. The fast, the right and the smart Working my way through the puzzles in Project Euler is...

In a previous post, I wrote some information on ways to work with sorted infinite lists.  Since then I have investigated some more and realise that the code I gave could be considerably improved.  Particularly if you are interested in sorted finite lists.

The improvement

I made the remark that while

elem n primes

would not return for the infinite list primes, the alternative

(head $ dropWhile (<n) primes) == n

would work.

This is true, but it raises a couple of issues that need to be addressed before it can be used more widely.

The first problem is that it actually doesn’t work for finite lists, which is rather annoying but can be resolved by adding an appropriate test before taking the head:

contains n ns = (not $ null rest) && (head rest == n)
   where
   rest = dropWhile (<n) ns

The other issue with finite lists is that this is actually pretty inefficient and a better way to test for membership is to use sets. A much faster approach is this:

contains n ns = Set.member n $ Set.fromList ns

Even though this would appear to be doing a lot more work, it does appear to be considerably faster.  However, this does not work for infinite lists, because the call to Set.fromList never terminates.

I have been making increased use of both of these methods to test for membership as I continue to work through Project Euler probems.  Now at level 2!

Related posts:

1. The fast, the right and the smart Working my way through the puzzles in Project Euler is...
2. Finding a member of an infinite list Haskell, and GHC in particular never cease to amaze me....

Working my way through the puzzles in Project Euler is pretty enlightening at times.  I made it to level 1 yesterday to much acclaim and adulation.  Taking this as an opportunity to look back at the sort of  patterns I have been coding threw up a couple of interesting practises which I have been performing.

Manipulating strings to and from numbers

A large number of the problems involving the rearrangement of numbers, for example, finding which pair of two-digit primes when rearranged in ascending order and concatenated give the cube of the difference of the original primes (I just made that up – there may well not be an answer).  In this example, if our two primes were represented as ab and cd then we would need to perform the rearrangement to get ba and dc as well. The tactic I have been adopting for this is judicious use of show and read.  For the example I just gave, the call would something like

reverseNum = read.reverse.show

In order to find all the two-digit numbers my current ploy is to make use of the permutations function in Data.List and apply it to a string of digits.  After a bit of processing, the correct answers pop out. For example, here is the code to return all nine-digit numbers without zeros:

nineDigitsWithStrings = map read $ permutations "123456789"

Its short and clear, and not a lot can go wrong with it. But the use of read just looks a bit ugly. I had a nagging feeling that the right way to do this was to actually do the conversion “properly” by stepping though the list multiplying by ten at each step, to get the same, proper answer. Something like this in fact:

nineDigitsWithNums = map makeNum $ permutations [1..9]
   where
   makeNum ds = makeNum' (reverse ds)
   makeNum' [] = 0
   makeNum' (n:ns) = n + 10 * makeNum' ns

A couple of things to note – firstly, the reverse is required so that  the proper digits get more multiplications.  Second – it appears to be a lot more complicated than the string version, but let’s be honest, there is a lot of complexity hiding within a call to read of which there is none in this version. I had no idea which might be faster so I created a quick test to see if one was clearly more efficient than the other. The results were somewhat surprising – the quick and dirty string-based method was around 20% faster and used about 20% less memory.  So much for doing things the “right” way!  Why this is the case I do not know (yet), but the reverse calls might be the culprit.  Unfortunately, they are somewhat important in getting the right answer.

Dealing with sorted lists

Another pattern I noticed using occurred when dealing with sorted infinite lists.  These keep cropping up – for example the list of primes is a prime (ho-ho!) example.

In this case, I would often want to grab the members of the list smaller than a given number.  Naively, I would write

filter (<n) primes

but this would never complete, due to the infiniteness of the list.  Knowing that the list is sorted, the correct effect can be obtained by a slight tweak:

takeWhile (<n) primes

which completes quite happily. This sort of thinking is also useful when interrogating a list for the existence of a particular element.  Again, a naive approach would be to use

elem n primes

which again doesn’t complete due to the infiniteness of the list.  Adopting the same sort of approach as before, we can re-write this as

(head $ dropWhile (<n) primes) == n

which (once you get your head around what it is actually doing) is simple, and more to the point works.

Having these solutions at your fingertips allows you to avoid the problem of arbitrarily truncating the infinite list, which would be the other option.  It isn’t a good option though – truncate too early and you miss the elements you need.  But truncate too late and you spend far more time than you need to in dealing with the list.  Haskell’s lazy lists are a real boon in this situation.

Related posts:

1. Notes on working with finite sorted lists In a previous post, I wrote some information on ways...
2. Finding a member of an infinite list Haskell, and GHC in particular never cease to amaze me....
3. Validation of use of Num2Str It’s always good to see that the code you write...

It’s always good to see that the code you write has some real-life application, however small.  So, it was heartening to find a Project Euler problem that required exactly the functionality provided by my Num2Str utility.

Project Euler

In an attempt to hone my Haskell skills, I have been playing around with Project Euler.  Combining as it does programming with mathematics it is the perfect playground for me.  The programs required are usually relatively short in both length and running time and so are ideal when you have a few minutes spare.

Validation!

Upon reaching the 17th challenge, I was delighted to be confronted by the problem:

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

Immediately reaching for my trusty num2str function, I found that my algorithm agreed with the results given for 1,2,3,4,5 and 342.  Validation is a great thing and in this case gave me a sense of enormous well-being.  Admittedly it did require a minor post-processing step to remove spaces and hyphens, but that was to be expected and easy in Haskell (filter isLetter anyone?).

It was but a small step from validation to merrily running the full problem and getting the correct answer.

Small victories

It is small victories such as this that make life worth living.  I am now on a quest to become the highest rated Scottish Haskeller (login required) on Project Euler.  I have some way to go but am currently in 7th place.  Onwards for Freedom!

Related posts:

1. Converting numbers to strings As a quick exercise for myself I coded up some...
2. The fast, the right and the smart Working my way through the puzzles in Project Euler is...

After my feeble fumblings towards what is quite possibly the most minimal HTTP server designed (minimal as in functionality rather than in minimal but complete according to specification), it was clear that part of the problem was trying to use HTTP preformance tools to test the chat server. To rectify this, it made sense that I write my own little test utility that would allow me to hammer the chat server and test it in a more appropriate way.

Aside

It is still clear that there are some issues with the original chat server since the shutdowns shouldn’t be occurring regardless of what kind of mad clients try to connect. However, the hope is that with a more focused test utility, the problems can be resolved more easily.

The plan

Rather conveniently, there is a corresponding simple TCP client for the original simple TCP server. Once again, this is where we shall begin our quest.

The idea is to convert the client from a command line user-interface to an automated tool that will connect to a server, send some input, receive some output, close the connection and then return the output received. In this way we will be able to test that we receive from the server what we expect.

The implementation

Rather suprisingly, implementation went relatively smoothly. I rapidly got a command line utility that takes a host, port and number of connections to make. It then forks a new thread for each one and each writes a single line, consisting of its number. Each then listens for a second beforewriting a final string and then closing the connection.

While this is happening, I am also listening to replies from the server. Any replies are tagged with the client id and added to a giant map. When the terminating string is recognised, that client is removed from a large list and when all clients have completed, this in turn returns. The value returned is a map of client id to the strings received from the server by that client. This should now allow some analysis to ensure all are working as they should.

Initial testing

First testing was against the minimal HTTP server. And it worked. But being keen to test it aggressively, I immediately cranked up the number of connections to make to 2000. At that point I got this rather worrying error.

getProtocolByName: does not exist (no such protocol name: tcp)

Thinking that it was likely that I had deleted the TCP protocol, I suspected an issue with open sockets once more. This was confirmed by a quick search over the number of connections. The maximum I was allowed without getting the delightful error above was in fact 1021. This looked fair enough when the output from socklist included the following TCP sockets

type  port      inode     uid    pid   fd  name
tcp   9999    2284399    1000  15202    3  minimal
tcp    631    2245789       0      0    0
tcp     25      99077       0      0    0

and ulimit -a provided the information

open files (-n) 1024

which implied that there would be 1021 sockets available.

Interestingly enough…

Doing a Google search for “getprotocolbyname does not exist no such protocol name tcp” turns up several Haskell-related links. Could this be an indicator that Haskell is often being used for large-scale socket manipulation? Or that Haskell programmers are more likely to be doing strange things with large numbers of sockets? Or even that Haskell programmers don’t know what they are doing and do crazy things like that?

Further testing

Since I was flush with my success, I moved on to testing the original chat server. Here, as expected, things did not go as well.

Small number of connections were fine. But when I rolled out the big guns and set 500 connections at the server, it promptly fell over (gracefully as ever).

Although disappointing that the chat server is somehow broken, the fact that the test utility reproduces the problem is reassuring as I slowly add to my minimal HTTP server making it more fully-featured.

Scary code

The thing about Haskell is that it lets you do some frightening stuff in a single line. Case in point:

sequence_ $ map forkIO $ zipWith ($) (zipWith ($) (repeat (start host portStr chan)) [1..n]) $ map (:[]) $ map show [1..n]

which is just scary. Of course there is probably a much simpler way to do something like this, but if it works, don’t mess with it, at least unless there is some sort of reliable test framework to rely on.

Conclusion

Getting a basic test framework was easy, but the proof of the pudding will be in the eating. Or, in other words, I shall wait and see how much use I can make of it as I progress. The final state of the code is reproduced below – for all its pretty colours, it is really quite messy!

The code

> module Main where
 
> import Prelude hiding (catch)
 
> import Network (connectTo, withSocketsDo, PortID(..))
 
> import System.IO
> import System.IO.Error (isEOFError)
> import System.Environment (getArgs)
> import Control.Exception (finally, catch, Exception(..))
> import Control.Concurrent
> import Control.Concurrent.STM
> import qualified Data.List as L
> import qualified Data.Map as M
> import Control.Monad
 
> main = withSocketsDo $ do
>     [host, portStr, nStr] <- getArgs
>     let n = (read nStr :: Int)
>     chan <- atomically newTChan
>     sequence_ $ map forkIO $ zipWith ($) (zipWith ($) (repeat (start host portStr chan)) [1..n]) $ map (:[]) $ map show [1..n]
>     output <- mainLoop chan  [1..n] $ M.fromList $ map (\i -> (i, [])) [1..n]
>     putStrLn $ (show output)
 
> start :: String -> String -> TChan (Int, String) -> Int -> [String] -> IO ()
> start host portStr chan i ss = do
>     let port = fromIntegral (read portStr :: Int)
>     sock <- connectTo host $ PortNumber port
>
>     netTID   <- spawn $ listenLoop i (hGetLine sock) chan
>     sequence_ $ map (hPutStrLn sock) ss
>     threadDelay 1000000
>     atomically $ writeTChan chan (i, "COMPLETE")
>     hClose sock

Related posts:

1. Creating a minimal HTTP server in Haskell I have been spending quite a lot of time lately...

I have been spending quite a lot of time lately looking at A simple TCP server written by the elusive and somewhat anonymous mrd.  It is, as the name suggests a simple TCP server which acts as a rudimentary chat server. Any input given is output to all clients. All very straightforward. Or so I thought.

First steps

My problems began many months ago when I began building a kind of generic network server on top of this basic framework. Everything seemed to be going well until I wondered to myself how it would cope under load. So I fired up ab and set about stressing my server. Sadly the stress was too much and my server exited cleanly.

Cleanly? Yes, it seemed that my server just shut down without a murmur. I found that a little odd – I was expecting it to become unresponsive and churn away to itself, or to crash with some error about too many sockets open or the like. What I was not expecting was what appeared to all intents and purposes to be a nice normal exit as though everything was normal.

Much head-scratching, hand-wringing, nail-biting and teeth-gnashing later, I  was a bit of a wreck but my server would still merrily shutdown under load. Clearly this was a time to go back to first principles. Unfortunately it  wasn’t so clear to me at the time, so I continued ever onwards, changing bits and pieces here and there to try and tease the answer out of the rather  convoluted server that was evolving before my very eyes. Unsurprisingly, the answer was not forthcoming.

Time to get serious

Fast-forward a few months and I had another go. More fool me. Once again after a few days work when I performed the stress test, the graceful shutdown again occurred. This time I stopped myself from beginning to create large convoluted forking mechanisms and instead decided to try testing the original building block itself.

Lo and behold – the same behaviour was present in the original. Now we were (finally) getting somewhere. Even better, the shutdowns weren’t my fault –  they must be either present in the basic server or else are some artefact of the interaction with the operating system.

Time constraints got in the way however, and I didn’t get a chance to look at what exactly was the problem. And so the issue sat in the back of my mind waiting for the opportunity to taunt me once more. And that time came a few days ago.

I sat down with the code and promised myself that I would resolve the issue. First, I made sure the problem was still present – which it was. My next step was to try the Haskell IRC channel but there were no clues to be found there. So I resorted to poking the code myself with surgical precision looking for any tumour that could be causing the symptoms.

Specifics

At this point I should probably start providing some specifics about what I was actually doing, since I suspect there are actually several issues present. The test run is

ab -n 1000 -c 100 http://localhost:9999/

with the following behaviours:

• left to run
• interrupted with ctrl-c
• interrupted with ctrl-c, rerun, interrupted, rerun etc.

There are few things to be aware of here. First, ab is sending HTTP requests and expecting HTTP responses. It doesn’t get these, instead it gets a whole bunch of HTTP requests sent back if it is lucky and they are likely to be all mixed up. Here is a typical log of the console when running:

new client
data: GET / HTTP/1.0
data: Host: localhost:9999
data: User-Agent: ApacheBench/2.3
data: Accept: */*
data:
data: GET / HTTP/1.0
data: Host: localhost:9999
data: User-Agent: ApacheBench/2.3
data: Accept: */*
data:
data: Host: localhost:9999
data: User-Agent: ApacheBench/2.3
data: Accept: */*
new client
new client
data: GET / HTTP/1.0

As a result of these malformed HTTP responses, the individual responses will, if all is well, time out. So, there are potentially 1000 requests waiting for responses.

The second thing to be aware of is that the behaviour is non-deterministic. This is not unexpected, as we are at the mercy of threading. Sometimes the first test (left to run) will not cause the server to shutdown, other times it will. Sometimes the second test (interrupted) will not cause the server to shutdown, other times it also will. However, the third test has always resulted in the server shutting down, almost always on the second interruption – although not always.

The investigation begins

The first exploratory incision was made by removing the

hPutStrLn h line

line. This does appear to have the effect of making the server reliable once more. Unfortunately it also has the effect of making the char server very quiet, since nothing is ever output to the clients. Rather an extreme solution, but it begins to suggest where the problem might lie.

The next attempt was to reintroduce the client communication but to make it small – by simply outputting a single character. This relatively small change retrieved the shutdown once more. So even a single character seems to cause problem. Unless, it is not the character itself, but the flushing of the character that is the issue?

Attempt number three reintroduced the original client communication but removed the

hFlush h

line trailing it. Now, I fully expected that this would again change the client behaviour most likely by preventing any output, but I was curious as to whether it was the flush rather than the write that was the problem.   Interestingly, the server still shutdown but it seemed to be a little more reliable as it was only the third (repeated interrupts and reruns) which cause the shutdown.

At this point, I sat back a little and considered what (little) I knew. I  knew that the server was shutting down cleanly. I knew that the process of writing to the clients was causing the problem. I knew precious little else.

Resorting to logic

Having exhausted my surgical probing for now, I resorted to trying to reason logically about the problem. The main issue was the fact that the shutdown was controlled – this suggested by looking at the code that there must be an exception being called.

start servSock `finally` sClose servSock

Commenting out the finally clause I was confident I would see some nice error pointing me to the cause of all my problems. But it was not to be. Commenting out the finally had no apparent effect whatsoever. Deflated, I replaced it and thought some more.

My next attempt to track the problem was, I thought, inspired. Since I had already reasoned that there was clearly some sort of I/O issue, I decided to remove all the internal putStrLns in case they were somehow overloading something. Namely, these likely culprits

putStrLn "new client"

putStrLn $ "data: " ++ line

when (dropped > 0) $
putStrLn ("clients lost: " ++ show dropped)

Once again though, my hopes were dashed – the console was much quieter, and  then provided me with the by-now all-too-familiar bash prompt. Still it shutdown without a murmur.

The next plan of attack was to try and find if there was some uncaught  exception somewhere which was somehow causing the server to exit. A quick look on Hoogle led to setUncaughtExceptionHandler. Feeling confident again, I liberally sprinkled some trivial handlers to do nothing more that output something so I could see where the uncaught exception might be. But as was becoming an apparent trend, nothing was output.

From despair to documentation

Around this time I was beginning to despair of actually finding the problem. Instead, I thought that perhaps the way to go was to accept the shortcomings of my little server and instead make the server talk HTTP to the client so that ab would get meaningful responses. However I felt that this was akin to sweeping the problem under the carpet.

By this stage I was desperate and had resorted to reading documentation. While doing do, I stumbled upon GHC’s implementation of concurrency. Up to this point had been simply compiling my server with the command

ghc --make original

but this suggested to me that perhaps a -threaded would be worth a try. Try I did, and while it seemed to take a bit more effort to get the server to quit, quit it nevertheless did. Not to be daunted I decided that while I was  messing around with threads, I might as well change the calls to forkIO to forkOS to see if that made a difference. Make a difference it did – the server was now again much easier to overload. Back to the drawing board once more.

It was time to start poking at the operating system. I set up a script to try and start 2000 instances of my server to see what happened.

for i in `seq 3000 4999`
do
./original $i &
echo $i
done

I kept an eye on the number of sockets being used with socklist | wc -l, but I needn’t have worried. The OS seemed quite happy to start up that many instances. It even seemed to manage when I then ran ab against one of them. However, the server still died under load. Still, I thought, it might be worth increasing the ulimits just in case. In particular, the maximum  number of open files might be worth increasing in case that is having an effect. After quite a lot of tinkering with making the number of open files ludicrously large in both the server shell and the testing shell, I came to the probably inevitable conclusion that this was not causing the problem  either.

Blame the code, not the OS!

By now, I had exhausted my efforts at trying to blame the operating system, so I was back to poking at the server code.

It seemed that it was time to try to sweep the problem under the carpet for now, do I modified the code to transform it from being a simple chat server to effectively be a very dull HTTP server by simply returning a trivial response to each request, and then closing the connection. To do this, I removed the forM clients loop and instead added the following lines to just after the “new client” output:

hPutStrLn h "HTTP/1.1 200 Ok\r\nContent Length: 2\r\n\r\nHi"
hClose h

Now, upon running the first (uninterrupted test, everything works much better. Which is to say, the server still shuts down, but it does it now with a proper error, namely

hPutStr: illegal operation (handle is closed)

This is progress! In addition, ab reports that there 1000 requests made (as expected) and that 64 failed with exceptions. There is also only one place in the code where hPutStr is used, so the search is narrowed down quite considerably.

The question is now this: how can the handle be closed when it has only just connected? Also, upon repeating the test, I found that sometimes, the additional error

accept: invalid argument (Bad file descriptor)

is returned. This however, seems more than likely due to my over-zealous testing before sufficient sockets have cleaned themselves up, so I don’t worry too much about it. As expected, if I curb my impatience and wait until

socklist | wc -l

returns a nice small number like 6 rather than a silly number like 1214, the test behaves better. Unfortunately, repeating the test yet more times  discovers that the number of sockets seems irrelevant and that sometimes the test fails spectacularly badly and sometimes it almost works well – but the server always shuts down with the illegal operation error, occasionally coupled with the invalid argument error.

Now, the accept error looks like a problem with the underlying socket which could be resolved with a suitable catch clause, so I add one in:

start servSock `catch` (\e -> error "TROUBLE!") `finally` sClose servSock

Voila! Now we get the server exiting with the single word “TROUBLE”. The plan now is to try drilling back in the callstack to that point to isolate the call that is causing the problem.

Distractions

As an aside, I notice at this point that the network package that I am  using is two versions out of date – 2.1.0.0 vs 2.2.0.1. Updating doesn’t appear to have any effect though, but it is probably better to keep up-to-date.

Another aside I noticed while looking at the code is that the tselect function appears to favour newer connections – they get added to the front of the list and then have their input dealt with first. This means that the first client to connect may just sit there, never getting its input read while the last client to connect is dealt with immediately. In order to see what effect this had, I changed the line

mainLoop servSock acceptChan $ (ch,h):clients

to

mainLoop servSock acceptChan $ clients ++ [(ch,h)]

which, while admittedly will be slower to perform might have a beneficial effect. So did it? Well, with fast, original, pre-pending version, the server seems to quit with the double error described above. However with the slow,  new, append version, we get a single error. Unfortunately the new version is reluctant to actually return any response – the console gets a few “new client” messages, but not the full 1000.

Revelations coming thick and fast

More revelations came to me now – due to the alteration of the server to return a response immediately upon connection, a lot of the code was now redundant. To see just how redundant, I removed the bits that weren’t needed. This left me with the following code:

module Main where
import Prelude hiding (catch)
import Network (listenOn, accept, sClose, Socket,
withSocketsDo, PortID(..))

import System.IO
import System.Environment (getArgs)
import Control.Exception (finally, catch)
import Control.Concurrent

main = withSocketsDo $ do
[portStr] <- getArgs
let port = fromIntegral (read portStr :: Int)
servSock <- listenOn $ PortNumber port
putStrLn $ "listening on: " ++ show port
acceptLoop servSock `catch` (\e -> error $ "TROUBLE" ++ (show e)) `finally` sClose servSock

acceptLoop :: Socket -> IO ()
acceptLoop servSock = do
(cHandle, host, port) <- accept servSock

hPutStrLn cHandle "HTTP/1.1 200 Ok\r\nContent Length: 2\r\n\r\nHi"
hFlush cHandle
hClose cHandle

acceptLoop servSock

The result when attempting to test this were surprising. The server was now fine, from what I could tell, but ab would now give errors of the form

apr_socket_recv: Connection reset by peer (104)

after a number of successful requests. Investigation via Google led to a discussion on an Apache dev mailing list] which threw up the -r option. Using this allowed the test to complete but with a large number of errors.

If thing aren’t working, swap tools

Beginning to wonder if this will all ever end, I decide that ab may be at fault, and try out httperf] instead. Initial runs were reasonably successful, but were all giving connreset errors which looked odd. Unfortunately all my efforts to fix this by using HTTP/1.0 and/or Connection: close were to no avail and then httperf decided to become rather unuseful and consistently fail with an assertion failure.

Noone said this was going to be easy!

Inspiration strikes

And then there is an inspiration. Because of course, behind a lot of the  madness there is the simple fact of human error. To be specific, the use of putStrLn rather than putStr. Oops. This was adding some extra characters to the response, which was no doubt confusing things somewhat. With this change, httperf works once more, but still announces connreset errors which I have now decided to ignore.

The good news is that the server itself now seems to be solid. Which it really should be, since it doesn’t do any real work any more. Sadly, the more complex version does not benefit so greatly and still experiences the illegal operation errors.

The home straight

But then there was more good news, accompanied, almost inevitably by more human error. In face the call I was using to httperf was invalid since I was trying to use the --num-calls option which I thought meant make a certain number of calls to the server. In fact it means the number of calls to  issue on each connection – and requires that the server support persistent connections: which mine does not. Removing this option makes the httperf test pass with flying colours – hurrah! This valuable information was found via Theodore Bullock’s httperf QuickStart Guide.

While ab still complains with its apr_socket_recv it looks as though  this might just be because the server is simply too fast. The documentation for ab does recommend that the client and server are not on the same machine. So for now, I am content that I have a solid platform to build upon and will now use `httperf` as my stress testing mechanism.

Conclusion

So what am I left with after all this investigation? Several lessons learnt  and a very minimal but nonetheless robust Haskell HTTP server.

1. When basing work on others’ work, test the original thoroughly first.
2. When using command line tools, make sure you know what the options do.
3. When implementing a protocol, be careful that you follow it.
4. Writing down what you investigate helps organise your thoughts.

The code

> module Main where
 
> import Prelude hiding (catch)
> import Network (listenOn, accept, sClose, Socket, withSocketsDo, PortID(..))
> import System.IO
> import System.Environment (getArgs)
> import Control.Exception (finally, catch)
 
> main = withSocketsDo $ do
>     [portStr] <- getArgs
>     let port = fromIntegral (read portStr :: Int)
>     servSock <- listenOn $ PortNumber port
>     putStrLn $ "listening on: " ++ show port
>     acceptLoop servSock
>         `catch` (\e -> error $ "===EXCEPTION: " ++ (show e) ++ "===")
>         `finally` sClose servSock 
 
> acceptLoop :: Socket -> IO ()
> acceptLoop servSock = do
>     (cHandle, host, port) <- accept servSock
 
>     hPutStr cHandle $ "HTTP/1.1 200 Ok\r\n" ++
>                       "Content-Length: 2\r\n" ++
>                       "\r\n" ++
>                       "Hi"
>     hClose cHandle
>     acceptLoop servSock

Related posts:

1. Testing a chat server After my feeble fumblings towards what is quite possibly the...
2. XML parsing with Haskell Although I have been aware of the existence of XML,...