Neil Mitchell's Haskell Blog

Pascal's Triangle in Haskell

2012-01-08T13:03:00.003Z

Summary: I'm continually amazed how concise and powerful Haskell is, compared to mainstream languages. This post describes how to write Pascal's Triangle, and gives some of the advantages of using Haskell.

Often, when programming in Haskell, I feel like I'm cheating. As an example, I recently came across this article by William Shields, which suggests that prospective interview candidates be given simple programming tasks like generating Pascal's Triangle. William gives examples in Python, including some of the answers a typical candidate might give.

Pascal's Triangle in Haskell

William describes Pascal's Triangle as:

"The root element is 1. Every other element is the sum of the one or two above it (diagonally left and diagonally right)."

As a Haskell programmer, the obvious technique to use is induction. The first row of the triangle is [1], and each row can be computed from the previous row by adding the row shifted left, and the row shifted right:


next xs = zipWith (+) ([0] ++ xs) (xs ++ [0])
pascal = iterate next [1]

Here, we define next to take one row and produce the next row. We then use the iterate function to repeatedly apply next starting at the root element. The solution is short, and follows from the definition.

Laziness for Modularity

William originally posed three questions:

Print out the triangle to a specific row: print $ take 100 pascal

Return a given row of the triangle: pascal !! 50

Return a given element (by row and index) of the triangle: pascal !! 10 !! 5

Thanks to laziness, we can concisely answer all these questions in terms of the original pascal definition. In contrast, using a language such as Python, the best solution (Dynamic Programming from the original article) can only perform the first task.

Interview problems

The original article was not about the choice of programming language, but about choosing suitable questions for interviewing programmers. I agree with William that Pascal's Triangle is a suitable problem - it isn't a trick puzzle, it isn't an API knowledge quiz - it's about understanding how to program. Given how much easier the problem is to solve in Haskell, I wonder if using Haskell in a job interview should be considered cheating? ;-)

Hiding Win32 Windows

2012-01-08T11:38:00.006Z

Summary: This post describes how to hide windows on the Windows operating system, by using the Win32 API from Haskell.

Imagine that whenever your computer restarts, it pops up a message box:

If you interact with this window, your computer will be destroyed. You can't kill the process, or dismiss the window harmlessly. (This scenario isn't hypothetical...) The solution is to hide the window, so it still exists but is out of the way of misplaced clicks. To hide the window, we first find it's OS handle, then we call some Win32 API functions.

Find the Window

To find the handle of the window, we use Spy++. Spy++ comes with Visual Studio, and is bundled in the Express edition (the free version) from 2010 onwards. Start Spy++, got to Search, Find Window, then use the finder tool to select the window in question. Check that the caption of the window matches what Spy++ reports:

The important information is the handle: 0004061E.

Hide the Window

To hide the window you need a programming language capable of making Win32 API calls. In the past I have used Word VBA as the host language, but Haskell is probably easier. Start GHCi, and type:


$ import System.Win32
$ import Graphics.Win32
$ showWindow (castUINTToPtr 0x0004061E) sW_HIDE

Replace 0x0004061E on the final line with 0xyour-handle. The final line should cause the window to be hidden, saving your computer from destruction.

Thanks: Thanks to Roman Leshchinskiy for reminding me that there were better solutions than just trying not to click the window. Thanks to the Win32 Haskell developers - the Win32 binding was a lot of work, which not many people ever see.

Enabling Reply To All in Outlook - version 2

2011-12-14T21:14:00.004Z

I previously described how to enable Reply To All in Outlook. Since then I've modified the VBA script so it works on both Office 2003 and 2007, gives better error messages, automatically replaces the disabled Reply To All buttons, allows editing messages (even if that feature has been disabled) and strips messages of inline images. Installation instructions and links to the code are in the user manual:

http://community.haskell.org/~ndm/darcs/office/ReplyToAll.htm

I don't want to duplicate the installation instructions here, as I will likely revise them over time. However, at the bottom of the manual is a plea to Outlook administrators not to disable Reply To All in the first place. I don't think arguments against disabling essential email functionality can be made often enough, so here is my plea:

Plea to Outlook Administrators

Please do not disable essential email functionality. With the workarounds linked to above, the attempt is futile, but remains deeply inconvenient. Consider the situation where Alice sends an email to Bob, Charlie and Dave asking for some financial details of Mega Corp. Bob has the details on a post-it note on his desk and quickly replies to everyone with the information. But in a world without Reply To All...

Bob replies just to Alice. Charlie, being the helpful soul he is, decides to search through the filing cabinet for the information. 15 minutes later Charlie finds the details and emails Alice, only to be told "Thanks, Bob answered this 15 minutes ago". Charlie realises he just wasted 15 minutes of his life, and goes to get a cookie to make himself feel better.

Bob replies just to Alice. At the end of the week Dave is reviewing his emails and realises that Alice still hasn't got a reply, but before he potentially wastes 15 minutes, he drops Alice an email - "Do you still want those details?". Alice replies "No". Dave concludes that he's a clever bunny for not going to the filing cabinet, and decides a one week latency when replying to Alice is just common sense.

Bob replies, but realising the potential cost of replying just to Alice, also replies to Charlie and Dave. Bob spent a minute retyping the recipient list, and wonders "Why can't Outlook have a button that does this for me?".

Bob replies, also including Charles and Dave. Woops! That should have been Charlie, not Charles. As a best case scenario, Charles gets annoyed with a useless email, but at worst Charles brings down Mega Corp with the sensitive information gleaned from the email. Charlie still ends up going to get a cookie.

Removing Reply To All increases the volume of email required, and increases the risk of email accidents. I've heard only two arguments against Reply To All, both of which are wrong:

When Bob replies to everyone, the financial information about Mega Corp gets sent to Charlie, but what if Charlie shouldn't have access to that information? Of course, if Charlie shouldn't have access to that information then Alice was at fault for sending the request to Charlie in the first place. Bob should also check when sending sensitive information, but most emails are not sensitive (it is a poor default), checking the senders should not require retyping the senders (it is a poor user interface) and by default mailing lists are not fully expanded (so he won't be able to tell the full list of senders anyway).

When Zorg, the owner of Mega Corp, sends a Christmas email to all his employees, what if one of them hits Reply To All? That wastes a lot of company time, and should be prevented - but not on the client side. It is possible to restrict the number of recipients to an email, Zorg could send out the email with everyone in the BCC field, or IT could set up a mailing list which does not permit replies.

Abstract Generics with Uniplate

2011-11-05T12:17:00.005Z

Summary: The new version of Uniplate has several wrappers for working with abstract data types, such as Map from the containers package. These wrappers let you transform abstract data types without breaking their invariants.

Abstract data types, such as Map from the containers package, hide their internal structure so they can maintain invariants necessary for their correct operation. Generic programming, such as the Data class used by SYB, allows programs to generically traverse data types, without detailed knowledge of their structure. The two are somewhat incompatible - if Map allows manipulating it's internal structure, the invariants could be broken causing Map to perform incorrectly.

Using the Data class, a Map String Int claims it has no constructors, but if you operate on it with gfoldl is behaves as though it were [(String,Int)]. When Uniplate traverses the Map, such as when searching for an Int, it first analyses the available constructors to see if a Map String Int can possibly contain an Int. Since Map has no constructors, it concludes that Map cannot contain an Int, and Uniplate fails to operate on the contained Int's.

For people who use the Data-style Uniplate module, using the new version of Uniplate you can now correctly operate over Map String Int, provided you use the newtype Map wrapper from Data.Generics.Uniplate.Data.Instances. When you transform over Bool (which does not touch the Map) it will ignore the Map and take O(1). When you transform over Int it will reconstruct the Map in O(n), and if you transform String or Char it will reconstruct the Map in O(n log n). Regardless of what operations you do, it will work efficiently and correctly. As an example:


$ import qualified Data.Map as Map
$ import Data.Char
$ import Data.Generics.Uniplate.Data
$ import Data.Generics.Uniplate.Data.Instances
$ fromMap $ transformBi toUpper $ toMap $ Map.fromList [("haskell",12),("test",18)]
fromList [("HASKELL",12),("TEST",18)]

There are two approaches for dealing with the Map problem in Uniplate. For users of the Direct-style Uniplate module, there is a function plateProject, which has been available for some time. For users of the Data-style Uniplate module, or for users of the SYB package, there is a new module Data.Generics.Uniplate.Data.Instances in uniplate-1.6.4 (released today) which provides three types with special Data instances (Hide, Trigger, Invariant). Using these three types we can construct wrappers providing Data instances for abstract types, and Uniplate includes wrappers for several of the types in the containers package (Map, Set, IntMap, IntSet).

plateProject

The plateProject function helps you define Direct Uniplate instances for abstract types. Instead of defining how to examine the data type, you instead define how to transform the data type into one you can examine, and how to transform it back. As an example:


instance Biplate (Map.Map [Char] Int) Char where
    biplate = plateProject Map.toList Map.fromList

If the types ensure that any operations will not change the keys we can optimise and use the fromDistictAscList function to reconstruct the Map:


instance Biplate (Map.Map [Char] Int) Int where
    biplate = plateProject Map.toAscList Map.fromDistinctAscList

Hide

The Hide data type is useful for wrapping values that you want to ignore with Uniplate. The type is defined as:


data Hide a = Hide {fromHide :: a}

But has a Data instance that pretends it is defined using the extension EmptyDataDecls as:


data Hide a

As an example of avoiding particular values, you can write:


transformBi (+1) (1, 2, Hide 3, Just 4) == (2, 3, Hide 3, Just 5)

As a result of having no constructors, any calls to the methods toConstr or gunfold will raise an error.

Trigger

The Trigger data type is useful for determining when a value was constructed with the Data methods. It is defined as:


data Trigger a = Trigger {trigger :: Bool, fromTrigger :: a}

But the Data instance pretends that it is defined as:


data Trigger a = Trigger a

However, whenever gfoldl or gunfold constructs a new value, it will have the trigger field set to True. The trigger information is useful to indicate whether any invariants have been broken, and thus need fixing. As an example:


data SortedList a = SortedList (Trigger [a]) deriving (Data,Typeable)
toSortedList xs = SortedList $ Trigger False $ sort xs
fromSortedList (SortedList (Trigger t xs)) = if t then sort xs else xs

This data type represents a sorted list. When constructed the items are initially sorted, but operations such as gmapT could break that invariant. The Trigger type is used to detect when the Data operations have been performed, and resort the list.

The Trigger type is often used in conjunction with Invariant, which fixes the invariants.

Invariant

The Invariant data type is useful for ensuring that an invariant is always applied to a data type. It is defined as:


data Invariant a = Invariant {invariant :: a -> a, fromInvariant :: a}

But the Data instance pretends that it is defined as:


data Invariant a = Invariant a

Whenever a gfoldl constructs a new value, it will have the function in the invariant field applied to it. As an example:


data SortedList a = SortedList (Invariant [a]) deriving (Data,Typeable)
toSortedList xs = SortedList $ Invariant sort (sort xs)
fromSortedList (SortedList (Invariant _ xs)) = xs

Any time an operation such as gmapT is applied to the data type, the invariant function is applied to the result. The fromSortedList function can then rely on this invariant.

The gunfold method is partially implemented - all constructed values will have an undefined value for all fields, regardless of which function is passed to fromConstrB. If you only use fromConstr (as Uniplate does) then the gunfold method is sufficient.

Map

Using the Hide, Trigger and Invariant types, we can define a wrapper for the containers Map type as:


newtype Map k v = Map (Invariant (Trigger [k], Trigger [v], Hide (Map.Map k v)))
    deriving (Data, Typeable)

The Map type is defined as an Invariant of three components - the keys, the values, and the underlying Map. We use Invariant to ensure that the keys/values/map always remain in sync. We use Trigger on the keys and values to ensure that whenever the keys or values change we rebuild the Map, but if they don't, we reuse the previous value. The function to extract a containers Map from the wrapper requires only simple pattern matching:


fromMap (Map (Invariant _ (_,_,Hide x))) = x

The function to wrap a containers Map is slightly harder, as we need to come up with an invariant restoring function:


toMap :: Ord k => Map.Map k v -> Map k v
toMap x = Map $ Invariant inv $ create x
    where
        create x = (Trigger False ks, Trigger False vs, Hide x)
            where (ks,vs) = unzip $ Map.toAscList x

        inv (ks,vs,x)
            | trigger ks = create $ Map.fromList $ zip (fromTrigger ks) (fromTrigger vs)
            | trigger vs = create $ Map.fromDistinctAscList $ zip (fromTrigger ks) (fromTrigger vs)
            | otherwise = (ks,vs,x)

The create function creates a value from a Map, getting the correct keys and values. The inv function looks at the triggers on the keys/values. If the keys trigger has been tripped, then we reconstruct the Map using fromList. If the values trigger has been tripped, but they keys trigger has not, we can use fromDistinctAscList, reducing the complexity of constructing the Map. If nothing has changed we can reuse the previous value.

The end result is that all Uniplate (or SYB) traversals over Map result in a valid value, which has had all appropriate transformations applied.

Haskell Implementors Workshop 2011

2011-11-01T18:00:00.003Z

The videos from the Haskell Implementors Workshop 2011 are now online at YouTube. I'm currently uploading them to Vimeo, but that will take another week (I ran out of free quota).

Many thanks to Kento EMOTO who did all the editing and conversion, and to all the speakers for the great talks.

Calling Haskell from R

2011-10-30T09:55:00.004Z

Summary: This post describes how to write a function in Haskell, and then call it from R.

R is a very popular language for statistics, particular with biologists (and computational paleobiologists). For writing high performance code, the R developers recommend the use of C or Fortran - not languages that are particularly easy for beginners. However, you can instead write a Haskell function that can be called directly from R. The basic idea is to create a C compatible library using Haskell (as described in the GHC users manual) and then call that library from R (as described in this document). As a simple example, let's write a function that adds up the square roots of a list of numbers.

Create an R-compatible Haskell library

In normal Haskell, we would define the function to add up the square roots of a list as:


sumRoots :: [Double] -> Double
sumRoots xs = sum (map sqrt xs)

However, to make a function that is compatible with R, we have to follow two rules:

Every argument must be a Ptr to a C compatible type, typically Int, Double or CString. (To be pedantic, we should probably use CInt or CDouble, but using GHC on Windows these types are equivalent - keeping things simpler.)

The result must be IO ()

Obeying these restrictions, we need to use the type:


sumRootsR :: Ptr Int -> Ptr Double -> Ptr Double -> IO ()
sumRootsR n xs result = ...

Instead of passing in the list xs, we now pass in:

n, the length of the list xs

xs, the elements of the list

result, a space to put the result

We can implement sumRootsR by using the functions available in the Foreign module:


sumRootsR :: Ptr Int -> Ptr Double -> Ptr Double -> IO ()
sumRootsR n xs result = do
    n <- peek n
    xs <- peekArray n xs
    poke result $ sumRoots xs

This function first gets the value for n, then for each element in 0..n-1 gets the element out of the pointer array xs and puts it in a nice list. We then call the original sumRoots, and store the value in the space provided by result. As a general rule, you should put all the logic in one function (sumRoots), and the wrapping in another (sumRootsR). We can then export this function with the definition:


foreign export ccall sumRootsR :: Ptr Int -> Ptr Double -> Ptr Double -> IO ()

Putting everything together, we end up with the Haskell file:


-- SumRoots.hs
{-# LANGUAGE ForeignFunctionInterface #-}
module SumRoots where

import Foreign

foreign export ccall sumRootsR :: Ptr Int -> Ptr Double -> Ptr Double -> IO ()

sumRootsR :: Ptr Int -> Ptr Double -> Ptr Double -> IO ()
sumRootsR n xs result = do
    n <- peek n
    xs <- peekArray n xs
    poke result $ sumRoots xs

sumRoots :: [Double] -> Double
sumRoots xs = sum (map sqrt xs)

We also need a C stub file. The one described in the GHC users guide works well:


// StartEnd.c
#include <Rts.h>

void HsStart()
{
   int argc = 1;
   char* argv[] = {"ghcDll", NULL}; // argv must end with NULL

   // Initialize Haskell runtime
   char** args = argv;
   hs_init(&argc, &args);
}

void HsEnd()
{
   hs_exit();
}

We can now compile our library with the commands:


ghc -c SumRoots.hs
ghc -c StartEnd.c
ghc -shared -o SumRoots.dll SumRoots.o StartEnd.o

This creates the library SumRoots.dll.

Calling Haskell from R

At the R command prompt, we can load the library with:


dyn.load("C:/SumRoots.dll") # use the full path to the SumRoots library
.C("HsStart")

We can now invoke our function:


input = c(9,3.5,5.58,64.1,12.54)
.C("sumRootsR", n=as.integer(length(input)), xs=as.double(input), result=as.double(0))$result

This prints out the answer 18.78046.

We can make this function easier to use on the R side by writing a wrapper, for example:


sumRoots <- function(input)
{
    return(.C("sumRootsR", n=as.integer(length(input)), xs=as.double(input), result=as.double(0))$result)
}

Now we can write:


sumRoots(c(12,444.34))

And get back the answer 24.54348. With a small amount of glue code, it's easy to call Haskell libraries from R programs.

Haskell Implementors Workshop 2011 slides

2011-10-01T18:28:00.003+01:00

I've just uploaded the slides for all the talks given at the Haskell Implementors Workshop 2011 - just click on "Slides" next to any of the talks. Many thanks to all the speakers for very interesting talks, and for sending me their slides.

There will be video, hosted on either YouTube or Vimeo, at some point in the future. I've got all the copyright permission forms, but I don't yet have the video footage. I'm currently working to get a copy of the video sent from Japan.

Template Haskell fights with Generic Programming

2011-10-01T08:00:00.004+01:00

Summary: The InfixE construction in Template Haskell fits poorly with generic programming, because its type does not capture all its restrictions. This mismatch can result in confusing bugs, but there is a simple workaround.

I have often said that anyone manipulating abstract syntax trees, without using some form of generic programming, is doing it wrong. Recently I have been manipulating Template Haskell syntax trees using Uniplate, my preferred generic programming library. Consider the problem of replacing all instances of delete with deleteBy (==) - this task can be done with Template Haskell:


{-# LANGUAGE TemplateHaskell #-}
module IHateDelete where
import Data.List
import Language.Haskell.TH
import Data.Generics.Uniplate.Data

iHateDelete :: Q [Dec] -> Q [Dec]
iHateDelete = fmap (transformBi f)
    where
        f :: Exp -> Exp
        f (VarE x) | x == 'delete = VarE 'deleteBy `AppE` VarE '(==)
        f x = x

We can test this function with:


{-# LANGUAGE TemplateHaskell #-}
import IHateDelete
import Data.List

$(iHateDelete
    [d|
        mapDelete x = map (delete x)
        myElem x xs = length (delete x xs) /= length xs
    |])

To see the result of running iHateDelete pass the flag -ddump-splices. As far as we can tell, our iHateDelete function works perfectly. But wait - let's try another example:


$(iHateDelete
    [d|
        myDelete x xs = x `delete` xs
    |])

In GHC 6.12, we get a GHC panic. In GHC 7.2 we get the error message:


Operator application with a non-variable operator: deleteBy (==)
(Probably resulting from a Template Haskell splice)

(I would find this message far clearer if it said "Infix application..." rather than "Operation application...")

The body of myDelete starts out as:


InfixE (Just (VarE 'x)) (VarE 'delete) (Just (VarE' xs))

After our transformation, this becomes:


InfixE (Just (VarE 'x)) (AppE (VarE 'deleteBy) ('(==))) (Just (VarE' xs))

Or, written in Haskell syntax:


x `deleteBy (==)` xs

This expression is not valid Haskell, and causes an error when spliced back in (when inserted back into the Haskell code).

The Problem

The underlying problem is called out in the Template Haskell Exp documentation:


InfixE (Maybe Exp) Exp (Maybe Exp)
    -- ^ It's a bit gruesome to use an Exp as the operator, but how else can we distinguish constructors from non-constructors?
    --   Maybe there should be a var-or-con type? Or maybe we should leave it to the String itself?

The operator in InfixE has a type which permits any expression, but has the restriction that when spliced back in the expression must only be a VarE or ConE. This restriction poses a problem for generic programming, where values are treated in a uniform manner. Sadly, both of the suggested fixes would also cause problems for generic programming. Perhaps the true fix is to let Haskell have arbitrary expressions for infix operators? Or perhaps Template Haskell should translate InfixE to AppE if the operator is incompatible with Haskell?

The Workaround

As a workaround, you can translate away all InfixE expressions that have a complex middle expression. I use the following function:


fixupInfix :: [Dec] -> [Dec]
fixupInfix = transformBi f
    where
        bad VarE{} = False
        bad ConE{} = False
        bad _ = True

        f (InfixE a b c) | bad b = case (a,c) of
            (Nothing, Nothing) -> b
            (Just a , Nothing) -> b `AppE` a
            (Nothing, Just c ) -> VarE 'flip `AppE` b `AppE` c
            (Just a , Just c ) -> b `AppE` a `AppE` c
        f x = x

The original iHateDelete can then be modified to become:


iHateDelete = fmap (fixupInfix . transformBi f)

Faster WPF ComboBoxes

2011-09-06T18:43:00.002+01:00

If you create a WPF ComboBox with 2000 items it will take about 2 seconds to drop down, and about 1 second to retract back. But you can make all operations complete instantly if the items are simple (such as strings). If you are writing XAML, add:


<ComboBox>
  <ComboBox.ItemsPanel>
    <ItemsPanelTemplate>
      <VirtualizingStackPanel />
    </ItemsPanelTemplate>
  </ComboBox.ItemsPanel>

  ...
</ComboBox>

If you are writing C#, add:


comboBox.ItemsPanel = new ItemsPanelTemplate(new FrameworkElementFactory(typeof(VirtualizingStackPanel)));

Thanks to Henry Hahn for the XAML code I started from. Reading the C# version, I am reminded of the Hammer Factory joke.

Sharing in Haskell

2011-09-04T13:07:00.002+01:00

Summary: The let and lambda constructs give a precise way to control sharing, but their exact use can be tricky. This post gives some worked examples and general guidance.

An easy way to improve performance is to call something fewer times, which requires understanding how many times something gets called. One topic I find myself regularly explaining is how lambda expressions under let expressions affect sharing. Consider the two following examples:

Example 1


f x y = sqrt x + y

result = f 1 2 + f 1 4

Example 2


f x = let sqrt_x = sqrt x in \y -> sqrt_x + y

result = let f_1 = f 1 in f_1 2 + f_1 4

Question

In each example, how many times is sqrt executed to compute result? (Assume no advanced optimisations - these often break down on larger examples.)

Answer

In Example 1 we execute sqrt twice, while in Example 2 we execute sqrt once. To go from Example 1 to Example 2 we need to make two changes:

Step 1: Rewrite f to compute sqrt after one argument instead of two.

Step 2: Rewrite result to share the result of f with one argument.

Performing either rewrite alone will still result in sqrt being executed twice.

Step 1: Rewriting f

Let's take a look at the original definition of f:


f x y = sqrt x + y

Rewriting this function in English, we can describe it as:


given x and y, compute sqrt x + y

But the computation of sqrt x does not depend on y. If the computation of sqrt x is expensive, and if we know the function will often be called with the same x for many different values of y, it is better to describe it as:


given x, compute sqrt x, then given y, add that value to y

The Haskell syntax for this description is:


f = \x -> let sqrt_x = sqrt x in \y -> sqrt_x + y

Which would usually be written in the equivalent declaration form as:


f x = let sqrt_x = sqrt x in \y -> sqrt_x + y

Step 2: Using the rewritten f

If we look at the definition of result:


result = f 1 2 + f 1 4

We see that the subexpression f 1 occurs twice. We can perform common subexpression elimination (CSE) and write:


result = let f_1 = f 1 in f_1 2 + f_1 4

With the original definition of f, commoning up f 1 would have had no performance benefit - after f was applied to 1 argument it did nothing but wait for the second argument. However, with the revised definition of f, the value f_1 will create the computation of sqrt 1, which will be performed only once when executed by f_1 2 and f_1 4.

The Optimisation

This optimisation technique can be described as:

Step 1: Rewrite the function to perform some computation before all arguments are supplied.

Step 2: Share the partially applied function.

Crucially the function in Step 1 must take it's arguments in an order that allows computation to be performed incrementally.

A Practical Example

In previous versions of Hoogle, the function I wrote to resolve type synonyms (e.g. type String = [Char]) was:


resolveSynonyms :: [Synonym] -> TypeSig -> TypeSig

Given a list of type synonyms, and a type signature, return the type signature with all synonyms expanded out. However, searching through a list of type synonyms is expensive - it is more efficient to compute a table allowing fast lookup by synonym name. Therefore, I used the optimisation technique above to write:


resolveSynonyms synonyms = let info = buildSynonymTable synonyms in \x -> transformSynonyms info x

This technique worked well, especially given that the list of synonyms was usually constant. However, from simply looking at the type signatures, someone else is unlikely to guess that resolveSynonyms should be partially applied where possible. An alternative is to make the sharing more explicit in the types, and provide:


data SynonymTable

buildSynonymTable :: [Synonym] -> SynonymTable

resolveSynonyms :: SynonymTable -> TypeSig -> TypeSig

The disadvantage is the increase in the size of the API - we have gone from one function to two functions and a data type. Something that used to take one function call now takes two.

Conclusion

I think all Haskell programmers benefit from understand how the interaction of lambda and let affect sharing. Pushing lambda under let is often a useful optimisation technique, particularly when the resulting function is used in a map. However, I wouldn't usually recommend exporting public API's that rely on partial application to get acceptable performance - it's too hard to discover.

IFL 2011 submission

2011-08-19T11:54:00.003+01:00

Summary: Submit to IFL 2011. It's a great breeding ground for ideas.

The IFL 2011 submission deadline has been extended until 31st August, and, in a move I thoroughly agree with, the notification of acceptance is now within 24 hours of submission!

IFL (and TFP) do not work in the same way as ICFP/Haskell Symposium. You submit a paper, describing the work you've done (something functional programming related) and then present the paper. After the conference, you resubmit the paper, and the result is reviewed in greater depth. There is a great opportunity to learn from the experience, and produce a second paper that is far better.

I submitted my original supercompilation work to IFL 2007. You can compare the paper I submitted before the conference with the paper I submitted afterwards. Note that the original paper doesn't even mention the word supercompilation! At the conference I talked to many people, learnt a lot about supercompilation, program optimisation and termination orderings (and lots of other interesting topics). Using this experience, and building on the enthusiasm people had expressed, I was able to produce a much better second paper. My work on supercompilation went into my thesis, and lead to a subsequent ICFP paper.

I think that IFL/TFP are great venues for to present your work, and in presenting and discussing it, to understand more about the work - making it better in the process. You have just under 2 weeks to make the IFL 2011 deadline of 31st August.

Submit to the Haskell Implementors Workshop

2011-07-17T16:40:00.002+01:00

Are you going to ICFP 2011 in Japan? Do you work with Haskell? You should consider offering a talk for the Haskell Implementors Workshop! You have until this coming Friday (22nd July 2011) to offer a talk, by emailing an abstract (less than 200 words) to benl -AT- cse.unsw.edu.au - for full details see the Call for Talks. Talks are 20 minutes long, plus 10 minutes for questions.

What topics are suitable?

If you have been doing or thinking stuff that would interest a bunch of Haskell implementors in a pub, you probably have something suitable for a talk. The aim of the workshop is to provide an "opportunity to bat around ideas, share experiences, and ask for feedback from fellow experts". Unlike ICFP or the Haskell Symposium, there are no published proceedings. If you have some work that isn't quite ready for a more formal setting, this workshop is a useful venue to seek feedback. If you have an idea which seems a bit crazy, it's probably also very interesting!

What if I have less to say?

In addition to the 30 minute talks, the Haskell Implementors Workshop will also have 2-10 minute lightening talks, organised on the day. Attend the workshop, and sign up on the day to give a brief talk.

Changing the Windows titlebar gradient colors

2011-06-18T13:08:00.005+01:00

Summary: This post describes how to change the gradient colors of the titlebar of a single window on Windows XP, using C#.

On Windows XP the titlebar of most windows have a gradient coloring:

For various reasons, I wanted to override the titlebar gradient colors on a single window. The SetSysColors function can change the colors, but that applies to all windows and immediately forces all windows to repaint, which is slow and very flickery. You can paint the titlebar your self (like Chrome does), but then you need to draw and handle min/max buttons etc. After some experimentation, using the unofficial SetSysColorsTemp function, I was able to change the gradient for a single window. As an example, here are some screenshots, overriding the left color with green, then overriding both the colors with green/blue and orange/blue:

Disclaimer: This code uses an undocumented function, and while it seems to work robustly on my copy of Windows XP, it unlikely to work on future versions of Windows. Generally, it is a bad idea to override user preferences - for example the titlebar text may not be visible with overridden gradient colors.

All the necessary code is available at the bottom of this post, and can be used by anyone, for any purpose. The crucial function is SetSysColorsTemp, which takes an array of colors and an array of brushes created from those colors. If you call SetSysColorsTemp passing a new array of colors/brushes they will override the global system colors until a reboot, without forcing a repaint. Passing null for both arrays will restore the colors to how they were before. To make the color change only for the current window we hook into WndProc, and detect when the colors are about to be used in a paint operation. We set the system colors before, call base.WndProc which paints the titlebar (using our modified system colors), then put the colors back.

There are two known issues:

1) If you change the colors after the titlebar has drawn, it will not use the colors until the titlebar next repaints. I suspect this problem is solvable.
2) As you can see in the demo screenshots, the area near the min/max buttons does not usually get recolored. If you only change the left gradient color this doesn't matter.


public class GradientForm : Form
{
    // Win32 API calls, often based on those from pinvoke.net
    [DllImport("gdi32.dll")] static extern bool DeleteObject(int hObject);
    [DllImport("user32.dll")] static extern int SetSysColorsTemp(int[] lpaElements, int [] lpaRgbValues, int cElements);
    [DllImport("gdi32.dll")] static extern int CreateSolidBrush(int crColor);
    [DllImport("user32.dll")] static extern int GetSysColorBrush(int nIndex);
    [DllImport("user32.dll")] static extern int GetSysColor(int nIndex);
    [DllImport("user32.dll")] private static extern IntPtr GetForegroundWindow();

    // Magic constants
    const int SlotLeft = 2;
    const int SlotRight = 27;
    const int SlotCount = 28; // Math.Max(SlotLeft, SlotRight) + 1;

    // The colors/brushes to use
    int[] Colors = new int[SlotCount];
    int[] Brushes = new int[SlotCount];

    // The colors the user wants to use
    Color titleBarLeft, titleBarRight;
    public Color TitleBarLeft{get{return titleBarLeft;} set{titleBarLeft=value; UpdateBrush(SlotLeft, value);}}
    public Color TitleBarRight{get{return titleBarRight;} set{titleBarRight=value; UpdateBrush(SlotRight, value);}}

    void CreateBrushes()
    {
        for (int i = 0; i < SlotCount; i++)
        {
            Colors[i] = GetSysColor(i);
            Brushes[i] = GetSysColorBrush(i);
        }
        titleBarLeft = ColorTranslator.FromWin32(Colors[SlotLeft]);
        titleBarRight = ColorTranslator.FromWin32(Colors[SlotRight]);
    }

    void UpdateBrush(int Slot, Color c)
    {
        DeleteObject(Brushes[Slot]);
        Colors[Slot] = ColorTranslator.ToWin32(c);
        Brushes[Slot] = CreateSolidBrush(Colors[Slot]);
    }

    void DestroyBrushes()
    {
        DeleteObject(Brushes[SlotLeft]);
        DeleteObject(Brushes[SlotRight]);           
    }

    // Hook up to the Window

    public GradientForm()
    {
        CreateBrushes();
    }

    protected override void Dispose(bool disposing)
    {
        if (disposing) DestroyBrushes();
        base.Dispose(disposing);
    }

    protected override void WndProc(ref System.Windows.Forms.Message m) 
    {
        const int WM_NCPAINT = 0x85; 
        const int WM_NCACTIVATE = 0x86;

        if ((m.Msg == WM_NCACTIVATE && m.WParam.ToInt32() != 0) ||
            (m.Msg == WM_NCPAINT && GetForegroundWindow() == this.Handle))
        {

            int k = SetSysColorsTemp(Colors, Brushes, Colors.Length);
            base.WndProc(ref m); 
            SetSysColorsTemp(null, null, k);
        }
        else
            base.WndProc(ref m); 
    }
}

INLINE pragmas in the Safe library

2011-06-07T20:03:00.002+01:00

Summary: The Safe library has lots of small functions, none of which have INLINE pragmas on them. The lack of INLINE pragmas probably has no effect on the optimisation.

I was recently asked a question about the Safe library:

I was wondering why you didn't use any INLINE pragmas in the Safe library. I'm not a Haskell expert yet, but I've noticed that in many other libraries most one-liners are annotated by INLINE pragmas, so is there any reason you didn't add them to Safe as well?

When compiling with optimisations, GHC tries to inline functions/values that are either "small enough" or have an INLINE pragma. These functions will be inlined within their module, and will also be placed in their module's interface file, for inlining into other modules. The advantage of inlining is avoiding the function call overhead, and possibly exposing further optimisations. The disadvantage is that the code size may grow, which may result in poor utilisation of the processor's instruction cache.

The Safe library contains wrappers for lots of partial Prelude and Data.List functions (i.e. head), with versions that don't fail, or fail with more debugging information. Using the tail function as an example, the library supplies four additional variants:

tail :: [a] -> [a], crashes on tail []

tailNote :: String -> [a] -> [a], takes an extra argument which supplements the error message

tailDef :: [a] -> [a] -> [a], takes a default to return instead of errors

tailMay :: [a] -> Maybe [a], wraps the result in a Maybe

tailSafe :: [a] -> [a], returns some sensible default if possible, [] in the case of tail

As the questioner correctly noted, there are no INLINE pragmas in the library. Taking the example of tailSafe, it is defined as:


tailSafe :: [a] -> [a]
tailSafe = liftSafe tail null

liftSafe :: (a -> a) -> (a -> Bool) -> (a -> a)
liftSafe func test val = if test val then val else func val

Given this indirection, and the lack of an INLINE pragma, is calling tailSafe as cheap as you might hope? We can answer this question by looking at the interface file at the standard optimisation level, by running ghc -ddump-hi Safe.hs -O -c. Looking at the definition attached to tailSafe, we see:


tailSafe = \val -> case val of
    [] -> []
    ds1:ds2 -> ds2

The tailSafe function has been optimised as much as it can be, and will be inlined into other modules. Adding an INLINE pragma would have no effect at standard optimisation. When compiling without optimisation, even with an INLINE pragma, the function is not included in the module's interface. Adding the INLINE pragma to tailSafe is of no benefit.

Let us now look at all functions in the Safe module. When compiled without optimisation (-O0) no functions are placed in the interface file. At all higher levels of optimisation (-O1 and -O2) the interface files are identical. Looking through the functions, only 6 functions are not included in the interface files:

abort

The abort function is defined as:


abort = error

Neither adding an INLINE pragma or eta expanding (adding an additional argument) includes the function in the interface file. I suspect that GHC decides no further optimisation is possible, so doesn't ever inline abort.

atMay and $watMay

The function atMay is recursive, and thus cannot be inlined even when it's definition is available, so GHC sensibly omits it from the interface file. The function $watMay is the worker/wrapper definition of atMay, which is also recursive.

readNote and readMay

The functions readNote and readMay both follow exactly the same pattern, so I describe only readNote. The function readNote is quite big, and GHC has split it into two top-level functions - producing both readNote and readNote1. The function readNote is included in the interface file, but readNote1 is not. The result is that GHC will be able to partially inline the original definition of readNote - however, the read functions tend to be rather complex, so GHC is unlikely to benefit from the additional inlining it has managed to acheive.

atNote

The atNote function is bigger than the inlining threshold, so does not appear in the interface file unless an INLINE pragma is given. Since the inner loop of atNote is recursive, it is unlikely that inlining would give any noticable benefit, so GHC's default behaviour is appropriate.

Conclusion

Having analysed the interface files, I do not think it is worth adding INLINE pragmas to the Safe library - GHC does an excellent job without my intervention. My advice is to only add INLINE pragmas after either profiling, or analysing the resulting Core program.

Hoogle talk from TFP 2011 [PDF]

2011-05-22T14:26:00.003+01:00

Last week I went to TFP 2011, and gave a talk on Hoogle entitled "Finding Functions from Types". The slides are now available online. These slides give some information about how the type searching works in Hoogle, and I intend to write further details in the future.

CmdArgs is not dangerous

2011-05-08T20:25:00.002+01:00

Summary: CmdArgs can be used purely, and even if you choose to use it in an impure manner, you don't need to worry.

As a result of my blog post yesterday, a few people have said they have been put off using CmdArgs. There are three reasons why you shouldn't be put off using CmdArgs, even though it has some impure code within it.

1: You can use CmdArgs entirely purely

You do not need to use the impure code at all. The module System.Console.CmdArgs.Implict provides two ways to write annotated records. The first way is impure, and uses cmdArgs and &=. The second way is pure, and uses cmdArgs_ and +=. Both ways have exactly the same power. For example, you can write either of:


sample = cmdArgs $
    Sample{hello = def &= help "World argument" &= opt "world"}
    &= summary "Sample v1"

sample = cmdArgs_ $
    record Sample{} [hello := def += help "World argument" += opt "world"]
    += summary "Sample v1"

The first definition is impure. The second is pure. Both are equivalent. I prefer the syntax of the first version, but the second version is not much longer or uglier. If the impurities scare you, just switch. The Implicit module documentation describes four simple rules for converting between the two methods.

2: You do not need to use annotated records at all

Notice that the above module is called Implicit, CmdArgs also features an Explicit version where you create a data type representing your command line arguments (which is entirely pure). For example:


arguments :: Mode [(String,String)]
arguments = mode "explicit" [] "Explicit sample program" (flagArg (upd "file") "FILE")
     [flagOpt "world" ["hello","h"] (upd "world") "WHO" "World argument"
     ,flagReq ["greeting","g"] (upd "greeting") "MSG" "Greeting to give"
     ,flagHelpSimple (("help",""):)]
     where upd msg x v = Right $ (msg,x):v

Here you construct modes and flags explicitly, and pass functions which describe how to update the command line state. Everything in the Implicit module maps down to the Explicit module. In addition, you can use the GetOpt compatibility layer, which also maps down to the Explicit parser.

Having written command line parsers with annotated records, I'd never go back to writing them out in full. However, if you want to map your own command line parser description down to the Explicit version you can get help messages and parsing for free.

3: I fight the optimiser so you don't have to

Even if you choose to use the impure implicit version of CmdArgs, you don't need to do anything, even at high optimisation levels. I have an extensive test suite, and will continue to ensure CmdArgs programs work properly - I rely on it for several of my programs. While I find the implicit impure nicer to work with, I am still working on making a pure version with the same syntax, developing alternative methods of describing the annotations, developing quasi-quoters etc.

CmdArgs - Fighting the GHC Optimiser

2011-05-07T22:37:00.004+01:00

Summary: Everyone using GHC 7 should upgrade to CmdArgs 0.7. GHC's optimiser got better, so CmdArgs optimiser avoidance code had to get better too.

Update: Has this post scared you off CmdArgs? Read why CmdArgs is not dangerous.

CmdArgs is a Haskell library for concisely specifying the command line arguments, see this post for an introduction. I have just released versions 0.6.10 and 0.7 of CmdArgs, which are a strongly recommended upgrade, particular for GHC 7 users. (The 0.6.10 is so anyone who specified 0.6.* in their Cabal file gets an automatic upgrade, and 0.7 is so people can write 0.7.* to require the new version.)

Why CmdArgs is impure

CmdArgs works by annotating fields to determine what command line argument parsing you want. Consider the data type:


data Opts = Opts {file :: FilePath}

By default this will create a command line which would respond to myprogram --file=foo. If instead we want to use myprogram foo we need to attach the annotation args to the file field. We can do this in CmdArgs with:


cmdArgs $ Opts {file = "" &= args}

However, CmdArgs does not have to be impure - you can equally use the pure variant of CmdArgs and write:


cmdArgs_ $ record Opts{} [file := "" += args]

Sadly, this code is a little more ugly. I prefer the impure version, but everything is supported in both versions.

I am still experimenting with other ways of writing an annotated record, weighing the trade-offs between purity, safety and the syntax required. I have been experimenting with pure variants tonight, and hope in a future release to make CmdArgs pure by default.

GHC vs CmdArgs

Because CmdArgs uses unsafe and untracked side effects, GHC's optimiser can manipulate the program in ways that change the semantics. A standard example where GHC's optimiser can harm CmdArgs is:


Opts2 {file1 = "" &= typFile, file2 = "" &= typFile}

Here the subexpression "" &= typFile is duplicated, and if GHC spots this duplication, it can use common sub-expression eliminate to transform the program to:


let x = "" &= typFile in Opts2 {file1 = x, file2 = x}

Unfortunately, because CmdArgs is impure, this program attaches the annotation to file1, but not file2.

This optimisation problem happens in practice, and can be eliminated by writing {-# OPTIONS_GHC -fno-cse #-} in the source file defining the annotations. However, it is burdensome to require all users of CmdArgs to add pragmas to their code, so I investigated how to reduce the problem.

Beating GHC 6.10.4

The key function used to beat GHC's optimiser is &=. It is defined as:


(&=) :: (Data val, Data ann) => val -> ann -> val
(&=) x y = addAnn x y

In order to stop CSE, I use two tricks. Firstly, I mark &= as INLINE, so that it's definition ends up in the annotations - allowing me to try and modify the expression so it doesn't become suitable for CSE. For GHC 6.10.4 I then made up increasingly random expressions, with increasingly random pragmas, until the problem went away. The end solution was:


{-# INLINE (&=) #-}
(&=) :: (Data val, Data ann) => val -> ann -> val
(&=) x y = addAnn (id_ x) (id_ y)

{-# NOINLINE const_ #-}
const_ :: a -> b -> b
const_ f x = x

{-# INLINE id_ #-}
id_ :: a -> a
id_ x = const_ (\() -> ()) x

Beating GHC 7.0.1

Unfortunately, after upgrading to GHC 7.0.1, the problem happened again. I asked for help, and then started researching GHC's CSE optimiser (using the Hoogle support for GHC I added last weekend - a happy coincidence). The information I found is summarised here. Using this information I was able to construct a much more targeted solution (which I can actually understand!):


{-# INLINE (&=) #-}
(&=) x y = addAnn x (unique x)

{-# INLINE unique #-}
unique x = case unit of () -> x
    where unit = reverse "" `seq` ()

As before, we INLINE the &=, so it gets into the annotations. Now we want to make all annotations appear different, even though they are the same. We use unique which is equivalent to id, but when wrapped around an expression causes all instances to appear different under CSE. The unit binding has the value (), but in a way that GHC can't reduce, so the case does not get eliminated. GHC does not CSE case expressions, so all annotations are safe.

How GHC will probably defeat CmdArgs next

There are three avenues GHC could explore to defeat CmdArgs:

Reorder the optimisation phases. Performing CSE before inlining would defeat everything, as any tricks in &= would be ignored.

Better CSE. Looking inside case would defeat my scheme.

Reduce unit to (). This reduction could be done in a number of ways:
- Constructor specialisation of reverse should manage to reduce reverse to "", which then seq can evaluate, and then eliminate the case. I'm a little surprised this isn't already happening, but I'm sure it will one day.
- Supercompilation can inline recursive functions, and inlining reverse would eliminate the case.
- If GHC could determine reverse "" was total it could eliminate the seq without knowing it's value. This is somewhat tricky for reverse as it isn't total for infinite lists.

Of these optimisations, I consider the reduction of unit to be most likely, but also the easiest to counteract.

How CmdArgs will win

The only safe way for CmdArgs to win is to rewrite the library to be pure. I am working on various annotation schemes and hope to have something available shortly.

Searching GHC with Hoogle

2011-05-01T17:56:00.004+01:00

Summary: Hoogle can now search the GHC source code. There are also lots of small improvements in the latest version.

A few weeks ago Ranjit Jhala asked me for help getting Hoogle working on the GHC documentation. As a result of this conversation, I've now released Hoogle 4.2.3, and upgraded the Hoogle web tool.

For GHC developers

You can search the GHC documentation using the standard Hoogle website, for example: llvm +ghc

To search within a package simply write +package in your search query. The ghc package on Hoogle includes all the internals for GHC.

If you want to search using the console, you can install Hoogle and generate the GHC package database with:


cabal update
cabal install hoogle
hoogle data default ghc

You can now perform searches with:


hoogle +ghc llvm

For all Hoogle users

The new release of Hoogle contains a number of small enhancements:

The web server has been upgraded to Warp. I'll write a blog post shortly on the move to Warp - but generally it's been a very positive step.

Some of the snippets of documentation have been fixed, where the markup was interpreted wrongly.

There is only an expand button next to the documentation if there is more information to expand.

Some iPad integration, so you can now add it to your home page with a nice icon.

Work on a deployment script to automate uploading a new version to the web server, which will allow for more frequent updates (until now it took over 2 hours to deploy a new version).

Updates as some web resources moved around, particularly the Haskell Platform cabal file.

The theory behind Hoogle

I'll be talking about the theory behind type searching in Hoogle at Trends in Functional Programming 2011 in Madrid in a few weeks time. It's not too late to register.

Darcs for my Wife

2011-04-29T11:31:00.002+01:00

Summary: Using the version control system Darcs is simple. This document describes the commands I use in my workflow.

Darcs is my favourite version control system because of its simple user interface. I am able to do everything I need with a handful of simple commands. I work with darcs as a single user, without branches, occasionally accepting small external contributions. This guide is designed to provide a sufficient reference for a someone who isn't a computer expert to continue using Darcs after their friendly comp-sci has set up the SSH bits for them (e.g. my wife).

A Darcs repository (or repo) is a set of changes (sometimes referred to as patches). There are three places changes may live:

Remote Repo, such as on community.haskell.org.

Local Repo, on your computer. You may have many local repos all using the same remote repo, especially if you use multiple computers.

Local Changes, modifications you have made to your local repo, by editing files.

The way changes move between locations is described by:

Basic Commands

I use four commands daily, shown in red on the above diagram, which are:

darcs pull - copy changes from the remote repo to your local repo. Use pull at the beginning of the day, and during the day if you are sharing a remote repo with other people.

darcs whatsnew - see what local changes you have made. A useful flag is --summary, which lists only the names of files which have changed.

darcs record - after you have decided to keep your changes, use record to store them in your local repo.

darcs push --no-set-default ndm@code.haskell.org:/srv/code/hoogle - at the end of the day use push to move your changes to the remote repo. This command is the most tricky to use, you need SSH access to the server and need to use the file path of the repo, not the URL exposed by the website. I recommend writing a .bat file to automate this command, or using the neil push command if appropriate.

In addition to the four commands above, there are two additional basic commands that are used more rarely:

darcs add filename - tell darcs that you have created a new file that should be kept in the repo. If you forget to add a file, darcs will not store it for you.

darcs mv oldname newname - rename a file stored in darcs. Use this command instead of directly renaming the file using a file explorer.

Creating Repos

Usually I work with existing repos, but it's useful to know how to create new repos:

darcs init - create an empty remote repo, with no changes in it. This command is usually run on the server.

darcs get http://code.haskell.org/hoogle - create a new local repo based on a remote repo.

Advanced Commands

These commands are useful to correct mistakes, but they aren't essential - you can do everything you need without them.

darcs revert - undo local changes that have not yet been recorded.

darcs unrecord - undo a previous record command. Do not unrecord if you have pushed the changes, or have done substantial work since the initial record. Instead, manually create a new change undoing the previous record, and record that.

Collaboration Commands

If you are accepting occasional contributions from other people, you will need the following commands:

darcs send -o filename.patch - make a file containing all the changes in your local repo, but not in the remote repo. This file can be emailed to other people.

darcs apply filename.patch - apply a set of changes sent to you by email.

Conclusion

Effective use of darcs requires only a few simple commands, with only a few command line switches. This guide includes all the commands I ever use. Darcs rarely surprises me, and I think it is a suitable version control system for people who are familiar with the command line, but aren't computer experts.

Experience Report: Functional Programming through Deep Time

2011-03-20T23:08:00.002Z

My wife has just completed a draft of the experience report she's intending to submit to ICFP 2011. It's called Functional Programming through Deep Time:

This experience report describes how Haskell was used to model the beginnings of complex life on Earth. My work combines ecological modeling in Haskell with statistical analysis in R, to answer some long standing paleontological questions. For my work, I found that neither Haskell nor R was suffcient - statistical analysis in Haskell is overly burdensome, while R lacks the structure to express complex algorithms in a maintainable manner. The reaction from my colleagues has ranged from indifferent to excited - but I have yet to tempt any of them over to the pure side!

I initially persuaded my wife to switch to Haskell, but since then, I have had little involvement with her code. If you have any feedback for her (ideally before Wednesday!) please leave it in the comments.

Hoogle for your language (i.e. F#, Scala, ML, Clean...)

2011-03-13T14:05:00.003Z

Summary: If you offer to help, I'll make Hoogle search your statically typed functional language.

Hoogle is a search engine for Haskell functions, that allows you to search by either name, or by type. But very little of Hoogle is actually Haskell specific - most is applicable to any language with a Hindley-Milner based type system.

Recently I have been asked by several people what they can do to allow Hoogle to search their preferred language. There are four steps to integrating a language with Hoogle, detailed below. If you are interested in helping please email me - I already have volunteers for both F# and Scala, but additional volunteers for other languages are welcome.

To allow searching a language from Hoogle, there are four steps:

1) A volunteer needs to generate some Hoogle input files containing details of the modules/functions/packages etc. to be searched. These files should be plain text, but can be in a language specific format - i.e. ML syntax for type signatures. For a rough idea of how these files could look see this example - for Haskell I get these files from Hackage. The code to generate these input files can be written in any language, and can live outside Hoogle.

2) Someone needs to write a parser that converts these language specific inputs into internal Hoogle representations. The equivalent code for Haskell is in the Hoogle repo. If a volunteer writes this code, I'll happily use it. If I have to write this code then that's OK, although I might take a bit longer. This code needs to be written in Haskell and live inside Hoogle.

At this stage, Hoogle will be able to search the new language. The remaining stages will just make the experience more pleasant.

3) Someone needs to write a query parser for the language, inside Hoogle. I may do this, as I'm intending to rewrite the Haskell query parser anyway, and I could probably find some savings by doing them together. This code needs to be written in Haskell and live inside Hoogle.

4) A volunteer would be useful to keep the function definitions up to date, generate new definitions, and ensure they get uploaded.

Email me if you want to volunteer!

Corner Cases And Zero (and how WinForms gets it wrong)

2011-02-13T18:31:00.003Z

Summary: Zero is a perfectly good number and functions should deal with it sensibly. In WinForms, both the Bitmap object and the DrawToBitmap function fail on zero, which is wrong. Functional programming (and recursion) make it harder to get the corner cases wrong.

Lots of programming is about reusing existing functions/objects. Many types have natural corner cases, e.g. an empty string, the number zero, and an array with zero elements. If the functions you reuse don't deal sensibly with corner cases your functions are likely to contain bugs, or be more verbose in working around other peoples bugs.

C#/WinForms has bugs with zero

Let's write a function in C#/WinForms which given a Control (something that can be displayed) produces a Bitmap of how it will be drawn:


public Bitmap Draw(Control c)
{
    Bitmap bmp = new Bitmap(c.Width, c.Height);
    c.DrawToBitmap(bmp, new Rectangle(0, 0, c.Width, c.Height));
    return bmp;
}

Our function Draw makes use of the existing WinForms function DrawToBitmap:


void Control.DrawToBitmap(Bitmap bitmap, Rectangle bounds)

The function DrawToBitmap draws the control into bitmap at the position specified by bounds. This function is useful, but impure (it mutates the bitmap argument), and somewhat fiddly (bounds have to satisfy various invariants with respect to the bitmap and the control). Our Draw function only handles the common case where you want the entire bitmap, but is pure and simpler. (Our Draw function can be renamed DrawToBitmap and added as an extension method of Control, making it quite convenient to use.)

Unfortunately our Draw function has a bug, due to the incorrect handling of zero in the functions we rely on. Let's consider a control with width 0, and height 10. First we crash with the exception "Parameter is not valid." when executing:


new Bitmap(0, 10);

Unfortunately the .NET Bitmap type doesn't allow bitmaps which don't contain any pixels. This limitation probably comes from the CreateBitmap Win32 API function, which doesn't allow empty bitmaps. The result is that our function cannot return a 0x10 bitmap, meaning that lots of nice properties (e.g. the resulting bitmap will be the same size as the control) are necessarily violated. We can patch around the limitations of Bitmap by writing:


Bitmap bmp = new Bitmap(Math.Max(1, c.Width), Math.Max(1, c.Height));

This change is horrid, but it's the best we can do within the limitations of the .NET Bitmap type. We run again and now get the exception "targetbounds" when executing:


c.DrawToBitmap(bmp, new Rectangle(0, 0, 0, 10));

Unfortunately DrawToBitmap throws an exception when either the width or height of the bounds is zero. We have to add another workaround to avoid calling DrawToBitmap in these cases (or at this stage perhaps just add an if at the top which returns early if either dimension is 0). The Bitmap limitation is annoying but somewhat understandable - it is driven by legacy code. However, DrawToBitmap could easily have been modified to accept 0 width or height and simply avoid doing anything, which would be the only sensible behaviour at this corner case.

The problem with bugs in corner cases is that they propagate. Bitmap has a limitation, so everything which uses Bitmap inherits this limitation. The DrawToControl function has a bug, so everything built on top of it has a bug (or needs to include a workaround). The documentation for Bitmap and DrawToControl doesn't mention that they fail at corner cases, which is unfortunate.

Induction for Corner Cases

One of the advantages of functional programming is that defining functions recursively forces you to consider corner cases. Consider the Haskell function replicate, which takes a number and a value, and repeats the value that number of times. To define the function it is natural to use recursion over the number. This scheme leads to the definition:


replicate 0 x = []
replicate n x = x : replicate (n-1) x

The function replicate 0 'x' returns []. To get the corner case wrong would have required additional effort. As a result, most Haskell functions work the way you would expect in corner cases - and consequently functions built from them also work sensibly in corner cases. When programming in Haskell my code is less likely to fail in corner cases, and more likely to work first time.

Exercise

As a final thought exercise, consider the following function:


orAnd :: [[Bool]] -> Bool

Where orAnd [[a,b],[c,d]] returns True if either both a and b are True, or if both c and d are True. What should [] return? What should [[]] return? If you write this function recursively (or on top of other recursive functions such as or/and) there will be a natural answer. Writing the function imperatively makes it hard to ensure the corner cases are correct.

Hoogle Embed

2011-01-23T09:35:00.010Z

Summary: Hoogle Embed lets you include a small interactive Hoogle search box on your web page.

I have just released Hoogle 4.2, which adds the feature Hoogle Embed, letting you embed a small Hoogle powered search box on any web page. For an example, visit the Hoogle page on my website, and try typing "database" in the search box on the right. You should see:

As you type, the search box will perform Hoogle searches on the Hoogle API, and display the results. Selecting a result will visit the associated documentation. Pressing the Search button will perform the search at the Hoogle website.

Hoogle Embed has been tested in Chrome, Firefox and IE. ~~Using IE~~ Using IE 7 or below you may not see results unless the page being displayed is on the same server as the Hoogle instance (i.e. haskell.org), due to restrictions on cross domain AJAX requests. This limitation can probably be overcome with additional work, if people are interested.

Hoogle Embed degrades gracefully if the browser does not support Javascript, leaving just the search box.

Configuration options allow you to automatically add a prefix or suffix to the users search, for example adding +hoogle to search only the Hoogle API.

This feature works with either a custom Hoogle instance, or the standard version on haskell.org.

Using Hoogle Embed in your web page

To include Hoogle Embed on a web page, simply add the following piece of HTML:


<script type="text/javascript" src="http://haskell.org/hoogle/datadir/resources/jquery-1.4.2.js"></script>
<script type="text/javascript" src="http://haskell.org/hoogle/datadir/resources/hoogle.js"></script>
<form action="http://haskell.org/hoogle/" method="get">
  <input type="text"   name="hoogle" id="hoogle" accesskey="1" />
  <input type="hidden" name="prefix" value="+base" />
  <input type="submit" value="Search" />
</form>

To use a different Hoogle server change the action field of the form. To specify a prefix/suffix for all searches add an input field with the name prefix/suffix. For example, the above snippet only searches the base pacakge. By eliminating the prefix line it will search using the default Hoogle settings (the Haskell platform).

The Hoogle Embed feature is usable on any web page, but I think would be particularly effective on pages such as the Hackage page for a package, or for any Haddock documentation (perhaps when using a flag such as --hoogle-embed). I encourage anyone who is interested to submit patches to the relevant projects.

Hoogle Manual

I am currently considering the issue of documentation, and would welcome other peoples thoughts. Currently the Hoogle manual is hosted on the Haskell Wiki, but is somewhat out of date. For all other packages, I tend to write an HTML manual stored in the darcs repo, such as for hlint. There are advantages to both formats - the wiki can be easily edited by many people, but the darcs manual can be updated simultaneously with the code and is available offline (most Hoogle work is done on a train without internet access, so this issue is very relevant). My current thought is to remove the wiki page and move it's contents into darcs.

Edit: Fixed the Javascript links.

Edit 2: Hoogle Embed now works cross domain in IE 8 and above.

Hoogle At 1.7 Million Searches

2011-01-16T19:19:00.004Z

Summary: I detail some of the changes in today's Hoogle release; I outline future plans for Hoogle; I plot some statistics, noting that Hoogle has been used for 1.7 million searches.

New Features

Hoogle is a Haskell API search engine, which I've been working on since 2004. Today I updated the web version at http://haskell.org/hoogle, and uploaded a new version to Hackage. Since my last release I've been working on several new features:

Instant Search - in the top right corner you will see a link entitled "Instant is off". Click that link to turn instant search on, and then searches will be performed as you type. This feature is still experimental, but I already rely on it for my searches.

Visual Refresh - I've modified the style and layout, trying to improve the general feel, especially when used in conjunction with instant search. I added links to make the package filtering options more accessible and I collapse identical results available from different modules.

Database Update - thanks to Ian Lynagh and Ross Paterson I've been able to update all the Hoogle databases, including for the base package. In the future I hope to keep Hoogle continuously updated.

Future Plans

There are three big improvements I plan to make to Hoogle:

Better Data - Hoogle relies on data from Haddock, uploaded to Hackage, by Cabal. This release improves the data, but there are still further improvements to be made. There are several bugs in Haddock, and data for the base library is not yet available on Hackage. If Hoogle could integrate more closely with Cabal then Hoogle could search users local packages. Many of these problems require coordination between several projects, and any offers of help would be welcome. Some bugs: #80, #11, #339, #60, #183.

Better Search Syntax - the search syntax in Hoogle is acceptable, but isn't that close to other search engines, doesn't always mesh well with instant search and has a number of bugs. I intend to overhaul the search syntax, hopefully improving the feel of Hoogle. Some bugs: #34, #61, #398, #130.

Improved Database/Searching - type search needs to execute faster and give better results. By executing faster Hoogle will be able to search the whole of Hackage at once. Hoogle has gone through four entirely different iterations of type search already, and I have a design for the fifth version. Some bugs: #79, #324, #30, #336, #381.

Statistics

Hoogle logs the date and contents of each search, but stores no personally identifiable information. These statistics all relate to the number of searches made, not including blank searches or suggestions offered by the Firefox search plugin. In the time between adding a logging facility, and making it log the date (2009-Apr-24), there were 631930 searches. Since then there have been at least 1012414 searches, not taking into account about a month where logging was disabled. Generally, searches range between 1000 and 2500 a day.

New Version of Hoogle (4.1)

2010-12-19T16:01:00.003Z

I've just released a new version of Hoogle to both Hackage and to haskell.org/hoogle. Hoogle is a Haskell search engine that allows you to search for functions by either name or approximate type signature.

What's New

The first release in over a year, building with up to date packages and compilers.

Up to date library definitions for all of Hackage.

Searches the Haskell Platform by default.

Significant improvements when installing Hoogle locally.

Lots of additional small improvements.

Searching all of Hackage

Hoogle can now search all of Hackage. By default it will search the Haskell Platform, but you can search additional packages using +package-name, for example +tagsoup Tag a -> Bool. You can search both the platform and additional packages by including +default, for example ([a] -> (b, [a])) -> [a] -> [b] +split +default.

I'm still not sure what should be searched by default, and which collections of modules should be available, but I'm open to suggestions.

Installing Hoogle Locally

Many of the improvements to Hoogle are of specific benefit when installing Hoogle yourself, not using the web version. To install Hoogle:


cabal update
cabal install hoogle
hoogle data

The last step will download information and generate databases for the Haskell Platform. You can then run searches, such as hoogle filter -n10. Hoogle now uses cmdargs, so hoogle --help will detail some of the options available.

You can also run Hoogle as a web server by typing hoogle server. Now visit localhost in a web browser and you'll have the power of Hoogle on your computer. If you often work offline, you can run hoogle data --local and hoogle server --local to use documentation on your local machine where available.

What Now?

Hoogle is currently the spare time project I'm focusing on - there are lots of improvements I am intending to make. Hoogle 4.1 is about getting the code up to a standard that can be easily maintained, allowing future versions to deliver more features. Please try out Hoogle, report any bugs you find, and let me know your thoughts.

Installing the Haskell network library on Windows

2010-12-12T10:31:00.007Z

Summary: This post describes how to install the Haskell network library on Windows.

The network library used to be bundled with GHC. Unfortunately it was unbundled from the standard installer (in my opinion, a mistake), and people were required to either install it using Cabal (rather tricky) or switch to using the Haskell Platform (which is not suitable for power developers who want to test with newer/older GHC versions, or those who want to upgrade/downgrade network). This post describes how to install the library on Windows using Cabal.

First, install Cygwin. I selected lots of options (configure tools, auto conf, compilers) - but I'm not sure which are necessary.

Then start a Cygwin window and run:

WHICHGHC=`which ghc` && PATH=`dirname $WHICHGHC`/../mingw/bin:$PATH && cabal install network --configure-option --host=i386-unknown-mingw32 --global --enable-library-profiling

This configures network to use mingw32, and sets up the PATH so that mingw binaries from GHC are first, and get configured in. You can then use the network library as normal, without ever using Cygwin again. I have successfully executed this command on GHC 6.12.3 and 7.0.1.

Dependencies on foreign libraries are a problem for any cross platform language. Several years ago, installing Haskell libraries was a painful process - but Hackage and Cabal have made it impressively easy. The only remaining packages that are complex to install are those that bind to foreign libraries, most of which use configure scripts, which are not well suited to Windows. I hope over time even libraries with foreign dependencies will become easy to install.

Update: Ivan Perez suggests the alternative form:


WHICHGHC=`which ghc` && PATH=`dirname $WHICHGHC`/../mingw/bin:$PATH && cabal install network --configure-option --build=i386-unknown-mingw32 --configure-option --host=i686-pc-cygwin --global --enable-library-profiling

Enhanced Cabal SDist

2010-10-14T19:57:00.002+01:00

Summary: I wrote a little script on top of cabal sdist that checks for common mistakes.

Cabal is the standard way to distribute Haskell packages, and has significantly simplified the process of installing libraries. However, I often make mistakes when creating cabal distributions using sdist. One common problem is that if you don't include a file in your .cabal file it will not be put in the distribution package and the package will fail to build for other people, but if the file is available locally it will still work for you. To work around this problem, I often perform a cabal install immediately after I upload a cabal package. Last week I discovered a package that I'd requested to be uploaded had suffered the same fate (hws – from the fantastic Haskell Workshop paper on writing a scalable web server in Haskell), showing this mistake isn't specific to me.

Eric Kow often says that programmers spend too little time writing tools to help their workflow. In response to this observation I have created the "neil" tool, available in darcs from http://community.haskell.org/~ndm/darcs/neil - darcs get and then cabal install. One feature of this neil tool is neil sdist. The actions neil sdist performs are:

cabal check

cabal configure to a temporary directory

cabal sdist to a temporary directory

change to that temporary directory

cabal configure –Werror –fwarn-unused-imports

cabal build

cabal haddock –executables

The intention is that this sequence of actions will fail if anything bad would happen on a users machine. If the file fails to build then cabal build will fail. If the haddock fails to generate than cabal haddock will fail. If there would be warnings during build then –Werror will cause it to fail. If all these checks pass then the package is likely to install without problems (once the cabal test feature is present then that can be included, which will give even more assurance).

I have deliberately not uploaded the neil tool to Hackage, and have no intention of doing so. The name "neil" is not suitable for Hackage, and I intend to add specific actions to help my workflow. If anyone wants to take any of the actions included in this tool and break them out in to separate tools, roll them back into cabal itself etc, they are very welcome.

Taking Eric's advice, I have found that by automating aspects of my workflow I can take steps which were error prone, or verbose, and make them concise and accurate. With neil sdist I have eliminated an entire class of potential errors, with very little ongoing work.

Three Closed GHC Bugs I Wish Were Open

2010-09-18T21:56:00.002+01:00

Summary: I want three changes to the Haskell standard libraries. System.Info.isWindows should be added, Control.Monad.concatMapM should be added, and Control.Concurrent.QSem should work with negative quantities.

Over the last few hours I've been going through my inbox, trying to deal with some of my older emails. In that process, I've had to admit defeat on three GHC bugs that I'd left in my inbox to come back to. All these bugs relate to changes to the Haskell standard libraries, that were opened as bugs, and that got resolved as closed/wontfix. I will never get time to tackle these bugs, but perhaps someone will? The bugs are:

Add System.Info.isWindows - bug 1590


module System.Info where

-- | Check if the operating system is a Windows derivative. Returns True on
--   all Windows systems (Win95, Win98 ... Vista, Win7), and False on all others
isWindows :: Bool
isWindows = os == "mingw"

Currently the recognised way to test at runtime if your application is being run on Windows is:


import System.Info

.... = os == "mingw"

This is wrong for many reasons:

The return result of os is not an operating system, but a ported toolchain.

The result "mingw" does not imply that MinGW is installed on the computer.

String comparisons are unsafe and unchecked, a simple typo breaks this code.

In GHC this comparison will take place at runtime, even though the result is a constant.

The Haskell abstractions and command line tools for almost all non-Windows operating systems have converged to the point where most programs with operating system specific behaviour have two cases - one for Windows and one for everything else. It makes sense to directly support what is probably the most common usage of the os function, and to encourage people away from the C preprocessor where possible.

Add Control.Monad.concatMapM - bug 2042


module Control.Monad where

-- | The 'concatMapM' function generalizes 'concatMap' to arbitrary monads.
concatMapM        :: (Monad m) => (a -> m [b]) -> [a] -> m [b]
concatMapM f xs   =  liftM concat (mapM f xs)

I've personally defined this function in binarydefer, catch, derive, hlint, hoogle, my website generator and yhc. There's even a copy in GHC. If a function has been defined identically that many times, it clear deserves to be in the standard library. We have mapM, filterM, zipWithM, but concatMapM is suspiciously absent.

Make Control.Concurrent.QSem work with negatives - bug 3159

The QSem module defines a quantity semaphore, where the quantity semaphores must be natural numbers. Attempts to construct semaphores with negative numbers raise an error. There is, however, a perfectly sensible and obvious interpretation if negative numbers are allowed. It is a shame that this module could provide total functions, which never raise an error, but does not. In addition, for some problems the use of negative quantity semaphores is more natural.

What Now?

I've removed all these bugs from my inbox, and invite someone else to take up the cause - I just don't have the time. Until these issues are resolved, I will test for Windows in a horrible way, define concatMapM whenever I start a new project, and lament the lack of generality in QSem. None of the issues is particularly serious, but all are slightly annoying.

Email etiquette: Today I've cleared about 50 emails from my inbox. Unfortunately my inbox remains big and unwieldy. If you ever email me, and I don't get back to you, email me again a week later. As long as you reply to the first message, Gmail will collapse the reply in to the original conversation, and there won't be any additional load on my inbox - it will just remind me that I should have dealt with your email. I apologise for any emails that have fallen through the cracks.

CmdArgs Example

2010-08-23T19:47:00.005+01:00

Summary: A simple CmdArgs parser is incredibly simple (just a data type). A more advanced CmdArgs parser is still pretty simple (a few annotations). People shouldn't be using getArgs even for quick one-off programs.

A few days ago I went to the Haskell Hoodlums meeting - an event in London aimed towards people learning Haskell. The event was good fun, and very well organised - professional quality Haskell tutition for free by friendly people - the Haskell community really is one of Haskell's strengths! The final exercise was to write a program that picks a random number between 1 and 100, then has the user take guesses, with higher/lower hints. After writing the program, Ganesh suggested adding command line flags to control the minimum/maximum numbers. It's not too hard to do this directly with getArgs:


import System.Environment

main = do
    [min,max] <- getArgs
    print (read min, read max)

Next we discussed adding an optional limit on the number of guesses the user is allowed. It's certainly possible to extend the getArgs variant to take in a limit, but things are starting to get a bit ugly. If the user enters the wrong number of arguments they get a pattern match error. There is no help message to inform the user which flags the program takes. While getArgs is simple to start with, it doesn't have much flexibility, and handles errors very poorly. However, for years I used getArgs for all one-off programs - I found the other command line parsing libraries (including GetOpt) added too much overhead, and always required referring back to the documentation. To solve this problem I wrote CmdArgs.

A Simple CmdArgs Parser

To start using CmdArgs we first define a record to capture the information we want from the command line:


data Guess = Guess {min :: Int, max :: Int, limit :: Maybe Int} deriving (Data,Typeable,Show)

For our number guessing program we need a minimum, a maximum, and an optional limit. The deriving clause is required to operate with the CmdArgs library, and provides some basic reflection capabilities for this data type. Once we've written this data type, a CmdArgs parser is only one function call away:


{-# LANGUAGE DeriveDataTypeable #-}
import System.Console.CmdArgs

data Guess = Guess {min :: Int, max :: Int, limit :: Maybe Int} deriving (Data,Typeable,Show)

main = do
    x <- cmdArgs $ Guess 1 100 Nothing
    print x

Now we have a simple command line parser. Some sample interactions are:


$ guess --min=10
NumberGuess {min = 10, max = 100, limit = Nothing}

$ guess --min=10 --max=1000
NumberGuess {min = 10, max = 1000, limit = Nothing}

$ guess --limit=5
NumberGuess {min = 1, max = 100, limit = Just 5}

$ guess --help
The guess program

guess [OPTIONS]

  -? --help       Display help message
  -V --version    Print version information
     --min=INT
     --max=INT
  -l --limit=INT

Adding Features to CmdArgs

Our simple CmdArgs parser is probably sufficient for this task. I doubt anyone will be persuaded to use my guessing program without a fancy iPhone interface. However, CmdArgs provides all the power necessary to customise the parser, by adding annotations to the input value. First, we can modify the parser to make it easier to add our annotations:


guess = cmdArgsMode $ Guess {min = 1, max = 100, limit = Nothing}

main = do
    x <- cmdArgsRun guess
    print x

We have changed Guess to use record syntax for constructing the values, which helps document what we are doing. We've also switched to using cmdArgsMode/cmdArgsRun (cmdArgs which is just a composition of those two functions) - this helps avoid any problems with capturing the annotations when running repeatedly in GHCi. Now we can add annotations to the guess value:


guess = cmdArgsMode $ Guess
    {min = 1   &= argPos 0 &= typ "MIN"
    ,max = 100 &= argPos 1 &= typ "MAX"
    ,limit = Nothing &= name "n" &= help "Limit the number of choices"}
    &= summary "Neil's awesome guessing program"

Here we've specified that min/max must be at argument position 0/1, which more closely matches the original getArgs parser - this means the user is always forced to enter a min/max (they could be made optional with the opt annotation). For the limit we've added a name annotation to say that we'd like the flag -n to map to limit, instead of using the default -l. We've also given limit some help text, which will be displayed with --help. Finally, we've given a different summary line to the program.

We can now interact with our new parser:


$ guess
Requires at least 2 arguments, got 0

$ guess 1 100
Guess {min = 1, max = 100, limit = Nothing}

$ guess 1 100 -n4
Guess {min = 1, max = 100, limit = Just 4}

$ guess -?
Neil's awesome guessing program

guess [OPTIONS] MIN MAX

  -? --help       Display help message
  -V --version    Print version information
  -n --limit=INT  Limit the number of choices

The Complete Program

For completeness sake, here is the complete program. I think for this program the most suitable CmdArgs parser is the simpler one initially written, which I have used here:


{-# LANGUAGE DeriveDataTypeable, RecordWildCards #-}

import System.Random
import System.Console.CmdArgs

data Guess = Guess {min :: Int, max :: Int, limit :: Maybe Int} deriving (Data,Typeable)

main = do
    Guess{..} <- cmdArgs $ Guess 1 100 Nothing
    answer <- randomRIO (min,max)
    game limit answer

game (Just 0) answer = putStrLn "Limit exceeded"
game limit answer = do
    putStr "Have a guess: "
    guess <- fmap read getLine
    if guess == answer then
        putStrLn "Awesome!!!1"
     else do
        putStrLn $ if guess > answer then "Too high" else "Too low"
        game (fmap (subtract 1) limit) answer

(The code in this post can be freely reused for any purpose, unless you are porting it to the iPhone, in which case I want 10% of all revenues.)

CmdArgs 0.2 - command line argument processing

2010-08-16T20:12:00.002+01:00

I've just released CmdArgs 0.2 to Hackage. CmdArgs is a library for defining and parsing command lines. The focus of CmdArgs is allowing the concise definition of fully-featured command line argument processors, in a mainly declarative manner (i.e. little coding needed). CmdArgs also supports multiple mode programs, as seen in darcs and Cabal. For some examples of CmdArgs, please see the manual or the Haddock documentation.

For the last month I've been working on a complete rewrite of CmdArgs. The original version of CmdArgs did what I was hoping it would - it was concise and easy to use. However, CmdArgs 0.1 had lots of rough edges - some features didn't work together, there were lots of restrictions on which types of fields appear where, and it was hard to add new features. CmdArgs 0.2 is a ground up rewrite which is designed to make it easy to maintain and improve in the future.

The CmdArgs 0.2 API is incompatible with CmdArgs 0.1, for which I apologise. Some of the changes you will notice:

Several of the annotations have changed name (text has become help, empty has become opt).

Instead of writing annotations value &= a1 & a2, you write value &= a1 &= a2.

Instead of cmdArgs "Summary" [mode1], you write cmdArgs (mode1 &= summary "Summary"). If you need a multi mode program use the modes function.

All the basic principles have remained the same, all the old features have been retained, and translating parsers should be simple local tweaks. If you need any help please contact me.

Explicit Command Line Processor

The biggest change is the introduction of an explicit command line framework in System.Console.CmdArgs.Explicit. CmdArgs 0.1 is an implicit command line parser - you define a value with annotations from which a command line parser is inferred. Unfortunately there was not complete separation between determining what parser the user was hoping to define, and then executing it. The result was that even at the flag processing stage there were still complex decisions being made based on type. CmdArgs 0.2 has a fully featured explicit parser that can be used separately, which can process command line flags and display help messages. Now the implicit parser first translates to the explicit parser (capturing the users intentions), then executes it. The advantages of having an explicit parser are substantial.

It is possible to translate the implicit parser to an explicit parser (cmdArgsMode), which makes testing substantially easier. As a result CmdArgs 0.2 has far more tests.

I was able to write the CmdArgs command line itself in CmdArgs. This command line is a multiple mode explicit parser, which has many sub modes defined by implicit parsers.

The use of explicit parsers also alleviates one of the biggest worries of users, the impurity. Only the implicit parser relies on impure functions to extract annotations. In particular, you can create the explicit parser once, then rerun it multiple times, without worrying that GHC will optimise away the annotations.

Once you have an explicit parser, you can modify it afterwards - for example programmatically adding some flags.

The explicit parser better separates the internals of the program, making each stage simpler.

The introduction of the explicit parser was a great idea, and has dramatically improved CmdArgs. However, there are still some loose ends. The translation from implicit to explicit is a multi-stage translation, where each stage infers some additional information. While this process works, it is not very direct - the semantics of an annotation are hard to determine, and there are ordering constrains on these stages. It would be much better if I could concisely and directly express the semantics of the annotations, which is something I will be thinking about for CmdArgs 0.3.

GetOpt Compatibility

While the intention is that CmdArgs users write implicit parsers, it is not required. It is perfectly possible to write explicit parsers directly, and benefit from the argument processing and help text generation. Alternatively, it is possible to define your own command line framework, which is then translated in to an explicit parser. CmdArgs 0.2 now includes a GetOpt translator, which presents an API compatible with GetOpt, but operates by translating to an explicit parser. I hope that other people writing command line frameworks will consider reusing the explicit parser.

Capturing Annotations

As part of the enhanced separation of CmdArgs, I have extracted all the code that captures annotations, and made it more robust. The essential operation is now &= which takes a value and attaches an annotation. (x &= a) &= b can then be used to attach the two annotations a and b (the brackets are optional). Previously the capturing of annotations and processing of flags was interspersed, meaning the entire library was impure - now all impure operations are performed inside capture. The capturing framework is not fully generic (that would require module functors, to parameterise over the type of annotation), but otherwise is entirely separate.

Consistentency

One of the biggest changes for users should be the increase in consistency. In CmdArgs 0.1 certain annotations were bound to certain types - the args annotation had to be on a [String] field, the argPos annotation had to be on String. In the new version any field can be a list or a maybe, of any atomic type - including Bool, Int/Integer, Double/Float and tuples of atomic types. With this support it's trivial to write:


data Sample = Sample {size :: Maybe (Int,Int)}

Now you can run:


$ sample
Sample {size = Nothing}

$ sample --size=1,2
Sample {size = Just (1,2)}

$ sample --size=1,2 --size=3,4
Sample {size = Just (3,4)}

Hopefully this increase in consistency will make CmdArgs much more predictable for users.

Help Output

The one thing I'm still wrestling with is the help output. While the help output is reasonably straightforward for single mode programs, I am still undecided how multiple mode programs should be displayed. Currently CmdArgs displays something I think is acceptable, but not optimal. I am happy to take suggestions for how to improve the help output.

Conclusion

CmdArgs 0.1 was an experiment - is it possible to define concise command line argument processors? The result was a working library, but whose potential for enhancement was limited by a lack of internal separation. CmdArgs 0.2 is a complete rewrite, designed to put the ideas from CmdArgs 0.2 into practical use, and allow lots of scope for further improvements. I hope CmdArgs will become the standard choice for most command line processing tasks.

Rethinking Supercompilation

2010-07-10T00:25:00.002+01:00

I have written a paper building on my Supero work that has been accepted to ICFP 2010. Various people have asked for copies of the paper, so I have put the current version online. This version will be removed in about three weeks and replaced with the final version, although the linked copy has nearly all the changes suggested by the reviewers. The abstract is:

Supercompilation is a program optimisation technique that is particularly effective at eliminating unnecessary overheads. We have designed a new supercompiler, making many novel choices, including different termination criteria and handling of let bindings. The result is a supercompiler that focuses on simplicity, compiles programs quickly and optimises programs well. We have benchmarked our supercompiler, with some programs running more than twice as fast than when compiled with GHC.

I've also uploaded a corresponding package to Hackage, but that code should be considered an early version - I intend to revise it before ICFP, to make it easier to run (currently I change the options by editing the source code) and include all the benchmarks. I don't recommend downloading or using the current version, and won't be supporting it in any way, but it's there for completeness.

In the near future I will be posting more general discussions about supercompilation, and about the work covered in this paper. In the meantime, if you find any mistakes in the paper, please mention them in the comments!

PS. Currently community.haskell.org is down, but I have uploaded the paper there anyway. It should be present when the site recovers.

Dangerous Primes - Why Uniplate Doesn't Contain transform'

2010-04-25T15:20:00.001+01:00

The Uniplate library contains many traversal operations, some based on functions in SYB (Scrap Your Boilerplate). SYB provides everywhere for bottom-up traversals and everywhere' for top-down traversals. Uniplate provides transform for bottom-up traversals, but has no operation similar to everywhere'. This article explains why I didn't include a transform' operation, and why I believe that most uses of everywhere' are probably incorrect.

The transform operation applies a function to every node in a tree, starting at the bottom and working upwards. To give a simple example:


data Exp = Lit Int | Add Exp Exp | Mul Exp Exp

f (Mul (Lit 1) x) = x
f (Mul (Lit 3) x) = Add x (Add x x)
f x = x

Calling transform f on the input 3 * (1 * 2) gives 2 + (2 + 2). We can write transform in terms of the Uniplate operation descend, which applies a function to every child node:


transform f x = f (descend (transform f) x)

On every application of f the argument always consists of a root node which has not yet been processed, along with child nodes that have been processed. My thesis explains how we can guarantee a transform reaches a fixed point, by calling f again before every constructor on the RHS of any clause:


f (Mul (Lit 1) x) = x
f (Mul (Lit 3) x) = f (Add x (f (Add x x)))
f x = x

Now transform f is guaranteed to reach a fixed point. The transform operation is predictable, and naturally defines bottom-up transformations matching the users intention. Unfortunately, the ordering and predictability of transform' is significantly more subtle. We can easily define transform':


transform' f x = descend (transform' f) (f x)

Here the transformation is applied to every child of the result of f. With transform every node is processed exactly once, but with transform' some nodes are processed multiple times, and some are not processed at all. The first clause of f, which returns x, does not result in the root of x being processed. Similarly, our second cause returns two levels of constructor, causing the inner Add to be both generated and then processed.

When people look at transform' the intuitive feeling tends to be that all the variables on the RHS will be processed (i.e. x), which in many cases mostly matches the behaviour of transform'. Being mostly correct means that many tests work, but certain cases fail - with our function f, the first example works, but 1 * (1 * 1) results in 1 * 1. The original version of Uniplate contained transform', and I spent an entire day tracking down a bug whose cause turned out to be a function whose RHS was just a variable, much like the first clause of f.

Before describing the solution to top-down transformations, it's interesting to first explore where top-down transformations are necessary. I have identified two cases, but there many be more. Firstly, top-down transformations are useful when one LHS is contained within another LHS, and you wish to favour the larger LHS. For example:


f (Mul (Add _ _) _) = ...
f (Add _ _) = Mul ...

Here the second LHS is contained within the first. If we perform a bottom-up transformation then the inner Add expression will be transformed to Mul, and the first clause will never match. Changing to a top-down transformation allows the larger rule to match first.

Secondly, top-down transformations are useful when some information about ancestors is accumulated as you proceed downwards. The typical example is a language with let expressions which builds up a set of bindings as it proceeds downwards, these bindings then affect which transformations are made. Sadly, transform' cannot express such a transformation.

The solution to both problems is to use the descend operation, and explicitly control the recursive step. We can rewrite the original example using descend:


f (Mul (Lit 1) x) = f x
f (Mul (Lit 3) x) = Add (f x) (Add (f x) (f x))
f x = descend f x

Here we explicitly call f to continue the transformation. The intuition that all variables are transformed is now stated explicitly. In this particular example we can also common-up the three subexpressions f x in the second clause, giving a more efficient transformation. If needed, we can add an extra argument to f to pass down information from the ancestors.

After experience with Uniplate I decided that using transform'/everywhere' correctly was difficult. I looked at all my uses of transform' and found that a few of them had subtle bugs, and in most cases using transform would have done exactly the same job. I looked at all the code on Hackage (several years ago) and found only six uses of everywhere', all of which could be replaced with everywhere without changing the meaning. I consider top-down transformations in the style of everywhere' to be dangerous, and strongly recommend using operations like descend instead.

Upcoming Workshops

Are you interested in either generics programming or Haskell? Are you going to ICFP 2010? Why not:

Submit a paper to the Workshop on Generic Programming - Generic programming is about making programs more adaptable by making them more general. This workshop brings together leading researchers and practitioners in generic programming from around the world, and features papers capturing the state of the art in this important area.

Offer a talk at the Haskell Implementors Workshop - an informal gathering of people involved in the design and development of Haskell implementations, tools, libraries, and supporting infrastructure.

I'm on the program committee for both, and look forward to receiving your contributions.

File Recovery with Haskell

2010-04-07T19:25:00.004+01:00

Haskell has long been my favoured scripting language, and in this post I thought I'd share one of my more IO heavy scripts. I have an external hard drive, that due to regular dropping, is somewhat unreliable. I have a 1Gb file on this drive, which I'd like to copy, but is partly corrupted. I'd like to copy as much as I can.

In the past I've used JFileRecovery, which I thoroughly recommend. The basic algorithm is that it copies the file in chunks, and if a chunk copy exceeds a timeout it is discarded. It has a nice graphical interface, and some basic control over timeout and block sizes. Unfortunately, JFileRecovery didn't work for this file - it has three basic problems:

The timeout sometimes fails to stop the IO, causing the program to hang.

If the copy takes too long, it sometimes gives up before the end of the file.

If the block size is too small it takes forever, if it is too large it drops large parts of the file.

To recover my file I needed something better, so wrote a quick script in Haskell. The basic algorithm is to copy the the file in 10Mb chunks. If any chunk fails to copy, I split the chunk and retry it after all other pending chunks. The result is that the file is complete after the first pass, but the program then goes back and recovers more information where it can. I can terminate the program at any point with a working file, but waiting longer will probably recover more of the file.

I have included the script at the bottom of this post. I ran this script from GHCi, but am not going to turn it in to a proper program. If someone does wish to build on this script please do so (I hereby place this code in the public domain, or if that is not possible then under the ∀ n . BSD n licenses).

The script took about 15 minutes to write, and makes use of exceptions and file handles - not the kind of program traditionally associated with Haskell. A lot of hard work has been spent polishing the GHC runtime, and the Haskell libraries (bytestring, exceptions). Now this work has been done, slotting together reasonably complex scripts is simple.


{-# LANGUAGE ScopedTypeVariables #-}

import Data.ByteString(hGet, hPut)
import System.IO
import System.Environment
import Control.Monad
import Control.Exception


src = "file on dodgy drive (source)"
dest = "file on safe drive (destination)"

main :: IO ()
main =
    withBinaryFile src ReadMode $ \hSrc -> 
    withBinaryFile dest WriteMode $ \hDest -> do
    nSrc <- hFileSize hSrc
    nDest <- hFileSize hDest
    when (nSrc /= nDest) $ hSetFileSize hDest nSrc
    copy hSrc hDest $ split start (0,nSrc)


copy :: Handle -> Handle -> [(Integer,Integer)] -> IO ()
copy hSrc hDest [] = return ()
copy hSrc hDest chunks = do
    putStrLn $ "Copying " ++ show (length chunks) ++ " of at most " ++ show (snd $ head chunks)
    chunks <- forM chunks $ \(from,len) -> do
        res <- Control.Exception.try $ do
            hSeek hSrc AbsoluteSeek from
            hSeek hDest AbsoluteSeek from
            bs <- hGet hSrc $ fromIntegral len
            hPut hDest bs
        case res of
            Left (a :: IOException) -> do putChar '#' ; return $ split (len `div` 5) (from,len)
            Right _ -> do putChar '.' ; return []
    putChar '\n'
    copy hSrc hDest $ concat chunks

start = 10000000
stop = 1000

split :: Integer -> (Integer,Integer) -> [(Integer,Integer)]
split i (a,b) | i < stop = []
              | i >= b = [(a,b)]
              | otherwise = (a,i) : split i (a+i, b-i)

There are many limitations in this code, but it was sufficient to recover my file quickly and accurately.

Optimising HLint

2010-01-23T18:07:00.001Z

HLint is a tool for suggesting improvements to Haskell code. Recently I've put some effort in to optimisation and HLint is now over 20 times faster. The standard benchmark (running HLint over the source code of HLint) has gone from 30 seconds to just over 1 second. This blog post is the story of that optimisation, the dead ends I encountered, and the steps I took. I've deliberately included reasonable chunks of code in this post, so interested readers can see the whole story - less technical readers should feel free to skip them. The results of the optimisation are all available on Hackage, as new versions of hlint, uniplate and derive.

Before I start, I'd like to share my five guiding principles of optimisation:

Tests - make sure you have tests, so you don't break anything while optimising.

Profile - if you don't profile first, you are almost certainly optimising the wrong thing.

Necessity - only start the optimisation process if something is running too slowly.

Benchmark - use a sensible and representative test case to benchmark, to make sure you optimise the right thing.

Optimising - to make a function faster, either call it less, or write it better.

Below are the steps in the optimisation, along with their speed improvement.

Special support for Rational in Uniplate.Data, 30s to 10s

HLint uses Uniplate extensively. HLint works over large abstract syntax trees, from the library haskell-src-exts (HSE), so a generics library is essential. There are two main variants of Uniplate - Data builds on the Scrap Your Boilerplate (SYB) instances, and Direct requires special instances. HLint uses the Data variant, as it requires no instances to be written.

One of the advantages of Uniplate is that it generally outperforms most generics libraries. In particular, the variant written on top of Data instances is often many times faster than using SYB directly. The reason for outperforming SYB is documented in my PhD thesis. The essential idea is that Uniplate builds a "hit table", a mapping noting which types can be contained within which other types - e.g. that there is potentially an Int inside Either String [Int], but there isn't an Int inside String. By consulting this mapping while traversing a value, Uniplate is able to skip large portions, leading to an efficiency improvement.

When computing the hit table it is necessary for Uniplate to create dummy values of each type, which it then traverses using SYB functions. To create dummy values Uniplate uses undefined, unfortunately given the definition data Foo = Foo !Int the value Foo undefined will be forced due to the strictness annotation, and the code will raise an error - as described in bug 243. Uniplate 1.2 had a special case for Rational, which is the only type with strict components contained within HSE. Uniplate 1.3 fixed this problem more generally by catching the exception and turning off the hit table facility on such types. Unfortunately this caused Uniplate 1.3 to turn off the hit table for HSE, causing HLint to run three times slower.

The fix was simple, and pragmatic, but not general. In Uniplate 1.4 I reinstated the special case for Rational, so now HLint makes use of the hit table, and goes three times faster. A more general solution would be to manufacture dummy values for certain types (it's usually an Int or Integer that is a strict component), or to create concrete dummy values using SYB. It's interesting to observe that if HLint used SYB as it's generics library, it would not be using the hit table trick, and would run three times slower.

Use Uniplate.Direct, 10s to 5s, reverted

Uniplate also provides a Direct version, which performs better, but requires instances to be written. In order to further improve the speed of HLint I decided to try the Direct version. The biggest hurdle to using the Direct version is that many instances need to be generated, in the case of HLint it required 677. The first step was to modify the Derive tool to generate these instances (which Derive 2.1 now does), and to write a small script to decide which instances were necessary. With these instances in place, the time dropped to 5 seconds.

Unfortunately, the downside was that compilation time skyrocketed, and the instances are very specific to a particular version of HSE. While these problems are not insurmountable, I did not consider the benefit to be worthwhile, so reverted the changes. It's worth pointing out that most users of Uniplate won't require so many instances to use the Direct versions, and that a program can be switched between Direct and Data versions without any code changes (just a simple import). I also considered the possibility of discovering which Uniplate instances dominated and using the Direct method only for those - but I did not investigate further.

Add and optimise eqExpShell, 10s to 8s

The next step was to profile. I compiled and ran HLint with the following options:


ghc --make -O1 -prof -auto-all -o hlint
hlint src +RTS -p

Looking at the profiling output, I saw that the function unify took up over 60% of the execution time:


unify :: NameMatch -> Exp -> Exp -> Maybe [(String,Exp)]
unify nm (Do xs) (Do ys) | length xs == length ys = concatZipWithM (unifyStmt nm) xs ys
unify nm (Lambda _ xs x) (Lambda _ ys y) | length xs == length ys = liftM2 (++) (unify nm x y) (concatZipWithM unifyPat xs ys)
unify nm x y | isParen x || isParen y = unify nm (fromParen x) (fromParen y)
unify nm (Var (fromNamed -> v)) y | isUnifyVar v = Just [(v,y)]
unify nm (Var x) (Var y) | nm x y = Just []
unify nm x y | ((==) `on` descend (const $ toNamed "_")) x y = concatZipWithM (unify nm) (children x) (children y)
unify nm _ _ = Nothing

The function unify is an essential part of the rule matching in HLint, and attempts to compare a rule to a target expression, and if successful returns the correct substitution. Each rule is compared to every expression in all files, which means that unify is called millions of times in a normal HLint run. Looking closely, my first suspicion was the second line from the bottom in the guard - the call to descend and (==). This line compares the outer shell of two expressions, ignoring any inner expressions. It first uses the Uniplate descend function to insert a dummy value as each subexpression, then compares for equality. To test my hypothesis that this method was indeed the culprit I extracted it to a separate function, and modified unify to call it:


eqExpShell :: Exp_ -> Exp_ -> Bool
eqExpShell = (==) `on` descend (const $ toNamed "_")

I reran the profiling, and now all the time was being spent in eqExpShell. My first thought was to expand out the function to not use Uniplate. I quickly rejected that idea - there are expressions within statements and patterns, and to follow all the intricacies of HSE would be fragile and verbose.

The first optimisation I tried was to replace toNamed "_", the dummy expression, with something simpler. The toNamed call expands to many constructors, so instead I used Do an [] (an is a dummy source location), which is the simplest expression HSE provides. This change had a noticeable speed improvement.


eqExpShell :: Exp_ -> Exp_ -> Bool
eqExpShell = (==) `on` descend (const $ Do an [])

My second thought was to add a quick test, so that if the outer constructors were not equal then the expensive test was not tried. Determining the outer constructor of a value can be done by calling show then only looking at the first word (assuming a sensible Show instance, which HSE has).


eqExpShell :: Exp_ -> Exp_ -> Bool
eqExpShell x y =
    ((==) `on` constr) x y &&
    ((==) `on` descend (const $ Do an [])) x y
    where constr = takeWhile (not . isSpace) . show

This change had a bigger speed improvement. I found that of the 1.5 million times eqExpShell was called, the quick equality test rejected 1 million cases.

My next thought was to try replacing constr with the SYB function toConstr. There was no noticeable performance impact, but the code is neater, and doesn't rely on the Show instance, so I stuck with it. After all these changes HLint was 2 seconds faster, but eqExpShell was still the biggest culprit on the profiling report.

Write eqExpShell entirely in SYB, 8s to 8s, reverted

My next thought was to rewrite eqExpShell entirely in SYB functions, not using the Eq instance at all. The advantages of this approach would be that I can simply disregard all subexpressions, I only walk the expression once, and I can skip source position annotations entirely. Starting from the geq function in SYB, I came up with:


data Box = forall a . Data a => Box a

eqExpShellSYB :: Exp_ -> Exp_ -> Bool
eqExpShellSYB = f
    where
        f :: (Data a, Data b) => a -> b -> Bool
        f x y = toConstr x == toConstr y &&
                and (zipWith g (gmapQ Box x) (gmapQ Box y))

        g (Box x) (Box y) = tx == typeAnn || tx == typeExp || f x y
            where tx = typeOf x

typeAnn = typeOf an
typeExp = typeOf ex

Unfortunately, this code takes exactly the same time as the previous version, despite being significantly more complex. My guess is that toConstr is not as fast as the Eq instance, and that this additional overhead negates all the other savings. I decided to revert back to the simpler version.

Call eqExpShell less, 8s to 4s

Having failed to optimise eqExpShell further, I then thought about how to call it less. I added a trace and found that of the 1.5 million calls, in 1.3 million times at least one of the constructors was an App. Application is very common in Haskell programs, so this is not particularly surprising. By looking back at the code for unify I found several other constructors were already handled, so I added a special case for App.


unify nm (App _ x1 x2) (App _ y1 y2) = liftM2 (++) (unify nm x1 y1) (unify nm x2 y2)

It is easy to show that if an App (or any specially handled constructor) is passed as either argument to eqExpShell then the result will be False, as if both shells had been equal a previous case would have matched. Taking advantage of this observation, I rewrote the line with the generic match as:


unify nm x y | isOther x && isOther y && eqExpShell x y = concatZipWithM (unify nm) (children x) (children y)
    where 
        isOther Do{} = False
        isOther Lambda{} = False
        isOther Var{} = False
        isOther App{} = False
        isOther _ = True

With this change the eqExpShell function was called substantially less, it disappeared from the profile, and the speed improved to 4 seconds.

Fix Uniplate bug, 4s to 1.3s

The next step was to rerun the profiling. However, the results were very confusing - almost 70% of the execution time was recorded to three CAF's, while I could see no obvious culprit. I reran the profiler with the -caf-all flag to more precisely report the location of CAF's, and was again confused - the optimiser had rearranged the functions to make -caf-all useless. I then reran the profiler with optimisation turned off using -O0 and looked again. This time the profiling clearly showed Uniplate being the source of the CAF's. The hit table that Uniplate creates is stored inside a CAF, so was an obvious candidate.

Turning back to Uniplate, I attempted to reproduce the bug outside HLint. I enhanced the benchmarking suite by adding a method to find all the String's inside very small HSE values. The standard Uniplate benchmarks are for testing the performance of running code, and I had neglected to check the creation of the hit table, assuming it to be negligible.


testN "Module" $ Module ssi Nothing [] [] []
testN "Decl" $ FunBind ssi []
testN "Exp" $ Do ssi []
testN "Pat" $ PWildCard ssi

testN :: Biplate a String => String -> a -> IO ()
testN msg x = do
    t <- timer $ evaluate $ length (universeBi x :: [String])
    putStrLn $ "HSE for " ++ msg ++ " takes " ++ dp2 t ++ "s"

My initial worry was that at 2 decimal places I was likely to see 0.00 for all values. However, that turned out not to be a problem! What I saw was:


HSE for Module takes 0.54
HSE for Decl takes 0.86
HSE for Exp takes 2.54
HSE for Pat takes 0.32

These results surprised me. In particular, the hit table from Exp to String is a subset of the Module one, so should always be faster. The computation of the hit table is reasonably complex, and I was unable to isolate the problem. The tricky part of the hit table is that it is necessary to take the fixed point of the transitive closure of reachability - I had tried to keep track of recursive types and reach a fixed point with the minimal number of recomputations. I clearly failed, and probably had an exponential aspect to the algorithm that under certain circumstances caused ridiculously bad behaviour.

Rather than try to diagnose the bug, I decided instead to rethink the approach, and simplify the design. In particular, the fixed point of the transitive closure is now written as:


fixEq trans (populate box)

Where populate finds the immediate children of a constructor, trans takes the transitive closure based on the current state, and fixEq takes the fixed point. Using this new simpler design I was also able to compute which types contained with types recursively and cache it, meaning that now computing the hit table for Module not only computes the hit table for Exp, but does so in a way that means the result can be reused when asking about Exp. After rewriting the code I reran the benchmark:


HSE for Module takes 0.03
HSE for Decl takes 0.00
HSE for Exp takes 0.00
HSE for Pat takes 0.00

I had hoped that the rewrite would fix the performance problems, and it did. I have not diagnosed the original performance bug, but at 0.03 seconds I was satisfied. I have now released Uniplate 1.5 with the revised hit table code. With this change, the time for HLint drops to 1.3 seconds and all the CAF's went away from the profile.

Sharing computation, 1.3s to 1.2s

At this point, I was happy to finish, but decided to profile just one last time. The top function in the list was matchIdea:


matchIdea :: NameMatch -> Setting -> Exp_ -> Maybe Exp_
matchIdea nm MatchExp{lhs=lhs,rhs=rhs,side=side} x = do
    u <- unify nm (fmap (const an) lhs) (fmap (const an) x)
    u <- check u
    guard $ checkSide side u
    let rhs2 = subst u rhs
    guard $ checkDot lhs rhs2
    return $ unqualify nm $ dotContract $ performEval rhs2

This function first strips both the rule (lhs) and the expression (x) of their source position information to ensure equality works correctly. However, both the rules and expressions are reused multiple times, so I moved the fmap calls backwards so each rule/expression is only ever stripped of source position information once. With this change the runtime was reduced to 1.2 seconds.

Final Results

After all that effort, I reran the profile results and got:


parseString                    HSE.All               16.2   17.7
matchIdea                      Hint.Match            14.4    1.6
eqExpShellSlow                 HSE.Eq                 9.2   11.4
listDecl                       Hint.List              6.1    4.1
lambdaHint                     Hint.Lambda            5.1    5.6
bracketHint                    Hint.Bracket           4.1    6.4
hasS                           Hint.Extensions        4.1    5.0
monadHint                      Hint.Monad             4.1    2.9
~=                             HSE.Match              4.1    2.5
isParen                        HSE.Util               3.1    0.0

Now the largest contributor to the HLint runtime is the parsing of Haskell files. There are no obvious candidates for easy optimisations, and the code runs sufficiently fast for my purposes.

Conclusions

There is still some scope for optimisation of HLint, but I leave that for future work. One possible avenue for exploration would be turning on selected packages of hints, to see which one takes the most time - profiling on a different measure.

In optimising HLint I've found two issues in Uniplate, the first of which I was aware of, and the second of which came as a total surprise. These optimisations to Uniplate will benefit everyone who uses it. I have achieved the goal of optimising HLint, simply by following the profile reports, and as a result HLint is now substantially faster than I had ever expected.

Footnote: I didn't actually profile first, as I knew that a performance regression was caused by the upgrade to Uniplate 1.3, so knew where to start looking. Generally, I would start with a profile.

Better .ghci files

2010-01-14T18:03:00.003Z

A few days ago I posted about my plan to use .ghci files for all my projects. I am now doing so in at least five projects, and it's working great. There were two disadvantages: 1) every command had to be squeezed on to a single line; 2) some names were introduced into the global namespace. Thanks to a hint from doliorules, about :{ :} I can eliminate these disadvantages.

Let's take the previous example from HLint's .ghci file:


let cmdHpc _ = return $ unlines [":!ghc --make -isrc -i. src/Main.hs -w -fhpc -odir .hpc -hidir .hpc -threaded -o .hpc/hlint-test",":!del hlint-test.tix",":!.hpc\\hlint-test --help",":!.hpc\\hlint-test --test",":!.hpc\\hlint-test src --report=.hpc\\hlint-test-report.html +RTS -N3",":!.hpc\\hlint-test data --report=.hpc\\hlint-test-report.html +RTS -N3",":!hpc.exe markup hlint-test.tix --destdir=.hpc",":!hpc.exe report hlint-test.tix",":!del hlint-test.tix",":!start .hpc\\hpc_index_fun.html"]
:def hpc cmdHpc

It work's, but it's ugly. However, it can be rewritten as:


:{
:def hpc const $ return $ unlines
    [":!ghc --make -isrc -i. src/Main.hs -w -fhpc -odir .hpc -hidir .hpc -threaded -o .hpc/hlint-test"
    ,":!del hlint-test.tix"
    ,":!.hpc\\hlint-test --help"
    ,":!.hpc\\hlint-test --test"
    ,":!.hpc\\hlint-test src --report=.hpc\\hlint-test-report.html +RTS -N3"
    ,":!.hpc\\hlint-test data --report=.hpc\\hlint-test-report.html +RTS -N3"
    ,":!hpc.exe markup hlint-test.tix --destdir=.hpc"
    ,":!hpc.exe report hlint-test.tix"
    ,":!del hlint-test.tix"
    ,":!start .hpc\\hpc_index_fun.html"]
:}

The :{ :} notation allows multi-line input in GHCi. GHCi also allows full expressions after a :def. Combined, we now have a much more readable .ghci file.

Using .ghci files to run projects

2010-01-09T16:50:00.004Z

I develop a reasonable number of different Haskell projects, and tend to switch between them regularly. I often come back to a project after a number of months and can't remember the basics - how to load it up, how to test it. Until yesterday, my technique was to add a ghci.bat file to load the project, and invoke the tests with either :main test or :main --test. For some projects I also had commands to run hpc, or perform profiling. Using .ghci files, I can do much better.

All my projects are now gaining .ghci files in the root directory. For example, the CmdArgs project has:


:set -w -fwarn-unused-binds -fwarn-unused-imports
:load Main

let cmdTest _ = return ":main test"
:def test cmdTest

The first line sets some additional warnings. I usually develop my projects in GHCi with lots of useful warnings turned on. I could include these warnings in the .cabal file, but I'd rather have them when developing, and not display them when other people are installing.

The second line loads the Main.hs file, which for CmdArgs is the where I've put the main tests.

The last two lines define a command :test which when invoked just runs :main test, which is how I run the test for CmdArgs.

To load GHCi with this configuration file I simply change to the directory, and type ghci. It automatically loads the right files, and provides a :test command to run the test suite.

I've also converted the HLint project to use a .ghci file. This time the .ghci file is slightly different, but the way I load/test my project is identical:


:set -fno-warn-overlapping-patterns -w -fwarn-unused-binds -fwarn-unused-imports
:set -isrc;.
:load Main

let cmdTest _ = return ":main --test"
:def test cmdTest

let cmdHpc _ = return $ unlines [":!ghc --make -isrc -i. src/Main.hs -w -fhpc -odir .hpc -hidir .hpc -threaded -o .hpc/hlint-test",":!del hlint-test.tix",":!.hpc\\hlint-test --help",":!.hpc\\hlint-test --test",":!.hpc\\hlint-test src --report=.hpc\\hlint-test-report.html +RTS -N3",":!.hpc\\hlint-test data --report=.hpc\\hlint-test-report.html +RTS -N3",":!hpc.exe markup hlint-test.tix --destdir=.hpc",":!hpc.exe report hlint-test.tix",":!del hlint-test.tix",":!start .hpc\\hpc_index_fun.html"]
:def hpc cmdHpc

The first section turns on/off the appropriate warnings, then sets the include path and loads the main module.

The second section defines a command named :test, which runs the tests.

The final section defines a command named :hpc which runs hpc and pops up a web browser with the result. Unfortunately GHC requires definitions entered in a .ghci file to be on one line, so the formatting isn't ideal, but it's just a list of commands to run at the shell.

Using a .ghci file for all my projects has a number of advantages:

I have a consistent interface for all my projects.

Typing :def at the GHCi prompt says which definitions are in scope, and thus which commands exist for this project.

I've eliminated the Windows specific .bat files.

The .ghci file mechanism is quite powerful - I've yet to explore it fully, but could imagine much more complex commands.

Update: For a slight improvement on this technique see this post.

Thanks to Gwern Branwen for submitting a .ghci file for running HLint, and starting my investigation of .ghci files.

Explaining Haskell IO without Monads

2010-01-03T10:29:00.007Z

This tutorial explains how to perform IO in Haskell, without attempting to give any understanding of monads. We start with the simplest example of IO, then build up to more complex examples. You can either read the tutorial to the end, or stop at the end of any section - each additional section will let you tackle new problems. We assume basic familiarity with Haskell, such as the material covered in chapters 1 to 6 of Programming in Haskell by Graham Hutton.

IO Functions

In this tutorial I use four standard IO functions:

readFile :: FilePath -> IO String -- read in a file

writeFile :: FilePath -> String -> IO () -- write out a file

getArgs :: IO [String] -- get the command line arguments, from the module System.Environment

putStrLn :: String -> IO () -- write out a string, followed by a new line, to the console

Simple IO

The simplest useful form of IO is to read a file, do something, then write out a file.


main :: IO ()
main = do
   src <- readFile "file.in"
   writeFile "file.out" (operate src)

operate :: String -> String
operate = ... -- your code here

This program gets the contents of file.in, runs the operate function on it, then writes the result to file.out. The main function contains all the IO operations, while operate is entirely pure. When writing operate you do not need to understand any details of IO. This pattern of IO was sufficient for my first two years of programming Haskell.

Action List

If the pattern described in Simple IO is insufficient, the next step is a list of actions. A main function can be written as:


main :: IO ()
main = do
    x1 <- expr1
    x2 <- expr2
    ...
    xN <- exprN
    return ()

The main function starts with do, then has a sequence of xI <- exprI statements, and ends with return (). Each statement has a pattern on the left of the arrow (often just a variable), and an expression on the right. If the expression is not of type IO, then you must write xI <- return (exprI). The return function takes a value, and wraps it in the IO type.

As a simple example we can write a program that gets the command line arguments, reads the file given by the first argument, operates on it, then writes out to the file given by the second argument:


main :: IO ()
main = do
    [arg1,arg2] <- getArgs
    src <- readFile arg1
    res <- return (operate src)
    _ <- writeFile arg2 res
    return ()

As before, operate is a pure function. The first line after the do uses a pattern match to extract the command line arguments. The second line reads the file specified by the first argument. The third line uses return to wrap a pure value. The fourth line provides no useful result, so we ignore it by writing _ <-.

Simplifying IO

The action list pattern is very rigid, and people usually simplify the code using the following three rules:

_ <- x can be rewritten as x.

If the penultimate line doesn't have a binding arrow (<-) and is of type IO (), then the return () can be removed.

x <- return y can be rewritten as let x = y (provided you don't reuse variable names).

With these rules we can rewrite our example as:


main :: IO ()
main = do
    [arg1,arg2] <- getArgs
    src <- readFile arg1
    let res = operate src
    writeFile arg2 res

Nested IO

So far only the main function has been of type IO, but we can create other IO functions, to wrap up common patterns. For example, we can write a utility function to print nice looking titles:


title :: String -> IO ()
title str = do
    putStrLn str
    putStrLn (replicate (length str) '-')
    putStrLn ""

We can use this title function multiple times within main:


main :: IO ()
main = do
    title "Hello"
    title "Goodbye"

Returning IO Values

The functions we've written so far have all been of type IO (), which lets us perform IO actions, but not give back interesting results. To give back the value x, we write return x as the final line of the do block. Unlike the imperative language return statement, this return must be on the final line.


readArgs :: IO (String,String)
readArgs = do
    xs <- getArgs
    let x1 = if length xs > 0 then xs !! 0 else "file.in"
    let x2 = if length xs > 1 then xs !! 1 else "file.out"
    return (x1,x2)

This function returns the first two command line arguments, or supplies default values if fewer arguments are given. We can now use this in the main program from before:


main :: IO ()
main = do
    (arg1,arg2) <- readArgs
    src <- readFile arg1
    let res = operate src
    writeFile arg2 res

Now, if less than two arguments are given, the program will use default file names instead of crashing.

Optional IO

So far we've only seen a static list of IO statements, executed in order. Using if, we can choose what IO to perform. For example, if the user enters no arguments we can tell them:


main :: IO ()
main = do
    xs <- getArgs
    if null xs then do
        putStrLn "You entered no arguments"
     else do
        putStrLn ("You entered " ++ show xs)

For optional IO you make the final statement of the do block an if, then under each branch continue the do. The only subtle point is that the else must be indented by one more space than the if. This caveat is widely considered to be a bug in the definition of Haskell, but for the moment, the extra space before the else is required.

Break Time

If you've gone from understanding no IO to this point in the tutorial, I suggest you take a break (a cookie is recommended). The IO presented above is all that imperative languages provide, and is a useful starting point. Just as functional programming provides much more powerful ways of working with functions by treating them as values, it also allows IO to be treated as values, which we explore in the rest of the tutorial.

Working with IO Values

The next stage is to work with IO as values. Until now, all IO statements have been executed immediately, but we can also create variables of type IO. Using our title function from above we can write:


main :: IO ()
main = do
    let x = title "Welcome"
    x
    x
    x

Instead of running the IO with x <-, we have placed the IO value in the variable x, without running it. The type of x is IO (), so we can now write x on a line to execute the action. By writing the x three times we perform the action three times.

Passing IO Arguments

We can also pass IO values as arguments to functions. In the previous example we ran the IO action three times, but how would we run it fifty times? We can write a function that takes an IO action, and a number, and runs the action that number of times:


replicateM_ :: Int -> IO () -> IO ()
replicateM_ n act = do
    if n == 0 then do
        return ()
     else do
        act
        replicateM_ (n-1) act

This definition makes use of optional IO to decide when to stop, and recursion to continue performing the IO. We can now rewrite the previous example as:


main :: IO ()
main = do
    let x = title "Welcome"
    replicateM_ 3 x

In an imperative language the replicateM_ function is built in as a for statement, but the flexibility of Haskell allows us to define new control flow statements - a very powerful feature. The replicateM_ function defined in Control.Monad is like ours, but more general, and can be used instead.

IO in Structures

We've seen IO values being passed as arguments, so it's natural that we can also put IO in structures such as lists and tuples. The function sequence_ takes a list of IO actions, and executes each action in turn:


sequence_ :: [IO ()] -> IO ()
sequence_ xs = do
    if null xs then do
        return ()
     else do
        head xs
        sequence_ (tail xs)

If there are no elements in the list then sequence_ stops, with return (). If there are elements in the list then sequence_ gets the first action (with head xs) and executes it, then calls sequence_ on the remaining actions. As before, sequence_ is available in Control.Monad, but in a more general form. It is now simple to rewrite replicateM_ in terms of sequence_:


replicateM_ :: Int -> IO () -> IO ()
replicateM_ n act = sequence_ (replicate n act)

Pattern Matching

A much more natural definition of sequence_, rather than using null/head/tail, is to make use of Haskell's pattern matching. If there is exactly one statement in a do block, you can remove the do. Rewriting sequence_ we can eliminate the do after the equals sign, and the do after the then keyword.


sequence_ :: [IO ()] -> IO ()
sequence_ xs =
    if null xs then
        return ()
     else do
        head xs
        sequence_ (tail xs)

Now we can replace the if with pattern matching, without needing to consider the IO:


sequence_ :: [IO ()] -> IO ()
sequence_ [] = return ()
sequence_ (x:xs) = do
    x
    sequence_ xs

Final Example

As a final example, imagine we wish to perform some operation on every file given at the command line. Using what we have already learnt, we can write:


main :: IO ()
main = do
    xs <- getArgs
    sequence_ (map operateFile xs)

operateFile :: FilePath -> IO ()
operateFile x = do
    src <- readFile x
    writeFile (x ++ ".out") (operate src)

operate :: String -> String
operate = ...

IO Design

A Haskell program usually consists of an outer IO shell calling pure functions. In the previous example main and operateFile are part of the IO shell, while operate and everything it uses are pure. As a general design principle, keep the IO layer small. The IO layer should concisely perform the necessary IO, then delegate to the pure part. Use of explicit IO in Haskell is necessary, but should be kept to a minimum - pure Haskell is where the beauty lies.

Where to go now

You should now be equipped to do all the IO you need. To become more proficient I recommend any of the following:

Write lots of Haskell code.

Read chapters 8 and 9 of Programming in Haskell by Graham Hutton. You should expect to spend about 6 hours thinking and contemplating on sections 8.1 to 8.4 (I recommend going to a hospital A&E department with a minor injury).

Read Monads as Containers, an excellent introduction to monads.

Look at the documentation on the monad laws, and find where I've used them in this tutorial.

Read through all the functions in Control.Monad, try to define them, and then use them when writing programs.

Implement and use a state monad.

Haskell DLL's on Windows

2009-11-23T11:58:00.004Z

The current section of the GHC manual on creating DLL's on Windows is fairly confusing to read, and has some bugs (i.e. 3605). Since I got tripped up by the current documentation, I offered to rewrite sections 11.6.2 and 11.6.3 (merging them in the process). Creating Windows DLL's with GHC is surprisingly easy, and my revised manual section includes an example which can be called from both Microsoft Word (using VBA) and C++. I've pasted the revised manual section as the rest of this blog post. I'll shortly be submitting it to the GHC team, so any feedback is welcome.

11.6.2. Making DLLs to be called from other languages

This section describes how to create DLLs to be called from other languages, such as Visual Basic or C++. This is a special case of Section 8.2.1.2, "Making a Haskell library that can be called from foreign code"; we'll deal with the DLL-specific issues that arise below. Here's an example:

Use foreign export declarations to export the Haskell functions you want to call from the outside. For example:


-- Adder.hs
{-# LANGUAGE ForeignFunctionInterface #-}
module Adder where

adder :: Int -> Int -> IO Int  -- gratuitous use of IO
adder x y = return (x+y)

foreign export stdcall adder :: Int -> Int -> IO Int

Add some helper code that starts up and shuts down the Haskell RTS:


// StartEnd.c
#include <Rts.h>

extern void __stginit_Adder(void);

void HsStart()
{
   int argc = 1;
   char* argv[] = {"ghcDll", NULL}; // argv must end with NULL

   // Initialize Haskell runtime
   char** args = argv;
   hs_init(&argc, &args);

   // Tell Haskell about all root modules
   hs_add_root(__stginit_Adder);
}

void HsEnd()
{
   hs_exit();
}

Here, Adder is the name of the root module in the module tree (as mentioned above, there must be a single root module, and hence a single module tree in the DLL). Compile everything up:


$ ghc -c Adder.hs
$ ghc -c StartEnd.c
$ ghc -shared -o Adder.dll Adder.o Adder_stub.o StartEnd.o

Now the file Adder.dll can be used from other programming languages. Before calling any functions in Adder it is necessary to call HsStart, and at the very end call HsEnd.

NOTE: It may appear tempting to use DllMain to call hs_init/hs_exit, but this won’t work (particularly if you compile with -threaded).

11.6.2.1. Using from VBA

An example of using Adder.dll from VBA is:


Private Declare Function Adder Lib "Adder.dll" Alias "adder@8" _
      (ByVal x As Long, ByVal y As Long) As Long

Private Declare Sub HsStart Lib "Adder.dll" ()
Private Declare Sub HsEnd Lib "Adder.dll" ()

Private Sub Document_Close()
HsEnd
End Sub

Private Sub Document_Open()
HsStart
End Sub

Public Sub Test()
MsgBox "12 + 5 = " & Adder(12, 5)
End Sub

This example uses the Document_Open/Close functions of Microsoft Word, but provided HsStart is called before the first function, and HsEnd after the last, then it will work fine.

11.6.2.2. Using from C++

An example of using Adder.dll from C++ is:


// Tester.cpp
#include "HsFFI.h"
#include "Adder_stub.h"
#include <stdio.h>

extern "C" {
    void HsStart();
    void HsEnd();
}

int main()
{
    HsStart();
    // can now safely call functions from the DLL
    printf("12 + 5 = %i\n", adder(12,5))    ;
    HsEnd();
    return 0;
}

This can be compiled and run with:


$ ghc -o tester Tester.cpp Adder.dll.a
$ tester
12 + 5 = 17

Please give feedback in the comments.

Reviewing View Patterns

2009-11-16T20:55:00.004Z

View Patterns are an interesting extension to the pattern matching capabilities of Haskell, implemented in GHC 6.10 and above. After using view patterns in real world programs, including HLint, I've come to like them. I use view patterns in 10 of the 27 modules in HLint.

View Pattern Overview

My intuitive understanding of view patterns is given in my Approaches and Applications of Inductive Programming 2009 paper, which describes the view pattern translation as:


f (sort -> min:ascending) = ...
    ==
f v_1 | min:ascending <- sort v_1 = ...
    ==
f v_1 | case v_2 of _:_ -> True ; _ -> False = ...
    where  v_2 = sort v_1 ; min:ascending = v_2

The view pattern on the first line sorts the list elements, then binds the lowest element to min and the remaining elements to ascending. If there are no elements in the list then the pattern will not match. This can be translated to a pattern guard, which can then be translated to a case expression. This translation does not preserve the scoping behaviour of the variables, but is sufficient for all my uses of view patterns. It is important to note that the translation from view patterns to pattern guards is fairly simple, and mainly eliminates one redundant intermediate variable. However, the translation from pattern guards to case expressions and guards is substantially harder.

How I Use View Patterns

My uses of view patterns seem to fall into a few distinct categories. Here are some example code snippets (mainly from HLint), along with explanation.

1) Complex/Nested Matching


uglyEta (fromParen -> App f (fromParen -> App g x)) (fromParen -> App h y) = g == h

Every operation/match pair in a pattern guard requires a separate pattern guard, whereas view patterns can be nested very naturally. Here the abstract syntax tree for expressions has brackets, and the fromParen function unwraps any brackets to find the interesting term inside. View patterns allow us to perform nested matches, which would have required three separate pattern guards.

2) Matching on a Different Structure


isAppend (view -> App2 op _ _) = op ~= "++"

The expression tree I use in HLint has lots of expressions which apply a function to two arguments - for example App (App (Var f) x) y and InfixOp x f y. I have a type class View that maps expressions into the data type data App2 = NoApp2 | App2 String Exp Exp, allowing easy matching on a range of expressions.

3) Safe Normalisation


dismogrify (simplify -> x) = .... x ....

While working with Yhc Core for the Catch and Supero tools I often wanted to process a syntax tree after simplifying it. If you name the original tree x, and the simplified tree y, then it's an easy (and type-safe) mistake to use x instead of y. To avoid this I wrote:


dismogrify bad_x = .... x ....
   where x = simplify bad_x

Using bad_x in the expression makes the mistake easy for a human to spot. Using a view pattern makes the mistake impossible.

4) Mapping


classify (Ident (getRank -> x)) = ...

Sometimes I want to take a variable in one domain, and work with it in another. In the above example getRank converts a String to a Rank enumeration. Within the classify function I only wish to work with the rank as an enumeration, so it's convenient to never bind the string. This pattern is similar to safe normalisation, but it's purpose isn't safety - just making things a little neater.

5) Abstraction

The view pattern example in the GHC manual is all about abstraction. I have mainly used HLint in programs which don't use abstract data types, just algebraic data types which are intended to be manipulated directly. I don't think there are many data types which are both abstract and have a structural view, so I suspect this use will be less common (Data.Sequence is the only type that comes to mind).

Improvements I Suggest

I think there are three improvements that should be made to the view patterns in GHC 6.10.4:

1) Warnings

In GHC 6.10 all view patterns are incorrectly considered overlapping (see bug #2395), so all users of view patterns need to supply -fno-warn-overlapping-patterns. This problem has been fixed in GHC 6.12, which is great news.

2) Scoping

The current scoping behaviour seems undesirable:


apply (f -> y) = ...
    where f = ...

Here the f in the view pattern isn't the f bound at the where. I suggest that the lhs of the -> can use variables from the where, in a similar manner to pattern guards. (It's possible this suggestion is misguided, as the scoping rules can be quite subtle.)

3) Implicit Patterns

The original view patterns wiki document asks what should become of (-> ...), and proposes it become (view -> ...). I like this idea as HLint already contains 12 instances of (view -> ...). The only question is which view should be used? I think there are two possible answers:

a) The view currently in scope

If the desugaring is simply to view, then people can select their imports appropriately to choose their view function. This proposal is similar to the rebindable syntax already supported, but in this case may be a legitimate default, due to several possible view interpretations. If one day everyone starts using Data.View.view, then the default could be switched. As an example (in combination with proposal 2) we could have:


uglyEta (-> App f (-> App g x)) (-> App h y) = g == h
    where view = fromParen

b) Data.View.view

In HLint I have used:


class View a b where
    view :: a -> b

I haven't needed any functional dependencies, as the matching always constrains the types sufficiently. I have mapped one source type (i.e. Exp) to several matching types (App2 and App1), but never mapped multiple source types onto one matching type. If I was to add a dependency it should be that b uniquely determines a, as usually b will have a pattern on the RHS which will constrain b already.

I think my preference is for using Data.view.view, primarily because all other Haskell syntax is bound to a fixed name, rather than using the name currently in scope. However, my opinions on functional dependencies should be taken with skepticism - I'm not normally a user of functional dependencies.

4) Rejected Suggestions

I do not support the idea of implicit view patterns without some leading syntax (see bug 3583) - view patterns are nice, but I don't think they are important enough to be first-class, like they are in F# (note that F# interoperates with OO languages, so first-class view patterns are much more reasonable there).

I also do not support the idea of implicit Maybe in view patterns - Maybe should not be special, and this suggestion doesn't seem to fit with the rest of Haskell.

Conclusion

View patterns are a nice enhancement to pattern guards, increasing their compositionality and reducing the need for redundant intermediate variables. I could live without view patterns, but I don't think I should have to - the design is good, and they fit in nicely with the language. As for pattern guards, I consider them an essential part of the Haskell language that really makes a substantially difference to some pieces of code that would otherwise be rather ugly.

Edit: Fix as per Christophe's comment.

How I Use HLint

2009-09-12T15:14:00.004+01:00

HLint is a tool for automatically suggesting improvements to your Haskell code. This post describes how I use HLint, and provides and some background on its development. Before reading this article, if you are an active Haskell programmer who has not yet tried out HLint, I suggest you perform the following steps:


cabal update && cabal install hlint
cd your-current-project
hlint . --report
# open report.html in your web browser

The original purpose of HLint was to help teach beginners. When helping with the functional programming course at York, I used to wander round the students, looking at their code, and suggesting improvements. After three years helping with the same course, I found myself regularly suggesting the same improvements. For example, the pattern if a then True else b came up a lot, which can be written more succinctly as a || b. Of course, having turned myself into a pattern recognition tool, the obvious step was to automate myself - and HLint is the result.

I am no longer at a University, and so the way I use HLint has changed. Often on the Haskell Cafe mailing list people ask for code reviews - intermediate level Haskellers trying to gain knowledge from those around them. The suggestions resulting from a code review are often split into two categories. There are small-scale suggestions about things such as using a better library function, and large-scale suggestions about what the structure of the program should be. Often it is useful to tackle the small-scale issues, tidying and polishing what is already there, before investigating any large-scale issues. Unfortunately reviewers are often short of time, so they may not get round to making large-scale suggestions. The hope is that HLint can automate much of the small-scale suggestions, allowing clever people to use their time more effectively on the more complex problems.

Another reason to use HLint is one of developer pride. Some developers do not react well to criticism, and take comments about their code in a very personal way. Worse still, if you declare that some small syntactic pattern is the "wrong way to do it", then you can inadvertently end up just point out the failings. In contrast, if HLint is run first, then the human suggestions are typically deeper, and are design trade-offs that can be debated.

HLint is not designed as a tool to fix existing code, but more as a tool to promote learning, thus pre-emptively fixing future code. I do not intend people to slavishly apply the hints given by HLint - each hint should be carefully considered. For example, the darcs project uses HLint, but has decided that they are not interested in eta reduction hints, so have used HLint's ignoring facility.

One use of HLint is to provide an easy mechanism to start participating in an open source project. One of the largest hurdles in project participation is writing your first patch. Many projects have different conventions and requirements, plus there is usually a large code base that needs to be learnt. A good first step might be to run HLint over the code. While many of the hints suggested by HLint might be design decisions, or minor issues, there are likely to be a few more unambiguous improvements. As a simple example, taking the xmonad code base and applying HLint shows that the import Data.Maybe statements in XMonad\Core.hs could be combined. This would be a perfect first patch for a budding xmonad developer.

HLint can be used in many ways, but my two golden rules for HLint usage are:

Do not blindly apply the output of HLint

Never review code that hasn't had HLint applied

Draft paper on Derive, comments wanted

2009-06-16T00:14:00.005+01:00

It's been a long time since I last blogged (about 3 months). Since then I've had a paper on Firstify accepted in to the Haskell Symposium (I'll post the final version to my website shortly). I've also been writing a paper on Derive to go with my invited talk at Approaches and Applications of Inductive Programming (co-located with ICFP this year). I have to submit a final version by the 22nd of June (6 days time), but any comments on this draft would be gratefully received - either add them as comments to this post or send an email to ndmitchell AT gmail DOT com.

Download link: http://community.haskell.org/~ndm/temp/derive_draft.pdf

Title: Deriving a DSL from One Example

Abstract: Given an appropriate domain specific language (DSL), it is possible to describe the relationship between Haskell data types and many generic functions, typically type class instances. While describing the relationship is possible, it is not always an easy task. There is an alternative -- simply give one example output for a carefully chosen input, and have the relationship derived.

When deriving a relationship from only one example, it is important that the derived relationship is the intended one. We identify general restrictions on the DSL, and on the provided example, to ensure a level of predictability. We then apply these restrictions in practice, to derive the relationship between Haskell data types and generic functions. We have used our scheme in the Derive tool, where over 60% of type classes are derived from a single example.

Home page: http://community.haskell.org/~ndm/derive/

Darcs repo: http://community.haskell.org/~ndm/darcs/derive

The work presented in this paper will become the basis of Derive 2.0. Many thanks for any comments!

Concise Generic Queries

2009-03-21T08:11:00.002Z

A few weeks ago David Miani asked how to write concise queries over a data type. The answer is certainly generic programming, a technique that I feel is underused in the Haskell community. I suggested David look at Uniplate, but he found greater success with SYB. Sean Leather gave a solution using EMGM. One of the advantages of Uniplate is conciseness, so I decided to tackle the same problem and compare.

A full description of the task, including data type definitions, is at Sean's blog. From a data type representing structured files (tables, headings, paragraphs) find a heading with a particular name then within that heading find a paragraph starting with "Description". The rest of this post contains solutions using Uniplate, EMGM (taken from Sean) and SYB (from David). The SYB solution is slightly different from the EMGM or Uniplate solutions, but they all do roughly the same generic operations. It is entirely possible that the EMGM/SYB solutions could be improved, but that is a job for other people.

Uniplate Solution

The Uniplate solution is:


projDesc :: String -> OrgFileP -> Maybe String
projDesc name p = listToMaybe [y |
 OrgHeadingP _ x ys <- universeBi p, name == x,
 ParagraphP y <- universeBi ys, "Description" `isPrefixOf` y]

The code can be read as:

Line 1: Type signature, given a name and a file, return the paragraph if you find one

Line 3: Find a heading with the right name

Line 4: Find a paragraph below that heading, whose name starts with "Description"

Line 2: Pick the paragraph

I find this code to be a clear, concise and simple description of the problem. The thought process to come up with the solution was as follows: You want to search, or perform a query. The first question is whether this is a deep (all nodes) or shallow (just the children) query - David doesn't say but the example seems to imply deep. If it's deep use universeBi. Operations are combined with a list comprehension that finds an element, check it has the necessary properties (the name), then performs more operations. The result is the code you see above.

EMGM Solution

Sean's solution can be found at his blog:


projDesc :: String -> OrgFileP -> Maybe String
projDesc name file = do
  hdg <- G.firstr (headings name file)
  para <- firstPara hdg
  if para =~ "Description" then return para else Nothing

headings :: String -> OrgFileP -> [OrgHeadingP]
headings name = filter check . G.collect
  where
    check (OrgHeadingP _ possible _) = name == possible

firstPara :: OrgHeadingP -> Maybe String
firstPara hdg = paraStr =<< G.firstr (G.collect hdg)
  where
    paraStr (ParagraphP str) = Just str
    paraStr _                = Nothing

This solution isn't bad, but is more verbose than the Uniplate solution. Perhaps it could be rewritten with list comprehensions? It seems that G.collect is similar to universeBi - although I am not sure.

SYB Solution

David's SYB solution can be found here along with another solution using different combinators.


eitherOr :: Either a b -> Either a b -> Either a b
eitherOr x@(Right _) _ = x
eitherOr  _ y  = y

getP14Desc :: OrgElement -> Either ErrString String
getP14Desc org = everything eitherOr (Left descError `mkQ` findDesc) =<<
                 everything eitherOr (Left findError `mkQ` findP14) org
    where
      findP14 h@(Heading {headingName=name})
          | name == "Project14" = Right h
      findP14 _ = Left findError

      findDesc (Paragraph {paragraphText=text})
          | text =~ "Description" = Right text
      findDesc _ = Left findError

      descError = "Couldn't find description for project"
      findError = "Couldn't find project."

Summary

The relative merits of each solution are highly subjective, but I believe the Uniplate solution is concise. The Uniplate solution is a simple translation of the problem, without any clever steps, so hopefully other users (who didn't write the library!) will be able to achieve similar results. The Uniplate solution required only one function from the Uniplate library, so has a small learning curve. Even if you don't choose Uniplate, generic programming techniques are very useful, and can make your code concise and robust.

Website move

2009-03-09T21:40:00.005Z

Today I spotted that I could no longer push to my darcs repos hosted at York University. A little more checking showed that my home page had also been removed - I guess that's what happens when you are no longer a student there (although a warning email before would have been nice...). So I am pleased to announce my new website address:

http://community.haskell.org/~ndm/

Thanks to the wondrous Haskell community for providing all the resources I needed to move my website with no human intervention at haste. Expect my darcs repos to move somewhere shortly too.

I have now submitted the final bound copies of my thesis, and have uploaded a copy to my website (I had uploaded it to York, but didn't get chance to announce it!). I should say a great thank you to everyone who helped with my work/thesis, in particular Colin Runciman for supervising me for six years, and Detlef Plump and Simon Peyton Jones for examining me and really helping improve the final document with their comments.

The thesis has four content chapters, corresponding to Uniplate, Supero, Firstify and Catch. I have submitted a paper to ICFP 09 which expands/clarifies the Firstify work, which I'll upload as a draft shortly. For the other chapters, the version in the thesis is an improvement on the version in any papers I've published.

Hoogle package search

2009-02-22T21:05:00.005Z

Recently on the Haskell mailing list there has been some discussions of which packages Hoogle searches by default. One person remarked that it was unfortunate that the network package isn't searched by default. There are lots of packages on Hackage, and Hoogle needs to decide how to cope with so much choice. There are a number of questions that I need to answer in Hoogle:

What packages should Hoogle search by default? All of hackage? The base libraries? Only the packages a user has installed? Only packages that make it in to the Haskell Platform?

What groups of packages should Hoogle have available? Each package individually? All packages which compile on Windows? All packages by a certain author? All packages whose minor version number is even?

What UI should Hoogle show? Should there be checkboxes for each os's package? Should their be a checkbox for each compiler/version? Should their be no UI but some documentation?

And these questions present a number of trade offs:

The packages have to be divided under sensible and clear lines - I don't want to (and shouldn't) arbitrate divisions like "good" or "popular".

The more packages you search, the less relevant the results will be.

The fewer packages you search, the more chance that you miss something.

The more UI that is added the more confusing things get.

My development time for Hoogle derives Bounded, Finite and increasingly also derives Small.

Thoughts and suggestions are very welcome. I've set up a wiki page to track peoples thoughts, please make your view and arguments known: http://haskell.org/haskellwiki/Hoogle/Packages.

(As an aside, I recently found that dolphin friendly tuna is actually really harmful to the environment, far more harmful than dolphin unfriendly tuna. Read more here.)

Monomorphism and Defaulting

2009-02-03T21:09:00.000Z

Haskell has some ugly corners - not many, but a few. One that many people consider exceptionally ugly is the monomorphism restriction. In this post I'm going to discuss three related issues - Constant Applicative Forms (CAFs), the monomorphism restriction and defaulting. But before we start, lets take a simple example.

Computing Pi

Haskell already provides the pi function which represents the value of pi, but lets assume it didn't. Taking a quick look at Wikipedia we can see that one way of computing Pi is the Gregory-Leibniz series. We can calculate pi as:

pi = (4/1) + (-4/3) + (4/5) + (-4/7) + (4/9) + (-4/11) ...

So let's write that as a Haskell program:


pie = sum $ take 1000000 $ zipWith (/) (iterate negate 4) [1,3..]

Here the constant 1000000 gives the accuracy of our approach, increasing this value will give a higher precision. As it currently stands, the Haskell library says pi = 3.14159265358979 and our program says pie = 3.14159165358977. Thirteen matching digits should be suffient for most uses of pi :-)

CAFs

The disadvantage of our pie function is that (under Hugs) it takes about 4 seconds to evaluate. If we are performing lots of calculations with pi, calculating pie each time will be a serious problem. CAFs are the solution!

A CAF is a top-level constant, which doesn't take any arguments, and will be computed at most once per program execution. As a slight subtlety, if the constant has class constraints on it (i.e. is Num a => a, instead of a) then it isn't a CAF because the class constraints act like implicit arguments. Our pie function above doesn't take any arguments, so is a CAF.

Defaulting

While pie doesn't have any class constraints, the right-hand side of pie does! Take a look in Hugs:


Main> :t sum $ take 1000000 $ zipWith (/) (iterate negate 4) [1,3..]
:: (Enum a, Fractional a) => a

Main> :t pie
:: Double

The right-hand side works for any Enum and Fractional type, for example Float, but pie is restricted to Double. The reason is the defaulting mechanism in Haskell - if a type can't be nailed down precisely, but is one of a handful of built-in classes, then it will default to a particular type. This feature is handy for working at an interactive environment, but can sometimes be a little unexpected.

Monomorphism restriction

Without defaulting the compiler would infer the type of pie as ::(Enum a, Fractional a) => a. However, such a definition would be rejected by the monomorphism restriction. The monomorphism restriction states that a function with no explicit arguments, but with class constraints, must be given a type annotation. This rejects functions like:


snub = sort . nub

To fix the problem there are two solutions:


snub i_hate_the_evil_mr = (sort . nub) i_hate_the_evil_mr

snub :: Ord a => [a] -> [a]
snub = sort . nub

For a function like pie only the second approach is applicable. The addition of dummy arguments to avoid the monomorphism restriction is sufficiently common that the HLint tool never suggests eta-reduction if the argument is named mr.

Conclusion

So why was the monomorphism restriction first introducted? For a function with no explicit arguments, the programmer might think they had written a CAF, but class constraints may substantially degrade the performance. Defaulting reduces the number of cases where the monomorphism restriction would otherwise bite, but it is still useful to be aware of the ugly corners.

There are proposals afoot to remove the monomorphism restriction and to increase the power of the default mechanism - hopefully both will be included in to Haskell'.

Small scripts with Haskell

2009-01-27T20:43:00.002Z

Normally I give blog posts detailing the fun, interesting or advanced stuff I do with Haskell. But that isn't a real representation of my programming life! Most of the time I am doing small scripts that do little tasks, so I thought I'd describe one of those. This post is written as Literate Haskell, which means you can save the whole contents as a .lhs file and run it in GHCi or Hugs.

The task I had to complete was to take a directory of files, and for each file foo.txt generate the files foo_m1.txt to foo_m3.txt, where each one file is a block of lines from the original delimited by a blank line. i.e. given the file with the lines ["","1","1","","2","","3"], the numbers "1" would go in foo_m1.txt etc.

This blog post isn't how I actually wrote the original script - I didn't use literate Haskell (since I find it ugly), I didn't give explicit import lists (since they are needlessly verbose), I didn't give type signatures (but I should have) and I didn't split the IO and non-IO as well (but again, I should have). It is intended as a guide to the simple things you can easily do with Haskell. Now on to the code...


> import System.FilePath(takeExtension, dropExtension, (<.>), (</>))
> import System.Directory(getDirectoryContents)
> import Data.Char(isSpace)
> import Control.Monad

First, let's import some useful modules. To find more about a particular function just use Hoogle and search for it, but a quick summary:


takeExtension "foo.txt" = ".txt"
dropExtension "foo.txt" = "foo"
"foo" <.> "txt" = "foo.txt"
"bar" </> "foo.txt" = "bar/foo.txt"
getDirectoryContents "C:\Windows" = running "dir C:\Windows" at the command prompt
isSpace ' ' = True

Every Haskell program starts with a main function, which is an IO action. For this program, we are going to keep all the IO in main, and only use other pure functions. With most file processing applications its best to read files from one directory, and write them to another. That way, if anything goes wrong, its usually easy to recover. In this case we read from "data" and write to "res".


> main :: IO ()
> main = do
>     files <- getDirectoryContents "data"
>     forM_ files $ \file -> when (takeExtension file == ".txt") $ do
>         src <- readFile $ "data" </> file
>         forM_ (zip [1..] (splitFile src)) $ \(i,x) ->
>              writeFile ("res" </> dropExtension file ++ "_m" ++ show i <.> "txt") x

Or in some kind of pseudo-code:


main =
    set files to be the list of files in the directory "data"
    for each file in files which has the extension ".txt"
    {
        set src to be the result of reading the file
        for each numbered result of splitFile
        {
            write out the value from splitFile to the location "res/file_m#.txt"
            where # is the 1-based index into the list of results
        }
    }

We can now move on to the pure bits left over. We want a function splitFile that takes a file, and splits it in to three chunks for each of the blocks in the file. When processing text, often there will be stray blank lines, and the term "blank lines" will also apply to lines consisting only of spaces. The code is below:


> splitFile :: String -> [String]
> splitFile xs = map (tabify . unlines) [s1,s2,s3]
>     where
>         xs2 = dropWhile null $ map (dropWhile isSpace) $ lines xs
>         (s1,_:rest) = break null xs2
>         (s2,_:s3) = break null $ dropWhile null rest

And now presented more as a list of steps:

split the text in to lines

for each line drop all the leading spaces from it

drop all the leading blank lines

break on the first empty line, the bits before are chunk 1

drop all leading blank lines for the rest

break on the first empty line in the rest, before is chunk 2, after is chunk 3

for each of the chunks, put the lines back together, then tabify them

The tabify requirement was added after. The person decided that all continuous runs of spaces should be converted to tabs, so the file could better be loaded in to a spread sheet. Easy enough to add, just a simple bit of recursive programming:


> tabify (' ':xs) = '\t' : tabify (dropWhile (== ' ') xs)
> tabify (x:xs) = x : tabify xs
> tabify [] = []

And again in English:

if you encouter a space, drop it and all successive spaces, and write out a tab

otherwise just continue onwards

Haskell is a great language for writing short scripts, and as the libraries improve it just keeps getting better.

FsCheck changes

2009-01-18T18:00:00.002Z

Kurt Schelfthout has just released FsCheck 0.4, a tool similar to QuickCheck but for F#. While working at my internship for Credit Suisse I spent a little bit of time modifying FsCheck to include automatic generators (so you don't have to describe how to generate arbitrary values) and failure shrinking (so the counter-examples are smaller). Both these changes have now been incorporated in to the main FsCheck tool. It is really nice to see the work being contributed back, and that big companies are taking the time to get the necessary legal clearance etc.

I find shrinking to be a particularly potent feature. In one real-world task I struggled to debug a test failure for 8 hours, before shrinking was available. Attacking the same example with FsCheck and shrinking made the reason for the test failure immediately obvious.

mapM, mapM_ and monadic statements

2008-12-11T12:03:00.002Z

In my last post on F# I mentioned that do mapM f xs; return 1 caused a space leak, and that the programmer should have written mapM_. I also proposed that monadic statements should work more like in F# where non-unit return values can't be ignored. Various people seemed to misunderstand both points, so I thought I'd elaborate.

mapM as a Space Leak

First, I should clarify what I understand as a space leak. A space leak is not a memory leak in the C sense. A space leak is when a computation retains more live memory than necessary for some period of time. One sign of a possible space leak is that lots of memory is retained by garbage collection.

Comparing mapM and mapM_ on the following program:


main = do
    mapM* putChar (replicate 10000 'a')
    return ()

The mapM_ variant has a maximum heap residency of 2Kb, while the mapM variant has 226Kb. Given an input list of length n, the residency of mapM_ is O(1), while mapM is O(n).

The exact reasons for the space leak are quite detailed, and I'm not going to attempt to cover them. My intuition is that the return list is wrapped in the IO monad, and therefore can't be deallocated until the IO action finishes. In summary, unless you are going to use the end result of a monadic map, always use mapM_.

Monadic Statements

In the above example it would be nice if the compiler had complained. You generated a value, but you didn't use it. Fortunately, it is a very easy fix - change the type of monadic bind (>>) :: Monad m => m a -> m b -> b to Monad m => m () -> m b -> m b. Now, if a monadic statement generates a value that isn't (), you get a type error. The above examples with mapM would be rejected by the type checker.

But what if we really wanted to call mapM? There are two options. The first is to bind the result, for example do _ <- mapM f xs; return 1. The second option, which F# favours, is do ignore $ mapM f xs ; return 1, with the auxiliary ignore :: Monad m => m a -> m (). I prefer the second option, as it clearly states that you want to ignore the result of a computation. You could even write a rule ignore . mapM f == mapM_ f.

F# from a Haskell perspective

2008-12-07T19:16:00.001Z

I've recently started a full-time job at Standard Chartered. Before that I was doing an internship with Credit Suisse, where I spent a reasonable amount of time doing F# programming. Before I started F# I had 6 years of Haskell experience, plenty of C# experience, but little exposure to ML. I've now had 3 months to experiment with F#, using an old version (the one before the latest Community Technology Preview) and here are my impressions.

F# is a functional language from Microsoft, previously a Microsoft Research language, which is moving towards a fully supported language. F# is based on ML, and some (perhaps many) ML programs will compile with F#. At the same time, F# has complete access to the .NET framework and can interoperate with languages such as C#. F# is a hybrid language - at one extreme you can write purely functional ML, and at the other extreme you can write imperative C#, just using a different syntax. F# seems to be designed as a practical language - it isn't elegant or small, but does interoperate very nicely with every .NET feature.

The Language

The F# language is based on ML, with the addition of indentation based layout, and many of the weaknesses in F# come from ML. F# is certainly more verbose than Haskell: in some places you need an extra keyword (often a let); pattern matching is not nearly as complete; the indentation isn't as natural as Haskell. However there are some nice syntactic features in F# that are not in Haskell, including generalised list/array/sequence comprehensions and active patterns.

The type checker in F# is powerful, but unpredictable. I often get surprised by where type annotations need to go, particularly when working with .NET object types. The tuple type is treated specially in many cases, and this also leads to surprise - inserting or removing a pair of brackets can effect the type checker. Much of this complexity is necessary to manage the interaction with .NET, but it does complicate the language. Unfortunately, even with the advanced type features in F#, there are no type classes. The lack of type classes precludes the standard implementation of things such as Uniplate and QuickCheck. However, F# does have some nice reflection capabilities, and often entirely generic implementations can be given using reflection. There is certainly an interesting design trade-off between reflection based operations and type classes, something I have looked at in the past and hope to explore again in future.

F# is an impure language, which offers some practical benefits from Haskell, but also encourages a less functional style. In Haskell I sometimes work within a localised state monad - F# makes this much more natural. The impurity also allows simple interaction with .NET. Having programmed with an impure language I did find myself reaching for localised state much more often - and was occasionally tempted into using global state. In most cases, this state became problematic later. Before using F# I thought purity was a good thing, now I'm convinced that purity is a good thing but that impurity is often very useful!

Haskell could learn some things from F#. Every statement in F# must either be bound to a value or evaluate to (). In Haskell it is possible to write do mapM f xs; return 1. Any experienced Haskell programmer should spot that the mapM is a space leak (it should be mapM_), but the type system doesn't enforce it. In F# the type system does. The change in Haskell is simple, and in my opinion, desirable.

The Platform

F# is a fully fledged member of the .NET platform. You can write a class in VB.NET, write a derived class in F#, and then derive from that class in C#. All the languages can produce and consume the same libraries. This integration with .NET allows companies that already use the Microsoft tools to easily migrate - even on a function by function basis. However, the combination of both an imperative framework and a functional language at some times leads to confusing choices. All of the standard .NET libraries work with arrays, but for a functional program the list is a more natural type. F# provides both, and it was never clear which I should use where, leading to lots of conversions. The .NET libraries are very powerful, but often are overly imperative. For example, the XSD libraries (Xml Schema Description) are very imperative - you have to create objects, mutate properties, then make calls. However, in Haskell, I probably wouldn't have had any XSD support, certainly nothing as well-supported as in .NET.

The Tool Chain

The most impressive aspect of F# is the integration with the Visual Studio environment. F# contains a debugger, profiler, auto-completion, identifier lookup and many other tools. While other functional languages have some of these tools, the Visual Studio environment tends to have very refined and polished implementations. The integration with F# is sometimes a little fragile, or at least was in the version I was using, but the tools are already very powerful and are likely to continue to improve.

Overall

The F# language isn't the most beautiful language ever, but it's not bad. The integration with .NET is incredible, and while this requires compromises in the language, the benefits are considerable. I still prefer Haskell as a language, but for many users the tool chain is a more important consideration, and here F# excels.

This post was brought to you by Ctrl and v, as the computer I am currently using doesn't have a # key!

Update: I'd recommend reading Vesa Karvonen's comment below - he has additional perspectives on F# from a more ML perspective.

Enabling Reply To All in Outlook

2008-12-06T09:39:00.003Z

Update: See http://neilmitchell.blogspot.com/2011/12/enabling-reply-to-all-in-outlook.html for an updated version of this functionality.

Some companies lock down the use of Outlook by disabling the Reply To All button. This makes it harder to manage email, and requires manually copying email addresses to get the same effect. But using a bit of Office VBA, it is possible to make a functioning Reply To All button. The following solution has been tested in Outlook 2003, but should work for older versions as well.

First, enable macros in Outlook. Go to Tools, Macro, Security and select Medium or Low security.

Second, add a Reply To All action. Go to Tools, Macro, Visual Basic Editor and put the following code in the text editor.


Option Explicit

Public Sub ReallyReplyAll()
Dim o As MailItem
Set o = Application.ActiveExplorer.Selection.Item(1)
o.ReplyAll.Display
End Sub

Finally, add a toolbar button to invoke the action. Go to Tools, Customise, Commands, Macros, and drag and drop the command Project1.ThisOutlookSession.ReallyReplyAll on to the toolbar. You can put this command exactly where you used to have Reply To All, and give it the same icon/name.

To test, select an email and click on the button you just added, it should do exactly what Reply To All would have done. There are some minor limitations to this method:

The button will not disable itself when it isn't applicable, i.e. when there are no emails selected. You will still be able to click on the button, but it won't do anything.
If you select a medium level of macro security, you will have to go through a security confirmation the first time you click Reply To All in an Outlook session.

If possible, try to educate the person in charge that Reply To All is perfectly good email etiquette, and that people should be trusted to use it responsibly. However, if that fails, the above method is a useful fallback.

General Updates

2008-09-29T20:21:00.003+01:00

It's been a little while since I last posted. I've recently got back from ICFP 2008, and quite a few people asked me what I was doing now. I've also got a few comments on a a few other things. The following as a section of disjointed paragraphs on a variety of topics, both academic and personal.

Catch Talk

I gave a talk at the Haskell Symposium, about Catch. A video of the talk is now online.

Generics Talk

Alexey gave a talk about generic programming libraries at the Haskell Symposium. I was particularly interested in this talk as it is somewhat like a competition between libraries, where Uniplate is one of the competitors. One thing I noticed is that the Uniplate version of the SYB example in the talk can be written as one single lexeme, namely uniplateBi. The talk was much more about generics libraries, while Uniplate is probably more accurately described as a traversal library, so issues such as conciseness of code were left out. One thing I did disagree with from the talk was the assertion that Uniplate requires Template Haskell and Data/Typeable deriving. In reality Uniplate requires neither, but if they are present, then you have the option of using them to write even less code.

From a combination of the paper and the talk I think its fair to conclude that if Uniplate does what you want, its a pretty good choice. This fits well with the Uniplate philosophy of giving up a small amount of power, to allow a massive simplification, while still being powerful enough for most tasks.

PhD/Work

I've had my PhD viva (passed with minor corrections), and have nearly finished making the minor corrections. I'll update my website with a revised copy of the thesis shortly. I'm currently working at Credit Suisse on a three month internship. I'm not working on Haskell stuff, but instead am doing F# programming. To get a feel for some of the things that are done by Credit Suisse I recommend looking at Ganesh's ICFP talk/paper and Howard's CUFP talk. Disclaimer: Nothing I say on this blog, or anywhere public, has anything to do with Credit Suisse, but are my personal thoughts.

Personal Life

I've just moved to Cambridge, and got engaged to my girlfriend (now fiancee), Emily King. I'll be commuting to Credit Suisse for the next two months.

My Libraries/Tools

Now I'm working full-time (long hours plus a long commute), its hard for me to put the same amount of time into updating and maintaining my Haskell libraries and tools. I will still be accepting patches and answering questions, but probably not fixing too many bugs at any great speed. I'm still maintaining my bug tracker, so feel free to add bugs, fix bugs, or comment on bugs. If anyone has any particular interest in a tool, I'd consider taking on a co-maintainer to reduce some of the maintenance burden.

Well Typed

There is now a Haskell consultancy, Well Typed, comprising of Duncan Coutts and Ian Lynagh. These are two very good Haskell hackers, who are now selling their knowledge and experience. Between them, they've had substantial experience with GHC, Cabal, Hackage, ByteString, TemplateHaskell and numerous Haskell libraries. They've also taught lots of students Haskell, and helped lots of beginners on IRC and mailing lists. If I want help with Haskell, or with the general infrastructure and tools, they are usually the first people I approach. I strongly recommend that anyone needing Haskell help in a commercial environment get in contact with them - they can help you get the most out of Haskell. Disclaimer: I haven't been asked to write this section, and haven't checked with Ian/Duncan first, but I do wish them luck!

Running your own Hoogle on a Web Server

2008-08-28T18:02:00.001+01:00

As promised, here is a guide on deploying Hoogle on a web server. Before doing so, you need to generate the necessary Hoogle databases, as described yesterday, and place them in the datadir configured with Cabal. Then:

Move the hoogle binary to a location where it can act as a CGI binary, perhaps changing its name to index.cgi, if necessary. Configure the CGI program to run, possibly changing the program to be executable or adding settings somewhere.

Copy the files from src/res in the darcs repo into a res directory located beside the binary.

Create a file log.txt and give it global write permissions.

Now you should have Hoogle running on a web server! Some of the features, such as OpenSearch integration, won't work - but Hoogle should be usable. If anyone does get Hoogle running on a web server I'd love to hear, any feedback appreciated. In particular, if there are any tweaks required please let me know.

Hoogle Database Generation

2008-08-27T10:06:00.002+01:00

Brief Annoucement: A new release of the Hoogle command line is out, including bug fixes and additional features. Upgrading is recommended.

Two interesting features of Hoogle 4 are working with mulitple function databases (from multiple packages), and running your own web server. Both these features aren't fully developed yet, and may change in their use, but can be used with care. This post covers how to generate your own databases, and how the web version databases are generated. Tomorrow I'm going to post on how to run your own Hoogle web server, but you'll need to generate your databases first! I'm going to walk through all the steps to create a database from the filepath library, as an example

Hoogle Databases

A Hoogle database is a set of searchable things, including text and type searching, and has a ".hoo" extension. A database may include the definitions from one package, or from multiple packages. Typically the Hoogle databases installed would include one database for each package (i.e. base.hoo, filepath.hoo), a default database (default.hoo) comprising of all the standard search items, and any number of custom databases (all.hoo) which comprise of different combinations of the other databases.

When using Hoogle, adding +name will include the given database in the search list, and -name will exclude the given package from the search. By default, Hoogle will use default.hoo, but if any +name commands are given then those databases will be used instead.

Hoogle looks for databases in the current directory, in the data directory specified by Cabal, and in any --include directories passed at the command line.

Step 1: Creating a Textbase

A Textbase is a textual representation of a function database. To generate a textbase you need to install the darcs version of Haddock, then use runhaskell Setup haddock --hoogle on your package. For filepath, this will create the file dist/doc/html/filepath/filepath.txt, which is a textbase.

Step 2: Converting a Textbase to a Database

To convert a textbase to a database use the command hoogle --convert=filepath.txt in the appropriate folder. If a package depends on any other packages, then adding +package will allow Hoogle to use the dependencies to generate a more accurate database. In the case of filepath, which depends on base, we use hoogle --convert=filepath.txt +base. This command requires base.hoo to be present.

Adding the dependencies is not strictly necessary, but will allow Hoogle to generate a more accurate database. For example, the base package defines type String = [Char], without the +base flag this type synonym would not be known to Hoogle.

We now have filepath.hoo, which can be used as a search database.

Step 3: Combining Databases

To generate a database comprising of both filepath and base, type hoogle --output=default.hoo --combine=filepath.hoo --combine=base.hoo. By combining databases you allow easy access to common groups of packages, and searching all these packages at once becomes faster than listing each database separately.

Web Version Databases

The web version uses the Hackage tarballs to generate documentation for most of its databases, but also has three custom databases:

base - the base package is just too weird, and isn't even on hackage. A darcs version and some tweaking is required.

keyword - the keyword database is a list of the keywords in Haskell, and is taken from the web page on the wiki.

hackage - the hackage database is a list of all the packages on Hackage, indexed only by the package name.

All the code for generating the web version databases is found in data/generate in the Hoogle darcs repo at http://code.haskell.org/hoogle.

Future Improvements

There are two database related tasks that still need to be done: Cabal integration and indexing all of Hackage.

Bug 80: In the future I would like Hoogle databases to be generated by Cabal automatically on installing a package. Unfortunately, I don't have the time to implement such a feature currently, and even if I did implement it, I'm unlikely to ever use it. If anyone wants to work on this, please get in contact. This is mainly a project working with Cabal.

Bug 79: The other work is to index all the packages on Hackage. The problem here is generating the textbases, once they have been created the rest is fairly simple. However, to run Haddock 2 over a package requires that the package builds, and that all the dependencies are present. Unfortunatley my machine is not powerful enough to cope with the number of packages on Hackage. Hopefully at some point the machinery that builds Haddock documentation for Hackage will also generate textbases, however in the mean time if someone wants to take on the task of generating textbases for Hackage, please get in contact.

Bug Tracker

I'm not working on Hoogle full-time anymore, so am using my bug tracker to keep track of outstanding issues. In order to interact more effectively with my bug tracker, you might want to read this guide. It describes how to vote for bugs etc.

Hoogle New Features

2008-08-20T15:18:00.003+01:00

I've now finished my Hoogle Summer of Code work, though I still intend to continue working on Hoogle when I get the chance. Before the coding period expired, I was able to add a number of new features to Hoogle. These features are all available at Hoogle, under http://haskell.org/hoogle/.

More Compact Text Searching

The old text search feature was very fast, using an on disk trie to navigate around the possible matches. The downside to this trie was the space it consumed, about half the database was devoted to it. Fortunately, I came up with an alternative way to get fast text searching (albeit slightly slower), in a lot more compact form.

Much smaller database files also mean much faster database generation, as the time spent in the IO routines is the main bottleneck.

Faster IO routines

I rewrote the underlying binary layer in Hoogle, to make it faster. It's not as fast as I would like, and I think that moving to memory-mapped files is probably a good idea. With these improvements, along with the compact text searching, I am able to generate databases in about 2 seconds (compared to about 20 seconds before).

Database Restricted Searches

Hoogle has been able to run database restricted searches for some time, but now the databases contain enough information to make it practical. By adding +package or -package to the search you can include or exclude certain packages. For example, to find out which map functions are in the containers package try map +containers. To find out which map functions are not in the containers or bytestring packages try map -containers -bytestring. I have also split out the GHC.* modules from base, so if you want to find some unboxed types in GHC's libraries try # +ghc. Note that not all the documentation links work from the GHC modules, I am still trying to fix this.

By default Hoogle searches the following packages: array, base, bytestring, cabal, containers, directory, filepath, haskell-src, hunit, keyword, mtl, parallel, parsec, pretty, process, quickcheck, random, stm, template-haskell, time, xhtml

The "ghc" package is also available if specified with +ghc and includes the GHC.* modules of base only.

Hoogle 3

I have now replaced the default Hoogle with Hoogle 4, but have copied Hoogle 3 to http://haskell.org/hoogle/3. Unfortunately, it doesn't yet work, as I need some admin help. But it will in the next few days, I hope. The only reason I can think of for using Hoogle 3 is Gtk2hs library searching, which I do want to add to Hoogle 4 when possible.

Give Me Feedback

There are quite a lot of enhancements to Hoogle that I still want to make. I have tried to list all these improvements in my bug tracker. If you find a bug, or want some feature, open an issue. If you have a particular interest in a bug, you can star it, to be informed on its progress and to indicate to me that you care.

I'm particularly interested in two pieces of feedback:

I don't use Hoogle 4 because ...

Do you use any type/name search engine? Do you want to still use Hoogle 3? Do you use Hayoo? If you use something else, what feature draws you to it? What do you dislike about Hoogle 4?

I use Hoogle 4, but my life would be nicer if ...

There are many things which effect Hoogle 4 users that I'm not aware of. If you open a bug saying what annoys you (or leave a comment and I'll do it for you) then I can keep track of this information. Even if you don't necessarily see any way to fix the problems, I'd still like to know them.

Thanks for everyone who has given feedback on Hoogle so far, it has been very useful.

GSoC Hoogle: Week 12

2008-08-15T20:17:00.002+01:00

This week I've been trying to get Hoogle 4 to the point where it can replace Hoogle 3. This is the final official week of Google Summer of Code, but I'm planning to continue hacking Hoogle next week, and then as time allows after that.

The priority this week was getting the documentation links working. The problem was not with Hoogle - displaying the links is trivial - but ensuring that Cabal + Haddock + Hoogle + random build scripts combine to generate the correct databases. This work involved lots of little changes in lots of places, but is now working properly. Included in this work is dependency tracking of packages (so that all packages using base know that String = [Char] etc), and merging multiple databases to create a single one.

After the Hoogle database was generated correctly, I started looking at using some of the additional information present. I have now added Haddock documentation inline in the search results. If the documentation is too long to fit comfortably, Hoogle uses AJAX wizzy-ness (or more accurately, DHTML) to allow the user to expand and show all the documentation. I suspect that this will eliminate many cases of the user actually following to the Haddock webpages. This feature is fairly new, and I have pushed it out because its useful - there are still many small improvements that need to be made.

This week I also spent some time attempting to generate documentation for all the Hackage libraries. I had some success, but the computer I am currently using is years old and lacks the necessary processing power. I will tackle this at some point in the future, once I have purchased a new machine (which should be quite soon).

With all these changes, I find Hoogle 4 to be significantly more usable than Hoogle 3. Please give it a try, and give feedback. At this point I'm particularly interested in any issues that would cause you to use Hoogle 3 instead of Hoogle 4.

Hoogle 3: http://haskell.org/hoogle

Hoogle 4: http://haskell.org/hoogle/beta

If there are no major issues, I will be replacing Hoogle 4 as the standard Hoogle sometime next week.

Next week: I will be no longer doing Google Summer of Code :-) I plan to refine some of the existing bits of Hoogle, and ensure that anything I haven't done is in a bug tracker for later.

User visible changes: The web search engine now gives Haddock links and displays Haddock documentation inline.

GSoC Hoogle: Week 11

2008-08-11T23:54:00.004+01:00

This week I've been releasing lots. Hoogle 4 is finally starting to come together, and should be a worthy replacement for Hoogle 3 very shortly. Rather than go into detail about the past week, I'm just going to give some of the bullet points:

I have released 4 versions of the command line version of Hoogle, available on Hackage. Many bugs have been spotted by some very useful testers, and improvements have been made.

I have released a web version of Hoogle 4, and encourage feedback.

I have started to update the wiki Manual, which now contains some details of Hoogle's query syntax.

I gave a talk at AngloHaskell 2008, which is available online, as slides and an audio stream. All of the other talks were excellent and are well worth listening to.

I have started to build Hoogle documentation for all of Hackage. The machine I'm doing this on is very slow, so its not a quick process!

Next week: I'm hoping to work on generating better Hoogle databases, including a Hoogle database for the whole of Hackage. I also have a number of bugs to fix.

User visible changes: Users can download and use Hoogle, and the web interface is online.

Hoogle 4.0 web client preview

2008-08-05T22:40:00.003+01:00

Since releasing a command line version of Hoogle 4 yesterday, I've had some useful feedback from a number of people. As a result, I have added a few bugs to the bug tracker, and fixed a few mistakes in the searching and ranking. The Hoogle on Hackage is currently 4.0.0.3 and is a recommended upgrade to all early testers.

I've now written a web interface to Hoogle 4, which has been uploaded to http://haskell.org/hoogle/beta/. This web interface is primarily so people can test searching/ranking without installing anything. There are a number of limitations:

The links to documentation do not work - this is the most severe problem, and probably stops people permanently changing to the new version.

The Haddock documentation is not present.

Some database entries are duplicates.

The Lambdabot says feature is missing.

The Suggestion feature is incomplete.

The AJAX style client features are not present.

The first three issues are fixed in Hoogle, but need various support through Haddock and Cabal to work. Other than these limitations, I am very interested in hearing what people think. As before, particularly regressions from Hoogle 3 or poor results/ranking.

Hoogle 4.0 release (beta, command line)

2008-08-04T18:54:00.004+01:00

I am pleased to announce Hoogle 4.0, available on Hackage. A couple of things to note:

This is a release of the command-line version only. It will have identical searching abilities to the web-based version, which I'm about to write.

It currently only searches the same packages as Hoogle 3 (the final release will search more).

It currently doesn't support the --info flag as previously described (problems with Haddock, not with Hoogle).

Walkthrough: Installation

If you have cabal-install available, it should be as simple as:


$ cabal update && cabal install hoogle

Otherwise, follow the standard Cabal/Hackage guidelines. Hoogle depends on about 4 packages on Hackage which are not available with a standard GHC install, so these will need to be built.

Walkthrough: A few searches

Here are some example searches. I have used --count=5 to limit the number of results displayed. If you are using a terminal with ANSI escape codes I recommend also passing --color to enable colored output.


$ hoogle map --count=5
Prelude map :: (a -> b) -> [a] -> [b]
Data.ByteString map :: (Word8 -> Word8) -> ByteString -> ByteString
Data.IntMap map :: (a -> b) -> IntMap a -> IntMap b
Data.IntSet map :: (Int -> Int) -> IntSet -> IntSet
Data.List map :: (a -> b) -> [a] -> [b]

$ hoogle "(a -> b) -> [a] -> [b]" --count=5
Prelude map :: (a -> b) -> [a] -> [b]
Data.List map :: (a -> b) -> [a] -> [b]
Control.Parallel.Strategies parMap :: Strategy b -> (a -> b) -> [a] -> [b]
Prelude fmap :: Functor f => (a -> b) -> f a -> f b
Control.Applicative <$> :: Functor f => (a -> b) -> f a -> f b

$ hoogle Data.Map.map --count=5
Data.Map map :: (a -> b) -> Map k a -> Map k b
Data.Map data Map k a
module Data.Map
Data.Map mapAccum :: (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
Data.Map mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)

$ hoogle "Functor f => (a -> b) -> f a -> f b" --count=5
Prelude fmap :: Functor f => (a -> b) -> f a -> f b
Control.Applicative <$> :: Functor f => (a -> b) -> f a -> f b
Control.Monad fmap :: Functor f => (a -> b) -> f a -> f b
Control.Monad.Instances fmap :: Functor f => (a -> b) -> f a -> f b
Data.Traversable fmapDefault :: Traversable t => (a -> b) -> t a -> t b

How you can help

I've released a command line version of the search to solicit feedback. I'm interested in all comments, but especially ones of the form:

I prefer the command line version of Hoogle 3 because ...

When I search for ... I would expect result ... to appear, or to appear above result ...

I was hoping for the feature ...

It takes too long when I ...

I'm going to be accumulating Hoogle 4 bugs in my bug tracker, or by email (http://www-users.cs.york.ac.uk/~ndm/contact/) - whichever you find more convenient.

Now I'm going to start work on the Web search :-)

GSoC Hoogle: Week 10

2008-08-03T14:41:00.003+01:00

This week I've been in Bristol, and am just about to head off to the Harbour Festival. Next week I'm heading off to AngloHaskell 2008, and will be talking about Hoogle type searching on the Saturday.

This week has been type search, yet again. There were issues with algorithmic complexity, combinatorial explosions and other fun stuff. However, its now finished. The type search is now fast enough (you can run Hoogle in Hugs against the core libraries) and gives good results. Rather than describe type searching, its easier to give an example. Searching for (a -> b) -> [a] -> [b] in Hoogle 3 gives:


Prelude.map :: (a -> b) -> [a] -> [b]
Data.List.map :: (a -> b) -> [a] -> [b]
Control.Parallel.S... parMap :: Strategy b -> (a -> b) -> [a] -> [b]
Prelude.scanr :: (a -> b -> b) -> b -> [a] -> [b]
Data.List.scanr :: (a -> b -> b) -> b -> [a] -> [b]
Prelude.scanl :: (a -> b -> a) -> a -> [b] -> [a]
Data.List.scanl :: (a -> b -> a) -> a -> [b] -> [a]
Prelude.concatMap :: (a -> [b]) -> [a] -> [b]

But in Hoogle 4 gives:


Prelude map :: (a -> b) -> [a] -> [b]
Data.List map :: (a -> b) -> [a] -> [b]
Prelude fmap :: Functor f => (a -> b) -> f a -> f b
Control.Applicative <$> :: Functor f => (a -> b) -> f a -> f b
Control.Monad fmap :: Functor f => (a -> b) -> f a -> f b
Control.Monad.Instances fmap :: Functor f => (a -> b) -> f a -> f b
Control.Applicative liftA :: Applicative f => (a -> b) -> f a -> f b
Data.Traversable fmapDefault :: Traversable t => (a -> b) -> t a -> t b
Control.Monad liftM :: Monad m => (a1 -> r) -> m a1 -> m r
Control.Parallel.Strategies parMap :: Strategy b -> (a -> b) -> [a] -> [b]

I think the new results are better. For more details, come to the AngloHaskell talk.

Next Week: I want to release a public beta of Hoogle 4 in command line form. I want to start on the web search engine and tweak the ranking algorithm. I'll also be writing up type search in the form of a presentation.

User Visible Changes: Type search works well and fast.

GSoC Hoogle: Week 9

2008-07-24T13:48:00.003+01:00

I'm off camping for the next weekend in a couple of hours, so this is my early weekly summary. From next week, for a week and a half, I'll actually have an SSH connection so expect to see 200+ patches flow into the Hoogle repo in a few days.

This week I've been rewriting the type search. I spent 3 days writing code, type checking it, but not actually having enough written to run it. Late last night I finished the code, and this morning I debugged it. Amazingly (although actually quite commonly for Haskell) it worked with only minor tweaks. I now have a type search which should scale to large databases and provide fast and accurate searches.

All the basic tests work, and I can generate a Hoogle database for the array library. I still can't generate a Hoogle database for the base library, due to a stack overflow, but I think the cause of the stack overflow has changed and should be easy to debug.

Next Week: A public beta of the command line version is now overdue, and hopefully will happen next week. I aim to finish the actual search side of Hoogle, and move on to the web interface.

User Visible Changes: Type search works again, mostly.

GSoC Hoogle: Week 8

2008-07-20T23:27:00.003+01:00

This week I've been travelling quite a bit, and rather busy with other things. Hopefully next week I'll be able to focus more time on Hoogle!

This week I fleshed out the final part of type search, including support for instances and alpha renaming of variables. After having implemented all the bits in the type search, I tried to convert the base libraries - and it failed, taking up too much time/memory to feasibly finish.

The type search is based around the idea of having nodes in a graph representing types, and then moving between these nodes, at a cost. In order to avoid a blow-up in the number of nodes in the graph, types are alpha-normalised and then alpha-renaming is performed afterwards. Instead of having 3 type nodes for (a,b), (c,d) and (a,a) there is just one named (a,b) and a 3 sets of alpha-renamings. All is good.

However, once you introduce instance restrictions, the types blow up. For example, from the type node a, you can move to Eq a => a, Ord a => a, Show a => a etc. The large (but feasible) number of type nodes, combined with even a small number of class names, gives a huge number of nodes. In fact, for every type variable in a node there are 2^n possible instance contexts it could take. All is bad.

Fortunately there is a solution - move instance checking outside the type graph. This makes the number of nodes feasible, and should work fairly well. It also has a few other benefits, including slightly better scoring and a simpler implementation in a few places. I also came up with a strategy for moving the cost associated with alpha-renaming into the graph search, which further simplifies things.

Of course, all this work takes time, so overall progress is slower than I would have liked. However, the results so far are promising, and the problems of scale seem to have been successfully addressed. The problem of fast and accurate type searching is hard, but hopefully Hoogle 4 will have a scalable solution that should be useful.

Next week: I want to finish the implementation of type searching, and check it works on the full base libraries. A release would be good, although may take place early in the following week.

User visible changes: Creating a database for the base library will now fail with a stack overflow. Hopefully next weeks changes will fix this!

GSoC Hoogle: Week 7

2008-07-11T23:46:00.003+01:00

This week I've continued to improve the type searching, and generated Hoogle databases for the core libraries. I'm away from a computer all weekend until Tuesday evening, which has happened every ICFP contest for the last 3 years.

I've substantially refactored the type searching, basing it on a proper abstract Graph data type. Now the mechanisms for dealing with type search and graph traversal are separate it is much easier to express clearly what type search is doing. I've also fleshed out the type searching code so that it can accurately perform searches with all the necessary features. There are still a number of tasks to do before the type searching code is finished, but each is a fairly discrete unit of work with well-understood problems.

The other challenge for the week has been generating Hoogle databases for the core libraries - the base library and all the other libraries GHC ships with a release. With these libraries in place, it is feasible to use Hoogle to perform useful queries. The libraries are generated using a combination of Cabal, Haddock and Hoogle. I've made changes in both the Haddock and Hoogle layers so that the full base libraries can now be processed.

In order to deal with the full base libraries there are numerous GHC extensions that must be supported. In particular, Hoogle now supports multi-parameter type classes, higher-ranked types, type operators, unboxed types, unboxed tuples and NDP style arrays. All of these features are translated down into Haskell 98 types, but most closely approximate their behaviour in GHC, and can be used in searches.

Throughout the week I've been profiling the database creation code in Hoogle. The databases for the core libraries come to about 4.5Mb, and are highly optimised for performing searches - often at the cost of making them harder to create. I've halved the time to create databases during the week, using profiling to direct improvements. The time required to process the Core libraries takes 60 seconds, which is a certainly an acceptable timeframe, but could always be faster. Currently the biggest culprit in the profile is the hPutByte function:


hPutByte :: Handle -> Int -> IO ()
hPutByte hndl i = hPutChar hndl $ chr i

Since the underlying databases are written using lots of hTell and hSeek commands, it is not possible to use something like the Data.Binary library. However, if anyone has any suggestions on how to improve performance they would be gratefully received.

Next week: I want to finish off the remaining type search features, and then package up a command line release for Hackage. Hopefully Hoogle 4 will be ready for initial use by early testers.

User visible changes: Type search is more robust, but still not fully featured. Database creation if faster and robust. You can search the base libraries.

GSoC Hoogle: Week 6

2008-07-06T20:48:00.003+01:00

This week I've been tackling type searching. I have just (in the last few minutes) got my first type search to work. At the moment type search is very limited, but all the ideas and scafolding are in place, so should now proceed relatively quickly.

In all previous versions on Hoogle, type searching was O(n), where n is the number of functions in the database. Hoogle compared the type search to each possible answer, computed a closeness score, then at the end wrote out the closest matches. This meant that before the first answer could be given, all functions had to be checked, i.e. the time for the first answer was O(n). As the Hoogle database is about to get massively bigger, this approach is insufficient.

The new version of Hoogle is much cleverer. It works by exploring a graph, following similar ideas to Dijkstra's algorithm, to reach more suitable results first. Typically, the best answers will be given without any search of the graph, and then as the graph is searched more results will appear with lower closeness. With the new scheme the complexity is O(m), where m is the number of results you want. I hope at some point after the SoC is finished to describe the algorithm properly, so others can understand it, and hopefully improve upon it.

Next week: Finishing off type searching, so it supports all the features planned. Build system work, and potentially a cabal pre-release.

User visible changes: Type search works to some degree, but not perfectly. Database debugging options (conversion and dumping to a text file) have been added.

GSoC Hoogle: Week 5

2008-06-26T19:10:00.003+01:00

This week I was going to tackle type searching, but then realised I'm going to spend 6 hours on Friday on a train (hence the weekly update on Thursday), so can spend that time productively working on paper tackling type search. So instead of type search, I worked on a few other pieces, some of which make type search easier:

Haddock Database Generation More patches to get better output from Haddock. The code now handles class methods properly, and deals with some FFI bits.

Lazy Name Searching Searching for a name is now fairly lazy. When searching for a name, Hoogle can return the prefix of the results without doing too much computation to calculate all the results. This work is useful in its own right, but very necessary for the type searching, and can be reused.

Hoogle --info The biggest feature added this week is the --info flag. When this flag is given, Hoogle picks the first result and gives more details, including any Haddock documentation associated with the function. For example:

$ hoogle +tagsoup openurl --info Text.HTML.Download openURL :: String -> IO String This function opens a URL on the internet. Any http:// prefix is ignored. > openURL "www.haskell.org/haskellwiki/Haskell" Known Limitations: * Only HTTP on port 80 * Outputs the HTTP Headers as well * Does not work with all servers It is hoped that a more reliable version of this function will be placed in a new HTTP library at some point!

Next week: Type searching! See last week for a description of what I hope to achieve.

User visible changes: The --info flag now exists.

GSoC Hoogle: Week 4

2008-06-22T14:42:00.004+01:00

This week I've stayed in one place, and had lots of opportunity to get on with Hoogle. I've done a number of different things this week:

More on Haddock databases I fixed a number of issues with the Haddock generated Hoogle information. These patches have been submitted back to Haddock.

Binary Defer library I merged the binary defer library into the Hoogle sources, and modified it substantially. Some of the modifications were thanks to suggestions from the Haskell community, particularly David Roundy. The library is now more robust, and is being used as a solid foundation to build the rest of Hoogle on top of.

Text Searching You can now search for words, even multiple words, and the search will be performed. The text searching uses efficient data structures, scales excellently, and returns better results first.

Suggestions These improvements were detailed earlier in the week.

Next week: Type searching. I have various ideas on how to go about this, but it is the most tricky part of the whole project. I hope to come up with the perfect solution by the end of the week, but if not, will come up with something good enough for Hoogle 4 then revise it after the Summer is over (it could easily suck in a whole Summer of time if I am not careful!). Much of the low-level infrastructure is already present, so it is just the search algorithm.

User visible changes: Text searching works. A session with Hoogle as it currently stands:


> cabal haddock --hoogle
-- generates tagsoup.txt
> hoogle --convert=tagsoup.txt
Generating Hoogle database
Written tagsoup.hoo
> hoogle +tagsoup is open --color
Text.HTML.TagSoup.Type isTagOpen :: Tag -> Bool
Text.HTML.TagSoup.Type isTagOpenName :: String -> Tag -> Bool

Hoogle 4 New Features

2008-06-18T22:37:00.003+01:00

I'm still developing Hoogle 4, and there are many things that don't work (such as searching for types and the web version). However, it's starting to come together, and I'm beginning to implement new features that aren't in Hoogle 3. Today I've implemented two useful features.

Multi Word Text Search

In Hoogle 3, if you entered "is just" it would be treated as a type search, exactly the same as "m a". Now, it will search for "is" and search for "just" and intersect the results. This seems to be something that people often try, so hopefully will make Hoogle more intuitive.

Intelligent Suggestions

Hoogle 3 tries to give suggestions, for example if I search for "a -> maybe a" it will helpfully suggest "a -> Maybe a". Unfortunately it's not that clever. If your search term contains a type variable (starting with a lower-case letter), which is more than one letter, it will suggest you try the capitalised version. For example, "(fst,snd) -> snd" will suggest "(Fst,Snd) -> Snd", which isn't very helpful.

The new mechanism uses knowledge about the types, arities and constructors present in the Hoogle database. Some examples:


"Just a -> a"  ===> "Maybe a -> a"
"a -> Maybe"   ===> "a -> Maybe b"
"a -> MayBe a" ===> "a -> Maybe a"
"a -> maybe a" ===> "a -> Maybe a"

darcs over FTP

2008-06-15T13:44:00.003+01:00

I'm currently unable to access SSH, and suspect this situation will persist for most of the Summer. Most of my darcs repo's are behind SSH, so this presents a problem. I've been looking for a way to work with darcs over FTP, and have managed to get it going on Windows. The following are instructions for (1) me when I forget them and (2) any Windows users who want to follow the same path. If you are a Linux user, then similar information is available from this blog post.

Step 1: Install Sitecopy

Go to http://dennisbareis.com/freew32.htm and download and install SITECPY.

Add "C:\Program Files\SITECOPY" to your path.

Add "C:\Home" to a %HOME% variable.

Open up a command line and type:


c:\> mkdir home
c:\> cd home
c:\home> mkdir .sitecopy
c:\home> echo . > .sitecopyrc

Step 2: Prepare the FTP site

Go to the FTP site, and create a directory. In my particular example, I created darcs/hoogle so I could mirror the Hoogle repo.

Step 3: Configure Sitecopy

Edit the file "c:\home\.sitecopyrc" to contain:


site          hoogle
   server     ftp.york.ac.uk
   username   ndm500
   local      C:\Neil\hoogle
   remote     web/darcs/hoogle
   port       21

Obviously, substituting in your relevant details.

Step 4: Initialise Sitecopy

Type:


sitecopy --init hoogle

darcs push

Now to do a darcs push, you can type:


sitecopy --update hoogle

The first copy will take a long time, but subsequent copies should be a lot faster.

darcs pull

After all this, you can either pull using FTP, or if your FTP is also a web site, you can pull over http. For example:


darcs get http://www-users.york.ac.uk/~ndm500/darcs/hoogle/

GSoC Hoogle: Week 3

2008-06-15T13:25:00.004+01:00

This week I've travelled a further 600 miles by train, but am now starting to get settled for the Summer, and down to work on Hoogle.

My main focus this week has been getting Haddock to generate Hoogle databases. For Haddock 0.8 I added in a --hoogle flag to generate Hoogle databases, and a similar --hoogle flag to Cabal. Unfortunately, for Haddock 2.0, the feature was removed as most of the code got rewritten. Now I've added the feature back, making extensive use of the GHC API to reduce the amount of custom pretty-printing required, and to support more Haskell features. The code has been added to the development Haddock branch, and will be present in the next release.

Most of the challenge was working with the GHC API. It's certainly a powerful body of code, but suffers from being inconsistent in various places and poorly documented. I mainly worked with the code using :i to view the API. I got bitten by various problems such as the Outputable module exporting useful functions such as mkUserStyle :: QueryQualifies -> Depth -> PprStyle, but not exporting any functions that can create a Depth value, and therefore not actually being usable. If Hoogle and Haddock could be used over the GHC API, it would substantially improve the development experience!

I've also worked more on defining the database format. I am about to start work on the implementation today. I've also added a few more command line flags, but mainly as placeholders.

Next week: Database creation and text searches (looking back I see some similarity to last week!)

User visible changes: haddock --hoogle now works.

GSoC Hoogle: Week 2

2008-06-09T08:58:00.002+01:00

This week I submitted my PhD thesis, emptied my entire rented house of furniture, spent £96 on petrol, drove (or was driven) 400 miles, travelled a similar distance by train, have been to the north of Scotland and am currently working on a borrowed Mac in London. Needless to say, its been rather busy - but now all the excitement is over and I should be able to focus properly on Hoogle.

In the last week I've been focusing on the database, the store of all the function names and type signatures, so a very critical piece of information. I want to support fast searching, which doesn't slow down as the number of known functions increases - a nasty property of the current version. For text searching, the trie data structure has this nice property, and can deal with searching for substrings. For fuzzy type searching, things are a lot more complex. However, I think I have an algorithm which is fast (few operations), accurate (gives better matches), scalable (independent of the number of functions in the database) and lazy (returns the best results first). The idea is to have a graph of function results, and then navigate this graph to find the best match.

Most of the database work has been theoretical, but I have done some coding. In particular, I have started on the database creation code, and polished the flag argument interaction code some more. Part of the development required the Derive tool, and in doing this work I noticed a few deficiencies. In particular, if you run Windows and run derive over a UNIX line-ending file, the tool will generate a Windows line-ending file. This problem, and a few others, are now fixed.

Next week: Database creation and searching. I want text searches to work by the end of the week.

User visible changes: The --help flag prints out information on the arguments.

PS. I was looking forward to seeing some blog posts from the other Haskell summer of code students on the Haskell Planet. If any Haskell GSoC student does have a blog, please ask for it to be included!

GSoC Hoogle: Week 1

2008-06-01T16:28:00.002+01:00

I started my Google Summer of Code project on Hoogle at the beginning of this week. In my initial application I promised to make my weekly updates via blog, so here is the first weeks report:

I've only done about half a weeks work on Hoogle this week, because I'm handing in my PhD thesis early next week, and because I'm moving house on Wednesday. I spent 14 hours on Saturday moving furniture, and many more hours than that on my thesis! I should be fully devoted to GSoC by the middle of next week.

Despite all the distractions, I did manage to start work on Hoogle. I created a new project for Hoogle at the community.haskell.org site, and an associated darcs repo at http://code.haskell.org/hoogle. I've done a number of things on Hoogle:

Improved the developer documentation in some places

Reorganised the repo, moving away dead files

Work on command line flags, parsing them etc.

Added a framework for running regression tests

Organise the command line/CGI division

I've started work from the front, and am intending to first flesh out an API and command line client, then move on to the web front end. The biggest change from the current implementation of Hoogle will be that there is one shared binary, which will be able to function in a number of modes. These modes will include running as a web server, as a command line version, as an interactive (Hugs/GHCi style) program, documentation location etc. This will allow easier installation, and let everyone host their own web-based Hoogle without much effort.

Next week: I hope to move towards the command line client and central Hoogle database structure. I also hope to chat to the Haddock 2 people, and try and get some integration similar to Haddock 1's --hoogle flag.

User visible changes: Hoogle 4 as it currently stands is unable to run searches, although hoogle --test will run some regression tests.

Interactive TagSoup parsing

2008-05-22T21:05:00.003+01:00

I've written quite a few programs using the tagsoup library, but have never really used the library interactively. Today I was wondering how many packages on hackage use all lower case names, compared to those starting with an initial capital. This sounds like a great opportunity to experiment! The rest of this post is a GHCi transcript, with my comments on what I'm doing prefixed with -- characters.


$ ghci
GHCi, version 6.8.2: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
-- load some useful packages
Prelude> :m Text.HTML.TagSoup Text.HTML.Download Data.List Data.Char Data.Maybe
Prelude Data.Maybe Data.Char Data.List Text.HTML.Download Text.HTML.TagSoup>
-- ouch, that prompt is a bit long - we can use :set prompt to shorten it
-- side note: I actually supplied the patch for set prompt :)
   :set prompt "Meep> "
