Sneaky Mustard

Long time no blog… I figure I’d just post a list of books I want to eventually buy and read. In fact I would have bought them already, but Amazon charges US$60 for shipping it all. Considering the books would cost US$130 it’s kinda expensive… Anyway, here’s the list, in alphabetical order. Anyone read any of these?

• Amulet
• Anathem
• By Night In Chile
• Choke
• Cryptonomicon
• Distant Star
• On the Road
• Slaughterhouse-Five
• Survivor
• The Alienist
• The Stories of Vladimir Nabokov
• Tristessa

 Edit: Oh well, I just went to the bookstore during lunch time and bought the ones struck above, and also Ficciones, El Aleph and La Pista de Hielo. I’m hoping that since the originals are in Spanish, the portuguese translations won’t be too horrible.

Edit 2: What the heck, I am such a consumist… More titles struck, as I figured buying them here ends up being cheaper, even if the books are more expensive, because shipping costs 6 times less. Also, more books to the Bolaño collection which weren’t on the list: Last Evenings on Earth and Nazi Literature in the Americas.

I’m currently reading 2666 and loving it, although I’m just about 100 pages in (of more than 900).

Today I created a new repository for a project I’ve been working on since last week, OSpec Behavior-Driven Development library for OCaml, inspired on RSpec. I started doing this to learn about Camlp4. Camlp4 lets you extend OCaml’s syntax, so I managed to create something that is quite similar to RSpec’s API, but still allowing it to be mixed with OCaml code.

Here’s a simple example of how it looks:

describe "The number one" do
  it "should equal 2 when added to itself" do
    (1 + 1) should = 2
  done;

  it "should raise when divided by 0" do
    let f = fun () -> 1 / 0 in
    f should raise_an_exception;
    f should raise_exception Division_by_zero;
    f should not raise_exception Exit
  done
done

From this it should be clear how Camlp4 is powerful. The should syntax is not native to the language, and it wouldn’t be possible to use it without a system like this. It even looks clearer than RSpec’s DSL, since we don’t need the dots and parenthesis that reduce the "english-like readability" of the domain-specific language.

I have to admit that the code I wrote is pretty ugly. As I mentioned in the announcement I made to the OCaml mailing list, it’ll make your eyes bleed. It relies on global variables, does not hide internal variables and functions and has quite a lot of repetition. The main reason for that is that I still don’t know how to do otherwise. Camlp4 went through a lot of changes for OCaml 3.10, and the new version seriously lacks documentation. Anyway, ugly or not, the code works, and since there was a question about what BDD library people used in OCaml this week on the list, I decided to make it public in its current form. I hope it’s useful for someone.

I have a small number of open source projects, neither of which can be considered extremely popular. They are all small wrappers or libraries that I wrote for something I was working on, and I never thought they’d actually have any real users besides me. This week, though, I had two nice surprises. One of them was that the OCamlFd library I wrote at work not long ago was mentioned this week on the Caml mailing list. The other was that I received a patch to implement TLS support on my Ruby/ManageSieve library.

I think this speaks a lot for the open source model of development. The feeling of having written code that was actually useful for other people that I don’t even know is awesome, and getting feedback in the form of code improvements is even better. This would never be possible for closed source code. I would never have implemented the TLS support for ManageSieve that I mentioned above myself, because I have no need for it, and I don’t even have where to test it. Moreover, the patch would not have been written if the source was not open, and its author would probably have to write his own library from scratch.

As a side note, I have decided to move some of my projects’ repositories to github. Git is a fantastic tool, and github allows me to keep my repositories at the same place. Check them out and send me patches!

16:30 <@andre> is 2009 looking good so far?
16:30 < arun> yes
16:31 < arun> but it smells bad
16:31 <@andre> LOL

This afternoon I was talking to gatz on #bsd about the origins of the name "Sneaky Mustard"… All the credit goes to phi, back in 2004:

13:24 <@andre> but there’s a reason it’s called sneaky mustard
13:25 <@andre> one day i complained about not being able to find something
13:25 <@andre> and phi said "just like mustard"
13:25 <@andre> and i was like "huh?"
13:25 <@andre> and he said he can never find the mustard in his fridge when he
               wants it
13:25 <@andre> so, sneaky mustard :p
13:26 < DaGr8Gatzby> Lol
13:26 < DaGr8Gatzby> hahaha shit that’s fuckin classic

The other day I  implemented the Fisher-Yates Shuffle in Haskell. The algorithm is pretty simple, but writing it in Haskell was a challenge, because I had to work with the ST monad (more specifically STArrays), which I had never done, in order to write an efficient version (Haskell’s immutable arrays are simpler to use but wouldn’t work very well because of the copying needed on every update), and not only that, but also combine it with the State monad using a monad transformer, because the shuffling algorithm requires a random number generator, and the State monad is useful to keep it updated without the need for extra parameters in functions.

These are the modules we’ll use:

> import Control.Monad.ST
> import Control.Monad.State.Strict
> import Data.Array.ST
> import Data.Array.IArray
> import System.Random

The first function we need is one that swaps the elements of an array, given their indices. The code is straightforward, and the only thing worth mentioning is that since we’re using an STArray, the function has to be in the ST monad. Here’s the code:

> swap :: STArray s Int a -> Int -> Int -> ST s ()
> swap arr i j = do
>   x <- readArray arr i
>   y <- readArray arr j
>   writeArray arr i y
>   writeArray arr j x

