Author Archives: Nicholas Lativy

Carla Bozulich

Posted on by
1

On a cold Monday night we migrate from nursing a pint in The Kingsland pub for over an hour to the short line outside Cafe Oto. After some grumbling about the doors not being opened fast enough we’re on our way in. In the absence of a stamp my wrist is scored with a marker pen and we make our way to a small table right in front of the stage.
The night starts with Jack Shirt who plays a kind of sinister fairground music on a guitar and an array of effects pedals. The music is hauntingly beautiful but the feedback often spirals beyond his control and he finally apologises and gives up. The crowd applaud warmly in support, and Jack looks a little dejected as he packs up. We decide to grab his CD-R, nicely packed in a felt pouch and wait for the main event.

Carla BozulichSimilar technical difficulties occur near the start of Carla’s set as Francesco Guerri’s cello falls silent and he frantically unplugs effects pedals to try locate a fault. Thankfully with two on stage Carla happily jams away on her guitar until the problem is solved and they launch into the first song. One of the highlights of the night is when Carla lays down her guitar to perform Baby That’s The Creeps. Carla wanders through the audience, brushing past audience members and knocking over furniture, captivating the room with her intense performance. When I start to shiver I’m unsure if it’s really because of the cold.

As the set ends Carla asks if she’s played a good amount, gesturing the length of the set with her hands. After shouts of “more” and rapturous applause Francesco and Carla return for an encore. I’ve put a handful of my photos on flickr.

Life in London

Posted on by
1

After nine months living in London I’m finding myself in an increasingly reflective mood. Life in the capital is pretty amazing. A trip to one of the many markets always has me returning with something cool like the Stylophone I picked up last week at Brick Lane Market or the yummy cheese and salami we grabbed at Borough Market the week before. The city is full of restaurants serving food from all around the globe and if I had a bit more money I’d probably try and eat through as many of them as I can. However, probably my favourite thing in London is music. Gone are the days when I flicked through the listings at the back of The Wire and lamented the number of cool gigs that I would be unable to go to. I’ve also discovered Cafe Oto and its amazing programme of new music which makes me think about moving to East London more and more each day.

Chelsea, London

It’s cool to just take the tube somewhere random and go for a walk and see what you find. Quaint little lanes in Chelsea, an independent record shop at the end of Portobello Road, stunning views on the South Bank or the awesome Dalston Peace Mural.

There are downsides to life here too, rent is ridiculously expensive and the quality of housing very low. It seems the demand is so high that landlords can be pretty much guaranteed a particular price based on area and don’t need to bother maintaining their property. My commute, although thankfully brief, usually involves being crammed into a smelly metal tube with a few hundred fellow Londoners. The hectic nature of life and work here can be tiring and a little stressful at times. Despite all this, I think it’s worth it to live in a place where I have the chance to discover something new every day.

Finding a loop in a linked list

Posted on by
Reply

I have been reading through the excellent SICP recently which has been an enlightening experience. The book takes a unique approach to the introductory programming textbook focusing not merely on introducing various basic constructs but on the computer language as a “novel formal medium for expressing ideas about methodology”.

Chapter three introduces assignment along with set-car! and set-cdr! for the modification of lists. This leads on to an interesting discussion of how lists are structured in memory and the possibility of creating a looped linked list with the procedures:

(define (last-pair x)
  (if (null? (cdr x))
    x
    (last-pair (cdr x))))

(define (make-cycle x)
  (set-cdr! (last-pair x) x)
  x)

As you can see make-cycle connects the end of x to the start forming a loop. Exercise 3.18 asks the reader to define a procedure which will determine whether a list contains a cycle or not. This can easily be achieved using eq? and waiting until we reach a null or visit a node twice. The problem is that this seems to require some auxiliary data structure or temporary modification of the original list.

Exercise 3.19 pushes us further and asks for an algorithm which runs in constant space. A possible solution would be:

(define (cyclic? x)
  (define (fast-adv x) (if (null? (cdr x)) '() (cddr x)))
  (define (cyclic-check slow fast)
    (cond ((null? fast) false)
          ((eq? fast slow) true)
          (else (cyclic-check (cdr slow) (fast-adv fast)))))

  (if (null? x) false (cyclic-check x (fast-adv x))))

Unfortunately my Scheme isn’t great and there is a little bit of redundancy in my expression of the algorithm but it achieves the goal of finding a loop using constant space. This works by having two pairs: one which advances normally with cdr and one which advances two at a time using fast-adv. If there is a loop in our list the slow object will eventually catch up with the fast one, otherwise we will reach the end. If you aren’t familiar with functional languages you may be wondering about the recursion in the previous procedure but since it is tail recursive it is in fact an iterative process. This algorithm is due to Robert W Floyd.

Wikipedia has an interesting article on cycle detection in terms of iterated functions which includes a discussion of Floyd’s algorithm.

Framework Design Guidelines

Posted on by
Reply

A few months ago I finished reading the second edition of Brad Abrams and Krzysztof Cwalina’s excellent Framework Design Guidelines book. I just love how this book condenses the lessons learned in building the .Net Framework in areas such as design patterns and API usability into a set of easy to follow guidelines annotated by various luminaries from Microsoft and beyond.

For me reading the book provided valuable insight into .Net, reinforced my knowledge of design patterns and provided lots of useful advice on software engineering in general. As an example one guideline that I recall as I write this is “do prefer protected accessibility over public accessibility for virtual members”. This leads to the suggestion of applying the template method pattern as follows:

public Control {
  public void SetBounds(...)
  {
    ...
    SetBoundsCore(...);
  }

  protected virtual void SetBoundsCore(...) { ... }
}

The book also makes the valuable point that this pattern allows the base class to enforce that overloads remain semantically consistent by defining them in the base class in terms of one core virtual method that can then be overridden.

On the usability front a comment from Krzysztof has stuck with me since reading the book:

The number of customers that will use your API is inversely proportional to the number of new statements in your simple scenarios.

This reinforces the book’s suggestion of a scenario driven design approach where we are encouraged to write code for common scenarios before designing the API and run user studies early on with other developers writing code exercising these main scenarios.

Finally Framework Design Guidelines introduced me to FxCop which does the great job of encoding the guidelines in a static analysis tool thus catching any accidental slips in our APIs early on. This makes following a large number of the guidelines incredibly easy.

As Miguel de Icaza asserts in the foreword: this book will help you become a better programmer.

Haskell in less than five minutes

Posted on by
Reply

I have been playing with Haskell and the Glasgow Haskell Compiler today, refreshing my memory of the language. After spending the last two years coding mostly in C++ and Python with a smattering of C it is a rather pleasant experience. Note: the simplest way to try out these examples is with ghci or hugs; simply place the code in file.hs and load it from within the interpreter with :load file.hs and then call the function as normal.

To start with a simple example of the language, the following calculates the nth Fibonacci number:

fib n | n < 2 = 1
      | n >= 2 = fib(n-1) + fib(n-2)


The boolean guards n < 2 and n >= 2 determine what is evaluated. We can then map this function onto the natural numbers using:

fibs = map fib [1..]


and subsequently get the first 10 Fibonacci numbers with take 10 fibs which returns the expected list. Higher order functions such as map are simple to define, such as:

map f xs = [f x | x <- xs]


The expression on the right of the equals is an example of list comprehension. The generator x <- xs takes each x from the input list xs in turn and the expression f x is applied forming a new list. Multiple generators can be used, for example the expression [(a,b) | a <- [1..3], b <- ['a', 'b']] evaluates to the list

[(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]


Making use of list comprehension gives us the rather lovely Haskell rendering of the quicksort algorithm:

qsort []     = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x]
                     ++ qsort [y | y <- xs, y >= x]


Simple, concise and, in comparison to C or the pseudo code rendition in the textbooks I have to hand, very easy to understand. When supplied with an empty list the qsort function returns an empty list. When given a list (consisting of the first element, x, and the remainder of the list xs) we use the first element as the pivot and apply qsort recursively to all the elements less than x, concatenate that list, using the ++ operator, with [x] and then concatenate that with the result of qsort applied to all elements greater than x. We could even make this slightly shorter by replacing [y | y <- xs, y < x] with filter (< x) xs. Of course I have glossed over the fact that using the head of the list as the pivot is not a very good idea but it’s still a very aesthetically pleasing piece of code. :)