-- lets download the list of packages
Meep> src <- openURL "http://hackage.haskell.org/packages/archive/pkg-list.html"
... src scrolls pass the screen ...
-- parse the file, dropping everything before the packages
Meep> let parsed = dropWhile (~/= "<h3>") $ parseTags src
-- grab the list of packages
Meep> let packages = sort [x | a:TagText x:_ <- tails parsed, a ~== "<a href>"]
-- now we can query the list of packages
Meep> length packages
648
Meep> length $ filter (all isLower) packages
320
Meep> length $ filter ('_' `elem`) packages
0
Meep> length $ filter ('-' `elem`) packages
165
Meep> length $ filter (any isUpper . dropWhile isUpper) packages
100
Meep> length $ filter (isPrefixOf "hs" . map toLower) packages
47
Meep> length $ filter (any isDigit) packages
37
Meep> reverse $ sort $ map (\(x:xs) -> (1 + length xs,x)) $ group $ sort $ conca
t packages
[(484,'e'),(374,'a'),(346,'r'),(336,'s'),(335,'t'),(306,'i'),(272,'l'),(248,'c')
,(247,'n'),(240,'o'),(227,'p'),(209,'h'),(185,'-'),(171,'m'),(159,'d'),(126,'g')
,(112,'b'),(96,'u'),(87,'y'),(78,'k'),(76,'f'),(74,'x'),(58,'S'),(53,'H'),(35,'w
'),(33,'v'),(29,'q'),(29,'L'),(27,'A'),(26,'F'),(24,'D'),(23,'C'),(22,'T'),(16,'
P'),(16,'M'),(16,'I'),(16,'G'),(13,'B'),(12,'W'),(12,'3'),(12,'2'),(10,'O'),(9,'
R'),(9,'1'),(8,'z'),(8,'j'),(8,'E'),(7,'X'),(7,'U'),(7,'N'),(6,'Y'),(6,'V'),(5,'
J'),(4,'Q'),(4,'5'),(4,'4'),(3,'Z'),(3,'8'),(3,'6'),(1,'9')]

We can see that loads of packages use lowercase, lots of packages use upper case, quite a few use CamelCase, quite a few start with "hs", none use "_", but lots use "-". The final query figures out which is the most common letter in hackage packages, and rather unsurprisingly, it roughly follows the frequency of English letters.

TagSoup and GHCi make a potent combination for obtaining and playing with webpages.

Haskell and Performance

2008-05-18T16:58:00.002+01:00

There has been lots of discussion on the Haskell mailing lists about the speed of Haskell. There are many conflicting opinions, and lots of different advice. Some of the information on Haskell's performance is written as a sales pitch, some is based on outdated knowledge. Since I've been working on optimisation for a while, I thought I'd try and give a snapshot of Haskell performance. Most of the following is personal opinion, and others could quite validly disagree. Since GHC is the best performing Haskell compiler, I have used Haskell to mean GHC with the -O2 flag throughout.

High-level Haskell is not as fast as C

If you write Haskell in a standard manner, it is unlikely to perform as fast as C. In most cases, linked-lists are slower than arrays. Laziness is more expensive than strictness. The Haskell code will almost always be shorter, and more concise, since it will abstract over low-level detail. But by writing that low-level detail in the C code, you are likely to produce faster code.

Low-level Haskell is competitive with C

If you use GHC, with unboxed operations, written in a low-level style, you can obtain similar performance to C. The Haskell won't be as nice as it was before, but will still probably express fewer details than the C code. Writing in such a low-level manner requires more knowledge of Haskell, and is probably something that a beginner should not be attempting. However, for a critical inner loop, low-level Haskell is a very attractive option.

Haskell's Code Generator is weak

The back end assembly generator in GHC is a weak link, but improvements are being carried out. After this work has been finished, it is likely that low-level Haskell will be able to produce nearly identical assembly code to C.

Some Haskell libraries are poorly optimised

Some of the central Haskell libraries have functions which are badly optimised. For example, the MTL library is known to be poorly performing. The words and isSpace functions in the base library aren't very good. These issues are being addressed over time, the Binary and ByteString libraries have fixed two holes. A new implementation of inits has been contributed. Over time, more issues will be identified and fixed, improving the speed of all code.

Haskell's multi-threaded performance is amazing

A lot of clever people have done a lot of clever work on making multi-threaded programming in Haskell both simple and fast. While low-level speed matters for general programming, for multi-threaded programming there are lots of much higher-level performance considerations. Haskell supports better abstraction, and can better optimise at this level, outperforming C.

Reading the Core is not easy

A standard advice to people trying to optimise Haskell is to read the Core - the low-level functional language used as an intermediate form in the compiler. While Core provides much useful information about what optimisations were performed, it isn't easy to read, and takes a lot of practice. Some effort has been done to make reading Core easier, but I still wouldn't recommend it for beginners.

Optimisation without profiling is pointless

People often want to make programs run faster. In general, this activity is a waste of time. I recently wrote a program for the HCI group at my university, which takes 10 minutes to run, and requires 4Gb of RAM, on a very expensive machine. I haven't even bothered to profile the program, because I have better things to do. Unless the speed of something actually makes a difference, you should not be spending excessive effort on optimisation.

If you have determined that the program in question is running too slowly, then profile. After profiling, you can usually identify some small part of the program that needs optimisation. Too often there is a focus on speeding up something that is not slow enough to make a difference.

The trend is for higher-level optimisation

As time goes buy, higher-level programs keep getting faster and faster. The ByteString work allows programmers to write high-level programs that are competitive with C. Performance enhancements are being made to the compiler regularly, pointer tagging, constructor specialisation etc. are all helping to improve things. More long term projects such as Supero and NDP are showing some nice results. Optimisation is a difficult problem, but progress is being made, allowing programs to be written in a higher-level.

My goal is that one day Haskell programs will be written in a very declarative, high-level style - and outperform C at the same time. I think this goal is obtainable, albeit some way in the future.

Bad strictness

2008-05-10T07:12:00.004+01:00

Haskell has one primitive construct for enforcing strictness, seq :: a -> b -> b. The idea is that the first argument is evaluated to weak-head normal form (WHNF), then the second argument is evaluated to WHNF and returned. WHNF is reduction until the outermost bit is available - either a function value, or an outer constructor.

You can model the behaviour by introducing an evaluate function, in a lower-level language, and showing how to perform reduction:


evaluate (seq a b) = do
    a' <- evaluate a
    b' <- evaluate b
    return b'

The evaluate function must return an evaluated argument, and it wants to return b which is not already evaluated, so it must make a recursive call. The evaluate function for id, which simply returns its argument, is:


evaluate (id a) = do
    a' <- evaluate a
    return a'

Notice that even though id does "nothing", it still has to evaluate its argument. Of course, evaluate (id x) is the same as evaluate x, so id performs no additional work.

Haskell is lazy, so if an expression has already been evaluated, then the evaluate call will be incredibly cheap, and just return the previous result. So let's consider the result of calling seq with the same argument twice.


evaluate (seq a a) = do
    a' <- evaluate a
    return a'

This time the second evaluation of a is skipped, as a is already evaluated. We can easily see that evaluation of seq a a is exactly equivalent to a. This means that any code which writes a `seq` a is wrong. There is plenty of this code around, and one example (which prompted me to write this) is on slide 15 of this talk.

The other classic seq related mistake is id $! x. The ($!) operator is for strict application, and is defined:


f $! x = x `seq` f x

For the particular instance of id $! x, we obtain x `seq` id x. Of course, all that id x does is evaluate x, so again there is no change from just writing x.

There are valid uses of seq, but any time you see either of the following constructs, you know the programmer got it wrong:

x `seq` x
id $! x

Summer of Code 2008

2008-04-21T23:44:00.003+01:00

This year I am going to be participating in the Google Summer of Code as a student, for the haskell.org organisation, on the Haskell API Search as an interface to Hackage project - aka Hoogle 4. I will be mentored by Niklas Broberg, author of various tools including Haskell Source Extensions, which is already used by Hoogle. My project link gives the summary I gave for the project, but below I've posted the interesting bits from my full application. I am going to be posting my progress at least once a week once the project phase starts (about 6 weeks time). I welcome any comments!

What is the goal of the project you propose to do?

There are two main goals:

1) Make Hoogle more useful to the community, along the same path as it is currently used.

2) Make Hoogle suitable to use as the standard interface to Hackage.

