Looking Out To Sea

Help, trapped in a cycle of not blogging that won’t stop. So many things that I have been enjoying that I want to mention, but that I can’t really bring to mind right now, and certainly not in an interesting fashion. Which means, a list!

• I bought myself a Kindle (third generation, but just wifi, not 3G) for reading stuff. In the first couple of weeks I was commuting by train and reading academic stuff. Since then I’ve been getting a lift and just reading for pleasure — which means a sub-list!

  • Bram Stoker’s Dracula: It’s strange reading a book that basically started a literary and cultural genre. I mean everything from Hammer Horror to Buffy, Twilight to Anne Rice has sprouted out of this book. It wasn’t the origin but it is by a long way the most famous Victorian vampire novel and it was interesting to see how much has been around from the start. The book is told in diary form, using snippets from the journals of Jonathan Harker, Abraham van Helsing as well as newspaper reports and other sources to “piece together” the story for the reader. It’s very effective and remarkably tense. My favourite scene is definitely the arrival in England of Count Dracula, told via newspaper clippings and the log kept by the captain of the ship that carried him. Sadly the part of Van Helsing, which gets more prominent as the book continues, is really badly written. I have never seen a worse depiction of a foreign speaker of English, it’s at least as bad as any Hammer Horror Dracula!
  • Robert Louis Stevenson’s Kidnapped: I remember reading Treasure Island when I was younger (and I think I’ll re-read it soon) but couldn’t recall if I’d ever done this one. It was really enjoyable and the kind of thing I would have definitely enjoyed as a child. Non-stop adventure from the start.
  • Jonathan Swift’s Gulliver’s Travels: There have been so many awkward adaptations of this (or at least the Lilliput part) that it’s another strange one to read in its entirety. I quite liked the Ted Danson adaptation and from what I can remember it was fairly faithful to the parts Swift wrote, while including a lot of other stuff about Gulliver’s struggles to adapt to English society on his return. The first half you can read without much awareness of the political/satirical nature but it reaches a point where suddenly the author starts putting the boot in to “civilised society” and doesn’t really let up until the end of the book. Eminently readable, though if you find a copy riddled with footnotes I would abandon it immediately. The first copy I tried to read seemed to have more superscript letters than normal ones, and that really makes it a chore.

  As you can see I’m working my way through all the free stuff available, of which there is a substantial chunk on Project Gutenberg. Recommendations for classics are always welcome. Some authors are obviously well-represented but it would be nice to know if there are any books in particular that people think I should investigate.

• Capoeira is continuing — I’m even beginning to enjoy the roda on Sunday, which I’m trying to attend as often as I can. I’ve started going to the training twice a week most weeks. Getting a job really put paid to the amount of effort I can devote to training/exercise in my own time. But it’s getting much warmer these days so maybe I can get the grass cut outside so we can practise in the garden. Last week I was even practising on the Meadows. Who knows whether people were laughing or just didn’t notice/care… most probably the latter.
• I made a big batch of baguettes the other day, for a sandwich-based birthday party, and was complimented from many quarters. But then people will sell you their children if you provide fresh bread sandwiches!
• I haven’t done any SICP study since I started working again but I’ve just got in touch with my co-conspirators and we’ve agreed a meeting date, which might just be a chance to catch up socially but will hopefully lead back to studying and learning again.
• Of course now I’ve started a list I’m obliged to add enough entries to make it worthwhile, but I can’t think of anything else. How have you been?

Well, it’s been a while since I wrote in this little box. My new job continues to form and my commute has been easier lately, since I’ve been getting a lift from a colleague who also lives in Edinburgh. I get back home in the evening much earlier, which is nice, though the start is still as early as ever (the alarm goes off at 5.30).

But I didn’t break this hiatus to talk about commuting, I promise. Last week was PyWeek, a twice-yearly programming challenge to write a computer game in the Python programming language. Nick was keen to give it a go, so between me, him and Mat we concocted an idea which was just interesting enough that it might be worth playing.

