malcolm

We are hiring Functional Programmers.

2017-02-13T19:51:00.001+00:00

The Modelling and Analytics Group was the original introducer of Functional Programming (especially Haskell) to the Financial Markets business of Standard Chartered Bank, and although there are now several other teams who contribute to our large codebase and who are also hiring, we now have some vacancies in the Core team. Please think about applying!

Job Description:

Join the Modeling and Analytics’ Core team, part of Financial Markets Front Office, in Singapore or London.
Apply Functional Programming concepts to the design and implementation of the unified bank’s Analytics library.
Support infrastructure requests from the Quant group, flow trading desks, structured trading desks & structuring worldwide.

Candidate qualifications:

Master or PhD in Computer Science, with a focus among: functional programming, language & compiler design, efficient data processing.
Excellent programming skills in one of the major statically typed functional languages (ideally Haskell), and preferably exhibited by academic output (research / teaching) or open-source development.
Proficiency with C/C++ and debugging / performance tuning tools is a strong advantage.
Good communication skills required for interactions with other team members and with trading desks.
Familiarity with financial markets is a plus but not required.

How to apply:

In the first instance, send your CV to Raphael.Montelatici@sc.com

Haskell Symposium 2009 - videos now online

2009-09-21T21:55:00.003+01:00

Videos from the recent Haskell Symposium 2009, held in Edinburgh, are now edited and uploaded to

http://www.vimeo.com/album/128530

The original programme of talks is at http://www.haskell.org/haskell-symposium/2009/schedule.html

HUGE Data but small Programs

2009-02-02T16:36:00.002+00:00

The slides for our PADL'09 talk, about language design (of DSLs) as a strategy for solving visualisation problems, are now available online. The "programs" for exploratory combinations of visualisations are small. So is the Haskell implementation behind it all.

codec implementations

2009-01-26T16:10:00.003+00:00

Many years ago, Jeroen Fokker wrote a "Functional Specification of the JPEG algorithm, and an Implementation for Free". It was great on clarity - really helped me to understand the codec - but totally sucked on performance. With all the recent activity in making pure Haskell libraries with decent speed, utilising fusion and other optimisation techniques, I'm wondering whether it is time to revisit that paper, and see whether we can keep the high-level specificational style, but do rather better on all that number-crunching. In fact, after JPEG, why not take a look at something more challenging, like specifying/implementing the H.264 or Ogg Theora video codecs?

Haskell Workshop 2007 videos

2007-10-09T17:40:00.000+01:00

Videos of all this year's Haskell Workshop talks, demos, and discussion, are now available: ̄here. The first location we hosted these at chewed through 100Gb of transfers in 24 hours, so go easy on the current host won't you? The videos are in QuickTime (H.264 + AAC audio, 320x240, about 8-12 fps), and are about 120-150Mb each.

HsColour gets a new backend

2007-07-11T21:30:00.000+01:00

This morning, people in #haskell were playing with colours and bold/underline style formatting in the IRC channel, having just discovered it was possible. Mauke took HsColour's output for ANSI terminal codes and wrote a perl script to translate it into IRC colour codes instead. Now, how could I live with that? - munging the output of a beautiful haskell program using a perl script that looks like pure line noise!

Hence, the emergence of a new pure haskell backend for HsColour: the -mirc formatting flag. It's actually really easy to create new backends, hence the growth from the original 2 (-tty and -html) to 5 formats now. In fact, it was 70 lines of haskell, against 89 lines of perl. Smaller, more beautiful, more readable, more maintainable.

And only yesterday, Christophe Poucet contributed another new feature to HsColour: the -lit flag for literate code. Obviously, you don't really want syntax highlighting on the main parts of the document, just in the embedded code fragments. So with a little cannibalisation of the unlit module in the Haskell 1.2 Report, voila, HsColour now only colourises the code, not the document.

Register-based bytecode

2006-05-01T10:06:00.000+01:00

I blogged a few months ago about a student who was looking at turning the standard stack-based bytecode into a register-based variant. Well, now the results are in, and they look pretty good. Just to recap, the plan was to take Yhc's backend bytecode (based on the spineless G-machine); to define a new bytecode that implements the same operations, using machine registers instead of a stack for temporary storage; to translate from one bytecode format to the other (including a register allocator); and to implement the corresponding runtime interpreter to execute the bytecodes.

