$ cat /home/buntine/mind_melting_brilliance

A big "thanks" to the people that emailed me and those who brought it up on forums, etc. Sorry for my delay, but I've just updated Witchhammer to be compatible with Firefox 3.6.*. All should be fine within the next 30 minutes or so (just waiting on Mozilla to update their cache).

As per usual, download it from the official repository: https://addons.mozilla.org/en-US/firefox/addon/9671/

Thanks again!

Exercise 1.12 in SICP is proposed as follows:

My brain saw it as:

I spent about 30 minutes working on a solution that would actually return a structure containing all of the elements of Pascals Triangle up to a particular row/width. I was wondering the whole time how any non-experienced programmer could ever solve the problem at such an early stage of the book! D'oh!

Here is what I came up with:

(define (pascal width)
  (reverse (pascal-helper '((1)) width)))

(define (pascal-helper rows width)
  (if (= (length rows) width)
    rows
    (pascal-helper (cons (next-row (car rows))
                         rows)
                   width)))

(define (next-row previous)
  (let ((body (row-body '() previous)))
    (if (null? body)
      '(1 1)
      (cons 1 (append body '(1))))))

(define (row-body body previous)
  (if (null? (cdr previous))
    body
    (row-body (cons (+ (car previous) (cadr previous))
                    body)
              (cdr previous))))

And lets see it in action:

> (pascal 5)
> ((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))

It works by building each row of the triangle in reverse order. Each row implements a linearly recursive process to build itself based on the contents of the previous row. We consume the previous row by taking it's cdr on each resursion. This means that the value of element y in row x is the sum of the first two elements in the previous row. This process is continued until the previous row has only one element left. At this point we throw a 1 on either side and we are done!

From now on I will be sure to pay more attention when interpreting the requirements for each exercise (although I secretly think this was much more fun)!

This is the second article in a two (maybe three) part series on tree data structures in Scheme. See the "representation article", also.

Previously, I've spoken about one way of representing a tree data structure in Scheme. This time, I'll talk about a simple algorithm for parsing such a structure, which uses a technique called mutual recursion.

Wikipedia defines mutual recursion as "a form of recursion where two mathematical or computational functions are defined in terms of each other". This is an appropriate explanation for our case, as we'll have two procedures which rely upon each other to produce a single result.

The first procedure will extract the child nodes from a tree structure. The second procedure will accept those children, a list of trees, and extract and parse each one. This process is performed recursively.

As an example, lets write an accumulative procedure that consumes a tree and returns a number representing the amount of parent nodes (that is, nodes which contain further children):

; Using the tree we created in the first article
> (count-parents family-tree)
  3

We can define this as follows:

(define (leaf? node)
  (null? (cdr node)))

(define (count-parents tree)
  (if (leaf? tree)
    0
    (+ 1 (count-parents-in-trees (cdr tree)))))

(define (count-parents-in-trees trees)
  (if (null? trees)
    0
    (+ (count-parents (car trees))
       (count-parents-in-trees (cdr trees)))))

It works by allowing the two procedures to only deal with the information they need. count-parents deals with trees, whilst count-parents-in-trees deals with a list of trees. leaf? is just a simple helper. Each branch of each tree is searched downwards until we reach a dead-end - a node with no children.

The recursive pattern in count-parents-in-trees should be fairly familiar. Basically, we take the first element (car) for inspection, and recurse with the remaining elements (cdr). Because of this, our base-case is the empty list, at which point we've hit every node in the branch and should have our result.

This general pattern can be applied to many tasks involving trees, from representing them graphically to mutating their structure. For example, to write a procedure that takes a tree and returns a new tree without the leaf nodes, all we need to do is use mutual recursion to build up a copy of the tree in question and ignore every leaf node.

This is the first part of a two (maybe three) part series on tree data structures in Scheme.

In many programming problems, an efficient way of organising data is in a tree-like structure. In essence, a tree in this sense consists of a root node, followed by zero or more sub-nodes, each of which can be followed by a set of further nodes. Common terminology for this node/subnodes relationship is mother and children, respectively. Other common terms are root/branch/leaf.

A picture is a great way to provide an example of such a structure:

The tree above is quite simple. It consists of a root node, followed by two children. The first child contains no further children (a leaf), and the second child is the parent to one child. An important thing to realise at this point is that every child is infact a perfectly valid tree in and of itself. We can see this in more detail a bit further on.

Representing such a structure in Scheme (or any implementation of LISP) is really quite easy. We use the obvious building block: lists. The tree in the image above would be encoded as:

'(a (b) (c (d)))

 

As I mentioned before, if we snap off the branches from the root node, we are left with a set of new trees; a forest. In LISP terms, the cdr of a tree is a list of lists:

'((b) (c (d)))

The first item in this list is a tree with only a root node. Not a very useful tree, but a tree none-the-less. The second; a tree with a root node and a single child element. The reason I've brought this up is because it shows us that there is most certainly a convenient recursive way to deal with such a structure (this I will talk about in the next article).

To help us with creating trees and get our terminology contextually proper, we can define the following helper procedures:

(define (tree root . children)
  (cons root children))

(define (leaf-node node)
  (tree node))

So, with these new procedures in place, lets create a basic tree structure:

> (define family-tree
          (tree 'family
                (tree 'karl
                      (leaf-node 'oak))
                (tree 'colin
                      (leaf-node 'celine)
                      (leaf-node 'ashin))))

> family-tree
  (family (karl (oak)) (colin (celine) (ashin)))

In the next article I'll talk about a cool way of recursively parsing such a structure.

If you're like me, you've probably read the first 150 pages of SICP (The Structure and Interpretation of Computer Programs) about three times. Personally, I find that it starts out extremely easy, but quickly becomes difficult. After a while I find that I am still reading, but not a whole lot is making sense to me. It's as though there is an underlying peice of knowledge that the authors assume I possess, which I don't.

I am of the school of "SICP should be read by all programmers". But I think my exact statement would be: "SICP should be read, and understood, by all programmers".

If we take a look on Amazon, we will see the strange mix of reviews SICP has received thus far (stars/reviews): 5/89, 4/8, 3/8, 2/3, 1/53

What?? So, I guess this implies that people either LOVE or HATE this book. If you go through the reviews in detail, you can see that a lot of the 1-star reviewers are upset with the text because it's simply too abstract and they do not leave with any confidence. I feel it is also worth mentioning that this text has received an elitist badge in our industry. If you read it, watch the lectures, and brainwash yourself into thinking you understood everything, you are now part of the genius club and can start quoting Paul Graham and Peter Norvig.

Enter Simply Scheme (Brain Harvey, Matthew Wright. 2nd ed, 1999, MIT press). A fundamental computer programming textbook for those of us who have trouble tackling SICP (and also for the people who, out of fear, pretend they could). According to the authors, SS was actually written as a pre-cursor to SICP. This textbook presents all the major concepts in a much more digestible way than SICP. This is good news!

As a word of warning, it's worth knowing that SS does use Scheme, but it teaches a slightly modified version of it. You will learn effective program design, but not the inner workings of Scheme itself. I already knew scheme when I started this book, and it annoyed me a little at the beginning, but I quickly got used to it.

The entire text is available free on the web. Take a look: http://www.eecs.berkeley.edu/~bh/ss-toc2.html.

I have also spent a lot of my freetime publishing my answers to all of the exercises at the end of each chapter. You can take a look at my solutions here: http://github.com/buntine/Simply-Scheme-Exercises (perhaps you can fork me and juxtapose your own solutions??). I hope this can help someone in their travels.

So, once you get through Simply Scheme, you may be much better suited to properly tackle SICP and finally become a master craftsman!

I had planned to post these more often, but hey, I guess I've been busy with non-computery stuff for the first time in far too long.

At the moment I am in Thailand, in Krabi Town specifically, a small-ish city in the south. It's near Phuket (which I did not like, for the record).

I've been on the road for about a month now and have loved (nearly) every minute of it. The first few days were a little rough as it was at that point I truly realised I was alone in a very foreign place.

At this point, I've seen most of the country. There are still some spots in central Thailand that I'd like to check out, but that will have to happen another time. I think my favourite place so far has been Chiang Mai, the proverbial "capital of the North". It's an ancient city with a laid-back atmosphere. Tomorrow night I am catching the overnight train up to Bangkok, where I will spend a few more nights.

On the 29th of December, I am flying directly to Munich, Germany. From there I will try and see as much of Eastern Europe as possibly can in 20 days (without rushing too much, of course). My only guideline is that I will need to be in Amsterdam on the 18th of January. At this point I will be meeting my younger sister, Grace, with whom I will travel through some of Western Europe (The Netherlands, Belgium, France, Switzerland).

At this point, I am feeling glad that I decided to travel alone. This type of radical decision really helps you come out your shell. I've met a lot of really cool people from all over the world and experienced Thai culture in a way that a lot of package travellers would never get to see.

Until next time!

A few weeks ago, I booked a one-way ticket to Bangkok. I have a netbook, a backpack, malaria tablets, new shoes, and some books on LISP.

I am departing from Melbourne at 2:55pm on December 1st, 2009.

The plan (well, if I had one, this would be it) is to spend a few weeks in Thailand, and then transplant myself into Cambodia. After visiting all of the Wats (temples) and soaking in the atmosphere, I'll travel into Laos and lay back for a few weeks. I've heard there is a cool "river-tubing" activity near Vang Vieng, which sounds fun.

Next is the hustle-bustle of Vietnam! I've heard excellent things about this country, and really look forward to checking it out. My sister says she will fly over and meet me in Hanoi, which would be ultra badass!

After that, depending on my financial, physical and emotional state, I may well just keep going and catch a flight to somewhere in China. But who knows? By then I might be in Africa or South America...

I'll still be online regularly (where possible), so hopefully I can document some of my travels as I go. Wish me luck! :)

Running an arbitrary process, such as a Python script, on your Linux box as a daemon is really quite simple if you have the right tools.

In my case, I had a simple Python socket server that needed to run permanently. Simply running it in the background (Ctrl-z) is no good as it would die the moment I logged off!

Enter daemon, a really handy tool for solving this exact problem.

Installation is easy. On Debian-based distros, you can just install it directly form aptitude. On CentOS, which uses yum, I had to install it from source. But I ran into no problems there.

Once installed, getting things running was easy:

$ daemon -r --name=myserver python /full/path/to/myserver.py

The "r" flag tells daemon to respawn itself if the service is killed. I've given it a name so I can refer to it later. And the rest of the line is the actual command I want to run.

To test if the process is still running, you can look in ps or pgrep, but the best way to do it is to simply ask daemon personally:

$ daemon -v --name=myserver --running

The "v" flag is for verbosity (of coarse). The "running" flag tell daemon that I want to know if the process specified by "name" is still running. The output you receive is simple to interpret, e.g: "myserver is running with PID: 23324".

To finally kill the process at some point in the future, you can issue the following command:

$ daemon -v --name=myserver --stop

And this one should be rather self-explanatory by now. :)

I've only grazed the surface here. Just check out the man page for an idea of how much more you can do with this. Good luck, muchachos!

Python is great. It's nearly at the top of my list of "most usable" programming languages.

But one thing annoys me. It's even been explained in detail, and it still annoys me!

Basically, the join() method is defined on the string class and not on the list/tuple class. Now, I admit, it's not really that big of a deal. It's hardly going to make me drop Python into the abyss of "tried, but shitty" languages.

When I was first learning Python, I knew that joining a list/array of strings on a specific delimiter would be part of the standard library. Here is what I tried:

["Balls", "to", "the", "walls"].join(", ")

But, no! Python makes me do this:

", ".join(["Balls", "to", "the", "walls"])

Eww! It's both backwards and ugly! Let me do it by way, Python! In Ruby, I could just duckpunch the hell out of the class and implement my own method. But thats another story...

The thing that bothers me the most is that you actually have to pass a list into the method. If the join method must be on string, then I should atleast be able to pass in an arbitrary number of arguments, like so:

", ".join("Balls", "to", "the", "walls")

I mean, Python does support optional arguments, after all. And if I have a list I want to join, I could just apply the list as arguments:

# Doesn't work...
args = ["Balls", "to", "the", "walls"]
", ".join(*args)

One other thing that (slightly) bothers me is that it also forces me to pass in a list of string objects. Being dynamically-typed and very-high-level, I would have expected Python to forcfully stringify any non-string members of the supplied list.

", ".join(["Balls", 2, "the", "Walls"])    => ERROR!

C'mon, Python. You already give me the option of writing questionable code by allowing me to access private instance methods externally (Note: I've never done this).

Installing ImageMagick + RMagick seems to be a common source of problems. Here is my eventual solution.

I must admit, I'm not a huge fan of yum. And this latest experience has not helped my disposition. There is an ImageMagick(-devel) package in the repository, but it's very old now requires an earlier version of RMagick. I also found that it didn't work with the FileColumn Rails plugin ("Invalid image" error).

I recommend, for CentOS 5.x atleast, that you build ImageMagick from source.

0) Install all the dependencies (yum should be fine for these):

• libjpeg - Read/write Jpeg files
• libpng - Read/write Png files
• freetype - Support for fonts

1) Grab ImageMagick and unpack it

$ wget ftp://ftp.imagemagick.org/pub/ImageMagick/ImageMagick.tar.gz
$ tar xvzf ImageMagick.tar.gz
$ cd ImageMagick-x.x.x

2) Compile and install ImageMagick. Note, these are the flags I used for my own server. Use --help to see a full list of the options.

$ ./configure --prefix=/usr --disable-static --with-modules --without-magick-plus-plus --with-quantum-depth=8
$ make
$ sudo make install

3) Play the waiting game. Or you can have a sword fight with an employee. :)

4) Install the latest version of the RMagick gem

$ sudo gem install rmagick

5) For good measure, open up IRB and see if it's installed correctly.

$ irb
> require 'RMagick'
> true

Good luck in your adventures, people.