Can you give some more detailed design of what precisely you intend to achieve?

# Removal of all bugs

Hoogle 3 has a number of embarrassing bugs, some of which are not easily fixed. The nastiest of these is to do with monads, which are horribly mistreated. Since I now know the underlying issues which have caused a problem with Hoogle 3, things like higher-kinded type classes can be solved in a more principled manner.

# Support for some Haskell type extensions

Hoogle 3 does not deal with multi-parameter type classes. I would like to support a variety of type system extensions, primarily by mapping them on to Haskell 98 equivalent types.

# Faster searching

The current implementation is O(n) in the number of functions in the library, where the constant factor is absolutely massive. I wish to make text searching O(s), where s is the length of the search string, and have an incredibly low constant overhead -- using the a lazy file-based trie.

The type searching also needs a massive speed up. I have some ideas on how to proceed, but it is a difficult problem! I will spend a small amount of time investigating this problem, but may have to use a simpler algorithm, rather than delay the rest of the project.

# Better deployment

Currently there is Hoogle for the base libraries, and a special (very hacked) version that supports Gtk2hs only. I have received several requests for custom Hoogle instances for tools such as XMonad, Ycr2js, wxHaskell etc. The new Hoogle will make deployment of individual versions for specific packages easy.

# Support for multiple packages

