Carmack on Static Analysis and Functional Purity

Posted in Haskell, Software Development by Dan on October 16th, 2012

In the absence of anything worthwhile of my own to write here at the moment, I thought I’d instead highlight a couple of interesting blog posts that I’ve discovered recently by id Software’s John Carmack.

I read Carmack’s thoughts on static analysis a few weeks ago and his reports on the effectiveness of tools for analysis of C++ code chimed with my own experiences with Java tools such as FindBugs and IntelliJ IDEA.

The first step is fully admitting that the code you write is riddled with errors. That is a bitter pill to swallow for a lot of people, but without it, most suggestions for change will be viewed with irritation or outright hostility. You have to want criticism of your code.

Automation is necessary. It is common to take a sort of smug satisfaction in reports of colossal failures of automatic systems, but for every failure of automation, the failures of humans are legion. Exhortations to “write better code” plans for more code reviews, pair programming, and so on just don’t cut it, especially in an environment with dozens of programmers under a lot of time pressure. The value in catching even the small subset of errors that are tractable to static analysis every single time is huge.

In the other article, which I only read today, Carmack espouses the virtues of pure (i.e. side-effect-free) functions. His is a pragmatic approach concerned with how to exploit purity in mainstream languages, where it is entirely optional, as opposed to advocating jumping ship to Haskell. Even when 100% purity is impractical there are still benefits in minimising impurity.

A large fraction of the flaws in software development are due to programmers not fully understanding all the possible states their code may execute in. In a multithreaded environment, the lack of understanding and the resulting problems are greatly amplified, almost to the point of panic if you are paying attention. Programming in a functional style makes the state presented to your code explicit, which makes it much easier to reason about, and, in a completely pure system, makes thread race conditions impossible.

My experiences with Haskell have informed how I approach coding in other languages. In certain cases I’ve ended up taking the functional approach to such extremes that I’ve been left questioning my original choice of implementation language.

No matter what language you work in, programming in a functional style provides benefits. You should do it whenever it is convenient, and you should think hard about the decision when it isn’t convenient.

“constrFields” runtime error message using HStringTemplate

Posted in Haskell by Dan on July 1st, 2010

This post is one for the Google spider so that if somebody else has this problem they can find the solution by searching (I haven’t found mention of it anywhere else on the web).

If you are using HStringTemplate (version 0.6.3 at least) in Haskell and your program is failing at runtime with the not-particularly-informative message "constrFields", you might wonder what the problem is. This message is generated by the SYB library used in the implementation of Text.StringTemplate.GenericStandard. The error is caused by attempting to access a constructor for a primitive type.

Why is HStringTemplate doing this? Looking at the HStringTemplate source we can see that it does not currently support generation of generic ToSElem instances for records that have fields of type Char. At the moment, the simplest solution to this problem is to change your Char fields into Strings.

Generating HTML with Haskell

Posted in Haskell by Dan on December 3rd, 2008

If you want to generate HTML pages from Haskell, there are a few different approaches available. The Haskell.org wiki lists several web-related libraries.

Text.Html

The standard Haskell libraries include the Text.Html module. This is a combinator library that allows you to generate HTML pages by combining Haskell functions. Each function is responsible for generating an HTML fragment and these fragments are combined to construct a complete page. Haskell’s static type-checking ensures that the output is well-formed (though not necessarily valid).

By arranging your code appropriately, you can achieve a satisfactory separation of presentation and logic, but I’m not comfortable with this approach. The combinator idea works excellently for implementing parsers with Parsec but, in my opinion, is not such a good fit for generating web pages. It reminds me a little bit of the dark age of Java web development when pages were generated by servlets concatenating Strings of HTML tags. The combinator approach is more elegant than the unchecked concatenation of Strings in Java, but it’s still an attempt to internalise HTML. I’d rather write my HTML in HTML than in Haskell (or Java), particularly for complex pages with CSS and JavaScript involved.

WASH/HTML

WASH/HTML is another implementation of the combinator approach. It guarantees both well-formedness and validity of its HTML 4.0.1 output. WASH stands for Web Authoring System Haskell. WASH provides a complete Haskell web stack, of which WASH/HTML is a part. With WASH/HTML, a simple Hello World page is generated using the following code:

build_document (head (title (text "Hello World!"))
               ## body (h1 (text "Hello World!")))

Haskell Server Pages

Haskell Server Pages (HSP) brings the ASP/JSP/PHP model to Haskell.  In other words, it mixes presentation mark-up with computations. There are a some minor differences in the Haskell implementation of this idea compared to the imperative variants. Perhaps most interestingly, all XML fragments are actually Haskell expressions, which allows the type-checker to enforce well-formedness. Using HSP, an HTML page can be expressed as a Haskell function as follows (where helloWorld is another function that generates the text content for the page):

page = <html>
         <head><title>Hello World!</title></head>
         <body><p><% helloWorld %></p></body>
       </html>

This is a lot closer to pure HTML than the combinator libraries. HSP also supports the concept of XML pages and hybrid pages, so instead we can create an actual HTML document that includes Haskell code fragments:

<% import System.Time %>
<html>
  <head><title>XML page</title></head>
  <body>
    <h1>Hello World!</h1>
    <p>Page requested at <% getSystemTime %></p>
  </body>
</html>

HSP has roughly the same high-level benefits and drawbacks as JSP and PHP. These technologies give you a lot of power but they can also lead you astray. It takes discipline to maintain a clean separation between logic and presentation. Since HSP permits (requires) side-effects, there’s nothing to stop you from doing truly ugly things such as embedding database update logic in the code that generates your HTML pages.

HStringTemplate

HStringTemplate is a Haskell port of Terence Parr’s StringTemplate engine (originally for Java but also available for C# and Python). StringTemplate is a templating engine along the lines of Apache Velocity but is more restrictive in what processing it permits templates to perform. Specifically, it strictly enforces separation between model and view. It is not possible for a template to cause side-effects elsewhere (no database updates, etc.). StringTemplate can be used for generating any kind of text output, not just XML/HTML. In fact, one of its principal uses is as a code generator for ANTLR.

I have chosen to use HStringTemplate, in preference to the alternatives described above, for my current Haskell project.

A StringTemplate template for an HTML page looks something like this (the StringTemplate website provides more details of the kinds of expressions that can be used):

<html>
  <head><title>Hello</title></head>
  <body><p>Hello $name$</p></body>
</html>

To convert this into an HTML page, the template must be parsed, a value assigned to the “name” attribute, and the HTML rendered to a file. The Haskell code to do this might look like this (see the Haddock documentation for descriptions of the various functions):

import Text.StringTemplate
 
main = do templateText <- readFile "templateFile"
          template = newSTMP templateText
          writeFile "outputFile" html
          where html = toString $ setAttribute "name" "Dan" template

This is only a very simple example. The StringTemplate template language provides facilities for working with lists and maps, and for recursion and basic conditionals. HStringTemplate defines the type class ToSElem for mapping custom data types to types that can be inserted into a template.

I have found that HStringTemplate works very well. It allows me to keep my HTML source separate from my Haskell code. The only criticism I have is that the conditionals are not very expressive. An “if” statement in a template can only check whether a particular attribute is set or unset, or whether a boolean is true or false. The particular problem that I had was that I wanted to apply different formatting depending on whether a value was positive or negative. There was no straightforward way to do this. Instead I had to insert a separate pre-evaluated boolean attribute, isNegative, into the template and check that. This appears to be a (deliberate) limitation of all StringTemplate variants, not just the Haskell version.

Installing GHC 6.10.1 on OS X 10.4

Posted in Haskell, Mac by Dan on November 21st, 2008

Every time I need/decide to upgrade GHC, it seems there’s a different set of hoops I need to jump through to get it working on OS X 10.4 (Tiger). I don’t have OS X 10.5 (Leopard) and I don’t intend to buy it, so unfortunately I don’t get to use the nice-and-simple installer. I’ve decided to write down the exact steps that I’m taking this time so that I have a reference if I need to do it again (or if somebody else needs to do the same).

I’m pretty certain that this isn’t the way I did it last time. I seem to recall manually building the whole thing from a source tarball and having to resolve the dependencies myself. Then again, that’s probably why I have to upgrade now – my 6.8.2 install appears to be broken.

MacPorts and Xcode

The GHC site recommends that Tiger users use MacPorts, so that’s what I’m doing. I would have used fink, because I already have that set-up, but they don’t have a recent GHC build available for Tiger (6.6.2 is relatively ancient).

First I tried to install MacPorts without upgrading Xcode. It hung. So then I did what I had been told (and had ignored) and downloaded the latest version of Xcode from the Apple Developer Connection. For Tiger the latest version is 2.5. 3.0 and above are for Leopard only. At 903mb the download is not exactly slimline. After running the Xcode installer the MacPorts installer worked properly, which was nice.

Installing GHC from MacPorts

After that, it’s supposed to be easy:

$ sudo port install ghc
Password:
sudo: port: command not found

MacPorts installs to /opt/local and I didn’t have /opt/local/bin on the path (it seems that the “postflight script” mentioned here didn’t run or didn’t work). No problem:

$ sudo /opt/local/bin/port install ghc

This is meant to download, build and install the latest GHC and all its dependenices (GMP, yet another version of Perl, etc.).  After some time had elapsed my first attempt failed with this helpful message:

Error: Status 1 encountered during processing.

The GCC output seemed to suggest that it couldn’t find the GMP library that MacPorts had just installed. Google revealed this to be a bug in the Portfile. Somebody else had run into the same problem earlier the same day and the maintainer was on the case. After leaving it for a day, the bug is now fixed and I tried again. This time the installation proceeded without problems, although it took a fecking long time to complete.

Paths and Symlinks

Once the install was done, I removed all traces of the previous 6.8.2 install (which was under /usr/local) and made sure that /opt/local/bin was on my path (in ~/.bash_login).

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.10.1

Excellent. The thing that prompted me to upgrade was that Haddock wasn’t working for me since I upgraded it to the latest version.  So that was the next thing to check:

$ ./setup.hs haddock
setup.hs: haddock version >=0.6 is required but it could not be found.

It seems that for this particular build of GHC the Haddock executable is called haddock-ghc, rather than haddock as in 6.8.2. Cabal is still looking for haddock though, so I added a symlink and everything was fine again:

$ sudo ln -s /opt/local/bin/haddock-ghc /opt/local/bin/haddock

I think I now have a working GHC 6.10.1 installation.

Real World Haskell

Posted in Books, Haskell by Dan on September 2nd, 2008

The book Real World Haskell by Bryan O’Sullivan, Don Stewart, and John Goerzen, will be available to buy from November.

The content is also freely available online already and is well worth a look if, like me, you are keen to learn more about developing actual useful programs with Haskell.

I first mentioned Real World Haskell last year. At the time I also highlighted GHC’s LGPL problems as an obstacle that could potentially discourage the wider adoption of Haskell. It seems that some progress is being made on that front. At present though, GHC will still statically link to GMP, which means that developers who distribute GHC-compiled binaries are distributing “derivative works” as defined by the LGPL.

Revisiting the Comments Debate: The Self-Documenting Code Contest

Posted in Haskell, Software Development by Dan on August 5th, 2008

The great commenting debate generated a lot of disagreement, both here and elsewhere, about the value of code comments with respect to writing self-explanatory code.  If you are of the opinion that good code does not need comments, here is your chance to prove it.  Laurie Cheers has created The Self-Documenting Code Contest.  The idea is to solve a given problem using the most understandabe code that you can write.  No comments are allowed.  The problem is to generate all two-word anagrams of the word “documenting”.

Although I’ve clearly stated my opinion in favour of comments, I decided to give it a shot.  I’ve already submitted my Haskell solution and, to be honest, you’d do well to improve on its readability.  I believe that it satisfies all of the requirements using a brilliantly simple algorithm.

I’ve hidden my code in case you want to try for yourself first.  Click “show” to reveal my solution: show

UPDATE: I got disqualified from the contest for “being a smartass” 🙁

Cedric’s Coding Challenge

Posted in Haskell by Dan on June 28th, 2008

Cedric Beust has posted a programming challenge on his blog.  Seeing as I have nothing better to do, I thought I’d give it a go in Haskell.  Here is a naive brute-force solution that I came up with.  I’m sure there are many optimisations that can be made.

import List(nub)
 
-- Predicate that returns True if a number contains no duplicate digits.
noDuplicateDigits :: Int -> Bool
noDuplicateDigits n = length (nub (digits)) == length digits
                      where digits = show n
 
values :: Int -> [Int]
values n = [x | x <- [1..n], noDuplicateDigits x]
 
-- Given a positive integer n, return the number of values between 1 and n that
-- contain no duplicate digits, and the largest gap between two consecutive
-- values in that sequence.
answer :: Int -> (Int, Int)
answer n = (length sequence, gap)
           where sequence = values n
                 gap = maximum (zipWith subtract sequence (tail sequence))

Useful Haskell Links

Posted in Haskell by Dan on August 16th, 2007

Tutorials

Specifications

Books

Compilers and Interpreters

Monads

Software Transactional Memory

Haskell – Ready for the mainstream?

Posted in Haskell, Software Development by Dan on May 25th, 2007

Having been exposed to pure functional programming in Miranda at university, Haskell is a programming language that I like a lot. I’ve dabbled with it on and off using GHC but I’ve never written a really substantial program in it. Certainly nothing to rival the Java behemoths that I develop day-to-day. Programs written (well) in Haskell are concise, expressive and have an elegance that is hard to match in more general-purpose languages such as C and Java.

Despite the appeals of strongly-typed, side-effect-free programming, Haskell (and non-strict, pure functional languages in general), have long been regarded as primarily the domain of academics. Haskell’s design owes much to the proprietary Miranda system but, unencumbered by commercial constraints, it has rapidly supplanted its predecessor. Even the University of Kent, previously the principal champion of Miranda, has long since switched to Haskell for teaching purposes. Haskell is now a part of undergraduate computer science courses around the world but, despite this, has little visibility in the world of commercial software development.

However, all that may be about to change. This week saw the announcement of the book “Real World Haskell”, to be published by O’Reilly. If the authors deliver on the proposed outline, it promises to provide a real boost for Haskell as a viable language for mainstream software development. The book will cover topics that are often ignored by existing Haskell guides but that are essential for solving real world problems. I/O, databases, GUI development, concurrency and unit testing are just some of the items to be addressed.

At present there is nothing much to see, but I’ll be monitoring their progress closely over the coming months in eager anticipation. Hopefully, by the time the book is out, GHC will have broken free from its LGPL shackles to remove another barrier to widespread Haskell adoption.