It’s been a long time since I’ve updated this blog, and a completely crazy past few months, so I hope to rectify the former by using the latter as the basis for this post :)

I turned 30 this September, and the force of switching from the deferring-friendly 20’s (‘I can achieve these things, don’t worry, I’m still young’) to the ‘oh shit I’m an adult now’ 30’s has hit harder than I expected (in fact, to be honest, I didn’t expect it at all).

So what’s happened? Well in my personal life, I finally did something about my weight issue and lost ~3.5 stone (~50lb, ~23kg).

In my intellectual/geek life I committed to the open Stanford AI course and completed it with a 98.7% average*, and wrote notes for the purposes of actual applying the course to real things (the notes are not yet fully complete, however I do plan to finish that later), which has really helped with my recently very low intellectual confidence.

Two fundamental things have changed - firstly I’ve got organised about things (for weight loss - food diary, for study - committed, realistic work schedule), secondly and far more importantly, I’ve stopped beating myself up quite as badly about everything. Beating yourself up like that makes you incapable of doing anything since you feel constantly bad about whatever it is you’re doing, and thus reticent to do it, which means you don’t improve/change anything, which means you beat yourself up more, etc. - a vicious, vicious cycle.

Another thing to note here is the amazing usefulness of timeboxing. The past week I have got more hacking done in a week than I have for hundreds of weeks prior.

So what about resolutions? Over the coming year I plan to contribute considerably more to go, and build weak into a fully-fledged chess engine (though I can make no guarantees to its eventual strength) and I intend to work on improving my algorithmic and computer science fundamentals knowledge. On the final bit - I plan to enter the google code jam and blog about the experience, though I don’t expect or predict any sort of performance, it’s more of a motivation and point of focus.

Happy New Year!

* I’m not boasting here. I fell considerably below the performance of many other participants and wish I’d been more careful with many of the answers. Also I realised how rusty I am at this stuff. Also I couldn’t stand to carry on attending the meetup I was attending given how erudite, intelligent and informed the other people were compared to me.

After writing my last post, I again worked my arse off this week to study both the Stanford AI and ML classes in a less crunchy fashion than the week before. Unfortunately the crunch avoidance did not come to pass and I was up until 3am this morning (well, 2am if you take into account the clocks going back :-) cramming on AI.

Since I actually want to learn about AI (and apply it to weak) I am not finding this cramming aspect of the study particularly beneficial. In my experience, cramming simply wears you out and gets you ready for a given short-term task (e.g. homework, later exams) before the information you’ve learned largely plops out of your brain.

For that reason, and for the sake of keeping this doable, I’ve decided to drop the machine learning course and focus fully on AI. There is an irony in that - I have found the AI work to be considerably more involved and challenging than machine learning (that’s not a comment on the relative quality of one course vs. the other by the way), however a. AI is of more relevance to what I want to do, and b. focusing on one thing reduces the stressful feeling of distraction that maintaing another course which requires homework, etc. brings.

I am still very interested in machine learning, so I might very well go over the machine learning course material at a later date. Additionally, the AI course contains some cross-over material so I won’t do entirely without.

Another aspect is that I would like to maintain my notes to a better standard than I have (and which more time would allow me to achieve), rather than having to rush them out because of time constraints. There are almost certainly better notes for the course out there, however there is nothing quite like having a set of notes to refer to you which you’ve written in your own style and to your own tastes. Not invented here syndrome, perhaps!

Meta-Blog Tediousness

On an entirely different subject, you may have noticed I’ve deleted a number of posts. This is because I felt they were of little value and often quite negative. This blog is meant to be a diary of where I’m at in my tech life, and yes that involves both positive and negative, however there is nothing more tedious than wading through either rather mediocre technical posts, or moany personal ones. I’d like to maximise the chances of me (and to some degree others of course :-) actually enjoying reading this blog.

I can only apologise to those few whose comments have consequently been deleted from this site. Hopefully you can understand why I’ve done it.

Am currently attempting to do both the Stanford AI and Machine Learning courses at once. My brain is melting.

I’m keeping my ongoing rough notes on github, I’m writing them in markdown so they render relatively nicely there.

I have realised that, if I am actually going to see both courses through to the end, I am going to have to put everything else on hold until they’re done.

