All posts by Bill

MVC – Man Vs. Computer

June 2, 2014 Bill Leave a comment

I confess, I’ve never done MVC before! I’ve heard about it and read about it of course, but just never had occasion to use it until now.

I run our arechery club’s website as a sort of a passtime. It’s enjoyable and relaxing and I’m not under any pressure to deliver anything. So I thought I would do a sightmarks calculator.

In case you’re not familiar with the finer points of archery, most bows have a sight attached. The sight is a vertical track marked in arbitrary units that sticks out in front of the bow and has a scope or a pin that can slide up and down the track for different distances. Archers have a little book of sightmarks that they keep, and write down their sightmark for each distance. Now the amazing thing is that all that physics of ballistics and mathematics of trajectories seems to cancel itself out, so that there is a simple linear (or very nearly linear) relation between sightmark and distance.

All I wanted to achieve then, was a simple tool where an archer could enter a set of sightmarks and get a line of best fit for the data, which could then be used to generate a set of estimated sight marks for all the standard distances.

The tool would have an input section for the sample sightmarks, a graph (canvas) showing the inputs and line of best fit, and a table of the resulting estimates.

It’s only slightly more complicated than that in practice because I wanted to be able to persist the data in the browser’s local storage, and to allow archers to save multiple sets of sightmarks for different bows, arrows and bow setups.

This is obviously screaming out for MVC. I didn’t want to add a dependency on any heavyweight javascript MVC framewaork, so I decided to write it from scratch. You can see the finished result at www.roystonarchery.org/new/sightmarks/ (apologies for the very slow site, it’s EIG.)

The basic idea of MVC is a Model which stores state, one or more Views which present the model to the user, and a Controller which allows manipulation of the model. Conceptually it’s as simple as:

I should point out that this is the original MVC pattern as espoused by SmallTalk80, not the more “modern” variants fitted to the web, but since this is a browser-only application that seems a reasonable choice of pattern.

Of course real world programming is not that simple, and it took me an unreasonable amount of time to get this working. First of all I needed two controllers. The first would deal with the editing of the current model: adding and removing sight marks. The second controller would be concerned with persisting the data to local storage, restoring the data from local storage, and generally managing that data. The final architecture I came up with looks like this:

The heavy vertical line demarcates user-visible components from the “back-end”.

It works quite well now, but I had a struggle to get there. Maybe it’s because I don’t know Javascript that well, and I’m only just learning jQuery and the DataTables API, but I think it’s more fundamental, that the MVC “pattern” is fundamentally flawed in that it is usually impossible not to blur the distinction between Model and Controller, or in my case between View and Controller.

The Storage Controller is fairly straightforward. It reacts to user input by saving and restoring the entire Model, and allows management of the storage directly (deleting unwanted sets of sightmarks.)

The Input controller was more difficult because it needs to take information from the displayed inputs (currently selected sightmark) in order to delete it from the model. I had to make some rules to stop the whole thing dissolving into mush.

Lessons Learned

The most important thing is to ensure that the only state kept is in the model. If there is any unavoidable secondary state (such as is maintained by the DataTables objects,) then that secondary state must be completely flushed and recreated by any change to the model, and should not be relied upon.

The second important thing is to resist the temptation to short-circuit the system by having controllers update views directly. To keep this thing sane, all communication between controller and view must go via the model.

Lastly, having a MVC structure is better than having no structure, but be prepared to have to twist things around to make it work.

MVC is a very old pattern, dating to the earliest SmallTalk systems in an age where user experience could take second place to a clean implementation. Nowadays the UX is paramount, and we may have to think again.

Biology, Code Generation, fractals, Graphics, Technology

So You Feel Lucky?

May 13, 2014 Bill Leave a comment

I’ve just finished reading Stephen Jay Gould’s excellent book Wonderful Life (again) and it got me thinking about random trees.