The next step would be the main action of the shuffling algorithm, which is selecting a random array index and swapping it with the current upper bound on the array indices. This is where our need for the State monad transformer (StateT) appears. We need to keep our random number generator in the State monad, and also use the ST monad for the array operations. So we define a type synonym that represents that:

> type ShuffleT s a = StateT StdGen (ST s) a

This simply means we’re using the State monad to store an StdGen and that ST s is our inner monad. Computations of this type require a parameter of type s, which is required by the ST monad, and one of type a, which is the type of the return value of the computation.

Now we need a function that will give us a random array index, that is, an integer in some range delimited by the function’s parameters. Since we’re using the State monad, we’ll retrieve and update the random number generator using the get and put functions to access this implicit parameter.

> randomInt :: Int -> Int -> ShuffleT s Int
> randomInt lb ub = do
>   g <- get
>   let (r, g') = randomR (lb, ub) g
>   put g'
>   return r

With that, we can write the function that does the random swapping very simply:

> swapRand :: STArray s Int a -> Int -> Int -> ShuffleT s ()
> swapRand arr lb ub = do
>   r <- randomInt lb ub
>   lift $ swap arr r ub

Note that we can call randomInt directly, because the State monad is the outer monad in our stack, but we need to lift the result of swap, because it’s in ST, our inner monad (I guess calling it "upper" instead helps understanding the purpose of lift, if you consider a pile of stacked monads, with State at the bottom and ST at the top).

Finally, we can write the main function, which simply calls swapRand multiple times, each time decrementing the upper bound parameter until every element has been swapped. I’ll call it shuffle’.

> shuffle' :: STArray s Int a -> ShuffleT s (STArray s Int a)
> shuffle' arr = do
>   (lb, ub) <- lift $ getBounds arr
>   mapM_ (swapRand arr lb) [ub, ub-1 .. lb]
>   return arr

Note that the return type now is ShuffleT s (STArray s Int a), because we’re in ShuffleT and want to return an STArray. We use mapM_ with a decreasing range for the upper bounds, and apply each one to the partial application of swapRand to its first two arguments. Once again we have to lift the return value of a function that lives in the ST monad, this time getBounds.

The last step is getting the shuffled array out of the ST monad. Here I’m assuming that the array won’t be modified by the rest of the program, so we’re given an immutable array as an argument, convert it to a mutable array, shuffle it, extract it from StateT (ShuffleT in our case), freeze it, and finally extract it from ST. The array needs to be frozen in order to be extracted from ST, to avoid the mutability of the array to "escape" to the pure world. Credit for this wrapper goes to Ryan Ingram, who kindly explained this to me in Haskell-Cafe. The function also returns the modified random number generator for further use in the program. Here it is:

> shuffle :: Array Int a -> StdGen -> (Array Int a, StdGen)
> shuffle arr gen = runST $ do
>   stArr <- thaw arr
>   (stArr', gen') <- runStateT (shuffle' stArr) gen
>   arr' <- unsafeFreeze stArr'
>   return (arr', gen')

And that’s it! The only hard function, in my opinion, is shuffle, the wrapper around shuffle’. It’s not hard in the sense that the code is hard to follow, but you have to understand what needs to be done to get stuff out of the ST monad. Knowing that, it’s actually pretty simple.

Out of boredom, I wrote a daemonize function in Haskell, following the steps in Advanced Programming in the UNIX Environment. Here it is:

module Daemon where

import System.Directory
import System.Exit
import System.Posix.Files
import System.Posix.IO
import System.Posix.Process
import System.Posix.Signals

daemonize :: IO () -> IO ()
daemonize f = do
  omask <- setFileCreationMask 0
  pid <- forkProcess child
  exitSuccess

  where

    child :: IO ()
    child = do
      sess <- createSession
      ohandler <- installHandler sigHUP Ignore Nothing
      forkProcess grandChild
      exitSuccess

    grandChild :: IO ()
    grandChild = do
      setCurrentDirectory "/"
      devNullFd <- openFd "/dev/null" ReadWrite Nothing defaultFileFlags
      mapM_ (closeAndDupTo devNullFd) [stdInput, stdOutput, stdError]
      f
      where
        closeAndDupTo dupFd fd = closeFd fd >> dupTo dupFd fd


I’m collecting a list of movies that I want to watch, mostly taken from this thread at Netphoria. I thought I’d post the list here just in case anyone has seen any of these and wants to share a comment. Here’s the list, in no particular order:

• Let the Right One In (Låt den rätte komma in)
• RocknRolla
• Slumdog Millionaire
• Appaloosa
• Komm, süsser Tod
• The Wackness
• Man on Wire
• Dogville
• Good Bye Lenin
• Goodfellas
• Gone Baby Gone
• Girl, Interrupted
• The Magdalene Sisters
• Bittersweet life (Dalkomhan Insaeng)
• Edge of Heaven (Auf der anderen Seite)
• The Visitor
• Miller’s Crossing
• High Fidelity
• 21 Grams
• The Darjeeling Limited
• Blow
• 25th Hour
• London
• A Good Year
• The diving bell and the butterfly (Le scaphandre et le papillon)
• La vie en rose (La Môme)
• Juno
• Happiness
• 13 Tzameti

Edit: Added a few more:

• Tideland
• Gegen die Wand
• Donnie Brasco
• Traffic
• Control
• Jackie Brown
• Before the Devil Knows You’re Dead
   

I’ve just set up a microblog for Sneaky Mustard at micro.sneakymustard.com. This will be a simple collection of random pictures and quotes that I happen to find. I’m using Asaph as the microblog engine, and it’s really awesome.

09:03 < rand_acs> I think andre has alienated his usual audience with that post