I wish to support searching through every package on Hackage at once. This requires a massive speed up in the searching algorithms.

# Generalised text searching

By searching both function names, and also cabal package descriptions, Hoogle can be much more useful in finding packages, as opposed to individual functions.

# Better Design

Hoogle 3 is a web application, with a hacked on command line program. Hoogle 4 will be a central API which can be reused from any IDE tools, and also used to build the web interface and the command line application.

# Generalised interface to all of Cabal

Hopefully all the above goals will result in a tool that is suitable to be an interface to Cabal.

What deliverables do you think are reasonable targets? Can you outline an approximate schedule of milestones?

I would plan to release a beta of Hoogle 4 approximately half way through the project, as a web application. Much of the initial design has been done, so this is primarily hacking time.

I would then hope to complete the final hackage integration for the second half. This stage will require discussion with the cabal people, and will be a combination of design, implementation and server administration/setup.

In what ways will this project benefit the wider Haskell community?

Hoogle is already of use to the community, but has never seen a final release, and has a reasonable number of known bugs. This project would produce a polished version of a tool for which we already know there is huge demand.

Hackage is working well, and gaining new packages every day. As the number of packages increases, the interface to hackage must be updated to handle this volume. Discussions with some of the hackage/cabal team seem to suggest that a search interface is the way forward. By making Hackage easier to use, everyone benefits.