In case you haven’t read it, Wonderful Life is about the fossil bed known as the Burgess Shales which contains extrordinarily well preserved fossils of soft and hard-bodied animals from a period just after the so-called Cambrian Explosion. The Cambrian Explosion marked the period when the seas first “exploded” with an enormous range of large, multicellular animals with hard shells that preserve easily. In the 1980s a detailed re-evaluation of the fossils found in the Burgess Shales provoked a scientific revolution in paleontology, because it turns out that only a small percentage of those fossils have any direct living descendants, and many of them represent previously unknown phyla (basic types of animals.) This did not fit comfortably with the established notion of evolution as ordered progress, with the basic groups of animals established early on and forming a predictable lineage all the way from microbe to man at the pinnacle. Rather it paints the picture of extinction being the norm, and the survival of one group or another very much in the hands of chance and historical contingency. The book is not an argument against Darwinism but rather a re-evaluation of some of its finer points. Crudely put, it’s not arguing against the existance of a Tree of Life, just questioning what shape the tree is.

Anyway with that in mind, and the somewhat vague hand-drawn trees in the book leaving my curiosity piqued, I started wondering what any real evolutionary tree might look like. Of course it’s impossible to ever produce an algorithm that will accurately represent a real evolutionary sequence, so I thought to keep it very simple.

We start with a “first progenitor“. It has two choices: form two new species or die out.

Each new species has the same option at the next toss of the coin. That’s it. In perl it would look something like this:

sub tree {
    my $tree = {};
    my @nodes = ($tree);
    while (@nodes) {
        my $node = shift @nodes;
        if (rand >= 0.5) {
            my $l = {};
            my $r = {};
            $node->{l} = $l;
            $node->{r} = $r;
            push @nodes, $l, $r;
        }
    }
}