Due to some unforeseen problems we didn’t get much time to write code, so the game didn’t really come together in time for the deadline. I think, in fact, that the code was broken as zero-hour ticked over. Oh well.

Having started we decided to finish, so we all met on Monday night (for the first time since the challenge started…) and got large chunks of the game completed. It’s now playable, I think, though outrageously taxing and quite awkward for one person to play against themselves. The plan, then, is to iron out some of the kinks and see if we can pitch the difficulty at just the right level to make it addictive. Maybe we’ll get it transferred to an Android/iPhone app in the future?

I’ve known these guys for years but we’ve never actually sat down and written a program together for the fun of it. It was really interesting, especially since we were all basically learning Python from scratch for the purpose, and I was trying to remember what all this OO stuff is supposed to be about. Maybe we’ll tackle it again for the autumn PyWeek with a new game idea, more experience and maybe a bit more time scheduled to the task.

I’m in a new job. I’ve done one week, so my life has mostly been on hold while I work out how things will fit together. I’m working for Honeywell Security writing embedded software. Similar to before but in alarm systems instead of networking.

The job requires a hefty commute — at least two hours each way if things go well, but between delayed trains and poor weather it’s sometimes an extra half hour on top of that. Which means I get up at 5.30, leave the house before 6.30 and get home in the evening around 7 o’clock. You can see why the rest of my life has been a bit quiet. I’m having to rethink how I look at the week. The arrival of the weekend is important and precious!

I’m still learning the ins and outs of work but the people are all very friendly and helpful, which makes the travelling more bearable. Spending hours travelling to and from a hateful job would be horrible. I spend an hour on the train each way which has given me more time for other things. I’ve been splitting my travelling activities, so that in the morning I read the freebie Metro for a bit and then do some “thinking” to limber up for the day. Recently I’ve been doing simple program calculation exercises, deriving the fusion rules for fold/unfold or map/map and so on. I’m really interested in the idea of deriving correct and efficient programs from executable specification.

