## STM in Clojure vs Haskell, why no retry or orElse?

February 15th 2013

A few months ago I reread Simon Peyton Joneses article on STM in the Beautiful Code book and decided to try and translate it into clojures STM

See the paper here

He says ‘Atomic blocks as we have introduced them so far are utterly inadequate to coordinate concurrent programs. They lack two key facilities: blocking and choice’ so I guess the implication is Clojures STM is inferior, any thoughts?

I had to use a constraint on a ref and try/catch to get the same effect (though I hate using exceptions for control flow it does seem to work)

I think a better solution might be had using watchers, how would you do it?
Any good links explaining differences in the STMs?

``````(ns santa.core)

(declare join-group)

[fn]
(.start

(defn random-delay []

(def printer (agent 0))

[somestring]
(send printer println somestring))

(defn make-gate
[max-size]
(ref {:max-size max-size
:remaining 0}
:validator #(>= (:remaining %) 0)))

(defn pass-gate
[gate]
(try
(dosync (alter gate #(update-in % [:remaining] dec)))
(catch IllegalStateException e
(pass-gate gate)))))

(defn helper
(let [[in-gate out-gate] (join-group group)]
(do (pass-gate in-gate)
(pass-gate out-gate)
)))

(fn []
(random-delay)
(helper group #(work-fn id))
(recur))))

(defn deliver-toys [id]
(str "Reindeer " id " delivering toys")))

(defn meet-in-study [id]
(str "Elf " id " meeting in the study")))

(defn operate-gate
[gate]
(dosync (alter gate assoc :remaining (:max-size @gate)))
(while (> (:remaining @gate) 0)
))

(defn new-group
[max-size]
(ref {:max-size max-size
:remaining max-size
:in-gate (make-gate max-size)
:out-gate (make-gate max-size)
}
:validator #(>= (:remaining %) 0)))

(defn join-group
[group]
(try
(dosync (let [{:keys [remaining max-size in-gate out-gate]} @group]
(alter group #(update-in % [:remaining] dec))
[in-gate out-gate]))
(catch IllegalStateException e
(join-group group)))))

(def elf-group (new-group 3))
(def reindeer-group (new-group 9))

(defn handle-group [group group-name]
(let [current-group @group
{:keys [max-size remaining in-gate out-gate]} current-group]
(if (= 0 remaining)
(do (dosync
(ref-set group {:max-size max-size
:remaining max-size
:in-gate (make-gate max-size)
:out-gate (make-gate max-size)}))
(threadsafe-print (str "***** With" group-name "*****"))
(operate-gate in-gate)
(operate-gate out-gate)
true))))

(defn santa []
(while (handle-group elf-group "Elves"))
(handle-group reindeer-group "Reindeer")
(recur))

(defn -main
[& args]
(dotimes [i 9]
(do (println "Launching reindeer thread:" i)
(dotimes [i 10]
(do (println "Launching elf thread" i)
(santa))``````

February 4th 2013

This year I did the Facebook Hacker Cup again. I didn’t do as well as last year, only getting to the first round and solving just one problem. It was interesting and fun though. I was in position 1952 of about 10,000 with 877 people solving more problems than me. Lots of people solved just the 3rd question, I wish I had a go at it, next time I’ll be sure to look at them all.

Qualification Round
For the qualifier I was in Leeds so didn’t have much time to look at it but solved the first in a few mins as I had most of the ‘plumbing’ (ie taking their input and spitting out a file in the correct format) from last year.

Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it.
The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn’t care about whether letters are uppercase or lowercase, so that doesn’t affect the beauty of a letter. (Uppercase ‘F’ is exactly as beautiful as lowercase ‘f’, for example.)
You’re a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?

``````(def letters
(set "abcdefghijklmnopqrstuvwxyz"))

;; If you don't know clojure it might be interesting that sets are functions of their elements
;; and return either nil or the element, so can be used as predicates

(defn counts [s]
(frequencies (filter letters (str/lower-case s))))

;; Here we filter the string for letters we care about (after lowercasing it)
;; and create a map of the characters to there count in the string

;; eg (counts "Good luck in the Facebook Hacker Cup this year!")
;; {\a 3, \b 1, \c 4, \d 1, \e 4, \f 1, \g 1, \h 3, \i 2, \k 3, \l 1, \n 1, \o 4, \p 1, \r 2, \s 1, \t 2, \u 2, \y 1}

(defn beauty [s]
(reduce + (map *
(reverse (sort (vals (counts s))))
(iterate dec 26))))

;; To make the score as big as possible you want the most frequent letter to be worth 26
;; then each one descending by frequency is work 25, 24 etc
;; (reverse (sort (vals (counts s)))) it the frequencies in descending order
;; (iterate dec 26) is 26, 25, 24 etc
;; we multiply each and then add them``````

Round 1
I had the evening cleared from about 8pm (it launched 6PM GMT, so I probably lost before I started anyway after seeing how rapidly others did them!)

You are given an array a with N ≤ 10 000 different integer numbers and a number, K, where 1 ≤ K ≤ N. For all possible subsets of a of size K find the sum of their maximal elements modulo 1 000 000 007.

Easy! 1-liner in clojure.

``````(defn sum-max-of-subsets [cards k]
(reduce + (map #(apply max %) (comb/combinations cards k))))``````
(however it does not scale to the size of the input)

My basic idea to make it faster was using a bit of combinatorics. If the deck is [1,5,7,11...] (it’s not a coincidence I ordered them now) with a hand size (k) of 3 then 1 and 5 will never be the max, 7 will be in the hand [1,5,7] and 11 will be the max of [1,5,11] [1,7,11] and [5,7,11], in general the nth card will be maximum ${n-1\choose k}$ “n-1 choose k” times, so the problem becomes easier, loop thorough the elements finding out how many times it would be the maximum. See here if that does not make sense.

``````(def factorial
(memoize (fn [n]
(reduce *' (range 1 (inc n))))))

(defn nCks [k]
(let [fac (factorial k)]
(map #(/ % fac)
(reductions (fn [acc n]
(* acc (/ n (- n k))))
fac
(iterate inc (inc k))))))

(defn sum-max-of-subsets [cards k]
(let [sorted (drop (dec k) (sort cards))
nck (nCks (dec k))]
(mod (reduce +'
(map * sorted nck))
1000000007)))

(defn bigparse [s]
(bigint (Integer. s)))

(defn parse-input [line1 line2]
(let [k (bigparse (second (str/split line1 #"\s+")))
cards (map bigparse (str/split line2 #"\s+"))
]
(sum-max-of-subsets cards k)))
``````

The final speedup (probably not necessary) was as k is fixed we dont need to calculate nCk every time so I used the Multiplicative Formula for calculating it to get a new value for ${n\choose k}$ from ${n-1\choose k}$ by multiplying by n and dividing by n-k each time (what I have called nCks in the code)

For the other problem I groped around the next day trying to solve it, thought ‘this looks perfect for core.logic’ then proceeded to procrastinate and watch The Shield and eat bacon. I am OK with this.

Code is of course on github

Posted by tom under clojure | No Comments »

## Sorry, command-not-found has crashed!

December 12th 2012

Whenever typed a command that didn’t exist on some of our servers I got the following

```\$ poop
Sorry, command-not-found has crashed! Please file a bug report at

Please include the following information with the report
command-not-found version: 0.2.44
```

It turns out that it was to do with locale settings, I fixed it by

```\$ sudo locale-gen en_GB.UTF-8
\$ sudo update-locale LANG=en_GB.UTF-8
```

Posted by tom under linux | No Comments »

## Solving 4clojure problems offline in emacs

November 14th 2012

It annoys me when sometimes a solution to a 4clojure problem gets a bit long to type and test in the little edit box. As they say it is not an IDE, and doesn’t try to be, so I wrote a little app that fetches the problems down via the api and wraps the tests up in an assertion so you can edit it in emacs or whatever, run the tests in lein and submit to 4clojure when you are done.
It’s on Github, probably more useful for the harder ones.

As an example, below is my soln to #73 using it, I can run it with
# lein run -m offline-4clojure.p73

``````; Analyze a Tic-Tac-Toe Board - Hard
; A <a href="http://en.wikipedia.org/wiki/Tic-tac-toe">tic-tac-toe</a>
; board is represented by a two dimensional vector.
; X is represented by :x, O is represented by :o, and empty is represented by :e.
; A player wins by placing three Xs or three Os in a horizontal, vertical, or diagonal row.
; Write a function which analyzes a tic-tac-toe board and returns :x if X has won, :o if O has won, and nil if neither player has won.
; tags - game
; restricted -
(ns offline-4clojure.p73
(:use clojure.test))

(def __
(fn [board]
(let [triples
(fn [board]
(map #(map (partial get-in board) %)
(concat
(for [x [0 1 2]]
[[x 0] [x 1] [x 2]])
(for [y [0 1 2]]
[[0 y] [1 y] [2 y]])
[[[0 0] [1 1] [2 2]]
[[0 2] [1 1] [2 0]]])))]
(ffirst (filter #(or (= [:o :o :o] %)
(= [:x :x :x] %))
(triples board)))))

)

(defn -main []
(are [x] x
(= nil (__ [[:e :e :e]
[:e :e :e]
[:e :e :e]]))
(= :x (__ [[:x :e :o]
[:x :e :e]
[:x :e :o]]))
(= :o (__ [[:e :x :e]
[:o :o :o]
[:x :e :x]]))
(= nil (__ [[:x :e :o]
[:x :x :e]
[:o :x :o]]))
(= :x (__ [[:x :e :e]
[:o :x :e]
[:o :e :x]]))
(= :o (__ [[:x :e :o]
[:x :o :e]
[:o :e :x]]))
(= nil (__ [[:x :o :x]
[:x :o :x]
[:o :x :o]]))))``````

Posted by tom under clojure | No Comments »

## 101 Goals In 1001 Days – Retrospective

October 26th 2012

Well, I guess this could be considered an early 2012 retrospective as this is my first blog post this year (so much for the goal of doing one a week, a goal I am not sure is actually all that worthy to be honest)

Firstly, about the 101 goals in 1001 days. I am so glad I did it, just the act of thinking about what you want to achieve is worthwhile, putting a time limit on it so it’s not a bucket list for someday but a list of things you are seriously going to try achieve in a few years. The 1001 days is interesting, short enough to feel some pressure but long enough to have a few of each season for anything that is time sensitive.
I think I was a bit ambitious with my list, though I always knew it was a reach I probably bit off more than I could chew. That said the list was formed when I was single and freelance and I would not swap either the last few years at my job (still at Forward) or with Petra for a few more goals ticked.

Before I go through them all I just want to say the most transformative thing of the whole 1001 days has been this year, in particular running and the impact it has had on my fitness.
When I talked about the 101 goals lots of people got excited but everyone kind of did a double take when they saw I was doing a marathon, I think they did not believe I could (and I can’t blame them, I’ve never been super-fit and was in my worst shape ever). I started in Jan with the NHS Couch to 5k and then an excellent training schedule provided by Oxfam as I was entered into Edinburgh for them in May. I trained really hard for it as you can tell from the runkeeper stats, 88,365 calories – 592.2 miles and active for nearly 6 days in total!

The purple in May is when I started biking after not having a bike for 15 years or so and unfortunately I came off it a few days before the marathon and broke my arm and dislocated my shoulder. I was so ready and had raised so much for Oxfam that I thought I had to do it so (after being dissuaded from duct taping my arm still) I decided to walk it, and finished just in time for medals!

So that went well but I was unable to train for quite a while and missed the chance of doing a triathlon this year.

I used my new fitness level to try and climb every 3000ft mountain in Wales in a continuous walk on a weekend when a months worth of rain fell in a day and we had 40mph winds, managed 11 of them.

After going on a safari in Kenya with Petra, my sister Carrie and my Mum (which Carrie captures perfectly here I met my friend Colin (who I have known since the first day of primary school, actually not the only friend I can say that of I am lucky to have a few) in tanzania and we climbed Kilimanjaro. It was the hardest thing I have ever done, but not in a satisfying way, the typical kili trip does not allow enough time to acclimatize and your resistance to altitude is largely genetic and it’s quite a dirty and busy mountain. Glad I did it? Yeah, proved I have some serious resolve. Would I recommend? No, there are nicer challenges that reward preperation more and are cleaner and more beautiful. Maybe I should say more but a portered trip walking only 5h a day and going too high too quickly does not compare to the Alps or even UK hill days. Maybe it’s still too soon and retrospective pleasure has not kicked in yet but I am sure I’ll stand by it.

The week after I did the Liverpool marathon too, basically I thought it was a toss-up between the red blood cells from kili and a twisted ankle how well I would do but in the end I had just not got enough long runs in and my quads packed in at 22 miles and I needed to walk a bit.
Me and Carrie, who apparantly I inspired to enter the marathon (though she beat me by 15 mins!)

The founding members of the Bread Wine and Cheese Athletics association crossing the line together then finishing the goodies we took along with us.

I’m still raising money at justgiving.com/tommys-final-push for WarChild. All money donated is doubled by Forward next week so every penny counts twice!

So, smashing it this year but how did I do overall? Dayzero has me on 42 complete. I am quite pleased but have decided to extend to the end of the year and try and tick a few more off, not least so I can have a finishing party. My goals, my rules after all

I will be doing another 101 goals, building up to swimming the Helespont and doing an ironman (quite a reach as I can’t swim at the moment!)

What would I change? Blog more about it, involve more people, have as much drive as I had this year for the whole period.

I am really please to have encouraged half a dozen others to start lists.

Done (42)
1, Teetotalitarianism for 3 months
2, Cheeseless for 3 months
48, Create a Backblaze storage pod
53, Make Jam
66, Via Ferrata in Italy
78, Learn to use Emacs
82, Visit Egypt
83, Re-visit Louvre
85, Visit Pergamon Museum
86, Give Carrie a British Museum Tour
92, Read “An Ode Less Travelled“, do the exercises (but not share them!)
97, Be 1/3 through in 2010
100, Set success criteria / progression metrics for each goal
5, Lose 2 stone
10, Write book reviews for each book I read\
76, Do on average 1 Project Euler problem per week
88, Go to the theatre on average once a month
44, Visit The Uffizi in Florence (was Get CCEE)
61, Do a UK long distance path
3, Do a marathon
24, Swim with sharks
73, Make a Dots and Boxes program
79, Raise £5005 for charity
39, Take Mum, Dad and Carrie to the Welsh Mountain Zoo
56, Make beer
51, Investigate Visa situation for Australia
52, Investigate Visa situation for US
54, Grow mushrooms
32, Bungee Jump
34, Vineyard tour
96, Let loans run course and don’t get any more
64, Climb a continental highest mountain
33, Safari
20, Organise a big bash for my 30th
84, Revisit Met Museum
31, Hire the whole of Salvos Salumeria for an evening

Attempting before Christmas (23)
13, Release 303 books on bookcrossing.com
68, Complete Pimsleur German
74, Read AI: A Modern Approach
75, Watch SICP, do exercises from book
91, Memorise 10 poems
46, Listen to Radio 4 / British Museum – A History of the World in 100 Objects and view each of them (was Get VCAP)
7, Write an article for Plus new writers
14, Read a short story for librivox
16, Send Dennett a letter
17, Send Dawkins a letter
23, Organise all my DVDs
38, Take dad to an opera
58, Cook a 4 course meal for 20 friends
55, Paint a watercolor
57, Make wine
71, Learn 10 magic tricks
80, Talk about Free Software at a school
87, Go on wine tasting course
99, Have a completion party

Abandoned / Failed (36)
67, Do another alpine 4000m peak
19, Blog on average once a week
50, Move 10 people to FreeAgent
95, Pay off all credit cards
81, Watch all TTC Art history DVDs
90, See all world heritage sites in the UK
43, Visit the rijksmuseum (was Get CCNP)
45, Give blood every 20 weeks (was Get MCITP – Enterprise Admin)
47, Make a Munro bagging site in Rails (was Say to a recruiter “I dont work ” and turn down work)
60, Hike on average once a month
62, Do a big hike in Europe
35, Visit 5 Michelin 3* restaurants
37, Visit porto
94, Go to Edinburgh festival
4, Do a triathlon
6, Attend martial arts classes for 3 months
22, Spend 3 months in another country
25, Paraglide
26, Learn to play bongos
27, Skydive
29, Do a banger rally
30, Have a track day
36, See Northern Lights
40, Do 1000 things in London
41, Do a standup comedy course
42, Visit Japan
49, Work only 100 days in a year
59, Do a photography course
63, Attend NIM
69, Learn to dance
70, Learn to play golf
93, Go to Melbourne Comedy Festival
65, Volunteer for the mountain bothies association
98, Have done 2/3 by day 666

Posted by tom under 101 | 3 Comments »

## Forward Vegas 2011

January 8th 2012

One again Forward took all its staff to Las Vegas for the Christmas party, cheers Neil!

We stayed at the Wynn again.

Beautiful view from my room

On the first day we went carting.

The final day I went to do a skyjump off the Stratosphere (have a DVD I’ll upload when I find it)

Between that some drinking and gambling…

Random head coming out of the lake in the Wynn

Then home!

Posted by tom under travel | No Comments »

## Day 700 of 101 goals in 1001 days

December 22nd 2011

This update is late as I have been busy.

84 – Revisit Met Museum
Went while I was at Hadoop World (pic is actually the Natural History museum but what the hell)

During my recent Africa Trip:
24 – Swim with sharks

33 – Safari
Visited Addo Elephant Park during my recent South Africa Trip

34 – Vinyard tour
I visited the boekenhoutskloof vinyard in Franschhoek South Africa

I’ll do a full write-up of the Africa Trip soon, it was amazing.

So now out of the 101 I have done 24 with 18 on track and only 300 days to go! Need to get a shift on and tick off as much as I can.

The dayzeroproject site is back up, I am on there as thattommyhall

Posted by tom under 101 | 2 Comments »

## Reith Lecture by Aung San Suu Kyi

June 28th 2011

Today I woke up to Radio4 as usual and was surprised to hear this years Reith Lecture by Aung San Suu Kyi on Securing Freedom. Very interesting, looking forward to hearing the remainder

The archive is available and I thought I would share my highlights:

Posted by tom under random | No Comments »

## Walking The Great Glen Way

June 26th 2011

Over Easter, while we had all the extra days off because some chinless wonder married a model in an old church in London I went with two of my best friends and walked the 73 miles from Inverness to Fort William along the Caledonian Canal.

(picture from Wikipedia)

We did it ultralight, using kit I have blogged about before. My mate Ben got well into expedition planning mode and prepared an optimal food mix for the trip and introduced us to SCROGIN (Sultanas Chocolate Raisons Orange Ginger Imagination Nuts) and ANZAC biscuits (his lovely other half is a kiwi).

I was pleased to fit it all in a 30L sack, made the walking much easier than it might have been.

As I had just been in Lisbon for a stag do the weekend before I was not feeling 100% when we got the sleeper to Inverness on the Monday night but we arrived somewhat fresh and started walking immediatly. The sleeper is really nice and I would deffinatly recommend it over flying if you need an early start in Scotland, see ScotRail. By the end of Tuesday we had got most of the way to Invermoriston (nearly 30 miles) but were all exhausted. We wildcamped with some stunning views.

The Wednesday we walked to Fort Augustus and decided to take a B&B for the night as non of us had slept well and our legs and feet were killing. We were fortunate enough to stay at Old Pier House which was lovely and we got moving again on the Thursday with much more enthusiasm than we ended the day before.

Thursday night we got past laggan and camped at a campsite on the north of Loch Lochy.

Friday was an epic day, taking in the 2 munros ( Meall na Teanga and Sròn a’ Choire Ghairbh and walking about 25 miles then (we thought) finishing the walk.

We had actually just reached Neptune’s Staircase and we wound up bivvying at the start line of Maggies Monster Bike and Hike. We must have looked quite odd…

We spent the first few hours of the Saturday finishing it off and arriving at Fort William where we ate the biggest amount of food we could.

A great hike with 2 great guys and as it is a UK long distance path it is another of my 101 goals in 1001 days days ticked off

Posted by tom under 101 & hiking & scotland | 1 Comment »

## Berlin Buzzwords

June 9th 2011

I have just returned from Berlin Buzzwords. It was a great conference and well organised so thanks to the organisers.

As all the talks will be online soon I will just mention a few things that I enjoyed.

The two keynotes were excellent, Doug Cutting on the history of Hadoop and Ted Dunning on the future. Both were very interesting and had a great feel for the community aspect of Open Source software. Ted works for MapR technologies but the talk was not a sales pitch. Ted spoke about how Hadoop fails currently to get the most out of the components and what we might get if we could. MapR are used by EMC for their new Hadoop distro, among other things I think they have reimplemented HDFS. An interesting number of companies had got some pretty big amounts of funding to build front-ends to Hadoop, DataMeer have an excel-like web frontend that looks interesting.

Talks I enjoyed were:

NODE.JS FOR HEAVY I/O
A superb intro to Node.js, with an example small enough to fit on a slide but not completely trivial.

TIME SERIES OR CAUSAL ANALYSIS WITHOUT LIMITS!
Shivek was awesome, engaging and enthusiastic. The topic itself was fascinating, using
Pi Calculus to reason about and design map/reduce algorithms. He made the point that most Hadoop jobs are datacentric but showed how to do some more mathscentric algorithms like FFTs

OH LEONHARD, WHERE ART THOU?
Jim Webber on graph databases in general and Neo4J in particular. Quite a nice reference to Euler in the title. If your data is a graph, why not have a database that is too?

From Jonathan Gray, this talk was really interesting – amazing the throughput they are getting from HBase. I think Forward are more like Facebook than Google (more freedom within teams, choice of tech/roll your own vs Google wanting everything on BigTable. I cringed a bit at the thought of loads of servers running random C++ apps all over the place though…)

NEWER DEVELOPMENTS IN LARGE DATA TECHNIQUES
Joseph Turian from MetaOptimise gave a great overview of recent academic work on Machine Learning and Natural LAnguage Processing, buzzwords to look out for are: Deep Learning, Semantic Hashing and Semantic Parsing. Also look at GraphLab, Machine Learning on graph databases

DIGITISED DUTCH CULTURAL HERITAGE, MAHOUT & HADOOP
COMPOSING MAHOUT CLUSTERING JOBS
Two good talks on using Mahout, the first is on a Dutch Gov project, Images for the future to archive and categorise AV heritage resources. The second had a nice demo of categorising stack-overflow.

Lightning Talks:
The Lustre filesystem from Eric Barton of Whamcloud talked about how his company are developing Lustre outside Sun/Oracle and he was trying to see where it could fit in with Hadoop. Luster is the other end of the spectrum from HDFS/Hadoop, really quick but assuming fast, highly available storage behind it. I would love to see some integration with Lustre or Ceph in a Hadoop-like system.

I gave a talk on the Flume Firehose Abs and I made at Forward last week, it was OK (though I still think no-one has done a good job of selling ZeroMQ in 10 minutes!). Slides are here (I’ll do another post about it as well, quite an entertaining fallout from it over twitter.)