The implementation proceeded in stages, at first using an array to represent a set of registers, then later using a cunning despatch mechanism to get hold of real registers. At this point, performance of the new system was about the same as that of the old system. But the cool thing is that register-based code allows more peephole-optimisation
opportunities. You can re-order instructions, provided they do not touch the same registers, and this code motion brings together pairs of instructions which can cancel each other out, or be fused into a different instruction that is cheaper. Alex also did some extensive profiling to discover common instruction/instruction pairings, and instruction/register pairings, and created specialised versions of those recurring operations. (This kind of profiling had already been done on the original nhc98/yhc stack-based bytecode, gaining about 25% in speed. The naive translation to register code actually threw away all that optimisation work, aiming initially for a simple, regular instruction set.)

So with some optimisation phases added, the register-based bytecode now runs up to 2x faster than stack-based code. There are more potential optimisations waiting in the wings too, although Alex will not have time to implement these.

One of the interesting negative results is that the first translation scheme ended up making the bytecode size larger (about twice the size on average per program), but that this made the "hello world" program 7x slower! Since yhc loads the program code dynamically at runtime, what this means is that there is a non-linear relationship between file size and loading time. But this is only really a concern for very short-running programs: above 1 second, the gains in running time outweigh the losses at loading time.

Improvements to HsColour

2006-01-25T22:21:00.000+00:00

After my last post about HsColour, Neil stepped up to the plate and implemented a CSS backend, to complement the existing HTML-3.2 and ANSI terminal code outputs. More recently, extensions have been added to Haddock, the Haskell library auto-documentation tool, that allow the generated documentation to link to a wiki for user comments, to a bug-tracker for bug reports, and to the original source code for reference.

This is an obvious place for HsColour to fit in. Why display just raw source code on the web, when you can colourise it as an aid to readability? So there is a clear further requirement now. Ideally, Haddock should link to each individual function definition, not just to the top of the module that contains it. So, the HTML generated by HsColour needs to embed an anchor tag with each definition, so that the page.html#anchor syntax for references will work.

But there is a difficulty with extending HsColour to do this. Colourisation is a simple lexical problem. To find the defining occurrence of a function identifier (or datatype, or class), you really require a parser. Although simple top-level definitions have the function identifier starting in the leftmost column, what about (for instance) an infix-style definition, with an arbitrarily deep pattern on the left of the identifier you are trying to find?

It turns out that one can in fact write a finite state automaton to find the defining occurrences. It is rather like a complex lexer, but I reckon it is still more lightweight than either writing a full parser, or stealing one from elsewhere. I have an initial design, and I'm aiming for less than 150 lines of extra code. Work in progress is available in the darcs repository.

Meanwhile, the Programatica project has solved the same problem very nicely. Their Hs2Html tool is integrated with the entire compiler front-end, so they have, not only a parser, but a full module-import resolution phase as well. This means they can generate HTML with cross-links from every /use/ of an identifier to its definition, even across source files. Extremely useful, and very navigable. The downside is that it is a rather heavy-weight mechanism - the tool needs to have every module available (including the Prelude) or it can't finish.

Colourising code

2005-12-08T20:41:00.000+00:00

If anyone is interesting in colourising Haskell code to paste into HTML on your blog (as in my previous entry below), it was done with a simple Haskell program (of course). HsColour is a little script I knocked up a few years back. It uses an intermediate mini-language of highlighting styles, and currently has two backends, one for HTML and another for ANSI terminal screen codes. I'm sure it would be simple to add other backend rendering formats - maybe CSS - with a tiny bit of effort. If you do modify it, or otherwise find it useful, please let me know.

The history of HsColour is vaguely interesting, because it was essentially a spin-off of my (winning) entry in the 0th International Obfuscated Haskell Contest - remorse. If you haven't seen remorse before, I'll try not to spoil the fun of discovering it, but suffice to say, it requires a mini-lexer for Haskell code, which I ripped out and re-used in HsColour. Don't worry - that isn't the obfuscated bit.

Replacement for Read class

2005-11-26T10:04:00.000+00:00