darcs Feature Request (Part II)

2008-04-12T12:20:00.003+01:00

I previously requested a feature for darcs. I always pull from an http repo, and push over SSH. I have to push using --no-set-default and typing the ssh repo in full, which I automate with a .bat file in each repo.

Today I noticed that darcs has _darcs/prefs/repos, which seems to list the repo's that darcs has used. In one of my typical repo files, I have an http entry and an SSH entry. To get darcs to behave the way I want, all I need to do is push using the first non-http repo in that list.

I have implemented my version of the darcs push command inside my paper tool, the code is all online here. Now I can delete all my push.bat scripts, and just type paper push from any darcs repo. As an added bonus, I now don't need to change to the root directory to perform a push.

It would be really nice if someone could incorporate this feature into the main darcs codebase. However, I'm quite happy using my paper tool for now. I certainly don't have time to patch, or even build darcs :-)

TagSoup Parsing: Dictionary Extraction

2008-04-09T22:26:00.002+01:00

I've just read issue 10 of The Monad.Reader. It's a great issue, including a tutorial on using the new GHCi debugger, and how to write an efficient Haskell interpreter in Haskell. The running example for the GHCi debugger is parsing the computer dictionary and extracting descriptions from keywords, using the TagSoup library. The article starts with an initial version of the extraction code, then fixes some mistakes using the debugger present in GHCi. The code was written to teach debugging, not as a demonstration of TagSoup. This post explains how I would have written the program.