sub tree {

my $tree = {};

my @nodes = ($tree);

while (@nodes) {

my $node = shift @nodes;

if (rand >= 0.5) {

my $l = {};

my $r = {};

$node->{l} = $l;

$node->{r} = $r;

push @nodes, $l, $r;

}

So there’s a 1/2 probability that the thing will never get started, and you’re left with a stump rather than a tree. But with 2 children, there’s only a ¼ chance that they will both die out, and if they both survive then there are 4 grandchildren, and so on. This code has a definite probability of running forever.

It turns out that if you run this a large number of times, and add up the number of each depth reached, you get a curve that asymptotically approaches zero at infinity:

The graph is normalized so the trees of depth zero come out at 0.5. The little kick at the right is those that reached the maximum depth in my test.

So what do these trees look like? I’ve given the game away by using a picture of one of them as the featured image for this post. As for generating the images, the excellent GraphViz comes to our rescue. With a little jiggery-pokery we can get the above perl code to produce a .dot file that we can feed to GraphViz and get a picture. I’ve extended the code to color nodes and vertices red if they are “survivors” (have descendents at the limiting depth) and black if they represent a species with no descendants. I’ve also changed the code to try again repeatedly until it generates a tree that reaches a limiting depth. Here’s a representative:

The limit was set at 60, so assuming 2 million years to create a species (I remember that figure from somewhere, I have a bad habit of throwing up unverified facts) this represents about 120,000,000 years of evolution from a single common ancestor. The interesting thing here I think is that the majority of branches don’t make it. Extinction is the norm, even for apparently large and flourishing branches. Apparently insignificant branches can suddenly flourish, and equally suddenly die out. I think this is close to Gould’s vision in general, if not in detail.

The other interesting thing is the huge variety of shapes. Some trees are wide, others are narrow, for example:

In this case all of the survivors share a common ancestor only a few generations (speciations) ago. This could easily be a model for the very earliest life, since the common ancestor of all current life on earth, who’s closest living relative is likely one of the Archaea, is far too complex to be a “first progenitor”.

I don’t know where I’m going with this from here, probably nowhere, but I think it’s interesting.

To finish off, here’s the full implementation of the tree generating code in case you want to try it yourself. You can pick up GraphViz from www.graphviz.org and run it from the command-line (the commands are called dot , neato , circo etc.) or via a gui.

#! /usr/bin/perl

use strict;
use warnings;
use Carp qw(confess);

use constant MAX => 50;

my $max = shift || MAX;

sub heads {
    return rand > 0.5;
}

sub iterate {
    my ($sub, @nodes) = @_;
    while (@nodes) {
        my $node = shift @nodes;
        push @nodes, $sub->($node);
    }
}

sub mark_ancestry {
    my ($node) = @_;
    while ($node) {
        return if $node->{survived};
        $node->{survived} = 1;
        $node = $node->{parent};
    }
}

sub free {
    my @nodes = @_;
    iterate(sub {
        my ($node) = @_;
        $node->{parent} = 0;
        return $node->{l} ? ($node->{l}, $node->{r}) : ();
    }, @nodes);
}

sub cull {
    my ($tree, $depth) = @_;
    iterate( sub {
        my ($node) = @_;
        if ($node->{depth} == $depth) {
            if ($node->{l}) {
                free($node->{l}, $node->{r});
                $node->{l} = $node->{r} = 0;
            }
            mark_ancestry($node);
        } elsif ($node->{l}) {
            return ($node->{l}, $node->{r});
        }
        return ();
    }, $tree);
}

sub make_tree {
    for (;;) {
        my $tree = {
            n => 0,
            live => 1,
            depth => 1,
            parent => 0
        };
        my @nodes = ($tree);
        my $n = 0;
        my $maxdepth = 0;

        while (@nodes) {
            my $node = shift @nodes;
            if ($node->{depth} == $max) {
                cull($tree, $max);
                return $tree;
            }
            if (heads) {
                my $l = {
                    n => ++$n,
                    depth => $node->{depth} + 1,
                    parent => $node,
                };
                my $r = {
                    n => ++$n,
                    depth => $node->{depth} + 1,
                    parent => $node,
                };
                $maxdepth = $node->{depth} > $maxdepth
                          ? $node->{depth}
                          : $maxdepth;
                $node->{l} = $l;
                $node->{r} = $r;
                push @nodes, $l, $r;
            }
            else {
                $node->{died} = 1;
            }
        }
        free($tree);
    }
}

sub print_tree {
    my ($tree) = @_;
    print "digraph G {\n";
    iterate(sub {
        my ($node) = @_;
        my $fillcolor = $node->{survived}
                      ? 'red'
                      : $node->{died} ? 'black'
                                      : 'blue';
        print '    N' . $node->{n}
            . qq' [label="", style="filled",'
            . qq' fillcolor="$fillcolor" shape="circle"];\n';
        if ($node->{l}) {
            my ($lcolor, $rcolor) = ('blue', 'blue');
            $lcolor = 'red' if $node->{l}{survived};
            $rcolor = 'red' if $node->{r}{survived};
            print '    N' . $node->{n}
                . ' -> N' . $node->{l}{n}
                . qq' [ color="$lcolor",'
                . qq' arrowhead="none" ];\n';
            print '    N' . $node->{n} . ' -> N'
                . $node->{r}{n}
                . qq' [ color="$rcolor",'
                . qq' arrowhead="none" ];\n';
            return ($node->{l}, $node->{r});
        }
        else {
            return ();
        }
    }, $tree);
    print "}\n";
}

print_tree(make_tree);

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

#! /usr/bin/perl

use strict;

use warnings;

use Carp qw(confess);

use constant MAX => 50;

my $max = shift || MAX;

sub heads {

return rand > 0.5;

}

sub iterate {

my ($sub, @nodes) = @_;

while (@nodes) {

my $node = shift @nodes;

push @nodes, $sub->($node);

}

sub mark_ancestry {

my ($node) = @_;

while ($node) {

return if $node->{survived};

$node->{survived} = 1;

$node = $node->{parent};

}

sub free {

my @nodes = @_;

iterate(sub {

my ($node) = @_;

$node->{parent} = 0;

return $node->{l} ? ($node->{l}, $node->{r}) : ();

}, @nodes);

}

sub cull {

my ($tree, $depth) = @_;

iterate( sub {

my ($node) = @_;

if ($node->{depth} == $depth) {

if ($node->{l}) {

free($node->{l}, $node->{r});

$node->{l} = $node->{r} = 0;

}

mark_ancestry($node);

} elsif ($node->{l}) {

return ($node->{l}, $node->{r});

}

return ();

}, $tree);

}

sub make_tree {

for (;;) {

my $tree = {

n => 0,

live => 1,

depth => 1,

parent => 0

};

my @nodes = ($tree);

my $n = 0;

my $maxdepth = 0;

while (@nodes) {

my $node = shift @nodes;

if ($node->{depth} == $max) {

cull($tree, $max);

return $tree;

}

if (heads) {

my $l = {

n => ++$n,

depth => $node->{depth} + 1,

parent => $node,

};

my $r = {

n => ++$n,

depth => $node->{depth} + 1,

parent => $node,

};

$maxdepth = $node->{depth} > $maxdepth

? $node->{depth}

: $maxdepth;

$node->{l} = $l;

$node->{r} = $r;

push @nodes, $l, $r;

}

else {

$node->{died} = 1;

}

free($tree);

}

sub print_tree {

my ($tree) = @_;

print "digraph G {\n";

iterate(sub {

my ($node) = @_;

my $fillcolor = $node->{survived}

? 'red'

: $node->{died} ? 'black'

: 'blue';

print ' N' . $node->{n}

. qq' [label="", style="filled",'

. qq' fillcolor="$fillcolor" shape="circle"];\n';

if ($node->{l}) {

my ($lcolor, $rcolor) = ('blue', 'blue');

$lcolor = 'red' if $node->{l}{survived};

$rcolor = 'red' if $node->{r}{survived};

print ' N' . $node->{n}

. ' -> N' . $node->{l}{n}

. qq' [ color="$lcolor",'

. qq' arrowhead="none" ];\n';

print ' N' . $node->{n} . ' -> N'

. $node->{r}{n}

. qq' [ color="$rcolor",'

. qq' arrowhead="none" ];\n';

return ($node->{l}, $node->{r});

}

else {

return ();

}

}, $tree);

print "}\n";

}

print_tree(make_tree);

fractals, Graphics

flam3-0000-0018

Image February 23, 2014 Bill Leave a comment

Graphics, Ray-Tracing

Tea

Image February 22, 2014 Bill Leave a comment

This one took a while to do. The image is a golden rectangle, each component occupying the next square. It is lit using a homemade light probe, and the wooden surface is just a texture with surface normals, rather than real 3-D. There’s a slight focal blur to stop the texture drawing the eye out of the top of the frame.

fractals, Graphics

Flame-4-0039

Image February 19, 2014 Bill Leave a comment

fractals, Graphics

flame-0018

Image February 19, 2014 Bill Leave a comment

Graphics, Ray-Tracing

The Mk. II

Image February 18, 2014 Bill Leave a comment

I was (usually am) more than a bit annoyed by the new style of luggage people are trawling through Kings Cross nowadays, I even saw a fight start when someone tripped over one of these things. I thought this would make a nice poster on a Kings Cross billboard.

Graphics, Ray-Tracing

Red Glass and Silver

Image February 18, 2014 Bill Leave a comment

cross-eye Stereogram

Graphics, Ray-Tracing

FlickrSpheres

Image February 18, 2014 Bill Leave a comment

This went through a few iterations before the final image. The code on the plane is the code that was used to create the image, screen-grabbed as a tiff and used as a repeating tile. I’m not smart enough to figure out how to write a syntax-highlighter in POV-Ray.

Graphics, Ray-Tracing

Dune

Image February 18, 2014 Bill Leave a comment

Not my best, the models are fully articulated though, in fact that’s the only way to do these kinds of things, it would be near impossible positioning each component separately if they weren’t connected.

Bill Hails

All posts by Bill

MVC – Man Vs. Computer

Lessons Learned

So You Feel Lucky?

flam3-0000-0018

Tea

Flame-4-0039

flame-0018

The Mk. II

Red Glass and Silver

FlickrSpheres

Dune

Random Blogs