So here's something that has annoyed me for ages. The standard Read class in Haskell. OK, so you can derive it automatically at the same time as you derive Show. But if you want to write your own instance of Show to make your data printer even slightly out of the ordinary, then you'll have to write your own instance of Read to match it. Writing an instance of Read is far more complicated than it ought to be. The list comprehension style is OK, but having to plumb the trailing unconsumed input all the way through it is rather tedious and offputting. This plumbing problem was solved ages ago when someone invented monadic parser combinators.

But wait, there's another annoying aspect of Read as well: rubbish error-handling. If anything at all goes wrong - for instance you edit the string produced by show and forget a comma, or you write your instance of Read incorrectly - then boom, your program crashes with the error "no parse". No opportunity to catch the error and do something graceful. No indication of what actually went wrong. It just dies and leaves you in the dark. But wait, the monadic parser combinator people solved that problem eons ago as well!

[Historical note: the Read class was originally defined (actually known as the Text class) long before any of us FP people even knew what a monad was, so we can't really blame the Haskell committee. It was a reasonable choice at the time.]

Now, I'm aware that Koen Claessen and Simon PJ have come up with a replacement for Read called ReadP, based on monadic parser combinators. It is even used internally by GHC when you derive Read. But the trouble is, their scheme is designed to get better efficiency and avoid backtracking, not to improve the error handling. The interface to the class Read remains the same. So my thought is, why not propose a complete replacement of the Read class, interface and all? Here's what I came up with:

-- | First a general parser monad, t = token type, a = result value.
--   Errors are returned through the Either type.
newtype Parser t a = P ([t] -> (Either String a, [t]))
instance Functor (Parser t)
instance Monad   (Parser t)

-- | Apply a parser to an input token sequence.
runParser :: Parser t a -> [t] -> (Either String a, [t])

-- | A TextParser is a specialisation of the standard parser monad
--   over character strings.
type TextParser a = Parser Char a

-- | The class @Parse@ is a replacement for @Read@.
class Parse a where
    parse     :: TextParser a
    parseList :: TextParser [a]

-- | If there already exists a Read instance for a type, then we can make
--   a Parser for it.
parseByRead :: Read a => String -> TextParser a

The monadic combinators still provide back-tracking, through a standard choice operator, but the key thing is that the caller of runParser gets to see whether there was an error, allowing it to do something sensible, and if there was an error, there is an explanatory message to go with it.

Also, defining an instance of the Parse class is dead easy. Here's an example:


data Shape =
    Circle  ShapeStyle Double
  | Polygon ShapeStyle [DoublePoint]

instance Parse Shape where
  parse = oneOf
      [ do{ isWord "Circle";  return Circle `apply` parse `apply` parse }
      , do{ isWord "Polygon"; return Polygon `apply` parse `apply` parse }
      ] `adjustErr` (++"\nexpected a Shape (Circle,Polygon)")

Even dealing with field notation is rather simple as well:

data ShapeStyle = ShapeStyle
    { styleStrokeWidth  :: Int
    , styleFill         :: Colour
    }

instance Parse ShapeStyle where
  parse = do{ isWord "ShapeStyle"
            ; return ShapeStyle
                `discard` isWord "{" `apply` field "styleStrokeWidth"
                `discard` isWord "," `apply` field "styleFill"
                `discard` isWord "}"
            }

I've been using this Parse class for a few weeks now, and it is a big improvement over Read, so much so that I'm thinking of proposing it (or something similar) for Haskell-prime, the new version of the language standard. The actual set of parser combinators used to underlie the class is not so important. I'm using my own recently developed set, called Text.ParserCombinators.Poly, based originally on the Hutton-Meijer combinators from 1996. But that is just because I'm most familiar with them. I'm sure Daan Leijen's Parsec combinators would be just as good a choice.

For now, both Poly and TextParser are distributed in HaXml-1.14, (also available in fptools CVS) and will no doubt continue to evolve over the next few weeks. Once they are fairly settled, I might distribute them as a separate package, not tied to HaXml.

Bytecode experiments

2005-11-17T20:02:00.000+00:00

I have another undergraduate starting a project this week. Originally he was to look at replacing the spineless G-machine bytecode used in nhc98 with a three-address instruction code. That is still the plan, only now he might use yhc as a platform instead.

The idea is simple. Standard G-machine instructions use the stack heavily as temporary storage. But this is potentially bad for performance, because of all the memory accesses. Using registers for temporary storage would potentially be much faster. This is what native-code compilers do of course. But I would like to continue to have a portable bytecode, running on a small interpretive virtual machine. So part of the problem will be to map temporaries to real registers in the VM itself.
However I expect that to be relatively straightforward, and the major work will be defining and generating a register-based bytecode. I'm thinking of translating the already-generated G-code to register code by simulating the stack.

Ultimately, I'm hoping for a decent speed-up, maybe 2x or better. But I guess there are quite a few pitfalls that could mean we only an improvement of say 20%. Or maybe it will go spectacularly well, and we'll get 3x improvement. We'll find out in a few months time.

Mentioned on Lambda-the-Ultimate

2005-10-30T09:39:00.000+00:00

Thanks to Lambda the Ultimate for pointing people who are interested in programming languages over to my blog. I suddenly noticed that lots of the things I talk about do not have hyperlinks to allow the interested party to find out more. Since I don't know how to go back and edit old posts, I thought I'd give a bunch of links here instead, whilst trying to be more disciplined in future.

The Haskell language.
The nhc98 compiler.
The Hat HAskell Tracer/debugger.

Failure Propagation and Transformation Calculus.
Dazzle Bayesian analysis tool.
Blobs diagram editor (webpage not yet live).
wxHaskell cross-platform GUI toolkit.
Haskell Workshop 2005.

HaXml libraries and tools.
Prerelease (1.14) of how HaXml-2 is shaping up.
DrIFT type-directed preprocessor.
Haskell Xml Toolbox from Uwe Schmidt.

O'Caml vs Haskell - is a strict language faster?

2005-10-19T12:19:00.000+01:00

A couple of years ago I had a student doing a project to compare Haskell with Clean for performance. He developed a translator (Hacle) from one language to the other, so the same program could be directly compared for measurement. The initial results were promising - it looked like Clean always produced faster code. But a more careful comparison over more test data showed a mixed picture, some were faster, some slower. Because the languages are so similar (both lazy) this seemed like a good test of one compiler team's skills against another.

So this year, I have a student doing something similar, only with O'Caml and Haskell. Again, there will be a translator from Haskell, and again we are looking to see if Xavier is just a better hacker than SPJ. :-) However, there is more to it this time. To what extent is laziness a time loss, or a time gain? The idea is that there are two possible translations from Haskell to O'Caml - one preserving the structure and semantics of the code, which is then simply evaluated strictly instead of lazily; and the other simulating non-strictness in O'Caml, so the code has the same termination behaviour as well as its semantics. I think everyone would expect O'Caml to win the first challenge, because of its reputation for very fast code. Even so, I suspect there may be cases where laziness is a better strategy, and Haskell might just do well. But how about lazy O'Caml vs lazy Haskell? That's the interesting question for me.

unifying Haskell2Xml and Xml2Haskell

2005-10-12T21:24:00.000+01:00

So, there I was, hacking on Blobs (see below), and I realised that the file storage format for these diagrams is XML, so naturally Arjan has used the HaXml library for writing/reading these files. Great. But wait, what do I see? Even though all the internal data structures to be stored are defined in Haskell, he hasn't used the Haskell2Xml class, which can be handily derived for you by DrIFT. No, he uses the low-level generic XML parser/printer, and then hand-converts from the generic tree into and from his own data structures. Why ever did he do that? And then the first thing hit me. The Haskell2Xml methods return a "Maybe a" type. For production software, that simply isn't good enough. If the input fails to parse, then the developer is jolly well going to want an explanation of why not. The low-level generic parser gives back decent error messages if it finds a problem. But the high-level typeful parser does not. And then the second thing hit me. The Haskell2Xml method is indeed a parser. It parses the generic tree into a user-defined typeful tree. Yet it isn't written as one. Even though the low-level parser is constructed with nice combinators, Haskell2Xml doesn't use them, but rolls its own ad hoc solution.

The realisation of what I had to do was swift and immediately convincing. I had to replace HaXml's Haskell2Xml class with a true parser combinator framework. Not only that, but there is a corresponding class Xml2Haskell, derived not by DrIFT, but by the Dtd2Haskell tool, which uses an XML DTD as the source of the data structures. And yes, that too is really a parser, but was not written as one. So yes, that too needed to be rewritten.

In fact, come to think of it, why are there two classes anyway? Surely if you want to parse some XML to a typeful representation, then it is the same job, no matter where the types were originally defined. OK, so the actual instances of the class will be different depending on whether you use DrIFT or Dtd2Haskell to write them, but so what? In fact, won't there be circumstances in which you want to mix code of different origins - to dump a Haskell-derived data structure into the middle of a document with an open DTD, or vice versa? Having two separate classes would be unpleasant and unnecessary.

And thus the tale started. HaXml-2 will shortly (I hope) see the light of day. The original three kinds of parsing techniques will be reduced to one - a new set of combinators - and the parsers written with them will layer on top of one another. The generic tree parser is on the bottom, and the typeful tree parser on top, but both now using the same set of monadic combinators. It is so much more aesthetically pleasing. Not to mention giving far better error messages than before, so more practically useful too.

P.S. The Haskell Xml Toolbox from Uwe Schmidt got a new release today. Apparently it has Arrows now. Must look into that.

Completed draft 0 of interactive diagramming tool.

2005-10-10T19:42:00.000+01:00

University term has just started today, so I'm feeling the potential pressure of getting snowed under with teaching commitments, so this was my last real chance to get some significant coding finished on my most recent tool project. Over the last couple of years, I've been developing the theory of FPTC - Failure Propagation and Transformation Calculus. It is a method for analysing safety-critical systems designs that consist of both software and hardware components. Essentially, you determine the failure modes of each component and communications mechanism, in response to any failures in their environment. So then you annotate each element of your design diagram with an expression denoting its failure behaviour. The calculus then allows the whole system behaviour to be determined automatically. I already had the calculus engine (written in Haskell) for some time now. But although it generated SVG diagrams as output, for input it used a textual description of the diagrams, and so was quite fiddly to use - it would take forever to layout a diagram by manually adjusting coordinates and stuff, then running the batch tool to see the result, rinse and repeat.

So, over the summer I came across Dazzle, a graphical tool for Bayesian analysis, written in Haskell using the wxWidgets toolkit. There was a paper about it at the Haskell Workshop 2005 in Tallinn. And I thought - hey, I need something just like that. Luckily, Arjan who is one of the authors is a nice chap, and although he could not release the entire source code to me, he spent an afternoon stripping Dazzle down to just the diagram editor, with no analysis backend, and sent it to me, calling it "Blobs". Fantastic! I didn't need to start a design from scratch, and didn't need to learn wxWidgets from scratch either. Just start tweaking the code and see what happens!

Well, today after only about a month's effort, I'm finally happy that Blobs, with my analysis engine plugged in, gives me the same results as I had before, with the same pretty output diagrams. But now it takes only minutes to draw a new diagram instead of hours. Click a button and the analysis is performed instantly. Very satisfying. And really, Arjan's Blobs code in Haskell was a joy to work with - totally easy to understand and modify.

Of course, this is only version 0. I still have much more in the analysis engine (tracing, probability) than I ever worked out how to display even on SVG diagrams. But these were difficult before in the batch-mode tool, mainly because of the tedious way needed to specify exactly what you wanted. It should be a lot smoother in an interactive setting.

A new haskell compiler

2005-10-07T19:57:00.000+01:00

Tom Shackell told me today about his "short weekend" project - he has completely reworked the backend of nhc98, and now has what amounts to the bulk of a new compiler he is provisionally calling "yhc" for York Haskell. Neil thinks he should call it THC (Tom's...) instead. :-)

The whole code generator and runtime system has been replaced. It now generates a platform-independent bytecode stored directly in a binary format, instead of encoding it into platform-specific C arrays that needed further C compilation. There are lots of great things about this. The generated code runs about 20% faster. You can copy the bytecode from one architecture to another without needing to recompile. The high-mem bug in nhc98's garbage collector is gone by default (new heap layout). The bytecodes are dynamically linked, so it should be possible to hot-swap running code a la hs-plugins. It works on 64-bit machines. The runtime system can be compiled natively on Windows with VC++, as well as the original gcc on Unix way.

All very cool. Now we just need to replace the frontend as well - get a decent type inference engine etc. Any volunteers?

Everyone's doing it

2005-09-23T22:23:00.000+01:00

Yes, blogs are the thing. Actually, I only signed up to write one because I wanted to leave a short comment on someone else's article.