Luckily, they both pertain to greater or lesser degrees to weak so its not entirely a pause on other projects. Also, I might choose to hack on weak from time-to-time since I am chomping at the bit to get it moving.

Recently found an amazing talk focusing on the social/interpersonal aspects of development from Google I/O (2009 vintage), the point on letting yourself be vulnerable particularly chimed with me.

Patch Accepted

I recently received some good news - after much code review (and much cleaning up of my messy first attempt :-) my go patch addressing issue 667 has been accepted into the mainline. Yay!

Recursive Types

The issue is related to invalid recursive types, so let’s cover that first - what exactly is a recursive type, and when is it invalid?

As to the first question - a recursive type is simply a type which, at some point or another references itself in its definition.

A simple example:-

type List struct {
        Value interface{}
        Next *List
}

A convoluted example (note the recursive types here are T2,T5-7) :-

type T1 struct { T2; T3 }
type T2 struct { T5; T7 }
type T3 T4
type T4 struct {}
type T5 T6
type T6 T7
type T7 struct { *T2 }

Note that both of these examples describe valid recursive types. So what is an invalid recursive type?

type Foo struct {
        foo Foo
}

What makes this invalid?

Simply put, determining the size required for storage of this type would (assuming we don’t check for this in advance) result in an infinite loop - there is a cycle in the type’s definition.

There are many ways in which you can achieve this in code, it doesn’t have to be as overt as the previous example, e.g.:-

type Foo struct {
        bar Bar
}
type Bar Foo

This second example can be made valid by making the bar field a pointer type - that way we have no problem determining the size of the type - the field’s size is the system pointer size, e.g.:-

type Foo struct {
        bar *Bar
}
type Bar Foo

The Bug

Now we get to the bug - the code above wrongly resulted in an ‘invalid recursive type’ error.

More generally - types which were validly recursive via a forward reference were wrongly reported as invalid recursive types.

Note that the following compiled just fine:-

type Bar Foo
type Foo struct {
        bar *Bar
}

The problem comes down to the way the compiler constructs its internal representation of declared types - it constructs underlying types first (assuming they haven’t been constructed already) before constructing the type itself.

A problem with this approach arises when you have a declaration like:-

type Bar Foo

In essence this says - ‘copy Foo into a new type called Bar’.

This is fine most of the time, but if the type you are copying is not constructed yet (remember I am talking about the construction of the internal compiler representation of the type here), then you get whatever the compiler defaults the type to before finishing its construction.

It turns out that the compiler defaults to classifying all types (for those that are interested in the internals - the etype field) as forward types (etype == TFORW), before setting their actual type once the underlying types are constructed. Later, the compiler checks to see whether the type is still classified this way, and if so an ‘invalid recursive type’ error occurs (this isn’t the only way invalid recursive types are picked up, incidentally).

This makes sense for situations like:-

type Foo Foo

Or:-

type Foo Bar
type Bar Foo

And is, in fact, a nice solution in these instances, however the fact that the language allows a pointer type to refer to a forward reference is the cause of our bug.

The Solution

The solution I came up with was to specifically look for these circumstances and defer the copying of type information until after the base type has been constructed.

So, at the point where we would otherwise simply go ahead and check the type, specifically check to see whether there is a forward-type in its underlying type graph. If so, defer the type copy.

We have to be careful to actively check for cycles in the underlying type list to prevent the compiler from disappearing into an infinite loop when we encounter:-

type Foo Foo

-type scenarios. I used ‘Floyd’s Cycle-Finding Algorithm’ which is O(n) - described here.

The Best Bit

My favourite part of it all is the fact I could refer to the solution as a ‘dance’:-

// a dance to handle forward-declared recursive pointer types.

The go team often uses the term which is quite appropriate for some of the things which are necessary to make sure stuff works :-)

$ cd $GOROOT/src
$ find . -iname *.c | xargs grep -i 'dance' | wc -l
17

There are obviously more details going on here, but I don’t want to go into unnecessary detail here.

Also, yeah - I know - the patch is far from perfect, and could well be improved, but in any case I’m proud to have been able to fix the problem and contribute to a project I believe in.

Go Open Source!