In Search of Lost Time

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:

1
2
3
4
5
6
7
8

(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:

1
2
3
4
5
6
7
8

(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.

I finally decided to check out one of the many web development frameworks out there. After narrowing my choice to Ruby on Rails or Django I settled on Django as I already knew Python so could get started right away.

As a first project I worked through the Django tutorial adapting the steps there to build a simple blog application. It's been good fun and over breakfast for the last week or so I've managed to hack together some software that can replace Wordpress for my blog. I've made the source code available for anyone who is interested although I imagine there are already many much better apps for blogging out there (Wordpress being one of them).

I have managed to add Akismet, twitter integration, tagging and markdown for comments and posts. That's pretty much everything I was using on Wordpress so the result is good enough for my purposes. I also replaced my generic Wordpress theme with a significantly simpler layout that was within my XHTML and CSS abilities.

Now time to think of the next project that I can work on...

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:

1
2
3
4
5
6
7
8
9

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 overriden.

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.

I was once asked in an interview what my favourite feature of C++ was to which I immediately responded "destructors". The interviewer retorted that garbage collection made destructors redundant. Looking back I assume that he was pushing me to give further explanation of what made destructors such a neat feature which I didn't manage to give immediately but I did explain in the context of boost::mutex::scoped_lock later on.

Lately working with C# has brought me back to the feeling that deterministic destruction is a great feature. In C# resources are destroyed using the dispose pattern

1
2
3
4
5
6
7
8
9

MyConnection connection = null;
try {
    connection = new MyConnection(foo);
    connection.Open();
    // Make use of the connection here
} finally {
    // Only today I encountered code where the null check was forgotten :(
    if (connection != null) { connection.Dispose(); }
}

this is made significantly less painful by the using keyword:

1
2
3
4

using (var connection = new MyConnection(foo)) {
    connection.Open();
    // Use connection here, disposed when we leave the using block
}

but it still relies on the caller to remember that instances of this class need special attention. In addition when there are multiple resources in use things can get a little messy (although nothing compared to Java which lacks the using keyword).

Back in the C++ world things are much simpler:

1
2

MyConnection connection(foo);
// use connection here, it will be destroyed when it goes out of scope

and this same pattern applies to all resources: files, memory, mutex locks, whatever. Not to mention the fact that it scales well to multiple objects. There is just something inherently elegant about solving the general case of resource management with one technique rather than the combination of garbage collection and the lock and using keywords.

I have noticed over the last few weeks that online retailers seems to be charging inflated prices for Professor Layton and the Curious Village on the Nintendo DS but this is just ridiculous!

According to what Google has cached this game was previously selling for £24.99 on play.com. I recently bought a Nintendo DS for Caterina and it would have been nice to pick up this game in time for Christmas but I think I will wait until its available in the shops again.