The original program is written in a low-level style. To search for a keyword, the program laboriously traverses through the file looking for the keyword, much like a modern imperative language might. But Haskell programmers can do better. We can separate the task: first parsing the keyword/description pairs into a list; then searching the list. Lazy evaluation will combine these separate operations to obtain something just as efficient as the original. By separating the concerns, we can express each at a higher-level, reducing the search function to a simple lookup. It also gives us more flexibility for the future, allowing us to potentially reuse the parsing functions.

I have fixed a number of other bugs in the code, and my solution is:


module Main where
import Text.HTML.TagSoup
import Maybe

main = do
    putStr "Enter a term to search for: "
    term <- getLine
    html <- readFile "Dictionary.html"
    let dict = parseDict $ parseTags html
    putStrLn $ fromMaybe "No match found." $ lookup term dict


parseDict :: [Tag] -> [(String,String)]
parseDict = map parseItem 
          . sections (~== "<dt>")
          . dropWhile (~/= "<div class=glosslist>")

parseItem xs = (innerText a, unwords $ words $ innerText b)
    where (a,b) = break (~== "<dd>") (takeWhile (~/= "</dd>") xs)

Instead of searching for a single keyword, I parse all keywords using parseDict. The parseDict function first skips over the gunk at the top of the file, then finds each definition, and parses it. The parseItem function spots where tags begin and end, and takes the text from inside. The unwords $ words expression is a neat trick for normalising the spacing within an arbitrary string.

This revised program is shorter than the original, I find it easier to comprehend, and it provides more functionality with fewer bugs. The TagSoup library provides a robust base to work from, allowing concise expression of HTML/XML extraction programs.

Optional Parameters in Haskell

2008-04-08T18:12:00.006+01:00

I use optional parameters in my TagSoup library, but it seems not to be a commonly known trick, as someone recently asked if the relevant line was a syntax error. So, here is how to pass optional parameters to a Haskell function.

Optional Parameters in Other Languages

Optional parameters are in a number of other languages, and come in a variety of flavours. Ada and Visual Basic both provide named and positional optional parameters. For example, given the definition:


Sub Foo(b as Boolean = True, i as Integer = 0, s as String = "Hello")

We can make the calls:


Call Foo(s = "Goodbye", b = False)
Call Foo(False, 1)

In the first case we give named parameters, in the second we give all the parameters up to a certain position.

In some languages, such as GP⁺, you can say which parameters should take their default values:


Call Foo(_, 42, _)

Optional Parameters in Haskell

Haskell doesn't have built-in optional parameters, but using the record syntax, it is simple to encode named optional parameters.


data Foo = Foo {b :: Bool, i :: Integer, s :: String}
defFoo = Foo True 0 "Hello"

foo :: Foo -> IO ()

Now we can pass arguments by name, for example:


foo defFoo{s = "Goodbye", b = False}

This syntax takes the value defFoo, and replaces the fields s and b with the associated values. Using a type class, we can abstract this slightly:


class Def a where
    def :: a

instance Def Foo where
    def = defFoo

Now we can make all functions taking default arguments use the def argument as a basis, allowing type inference and type classes to choose the correct default type. Even still, optional parameters in Haskell are not quite as neat as in other languages, but the other features of Haskell mean they are required less often.

This technique has been used in TagSoup, particularly for the parseTagOptions function. I've also seen this technique used in cpphs with the runCpphs function.

Automated Proof Reading

2008-04-01T11:33:00.005+01:00

I've been spending the last few months writing papers, which requires lots and lots of proof reading. Yesterday Tom shared one trick he'd used to help with his thesis. He took his thesis, ran detex over it, then used a text-to-speech program to read it back to him. This trick ensures you pick up all the subtle things like repeated words, and forces you to listen to every word, not skim reading bits. I thought this was a great idea, so implemented something similar in my paper preparation tool (release forthcoming), so typing paper talk reads the paper back to you, converting the LaTeX in a sensible way, to make it as readable as possible.

Here is result of running paper talk on the introduction section of my Catch paper:

The audio is a little clearer before being compressed for upload, but still has a very clunky feel. It is surprisingly useful - I made about 12 minor changes as a result. It has some oddities, for example ML becomes millilitre, and some pause issues with brackets, which the preprocessor sorts out. The entire paper takes 49 minutes to read, but I think I will be doing this will all papers from now on.

Toddler's play with HTML in Haskell

2008-03-30T23:16:00.003+01:00

I just read a blog article entitled Kid's play with HTML in Haskell, where the author extracts some information from an HTML document, using the Haskell XML Toolbox. I have an alternative XML/HTML library, TagSoup, so I decided to implement their problem with my library.

The Problem

Given an HTML file, extract all hyperlinks to mp3 files.

In TagSoup


[mp3 | TagOpen "a" atts <- parseTags txt
     , ("href",mp3) <- atts
     , takeExtension mp3 == ".mp3"]

The code is a list comprehension. The first line says use TagSoup to parse the text, and pick all "a" links. The second line says pick all "href" attributes from the tag you matched. The final line uses the FilePath library to check the extension is mp3.

A Complete Program

The above fragment is all the TagSoup logic, but to match exact the interface to the original code, we can wrap it up as so:


import System.FilePath
import System.Environment
import Text.HTML.TagSoup

main = do
   [src] <- getArgs
   txt <- readFile src
   mapM_ putStrLn [mp3 | TagOpen "a" atts <- parseTags txt
                       , ("href",mp3) <- atts
                       , takeExtension mp3 == ".mp3"]

Summary

If you have a desire to quickly get a bit of information out of some XML/HTML page, TagSoup may be the answer. It isn't intended to be a complete HTML framework, but it does nicely optimise fairly common patterns of use.

Poor Ada Error Message

2008-03-11T18:45:00.004Z

I have been demonstrating on the York University "Algorithms and Data Structures" course for 4 years now. As part of the course, first year students learn Ada. A lot of the error messages are really bad - but over time I've created a mental mapping between the message and the cause. I am now fairly fluent at recognising what mistake a student has made, given the exercise they are attempting and the error message. But yesterday I encountered a brand new misleading error message.

The error message was:


bad.adb:12:22: actual for "N" must be a variable

As always, the most useful thing in the error message is the line number. I read enough of the error message to check whether its a parse error, type error or something else, then head for the line mentioned. (I follow this same tactic in all languages, not just Ada.)


12:     Add_Cell(I, Next(N));

Nothing obviously wrong about this statement, so I read the error message. It seems to want N to be a variable. But I already know that N is a variable, or at the very least a parameter, so this condition seems to be met.

Next step is to head to the definitions of Next and Add_Cell, to see if they can shed some light on the situation.


function Next(N: List) return List is ...
procedure Add_Cell(I: Integer, N: in out List) is ...

The in out in Add_Cell can be read as "pass as a pointer". Aha, maybe the error message is complaining that the second argument to Add_Cell can't be made a pointer, as its a return value from a function. That would explain it, and indeed, that turned out to be the cause of the problem. But back to the error message, what was it trying to tell us?


bad.adb:12:22: actual for "N" must be a variable
12:     Add_Cell(I, Next(N));

When the error message refers to N it isn't talking about the variable N I can see, but the second argument of Add_Cell, which is also called N. If the function being calling was in a separate library, it would have been even harder to understand. A more helpful error message might have been:


bad.adb:12:22: expression passed as the second argument to Add_Cell must be a variable
    Found: Next(N)
    Expected: A variable
    Reason: Second argument of Add_Cell is declared "in out"

In general compiler error messages should be in terms of the line where the error resides, not requiring a large amount of global knowledge. The error can be resolved, but without help from the message. All compilers have bad error messages in some circumstances, but this one seems almost malicious!

Sorting At Speed

2008-03-10T16:16:00.003Z

Sorting is currently a hot topic within the the Haskell community. Christopher brought it up in a recent thread on the mailing list, and this weekend I ended up spending several hours looking at sort routines.

I was browsing through the Yhc standard libraries, as one does on the weekend, and was drawn to Yhc's sort function. It had some undesirable characteristics for one of the projects I was working on, so I wondered if other Haskell systems used different implementations. I checked GHC, and discovered it their sort was different. In general, when Yhc and GHC have different implementations of a standard library function, the GHC one is better tuned for performance. I decided to replace the Yhc sort function with the GHC one, but before doing so, thought a quick performance test was in order. So I came up with something simple:


test = do
    src <- readFile "Sort.hs"
    print $ ordered $ sort $ sort $ reverse $ sort src

The file "sort.txt" was simply the source code to the program. The code sorts the contents of this file, then reverses it, sorts it and sorts it again. This means that the program performs one sort over semi-random data, one over reverse-ordered data and one over ordered-data. These are some fairly standard cases that should be checked. This test is not a comprehensive benchmark, but a nice quick indicator.

I ran the Yhc sort function against the GHC version, and was shocked to find that the Yhc code was twice as fast. I ran the benchmark under Yhc, GHC and Hugs (using reduction count in Hugs), and in all cases the performance was doubled. I was not expecting this result!

The code for the GHC sort is:


mergesort :: (a -> a -> Ordering) -> [a] -> [a]
mergesort cmp = mergesort' cmp . map (:[])

mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
mergesort' cmp [] = []
mergesort' cmp [xs] = xs
mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)

merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
merge_pairs cmp [] = []
merge_pairs cmp [xs] = [xs]
merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss

merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
merge cmp [] ys = ys
merge cmp xs [] = xs
merge cmp (x:xs) (y:ys)
 = case x `cmp` y of
        GT -> y : merge cmp (x:xs)   ys
        _  -> x : merge cmp    xs (y:ys)

The function works by splitting the list into one element lists, resulting in each basic list being ordered. These lists are then merged in pairs until a single list is left. For example, given the input "sort":


"s"  "o"  "r"  "t"
  "os"      "rt"
      "orst"

We first split each character into its own list, then merge adjacent pairs. This code corresponds to the standard merge sort. But instead of making each initial list a single element, we could use sequences of increasing elements, for example using the risers function:


risers :: Ord a => [a] -> [[a]]
risers [] = []
risers [x] = [[x]]
risers (x:y:etc) = if x <= y then (x:s):ss else [x]:(s:ss)
     where (s:ss) = risers (y:etc)

Now, if we apply risers "sort" we get ["s","ort"]. We can now follow the same merge procedure as before:


"s"    "ort"
  "orst"

Instead of doing 3 merges, we have done only 1. Given the input "abcd" the effect would have been even more dramatic. We can refine this scheme further, by detecting both ascending and descending chains of elements in the initial list. This technique is used by Yhc, and is based on code originally written by Lennart Augustsson. Knowing the original source of the code, my shock at the performance benefits offered by the Yhc version have decreased substantially.

The GHC sort function should probably be replaced by the one from the Yhc libraries. This would offer increased performance, especially in the case of ordered or reverse-ordered lists. The asymptotic complexity of the two sorts means that there must exist some value of n such that sort [1..n] runs faster in Yhc than GHC (assuming sufficient stack/heap for both). I wonder whether Int32 is capable of expressing such a value...

A side note: I have been playing with the risers function for several years. I've used it as an example of pattern match checking, both specialised to Int and on a general Ord class. I've used it for supercompiling. It's appeared in blog posts, a TFP paper (Mitchell+Runciman 2007), a Haskell Workshop paper (Xu 2006) etc. I originally had this example suggested from a functional programming exam paper, but only today at lunch did I discover its true origins. The risers function had originally been the first-step in a merge sort!

Lazy Evaluation: Strict vs. Speculative

2008-03-04T11:01:00.000Z

For the last few days I have been thinking about how to write a low-level program optimiser, based on the ideas from Supero. Supero works at the level of a lazy Core expressions, but actual hardware works on a sequence of strict instructions. The possible idea is to translate the lazy expressions to strict sequences, then borrow the ideas from supercompilation once more. In particular I have been looking at the GRIN approach, which defines such a set of instructions.

The GRIN work is very clever, and has many ideas that I would like to reuse. However, the one aspect that gave me slight concern is the complexity. A GRIN program requires the use of several analysis passes, and many many transformation rules. While this approach is perfectly acceptable, one of the goals of the Supero work is to make the optimisation process simpler -- comprising of a few simple but powerful rules.

I will first explain how strictness works, then how my speculative approach works. Readers who already know about unboxing are encouraged to skip to the speculative section.

Strictness

When doing low-level compilation, one of the most important stages is strictness analysis, and the associated unboxing. To take the example of the factorial function in Haskell:


factorial :: Int -> Int
factorial n = if n > 0 then n * factorial (n-1) else 1

Here it is easy to see that the factorial function always evaluates n. We can also use our knowledge of the definition of Int:


data Int = Int# I#

Where I# is an actual machine integer (possibly stored in a register), and Int# is a lazy box surrounding it. Since we know that factorial will always unwrap our n, we can pass the n around without the Int# box. I have made all the conversions from I# to Int explicit using an Int#, but have left all the unboxings implicit. The operators ># etc. are simply unboxed and strict variants of the standard operators.


factorial# :: Int# -> Int
factorial# n# = if n# ># 0 then n# *# factorial (Int# n# - 1) else 1

Also, since we know factorial is strict in its first argument, we can evaluate the first argument to the recursive call strictly. Applying all these optimisations can now write:


factorial# :: Int# -> Int
factorial# n# = if n# ># 0 then n# *# factorial (n# -# 1) else 1

We have removed the explicit boxing in the recursive call, and work entirely with unboxed integers. Now factorial is entirely strict. We can even write a wrapper around our strict version, to provide a lazy interface matching the original.


factorial :: Int -> Int
factorial n = factorial# n#

I have used n# to denote the unboxing of n. Now factorial looks like it did before, but operates much faster, on unboxed integers.

Speculative

I would like to not include a strictness analyser in my optimiser, or if it is included, have it be the result of a series of transformations -- without explicit "stop and analyse" then "use the results" stages. As part of my thoughts on this, I was trying to consider how to optimise factorial without invoking the strictness analyser.

The speculative transformation I have defined first generates factorial# - I have left out the details of why it decides to.


factorial :: Int -> Int
factorial n = if n > 0 then n * factorial (n-1) else 1

factorial# :: Int# -> Int
factorial# n# = if n# ># 0 then n# *# factorial (Int# n# - 1) else 1

This step is entirely safe - we have defined factorial#, but we have not written a wrapper that invokes it, even in the recursive case. The factorial# function is equivalent to factorial if the initial argument was evaluated. We have transformed factorial# using only local knowledge, at the point. We can also transform factorial, replacing any uses of n which are guaranteed to come after n is evaluated, with (Int# n#). This transformation is merely reusing the knowledge we have gained unwrapping n:


factorial n = if n > 0 then Int# n# * factorial (Int# n# - 1) else 1

Now we promote any primitive operations on only unboxed values. Given (-), it is cheaper to evalute the subtraction than to store a lazy thunk to the function.


factorial n = if n > 0 then Int# n# * factorial (Int# (n# -# 1)) else 1

factorial# n# = if n# ># 0 then n# *# factorial (Int# (n# -# 1)) else 1

We can now use our knowledge that if we know an argument to a function is already evaluated, we can call the strict variant (this corresponds closely to constructor specialisation):


factorial n = if n > 0 then n# *# factorial# (n# -# 1) else 1

factorial# n# = if n# ># 0 then n# *# factorial# (n# -# 1) else 1

We can also replace the * in factorial with *# as we know we will have to evaluate the result of a function. Now we have ended up with a fast inner loop, operating only on unboxed integers. We have not required strictness information to make any transformation.

One way of viewing the difference between strictness and this transformation is the flow of information. In strictness, the caller is informed that a particular argument will be evaluated. In speculative, the callee informs the caller that an argument has already been evaluated. These two concepts are not the same, and while they overlap, there are instances where they differ considerably.

Strict vs. Speculative

Consider the following example:


strict :: Int -> Int
strict x = x `seq` lazy x (x-1) (x+1)

lazy :: Int -> Int -> Int -> Int
lazy a b c = if a == 0 then b else c

Here the lazy function is strict in a, but not either of b or c. A strictness analyser would generate a variant of lazy with only the first argument unboxed. In contrast the speculative variant will determine that x-1 and x+1 should be evaluated, and pass unboxed values in all arguments of lazy, even though lazy may not evaluate b or c.

To see this behaviour in GHC, it helps to make lazy recursive:


module Temp where

strict :: Int -> Int
strict x = x `seq` lazy x (x+1) (x-1)

lazy :: Int -> Int -> Int -> Int
lazy a b c = if a == 0 then lazy b b b else c

Now run with the options ghc Temp.hs -c -O2 -ddump-simpl, and you will see the lazy variant has type lazy :: Int# -> Int -> Int -> Int.

These thoughts are still very preliminary, and there are a number of unanswered questions:

What is the overlap between strict and speculative?

Can both variants be combined? (almost certainly yes)

Is speculative really simpler?

Is speculative sufficient?

What are the performance benefits of speculative?

Hoogle 3 Security Bug

2008-02-29T17:17:00.000Z

I recently released Hoogle 3.1, in response to a security bug spotted by Tillmann Rendel. Checking back through my records, I found that Botje on #haskell had previously spotted the same issue, but at the time I hadn't noticed it was a security bug. The security implications of the bug are very low, and it could not be used to cause any real harm.

The Bug

The bug is that in the Hoogle web interface, user supplied data may end up being shown to the user without escaping. For example, searching for the number 1 results in an error message, which says "Parse Error: Unexpected character '1'". Unfortunately, in Hoogle 3, if that search string had been "1<u>2<u>", then the result would have been "Parse Error: Unexpected character '12'" - i.e. the number 2 would be underlined. If you try this same example in Hoogle 3.1, you do not get any formatting, and see the entered tags.

The bug could be provoked in several places:

The error message, on a parse error.

The input box, after a search had been entered.

As the string listed as what the user searched for.

To perturb the input box would require entering a quote character ("), and to perturb the other instances would require an opening angle bracket (<).

The Severity

I am fairly sure the severity of this bug is "incredibly low". As a result of entering a malicious query, the attacker could cause the page displayed to contain whatever was desired. However, the Hoogle online interface has no privileges beyond that of a normal web page, and so can't actually do anything evil. The bug does not permit any supplied code to be executed on the server.

There is only one malicious use I could think of: browser redirects. Sometimes evil companies will send out spam mail, with links such as "click here to go to example.com and order Viagra". One anti-spam measure is to reject all emails linking to a particular domain name. By crafting a URL, it was possible for a link to Hoogle to redirect to another domain, thus appearing that the initial link was to a trusted website. The spam recipient still goes to the original page, but it may defeat their spam filters.

Checking the server logs for Hoogle shows that no one ever actually exploited the flaw to perform a redirect, or even to insert a <script> tag - the first step to any such exploit.

The Fix

I had to make two fixes to the code. I use Haskell Source Extensions to generate most of the HTML shown in Hoogle. As part of that, I have a ToXML class that automatically converts values to an XML representation, which is then rendered. The ToXML instance for String did not escape special HTML characters, now it does. I wrote the ToXML instances, instead of relying on those supplied in the associated HSP, and thus introduced the bug.

The only other code that generates HTML uses a formatted string type, which can represent hyperlinks and various formatting, and can be rendered as either console escape characters or as HTML. Since this part of the code was written before moving to Haskell Source Extensions, it generates raw strings. This generating code was also patched to escape certain characters.

As a result of using libraries and abstractions, it wasn't necessary to fix each of the security flaws one by one, but to fix the interface to the library. In doing so, I have much more confidence that all the security flaws have been tackled once and for all, and that they will not reoccur.

Is Haskell Insecure?

Enhanced security is one of the many advantages that Haskell offers. It is not possible to overrun a buffer and conduct stack smashing attacks on a Haskell program. Passing query strings will not overwrite global variables, and escaping cannot cause user code to be executed on the server. However, when Haskell code generates HTML, it is not immune from code injection attacks on the client side.

In the beginning Hoogle did not use any HTML generation libraries. As I have slowly moved towards Haskell Source Extensions, I have benefited from better guarantees about well-formed HTML. By creating appropriate abstractions, and dealing with concerns like escaping at the right level, and enforcing these decisions with appropriate types, the number of places to introduce a security bug is lowered. Hopefully Hoogle will not fall victim to such a security problem in future.

Adding data files using Cabal

2008-02-28T00:02:00.000Z

Cabal is the standard method of packaging Haskell programs and libraries for release. One problem I've encountered more than once is that adding data files to a Cabal built project is not as easy as it could be. I'm not entirely sure why - having just added data file support to Hoogle, it wasn't excessively painful, but I still came out of the experience feeling slightly bruised. To help others (and my future self), I thought I'd write down the details while they are still freshly spinning round my head.

Let's assume we start with an existing Cabal project, with an associated .cabal file. In the root directory of the project we have readme.txt and data.txt. The readme file contains a basic introduction to the user, and the data file contains some data that the program needs to access at runtime.

We first modify the .cabal file to add the following lines in the top section:


Extra-Source-Files:
    readme.txt
Data-Files:
    data.txt

The Extra-Source-Files tells Cabal to put the files in the release tarball, but nothing more - for a readme this behaviour is perfect. The Data-Files section tells Cabal that the following files contain data which the program will want to access at runtime. Data files include things like big tables, the hoogle function search database, graphics/game data files for games, UI description files for GUI's, etc.

Now we have added the data file to Cabal's control, Cabal will automatically manage it for us. It will be added to the source tarball, and will be installed somewhere appropriate on the users system, following operating system guidelines. The only question is where Cabal has put the file. To figure this out, Cabal generates a Paths_hoogle module (change the project name as appropriate) which it links in with the program. The Paths module provides the function:


getDataFileName :: FilePath -> IO FilePath

At runtime, to find the data file, we can simply call getDataFileName "data.txt", and Cabal will tell us where the data file resides.

The above method works well after a program has been installed, but is harder to work with while developing a program. To alleviate these problems, we can add our own Paths module to the program, for example:


module Paths_hoogle where

getDataFileName :: FilePath -> IO FilePath
getDataFileName = return

Place this module alongside all the other modules. While developing the program our hand-created Paths module will be invoked, which says the data is always in the current directory. When doing a Cabal build, Cabal will choose its custom generated Paths module over ours, and we get the benefits of Cabal managing our data.

Cabal's support for data files, and extra source files, is very useful. It doesn't take much work to make use of the provided facilities, and it will help to ensure that users of your program on all operating systems get the style of installation they were expecting.

Safety and Optimisation: joinMaybes'

2008-01-26T15:33:00.000Z

In a recent blog post by Conal, he introduced the joinMaybes' function, defined as:


filterMP' :: MonadPlus m => (a -> Bool) -> m a -> m a
filterMP' p = (>>= f)
 where
   f a | p a       = return a
       | otherwise = mzero
 
joinMaybes' :: MonadPlus m => m (Maybe a) -> m a
joinMaybes' = liftM fromJust . filterMP' isJust

He laments that the use of isJust and fromJust mean that his code will run slower (having two Just tests), and that an automated checker such as Catch won't be able to check it successfully. Fortunately, Catch can check the code perfectly, and Supero can optimise the code perfectly. As such, this simple definition is perfectly fine from all points of view. I'm going to go through the checking with Catch in some detail, and if anyone wants, I'll post another article on the optimisation with Supero.

Checking With Catch

To simplify things, I'm going to work only in the [] monad, so here is a new variant of the code:


filterMP' :: (a -> Bool) -> [a] -> [a]
filterMP' p = concatMap f
 where
   f a | p a       = [a]
       | otherwise = []
 
joinMaybes' :: MonadPlus m => m (Maybe a) -> m a
joinMaybes' = map fromJust . filterMP' isJust

Catch would remove the dictionaries before starting, so would accept the original code unmodified. The first thing Catch wold do is reduce this fragment to first-order. The end translation would be:


filterMP_isJust x = concatMap_f x
concatMap_f [] = []
concatMap_f (x:xs) = (if isJust x then [x] else []) ++ concatMap_f xs

joinMaybes x = map_fromJust (filterMP_isJust x)
map_fromJust [] = []
map_fromJust (Just x:xs) = x : map_fromJust xs
map_fromJust (Nothing:xs) = error "Pattern match error"

I've also taken the liberty of inlining the otherwise, and used pattern matching rather than case expressions. Catch will take care of those details for us, but the code is a little easier to follow without them in. Now Catch can begin the checking process.

Catch first decideds that if map_fromJust is passed a list matching the pattern (Nothing:_), it will crash, and annotates the precondition of map_fromJust as being either the input list is [] or (Just _:_). It then spots the recursive call within map_fromJust, and determines that the revised precondition should be that the input list is a list, or any length, whose elements are all Just constructed (we call this condition P).

Having determined the precondition on map_fromJust, it uses that within joinMaybes. Catch transforms the condition P, trying to find the precondition on filterMP_isJust to ensure the postcondition P holds. By examining each branch, Catch determines that under all circumstances the postcondition will hold, therefore the precondition is just true. Given that filterMP_isJust always satisfies the precondition of map_fromJust, it is clear that joinMaybes never crashes.

Catch can generate the above proof automatically, showing the above function is safe.

Functional Flow Control

2008-01-25T14:37:00.000Z

In normal programming languages, there are many keywords for flow control, such as for, while etc. These flow control keywords encode a particular pattern of iteration, such as looping over a range (in the case of for) or continuing until some condition holds (while). Imperative programming languages continue to add more iteration keywords: both C#/Java have introduced some form of for-each; Python/C# have yield; Ada has many variants.

Haskell doesn't have these iteration keywords, but instead relies on recursion. This choice, when coupled with a few other Haskell ingredients, makes it much more powerful. Take for example the task of looping over a sequence, adding 1 to each element:


// In C
for (int i = 0; i < n; i++)
    list[i]++

-- In Haskell
incList (x:xs) = 1+x : foo xs
incList [] = []

I've used C mutating an array, and Haskell allocating a new list, simply because that would be the natural thing to do in each language. However, the great thing about higher-order functions is that we can now go back and abstract the flow control in Haskell, giving us:


incList = map (+1)

The above function maps over a list, incrementing each element. People have identified a common pattern (iterating over a list) and rather than baking it into the language with a keyword such as iterate-over-list, a library function can provide the operation. It is very important that map is not special in any way, and can simply be defined as:


map f (x:xs) = f x : map f xs
map f [] = []

The great advantage is that rather than being restricted to a limited range of flow control operators that someone somewhere decided upon, we can add new ones. Let's take another example, that of summing a list:


-- in C
int total = 0;
for (int i = 0; i < n; i++)
   total += list[i];

-- in Haskell
sum [] = 0
sum (x:xs) = x + sum xs

-- or using the built in foldl
sum = foldl (+) 0

In Haskell there is a standard library function foldl which iterates over a list using an accumulator, managing updates to the accumulator for you, and setting an initial value. In C there is no such operator, so the more general purpose for is used.

But these examples are very common, so C's for keyword has provided most most of the control flow. However, sometimes you need more exotic flow control, which the authors of the language did not think of including. Take the example of computing a fixed point of a function f on the value x:


int x;
while (1) {
   int x2 = f(x);
   if (x == x2) break;
   x = x2;
}

fix f x = if x == x2 then x else fix f x2
   where x2 = f x

Here the Haskell version shows its power, instead of having defined a particular instance for a particular f and a particular type of value x, in Haskell we have basically defined fix as a new form of flow control.

In C we were still able to define something, but it was much harder. Now consider the following example that I was working on yesterday. I have an algorithm which has 4 stages, lambda, simplify, inline, specialise. Each stage must be run in turn, but if any stage changes something, then we restart from the beginning. For example, we apply lambda, then simplify - if something changes we restart at lambda. We only finish once all the stages have been run without changing anything. In Haskell this code is simple:


fixList orig x = f orig x
   where
      f [] x = x
      f (a:as) x = if x == x2 then f as x else f orig x2
            where x2 = a x

fixList [lambda,simplify,inline,specialise]

I define a new function called fixList, which provides an abstraction of flow control. The actual operations have been well isolated from this structure. I considered how to express this in structured C and drew a complete blank. My best guess is:


int x, x2;

begin:
x = x2;

x2 = lambda(x)    ; if (x != x2) goto begin;
x2 = simplify(x)  ; if (x != x2) goto begin;
x2 = inline(x)    ; if (x != x2) goto begin;
x2 = specialise(x); if (x != x2) goto begin;

It might be possible to change some of this flow control into a macro, but I can think of no clean abstraction. Haskell is a great language for building abstractions, flow-control is just one highly useful instance.

PS: C Issues

Some of the code in this article isn't quite as nice as I'd wanted it to be, and isn't really a fair comparison. The array processing code in C relies on having defined n to be the length of the list, and having that tracked separately. The fixed point definition on C works over int to get a nice equality test, but that is merely a limitation of the language not having a standardized way to do equality. The C code could use function pointers, but in reality inline takes an extra argument so is used as a closure in Haskell - and besides, that would hardly be the standard way of coding C.

darcs Feature Request

2008-01-15T21:01:00.000Z

I use darcs all the time. I have 15 repos listed on my website, and at least an additional 10 that haven't made that list yet. The main reason I use version control is for syncronising files between the various computers I use (at least 4 on a regular basis). Of course, having the version control features available as well is an added bonus. I used to use CVS, and its Windows graphical companion, Tortoise CVS, which is a fantastic tool. However, as the Haskell community has migrated to darcs it has become more convenient to standardise on one single tool.

All my darcs repo's are available behind ssh (for pushing to) and behind http (for pulling from). So for example, to pull from the filepath library, I use the http accessible version:


darcs pull http://darcs.haskell.org/packages/filepath/

And to push my changes I do:


darcs push neil@darcs.haskell.org:/home/darcs/packages/filepath

The reason for pulling using http is that this operation doesn't require a public key to be active, doesn't fail if SSH is blocked (which it is in at least one of the locations I regularly visit), and is much quicker.

One feature of darcs is that it saves the last repo address used in a prefs file, so after typing the long darcs pull command the first time, in future I can just type:


darcs pull

Much handier! Unfortunately, if I then do a long-winded push command, it overrides the default repo, and future pull's would go from the ssh path. There is a solution, instead type:


darcs push --no-set-default neil@darcs.haskell.org:/home/darcs/packages/filepath

Ouch! Now that command line is getting a bit of a mouthful. As a result, I pasted this line into a file push.bat, and committed that to the repo. Now I can do the simple darcs pull and a push is as short as:


push

But this isn't ideal. It's a bit sad that one of the core Hsakell libraries contains a batch script which is platform specific and only works for people with shared keys on my Haskell account (which is now about 10 people...). I'd love to remove this script, which brings me on to...

Feature Request: have darcs allow a different default for push and pull commands.

One way of engineering this would be for darcs to store them entirely separately. Another option would for pull to use the last repo url, and push to use the last repo that wasn't http (since you can't usually push over http). There may be other options that will achieve the same effect.