(Just to show you what I’m talking about, this is the fold/unfold fusion rule. Let us say there are two functions, foldr and unfoldr defined as follows:

foldr f z     [] = z
foldr f z (x:xs) = f (foldr f z xs)
 
unfoldr g s = case g s of
                Nothing     -> []
                Just (x,s') -> x : unfoldr g s'

The function foldr combines a list of elements according to the function f and unfoldr creates a list of elements from the seed s. We might use foldr to define a product function which combines the elements of the list by multiplying them together:

product = foldr (*) 1

And we might create a list of elements from 1 to n with an unfold.

enumTo n = unfoldr step 1
  where step s = if s>n then Nothing else Just (s, s+1)

The observant reader will have noticed that combining these two separate functions will give us factorial, the product of numbers from 1 to n — first we create the numbers 1 to n, then we multiply them all together.

factorial = product . enumTo

The inefficiency is that enumTo works on producing a list which is consumed by product. The elements are inserted into a list only to be removed straight away. Can we omit the redundant list production? It turns out we can, and we can do it for all cases where foldr operates on the result of unfoldr. The product and enumTo are specific instances of a general method which we can use to fuse production and consumption of values.

This fusion rule can be demonstrated by algebraic manipulation of the programs we’ve defined so far. We’ll call the unfoldr and then foldr by the name hylo, with the naive implementation shown:

hylo f z g = foldr f z . unfoldr g

The equational style here facilitates some nice rearrangements which help to assert their correctness from step to step. Let’s see how this works — each line will be justified by some comment in braces:

  hylo f z g s
= { definition from above }
  foldr f z (unfoldr g s)
= { definition of unfoldr }
  foldr f z (case g s of
                  Nothing     -> []
                  Just (x,s') -> x : unfoldr g s')
= { push foldr into result }
  case g s of
       Nothing     -> foldr f z []
       Just (x,s') -> foldr f z (x : unfoldr g s')
= { foldr on empty lists }
  case g s of
       Nothing     -> z
       Just (x,s') -> foldr f z (x : unfoldr g s')
= { foldr on non-empty lists }
  case g s of
       Nothing     -> z
       Just (x,s') -> f x (foldr f z (unfoldr g s'))
= { definition of hylo }
  case g s of
       Nothing     -> z
       Just (x,s') -> f x (hylo f z g s')

Each step should be clearly equivalent to the one before and the one after, but by the end we have a definition for hylo which doesn’t construct a useless list.

hylo f z g s = case g s of
                 Nothing     -> z
                 Just (x,s') -> f x (hylo f z g s')

Naturally we can use the original definitions of product and enumTo to create an optimised factorial using this logic. The result is that factorial doesn’t create a redundant list either:

factorial n = hylo (*) 1 step
  where step s = if s > n then Nothing else Just (s,s+1)

I think this is beautiful result despite its obvious simplicity. However this has been a long digression, so I’ll stop now. But if you found it interesting I encourage you to check out work on “program calculation”, “program derivation”, “algebra of programming”, “origami programming” and so on.)

My evening journeys have been spent unwinding with a book, though the evening trains are noisier. I’m reading Brighton Rock right now and it’s good though the story makes me feel quite uncomfortable at times. One of the characters seems close to doing something wild and dangerous and it’s a fight between “must find out what happens” and “can’t bear to read any more” on a daily basis.

I hope week two will be easier and I will start to feel like my routine is falling into place. Watch this space.

The sufficiently smart compiler is one that removes any need for engineering judgement/ability on the part of the programmer. The sufficiently aesthetic compiler does the same for artistic judgement.

My troubles with parsing the ComicBake script format have been resolved, in particular by checking out John Goerzen’s ConfigFile package, which uses the same parser combinators to read INI files.

The code in ScriptParser.hs is slightly reduced and hopefully more robust and flexible than it was before. It certainly now recognises optional (Thinking) keyword, though right now the option is ignored later in the compilation process.

One advantage of finalising the parser is that I have a much better idea what the file format is. It helped to crystallise some of the fuzzy areas in my mind. This is the inevitable result of any programming endeavour — vague ideas are made exact or abandoned altogether.

I’ve updated the README to describe the key/value format used for defining metadata, and ensured that the old comics all still build properly. The new parser just skips comments which were previously meaningful if they don’t have the correct keyword specified. So I didn’t need to rewrite my examples.

Also I just noticed that I’ve made 150 commits to this repository. I doubt that means anything but I’m surprised it’s so many. I suppose at one point I was being quite good about lots of little commits for independent changes. Lately I’ve just been working on hulking great code bombs which can’t be split up until after they’re done, and by then it hardly seems worth it.

Thinking about calculating the number of working days between two dates. (Note, I haven’t actually executed any of this code, just thought about it. It could be quite wrong.)

workingdays :: Day -> Day -> Integer
workingdays start end = undefined

For this scenario I assume that end is no earlier than start. (Obviously we can deal with this situation using some wrapper function to sort the dates if the result depends on this order.)

If start and end are the same day we define this as “zero working days”.

workingdays :: Day -> Day -> Integer
workingdays start end | start == end = 0
                      | otherwise    = undefined

If start and end are both the same day of the week then there will be a whole number of “working weeks” between the dates, eg one Monday to the next Monday is one working week. A working week is 5 days, so the number of working days is the number of working weeks times five.

We determine if two dates occur on the same day of the week by checking the number of days between them. Any number which is a multiple of seven (0, 7, 14, 21, …) indicates the two dates are a whole number of weeks apart. Multiples of seven produce a remainder of zero when divided by seven, so we divide the span by seven and check the remainder.

workingdays :: Day -> Day -> Integer
workingdays start end | start == end = 0
                      | is_sameday   = 5 * wholeweeks
                      | otherwise    = undefined
    where is_sameday = diffDays start end `mod` 7 == 0
          wholeweeks = diffDays start end `div` 7

At this point we notice that the first scenario is a simplified case of the second, where the two dates occur on the same day of the week with exactly no weeks between them. We can just collapse them into one calculation.

workingdays :: Day -> Day -> Integer
workingdays start end | is_sameday = 5 * wholeweeks
                      | otherwise  = undefined
    where is_sameday = diffDays start end `mod` 7 == 0
          wholeweeks = diffDays start end `div` 7

If the two dates don’t fall on the same day there may be some fraction of a working week between the two. The number of days leftover in the last week is the remainder when the number of weeks is calculated, which we’ve already worked out once. Rather than doing it twice we’ll separate it out into whole weeks and days.

workingdays :: Day -> Day -> Integer
workingdays start end | days == 0 = 5 * weeks
                      | otherwise = 5 * weeks + partweek
    where (weeks,days) = diffDays start end `divMod` 7
          partweek     = undefined

The bit we don’t know yet is the number of working days which make up the last part-week. The value of partweek is between zero and days with an upper limit of 5 because there can only be 5 working days between any two dates less than a week apart. At this point we’d be as well to just count them.

workingdays :: Day -> Day -> Integer
workingdays start end | days == 0 = 5 * weeks
                      | otherwise = 5 * weeks + partweek
    where (weeks,days) = diffDays start end `divMod` 7
          partweek     = length $ filter weekday $ enumFromTo newstart end
          newstart     = addDays (7 * weeks + 1) start

We count the number of weekdays from the day after the first day, since that day doesn’t count. At this point it probably hasn’t escaped you that we’ve got more repetition. We could remove the first case (for whole weeks) because partweek will evaluate to zero in that case.

If there is a nicer way to calculate the remaining part of the week I haven’t spotted it. I feel sure there must be something better than just looping over the remaining days, though maybe I am wrong.

In the last few days I’ve been snatching some moments to rewrite the awful, ugly parser in ComicBake into something readable and adaptable. While doing this I’ve been slowly rewriting the format of the accepted scripts. All of the improvements have been fairly subtle but sometimes with large improvements in usability and ease of implementation.

The big one is the comments. Previously the first N comments were hard-coded to contain the comic title, author and other information, prefixed with the “comment delimiter”, a double-dash symbol. I’ve adopted a key-value style instead which means comments can be included (or omitted) as necessary from the header without problem:

Old style:

-- Pandemic
-- Board games
-- Dougal Stanton
-- January 2011

New style:

-- title: Pandemic
-- series: Board games
-- author: Dougal Stanton
-- date: January 2011

At the moment I’m only storing the title and author names but it’s possible to tag anything now and use it later if necessary. The tags can be re-ordered as desired and if you miss them altogether I just use an empty string.

I’m also experimenting with adding directions to indicate speech/thought bubbles. At the moment the code uses this format but it may change:

Garfield: (Thinking)
    I hate Mondays

Sadly I’ve realised that the language is still ambiguous about divisions between scenes. A scene may end when a new one starts, or when the file ends. Getting it to manage both is proving awkward. I don’t want to add more syntactic elements just to make it easier to parse, so I’ll have to see how other languages which define loosely-grouped sections (eg, INI files) are parsed.

For about six months now I (and then Helen) have been going to Capoeira Angola classes run by Mão no Chão group. Suffice it to say we are neither of the people in this photograph in fact, it’s just one I found on Flickr.

Continue Reading »

Right now I’m reading The Three Musketeers by Alexandre Dumas. It’s really enjoyable so far — whimsical and witty like a 19th-century The Princess Bride (not inconceivable). I’ve got a big ol’ pile of things to get through after that. I still have a book from my birthday in June and a bunch from Christmas too. I came away from last night’s book group with two more — Pathfinders: The Golden Age of Arabic Science by Jim Al-Khalili. I’d been swithering over this one until I noticed the author. He has produced some great science television so I thought his book might be worth it. And Under Milk Wood, a play I associate strongly with my father though I’ve never heard or read it. But I’ve been quoted it a lot!

I took along Seamus Heaney’s translation of Beowulf but no-one was interested. I think a lot of people had book overload and weren’t taking new ones to read. We’re not having our next meeting until March so there will be plenty of time for people to finish the books they’ve got. Hopefully I can deplete my to-read pile slightly by then.