This Blog Has Moved! Visit chriswarbo.tk instead!

Closures vs. First-class functions vs. Higher-order functions

2011-05-02T18:08:00.005+01:00

This is a reply to http://notes-on-haskell.blogspot.com/2007/02/whats-wrong-with-for-loop.html which tries to make the point that closures are a good thing, but ends up not mentioning closures at all in the argument ;) My reply was too long for Blogger, so I've posted it here, since I think it's interesting on its own too.
Note that the examples here are written in Python, and I've put "...." to represent indentation, since the Blogger post editor is terrible at HTML (it second-guesses me every time, surely if there is a "HTML" tab then the "Composer" tab shouldn't be for HTML? But writing escaped HTML entities just makes them appear verbatim in their escaped form >:( )

As has been stated above, the article uses first-class and higher-order functions, without actually making use of closures.

The difference is that closures contain an environment, which can be modified by the code in the closure. Thus calling a closure over and over with the same arguments won't always give you the same results.

My Java's a little rusty, so I'll give some examples in Python. Let's say we want to sum a list of numbers. The first-class function approach, shown in the article, relies on the concept of a "sum" function for adding values, and a "reduce" function for walking the list:

def sum(x, y):
....return x+y

total = reduce(sum,my_list)

The way we would approach this with closures would be to define an "accumulate" closure. This is like the "sum" function but instead of taking 2 arguments and returning their sum, it takes 1 argument and adds this to its own internal state. We can then use "map" to apply it to my_list:

def make_accumulator():
....running_total = 0
....def acc(a):
........running_total += a
........return running_total
....return acc

accumulator = make_accumulator()

map(accumulator, my_list)

total = accumulator(0)

Python's scoping rules are a little weird, so I'll walk through this. First we create a first-class function object and call it "make_accumulator". Whenever this function is called, it creates 2 objects in its internal namespace; a number object called "running_total" and a function object called "acc".

Crucially, Python's name resolving works from the inside out: any code can access variables defined in a 'parent' namespace (as long as this name hasn't been overridden in the local namespace), but cannot access any local namespaces defined inside it (eg. the namespace of an inner function).

Thus "acc" has complete access to the "running_total" variable, and thus the function is free to increment running_total by whatever argument it is passed.
"acc" isn't yet a closure, since the body of "make_accumulator" is also free to change the value of running_total, although in our case it simply returns the "acc" function object.

Next we call "make_accumulator" and bind the function it returns to the variable "accumulator". It is actually this binding that makes "accumulator" a closure, rather than a regular function!

In order to be a closure, "acc" functions (like the one bound to "accumulator") need exclusive control over ('to close over') their internal environment, which in this case is "running_total". As long as "make_accumulator" is running, this is not the case. Once it finishes then the function obtains complete control over running_total and becomes a closure. If the result is discarded, however, the "acc" closure just gets garbage collected and is useless. However, if we bind it, like we do to "accumulator", we have a function with internal state. (Note that calling "make_accumulator" again will create new, independent instances of "running_total" and "acc", so our closures retain complete control of their own instances of running_total).

With this closure in hand we then run every value of my_list through it using "map". This returns a list of each intermediate result, but we don't care about them (except for the last one) so they're discarded.

To recover the final result we call the closure again, but with an identity value (0 is the identity for addition). This gives us our result.

Note that closures don't have to return their state when called. For example we could make a closure that returns its argument, but negates it on alternate calls:

def make_flipper():
....is_odd=True
....def flipper(x):
........is_odd = not is_odd
........if is_odd:
............return x
........else:
............return -1 * x
....return flipper

f = make_flipper()
print str(map(f,[0,1,2,3,4,5]))

This would output "[0,1,-2,3,-4,5]" (since -1 * 0 = 0)

Of course there are parallels to be made between closures (functions with internal values) and objects (values with internal functions ('methods')). It's been said that closures are a poor man's objects, and that objects are a poor man's closures. Still, they're another useful tool to have available, especially if they're done in a less clunky way than in Python (which seems like a useful side-effect of the scoping rules, rather than an explicit design decision).

Python Decompiler Performance

2011-04-12T21:23:00.002+01:00

I knew the performance of Python Decompiler was rubbish, but I didn't realise how rubbish! Based on the code analysis I wrote about last time, I've put the node classes in order of frequency and reordered the comparisons made in "thing" to match this. That's all I've done, and it's given a 58% speed increase and a 47% RAM decrease compared to the alphabetical order! Running the tests file on itself now only takes 16 seconds and 69MB of RAM. If I compare it to before I had a go at optimising, back before it used the input stream as a stack, the current code takes 64% less time and 66% less RAM.

Nice!

Code, as always, is on Gitorious :)

Some Python Stats

2011-04-09T15:50:00.003+01:00

I realised today that there's a really easy-to-fix bottleneck in my Python Abstract Syntax Tree decompiler. The decompiler looks for "things", and for each "thing" it checks against a list of alternatives to see what it might be (and hence how to decompile it). This list is ordered, so it checks against the first rule, if it doesn't match then it checks against the next rule and so on until it either finds a match, or it runs out of rules to check against (and throws an error).

This ordering of the checks, specifically ordered choice, is what defines Parsing Expression Grammars as a deterministic counterpart to Backus-Naur Form, along with greedy matching.

There are two quirks of my Python decompiler, however, that can be used to our advantage to make it faster really easily.

Firstly, if the choice were not ordered, as in Backus-Naur Form, there is only one instance of nondeterminism, which happens for deletion. Thus, as long as deletion comes first, we can actually rearrange the other rules however we like.

The second quirk is that I have implemented the rules pretty much in accordance with the classes of AST nodes used in Python's compiler module. This means that we can predict the chances of each match succeeding by simply parsing existing Python code and counting up the number of times each node occurs.

I've written a quick script to do this counting, which you can find here. To use it, you need to provide a list of Python files for it to check. I did this for my whole operating system by running the command 'find / -name "*.py" > ALL_PYTHON_FILES' which will (after some time and "permission denied" warnings) give you a list called "ALL_PYTHON_FILES". For me this list contains 25,087 files.

Whilst the node_counter.py script runs reasonably quickly, I keep getting a segmentation fault with around 23,700 files to go. For this reason, I've also given it an optional second argument, which is the number of files to use from the given list. These are picked at random from throughout the file, to prevent it grabbing everything from the same project and thus biasing the results.

The script outputs a spreadsheet which contains each type of node and the number of times it was found in the files it checked. I used Gnumeric to work out some percentages and collate the results from running it against 1 file, 10 files, 100 files and 1000 files, and generated the following (which you can find the source for here)

The green lines are the most accurate, since they're from the sample of 1000 files; the others are there to give an indication of the variance, because I couldn't be bothered to work out the standard deviation.

What this shows us is that we can't guess what kind of node a given "thing" will be, since none of these is above 0.5 (ie. 50%), but what it does show is that some types of node are far more common than others. We can see that Name nodes (which represent the "x" in "x = 5", for example) are used all over the place, such that around 30% of the nodes are Names. Getattr is probably the next-most-used node (which represents the ".foo" in "bar.foo = 8") and the frequency rapidly decreases until we get some very niche nodes like Ellipsis which don't occur at all. Note that some classes, like "Expr" and "Node" will always show zero since they're superclasses that aren't directly instantiated by the compiler.

So what does this mean for performance increases? It means that by putting the node types in order of frequency, we can make the most common cases match after only a few attempts, whilst sacrificing the performance of rarely used classes.

Since this script is part of the Python decompiler, it's Public Domain. If it's of any use to you, go ahead and take it :)

Dear World

2011-04-08T23:32:00.004+01:00

Have you *STILL* not realised that everything you ever put online is up for grabs? Just because someone spouts some bullshit phrases like "privacy settings", "passwords", "secret questions", etc. doesn't change this fact. What we do know is:

1) It's not known if computer security is even possible in theory.

2) Even if computer security turns out to be possible, then implementing it correctly is still a difficult problem.

3) Even if computer security is possible, and someone manages to implement it correctly, you have no idea if they're lying unless you have full access to all parts of the code and environment.

4) Even if computer security is possible, and someone manages to implement it correctly, and this can be verified, then you sure as hell shouldn't give them any stuff you care about, because they'll put in in a system that's theoretically sound, verified, correct and proven to be able to stop you ever getting it back. In short, you'd be fucked.

Whilst all software fails the first test, and most software fails the second test, Dropbox also fails the third and fourth. Don't use it, or anything like it, for anything private. If you still want to upload stuff then there are plenty of Free Software programs for doing so, ie. they pass tests 3 and 4.

Yes, I know that banks, credit card companies and the like send transactions over the Internet, but that doesn't mean that doing so is secure. It means that doing so is cheap. So cheap, in fact, that they can afford to pay for insurance to cover all of the fraud that happens on the system every day.

Update: DropBox are now being investigated for false advertising. What's the false claim they made? That they're secure. Specifically, DropBox claimed that their employees cannot access any of the data stored in their system, which turns out to be complete bollocks. The investigation is being made since DropBox has provided a simple, quick, insecure system but presented it as a simple, quick, secure system; whilst companies attempting to create real secure systems, which inevitably end up less simple and quick than DropBox, have been left in the dust by DropBox.

The moral of the story is to run your own clustered filesystem, or if speed isn't your main concern then use FreeNet.

Abstraction Fail

2011-04-08T14:04:00.004+01:00

Loading Javascript in a Web page. Pretty high-level stuff. Isn't it fun to live in a world without endianness, memory allocation, GOTO, compilation, packets, out-of-order message arrival, unreliable streams, network addresses, filesystems and all of that other low-level crap? We can float in our clouds high above it all :)

Except when Facebook Connect doesn't work in IE because of an OS bug in the networking stack. The network layer in Windows XP can throw away incoming data if it is a) "chunked" (ie. split into sections) and b) compressed. Since missing data causes the decompression to fail, this results in compressed data being sent to the browser, which subsequently ignores it as incomprehensible gibberish. Thus Facebook Connect didn't work. Bloody Microsoft >:(

If you've been hit by this, there's no solution I know of. As a workaround, you may be able to try swapping from HTTP to HTTPS or HTTPS to HTTP in the URL you're referencing, but of course that will only work if a) the server you're contacting supports HTTP and HTTPS (Facebook does, thankfully), b) the one you switch to doesn't trigger this bug as well and c) you don't give a crap about using SSL.

PyMeta Stacks

2011-04-02T17:44:00.004+01:00

As you may know if you've been following my blog, I've been working on a project for a few years called, rather glamorously, "python decompiler". I've released it into the Public Domain and you can find it on gitorious.

The idea is that compiling software (translating it from one form to another) is a mathematical operation, and that for every mathematical operation we would like to know its inverse. Version 2 of Python contains a compiler, which creates Abstract Syntax Trees (ASTs) out of Python code, but there is no reverse transformation to be found. That's what python decompiler does; it takes an AST and produces Python code that will compile into that AST, thus compile(decompile(compile(code))) is the same as compile(code). We can't quite make decompile(compile(code)) match the original code since the compiler throws away information ((((((like redundant brackets)))))).

So how does it work? I've used the PyMeta library, a Python implementation of the OMeta pattern matching system. This is applied to the AST, and pattern-matches against AST node objects. The only difficulty with doing this is that a OMeta is designed for pattern-matching against an iterable object, such as a string of text, a list of objects, etc. and I want to use it to pattern-match recursively inside objects, preferably without blowing those objects apart into a serialised form beforehand.

The original way I did this was to instantiate a new pattern matcher on every child object, so for example the Python code "1 + 2 * 3 / 4 - 5" will produce an AST a bit like "Sub(Add(Const(1),Div(Mul(Const(2),Const(3)),Const(4)),Const(5))". The classical way to pattern-match such a tree is to make a rule that matches "Sub(A,B)" where "A" and "B" are themselves other rules, and so on. This recursion of rules is great for digging out structures like the AST I've written out as text above, however in Python we've got a structured system of objects that a) doesn't need constructing (it's already structured) and b) has encapsulated innards, which makes pattern-matching against the structure tedious (although Python's introspection makes it reasonable, at least). Since Python is a dynamic language we would also like to avoid having to look at the inside of objects, since that would make the code less flexible than if it implies the contents. By making new pattern matchers, rather than defining new rules, we get arbitrary nesting ability and don't have to look inside objects (they look inside themselves, recursively). The drawback to this is that every single node in the AST needs its own pattern matcher, which takes ages to run (since OMeta pattern matchers are bootstrapped from the ground up in themselves) and eats up tons of RAM.

I received a couple of emails about python decompiler the other day, so it seems that people may be playing with it after all. To that end, I decided to have a bit of a think about improving its efficiency, and realised that I could get the required recursion if I turn the input stream into a stack. This is suprisingly easy to do, and straightforward to use (as long as you make sure the stack will be clean when you're finished, regardless of if your rules match or not!). We add the following function to a newly constructed grammar (which is a class in PyMeta):

def ins(self, val):
...self.input.data.insert(self.input.position+1, val)
...self.input.tl = None
...self.input.memo = {}
grammar.ins = ins

(I've written "..." to represent indentation. Silly blogger HTML editor.) 5 lines is all it takes, but now we can push on to a pattern matcher's input stream from within the grammar. We do this by calling Python code from within a rule, by wrapping it as !(code). Thus we just have to call !(self.ins(a)) and "a", whatever it is, will be the next thing on the input stream, so we can match against it. This turns the input stream into a stack, and makes OMeta recursive whilst only needing 1 pattern matcher object.

I've now converted python decompiler to use this form. I've run some quick tests by getting python decompiler to compile, decompile and recompile its own test file, and check the results for validity. The previous method managed, using the "time" utility and KDE's system monitor, take 44 seconds and 202MB of RAM. This is a completely stupid amount of resources for text processing, even in an interpreted language. After the change it now takes 38 seconds and 129MB RAM. That's not a great speed improvement (14%), but the memory usage is much better (a 36% reduction). I'm sure I can get this down even more with a little playing :)

Enigma Number 1628

2011-01-22T12:02:00.002Z

Was reading through New Scientist and thought I'd have a go at their "Enigma" puzzle, which I've always glossed over since they're pretty difficult maths. However, since I've got a computer I thought I'd see what the answer is anyway.

The question is this: raising a number to the power of itself is like 5 to the power of 5, or 5**5 in Python; a 'reverse' number is a number with its digits backwards, so 45 is the reverse of 54; a number that ends with another means that the least significant digits of the former are the same as all of the digits of the latter in the same order. Given this, what is the 2 digit number x such that x raised to the power of x ends with x, the reverse of x raised to the reverse of x ends with the reverse of x, the reverse of x raised to the power of x ends with the reverse of x and the digits in x aren't the same?

Translating this into Python is quite simple. We start with all of the possible answers, ie. the numbers 00-99, which we get via range(100). Next we can split them into a pair of the "tens and units" as they used to say in primary school. We do this with [(a/10,a%10) for a in range(100)]. Next we can put these back into a list of numbers by undoing the separation of the digits, like this [x*10+y for x,y in [(a/10,a%10) for a in range(100)]]. Next we want to put our filters on this. Namely, the 2 digits x and y cannot be equal, so x!=y; the number raised to itself, (x*10+y)**(x*10+y), must ends with itself, ie. ((x*10+y)**(x*10+y))%100==x*10+y; the same must be true for the reverse, where we just swap x and y; and the reverse to the power of the number, (y*10+x)**(x*10+y), must end in the reverse, y*10+x, so ((y*10+x)**(x*10+y))%100==y*10+x. Putting it all together we get a list of answers:

[x*10+y for x,y in [(a/10,a%10) for a in range(100)] if x!=y and ((x*10+y)**(x*10+y))%100==(x*10+y) and ((y*10+x)**(y*10+x))%100==(y*10+x) and ((y*10+x)**(x*10+y))%100==(y*10+x)]

Easy :)

PS: The answers are 16, 61 and 57

More ocPortal Thoughts

2010-12-19T16:03:00.003Z

I've just finished a 0.1 version of my Flattr addon for ocPortal, which means that I'm looking for a new project to hack on. I've created a list of ideas in Basket, which includes many of the things I mentioned in my last post. Since I've taken some time off over Christmas I thought I'd try and make a start on getting ocPortal integrated with the Federated Social Web framework that's emerging. This includes:

WebFinger support: WebFinger is an extension of the classic UNIX finger utility. It allows arbitrary data to be associated with an email address. There are 2 parts to this: ocPortal can take advantage of WebFinger data by populating profiles with existing public information, and it can produce WebFinger data by making public profile information available to services looking for it.

Salmon support: Salmon allows content to flow upstream (ie. towards the source). It means that, for example, a news article can be syndicated by many different sites, and comments from all of them will be sent upstream to the source. There's an issue here with comment spam, since we would like this to be automatic (ie. CAPTCHA wouldn't work), but once the protocol is supported we can keep it turned off until we work out a solution to spam.

PUbSubHubbub: This is a publish-subscribe mechanism, similar in principle to XMPP PubSub which I wrote a library for a couple of years ago. This allows arbitrary content to be sent downstream to everyone subscribed to a source. For example, it allows comments on a news article to be sent to everyone who is syndicating it. Combined with Salmon, this allows content like comments on a republished article to be sent upstream to the original, which can then push them out to everyone who's republished that article.

OStatus support: This is a group of standards made to interoperate with each other. It allows users on different sites to follow each other's activity, comment and converse. There's a really clear breakdown of how to make a site/application/service OStatus capable. The nice part is that each step towards integration gives useful functionality. This depends on WebFinger, Salmon and PUbSubHubbub support, if we want to support the whole lot.

There are some ocPortal hacks knocking around in Subversion to log user activity in a "Bob made a comment on Foo" way, so this could be piped into any social web structure I manage to put in place. Ideally, ocPortal should be able to pass the SWAT0 test.

If I manage to get some of the above done then I might have a go at turning ocPortal into a Diaspora "pod". From what I can tell, this also requires WebFinger and Salmon support, but the only documentation I can find for Diaspora's message-passing interface is pretty sparse. When I do get around to this I think I'll have to have a chat with some Diaspora devs.

Oh well, time to install Apache, MySQL, PHP and ocPortal on my XO :)

UPDATE: Holidays are over. I've done a lot of reading of specifications, and I've started hacking the "Salmonpress" plugin for WordPress into ocPortal. This also includes a skeletal use of WebFinger and, the main reason I chose it, "Magic Signatures". I've cleaned up the code to remove WordPress-specific stuff, mostly put ocPortal replacements in place, and have got rid of its stupid use of classes and static methods (otherwise known as functions, which is what I've turned them into). Haven't worked out the best way to get this working for all content types (or as much as possible) yet. Also, didn't need MySQL on my XO, I used ocPortal's built-in XML database :)

Blog Dump 8: Building a Language

2010-12-14T21:13:00.003Z

We want a high-level language. We want it to have objects. We want it to be dynamic (latent typing). We would like it to be functional. We want it to be pure; both in an object-oriented sense (everything is an object, there are no 'built-in types' or objects which differ in implementation from user-created objects) and in a functional sense (we don't want implied state or mutable values, we want referential transparency, we want functions which take one object and return one object, we want currying).

To do this we should use an Id object system:

The master object is defined as a reference to another object (eg. a pointer) and some (unknown) contents. Thus we can say the type of an object is:

type(object) := (reference × contents)

This object can be used as a prototype by a function we'll call clone:

clone :: object -> object
clone :: (reference × contents) -> (reference × contents)

The cloned object's reference points to the cloned-from object, whilst the contents of the object should be independent of any other. We can't initialise it with default values, since they're to be immutable and thus we'd never get a non-default object! We must therefore forget about this object's contents until they're set or accessed, which requires us to be lazy in some respect. We don't neccessarily need to use lazy computation, delaying all computation until we know everything we need to. We could deal with memory allocation and such if we knew the size of the object, or if we had functions in place to reallocate memory when the contents become more defined.

Every reference is an object, every reference points to an object and every object contains a reference. This gives a large number of objects, but we will not reduce this in the design phase.

To specify the behaviour of an object we look in its vtable, which is what the reference points to. A vtable is also an object, since we want a pure object system. Thus we have to make the root object somehow, ensuring that the mechanisms used to do so can be coerced into objects afterwards. This, once again, relies on a lazy approach to data:

# Get an 'empty' (ie. undefined) object
object = make_raw_object()
# Make another empty object
object_vtable = make_raw_object()
# Use this second object to describe the behaviour of 'object'
give_reference(object, ref_to(object_vtable))
# Now make a third empty object
vtable_vtable = make_raw_object()
# This third object describes the behaviour of behaviour objects
give_reference(object_vtable, ref_to(vtable_vtable))
# Since the third object is a behaviour, it describes itself too
give_reference(vtable_vtable, ref_to(vtable_vtable))

Now we have the Id object model: everything is an object, our objects have a reference to some behaviour (vtable) along with some contents. Each object has a behaviour (object has object_vtable, object_vtable has vtable_vtable and vtable_vtable has vtable_vtable). We have used functions 'make_raw_object', 'ref_to' and 'give_reference'. Not only are these are impure (they are not in our object model, and are probably not even objects if we're using a low-level starting point), but they also break the object system by allowing new object hierarchies to be defined! Thus these should not exist in the final system, which is OK since they are not needed after we have bootstrapped the object system; thus they can live in a bootstrap compiler which can be thrown away once it's compiled a native compiler.

Now we have a skeletal object hierarchy
object -> number -> integer -> natural
object_vtable -> num_vtable -> int_vtable -> nat_vtable

object -> vtable -> num_vtable -> int_vtable -> nat_vtable
object_vtable -> vtabl_vtabl -> vtabl_vtabl -> vtabl_vtabl -> vtabl_vtabl

object -> vtable -> vtable_vtable
object_vtable -> vtable_vtable -> vtable_vtable
Now we loop the hierarchy around so that the vtable's reference points to vtable_vtable:

This is where the post trails off. From a quick skim I'm pretty certain I've got Id right so far, although I've stopped short of mentioning anything directly functional (eg. function objects, continuations, etc.). Maybe I'll finish this off some time.

Blog Dump 7: Reasoning & Proof

2010-12-14T20:40:00.001Z

Code is formal mathematical notation, defined only from the axioms specified by the language. Compilers and interpreters are assumed to make-good these axioms based on the axioms of their own implementation. At some point the axioms become the specification of a machine, wherein the machine is assumed to make-good those axioms based on either further axioms of languages (if we're in an emulator), or through the laws of Physics (if we've got physical hardware). Any failure of these axioms results in undefined behaviour of the code. Thus, it is justified to formally study programs with very high-level axioms by assuming that they're true. We can check them later, of course, by studying the implementations. Thus we don't need, even through we can have if we want, a full proof of a program's execution right down to the metal. We just need to prove what it implements given the axioms of its language. Given such high-level axiomatic specification of a language, it is straightforward (if computationally expensive and undecidable) to compare specifications and programs in any relevant language.
The issue becomes what language to use for specifications and axioms. Here there is no point inventing yet another new language, and it would be best to use a declarative language. Standard Mathematical notation, such as propositional logic, Hoare logic, Lambda calculus, etc. would suffice.
An important issue is the structure of our types, as there are two ways we would like to exploit it. We would like to be able to hack our type system when convenient, which requires knowledge of type internals. For example, if we know that C's integers are stored as a list of 32 bits then we can use the individual bits via bit masks, bit-wise operations and even via decimal equivalents. If we treat types only as the concepts which they embody then we can use more high-level reasoning like "this is an integer", and therefore apply whatever we know about integers (including swapping the implementation for a different integer representation, which breaks any hacks being used).

Knowledge should be completely bottom-up. Specify as many facts (triples) as you can, and at some point higher-order patterns may fall out. If they don't, then we write more triples. The reasoning approach should be a 'destructive' one, based on filtering. For example, a 'constructive' approach would construct a path for inference like 'trees are plants and plants are living, therefore trees are living'; whilst a 'destructive' approach would describe the undefined concept of 'tree' by saying 'X is a tree, X is a plant, X is alive'. This is less reliable than the 'constructive' approach (which can also be used), but allows us to use learning like a human: a child sees a red ball and is told "red". As far as the child knows, red balls are "red" but the word "red" could describe its shape, its size, its colour, etc. These possibilities are narrowed down (filtered, destroyed) by describing a red car as "red", a red traffic light as "red", etc. With enough examples of "red", there are enough filters to narrow down what is meant. A red ball and red traffic light are both round, perhaps that is what "red" means? No, because a red car is not round, thus "red" is not the shape. In the tree example we can say 'trees are plants', which narrows down the scope of what trees might be. We can say 'trees are alive'.

The advantage is that we have an implied generality: we don't have to choose whether a particular object is one colour or another, we can say it's both. We can say that white wine is "white", which it is, without having to worry about breaking an ontology by 'misusing' the adjective 'white'. The lack of focus lets the system 'keep an open mind'. It can clarify things and verify its own inferences by asking questions, in order of the impact of the answer (ie. whether yes or no will make the biggest differentiation of the emerging ontology): 'Is a pineapple a tree?', 'Are plants alive?', etc.

If the system is going wrong for some reason, eg. asking a string of ridiculous inferences, and its own differentiation checker isn't stopping it, then the problem is simple: more triples need to be given explicitly.

Reusing URIs is a good idea, so we can have the system search out existing ontologies and instantiations, then ask things like: "are trees plants in the same way that cars are vehicles?". In that case we've said 'trees are plants' and it has found an ontology which says 'cars are vehicles' and is wondering if the relationship is the same, ie. if it should reuse the URI of the predicate. In a grahical way we could offer a multitude of possibly preexisting definitions, along with tick boxes to indicate which ones are similar.

Blog Dump 6: The Web of Code

2010-12-14T20:28:00.000Z

The original World Wide Web consists of big lines of text, called pages, which, by virtue of some ill-defined, external set of rules, somehow manage to contain knowledge. The pages can point to other places on the Web for whatever reason, and to a person this is great. However, to a machine it's just a bunch of numbers with no discernable meaning.

Mixed in with this knowledge are various well-defined, machine-understandable properties which originally denoted the presentation of the text (eg. 'b' for a bold bit, 'i' for an italic bit, etc.) but which gradually changed to instead merely split it up in various ways (eg. 'em' for a bit that needs emphasising, 'strong' for a bit which is important, etc.). The knowledge in the text, however, is still lost to the machine processing it.

This means that a person has to be involved somewhere, requiring a load of unfortuate individuals to navigate through the shit user interface of the Web, reading everything they find, until they get the bit of knowledge they were after.

These days we have search engines which slightly lessen the burden, since we can jump to places which we, as people, have reason to believe are pretty close to our destination and thus shouldn't require much navigating from. Still, though, the machines don't know what's going on.

In the Web of Data we entirely throw away the concept of a page, since it's irrelevant to our quest for knowledge. Text can be confined to pages, but knowledge can't; knowledge is pervasive, interconnected, predicated, higher-order and in general we can't contain a description of anything to a single unit without reference to other things, the decriptions of which reference other things and we end up with our 'page' on one thing actually containing the entire sum of all knowledge. Since there's only one sum of all knowledge, we don't need to use a concept like 'page' which implies that there is more than one.

With the artificial limit of pages done away with we can put stuff anywhere, as long as we use unique names (Universal Resource Identifiers, URIs) to make sure we don't get confused about which bits are talking about what. Now we've got a machine-readable, distributed, worldwide database of knowledge: that's the Web of Data.

At this point many short-sighted people think that the next step is to rewrite the old Web on top of the Web of Data, so that both humans and machines can understand it and work in harmony. These people are, of course, sooooo 20th century.

Machines aren't intelligent (yet), so there's no way we could make a serious moral argument that they are our slaves. Therefore, why aren't they doing everything? There should be no relevant information kept back from the machine, and nothing it outputs should contain any new knowledge which can't already be found on the Web of Data. If we want to refine what it programatically generates, we should do so by adding new information to the Web of Data until it knows what we want, and thus nobody else need specify that data again.

To me, as a programmer, there is an obvious analogy to be made:

The original coding system consists of big lines of text, called files, which, by virtue of some well-defined, external set of rules, somehow manage to contain computation. The files can import other files in the system for whatever reason, and to a person this is great. However, to a machine it's just a bunch of calculations with no discernable meaning.

Mixed in with this computation are various well-defined, machine-understandable properties which originally denoted the representation of the data (eg. 'int' for a 32bit integer, 'double' for a 64bit rational, etc.) but which gradually changed to instead merely split it up in various ways (eg. 'class' for a bit that contains related parts, 'module' for a bit which is self-contained, etc.). The computation in the text, however, is still lost to the machine processing it.

This means that a person has to be involved somewhere, requiring a load of unfortuate individuals to navigate through the shit user interface of the system, reading everything they find, until they get the bit of calculation they were after.

These days we have search engines which slightly lessen the burden, since we can jump to places which we, as people, have reason to believe are pretty close to our destination and thus shouldn't require much navigating from. Still, though, the machines don't know what's going on.

In the Web of Code we entirely throw away the concept of a file, since it's irrelevant to our quest for computation. Text can be confined to files, but computation can't; computation is pervasive, interconnected, predicated, higher-order and in general we can't contain a serialisation of anything to a single unit without reference to other things, the serialisations of which reference other things and we end up with our 'file' on one thing actually containing the entire sum of all computation. Since there's only one sum of all computation, we don't need to use a concept like 'file' which implies that there is more than one.

With the artificial limit of files done away with we can put stuff anywhere, as long as we use unique names (Universal Resource Identifiers, URIs) to make sure we don't get confused about which bits are talking about what. Now we've got a machine-readable, distributed, worldwide database of computation: that's the Web of Code.

At this point many short-sighted people think that the next step is to rewrite the old coding system on top of the Web of Code, so that both humans and machines can understand it and work in harmony. These people are, of course, sooooo 20th century.

Machines aren't intelligent (yet), so there's no way we could make a serious moral argument that they are our slaves. Therefore, why aren't they doing everything? There should be no relevant information kept back from the machine, and nothing it outputs should contain any new calculation which can't already be found in the Web of Code. If we want to refine what it programatically generates, we should do so by adding new information to the Web of Code until it knows what we want, and thus nobody else need specify that process again.

What Is The Web of Code?

The Web of Code is code like any other. However, the operations it performs are not on memory, they are on things in Web of Code. Memory is just a cache. The Web of Code is as high-level and sparse as possible, describing only what it needs to and no more. If we want to alert the user then we alert the user, we do not want to display rectangles and render glyphs, so we do not display rectangles and render glyphs, these are low-level details which can be worked out through reasoning and search on the Web of Code.

ocPortal Ramblings

2010-12-12T04:54:00.002Z

Since I've now been working with ocPortal long enough to get to know its internals pretty well, and which bits are a joy to use and which aren't, I thought I'd write down a few thoughts about what I think works badly, which areas would benefit from attention, what features I'd like to see and what may be possible in the future. Due to ocPortal's nature, as a layer on top of stubborn databases, flaky libraries and inconsistent languages, which needs to offer flashy, dynamic, user-editable coolness in a reliable way, this list will inevitably include low-level and high-level details. My bias is, of course, on the internals, but I am also a Web user so I care about the user-facing parts too :)

The Good (the majority of ocPortal)

Before I get into a rant about the less brilliant parts of ocPortal, I thought I'd make it absolutely clear that these are specific examples picked out because of their annoyingness; they aren't anything like a representative sample of ocPortal as a whole. ocPortal contains loads of really cool features, which make it a really nice platform to code on.

Some examples of this are the "require" systems, which allow you to say "require_code('a')", "require_lang('b')", "require_javascript('c')" and "require_css('d')". This will tell ocPortal that, before your code runs, the page should have access to the code in 'a.php', the language strings in 'b.ini', the Javascript in 'c.js' and the style information in 'd.css'. The major problem this solves is that it's often a bad idea to include some dependency "just in case" it's not been included yet, because this can cause a load of errors about conflicts where the dependency tries to overwrite a previously included version of itself. With ocPortal, these headaches never occur. A similar feature is the "extra_head" function, which allows things (for example, raw Javascript, metadata tags, etc.) to be written into the page's <head></head> section at any point during page generation, rather than having to specify them all at the start.

A related feature is ocPortal's fallback system. Code requested by "require_code" will be taken from the "sources_custom" folder if possible, and if there's nothing which matches then ocPortal falls back to the regular "sources" folder. The same happens for themes, where the "templates_custom" folder of a theme will be checked first, falling back to the "templates" folder, then if there is still no match the "templates_custom" folder of the default theme is checked, and finally the "templates" folder of the default theme is used. The same applies to the "css_custom" and "images_custom" folders. Languages also use fallbacks, going from "lang_custom" of the desired language, to "lang" for the desired language, to "lang_custom" for the default (currently English) and finally to the usual "lang" folder for the default language (English). This makes it very easy to specify, for example, tweaks to a theme (in the theme's *_custom folders), specify a theme's standard behaviour (the theme's non-custom folders), specify new functionality available to all themes (the *_custom folders of the default theme) and keep the original, known-to-work ocPortal defaults intact (the non-custom folders of the default theme). The same is true for the sources and sources_custom, although a little magic here allows you to specify only the additions/changes you want to make, rather than having to make a complete copy of the file first.

ocPortal's abstractions are also nice to work with, namely the database and forum drivers. They are rather leaky and can easily be abused (for example dumping raw SQL into the parameters of a nice abstract function), but as long as this is avoided on the whole, then it can be a handy thing to keep in place when you're in a pickle and need a bit of a hacked solution. It's like the UNIX philosophy that if you take away people's ability to do stupid things, you also take away their ability to do clever things (otherwise known as "giving you enough rope to hang yourself ;) ).

There's a lot more I could write about cool features of ocPortal, like the Tempcode templating language, the hooks system, the AJAX workflows, etc. but I am writing this to talk about what *can* be done, rather than what is *already* done. Let's move on.

The Bad (things which aren't the best way to solve the problems they're for)

I mentioned in the above section that I could have gone on about ocPortal's hooks being a good thing. They are. However, they are also "bad" in that there is the potential for them to be so much more. OK, a little background: a lot of systems in ocPortal aren't really suited to being written in one big chunk, the classic example being site-wide search which has to include bits from every other system. To handle these cases, ocPortal has a feature called "hooks"; instead of putting the desired behaviour in a few strategic places, we instead put a call to every one of the hooks we have for that system. So for example, rather than having a large chunk of search code which will look in the galleries, the downloads, the forums, the news, the catalogues, the users, and so on, we instead say "grab all of the search hooks and run each one". Then, in the "hooks/systems/search" folder of sources (or sources_custom) we can put a new file to deal with galleries, one to deal with downloads, and so on. Since the search says "all of the search hooks", rather than some specific list, we can add new hooks into the folder whenever we like and they'll be used everywhere that the built-in ones are.

Hooks rely heavily on a methodology called "metaprogramming", where a language manipulates some text, adding bits on, replacing bits, etc. just like a regular program, but the text it's manipulating is actually code written in that language, which then gets run. Metaprogramming is really cool, but can get quite confusing quite quickly, so it's usually reserved for when nothing else is available. ocPortal hooks are created through metaprogramming as PHP objects, which are then asked to perform their task. Now, the problem with hooks is that this metaprogramming magic must be invoked each time we want to use a hook or hooks, and there's a lot of duplication in the hooks' contents.

When we design a system we usually try to keep related things together, but we inevitably end up having some similar code split up into various disparate places. With hooks, to me, the problem is that the search hooks have a gallery search. The introspection hooks have gallery introspection. The configuration hooks have gallery configuration. And so on. I think a better Object Oriented way to do this would be to generate large, amalgamated, Katamari-style objects to represent each part of ocPortal (galleries, downloads, catalogues, etc.) which a hook may want (each being defined via a hook, of course), and generate their methods from the current hooks (eg. gallery->search, downloads->search, downloads->introspection, etc.). This also makes it unnecessary to specify which hooks you want to instantiate before using them (an annoyance with the current model), as instead you can just ask ocPortal for a specific hook object (eg. 'search/galleries'), or all objects used by a set of hooks (eg. 'search'). This can be encapsulated behind a single function call like "require_object". Then the methods can be generated and called via proxy methods on the objects. For example if we ran "$galleries = require_object('search/galleries'); $galleries->search($params);" then the call to "search" is intercepted, a relevant hook is looked for and instantiated, then called with $params. That keeps down the overhead of having to generate objects with all hooks instantiated in them to start with. Performing a complete search of the site would be as simple as "$site_objects = get_objects('search'); $results = array(); foreach ($site_objects as $obj) { $results = array_merge($results, $obj->search($params)); }". We could even recurse through all of the hooks, bunging the methods into the generated objects. For example if we were writing part of the gallery system then we might access our desired hooks via "$objects = get_objects(); $search_results = $objects['galleries']->search($params); $relevant_configs = $objects['galleries']->configs();". Here I've used the convention that "hooks/foo/bar.php" will be at the key "bar" in the objects array, and will have the method "foo".

The Ugly (things which are unfortunate, and waiting to be fixed)

At the moment ocPortal has a few historic systems which aren't actually used. For example, there is infrastructure to create new configuration options. This is actually useless, however, since the configuration options are designated via hooks. Such implementation changes have left various cruft around, and this can be confusing for programmers as they wonder why calls to these things don't do as they expect.

Some parts of HTML and its kin are a little annoying, for which various workarounds can be used. Unfortunately, ocPortal uses Flash to work around some of these, for example the limitations of file uploading (a form must be submitted (ie. a new page loaded), no progress information is given, etc.). This is unfortunate because the only viable runtime for Flash is Adobe's (formerly Macromedia's) and this isn't Free Software. Another example is video and audio playing, where the pending HTML5 standard defines how to embed such things, but makes no requirements for the formats to use. The current formats most used are h.264, which gives high quality video, is supported by many proprietary vendors like Apple, but Free Software implementations of it are illegal in many countries due to patents; Ogg Theora, which is a medium quality codec (used to be poor, but has improved a lot recently) which has been the format of choice for Free Software for years, and is thus supported by browsers like Firefox easily; and WebM, a new format pushed by Google, which is patent-free (as far as we know) and supported by Free Software browsers. Until this settles down, it is difficult to make a HTML5 video site which will work on the majority of machines, without keeping at least 3 copies of each video (which is an awful lot of space) and potentially infringing patent law when converting to h.264. This unfortunately makes Flash a more widespread option than the standard, for the moment at least. It is only a matter of time before these things get replaced, but I would like to see it sooner rather than later, especially since I refuse to comply with Adobe's licensing terms.

The Future (my wishlist and thoughts)

These are ideas for where ocPortal can go. They're not a roadmap, they're not a vision, they're just things I've noticed and thought about, along with explorations of what new possibilities we would have if we implemented any of these.

WebDAV: WebDAV is a filesystem which runs over HTTP. On UNIX systems we're used to accessing everything via a file descriptor, and interfacing with all of this via some address underneath /. More recently, thanks to FUSE, we've become used to the idea of mounting filesystems which transparently encrpyt their contents, which transparently compress their contents, those which offer access to machines over a network, those which auto-generate contents from some source such as WikipediaFS, and so on. Now, spare a minute for those poor folk still stuck on legacy operating systems, which can't even handle ext2 by default. They can, however, mount WebDAV. That makes WebDAV, as a standard, a much better filesystem concept than an ocPortal-specific filesystem akin to WikipediaFS which very few users would be able to use.

By having ocPortal available via a filesystem like WebDAV, we can remove the barrier which prevents UNIX awesomeness from being unleashed on it. With an ocPortal filesystem, auto-generated and managed by PHP server-side code rather than being a direct representation of some disk's contents, we can allow users new ways to interact with a site (mount a site with your login credentials and have access to all of the files you're allowed to view, organised neatly into folders, which are populated automatically, and offer several concurrent hierarchies to choose from (eg. "images/dave/october" and "images/october/dave" could both generate the same results)), we can allow administrators new ways to manage their site (copying CSVs directly into and out of the site, dragging RSS in to post news, etc.) and we allow developers new ways to customise a site (direct manipulation of a site's source with native programming tools, with the changesets being available directly to the site's PHP).

Another advantage to doing this is that we can cover the same ground as ownCloud. This tries to offer an online filesystem like Dropbox or UbuntuOne but Free Software (CPAL's good for this, although not quite AGPL). Users can store their desktop preferences there so they can be available on whatever machine they're using. We've already got a great Web frontend, just not the filesystem backend (so the opposite to ownCloud at the moment).

The point about handling changesets is what intrigues me the most. Since all writes to the site will be handled by PHP, we can do what we like with them. A nice way to handle them would be to have the whole site in a distributed version control system like Git, and have the changes saved as commits as they are made. This would let site admins roll back changes very easily, whilst also allowing changes to ocPortal sites to cross-polinate as users can pull changesets from each others' sites (if this is specifically enabled by the admin, of course). ocPortal change from being broadcasted from a restricted SVN repository to those sites which poll the central server; into being a true community of shared code, with no barriers to entry.

There would be no need to keep backups of things which are removed (like addons), since they can be restored from the site's revision history or pulled in from the ocPortal network. Indeed, the entire concept of addons can be restructured into Git changesets which, along with themes, can spread through the network without the need for a central repository. ocPortal.com would be a showcase of suggestions, rather than a key piece of infrastructure.

There are lots of services out there which would enhance various parts of ocPortal, even if they remain as separate servers. The obvious one is email. Forum threads should generate mailing lists and emailing the list should populate the correct forum (there are PHPBB mods which do this, but I've not tried them). All content, like blogs, news, galleries, etc. should be emailed out to those who want it (in the body if possible, or else as an attachment) whilst comments can be posted by sending a reply. Interacting with an ocPortal site should be, as far as possible, doable via email.

If a site is being hooked into an email server, then there should be the ability to auto-generate email accounts for users. This is less standardised, but some reference implementation could be written, eg. against SquirrelMail. This would only need to tie together the account credentials, it wouldn't need any interface work since a direct link to the mail frontend can be given.

The same goes for XMPP/Jabber. There is limited support in ocPortal at the moment for using XMPP in the chat rooms. I think this should be available as standard, such that every chat room is discoverable via XMPP service discovery on the site's URL. Going further, the site can offer content via Publish/Subscribe and allow all of the same kind of interactions that are possible via email.

A nice feature would be for ocPortal to seed its content via Bittorrent, offering Magnet links via the site and using the Distributed Hash Table to manage peers (rather than a tracker).

There is a lot of opportunity for ocPortal to sprinkle more metadata around sites. At the moment it uses Dublin Core plus a custom ontology to describe documents. The most obvious next step is to generate RDF for users' profiles, using ontologies like Friend of a Friend.
There is the choice to use RDFa, which is scattered throughout the pages, but this would make templating much harder, so I think having separate RDF files for each thing we care to describe is enough. We should make sure that we're following the Linked Data recommendations of using HTTP redirects whenever a non-digital resource is requested (eg. the URI of a person is requested). Generic concepts common to all ocPortal sites, like "image", "video", etc., could be linked to a reference on DBPedia for that concept. Sites may have an RDF endpoint, if we find bots are taking too much bandwidth or aren't finding what we're giving out, but it's not too important. While we're discussing metadata, we can scrape incoming data for metadata, for example EXIF data in an uploaded image. Display this alongside regular
ocPortal fields.

There should be a federation between ocPortal sites, such that accounts made on one site will work on another ocPortal site, if the admins turn on this option. This could be achieved via OpenID, ie. scrap ocPortal-specific users in favour of everyone being identified by OpenID. In which case we would like to have a mechanism to generate these for users who don't already have one, or who want another. There is some nice code floating about which used to run xmppid.net which allows an XMPP ID to be used as an OpenID, by asking for confirmation out-of-band via XMPP. If we have an XMPP server hooked up to the site, with accounts for each user, then this would be a nice solution.

Along with this, users on any ocPortal site should be able to message any user on another ocPortal site. This could be achieved via XMPP/email integration, and/or through some form of OStatus-style messaging.

We should allow sites to use client-side cryptography. Thus the site is merely a host; the user's browser does the encrypting via Javascript before uploading, and does the decrypting after downloading. This would be difficult if we use WebDAV.

If we had OpenCollaborationServices support then lots of desktop applications would be able to grab data from ocPortal sites. This is a bit of a moving target at the moment, with the only major implementations being on the various parts of opendesktop.org (eg. gnome-look.org, kde-apps.org, etc.), but this would give us a hook in to many existing desktop applications.

Would be nice to have a few more protocols coming in and out, under some abstraction (maybe an "activities" log). PSYC can be used for server-server communications (eg. syncing), Wave could be used for client-server. We might even look at the Gobby protocol if we wanted to allow concurrent editing.

More coherent Javascript management. Currently Javascript works on DOM
elements in a procedural way. Would be nicer to have an Object Oriented
approach, where the objects are whatever the hell we want them to be, and
there may be some DOM objects associated with an object if we like; the
objects should sort out all of the logic amongst themselves.

There is a lot of interest in distributed social networks like Diaspora, GNUSocial, StatusNet, etc. which are trying to be Free social networks or replacements for specific services. They have the ideas right, some have protocols, but none have any kind of decent sites coming out of their HTML generators. Could we usurp them by taking the existing awesomeness of ocPortal sites and making them support these protocols? Would be nice, in that we'd get publicity, we'd get new features, plus everyone would get ocPortal as a kind of uber-Diaspora/GNUSocial/StatusNet. CPAL terms are like AGPL, which helps
the cause.

Not a specific criticism, but Tempcode is a bit daunting to use at first. Being a string-replacement system, it is all about metaprogramming. This is powerful, but do we want it to be a text replacement system, or do we maybe want a generative language? Do we want to work at the string level, or at the token level? What's wrong with XML? What's wrong with s-expressions? Would be nice to have the minimum amount of syntax possible, and no special-cases (we can break this symmetry at the function/directive level, which is interpreted by PHP anyway). s-expressions would be good for this. Similarly, if we want to overhaul templating, we could make quite a nice generative language for CSS with bugger all syntax and much more flexibility and extensibility. Would be a job to get working in a way that Web people would accept though. Could we make an XHTML-to-Tempcode convertor, to handle all of our legacy support? If we had a higher-level (eg. token-based) language then it would be a lot easier to make higher-level tools, like drag 'n' drop of elements/directives, live previews, etc.

Blog Dump 5: Some Statistics

2010-12-09T22:53:00.001Z

Statistical models are well suited to computer simulations. The most interesting results can usually be found in random processes, so here's an example showing the St Petersburg Lottery:

#!/usr/bin/env python

import random

def flip():

"""Simulate a coin flip."""

if random.randint(0,1): # Choose this statement or the next with equal chance

return "Heads" # Give a "Heads"

else:

return "Tails" # Give a "Tails"

def lottery():

"""Run a St Petersburg Lottery, flipping a coin until it's tails. Each time it's heads

our pot is doubled and added to the running total."""

winnings = 1 # Start with 1 pound

pot = 1 # The pot starts at 1 pound

while flip() == "Heads": # Loop until we get a Tails

pot = pot * 2 # Double the pot

winnings = winnings + pot # Add it to our winnings

return winnings # When we've finished looping, return the result

def play(rounds):

"""Run the lottery 'rounds' times in a row."""

cost_per_game = 2 # Deduct this from the wealth for each round

wealth = 1 # Start with 1 pound

print "Rounds, Wealth" # Column headings for our spreadsheet

print "0,1" # Print the first results

for x in range(rounds): # Loop through each round

wealth = wealth - cost_per_game + lottery() # Deduct the cost and add the winnings to our wealth

print str(x+1)+', '+str(wealth) # Print the round number and our current wealth

play(1000) # Play 1000 rounds

The scenario is that we start with £1 and pay a fixed sum (here £2) to play a lottery, in which a coin if tossed. If it's tails then we take the winnings, which start at £1, but if it's heads then the winnings go up by twice the last increase, so they become £1 + £2. If we get a tails next, we get the winnings, but if we get heads it goes up by double the last increase again, so the winnings become £1 + £2 + £4. This keeps going on until we get a tails, when we get the winnings so far. The remarkable thing about this game is that the amount you can expect to win is infinite (0.5*£1 + 0.25*£2 + 0.125*£4+... = 0.5 + 0.5 + 0.5 + ...), so that you should be willing to pay any finite amount to enter. In this case the entrance fee for the lottery is £2, but it could be £2,000,000 and it wouldn't make a difference. We can see this from the graph below, where we run 1000 lotteries in a row, with 25 of these simulations running simultaneously (ie. 25,000 lotteries). The number of lotteries entered goes along the bottom, whilst the winnings goes up the side. The 25 runs of the simulation have been superimposed on each other to better approximate what's going on (I can't be arsed working out the error bars for a blog post). At any point on the graph, the darkness is a rough estimation of the probability of owning this amount of money after this many rounds (we use the area under the curve since, if we have £50 then we also have every amount below £50).

I've also made some simulations of the Monty Hall problem, random walks (intersecting and non-intersecting) and a few other statistical phenomena. I might post them if I get time. They can be the source of pretty patterns :)

Blog Dump 4: What Makes Me A Geek: Reason 0x54F6

2010-12-09T22:52:00.000Z

I have only ever paid for one album in my life. The rest of my music is freely distributable online. The name of that album is 01011001, which is Y in ASCII.

Blog Dump 3: Duck Typing as Contraint Propagation

2010-12-09T22:22:00.002Z

Another of my unfinished programming musings:

Personally, I really like Python. Python is quick to write, quite readable, but most of all it's dynamic. Many people get caught up on the syntax of languages, usually because that's the easiest part, however the syntax is just a way of expressing the semantics, which is what you actually mean when you code. Let's compare some C code to some Python code:

int square(int x) {

return x*x;

}

int mynum = 5;

int mynum_squared = square(mynum);

Don't focus on the syntax, I'm keeping such things as simple as possible. This C code simply defines a function called "square". It says that square acts upon integers ("int") and gives back ("return"s) integers as a result; in this case the result is the input multiplied ("*") by itself. We then make an integer which we call "mynum" and set it to equal to the number 5. We then make another integer which we call "mynum_squared" and we set it equal to the result of the function square acting upon mynum. Since code is just Maths we can simplify (or "run") this to show:

mynum_squared = square(x=mynum)

mynum_squared = {mynum*mynum}

mynum_squared = {5*5}

mynum_squared = 25

It's pretty straightforward, just like Maths in school. Let's see how we would write this if we were using Python:

def square(x):

return x*x

mynum = 5

mynum_squared = square(mynum)

Let's read what this code is doing. We define a function called "square" which acts on something. It also "return"s something as a result. More specifically, what it returns is the input "*" with itself. We then give a name "mynum" to the number 5. We then define another name, which points to the result of the function square acting upon whatever mynum points to. Once again, code is just Maths so we can simplify this too:

mynum_squared = square(mynum)

mynum_squared = square(5)

mynum_squared = 5*5

In Python, the asterisk "*", rather than being an easier-to-write-on-a-keyboard multiplication sign like it is in C, is actually syntactic sugar. Syntactic sugar means that it is a shorthand way of writing something that's annoying to write out in full every time. Let's write out the full description of this code, rather than using the convenient shorthand:

mynum_squared = 5*5

mynum_squared = 5.__mul__(5)

Now what does this last version say? Well you may recognise the "(5)" as passing the number 5 to a function. The function we're running is called "__mul__", and the "." means that its definition is stored inside the number 5. So what it says is to get the function __mul__ which is stored in the number 5, give it a number 5 and make a pointer to the result called "mynum_squared". Since we can't see the definition here of what the function "__mul__" does, there's no way for us to simplify this code any more.

So how does this massive difference in semantics manifest itself in the syntax of C and Python? In the C code, everything had a type, for example "int mynum = 5;". The name "mynum" cannot store anything that is not an integer*. This allows us to know exactly what the code will do before we run it (as long as we know what the input will be), since we know how everything behaves, although of course it may take us a while to work out exactly what it does (otherwise there's no point writing the program ;) ) and it may take forever (see Halting problem). So where are the types in Python code? Well they're there, but they're a bit redundant. Let's give our Python code some types in a C-style syntax:

object square(object x):

return x*x

object mynum = 5

object mynum_squared = square(mynum)

As you can see, the type of everything is just "object"**, so there's not much point writing it out explicitly for everything. The vagueness of having the type of everything no more specific than object, or essentially "something", makes Python incredibly powerful, since we get a type system called "duck typing". Duck typing comes from the saying "if it walks like a duck, sounds like a duck and looks like a duck then it's a duck".

More formally, what this means is that in our "square" function we take in an object "x" then return "x*x" or, without the syntactic sugar, "x.__mul__(x)". In our C function we take in an int, if we want to use our square function on something else (for example a real number) we need to copy and paste our existing definition and replace all of the "int"s with something else (eg. "float"). In duck typing the type of the input is just 'anything which works', no more and no less.

This is a bit tautological, ie. "square accepts anything which square accepts" but is nevertheless more specific than simply "an object", which is the largest upper bound we could have on the type. If we call the type consisting of all objects T, so that

forall o of type object, o is a member of T of type P(object)

We get, through a bastardisation of formal logic, a search over the space of all objects. "T" is the type of object we're looking for, so it is "of type type". At the moment we're just dumping every object we find into T, since we know it acts on objects (although we define it in reverse; we don't put objects into T, we say that T contains it, so that we get a timeless mathematical truth). Now our more specific version we can call T', such that:

forall o of type object, o is a member of T' of type P(object) if and only if square(o) is not a member of errors

As I said, this is a bit better, but what we would like to do is replace the use of square(o), since we'd like to get rid of the tautological aspect. We'd also like to use more easily defined concepts than a set of all errors, since if we tried to define the set of all errors we'd end up solving this type problem as part of that, so we've not made our lives easier yet. Let's get rid of those by further refining the type based on what we know about the function, so the more specific T'' is defined such that:

forall o of type object, o is a member of T'' of type P(object) if and only if there exists an f of type function where name(f) = '__mul__' and f is a member of o

Now that's gotten rid of the tautology nicely, but our replacement of 'the set of all errors' with 'o must have a function __mul__' is pretty vague since this is still true for objects which would give errors. Thus we can make another refinement and say T''' is defined as:

forall o of type object, o is a member of T''' of type P(object) if and only if there exists an f of type function where name(f) = '__mul__' and f is a member of o and there exists an x of type U where x is a member of arguments(f) and o is a member of U

This is getting a bit unweildy, but formal logic has a tendency to do that (and of course I'm using English rather than Unicode symbols, both for convenience of typing and I'd end up translating it to English anyway as an explanation). Essentially our search now contains some undefined bits, most importantly the type U which is the type of the arguments accepted by the function __mul__. We don't just want to make sure that x.__mul__ exists, we also want to make sure that x.__mul__(x) is valid, so we need to know the type of __mul__'s arguments and ensure that our object o is a member of that type.

Now we've nicely defined a type for square, namely T''', using all of the knowledge that we can get from the code without restricting it, but this definition itself is defined by another type U. Of course, we also haven't defined the type "function", but we can do that in a similar way if we know how Python works (a Python function f is an object for which f.__call__ exists), and we can define U if we have the source code for __mul__. Of course, it can become intractable to define types in this way for an entire system, so what we would like is a function which takes in function objects and returns type definitions on its arguments so that we can do this automatically. Of course such a function might never halt, for example if we have a recursive function like:

def recursive(x):

return recursive(x)

attempting to inspect this in a naive way would result in endless attempts to find types for both, since it will accept anything and never halt (or in the case of real hardware, the stack depth will be exceeded and the program will exit with an error). Of course, as human programmers we know what this will do, so we could make a more sophisticated system for inspecting our code, which can notice such recursion and tell us that the type of x is just "object" and the return value of recursive(x) is "RuntimeError". This would be necessary to reason about the following perfectly valid Python:

def infinity(x):

return infinity(x)

def buzz_lightyear():

try:

infinity(1)

return "And beyond!"

except RuntimeError:

return "Falling with style."

The function "buzz_lightyear" tries to run the function "infinity", which breaks when it reaches the maximum recursion depth imposed by the Python interpreter and gives a RuntimeError indicating this. The line 'return "And beyond!"' is never reached, due to this error, and instead we GOTO the "except RuntimeError" line, which tells us what to do if we get a RuntimeError. The line 'return "Falling with style."' is run, so that this function always returns the text string "Falling with style.", and of course it doesn't accept any input. It is possible to reason about this function in a very simple way and figure out that it returns a text string (both of the "return" statements have a text string, regardless of what "infinity" returns). It's slightly harder to work out that it always returns "Falling with style.", but possible. Of course, we could write a nasty bit of code like:

def infinity(x, values):

x.__class__.getValue = values[0]

return infinity(x, [values[1], values[0]])

def buzz_lightyear():

def value1():

return "Hello world"

def value2():

return value2

try:

infinity(copyright, [value1, value2])

return 3

except RuntimeError:

return copyright.__class__.getValue()

This is a complete bastard, and actually depends heavily on global variables which may have different defaults on different systems, and may be changed during the running of a program. What it does is the following: Define a function called "infinity" which takes two objects, which we call "x" and "values". The first thing we do in this function is change the 'class' of x (the type of object it is) so that its function 'getValue' is the first element of our values argument. We then return the result of running the infinity function on x and a list object containing the first two elements of 'values' in reverse order. In other words, this will run itself over and over, each time swapping the 'getValue' function between those first two elements of 'values'. This will cause a RuntimeException, since it can't recurse infinitely, but we don't know what 'getValue' will be when this happens, just by looking at the code. We then define our function 'buzz_lightyear' which takes no arguments. Inside buzz_lightyear we define two functions, 'value1' and 'value2'. The former takes no arguments and returns a string "Hello world"; the latter simply returns itself as an object (but without running itself recursively). With these in hand we proceed to attempt a call to 'infinity', giving it Python's built-in 'copyright' object and a list object containing our value1 and value2 functions. After running infinity we return the object 3 (which never happens, as a RuntimeError is encountered). What ends up running in the 'except' statement is whatever function the 'getValue' name is pointing to, which is one of value1 or value2, and we return the result. Here there are three possible return types, a number 3 (which never happens), a string "Hello world" or a function value2. Reasoning about such a program in a general way is very tricky, for example the return type of buzz_lightyear could be defined as A where:

forall o of type object, o is a member of A of type P(object) if and only if o is a member of (function unioned with string unioned with number)

or as A' where:

forall o of type object, o is a member of A of type P(object) if and only if o is a member of {F, "Hello world"} where F of type P(function)

Doing any more than this would be beyond the scope of our code, so we don't really want to take it any further. We can use these types as constraints to work out the types of everything that depends on them, until we've exhausted the information contained directly in the code. The rest we can only work out as the code's running, when we know what exact values these objects have, and thus what type they are. As long as we're always working on lowering the upper bound on the types then we're not imposing any restrictions on the code which were not already present by virtue of Python's semantics. When it comes to runtime the introspection abilities of the language (the ability to know about itself) can be greatly enhanced this way.

Of course, there are other ways of doing type inference which give a lower limit to types, essentially turning pure object functions like our Python "square" function into ones with concrete types, ie. types built up from "atomic types" (or, as I call them, bloody annoying non-object crap). Essentially it takes C-style declarations and puts them in Python, for example Pyrex. These allow working with statically/concretely typed C code, but in a backwards way: rather than seeing these restricted C functions as an alternative execution path for Python objects and treating them accordingly (we don't care how it's implemented, just that it works), instead the concrete typing leaks out and we end up hitting artificial walls when we try to program, which are only there due to a leaky implementation (for example, in Python 2.x try to run "hello".foo = 10).

So what's the point of all this? Well firstly, code can only run when we know what type everything has. Treating everything as a generic "object" can slow down execution speed as it becomes very hard to automatically optimise the code. If we knew that something is only ever an integer then we can put number-specific code there to make it much faster, rather than keeping it generic. The simplest way to implement a dynamic language like Python ends up being with an interpreter and a virtual machine, a statically typed program which simulates a computer capable of reading and executing Python line by line***, whilst statically typed languages can instead be compiled (translated) into code which a real computer will understand, and are thus much faster. If we have type information then we can compile Python into machine language and see a massive speed boost whilst remaining duck typed. Since concrete type information can only ever be known at run time, such compilation would need to happen as the program's running: so-called Just In Time compilation.

Current approaches to JIT compiling successfully use type feedback, where a function is run in the regular way in virtual machine, but the specific types it uses are remembered. A compiler then takes the function and the type information and compiles a machine-code version, so that next time the function is run with the same type of input it can use the machine-code version instead. This is nice, but requires all of the work to be done when its needed, so a little push in the right direction from inferred types might reduce this overhead.

The most interesting use, as far as I'm concerned, is with automatically generating specifications. Given enough information about the code it becomes possible to know a lot about what it is capable of doing, without running it. This allows some code to become declarative, meaning that the description of the code specifies exactly what it does, and the code itself just becomes one particular way of implementing that specification. Comparing specifications (which is not possible in the general case, but we can still try opportunistically, eg. with a timeout) allows us to automatically replace the code (implementation) with alternatives that do the same thing. This is useful for building compilers, and if we want to make languages work together (although of course we just shift the problem, since we can have competing, incompatible specification languages).

Another useful feature of this specification-carrying-code has been implemented by Hesam Samimi in an extension to Java, where the programmer can supply a specification for each block of code, and the virtual machine can check if the supplied code actually does implement the specification or not. This makes debugging easier, as long as you can get your specifications right, but interestingly it can be input-dependent. For example, a function has a specification, and when that function is called the code is checked against the specification to see whether it matches, given the input. If it does then great, but if not then an alternative can be used. This makes handling of edge-cases and corner-cases much nicer. Here's a literal example of edge- and corner-case handling code; We define a function which takes four arguments, a "grid", a function called "process" and an x any y coordinate. We want to run "process" on the square in the grid at position (x,y), along with every neighbouring square, and return a list of the results. This function looks like the following:

define my_function(grid, process, x, y):

if x == 0 or x == 99 or y == 0 or y == 99:

if 0 <>

if y == 0:

return map(process, [grid[x-1][y], grid[x-1][y+1], grid[x][y], grid[x][y+1], grid[x+1][y], grid[x+1][y+1]])

else:

return map(process, [grid[x-1][y-1], grid[x-1][y], grid[x][y-1], grid[x][y], grid[x+1][y-1], grid[x+1][y]])

elif 0 <>

if x == 0:

return map(process, [grid[x][y-1], grid[x][y], grid[x][y+1], grid[x+1][y-1], grid[x+1][y], grid[x+1][y+1]])

else:

return map(process, [grid[x-1][y-1], grid[x-1][y], grid[x-1][y+1], grid[x][y-1], grid[x][y], grid[x][y+1]])

else:

if y == 0 and x == 0:

return map(process, [grid[x][y], grid[x][y+1], grid[x+1][y], grid[x+1][y+1]])

elif y == 0 and x == 99:

return map(process, [grid[x-1][y], grid[x-1][y+1], grid[x][y], grid[x][y+1]])

elif y == 99 and x == 0:

return map(process, [grid[x][y-1], grid[x][y], grid[x+1][y-1], grid[x+1][y]])

else:

return map(process, [grid[x-1][y-1], grid[x-1][y], grid[x][y-1], grid[x][y]])

else:

return map(process, [grid[x-1][y-1], grid[x-1][y], grid[x-1][y+1], grid[x][y-1], grid[x][y], grid[x][y+1], grid[x+1][y-1],

grid[x+1][y], grid[x+1][y+1]])

This looks pretty messy, but what is it doing? Well it handling the neighbours: if a square is on the edge of the grid (here we say it's on the edge if its coordinate is 0 or 99) then it won't have any neighbours on one side. The first four "return" lines handle the bottom, top, left and right edges respectively. Likewise, if we're in a corner then we have no neighbours on two sides, so the next four "return" lines handle the bottom left, bottom right, top left and top right corners. The bottom line, the final "return" statement, will work for every square which isn't a corner or edge case, ie. one that is surrounded by neighbours. This type of code is really ugly, and very prone to making mistakes like a plus or minus the wrong way around. A lot of my current Physics project requires code like this, except in three dimensions where there are 26 neighbours to each cube, 6 face cases, 12 edge cases and 8 corner cases. Needless to say, I've often spent a whole day trying to track down a single misplaced minus sign. What makes specifications nice is that we can replace this whole lot with the following:

define my_function(grid, process, x, y):

return map(process, [grid[x-1][y-1], grid[x-1][y], grid[x-1][y+1], grid[x][y-1], grid[x][y], grid[x][y+1], grid[x+1][y-1],

grid[x+1][y], grid[x+1][y+1]])

Which is just that last line from before. This will work the majority of the time, but if we're on an edge or in a corner then it won't match the required specification and won't be used. In our 2D example there are four corner cases, four edge cases and one regular case. In a relevant 100x100 grid there are 4 corner squares, 392 edge squares and 9604 regular squares. That means, only counting return statements, 11% of our code is handling 96% of the data, 44% of the code is handling 3.9% of the data and 44% of the code is handling 0.04% of the data. The larger the input, the less significant the edges and corners become.

Corners completely handle the 1x1 and 2x2 grids, but then remain constant regardless of grid length. Edges come into play in the 3x3 grid, already equally important as the corners, then increase linearly with the grid length. The regular, non-edge case also starts in the 3x3 grid, but goes up with the square of the grid length, until by the 7x7 grid they are more significant than the edges and corners combined. After that the edge cases aren't worth mentioning.

Not only does getting rid of edge cases make the code far more readable and understandable, but the code becomes simpler for the machine to run. In our case the edge case code does about as much as a results verifier would, so there's probably no speedup achievable here, but if a costly algorithm is used by a function to handle every possibility, where the vast majority of cases can be fulfilled by a quick algorithm, then simplifying it in this way can give speed gains. For example, speeding up the non-edge case of our grid function, for a 100x100 grid is worth 96/4=24 times as much as a speed increase in the edge case code. Thus if we double the speed of the regular case we can get away with an order of magnitude slow-down in the edge case and still get an improvement.

The obvious question becomes: what happens if we get an edge case? If our code comes with specifications then we don't need to care about the edge cases, since an adequate function can be created to handle them automatically by looking through the specifications of everything else and building the required functionality out of the available components. In fact, we don't even need to write the regular function, that can be automatically generated too! Writing the function by hand just becomes an optimisation, with the regular case being the most obvious candidate for optimisation in this example. Since automatically synthesised code can be expensive to produce and inefficient to run, it is a good idea to do such optimisation, but not at all necessary. The specification language becomes the language to program in, and the computer does the rest (as long as sufficient components are written with implementations, or else no code can be generated).

So why am I writing this long and boring post? Well, firstly I am a great believer in the need for correctness proofs: code is just a fancy Mathematical notation, and without a proof of what it does then it's no better than engineering or a social science. Rules of thumb (eg. design patterns) are all well and good for day-to-day tasks, but a rule-of-thumb mindset isn't going to produce anything truly new, truly insightful or truly robust: the second law of Thermodynamics is not "hot stuff tends to cool down and cold stuff tends to heat up", that's a rule of thumb; it is in fact proved from Atomic Theory using Statistical Mechanics, whilst Atomic Theory is proved from Quantum Mechanics and Statistical Mechanics is Statistics and Probability Theory, which also underlies Quantum Theory along with Guage Theory, Topology and so on. Whilst there can never be a complete proof of anything, we can narrow down the number of assumptions we have to make.

* In reality it can store anything, since everything in a computer is the same old binary, but since it will treat what you give it as an integer you'll get corrupted data unless your data behaves exactly like an integer, in which case you may as well use an integer :P Note that a program doesn't particularly care if your data is corrupt, since it will carry on using it, happily working its way down the execution path, all the while fucking up whatever you thought it was meant to be doing because you didn't understand what program you just wrote.

** Functions are actually a bit of a strange type, since we give them things to act on. Python functions are a kind of object, but when we run them we're doing a funny thing called Currying. For example, our "square" function in Python has the type object->object, since we give it an object and get an object back. If run a function which makes a list out of two objects we have a type of object->object->object. We can give it an object, like 2 for example, and it gives back something of the type object->object, which is also a function, which in this case takes an object and gives out an object. If we put in the object 78 to this new function then we would get out a list object [2, 78] (based on the definition we gave). In Python we can't directly Curry functions, ie. we can't turn an object->object->object into an object->object, we can only go straight from one end to the other, but since this is all Maths it doesn't stop us from thinking about it :)

*** Actually the raw Python is turned into bytecode, a much simpler language which is faster to execute, and it is this which is interpreted in the virtual machine.

Blog Dump 2: The Universality of Search

2010-12-09T22:19:00.001Z

Another unfinished post I thought I'd share:

Searching is a much-studied area of computer science. The reason for this is that, like the Travelling Salesman Problem, the problem of how to search can be applied to a massive number of problems if they are phrased in the right way. As a straightforward example (if you'll excuse the pun) let's look at navigation: How do I get from Sheffield Train Station to the Devonshire Cat pub? This can be modelled quite literally as a search problem if you take all of the roads heading away from the train station (this is called enumerating them) and for each one, see if it ends up at the Devonshire Cat. If none do then enumerate all of the roads you found coming off them and do the same thing. Keep going until you either find the Devonshire Cat, or you run out of roads.

Another example this can be applied to is deciding where to eat with a group of friends. Here you can either enumerate the venues and search through them for the best match with your group's preferences, or enumerate the preferences and search through those until the best venue is found.

The shear generality of search is what makes it fascinating. Indeed, for any problem where you know the answer is in a certain set of possible answers, and you have some way to verify the answer (equivalent to rating each venue in the dining out example) then you can enumerate the possible answers and check each one. The problems with this approach are pretty obvious: firstly the set of possibilities could be unfathomably large (eg. trying to find the first sentence of this post, if we were to first enumerate 1-character-long sentences, then 2-character-long sentences and so on then we would only find it after looking through about 2,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possibilities, which according to this site is pronounced "two quattuorvigintillion"), then of course there are infinite sets like the natural numbers, where we can start counting through them but we've no idea how long it may take to find the answer we're after, and then there are non-recursively-enumerable sets, which means that not only can you not know how long it will take to look through, but you can never even find a way to go through every member of the set (for example, trying to enumerate the Real numbers, eg. with a decimal point, then there will always be an infinity of numbers between those we decide to test which will be skipped, no matter how we choose them).

Once again, it trails off before making any real point :P

Blog dump 1: Diet Python

2010-12-09T22:16:00.002Z

I've got a few blog posts hanging around on my PC, so I thought I'd post them even though they're not really finished. Here's the first.

I've talked about this before, but have been doing some more work on Diet Python (available in my Python Decompiler on gitorious.org).

Diet Python is a sub-set of Python which is just as expressive. The PyPy project, for example, uses a subset of Python called RPython which is restricted to exclude the really dynamic stuff, and Google's Go language is essentially the same. They exist to keep the syntax and readability of Python, but by throwing away bits they make it much easier to implement. That's not the goal of Diet Python. In Diet Python we don't really care about readability, and syntax can be as awkward as we like as long as it's still valid Python. What Diet Python does is throw away the redundant bits of Python that can be replaced with other Python that does exactly the same thing.

As a simple example, a + b does the same thing as a.__add__(b), but if we're making a Python interpreter we have to handle both. Diet Python throws away the +, since it's less general than the function call, so that Diet Python implementations would only have to implement the function call, they can forget about the +. Diet Python has a 'compiler' which translates Python into Diet Python, so that we can write normal Python (eg. a + b) and then strip away the fat to get a Diet Python equivalent. This Diet Python, since it's a subset of Python, will also run fine in a standard Python interpreter.

There are two approaches I'm taking with Diet Python. The first is to remain 100% compatible, so that there is no change between the input semantics and the output semantics and both can run the same in a standard Python interpreter. The other is to make the output as 'pure' as possible, so that we may end up doing things which make no sense in standard Python but 'should' make sense: for example adding methods to True and False. In CPython that's not possible since they're poorly implemented in C, and this would also change their API, but as a Python programmer it feels like this is a bug in CPython and that there's no reason to stop doing it just because it doesn't work due to CPython. That gives optional translations which, for example, change:

if a:

print b

else:

print c

to (a).__if__('print b', 'print c') which wouldn't work in CPython due to its True and False peculiarities.

Given enough of each type of translation, compatible and uncompatible, I hope to able to get Python code down to a bare minimum of syntax. I believe that to be message sends and strings.

The blog post kind of trails off there. Oh well, better that I'm writing code than blogs anyway ;)

Odd SOCKS

2010-09-03T22:32:00.003+01:00

As a follow-on from my last post I'll discuss the networking on my Fedora 11 machine. I'm not a massive networking geek; I know quite a bit, but mostly through trial-and-error as a step to getting something else working. For this reason I've never introduced something unnecessary into the mix for its own sake, and thus all I knew about SOCKS was that there's version 4 and 5 in the wild, and it's used by The Onion Router. Since I've always used TOR for HTTP, and used a privacy-filtering-type proxy like Privoxy to handle the HTTP<->SOCKS tunneling, I've never bothered learning more about it.

Now, my office machine is set up to route through a SOCKS proxy on a different machine on the ethernetwork. Web browsing is simply a matter of Firefox's Edit->Settings->Advanced->Network->Settings. However, Thunderbird (which has exactly the same connection changing interface as Firefox) can't connect through IMAP this way. This is due to IMAP not going over HTTP. The same applies to SVN, ping, etc. There is a solution though, which is to use connect-tunnel to run a local server for redirecting calls to any port through a HTTP proxy. Running a connect-tunnel command like "./connect-tunnel -P 192.168.1.1:1080 -T 10234:mysite.com:3690" will allow us to run a command like "svn co svn://localhost:10234" which will think it's checking out a subversion repository from the current machine on port 10234, when in fact it is being routed through a HTTP proxy on port 1080 of 192.168.1.1 to the remote machine at mysite.com on port 3690.

This is great, but the proxy isn't HTTP, it's SOCKS, so we need some way of tunneling this HTTP connection through SOCKS (so, in this example, we'd have a SOCKS proxy redirecting HTTP traffic which is encapsulating an SVN connection). This was fine for Firefox, which has built-in facilities to redirect over a SOCKS proxy, but not all applications do (especially if they don't even know they're being tunneled through HTTP in the first place!). This is where we use a "socksify" program, which intercepts HTTP requests and redirects them without the application which made them knowing about it. There are a few of these, for example Dante contains such functionality and is in Debian, but unfortunately it isn't in Fedora and I was after something I wouldn't have to compile (due to dependency hell). Fedora does contain tsocks which is pretty simple to set up and use, and worked for some applications. It could be used either via "tsocks my_application_name" (eg. "tsocks evolution" to run the Evolution mail reader through SOCKS), or via adding its library to the LD_PRELOAD environment variable, which affects all subsequently executed applications (eg. put it in your .bash_profile). However I found it didn't work for some programs. I then tried proxychains, which I'm pretty happy with. It is called in a similar way to tsocks, eg. "proxychains evolution", and works in some cases where tsocks doesn't.

Aside from this I also recommend setting environment variables, such as "http_proxy" (which, once again, can be done via .bash_profile) and your desktop's settings (I found Gnome's to be useless here, since I didn't come across any application which actually paid attention to it, but KDE applications consistently adhere to this setting, even if not all of them wind up working properly). For Subversion the /etc/subversion/servers file is a good place to put HTTP proxy settings, and try using http:// for the repository address, as this may be configured to work as well as svn://.

Basically, try everything you can find, try them in combination and try layering/tunneling them. Even if you don't seem to need one method now, the next application you try may need it ;)

Freedom to Work

2010-09-03T18:55:00.006+01:00

I've been messing with my new work computer, on which I had the option of running Windows Vista or Fedora 11, and thought I'd give a run-down of how I've been finding it, the issues I've come across, how I've fixed them and future tinkering opportunities. Needless to say, if you're looking for any information about fixing issues with Windows Vista then you're in the right place. As a first step you'll need to wipe over it with Fedora 11, then your computer will be usable and under your control so that you can follow the advice below if you'd like to.

Graphics
The graphics card is Nvidia, but isn't supported by the nv driver :( I tried nouveau, which starts up OK with the right resolution and a working cursor, but everything else looks like someone's taken a dump in the framebuffer. I've kept clear of Nvidia cards for years because they're anti-Freedom, but a consequence of this is that I'm not familiar with nouveau settings like I am with Intel, AMD and VIA. Rather than spend too long trying to grok nouveau I had to do the unthinkable: install Nvidia's binary blob :( Gives output at the native resolution of the widescreen monitor, unlike VESA, but obviously I'd like to purge this proprietary contaminant from the machine at some point. I think I'll do some research into nouveau driver options in my own time, then spend a few minutes each morning testing them at work, since it obviously requires restarting X over and over. If I can get it working I'll post the results here and maybe on some Wikis. It certainly can't be as awkward as getting my XO's screen to play nicely under Debian ;)

Codecs
There were only (supposedly) patent-free Free Software codecs installed on the machine, since that's how Fedora has to ship as it's from the "land of the the free", but for those of us in less backwards jurisdictions this isn't particularly brilliant for testing videos and things. I'm not overly familiar with Fedora's package naming conventions so I installed Gstreamer's good, bad and ugly meta-packages, but a lot of guides don't make a distinction between non-Free codecs and patent-encumbered Free Software codecs, so I might've unwittingly pulled in some evilware. I'll take a closer look through at some point, but for now I'm sticking to MPlayer, since it's a far more powerful application than, eg. Totem, and is more useful from the commandline.

Previously-installed Malware
When I took over the machine it was full of proprietary junk. It's got some scarily dangerous repositories enabled like one from Adobe, one from Dropbox and, less evil (or so they say), one from Google. It's got some crappy Flash plugin installed from Adobe, but thankfully SWFDec overrides it. I'm not sure how this proprietary player's installed itself, so I haven't looked into how to undo it utterly. When I do I think I may have to keep an equivalent in some sort of sandbox anyway (eg. a UnionFS overlay) since I may have to test some sites which are infected with Flash (although, of course, I don't know how anyone could debug something for which they don't have full, irrevocable access to the source). As well as this it's also got Skype, which is a program that does a limited form of SIP/Jingle-style VoIP. However, not only is the client proprietary, the whole network it uses is a black box too! I'd like to purge this from existence, but unfortunately work does some communication via this obfuscated mess, so I can't for the moment because there's no interoperable replacement (did someone say "vendor lockin" AKA "the exact reason why this crock should never be used by anyone"?). Once again I think a sandbox might be required to stop it playing havoc with the system, or whatever it's meant to do (I don't know since I've not seen the code). As well as this is Dropbox, which I've never had the misfortune to use directly, but heard many horror stories from the Computer Science department about how prevalent the myth is that Dropbox is somehow a version control system. What it really is seems to be is some sort of UPnP-aware WebDAV-esque remote filesystem, which appears to attempt peer-to-peer synchronisation and causes unending conflicts if it's used for anything more elaborate than the equivalent of an email conversation. I can't really see the point of it, since it's just a poor man's Git, but once again I don't know of any compatible alternative (LOCKIN ALERT! LOCKIN ALERT!) so I think I'll sandbox it too, at least the daemon.

It seems a shame to me that so much infrastructure has been build on such untrustworthy foundations, for a company which is apparently "Proud to be Open Source". Of course, the gatekeepers of these secret services will die at some point, and their code will either be freed or become useless, but hopefully we won't have to wait that long for someone to kill it. Who knows, maybe I could play a role in this now that I'm trying my hand at Web technologies?

Next post will cover networking, which is occasionally cropping up problems as I do new things, but is worth sharing what I tried nonetheless.

Ciao.

IWF Crap

2010-08-26T13:40:00.003+01:00

Seems the Internet Watch Foundation are at it again! Sub-domains of Webs.com are currently inaccessible to anyone in the UK who's ISP pays attention to the IWF. This means that I am being blocked from visiting my own Web site because it contains child porn (the only reason the IWF blocks sites). Hmm. You can visit it via its old address here and judge for yourself how much is illegal pornography, or you can visit it through a non-UK proxy. Annoyingly the www.tk servers won't let me change the redirect address of www.chriswarbo.tk. I think it may have expired :'( If you think this is ridiculous then do what I do, support the Open Rights Group :)

Bits & Bobs

2010-06-26T08:43:00.002+01:00

The title of 'father of computing' is usually assigned to Alan Turing. Before him Babbage had sketched ideas for his Analytical Engine, but had not proved anything about its operation. Alonzo Church had created his Lambda Calculus formalism, but the computation (beta reduction) still had to be performed by hand. It was Turing who considered a physical machine for performing computation, studied the machine mathematically and then build some.

Turing's approach was to think of a mechanical Mathematician. He thought, what is it that Mathematicians actually do when they perform Mathematics? Well they sit in front of a piece of paper containing some Maths, for example it might be the statement of a problem like:

x+2*5y=12
y=-3
x?

Turing argued that a machine would find it easier to read such things if, rather than having a variety of notation styles, the symbols used could be written neatly instead; for example by writing one symbol in each square on some squared paper.

x + 2 * 5 y = 1 2
y = - 3
x ?

Next he said that we don't really need a 2D sheet of squared paper, we can do it in 1D if we have some symbol for a new line, like ";". Thus our Maths becomes:

x + 2 * 5 y = 1 2 ; y = - 3 ; x ? ;

Now, which symbols should we use? If we want to build a machine then we want as few as possible, to keep things simple. Turing noted that rather than giving everything a unique symbol, they could be given labels based on a number of simpler symbols, like writing "10" instead of "x" for example. Thus we can say "10" means "x", "11" means "y", "12" means "+", "13" means "*", "14" means "=", "15" means ";", "16" means "?" and "17" means "-". Now our problem looks like:

10 12 2 13 5 11 14 1 2 15 11 14 17 3 15 10 16 15

Now it's getting confusing: we've got things like "1 2" as well as "12", how can we tell the difference? We do it by making every number 8 digits long, filling any unused digits with 0. This gives

00000010 00000012 00000002 00000013 00000005 00000011 00000014 00000001 00000002 00000015 00000011 00000014 00000017 00000003 00000015 00000010 00000016 00000015

Now that everything is written using only numbers, all in a straight line, in groups of 8, it's looking much more likely that a machine will be able to read it mechanically, since it only needs to know how to read "0", "1", "2", "3", "4", "5", "6", "7", "8" and "9". In fact, we don't even need to use all of these, since it's entirely possible to write numbers with only "0" and "1", which is called binary (as opposed to digital) Maths. So we can rewrite the above problem converting each 8-digit-long digital number into an 8-bit-long binary number:

00001010 00001100 00000010 00001101 00000101 00001011 00001110 00000001 00000010 00001111 00001011 00001110 00010001 00000011 00001111 00001010 00010000 00001111

Of course, I'm also using spaces (" ") to make it clear where one number ends and the next begins. Since they're all 8 bits long I don't need to do this, so our final, simplified problem is written as:

000010100000110000000010000011010000010100001011000011100000000100000010000011110000101100001110000100010000001100001111000010100001000000001111

Now our machine only needs to be able to tell the difference between 2 things, 0 and 1. Of course, we don't need to write them down on paper as 0 and 1, we can use anything that can be in one of two states. For example we can use the magnetism of a piece of metal, which can point in one of two directions (this is used in hard drives); we can use switches, which can be either on or off (this is used in RAM and USB drives); we can use the reflectivity of a surface, which either reflects or doesn't (this is used in CDs and DVDs), and so on.

Now that we have a mechanical device that reads our incredibly simplified Maths notation, what does it do? Turing argued that brains aren't magical things: people just follow certain rules that they've learned, or even things that they've read further back on the page. Thus people go forwards and backwards over the page, changing the contents of their brain as they read, and occasionally writing something down. Thus Turing's machine just has to go forwards and backwards over its zeros and ones, called "the tape", performing certain actions based on what it reads, and occasionally writing to the tape (setting a bit to be 0 or 1). The actions it takes define the machine, and Turing proved that some sets of instructions are able to mimic any other set of instructions. These types of machine are called Universal Turing Machines, and Turing proved all kinds of interesting things about them, for example that's impossible to know for certain whether a given machine will ever run out of actions to take or not (known as the Halting Problem).

An illustration of Turing's machine is shown above, and Turing and Church showed that Universal Turing Machines are just as good at Maths as Church's Lambda Calculus, ie. they can solve exactly the same problems. They put forward the argument that many other things can solve those exact problems too, but that nothing exists which can solve more than those. This is known as the Church-Turing Thesis, and was proved recently by Yuri Gurevich. Thus Turing's simple little device, trundling back and forth over its tape, is actually the most powerful computer in the world. Of course, it's in joint-first-place with every other computer, since the machines we use every day are equivalent in power to a Universal Turing Machine; they are known as Turing Complete.

Symmetry in Languages

2010-05-25T12:48:00.003+01:00

This post is about languages and grammars*, and I'll be using examples in a pseudo-BNF notation which looks like the following:

abc ::= ('foo' <bar>) | <baz> | <bar> <baz>

This reads as "An abc is defined as the letters 'foo' followed by a bar, or as a baz, or as a bar followed by a baz."

Consider the Newspeak language from George Orwell's 1984. Part of the grammar would look like the following:

word ::= ('un' <base>) | <base>
emphasised ::= 'plus' <word>
twiceemphasised ::= 'double' <emphasised>
valid ::= <word> | <emphasised> | <twiceemphasised>

Such a grammar allows us to, given the base word "good", say the valid words "good", "ungood", "plusgood", "plusungood", "doubleplusgood" and "doubleplusungood". This is the entire spectrum of "goodness" allowed by Newspeak, which is a purposefully restrictive language.

Now, what happens if we get rid of some of these rules? Let's try getting rid of 'twiceemphasised':

word ::= ('un' <base>) | <base>
emphasised ::= 'plus' <word>
valid ::= <word> | <emphasised>

We reduce the expressiveness, since we now only have one way to emphasise things, there's no level above "plusgood".

Now what if we get rid of "emphasised", but just call it another kind of "word"?

word ::= 'un' <base> | <base> | 'plus' <word>
valid ::= <word>

Now, the definition of "word" contains the use of a "word", which is recursive. What does this mean? Well "plusgood" is now a "word", and we're allowed to write 'plus' in front of "words", so we can say "plusplusgood", "plusplusplusgood" and any other number of new words. We can also say "plusplusungood" along with an infinite number of negatives.

Thus getting rid of rules completely (like "twiceemphasised") reduces what we can say, but by getting rid of distinctions and special cases (like the distinction between "word" and "emphasised") we get a whole new level of expressiveness. In fact, since we can say "plusplusgood" there isn't a need for "doubleplusgood" anymore, it's redundant, so there's no point putting it back in. Also, the idea of "valid" is also redundant, since it's now just the same as a "word", so we can get rid of that too, to reduce our entire grammar (minus the "base" vocabulary of words like "good") to:

word ::= 'un' <base> | <base> | 'plus' <word>

This grammar, even though it only contains two concepts, allows us to say infinitely more than the original grammar that contained five. We can even get rid of the distinction between "base" and "word" by writing it as:

word ::= 'un' <word> | <base> | 'plus' <word>

Now we can say "unungood", "unplusgood", "plusunununununplusplusunplusgood" and infinitely more new words.

Now, where am I going with this? Well, let's consider a bit of grammar for the C programming language:

simpletype ::= 'int' | 'float' | 'double' | 'char'
modifiedtype ::= <simpletype> | ('const' | 'long' | 'signed' | 'unsigned') <modifiedtype>
composite ::= <union> | <struct>
pointer ::= <type> '*'
type ::= <pointer> | <composite> | <modifiedtype>

This is a bit off, but will serve for our purposes. It says, quite simply, that we can make things that have type "int", "float", "double" or "char", or we can modify those types to get things like "unsigned long long int". We can have "unions" and "structs", which are built out of other types, and we can have pointers to any of them (including pointers to pointers (to pointers...)).

Now let's consider a similar thing in Java, which claims to be an "object oriented" language:

basetype ::= 'byte' | 'short' | 'int' | 'long' | 'float' | 'double' | 'boolean' | 'char'
type ::= <object> | <basetype>

Where anybody can create their own kind of "object", for example strings of text, key/value pairs, Web browsers, customers, etc. In the end though, everything in Java ends up being defined via a few things from "basetype".

If we look at the first Object Oriented language, Smalltalk, we can see why I said Java is "object oriented" in quotes:

object

That's it. EVERYTHING in Smalltalk is an object. If you want a number, that's fine since there are number objects. You want a true/false boolean? That's fine since there are true and false objects. No expressiveness has been lost by throwing away the complicated special-cases of languages like C, and by adding "base types" Java has gained no expressiveness over Smalltalk. In fact, by having more special cases we lose expressiveness. For example if we want to write, in pseudocode, a function for the square of something, we can do so in C like so:

int square(int num) {
return num*num;
}

char square(char num) {
return num*num;
}

float square(float num) {
return num*num;
}

double square(double num) {
return num*num;
}

We would also need to take into account the various modified versions, whilst structs and unions can't be squared in a general way. We're also forgetting here that C would complain about multiple function definitions, so we would have to call each function something different (eg. int square_int(int num)), and the obvious issue that some of these number types might not be able to store the result of the multiplication if it's too big (don't get me started on that bollocks). In Java we get a similar thing, although we're allowed multiple functions with the same name since they take different argument types:

int square(int num) {
return num*num;
}

float square(float num) {
return num*num;
}

byte square(byte num) {
return num*num;
}

long square(long num) {
return num*num;
}

short square(short num) {
return num*num;
}

char square(char num) {
return num*num;
}

boolean square(boolean num) {
return num*num;
}

double square(double num) {
return num*num;
}

Object square(Object num) {
return Object*Object;
}

The last case, of Object, won't work since Java has EVEN MORE special cases to do with operators like *, defining them for some kinds of objects and not others. Now, what would we write for Smalltalk?

[:num | ^ num * num]

That's it. Done. Works for everything (for which multiplication is valid).

The nice thing about using objects in this way is that everything stays symmetric, ie. you can treat everything in the same way. This lack of special cases and artificial distinctions means that it's much easier and more intuitive to make systems which handle everything thrown at them. As long as there's a sane fallback in the case of failure, we can leave this function (that one line) alone FOREVER and be confident that it will still work with everything we give it; we don't need to keep fiddling with it as more types are added to the language.

What's more, now that we've got this working function, we can stick it in a library and use it everywhere. We can do the same for branches, via the methods:

foo isTrue: [something run] isFalse: [somethingelse run]

That works for ANY foo, and the two code blocks given are of course examples. We can do the same for iteration:

foo do: [:x | something run using x]

That will work for ANY foo which is iterable. Everything works in the same way, 40 year old code can work with objects written last week, code written last week can work with objects defined 40 years ago.

If you're adding a feature to a language via extra syntax, ask yourself whether you're allowing the expression of something new which was not previously possible, or whether you're just breaking the symmetry between that feature and the entirety of the rest of the language.

To bring this back to where it started, I'm very interested in the development of Newspeak.

* More specifically formally defined languages and grammars, not broken grammars retrofitted to natural languages via the use of duct tape and insistence that the language's users aren't adhering to the 'standard' which is based around the user's use of it anyway.

Some Reading Material

2010-05-21T15:41:00.002+01:00

I thought I'd upload some of my University work, since I'm quite proud of it, so if you want to know about parallel programming, Physics simulations and Nvidia's CUDA then take a read of this http://chriswarbo.webs.com/CUDAProject.pdf

If you're interested in the world of the tiny, and what you can build given some pieces of DNA, take a look here http://chriswarbo.webs.com/DNAEssay.pdf

My thoughts on the new Amiga

2010-05-10T14:05:00.002+01:00

I heard a while back that there's a new Amiga being worked on, and it cropped up in my browsing today too. I thought it would be worth espousing my opinions on this.

The new machine is, supposedly:

Dual-core 1.8GHz PowerISA v2.04+ CPU.
"Xena" 500MHz XMOS XS1-L1 128 SDS.
ATI Radeon R700 graphics card.
2GB RAM.
500GB Hard drive.
22x DVD combo drive.
Customised case, keyboard and mouse.
7.1 channel HD audio.
Ports and connectors:

4x DDR2 RAM slots.
10x USB 2.0.
1x Gigabit Ethernet.
2x PCIe x16 slots (1x16 or 2x8).
2x PCIe x1 slots.
1x Xorro slot.
2x PCI legacy slots.
2x RS232.
4x SATA 2 connectors.
1x IDE connector.
JTAG connector.
1x Compact Flash.

Now, straight away I can say that most of this is marketing bollocks because it's commodity stuff that can be picked up from a skip somewhere. What matters is the following:

Dual-core 1.8GHz PowerISA v2.04+ CPU.
"Xena" 500MHz XMOS XS1-L1 128 SDS.
Ports and connectors:

1x Xorro slot.
JTAG connector.

Now, these are what sets this computer apart from others. The processor may well be a Cell, which would be great for programmers but we'll have to wait and see (remember: there are NO games out there that would use this; only intensive, custom-written code would benefit). The JTAG connector is nice for low-level and hardware debugging, whilst the XMOS and 'Xorro' make reprogrammable hardware useful. So what may it be used for?

The idea that one would buy a computer with integrated FPGA for developing embedded FPGA systems is optimistic to say the least. A PCI card with an FPGA is a much better investment, since it's cheaper, can be replaced when newer chips come out and can be put into any computer from the last 15 years (or PCIe if you're really wanting speed, at the sacrifice of capable computers). Development for external devices is thus out, so the existence of this chip is only of use to the machine itself.

Now, what can the machine do, given this chip on board? Well, right away we can say nothing: since the chip is accessible via the Xorro slot, requiring a loopback connector to something like the PCI ports in order to actually use the chip for anything. The requirement to install such a loopback negates a lot of the advantage of building it into the machine (ie. that it's guaranteed to be there and accessible). So what does that leave us with? Well, if you're not a programmer, nothing, since you'll have to wait for others to build stuff for it and that isn't going to happen, so you'll need to get out of your Microsoft/Apple bubble and learn how your computer actually works for a change.

Now, if you are a programmer then you could rewrite the chip to, for example, offload intensive computation. This would, like the (potential) Cell, only be of extremely limited use. For a comparison, just look at the amount of software that uses GPUs to offload intensive tasks: there's hardly any, except for a few graphics apps, and GPUs are everywhere. The big winners from General Purpose GPU programming at the moment are researchers wanting more speed in their similations. The reason for this is that once the code has been written, it is immediately useful. There's no requirement for support software like GUIs to be made, there's no need to create specific data like graphics, 3D models, etc. like there is in games development, there's no need to market or deliver the code to others. There's no need to make it general enough for large numbers of computers. Once it's been written and is working on your GPU, then give it some numbers to crunch and get back the results. Done. Once again I'll state it: if you're not a programmer, this is of no use to you.

So what could we use an FPGA for, really? I would like to see FPGAs become integrated alongside CPUs/GPUs as co-processors, such that often-used programs (eg. Web browsers) can be compiled to the FPGA and run much faster. This would require a paradigm shift in compiler technology which puts it a long way off as yet, but in any case this isn't a good start since, as I said earlier, the FPGA isn't connected to the rest of the machine in a closed loop! When we consider that those experimenting with FPGA compilers, high-level languages, static analysis and such are often releasing their code as Open Source, then we can be rather certain that a Linux box would do much better than an AmigaOS box, and that if Linux is the target then any off-the-shelf/out-of-the-skip box will do, given a PCI FPGA card.

tl;dr: All if does is integrate (badly) existing technology, in a way that won't appeal to developers and doesn't have any point for "consumers" (a word I am defining to mean those too lazy to learn how to read and write).

Diet Python

2010-05-09T03:29:00.003+01:00

I've talked about this before, but have been doing some more work on Diet Python (available in my Python Decompiler on gitorious.org).

That's not the goal of Diet Python. In Diet Python we don't really care about readability or programmer-friendliness, and the syntax can be as awkward as we like as long as it's still valid Python. What Diet Python does is throw away the redundant bits of Python that can be replaced with other Python that does exactly the same thing.

As a simple example, a + b does the same thing as a.__add__(b), but if we're making a Python interpreter we have to handle both + and .__add__. Diet Python throws away the +, since it's less general than the function call, so that Diet Python implementations only have to care about .__add__, which they would have to handle anyway since it's a function call and function calls are everywhere in Python. Diet Python has a 'compiler' which translates Python into Diet Python, so that we can write normal Python (eg. a + b) and then strip away the fat to get the __add__ equivalent. This id "Diet Python", but since it's also perfectly valid Python it will still run fine in a standard Python interpreter.

There are two approaches I'm taking with Diet Python. The first is to remain 100% compatible, so that there is no change between the semantics of the Python input and the Diet Python output, and both will run the same in a standard Python interpreter. The other goal is to see just how much of Python we can throw away, without losing any functionality. Some of this relies on incompatibilities with the standard CPython interpreter, but only due to limitations in the interpreter.

For example, in Python we can do conditional branches like this:

if a:

print b

else:

print c

Whilst in Smalltalk the same thing is done with a message send (function call) like:

a ifTrue: [Transcript put b] ifFalse:[Transcript put c]

So, can we throw away Python's keywords and use a Smalltalk-style message-send? Well, this would look something like the following:

a.__if__(lambda:print b, lambda:print c) # Stupid function use, for demonstration only

But this would require a bit of support in the form of:

True.__if__ = lambda first, second: first()

False.__if__ = lambda first, second: second()

Now, this all looks fine and dandy until CPython tells you off for trying to modify the True and False objects, which are written in C without any of Python's dynamic capabilities. To me this is a bug in the implementation, however since the only standard for Python is what the CPython interpreter does, this is actually the expected, valid behaviour of Python :( This is the reason Diet Python has two approaches: one does everything we can, given the inherent limitations of CPython's internal structure, whilst the other sees what we can do with a language if it were 'Python all the way down'.

Given enough of each type of translation, compatible and uncompatible, I hope to able to get Python code down to a bare minimum of syntax. At the moment I believe that at least all operators can be done away with, since the only ones left are bit shifts which I've not bothered translating yet since I've never used them. After that I think every keyword can be thrown away; elif is sugar for else: if:, whilst all of the hard work in if: and else: conditions is actually just working out the truth value of the condition, which it does itself, so we can thus give True and False methods like the above. I'm undecided about for loops at the moment, I may try a map approach or I may convert them to a while using the __iter__ method. while itself may require a translation to Continuation Passing Style which would be interesting, but that would also get rid of try:, except:, finally:, yield, pass, break, continue and return for us. Function and class definition can be achieved with __new__, and if we change the behaviour of globals() and locals() to define mutable return values then we can do away with assignment, imports, numbers, strings and other such things.

Once we've done this, we have a tiny target which Python implementations must handle. Everything else can be implemented by asking Diet Python to translate it away :)

=-=-=-=-=
Powered by Blogilo

What Makes Me A Geek: Reason 0x54F6

2010-05-09T02:42:00.002+01:00

I have only ever paid for one album in my life. The rest of my music is freely distributable online. The name of that album is 01011001, which is Y in ASCII.

=-=-=-=-=
Powered by Blogilo

(Anti)Object-oriented reasoning

2010-04-27T09:30:00.005+01:00

Brain dump:

Object-oriented programming is a style of writing instructions for computers which was invented to make comprehending these instructions easier. Using a list of things to do, like a cooking recipe, works well for short tasks, but with a computer it is required to provide every step of every instruction. Imagine a recipe that has a step "break two eggs into a bowl, keeping the yolks separate". This is a "high-level" instruction, since it doesn't tell us what muscles to move, what senses to pay attention to, etc. Making high-level instructions can be done by declaring "functions", such as "break_eggs_into_bowl(egg_number, separate_yolks)", then specify in this function exactly how to do this. Once the function is declared we can simply say "break_eggs_into_bowl(2, true)" in our recipe, rather than having to specify them all over again. Of course, we can use functions inside functions, so we could even make the entire recipe a function like "make_cake(flavour)" which includes running the function "break_eggs_into_bowl(2, true)" as well as many others. The problem then becomes how to keep track of all these functions.

Using "libraries" is one way of doing this; you put everything to do with images in an "image library" and everything to do with music in a "music library", and so on, then when you want to write a program which handles images you just say 'I'm going to use the image library' (eg. in C this would look something like "#include " and Python would look something like "import images"). The problem with libraries is that, since they're meant to include ("encapsulate") everything to do with their subject (so that nobody using it has to care what it does, only what it's functions are called) by dragging a library into a program you end up "polluting the namespace".

A "namespace" is the embodiment of everything a program knows about at a certain point in its execution. Before we declare the "break_eggs_into_bowl" function it is not in our namespace, by declaring it we put it in the namespace so that later on we can use its name and the computer will know what we're talking about. The problem with libraries is that by asking to include them in our program, the namespace of our program gets filled with everything from the library. That might be good in that we can include the image library then say "display(my_image)", but we have to be very careful that names don't get overwritten. For example we might want to make a spreadsheet that uses a graph library and an image library, but they might both declare a "display" function. It would not be obvious to us that our command "display(my_image)" is broken since it's actually trying to draw a graph because both functions have the same name. That's why we use more than one namespace in our programs, so that a command "import image" in Python won't make everything from the image library directly accessible, instead it makes the namespace of the image library accessible so that we can say "image.display(my_image)" and, if we like, "graph.display(my_graph)". That makes it much more obvious to us which one we're using, and the only names that get put in our namespace are those of the libraries, which we've explicitly asked for. There are no hidden surprises caused by unknown things overwriting parts of our program.

An extension of this is to use Objects. An object is like a library, in that it encapsulates everything about a given topic, but objects make it easier to understand our programs since we can treat them as the actual things themselves. Rather than saying "import image" then "image.display(my_picture)" we can say "my_picture.display()", ie. we send a message to "my_picture" asking it to display itself. The reason this makes understanding code easier is that we make the assumption that whoever made the object has done it sensibly (the same assumption we must make about libraries in fact), so that when we ask our objects what to do, they react in intuitive ways. Another nice thing about objects is that they know all about themselves, so whereas before we had "graph.display(my_graph)" and "image.display(my_image)", if the graph and the image are objects then we can say "my_graph.display()" and "my_image.display()" and they both know what to do, even though we're asking them the same thing. In fact, we can just say "something.display()" and it will work whether "something" is a graph or an image, we don't have to care. Later on we can make a Web page object and tell that what to do when asked to "display" and voila our "something.display()" now works for Web pages too.

Object oriented programming allows us to write programs as a bunch of interacting objects, a lot like the real world is. Since we can handle the real world pretty well, this allows us to transfer those skills to our programming. However, OO programming is not just limited to creating models of the real world. For example, the use of "anti objects" can make programs much easier to write and understand, even though they go against what we know of the world. Anti-objects are objects in a program which don't represent anything that exists, but since we're making a computer program there's nothing to stop us making up such things and then making them do stuff for us. The classic example is the game Pacman. If you want to write a Pacman game, the hardest part is trying to make the ghosts intelligent. They have to chase Pacman (ie. head towards Pacman), but they also have to work around the walls of the maze, it's no good just homing in on Pacman if there's a wall in the way. By using the level as an anti-object we can make the job of the ghosts much easier: rather than having intelligent ghosts that try to think of the best way to get Pacman, we instead make each part of the level contain an amount of "pacman-ness". Wherever Pacman is has 100% pacman-ness, every wall has 0% pacman-ness and the pacman-ness of every other square in the level is the average of its neighbours. This makes the 'pacman-ness' diffuse through the level like a 'smell', but since it doesn't go through the walls the pacman-ness of each square becomes a good indicator of the distance from that square to pacman, following the maze. Now the ghosts can be really dumb, since they just have to choose their next move based on whichever direction has more pacman-ness and it will always be the best move. In fact, if the ghosts are made to act like walls (ie. they don't let pacman-ness through) then once a ghost has blocked a path leading to pacman, it will also block the pacman-ness smell. The other ghosts will thus find alternative open routes to pacman and the player's escape routes will be blocked off. This guarantees that the ghosts will beat pacman if the number of pacman's escape routes is less than or equal to the number of ghosts. I wrote such a pacman game in an afternoon, but unfortunately it's on my laptop which is bust at the moment so I can't share it. Still, it was an interesting approach to the problem, even if the resulting game became too hard to ever beat even with 1 ghost :P

So, we can encapsulate domain-specific knowledge inside objects, we can ask many different kinds of objects the same thing and they can interpret it in their own specific way and we can invent objects that don't necessarily exist in the system we're modelling, and transfer our logic to them. How might we use this to make an AI?

Imagine that we generalise the pacman example: rather than ghosts, we have a more general concept of agents and rather than pacman we have a more general concept of a goal, of which there can be many. The space, rather than being a maze which we traverse with movement, becomes a more general space of every imaginable scenario which we traverse by taking actions (a generalisation of movement). In this space we have objects for everything we know about, rather than just pacman. Each type of object has a 'smell' in each scenario, which means "how likely are you?"; ie. given that scenario, what is the chance that an agent can obtain or access you? The objects can update their own likelihoods if they encapsulate enough domain-specific knowledge of themselves, which can be learned over time. The agents then just decide which goal/goals they want and take the action which leads to a scenario where the goal is more likely. The only major complication is that the scenario space isn't fixed: every object may add contributions, but considering that the probabilities will be multiplied (eg. the probability of having an Internet connection via a computer is the probability of having a computer * the probability of it having an Internet connection), thus they fall off rapidly and simple heuristics can prune the scenario space quite quickly.

In such a system, our reasoning does not have to depend on what we know, since every object looks after itself. Thus a separate program can handle the creation, specialisation and connections between objects (for example through a hierarchy of Bernoulli trials performed on the sensory input). A problem in AI is often in choosing what to do. Given our probability system for sub-goals which extends to whatever granularity we like, we only need one top-level goal, which I propose is "Maximise your freedom". This sounds very philosophical, but essentially it means that, without being given anything else to do, the program would try to improve its position in the world so that it can do more things in the future. This could involve performing tasks for payment, since the possession of money increases what it is able to do. It could of course rob a bank to obtain money, but there is a large probability of being caught and deactivated if that course of action is taken, and being deactivated stops the program from doing anything, and is thus avoided (ie. self-preservation). By maximising its freedom, a program will be more likely to be in a good position for doing tasks asked of it in the future.

This is just a vague, hand-wavey brain dump, but would probably be interesting to build...

The Web as an Oracle

2010-04-12T22:13:00.004+01:00

I've tried a few times to write up my programming thoughts to this blog, each time from a different perspective and getting rather off-topic most of the time. Those posts will probably appear soon, since I've invested the time to write them I may as well publish them, but a thought struck me about how to clarify my meaning in a concise way.

My ideas have been revolving around formal specification and verification of programs. Since I approached the subject from a Python perspective it meant living without the luxury of an enforced type system, definite syntax and semantics, immutability of variables, etc. that one gets with a functional language like ML or Haskell. Since anything in Python can be redefined at any point, for example swapping an object's class via my_object.__class__ = Foo, I started by considering a system that broke down code into black-box style atomic operations (assuming a single thread, because I'm against multithreading as a usable model for concurrent processing).

For example, we could look at a function and work out conservative bounds on the preconditions and post conditions. For example if we have a function which runs "argument.foo += 1" then we know that the argument "argument" must contain something called "foo", unless we're catching a runtime exception, it must be mutable, have a runnable method "__add__" which accepts the argument "1" and so on.

It struck me that bundling such specifications with the code would be useful, but it would be a far cry from a verified system. For example, one can replace an object's methods at any time, so the specifications of code snippets like functions would have to be self-describing only and make reference to the specifications of their arguments and global names, etc. since they can't be relied upon to be known before run-time. That way, at runtime the full specification can be derived (once the arguments are definitely known), but not before.

In essence, a function's specification is built upon the specification of its arguments, accessible namespace members (eg. globals) and the semantics of the language. If this is the case then even having a complete, correct, verified specification of the language (eg. Python) does not let us make assumptions about functions, modules, etc. without knowing their arguments. The system's state is just as powerful as the language; in fact, the system's state can be regarded AS the language! Running the same function in different environments isn't just an impure, non-functional way of working, it may as well be running the same function in two different languages!

With this in mind it became obvious that the lack of ability to make valid specifications is a boon: current state, libraries, programming language, etc. can be combined to give a combinatorial explosion of languages to predicate a function's specification on. Thus we don't NEED a specification for Python at all, since it would be tainted by whatever modules we import, and those would be tainted by the running program's state, so we just stick to our conservative specifications like "it must contain foo" rather than "it must be an (int x int) -> float" and we can refine these as we go by making more and more of them for each library, language, etc. we come across. Thus we don't get a formal specification, but we do get an algorithm to piece together a specification given at least one set of loose, conservative specifications. We don't need to verify all of the way down to the metal; we can verify what we can and leave the rest for later (ie. use them as axioms).

What is the algorithm for doing this? It's reasoning. Predicate logic. It's just the thing RDF/OWL is good for! So what happens if we have an RDF database of code along with specifications? First of all we do a massive Web crawl and fill our database with code. Then we do a massive spec-finding session (automatically of course). Then we do a load of cross-referencing and such (ie. if function foo's spec says it requires XYZ and function bar's spec says it returns XYZ then we know that foo(bar) is a reasonable expression to consider). Essentially we can make a program synthesis engine which, rather than writing a program from scratch and thus searching the entire space of possible programs, we piece one together from stuff people have bothered to write and upload (which should remove a lot of the trivial and dead-end branches from the search tree). Also, by abstracting to a search, rather than using a deterministic pattern-matcher (for example) we make the algorithms to build such a system much simpler, at the cost of large resource overhead. Worth building in my opinion, as a more powerful evolution of the "code snippets" databases that are springing up.

Enviro Mental

2010-04-12T16:16:00.002+01:00

Just found this baby:
Either it's a recycled PDF, or it's prescient about how I'm going to print it off.

Unfortunately only 23.4% of this blog post is recycled.

Publicly whoring onesself out for politics

2010-04-08T16:05:00.001+01:00

Quoting from here:

The Conservatives said the bill, as it stood, was an "Amstrad" when "we wanted an IPod".

Why compare Sky digiboxes to music players?

Of course, whoever came up with this probably doesn't know or care that Amstrad are still going and have been making set top boxes for Sky for ages. They were probably inferring PCs from 20 years ago. If I were to reinterpret their analogy in this way then it would be an analogy between a well-known, understood, documented, agreed-upon, standardised, tested and universally relevant computer: the "IBM Compatible", which we would now call x86, which for some reason in this argument is specifically referring to one sold by the Amstrad company rather than any of the identical such units shipped by other companies; and on the other hand would be a locked-down, secret, proprietary, incompatible, unknowable, vendor-controlled, feature-stripped computer: the iPod. Yes I'm a freetard, but the point of discussing a law is to debate the freedoms and restrictions it implies, so those are the only relevant characteristics we can use when interpreting this analogy.

Give me such an Amstrad and I'll plug in a few hundred GB of storage and use it as a file server. Give me an iPod and I'll most probably try to blend it, since it's fun to watch the glowing screen bouncing off the blades. Apparently some people actually buy iPods, but I can't justify that price just for a few seconds of blending fun. Maybe I could think of a different use for one if I happened to get one, but I can't fathom any at the moment. It's too glossy to make a good doorstop, since it would just slide over the carpet, even if you jammed it right under the door.

=-=-=-=-=
Powered by Blogilo

My Current Browser Tabs

2010-04-07T11:34:00.001+01:00

A while ago, Firefox implemented one of Epiphany's awesome features: the ability to restore a crashed browsing session. This was then extended to support restoring the previous session regardless of whether it had crashed or not, and then the implementation changed from having a single saved session with "OK/Cancel" dialogue to restore, into a specially crafted locally generated Web page. What's cool about this implementation is that, since the restore session system is just a page like any other, it too can be restored. I thought it would be insightful to list all of the open pages I have in Firefox, including the contents of the Restore Session pages. As I write this I don't know what's in there, but unfortunately I had to delete the saved sessions a while back since starting Firefox made my desktop go into swap-death. So, here is a tree view of my current Firefox session.

=-=-=-=-=
Powered by Blogilo

Twilight: New Moon

2010-04-01T21:27:00.000+01:00

Either do an in-depth character exploration, or do some mindless entertainment. This is neither. It's not the former, since the characters are all stereotypical, as shallow as puddles and annoying whiney attention seeking whores. It's also not the latter since it's fucking boring. Apparently this inanity goes on for two hours, so I'm off to read some more papers on programming language theory.

Browsing on a budget

2010-04-01T19:21:00.000+01:00

I've been trying to find a perfect browser for use on my XO and have almost exhausted Fedora's repository ;)

The default Browse activity, based on Firefox 2's rendering engine, is slow, very resource hungry, doesn't have tabs and only allows access to the XO's Journal, not the filesystem.

Midori is nice and fast, since it's Webkit based, but the file manager doesn't work :(

Kazehakase was my choice for a while, which can use Gecko (Firefox's renderer) or Webkit, but it suffers an annoying bug such that it thinks the window is wider than it is, so that constant left-right scrolling is needed to read every line. Zooming in and out and changing the text size don't help, the lines stay longer than the screen but just fit more characters on them.

Dillo is great: fast, lightweight and turns off unnecessary cruft. However, I find it can be a little too much of a compromise when page layouts are affected.

I thought I'd give Seamonkey a whirl, the latest rebranding of the classic Netscape suite, and I think it's just about what I'm after. It's a bit hefty in the resources side, but runs fast, especially once I turned Javascript off. I'm gonna set up the news and mail client too, so that I don't have to visit any bloody Web sites over and over.

Also, for those using ojp.nationalrail.co.uk , disabling their Javascript crap makes buying train tickets a hell of a lot more straightforward.

Divergence and reduction with complex numbers

2010-03-26T12:40:00.009Z

I came across this introduction to the concept of "imaginary" numbers, and thought it would be worthwhile to write a post about how cool complex and imaginary numbers actually are.

If you don't know what an imaginary number or a complex number is then don't worry. That link provides quite a nice intro, and I'll give my own here:

An "imaginary" number is a number which doesn't fit anywhere on the number line. No matter how closely you zoom in, or how far along you go, you'll never find it. That's why they're called "imaginary", even though it is an unfortunate name as the other blog points out. Before you dismiss imaginary numbers as useless, let's consider another set of numbers which is made up and doesn't exist in the real world: negative numbers.

Negative numbers cannot exist like the natural (positive) numbers do. You cannot have -5 apples. Nevertheless, negative numbers are useful for made up mathematical worlds, like banking for example, which can have a definite impact on the real, physical world. Negative numbers also arise in situations involving symmetry, relative values and arbitraryness. Let's take a realistic example: if we think of positions, there is no set of coordinate axes in the physical world, and the whole Universe is symmetric spatially, so we can just make up the numbers we use to be anything we find convenient. Let's say we've got a chocolate bar:

We'd like to be able to refer to each section of chocolate in a unique way, so we can say that the bottom left section is at position (0,0), and define our unit of length to be one chocolate section. Thus we can say "The sections at (0,2) and (0,3) have been bitten". Now let's say that Dr Ed Daw has had a busy day and didn't have chance to grab some food. He's so hungry that he doesn't have enough energy to move more than one unit of distance to get the food he needs, but he spies our chocolate bar. Can Dr Daw get the food he needs?:

To find the distance between the doctor and the chocolate we need to know the doctor's position. We can't use a positive number to define the position, since even though there are an infinite number of them, they get less and less accurate the further we look. Instead we have to use a negative number, allowing us to say that Dr Ed Daw is at position (0, -1). We know there is chocolate at (0,0), so to get from his position to the food only takes one unit of distance, since (0,-1)+(0,1)=(0,0). The only reason we had to use a negative number here is because of the way we defined our mathematical model of the situation. There's no such thing as "negative position", but when we used the doctor's negative position to find the distance he has to move, which is a physical quantity, the negative numbers disappeared and we got a meaningful, and correct, answer.

So let's move on to imaginary numbers: Close to the surface of the Earth, gravity is pretty constant, with a value of 9.81 metres per second per second. This means that vertical speed (metres per second, miles per hour, etc.) will go down by 9.81 metres per second (if it's pointing up), or up by 9.81 metres per second (if it's pointing down) every second. Speed describes how your position changes in time (eg. how many metres you move in a second), so the position of something flying through the air will change by the speed which itself will change due to gravity, so the position will curve. The shapes made by these curves are called parabolas and behave like the quantity -Ax^2 + Bx + C, where x is your horizontal position (or you could use time here instead) and A, B and C are numbers specific to what you're looking at. We get a minus sign for the x^2 because gravity points down and we define up to be positive. If we want to know at what position or time a ballistic (falling) object will reach a certain height, what we're really asking is at what position or time does Ax^2 + Bx + C equal the height we're interested in. We can do this with an example: Dr Daw has finished his chocolate and is trying to show off some lasers to his younger, more tanned brother. They each attach a laser to their head, Ed takes the red one and his brother De takes the green one. The lasers need to be kept cool, so they go to the Sheffield Ski Village. While they watch the skiers go past, De asks his brother "When do the skiers get higher than the lasers attached to our heads?". How can Ed work this out, given that the skiers motion can be described by -x^2 + 0x + 5, that De's green laser is a height of 4 and that Ed's red laser is at a height of 6?

Ed knows that he can take the skiers's motion and, using the apex of the jump as position 0, work our at which positions they get above the lasers by saying -x^2 + 5 = 4 when they get above De's laser and -x^2 + 5 = 6 when they cross his laser. Working out the first gives the valid positions, x, as:

-x^2 + 5 = 4
-x^2 = 4 - 5
-x^2 = -1
x^2 = 1
x = +1 or -1

He tells his brother that the skiers will cross the green laser at positions -1 and +1, since they satisfy the equation of motion. He then tries to work out when they cross the red laser:

-x^2 + 5 = 6
-x^2 = 6 - 5
-x^2 = 1
x^2 = -1

Then Ed gets stuck, since there's no positive or negative number he can think of which would fit as x here. Thus he declares to De "There are no solutions, so the skiers never get above my laser.". De is not satisfied with this. He says "That's cheating. I want you to finish working it out.". Ed knows how stubborn his brother is, since he carried on wearing fake tan even after going on "Snog, Marry, Avoid" the previous year, so he invents a number to satisft this equation:

"The skiers cross my laser whenever they get to a position which I will call N. They will also cross the laser if they get to a position -N. Thus, +N and -N are the solutions to this equation."

De is still not satisfied, so he asks his brother what N is. The doctor then explains imaginary numbers to the younger man:

"N is a quantity that is not a positive number, or a negative number, however it is a very useful quantity, since it lets us solve the equation for my laser. You can't find it no matter how closely you look between the numbers, or how far along you go. This means that its value is orthogonal to the real numbers, since the two are independent, in the same way that you can't change an x coordinate by moving in the y direction. In fact, we could draw a diagram using the real numbers as an x axis and these imaginary ones as the y axis."

"I'm confused." said De, "Will you please draw me such a diagram?"

"I can't be arsed," Ed replied, "so here's one I found on Wikipedia."

Using this diagram, Ed could explain to his brother how a Real number (Re) sits on the horizontal line, how an Imaginary number (Im) sits on the vertical line, and how the quadrants are filled with numbers that have an imaginary part and a real part, and are called Complex numbers. De seemed to understand, but had some questions:

"OK, I'll accept what you just said, but then where does our quantity N fit in this diagram? Also, there are some undefined variables; what is the value of the "i" that's written on the diagram?"

"The "i" represents the Imaginary unit." Ed explained, "It's equivalent to the number 1 for natural numbers, and -1 for negative numbers. Every Imaginary number is made out of some quantity of i."

"So what is the value of i?"

"The imaginary unit is defined by the equation i^2 = -1. No more, no less."

"But that's the equation for the skiers crossing your laser! That means that N = i and the skiers will cross if they ever get to a position i, which they can never do because imaginary space is orthogonal to physical space, so no force can ever push them off the Real lines for x, y and z."

"Well done" said an impressed Ed "but you're forgetting how to do square roots! There are always two square roots of a number, just like we had +N and -N. That means that i^2 = -1 and (-i)^2 = -1. So tell me, does N = i or does N = -i?"

De thought about this for a minute before declaring "There's no way of telling! If N = i then N^2 = -1 since i^2 = -1, but also (-N)^2 = -1 since the minus signs cancel so -N = i. But also, (-i)^2 = -1 so N = -i and, because the minus signs cancel, i^2 = -1, so N = i. So N = +i or -i and -N = +i or -i, they're equal!"

"Don't be too hasty to call them equal!" cautioned Ed "If N = -N then i = -i and I could do the following:

i = -i This is what you are claiming
i + i = -i + i We can add i to each side to preserve the equality
2i = 0 Adding i to i gives 2i, whilst adding i to -i gives zero
i = 0 We can divide both sides by 2 and preserve the equality
i*i = 0*i We can multiply each side by i and preserve the equality
i*i = 0*0 We showed that i=0 so use that on the right hand side
i*i = 0 We know 0*0=0
-1 = 0 From the definition of i, i*i = -1

We have reached an absurdity! The only conclusion is that i cannot be equal to -i, and thus N cannot be equal to -N."

"So which way around are they?" implored De.

"It's unknowable." replied Ed, "You can use either i = N or i = -N and you'll get the same results. Swapping every i for a -i in any Maths will change nothing, as long as you're consistent in which value (i or -i) you take to be positive. By convention we say that i is positive, and that -i is negative, but that's just a sentence in this silly human language of ours. It has no mathematical meaning, since they are both the imaginary unit, whilst also being distinct and not equal."

"Fascinating!" exclaimed De, "Can you give me some examples of swapping i and -i?"

"No." said Ed stubbornly, "We've taken this example far too off course, so we'll leave Chris to explain that. Now let's take these lasers back to the Hicks before Professor Fox realises we've taken them!"

Q.E.D.

So, why is having two imaginary roots cool? Well, just as in the case of negative numbers, where the physical quantities like length always end up positive despite our use of negative numbers in our made up mathematical models, similarly every physical quantity calculated using imaginary numbers turns out to be real, and furthermore it turns out the same no matter whether you use i as your basic unit of imaginaryness or -i. They both represent the same unknowable pair of imaginary quantities that Ed called +N and -N, and since we can never know the "N"s we may as well use the "i"s, and just treat them as algebraic names (like we would "x" or "p" or any other variable name), and always keep in mind that the equation i^2 = -1 is simultaneous to everything we do.

So on to some examples of swapping the signs. Mathematically, swapping the sign of the "i"s in a number is called "taking the complex conjugate", so Ed's explanation tells us that if we take the complex conjugate of the entirety of Maths, we'll get the same thing that we started with.

In Quantum Mechanics there are imaginary and complex numbers all over the place. Instead of describing things in 3D space with x, y and z being the units of length in each direction, we instead use what is called a Hilbert space, which allows us to use all manner of crazy things as our axes, and any number of them we want. In a complex Hilbert space, ie. a space where positions may include imaginary components, there is what's called a dual space, containing the complex conjugate of everything in the original space. Since taking the complex conjugate doesn't do anything as long as we do it consistently (ie. to everything) then any Hilbert space can be swapped with its dual and nothing about the Maths will change!

A closely related example is that when using Dirac's notation for Quantum Mechanics, we have a "bra" and a "ket" which together make a "braket". 'Bra A' looks like <A|, 'ket A' looks like |A> and a braket looks like <A|A>. The bras represent complex conjugates whilst the kets represent the original values, so <A| is the complex conjugate of |A>. Essentially bras and kets represent views into the Hilbert space and its dual: |A> is A as seen in the Hilbert space we're using, whilst <A| is A as seen in the dual space. Since we can swap the Hilbert space and dual space, we can use bras instead of kets and kets instead of bras and get the same answers to our calculations.

Another interesting use of complex conjugates is in the transactional interpretation of Quantum Mechanics. Quantum Mechanics involves lots of funky Maths, which works, but when people look for stories they can tell about what the Maths is doing (for example, if BBC's Horizon wants a voice-over to an irrelevant analogy) then there are several ways of explaining it. A nice idea is the transactional interpretation, where Schroedinger's equation (which describes how a quantum system changes over time) and its complex conjugate (which arises due to relativity) are both taken to be actual Physical laws. In other interpretations, the complex conjugate form is discarded as unphysical (like Ed tried to initially do with the red laser equation), leaving the Schroedinger equation to describe the movement of waves over time. This is a bit of a rubbish thing to do though, since we know that our imaginary units represent the same quantities, so we'd like a solution which doesn't involve throwing away whichever imaginary 'direction' is inconvenient. If we do keep the complex conjugate version then we get a second equation describing the movement of waves backwards in time, which is pretty peculiar but we're just upright apes so that's no reason to stop investigating.

The transactional interpretation of Quantum Mechanics shows that every event sends waves forwards and backwards in time, for example the emmission or absorbtion of radiation. However, we don't see these "waves from the future" since they stack up on top of each other and end up cancelling each other out. For example, an electron emits radiation and sends it forwards and backwards in time. Later on an electron absorbs this radiation and it too sends waves forwards and backwards in time. The forwards-in-time wave given out by the absorbtion exactly cancels with the forward-in-time wave given out by the emission, so at times after the absorbtion, the waves cancel to nothing. Likewise the backwards-in-time waves cancel for all times before the emmission, so there's nothing about an event which exists before it occurs (since the waves, when multiplied by their ocmplex conjugate, give probabilities. If the waves cancel to zero then the probability of anything to do with the wave existing at that point is zero). In the time between emmission and absorbtion, there is a wave travelling forwards in time and a wave travelling backwards in time, which turn out not to cancel, and we see one wave (the sum of the two) as we travel along in time. This is nice since we can swap the "i"s for "-i"s and get the same results, we'd just change the direction in time we're travelling in from "forwards" to "backwards", but like the +N and -N of Ed Daw's example, we've just made up those concepts as if they mean something. The reality is that there's no way of making such a distinction, so it becomes meaningless to try and find the values of "+N", "-N", "forwards" or "backwards". Just choose one and stick to it, like we normally choose "i" to be the positive root and "forward" to be the direction we perceive as our neurons interact thermodynamically.

Blogilo test

2010-03-22T17:35:00.001Z

Having problems getting Blogger to talk to Blogilo, and since the Blogger interface is a fucking shit bollock Web turd I'm playing with Blogilo to see if I can get it working.

=-=-=-=-=
Powered by Blogilo

Digital Economy Bill

2010-03-18T22:13:00.000Z

In case you weren't aware, the Digital Economy Bill is being rushed through parliament right now, despite it granting ambiguous and far-reaching powers which will harm entire organisations in the name of copyright infringement witch-hunts against individuals. I urge you to go to http://www.38degrees.org.uk/page/speakout/extremeinternetl read about the bill and contact your MP via the box on the right. Here's the email I sent (reworded from the default).

Dear Mr Caborn,

I'm writing to express my concerns over the Digital Economy Bill, which the Government is planning to rush into law without a full Parliamentary debate.

The proposed law has caused much controversy, in itself reason for ensuring a thorough public debate, and contains many measures that worry me. I implore you to see that the Bill undergoes proper, rigorous scrutiny, in public view, and is not rushed through without sufficient discourse. Many people have stated that its coarse-grained punishments will damage schools, businesses and innocent citizens who rely on the Internet, in its heavy-handed provisions aimed at disconnecting those individuals suspected of copyright infringement.

Industry experts, Internet service providers (for example Talk Talk and BT) and Internet businesses like Google and Yahoo! are all opposing the bill - yet the Government seems intent on forcing it through without taking on board these comments or allowing thorough debate.

As a constituent I am writing to you today to ask you to do all you can to ensure the Government doesn't just rush the bill through and deny UK citizens our democratic right to scrutiny and debate.

Regards,
Christopher Warburton

[address withheld from blog]
[telephone withheld from blog]

I've Got an XO!

2010-02-26T17:00:00.002Z

Hello, world! I'm typing this from my newly acquired XO laptop, otherwise known as "Children's Laptop 1" or the "$100 laptop".

Despite my l33t usage, Sugar's actually pretty nice to use. I've put leafpad, Kazehakaze (browser), XPDF and Pidgin on it, which suits my needs well along with a terminal. I would use the default Sugar apps, but their restriction to interacting only with the Journal database and not the filesystem gets in my way a bit, especially with there being no Journal-accessing terminal.

Getting online at Uni takes the use of a shell script, as the eduroam network doesn't appear in the Neighbourhood, but it doesn't bother me one bit that my Free Software XO doesn't sit particularly comfortably with immoral technology like WPA.

It came with an SD card of Ubuntu Intrepid, which I immediately tried to upgrade to Karmic which broke it. After reinstalling via Qemu and chroot I found the problem was in the init system. Taking apart the XO's initramdisk image yields a collection of Python scripts and some Pyrex (which needs compiling! That took me a while to track down) which are part of the Bitfrost security system. Since this is always running, spawning sysvinit, it doesn't work well with Upstart, which only works when it's PID 1. cAfter gutting Bitfrost, getting Upstart to work but having further problems in the boot, I decided to screw the whole thing since I prefer Debian anyway. After half an hour Debian was up and running, although X still doesn't come up. Oh well, it gives me something to do next!

Fffffffffffffffffffff...

2010-02-23T15:09:00.001Z

A Whole New World

2010-02-15T20:39:00.001Z

I've found a couple of programming language projects which introduce the concept of "Worlds" as first-class citizens, although in slightly different ways.

In the land of Object Oriented programming, ie. Smalltalk and its derivatives, the concept of worlds is used to encapsulate the state of a program. All computation happens in a world, getting the current world is a simple function call, new worlds can be spawned from other worlds (OO-style inheritance applies to the worlds) and any world can be "committed to", ie. moving the rest of the computation into that world where it carries on. Essentially it gives programs an internal "undo" system, which can be used to try many possible execution paths safely. Some use cases are the following:

We want to do goal, and there are X ways we could go about doing it.

We split our computation into X new worlds, all running concurrently.

In each world we attempt a different way of fulfilling goal.

Once goal is achieved, all worlds except the current are deleted.

The program continues to run in whichever world managed to satisfy goal first.

This way we guarantee that we reach goal using the fastest method (since we use every method), but this is achieved in an inherently distributed way: running multiple, concurrent attempts on one CPU in one machine may often give slower results than arbitrarily choosing one attempt and waiting for it to finish, even if it's not the fastest way possible. However, the nice thing about this use of worlds is that concurrent processing power can be utilised in an easy way without conflicts, and the thought required to understand it is very minimal; there's no scheduling, preempting, breadth-first/depth-first tradeoffs or anything like that. Just try everything and the fastest one will win by virtue of being the fastest, then move on to the next part of the program.

Another simple way of using worlds is to deal with potential errors (ie. exceptions). This is useful since exception handling is notoriously annoying to get right. In many programming languages and paradigms, when something fails (like attempting to contact a remote server for example) then the computation stops and an "exception" gets "thrown"/"raised", which means that whatever asked for that computation to happen is given an "exception" rather than whatever it requested. Receiving an exception is essentially a "GOTO" which jumps to whichever bit of code is assigned to deal with that type of exception (for example there might be SyntaxError, IOError, DivisionByZeroError, etc.). The problem with exceptions is that the catch-all nature of their handlers makes it difficult to determine where the exception came from. For example, we might write (in Python):

import urllib2

import time

page1 = urllib2.urlopen('http://www.identi.ca/warbo')

time.sleep(60)

page2 = urllib2.urlopen('http://www.identi.ca/warbo')

rate = post_difference(page1, page2)

print str(rate)+" posts per minute"

This downloads my Identi.ca timeline and gives it the name page1, then waits for a minute and does it again for page2. Some arbitrary function called post_difference is run, presumably to count the difference in Identi.ca posts between page1 and page2, and the result is called rate. We then write out a string of rate along with units. A problem with this is that the download may fail, and we haven't given any code to handle this, which means the program will exit with an error if this happens. To prevent this we can do:

import urllib2

import time

try:

page1 = urllib2.urlopen('http://www.identi.ca/warbo')

time.sleep(60)

page2 = urllib2.urlopen('http://www.identi.ca/warbo')

rate = post_difference(page1, page2)

print str(rate)+" posts per minute"

except:

del page1

del page2

del rate

Now if we get any type of exception in the three lines following try: then execution will jump to the except: block, otherwise the except: block will just be skipped. Since having one page is useless without the other, and keeping such useless objects accessible prevents the garbage collector from freeing up the memory they take up, we use this exception block to simply delete the page1, page2 and rate objects. Unfortunately there's actually a problem with this code too! Since we delete page1, page2 and rate, and the exception might happen before those objects are defined (for example if an exception occurs whilst trying to download page1, then the download of page2 and calculation of rate will never occur), then we might be asking to delete things which don't exist, which causes an exception! The example I've chosen here is meant to be slightly pathological, since the two dangerous operations we're doing (downloading my Identi.ca timeline) are exactly the same apart from binding name and line number. This means we can't, for example, have one except: block to deal with network errors and another to deal with some other exception type, since they both have the same exception possibilities. There are various ways of doing this correctly (using multiple try:/except: blocks, using temporary booleans to store whether each bit succeeded or not, etc.), but none of them are as intuitive as the way shown above. Using worlds, however, makes things easy, since we can encapsulate all of the side-effects of our attempts in a child world and simply delete the world if we fail, ie. something like the following (although I've made up the syntax since it doesn't exist for Python ;):

import urllib2

import time

child_world = get_world().spawn()

use_world(child_world)

try:

page1 = urllib2.urlopen('http://www.identi.ca/warbo')

time.sleep(60)

page2 = urllib2.urlopen('http://www.identi.ca/warbo')

rate = post_difference(page1, page2)

print str(rate)+" posts per minute"

child_world.commit()

except:

del child_world

Here we know that every side-effect (including the definition of new objects) will be contained in child_world, so if we fail we can simply delete it. Of course, there's nothing to stop a language using worlds directly for its exception handling (say by destroying world after world until one is reached that handles the exception, rather than just destroying stack frames), but Python couldn't do this as it would break its behaviour and thus existing code.

Another suggestion for using worlds is for namespaces and module systems. In Python, code from other files is made accessible to a program by using a line like:

import xyz

Which makes the contents of the module xyz available to the program, so that you can run, say:

import xyz

xyz.some_function(a, b, xyz.something)

The xyz module has its own namespace, so that everything it contains is only accessible if you put xyz. before the name (and namespaces can be nested, so we could say xyz.abc.something.foo() ). It's similar to a Web site address but using full stops instead of slashes. This makes sure that whatever xyz contains, it won't mess up your program, since you can call something a and xyz can call something a, but they won't conflict in your program since your a is called a and xyz's a is called xyz.a. There is also namespace injection, which takes things from a module and puts them in the current namespace, for example:

from xyz import a, b, some_function

Now those three things we've imported will be available without the xyz. in front of them. However, this is acceptable since we've explicitly defined which bits of xyz we want, so it should be obvious to us if this will cause any conflicts without having to know what's in xyz. However, in Python there is a dangerous and frowned-upon wildcard for namespace injection, which looks like:

from xyz import *

This will make everything from xyz available in your program without having to put xyz. before it. Since this line doesn't specify any names, the only way we could know what this is going to do would be to manually read the code in xyz or do:

import xyz

dir(xyz)

But this would still only work for that particular version of xyz you're using. Other people might be using different versions, and future updates might change which names it uses internally. This is often called polluting the namespace, since you end up with crap that gets in the way.

By defining modules in their own worlds, we essentially get the advantage of namespaces (ie. worlds can be used as a namespace implementation), plus we can make and destroy namespaces at any time. For example:

import xyz

abc = xyz.some_function(12)

g = abc+2

switch_world(get_world().spawn_world())

import abc

abc.some_other_function(g)

destroy_world()

print str(abc)

The final line will display the value we called abc in the second line, regardless of what importing a module called abc did to mess up our namespace later on.

Functionally

In the world of functional programming, there is no need to encapsulate side-effects, since all purely functional programs are side-effect free (ie. if something is true somewhere, then it is true everywhere, like regular Maths notation). The concept of worlds here is slightly different, since worlds are passed around as arguments to functions rather than acting like a stack, but the idea of encapsulating state remains the same.

In a functional language a function, let's call it increment_answer, can be given another function as an argument. This is known as a higher-order function, and as far as the language is concerned, increment_answer is a perfectly valid function just waiting to act on something. To put some tangible code for this, we can say:

square(x) ::= x*x

increment(x) ::= x+1

increment_answer(f, x) ::= increment(f(x))

square_plus_one(x) ::= increment_answer(square, x)

Even though I've made up this syntax, I'm sure it is pretty straightforward. The interesting thing to note, however, is that at no point in the above is x ever defined. We can assume that * and + are defined somewhere in this made-up language, but x only acts as a placeholder; it can stand for anything and the definitions given above always be valid, no matter what the functions do. So far so good, and if you've used a language like Ruby or Python you probably know of higher order functions already. So let's spice things up a bit:

max(x, y) ::= x if x > y else y

allow_positive(x) ::= max(0, x)

This probably seems straightforward too: max will give the larger of its two arguments whilst allow_positive will return its argument if it's positive, or else zero. Here we've been implying numbers, however. So let's look at what happens if we give everything a type:

square(number x) ::= x*x

type(square) = number -> number

increment(number x) ::= x+1

type(increment) = number -> number

increment_answer(number -> number f, number x) ::= increment(f(x))

type(increment_answer) = number -> number -> number -> number

max(number x, number y) ::= x if x > y else y

type(max) = number -> number -> number

allow_positive(number x) ::= max(0, x)

type(allow_positive) = number -> number

The type notation I've used means that the left-hand-side is the input and the right-hand-side is the output, so that the type number -> number is a function that, when given a number, will return a number. Easy, yes? Well what about the type of increment_answer? It has two arguments, the first is a function which must accept a number (since we pass it x) and return a number (since increment takes a number), so the type of its first argument must be a function number -> number. Its second argument is just a number. Giving it both of these will return a number, so its type is number -> number -> number -> number. That may seem a little confusing (where does "left" end and "right" begin?), so to consider a slightly simpler, non-higher order example let's take a look at max.

There are two arrows in the type of max, and it's not completely clear that both of the left ones are the inputs x and y. Why have I made the confusing mistake of putting number -> number -> number instead of something like (number -> number) -> number? Well it's because of Currying. The type of max is number -> number -> number, with the left as input and the right as output, as I said earlier, but attempting to segregate arguments and returns, for example with brackets, is futile: thanks to Currying it's completely up to you what you consider to be the left and right! The obvious type from the function definition would be two numbers in to get one number out, but it's also valid to say that it takes a single number in and gives out a number -> number. But what the hell kind of return value is that? Well, if you look at the other types I've scattered around there, it should be obvious that number -> number is a function which takes a number and returns a number. So max(5) is a perfectly valid function call, and will return a function for us! So what does such a function do? In this case it will give the larger of its argument or 5, so we can say:

five_or_above ::= max(5)

type(five_or_above) = number -> number

five_or_above(12) = 12

five_or_above(3) = 5

type(10) = number

type(five_or_above(10)) = number

It basically acts like max but with the first argument 'filled in' with a 5. This actually allows us to use a simpler definition of our allow_positive function, since we can say:

allow_positive ::= max(0)

type(allow_positive) = number -> number

This will behave in exactly the same way as the previous definition.

What about the other way around? What happens if we give max an argument of number -> number (ie. a function from numbers to numbers)? Do we get the remaining, right-most number as a return? Not quite. It's perfectly valid to call max with a function, for example:

max(number x, number y) ::= x if x > y else y

type(max) = number -> number -> number

increment(number x) ::= x+1

type(increment) = number -> number

result ::= max(increment)

type(result) = number -> number

Hmm, we seem to have received a function back rather than a number. Why's that? Well it's because the function we gave to max, namely increment (for lack of a better example), requires an argument in order to do anything. Calling max of increment only makes sense when we give increment something to add one to! Thus max(increment) gives us a function which can be thought of as follows:

max(increment) = x if x > x+1 else x+1

type(max(increment)) = number -> number

In other words it takes a number in for the first argument of max, namely x, then sends that to increment to find out what to use for y (which will be x+1, since that's what increment returns), then runs max of x and y, ie. of x and x+1 (which incidentally will always behave like increment because I used silly examples, as long as > is defined as we would expect of course ;) ). I know that's quite long-winded, but re-read it a few times and you'll soon pick it up!

So what of the beast increment_answer with its type number -> number -> number -> number? Well it's the same thing again: we can give it a single number to get a function number -> number -> number (the same type as max) which essentially has the first argument 'already filled in'. We can give it two numbers to get a function number -> number which behaves as if the first two arguments are 'already filled in', or we could give it a function number -> number which will 'fill in' the first argument as required and fill in the second argument with that function applied to the first. We can keep doing this, replacing values with functions and functions with values, making for a program that's applicable to a very general set of problems. As you might be thinking, Currying is a very powerful technique indeed! It's one of the reasons people get so enthused about functional programming and languages like Haskell.

OK, so that's a little functional programming basics, let's move on to more interesting things than numbers! Our programs can contain functions that do anything we want, and our entire program itself is just a function as well. So what type do programs have? void -> void. This is a rather rubbish type, which basically means they take in nothing and return nothing. What makes this especially worse is that a large number of programs spend a lot of time initialising themselves to start with, and backing up their calculations before they close.

The functional idea of worlds is to make programs have the type world -> world, which gives them an input which they can get started straight away with, rather than having to faff around with loading and parsing and such (which is made all the more difficult due to the stateless nature of the program, which is somehow accomplished by monads even though I still can't get my head around what they do), and at the end they can dump their computations straight out to the operating system for storage, rather than having to mess with IO, and all of the complexities, edge cases and breakages that entails.

Thus in this system a program to update a clock on the desktop can be as simple as:

update_clock(world w) ::= new_world_from_existing(w, "clock", w.clock+1)

This is my own made-up syntax, but the the point is that it takes in a world, whatever that happens to be, and outputs a new world which is the same as the input except that its "clock" is '1 higher'. The point is that this is an entirely self-contained program (given the function new_world_from_existing, which I only abstracted away here since I can't be arsed to specify a structure for these worlds, since it's arbitrary); the OS gives this program a world when it starts and saves the new world it passes back when it's done.

As far as the OS is concerned the worlds are just black boxes, it doesn't need to know or care what they are. When an event occurs, an OS daemon will trigger the associated programs (imagine something like Unix's cron), and these can of course trigger actions themselves (for example a clock tick can trigger a time update program, an updated time can trigger a program to render the new clock face image and having a new clock face image can trigger a screen refresh). Essentially it allows unrolling of main loops into one OS-level mechanism, and allows the programs to be short, simple, cooperative and to-the-point.

A difference between the stateful and functional world systems is that in the former, computation happens inside worlds, which capture all of the side-effects to prevent them wreaking havoc. In the latter, computation happens to worlds and new worlds are generated based on the effects of the computation; worlds are immutable and unchanging, but you can make new ones with whatever properties you like (worlds never get "replaced", although it is valid for the operating system to pass a world to a program and store the new world that is returned in the same place as the old world, as long as no other programs use the old world, but this isn't so much mutability or replacement as much as it is garbage collection; the old world is not needed any more so it is deleted, whilst some space is required for the new world which may as well be the space previously occupied by the old world).

However, the observant amongst you will have spotted by now where I'm going with this. If you've not spotted it yet then it's that these two concepts of Worlds are the same! The advantage to using worlds in an imperative, stateful language is that side-effects can be tamed, kept isolated and the APIs kept pure and side-effect free to allow more scalability and predictability. With everything wrapped up in world sandboxes, assertions about behaviour can be made which only rely upon the individual pieces of code and the little world in which they live. In other words, this stateful code behaves like pure functions which are Curried with the worlds they return!

In a functional language, worlds allow state to be passed around, so that the same small, simple functions can be used for a variety of behaviours based on the world that they take as input. In other words these pure functions behave like imperative code, just with the state being passed around explicitly!

So what does this mean? Well firstly, if we can make pure, side-effect-free imperative code then we get the awesomeness of functional code in our non-functional languages. This, admittedly, would only occur in a coarse-grained way, since there's no guarantee that anything below the API level behaves purely, but it's enough to let us build non-leaky abstractions in the way that functional languages get for free. If we have correct abstractions then we can treat them as black boxes and do all sorts of cool analysis on them, like automatic translation, optimisation, compilation, program synthesis, inter-language calls, etc.

Some of this is going on in the Viewpoints Research Institute's STEPS project, with their kernel abstractions, essentially treating function calls like virtual machines, implemented as on-the-fly domain-specific language compilation in separate worlds, which makes each layer in the call stack become more sandboxed, more secure, more abstract, simpler and more specialised at its job. It's an interesting project with some cool papers floating around (although I wish they'd release their publications more often ;) )

Anyhoo, I thought I'd write a blog entry to test out KDE's Blogilo program, since Google's fail Web app POS doesn't like me, and I'm getting rather carried away with it :) Hope this works!

Web Apps are shit

2010-01-26T17:48:00.001Z

They really are

Web Apps are shit

2010-01-26T17:47:00.001Z

OMG they really are.

Diet Python and some ranting

2010-01-26T15:37:00.009Z

Long time no post (in fact, I haven't posted at all since starting my fourth year at Sheffield Uni!). I keep writing big ranty things, meaning to post them, but haven't got around to it yet. Ah well, maybe soon (exams at the moment though :( )

As part of my biannual exam revision procrastination I've started to rejig my Diet Python language. The idea behind Diet Python is pretty simple: take all of the syntactic sugar out of Python. Thus Diet Python is just a subset of Python, which is just as powerful as the complete language. Diet Python isn't meant to be programmed in, however; it exists to simplify Python programs so that they can be handled more easily by automated tools. For example, in Python the following two lines are equivalent:

a + b

a.__add__(b)

So the Diet Python equivalent is this:

a.__add__(b)

It is thus completely compatible with Python, but there is no need to bother with "+" (or the associated nodes in the Abstract Syntax Tree). The same applies to other Python syntax such as:

my_list[index]

my_list.__getitem__(index)

In Diet Python we can get rid of the "[]" subscription notation, without losing the ability to grab elements from lists (or any other type of object which implements the "[]" syntax, which is done via the __getitem__ method). Thus if we have a Python implementation (CPython, Jython, PyPy, IronPython, etc.) then it is also a Diet Python implementation (plus some extra stuff that Diet Python won't use), but more interestingly if we implement Diet Python then we've actually implemented the whole of Python in terms of features, just not the syntax. This can be overcome easily by using a translator to turn Python's nice, sugary syntax into Diet Python's awkward, canonical syntax, which is exactly what I've done.

Diet Python originally started as a simple test case for my Python pretty printer (or "decompiler"), which turns a Python Abstract Syntax Tree, produced by Python 2.x's built-in "compiler" module, into valid Python code which implements the AST's functionality (ie. compile some Python into an AST, stick that into the decompiler to get some Python code, then compile that to an AST and the two ASTs should be the same (as long as every transformation is reversible, is reversed, doesn't lose information and is done naively, that is ;) ).

The decompiler itself was an experiment to get used to the PyMeta pattern matching framework (which I've since used in a University project to test my code), and since PyMeta, as an implementation of Alessandro Warth's OMeta, should be nicely extensible via subclassing, I wanted both an experiment in PyMeta and an experiment in extending my experiment in PyMeta to really get to grips with it.

Unfortunately subclassing in PyMeta has proven difficult, which might be a bug in the implementation (I'll have to check up on that). Making a pattern matcher, for example to decompile Python ASTs, in PyMeta allows anyone to make a similar pattern matcher based on it quite easily through Python's object system. For example if you want to get rid of every "print" statement in some code, you take the decompiler (which is a Python class object), then you write down the grammar rules which differ from the original (in this example every Print and Printnl node should be translated into '' (ie. an empty string, and thus no code)), then you tell the decompiler to make a grammar out of your rules, and it will give you a new Python class which implements a pattern matcher using the decompiler's rules + your new ones (where the new ones override the decompiler's ones in case of conflicts).

This is all well and good, however the REALLY cool thing about OMeta and thus PyMeta is that their operation, ie. turning written rules into parsers for those rules, is written in (O/Py)Meta (which is why they are Meta). Thus it is possible to take OMeta and, by writing some OMeta rules, change the way that OMeta works, we could call it OMeta'. Now OMeta' can be changed by writing rules in either OMeta or OMeta', to produce another pattern matcher which we can call OMeta'', and so on. This, however, doesn't seem to work in PyMeta, despite trying multiple ways and looking through the source code (which is written in OMeta) over and over again. Sad face :(

Ah well, this limitation has resulted in a bit of hackiness when it comes to the Python decompiler and Diet Python translators. Firstly, PyMeta has no syntax for comments, which is annoying. It should be simple to subclass PyMeta to make a PyMeta' which supports comments, but since I can't subclass PyMeta without losing its bootstrapping, I'm stuck with using Python to remove comments before passing the rules to PyMeta. The second hack is that doing tree operations requires recursion. Whilst PyMeta has recursion built in, it's not available in the most suitable way for my experiments. Once again, subclassing PyMeta should solve this, but I can't, so I've had to monkey-patch the AST nodes (ie. pollute their namespaces with functions and attributes) then call these from inside the grammar. What this results in is every node instantiating their own pattern matcher on themselves, which happens recursively down the trees.

Unfortunately the "type" system of Python 2.x rears its ugly head here, where historical implementation decisions have left Python with 2 object hierarchies (which, I believe, was one of the main motivations for making Python 3). The object system which is the most familiar, since it's used in Python code, has the class "object" as the eventual ancestor of everything, such that every class is a subclass of object, or a subclass of a subclass of object, etc. This would be a "pure" object system, except that "everything" isn't quite everything. Many core pieces of Python, for example text strings, are not descendents of "object" at all, and are not subclasses of anything, or indeed classes. Instead they are "types", where each "type" seems to be isolated from everything else, written by hand in C, utterly inextensible, cannot be subclassed, and basically brings to mind those nightmarish things that Java programmers call "basic types" (*shudders*, *washes mouth out with soap*). Since they are in their own little statically-compiled-C world there is no way to monkey patch them with the required functions and attributes, so that every string, number, None and probably more require custom code in the pattern matchers. Shit. This also brings with it that great friend of everybody who loves to waste time known as combinatorial explosion. In other words, instead of doing a substitution like:

apply_recursively ::= <anything>:a => a.recurse()

("apply_recursively" is defined as taking anything and calling it "a", then outputting the value of running "a.recurse()")

We have to do something like:

apply_recursively ::= <anything>:a ?(not issubclass(a.__class__, Node)) => a

| <anything>:a => a.recurse()

("apply_recursively" is defined as taking anything and calling it "a", as long as it is not descended from "Node", and outputting it's value, or else taking anything and calling it "a" and outputting the value of "a.recurse()")

And of course, since this is our friend combinatorial explosion, we cannot write:

apply_recursively ::=<anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 => a1.recurse() + a2.recurse() + a3.recurse() + a4.recurse()

Oh no, if there's the chance that any of those might be "types" (*winces*) then we are forced to write instead:

apply_recursively ::= <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a1__class__, Node) or issubclass(a2__class__, Node) or issubclass(a3__class__, Node) or issubclass(a4__class__, Node))) => a1 + a2 + a3 + a4

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a1.__class__, Node) or issubclass(a2.__class__, Node) or issubclass(a3.__class__, Node)) and issubclass(a4.__class__, Node)) => a1 + a2 + a3 + a4.recurse()

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a1.__class__, Node) or issubclass(a2.__class__, Node) or issubclass(a4.__class__, Node)) and issubclass(a3.__class__, Node)) => a1 + a2 + a3.recurse() + a4

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a1.__class__, Node) or issubclass(a2.__class__, Node)) and issubclass(a3.__class__, Node) and issubclass(a4.__class__, Node)) => a1 + a2 + a3.recurse() + a4.recurse()

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a1.__class__, Node) or issubclass(a4.__class__, Node) or issubclass(a3.__class__, Node)) and issubclass(a2.__class__, Node)) => a1 + a2.recurse() + a3 + a4

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a1.__class__, Node) or issubclass(a3.__class__, Node)) and issubclass(a2.__class__, Node) and issubclass(a4.__class__, Node)) => a1 + a2.recurse() + a3 + a4.recurse()

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a1.__class__, Node) or issubclass(a4.__class__, Node)) and issubclass(a3.__class__, Node) and issubclass(a2.__class__, Node)) => a1 + a2.recurse() + a3.recurse() + a4

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a1.__class__, Node)) and issubclass(a2.__class__, Node) and issubclass(a3.__class__, Node) and issubclass(a4.__class__, Node)) => a1 + a2.recurse() + a3.recurse() + a4.recurse()

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a4.__class__, Node) or issubclass(a2.__class__, Node) or issubclass(a3.__class__, Node)) and issubclass(a1.__class__, Node)) => a1.recurse() + a2 + a3 + a4

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a3.__class__, Node) or issubclass(a2.__class__, Node)) and issubclass(a1.__class__, Node) and issubclass(a4.__class__, Node)) => a1.recurse() + a2 + a3 + a4.recurse()

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a4.__class__, Node) or issubclass(a2.__class__, Node)) and issubclass(a3.__class__, Node) and issubclass(a1.__class__, Node)) => a1.recurse() + a2 + a3.recurse() + a4

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a2.__class__, Node)) and issubclass(a1.__class__, Node) and issubclass(a3.__class__, Node) and issubclass(a4.__class__, Node)) => a1.recurse() + a2 + a3.recurse() + a4.recurse()

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(issubclass(a1.__class__, Node) and issubclass(a2.__class__, Node) and not (issubclass(a3.__class__, Node) or issubclass(a4.__class__, Node))) => a1.recurse() + a2.recurse() + a3 + a4

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(not (issubclass(a3.__class__, Node)) and issubclass(a2.__class__, Node) and issubclass(a1.__class__, Node) and issubclass(a4.__class__, Node)) => a1.recurse() + a2.recurse() + a3 + a4.recurse()

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(issubclass(a1.__class__, Node) and issubclass(a2.__class__, Node) and issubclass(a3.__class__, Node) and not (issubclass(a4.__class__, Node))) => a1.recurse() + a2.recurse() + a3.recurse() + a4

| <anything>:a1 <anything>:a2 <anything>:a3 <anything>:a4 ?(issubclass(a1.__class__, Node) or issubclass(a2.__class__, Node) or issubclass(a3.__class__, Node) or issubclass(a4.__class__, Node)) => a1.recurse() + a2.recurse() + a3.recurse() + a4.recurse()

Which, even if you've never programmed before, should look like a bloody stupid hoop to have to jump through.

So, there's a little insight into how even high-level, meta, abstract things can be hindered by ancient, low-level implementation artifacts, and possibly an insight into the angry posts I was making to Indenti.ca whilst writing this stuff six months ago ;)

My code, as always, is on Gitorious, and now that I've turned the Diet Python translator into a tree transform it should be much easier to strip away more and more layers of unnecessary Python (and thus pave the way for some interesting programming experiments!)

mv/((1-(v/c)^2)^(1/2)) or, in non-relativistic terms, momentum

2010-01-21T17:56:00.005Z

I know this will probably start a flame war if widely read (which it probably won't be, since this is just a braindump page) but I want to say it anyway: I think the Gnome desktop is in a bit of a pickle, and the problem I think it is facing is that which many people have to deal with when programming, and that is stopping too early.

I'll talk you through one of my first programs as an example; it was for an assignment in Object Oriented Design in Java, which was to make a very simple pinball game. There was some code given as a starting point, but it was terrible (it was essentially a C program shoehorned into compiling as Java, thus it didn't follow an Object Oriented Design and, whilst syntactically correct, wasn't really written in Java at all), though most (probably all) used it as a starting point. Being very new to programming, especially in such a verbose and overly-strict language as Java, I couldn't really follow the given code: I could see the API and get it to do the things I told it, but I couldn't understand all of what it was doing, and amongst those bits which I did understand I saw some obvious hacks. As a Physicist and perfectionist-who-never-ends-up-finishing-anything I didn't want to use incorrect code, and especially didn't want to rely on someone else's proof without understanding it (Curry-Howard and all that). Thus I did the first thing that anyone who's ever done any Maths would do and tried to work it out myself and see if my solution matched. The result was a program of which I was quite proud: rather than being a hack to shift graphics around the screen (as the provided code had been), I'd started from what I knew and had made a basic Physics simulation with graphical output (originally based on AWT then switched to Swing). The code was spread out amongst many classes, there were no hacks in the object system (although there were a few in the main method to set things up, but that was just for testing), it was very intuitive, was the largest programming project I'd tackled thus far (although now I'd consider it to be the size of a moderate experiment) and I had it running pretty early into the assignment. It now needed some recognisable objects from a pinball table (like flippers) and more game-like control. However, rather than writing these I just played around inside it. Constantly. It was fun to throw things around, generate hundreds of objects and watch them bounce around off each other but most of all it was fun to know that I'd made it. In the end it got marked as 70%, since all my playing stopped me from actually making any kind of pinball game (I talked through the code, but when running it just presented a bunch of balls bouncing off "pins" which were just fixed balls).

Now, what's this got to do with Gnome? Well, Gnome works really well. It's unobtrusive, stable, intuitive and does "what people want". Reading through Planet Gnome gives some design bugs (the keyring dialogue asking for a password without indicating what is after the keyring or why, allowing a trojan to ask for the keyring without the user having any indication that they're giving access to malware and not NetworkManager or Evolution or Empathy or whatever), a few posts on Zeitgeist, translations, some compatibility improvements and a call for more contributions to the 2.29 features list. Other than that it's musings about transport, architecture, low-level distro tweaking (nothing to do with Gnome, things like boot performance). It seems that there are three levels of Gnome developer (and I mean developer here as anybody involved in improving Gnome):

1) The it does "what I want" developers, who may maintain things but make very gradual changes (like layout changes, adding translations, etc.). To these, Gnome is an excellent platform which chugs away unobtrusively for them in the background and allows them to get on with life; their itches are the "papercut" annoyances that are small, but happen a lot (something like an info dialogue which doesn't have a "don't show this again" option).

2) The inspired developers who's itches are to push the platform in new directions. They work hard to do this, but as one-person-armies they can only do well on one thing at a time (for example UPnP support).

3) The ignored developers who's itches to make sweeping changes never really get scratched due to the inertia of userbase familiarity and developer apathy due to the adequate nature of the platform as-is. These include the Gnome mobile efforts, the online integration attempts and so on. For those wanting an example of inertia, take Nautilus's spatial mode. This is rejected in favour of the old one-window browser mode by many users, simply because it was there first.

Now, I am not trying to crap on the project, far from it I'm offering my observations of the development slowdown over the past 6 or 7 years I've been using Gnome and following its developers. I'm not in any way trying to undermine the efforts of those three groups I've mentioned, I am trying to point out the obstacles that each face and how they could be overcome.

Many of those developers in groups 2 and 3 could benefit from Gnome 3 stirring things up a bit to break the stagnation. The reason I put quotes around does "what I/people want" is because, in my opinion, there's no such thing. Recall Henry Ford's famous remark that if he'd given people what they wanted then he would've given them a faster horse. Nobody knows that they want something unless they try it for a while and integrate it into how they go about things. I'm frequently met with the does "what I want" argument with regards to Windows. If the current situation in Gnome is unfortunate then that lumbering beast known as Windows XP is the armageddon! Admittedly, Windows Vista is awful: those few of its features which are any good don't make up for the cost in performance, and many of the features deemed "good" by others aren't features they're just attempts at shifting responsibility for brokenness onto users (those damned popups!). However, since there was an explosion in computer ownership during the lifetime of XP (2001-2007), for many people XP is a fundamental fact about what a computer is, in the same way that a toaster is not a toaster without a spinny dial for toasting time. Of course there are those who lived through Windows 95, 98, ME (lol), 2000 and XP, and who saw Vista as the next rung on the steady upgrade ladder it was intended to be, but viewed it as not worth the wait compared to the more timely releases of the past, and no doubt the growing use of computers made its drawbacks all the more annoying.

The appearance of KDE 4 stirred things up in KDE land, but there was such a wholesale developer switch due to the underlying library improvements that the users have been dragged kicking and screaming into a more flexible system, which is a must for supporting both the type 1 people and the types 2 and 3. Plus any annoyance generated has either been blogs-full-of-ads whoring or else has been reacted to by the KDE developers and sorted, or at least steps have been taken so that they become sorted some time in the future ;)

The alternative to the kicking and screaming approach is to fork. Forking is usually bad news, but unfortunately there seem to be quite a few projects aiming to address deficiencies in Gnome, without actually fixing what they perceive to be wrong with Gnome. For example XFCE tries to use fewer resources, whilst LXDE tries to use even fewer resources. There are loads of custom file managers, panels, window managers, widget systems etc. which each do an OK job, but don't play nicely with each other and so don't quite combine to become teh awesomes as they rightfully should.

Doing things the "right" way, or leaving many opportunities open for others to reject what you've made in favour of something else, is a much harder thing to accomplish than just shipping a vertical, one-size-doesn't-fit-any stack. Lots of standards are supported in Gnome, but a lot of work is happening outside the project and being shoehorned into the defaults later because it happens to use Glib.

I hope the introspection initiative gets the ball rolling for Gnome again, since it's lowering the barrier to entry and allowing customisation through abstractions and introspection which can guide enthusiastic minds into tackling the itches they face without putting them off by archaic languages like C.

A Decent Compressed Filesystem At Last?

2009-08-11T23:14:00.002+01:00

I have a 2.4GHz CPU, a 250GB hard drive and I want to store 29GB of zipped music I just downloaded. The music is in a variety of ProTracker formats, so what's the best way to store it?

I know for a fact that tracker songs are very easy to compress, since the format originates on computer systems like the Amiga where any compression more sophisticated than Run Length Encoding takes away valuable clock cycles which are often needed elsewhere. Such uncompressed, or crudely compressed, data is ripe for extra compression (hence why it is transported in a zip archive).

Actually playing this music is now nontrivial though, since whilst all of my music players support protracker, not all of them support reading them from zip files. The obvious thing to do is decompress them, but since trackers are highly compressible, this means that the 29GB archive will certainly become even more vast when decompressed, and that's just a waste of storage space. The solution is to use a compressed filesystem.

For those who are stuck on shit operating systems, I'll give you a little insight into how your computer works. Let's say we're running Microsoft Windows, and we insert a CD into our CDROM drive. In "My Computer" we may see our CDROM is called "D", and if we double click on it we see the things stored on it. However, we then go back to My Computer and right click on D, then tell it to eject. We take out the CD and close the drive. Now we tell it to eject again, and the drive opens. So, what is "D"? It's our CD, since we saw the files on it, but it's also the drive, since we can tell it to do things when our CD is nowhere in sight. Which is it really? Well, that depends completely upon what you want to do, since Windows is a very poor system indeed.

Let's imagine a similar thing on a UNIX system like Debian. Our CDROM will be something like /dev/hda. We can send it commands, for example "eject /dev/hda" (or do the same thing in whichever graphical environment you happen to use). Can we access the files on a disc through /dev/hda? No. What we can do, however, is take the data given to use by the drive, and reconstruct it somewhere. This is what we mean by mounting the filesystem. The filesystem is the particular way the ones and zeroes represent our files and folders (CDs use the standard ISO9660, which is often extended with certain proprietary formats from Microsoft to allow longer filenames. Ironic, considering that the original format only had short 8.3 filenames to make sure it would work on Microsoft's POS crapware), whilst mounting it means making it available to peruse. Here we can choose where we want to see things, so we can run a command like "mount /dev/hda /our_cd". Now if we go to the folder /our_cd the previous contents will be hidden (until the CD is unmounted) and the contents of the disk is accessible. /our_cd is a different file to /dev/hda. The same is true of hard drives.

In fact, filesystems can be anything. The FUSE (Filesystems in USErspace) driver allows regular programs to be written which can be accessed like filesystems. This is how the Wikipedia filesystem works (mount it somewhere and that folder becomes filled with files for each article), how the GMail filesystem works (data is stored online as a series of emails in a GMail account, which can be retrieved from anywhere and are automatically converted back to their original state), and many others. There are several FUSE filesystems which transparently compress and decompress their contents, ie. everything copied into the filesystem is sent to a compression program and saved somewhere, and everything read from the filesystem is sent through a decompression program before it reaches the destination. Thus any program, as long as it can load files, can load compressed files, and any program, as long as it can save files, can save compressed files.

Seems cool, but until recently the only ones I'd tested were pretty dire, most noticably CompFUSEd. INCREDIBLY slow and memory hungry, it was not worth using, and that was only when a few MB were put into it.

However, FuseCompress has recently been added to Debian, and I'm trying it out for these tracker modules. Whilst populating the filesystem is taking a while (I'm having to decompress all 122 thousand songs (since that's how we want them to be read and therefore written), then move them into the filesystem where they're recompressed (although using LZO this time, which is damned fast). All I can say is thank Guido for Python, since it makes automating such things a breeze :)

I thought I'd finish with a little introduction to compression, and what it actually is. Compression is completely based on Claude Shannon's Information Theory (also the basis of using switches to represent Boolean logic, ie. allowing a physical way of building Alan Turing's theoretical "computers"). Information, measured in bits, is irreducible, you can't throw away any bits without losing some information (compression which does this is called "lossy" compression, for example the Vorbis audio codec. However, the algorithms are crafted in such a way that information is only thrown away when it is imperceptible to us, in the case of Vorbis we can't hear the difference), but the key thing to know is that each bit of information is not necessarily mapped one-to-one with each bit of whatever material is being used to store it (eg. magnetic domains on a hard drive). A bit of information is required to describe a situation where there is a 50/50 chance of the next bit being 0 or 1, but this is only true for random sequences, or those which appear random. A sequence like "AAAAAAAAAAAAAAAAAAAA" is not random (each bit isn't independent of the previous), and thus does not require all of the 160 bits that are being used to describe it. Information theory gives us a lower limit, saying how many bits are REQUIRED to store the given information, so we want our algorithms to approach this limit as much as possible.

A really simple type of compression is Run Length Encoding. This looks for repetition and replaces it with multiplication. For example, the sequence "ABCBAAAAAAAAABBCCCCCCCCDBDDDDB" could be compressed to "ABCB9ABB8CDB4DB". Our algorithm here is simply "if you find more than 2 of the same letter in a group then replace that group with its size followed by the letter", so a stream of "AAAAAAAAA" becomes "9A". To decompress this we use the algorithm "If you find a number, put that many of the next letter".

There is a slightly more general form of this, where instead of grouping similar things, we use a pointer. The pointer is a number which means "I am the same as whatever is this far behind me". In this way "AAAAAAAAA" can become "A12345678", where each number is telling us to get the next value from this far back (they all point back to the first A), however pointers can also point to pointers, so we could just as easily put "A11111111", since each of those "1"s becomes an "A", so it's perfectly valid for the next one along to point to it. This is easily compressible with the runlength encoding seen above (which is just a subset of this form of compression), but is more powerful. For example "ABABABABABABABABABABABA" cannot be compressed with runlength encoding, but using pointers we can compress it to "AB222222222222222222222". Now this is easily compressible. This works for any size of pattern, although since it is a search operation it can get quite slow for large search spaces, so files are usually split into more manageable chunks first.

A final form of compression I'd like to mention involves binary trees. Let's say we made a survey of the occurances of every letter in a file. We could say, for example, that "e" was the most common, followed by "a", followed by "s" and so on. Now we can compress these from their usual 8 bits to a much more compact form. First we define a binary tree, that is a tree where every non-leaf node (branch junction) has a left and a right branch. If we meet a "0" we will go down the left branch and if we meet a "1" we will go down the right branch. Our tree will begin with two branches, and we can stick "e" at the end of the right branch. On the left branch we put another node with two children, on the right we put "a" and on the left we put another node with two children. On the right of this we put "s" and on the left another node with two children, and so on. Now we can replace each letter by the path we must take in our tree to reach it (with our tree we know that "1" marks the end of a letter). Every time we find an "e" we simply put a "1", since that's how we get to "e" from the top of the tree (1 means go right) This saves 7/8 of the space every time. Every time we find an "a" we replace it with "01", which saves us 3/4 of the space, an "s" with "001", and so on. By constructing optimised trees (which is once again a search operation) we can get really good compression ratios.

Anyway, rant over since my script has finished moving all of the "A"s :D

The Ugliest Hack I've Written So Far

2009-08-04T19:28:00.006+01:00

raise :i ::= :a ?(a.__class__ == Raise) => 'raise '+', '.join([t[0] for t in [[e] for n,e in enumerate([a.expr3,a.expr2,a.expr1]) if e is not None or any([a.expr1,a.expr2,a.expr3][-(n+1):])] if (t[0] is not None and t.__setitem__(0,t[0].rec(i))) or (t[0] is None and t.__setitem__(0, 'None')) or True][::-1])

This is a 1-line PyMeta rule which means the following:

Define a rule named "raise" with an amount of indentation "i", which applies to anything, which we'll call "a", as long as "a" is a type of 'Raise'. Upon finding such a thing we should output a string 'raise ' followed by the first item of every list in the set of singleton lists of "a"'s attributes 'expr3', 'expr2' and 'expr1' when reversed which is either not equal to "None" or else comes after a non-None attribute, if the element of these lists is not None and swapping the first element for its contents recursively at the same indentation level, or if it is None then replacing it with the string "None".

If I were writing this normally it would be something much cleaner like:

def raise(i, a):
  if a.__class__ == Raise:
    to_return = 'raise '
    attribs = [a.expr3, a.expr2, a.expr1]
    to_keep = []
    not_end = False
    for att in attribs:
      if att is None or not_end:
        to_keep.append(att)
      elif (not att is None) and (not not_end):
        to_keep.append(att)
        not_end = True
    to_keep.reverse()
    to_return = to_return+', '.join(to_keep)
    return to_return

but the default PyMeta grammar only allows a single line of Python in the output. Whilst the point of OMeta is that I can subclass and rewrite it to work in whatever way I want, I can't get the hang of subclassing grammars yet, and hence this mind-bending, yet at least partially elegant, functional approach.

Wish I had some free time

2009-05-26T19:27:00.002+01:00

Just trying to publish stuff that's been in draft form for months, whether it's finished or not :P

Lectures are finally over for this semester (mine went on a week longer than everyone else's it seems) and my exams start next week (I only have 3, as opposed to the usual 6!). However, I've got projects overdue and some slipping off the radar altogether because of my stubborn insistence on doing things correctly. I didn't get very far at all with my second Numerical and Computational Physics assignment, since I can't get my head around the Runge Kutta method of approximating functions based on their derivative and some initial conditions. I did manage to use them during an assessment/exam for the same module (after attempting to use Microsoft Word and Excel, then giving up at the hopeless confusion they caused me and instead downloading and installing Gnumeric and Abiword which, whilst allowing me to actually get some bloody work done without flashing any fancy-yet-utterly-fucking-useless-because-I-don't-know-what-it-does bling at me, still took up about half an hour of my exam), but a spreadsheet is a horrible way to do any kind of programming, so my disgust at entering hard-coded functions was drowned out by the limited use of the actual tool.

Experiment Dump

2009-04-27T12:44:00.002+01:00

Over the past few years I've accrued a lot of failed, successful or otherwise abandoned experimental programs in my /home/chris/Files/Documents/Play/Programming directory (yes, I am somewhat OCD about file organisation). Since they might be interesting to some people, as they were obviously so interesting to me that I wanted to write them, I've started to upload them to FreeWebs. Here's a list, along with a brief description.

MaxInt.java - This is a simple test showing one of the reasons I hate Java. Java stores integer numbers in a fixed amount of space, 32 bits. 32 bits can be in one of 2^32 unique combinations, which Java divides down the middle. The middle combination, 10000000000000000000000000000000, is taken to be zero. The combination above, 10000000000000000000000000000001 represents 1, and so on up to 11111111111111111111111111111111, which is 2147483647. In the other direction, the combination below (01111111111111111111111111111111) represents -1, 01111111111111111111111111111110 represents -2 and so on until 00000000000000000000000000000000, which is -2147483648. The problem with this can be shown if you try to add 1 on to the biggest number, which gives 100000000000000000000000000000000, but since Java only allows numbers to be 32 bits long it only bothers looking at the last 32 bits, so it thinks that 2147483647 + 1 = -2147483648, which in my opinion is a fail. To add insult to injury, Java doesn't allow applications to compile unless they handle every possible exception they come into contact with, including those that will never be thrown or which aren't even used, yet Java is perfectly happy to let its own failures pass without comment, causing debug headaches.

To run this just compile it (for example with "javac MaxInt.java"), then run it (for example with "java MaxInt").

JavaGnucleon.tar.bz2 - This is a simple board game along the lines of Atoms on the Amiga. Players take it in turns to click on squares to "add an atom to them". Anyone can click on an empty square (indicated by a 0), but once a square has an atom in then it is owned by that player (and changes colour) and only that player can click on it from then on. Once a square gets as many atoms in it as it has nearest neighbours (not including diagonals) then it explodes, sending one atom to each neighbour and claiming them for the player. Chain reactions can occur if a square explodes and sends an atom to a neighbouring square, giving it enough to explode, and so on.

package-installer.tar.bz2 - This is a non-functional Java GUI for a package management tool I was working on a couple of years ago. It's similar to APTonCD, but as far as I know predates it a little.

AppPrefs.tar.bz2 - This is a non-functional Python/GTK GUI for choosing GNOME's default applications. It shows how the default browser could be chosen, giving a textual description of each one's unique features (ie. what makes it different) along with a screenshot. The idea is that users don't need to know or remember the names of the applications, they can read the description and look a the screenshot to see if it's the one they were looking for (these days Synaptic can show screenshots, which is awesome :D ). Also, I wanted to get rid of the IMHO broken idea of associating applications with filenames, such as files ending in ".mp3" and so on. File types should be determined using magic or libmagic, and users shouldn't have to care about the implementation. They should just be able to say "Music" or "Spreadsheet".

Bouncy.py - A very simple Python script which makes a square bounce around the screen based on some very dodgy Physics.

Some Nice Things

2009-04-27T01:31:00.004+01:00

I've not posted for a while, due to a mixture of an increasing workload, the ability to let off a constant barrage of my thoughts to Identi.ca rather than build them up into a blog post, and my constant disdain for Web-based apps.

So what do I want to blog about? Nothing particularly structured, just some stuff that I find interesting. Keep in mind though, that my definition of interesting includes the fact that 12cm optical discs have increased their storage capacity by 2 orders of magnitude in the 27 years from the CD to the BluRay, whilst in the same time frame the capacity of 3 1/2" hard drives has gone up 12 orders of magnitude. (I'm writing an essay on Optical Data Storage for a Physics module :) )

For those of you who may remember Deluxe Paint on AGA capable Amigas I can heartily recommend that you check out Grafx2, which seems to work on pretty much every OS and has recently been added to Debian, so you can install it by ticking "grafx2" in any package manager, it will be downloaded and installed along with everything it depends on :) Doesn't seem to do animation yet, as far as I can tell, which is a shame.

Also recently added to Debian is Closed World Model, cwm. This is pretty special, since it takes cutting edge computer knowledge representation as used by the Semantic Web, and makes it accessible via a tool similar to UNIX's (and of course GNU's) classic sed tool. For example, you can use a command like "cwm --rdf inputfile1.rdf inputfile2.rdf --n3 inputfile3.n --rdf --think --pipe > output.rdf" to take at all of the knowledge from the RDF files inputfile1.rdf, inputfile2.rdf and inputfile3.n (in RDF-XML and Notation3 formats), comparing the knowledge they contain, and dumping all of the new knowledge it can infer into the RDF-XML file output.rdf. For example, inputfile1.rdf could contain statements that Chris Warburton is a student, Chris Warburton has a website http://www.freewebs.com/chriswarbo and that Chris Warburton has a brother David Warburton. inputfile2.rdf could say that Brothers are related and that Brothers share a Mother. inputfile3.n could say that David Warburton has a blog at http://fun-chips.blogspot.com and David Warburton has a mother Cheryl Warburton. cwd would then combine these and the output file would contain deductions such as David Warburton is related to a student, http://www.freewebs.com/chriswarbo is run by a student and Chris Warburton has a mother Cheryl Warburton.

This is pretty cool, since it commoditises the previously tricky area of RDF access, allowing it to be scripted, for example in the backend of Web sites, in the same way that Imagemagick has done to images (eg. for thumbnailing).

Pretty cool. Anyway, it's getting late so I should get some sleep now.

I'm going to post some of my programming experiments soon, so look out for them :)

BBC News comments are broken

2009-03-24T20:15:00.001Z

Tried to post on this http://news.bbc.co.uk/2/hi/uk_news/7955205.stm but it failed :( Didn't want to lose it though.

The harrowing trend to notice amongst government statements on these issues of technology, privacy and civil liberties is the focus on the meaningless technology arguments rather than the important freedom related ones.

To me the idea of "a profiling tool which examines a child's behaviour and social background to identify potential child offenders" makes a sickening mockery of the notions of innocent until proven guilty, freedom of speech and expression and equality. I don't care if it's encrypted or 'secure', or how much such a thing would cost, it simply shouldn't exist in the first place!

The same sidestepping of the main topic can be seen in most of these stories, even across the world. There was an article posted recently about Australia's Internet blacklist, and whether it is an offence to the human right to Free Speech. The conclusion was that such a blacklist might slow down the Internet, and wouldn't stop everything, which once again I don't much care about.

Technology is advancing ferociously, and will continue to do so. Making important decisions based on technological issues sets an unnerving precedent. In the Australia example, in a few years or decades time I'm sure Internet latencies will be so low that such a blacklist would be unnoticable. From the misdirected conclusions of that article then it should, since the technological issues raised will have been fixed.

In the case of these databases, if technological advances such as quantum entanglement cryptography fix the security concerns, and supercomputer-esque processing power and storage are available for pennies, does this mean that all such databases should be made? Of course it doesn't, yet that is the argument being put forth by the government.

I call to reject any spin-ridden arguments based on petty implementation details and keep the focus on where it matters, the reasons for and against even contemplating the possible existence of such systems.

Learned Helplessness in Computing?

2009-02-06T02:37:00.003Z

I know I should be revising, seeing that my Atomic and Laser Physics exam is mere hours away, but I ended up on another Wikipedia trek, and came across the article on learned helplessness. Reading through it, I found that I could make many connections with the currently depressing state of computing, and attributing it to the complexity and proprietaryness of software.

Learned helplessness is a much-studied psychological phenomenon, where a subject gives up trying to change their situation. An example cited consists of three groups of dogs; group A is a control group and are put into harnesses and left for the duration of the experiment; groups B and C are put into harnesses but are also given unpleasant electric shocks. Each group B dog has a lever in front of it which does nothing when activated, whereas each group C dog has a lever which turns off the shocks to that dog and one of the group B dogs. The dogs in group C learn that the lever turns off their shocks, and they use it whenever they start to get shocked. Group B dogs, however, learn that their lever does nothing, whilst their shocks seem to stop randomly (remember, each B dog is paired to a C dog's lever, so the B dogs don't know why their shocks stop).

After this stage of the experiment all of the dogs are put into part two. where they are unharnessed in a pen divided in two by a small partition. The half of the floor with a dog on is electrified, whilst the half without is normal. Dogs from groups A and C would hop over the partition, away from the electricity and thus away from the pain. They don't know that the other side's not electrified, but they have a go and find that it's not. The dogs from group B, however, just lie down on the electrified floor and whimper, as they are repeatedly electrocuted. They could hop over the partition, but don't bother trying. These dogs become depressed.

The conclusion of the experiment is that the sense of control is very important. Dogs in group B and group C got exactly the same shocks (since they were both controlled by group C's levers), but only group B got depressed. Essentially, they learned that nothing they did would stop the electricity, it just stopped randomly. They then applied this knowledge to the second situation and took the shocks, rather than trying the new possibility of jumping over the divide.

This can be seen in people, where some parents can end up neglecting their babies since they 'learn' that the child doesn't stop crying whether they give it attention or not, and thus ignore it, thinking they are helpless to stop its cries.

The psychological explanation for this is that the depressed subjects, in an attempt to rationalise the seemingly random lack of control, think of it as an inevitability ("Babies cry"), blame themselves ("I'm making it cry") and think of it as pervasive ("I'm a bad parent"). This learned helplessness digs a psychological hole which is notoriously difficult to break out of, and even causes feedback loops, for example a neglected child will cry more and have more problems than that of an attentive parent, thus reinforcing the "I'm a bad parent" and "I'm making it cry" beliefs. In fact, even knowledge of learned helplessness can make things worse, since it can act as a confirmation of the helplessness ("You've told yourself that you're helpless when you're actually not." "See? I TOLD you I was a bad parent!") and others can end up blaming the condition for things rather than the person ("It's not your fault that your baby's ill, you've learned to be helpless at looking after it." "Yes, you should probably take it away since I'm too learned-helpless to look after it.")

So, aside from knowing more being awesome, how does this apply to anything I'm interested in? Well I couldn't stop contrasting the explanations with computing. The dominant computing platform these days is Microsoft Windows which, although all software has bugs, seems to be full of them. A lot of these bugs are user interface related, where the required action to achieve the desired task is non-obvious, or a seemingly obvious action produces an unexpected result (which includes 'crashes', where a program disappears without the user telling it to). Although anyone more involved in software development would view these as bugs in the software which should be reported and fixed, frequently less technical users (which is the vast majority) view such things as inevitable ("Computers crash"), as their fault ("I made it crash") and pervasive ("I'm bad with computers"). Just look at the currently running adverts for the Which? PC Guide: A bunch of regular people saying how their computers keep messing up, and then an offer of a guide to show them how it's all their fault because they're doing it wrong.

Since I write software, I would say that the Which? PC Guide is a complete hack: It's fixing something in the wrong place. A broken piece of software should not be fixed by telling each and every user how to work around the broken bits, the software should be fixed so that nobody ever experiences those issues again. However, since it's proprietary software, nobody is allowed to fix it other than Microsoft (although there are numerous other hacks to work around the broken bits, some of which have created an entire industry, such as firewalls, anti-virus/spyware/adware programs, etc.).

The majority of computer users, however, do not think like me, since I am a group C dog: I know how to fix things. In fact, in human experiments into learned helplessness, it was found that people could concentrate more and solve problems more quickly in the presence of an annoying and distracting noise if they had a button which could turn it off, than those subjected to the noise without such a button, EVEN WHEN THE BUTTON WASN'T PRESSED. So on a Free Software system, where I know that it is possible for me to fix something if I truly wanted to, I don't get depressed, however on a proprietary system I frequently get annoyed, angry, irritated, etc. when the software behaves in undesirable ways.

For example, clicking a link that says "Download this program" in Idiot Exploiter 8 doesn't download the program, it just gives an subtle message under the toolbar that Internet Explorer has "protected" me by preventing the program from downloading and that I should click it to change that, and when clicked presents a menu with the option to download the program (how is this any different to the previous promise of a download?), which when clicked brings up a box asking if I want to save the program or run it, so I click run and when it's downloaded I get a warning saying that programs can do stuff to the computer, do I want to run it? I click run again (how is this any different to the previous promise of running the program?) and Windows pops up a message saying that the program is doing stuff, do I want to allow it to continue? I press continue an FINALLY get the the "first step" of the installer.

On Debian I could give a similar example that I can't get the Gdebi package installer to work, which means that I have to save packages and install them with the command "dpkg -i package_filename.deb", which can result in a broken setup if the newly installed package depends on other stuff, which means I need to install the stuff to fix it with "apt-get -f install" and press "y" to confirm it. This may seem annoying, but I know that if I wanted to fix it badly enough then I could, and would even be encouraged to do so (afterall, Gdebi works perfectly well in Ubuntu).

Whenever my wireless card messes up on Debian, on the other hand, I get incredibly frustrated and annoyed, and often need to walk away from my laptop and have a break, since I feel completely powerless over it. The wireless firmware I use is proprietary, since Broadcom don't tell anyone the language that their wifi chips speak (although clean-room reverse engineering of a Free Software replacement in Italy seems to be showing some promise), so even though I'm running completely Free Software applications on a Free Software kernel of Free Software drivers (in my case Linux), and can look at the code at any time to see what it's doing and possibly fix any problems, when it comes to my wireless card the disconnects are seemingly random, as I have no way of inspecting the firmware since it is proprietary. I therefore feel helpless to stop it disconnecting, and can't remedy the situation in any way other than disabling the Wifi, unloading the driver, reloading the driver, enabling the Wifi and trying to reconnect. If that doesn't work then all I can do is to try it again. In fact, I've even written a little script which does all of that whenever I run "restart-wireless". It's so bad that the developers of NetworkManager, the (currently) best network control system on Linux, do the same thing. If network manager's running and I get disconnected then I see the wireless network icon disappear and the wifi LED turn off. After a few seconds the Wifi LED comes back on, the Wifi icon comes back and it tries to connect. If it doesn't work then it happens again. It's depressing.

So there's one reason I think computing is in the sorry state that it is, people are being conditioned to think that "computers crash" (which conveniently keeps the cost of quality control down), that they aren't "using them properly" (which conveniently keeps the costs of having good designers down) and that they're destined to always be "clueless with everything computer-related" (which conveniently keeps people upgrading stuff they don't need to on the advice of the 'experts' selling the upgrades). This was caused by the proprietary software world, since with Free Software the volunteers, users, developers, companies and organisations which make and sell it actively encourage all users to "hop the partition" and 'scratch their own itches', since it results in less work and more Free software for those doing the encouraging. Whether it was intentional or not is debatable (never assign to malice that which can be explained by (in?)competance).

This unfortunately means that people like my Mum have some kind of internal off switch which is activated by the word "computer", so that when things like the broadband packages they are paying for are discussed with a sentence like "This one has a limit on how much we can do per month, so they'll charge more if we go over it, but this one doesn't" are met with a response such as "Well you know I don't understand these things" (which is the exact same sentence used for every attempt at explaining something, no matter how basic). It makes me *REALLY* frustrated when people don't bother to apply mentals skills which even five year olds possess, simply because they know computers are involved. Discuss the exact same thing with phone contracts, or even the price of meat per kilo, and they'll readily discuss the merits of each option, and even go into the small print, but with computers they've learned to be helpless, and thus think they have no control over anything related, and feel much more comfortable being extorted by monthly bills twice the size of what they could have, where the value calculations are worked out by someone else, than they do with having to confront some computer-related thinking for a few minutes.

Another big cause of computer-helplessness is a genuine problem with computing today, Free Software or not. Empirical evidence does say that just the presence of control, whether or not it is used, is the important bit (like my access to the source code for everything I use), but it's still a chore to actually make use of that control.

As an example, a few years ago the Nautilus file manager changed so that icons got bounding boxes. This meant that before the change if I clicked in a transparent corner of a circular icon then nothing would get selected, but after the change the circular icon would be selected because I'd clicked within the bounding box. This is a good thing usability-wise, but I was rather annoyed with the way it interfered with my specific setup. I had cut out images and assigned them as icons to the various folders in my Home folder, stretched them rather large and arranged them manually so that they filled the Nautilus window without overlapping, so that clicking the visible parts would select the icon, whilst clicking on a transparent part would 'fall through' and select one visible below. I was very proud of this, and it had taken quite a while to do. Then, after an update, all of the icons got bounding boxes and thus clicks in transparent areas no longer fell through, making selecting and double-clicking things unusable. I had to make all of the icons small again, and arrange them in a grid, destroying the previous awesomeness. I took it upon myself a few months ago to bring back the no-bounding-box Nautilus as a well-buried option, so I got the source code to the most recent version of Nautilus and looked through the version control history to find out when the change was made which added the bounding boxes (I think this is where it changed http://svn.gnome.org/viewvc/nautilus?view=revision&revision=9123 ) and replaced that section in the latest code with the old code, and it worked. However, this took a few days, since I've done very little C programming and never used GObject with C before, and I didn't even have to write any code (it was just copypasta). If I want to fix every bug I find it would take an intractable amount of time, even though I can fix any bug I want to individually.

There looks to be some promising stuff going on to rectify this at the Viewpoints Research Institute, an organisation funded by the US government with awesome Computer Scientists like Alan Kay. One of their aims is to "reinvent" computing, which basically involves making (yet another) computer system, but one which is as understandable (and hence small) as possible. They're aiming for a complete, working system in under 20,000 lines of code (for comparison, Windows has around 40,000,000), and have got some nice tools like their "Combined Object Lambda Architecture" programming system, which aims to be written in itself and be able to compile down as far as FPGAs (ie. rewiring the microchips themselves to represent the program), and OMeta which allows very compact and easy to understand programming language implementations (for example they have an almost-complete (missing "try"/"catch" and "with") Javascript interpreter which is only 177 lines of code), which, like their COLA, is written in itself. This allows COLA-based implementations of other languages to make their system, with new languages so easy to define that each part can be made in a tailor-made language, even being redefined in places where it makes things more comprehensible.

Hopefully having more understandable and approachable code will mean it is easier to find and fix bugs, so that nobody has to experience them for long. It might also help to reduce the number of people who teach themselves to be helpless at computing, although as for the ones who are already learned-helpless it will take a lot of effort on their part to break out of it, which won't be helped by proprietary companies trying to dress up their shit code as some kind of magical snake oil which cannot be obtained from anywhere else, or be written by mere mortals (which GNU set out to disprove with UNIX and has done a pretty fine job), and the media displaying binary all over the place whenever the internals of computers is mentioned.

OK, I think I should carry on revising now, as I've gone off on a bit of a rant, but damn it my blog's still not boring or crap! :P

Retarded = backwards

2009-01-30T17:02:00.002Z

It seems that our literally retarded government is mulling over the idea of a "broadband tax" of 20 quid per year for everyone with broadband (which is actually everyone in the country, since they also want universal broadband access) which will be given to the "music industry" and the "film industry".

With this in mind, perhaps now is the time we can finally recover our failing Ice House economy with Ice House taxes on all fridges? Our TV channels and film studios can receive tax on VHS tapes and DVDs? Our dwindling equine propulsion industry could benefit from a tax on all internal combustion engines, electric motors, petrol and diesel. Our whale oil industry could benefit from a tax on light bulbs, flourescent tubes and LEDs. The typewriter industry could have a tax on all computer sales, as can gramophone makers. Whilst we're at it, why not charge for Wikipedia and give all of the proceeds to the desperate Encyclopedia Britannica?

In fact, to encourage these ideas I propose that everyone who uses a fridge, a video or DVD player, any form of engine-powered travel, electric lighting or computer should be labeled as a criminal, since it is completely within my rights to make such accusations when there is no legal basis at all for it. Actually, criminal is too light a word, afterall some crimes are legitimate in certain circumstances when they're the lesser of two evils. The label I propose therefore must be something that's never legitimate, so that juries can have their minds made up for them beforehand rather than having to go through that tedious business of deciding guilt (which, after all that effort, might not even get me the result I want!). They should be called some kind of word which implies rape, murder and that sort of thing... how about serial killer? Yeah, that works. OK, now on with the spreading of my message with twisted logic, brainwashing and of course my all time favourite, the outright lie.

Here's one to get started with:

"You wouldn't strangle a toddler

You wouldn't stab a pregnant woman in the womb

Refridgeration is murder

Murder is a crime

Don't let the serial killers get away with it

Copyright the Respected Icehouse Association of America"

Or how about a more subtle brainwashing?

"He's the, kind of man that makes edits in-place,

He kills post men and shits on their face,

He wanks in the sandwiches you leave in the icebox,

He makes documents using a word processor, what a fucking cock,

He's a, Nerdy Nigel, a Nerdy Nigel

Nerdy Nigel word processes his documents

(Copyright the British Typewritographic Institute)"

Or, perhaps, we should actually EMBRACE technological innovation? ESPECIALLY innovation which looks set to destroy the crumbling monopolies of the 20th century's "music industry" (ie. the few rich sods who decide that you don't want to listen to the vast majority of bands and thus give millions to Britney Spears whilst decent acts end up working in McDonalds) and "film industry" (ie. the few rich sods who decide that potentially good, inventive ideas are too risky to back compared to more sequels of the same old shit). Giving them such a "tax" is not only COMPLETELY disruptive to the economy, but offers NEGATIVE incentive for them to do stuff, since their income could come straight from the tax without wasting any money doing any of that 'making stuff' kerfuffle.

Labour need a firm kick to the teeth for all of the bullshit they're shovelling over us. They're as conservative as the Conservatives, leaving the Liberal Democrats as the only viable way out (and that's still rather tenuous). The problem with the Lib Dems is that they don't seem to have any morals either, not in a 'Fuck you, I'm in charge' Labour way, but in an 'OK as long as you vote for us' way. I think forming policies specifically to cater to a minority so that they'll vote for you, regardless of how it affects the majority, isn't a particularly good thing (here I'm not using minority in an ethnic sense, but for instance their stance for legalising cannabis. Whilst this is obviously backed wholeheartedly by that minority who abuse cannabis, it's impact on the majority of the population is far from clear cut).

On a side note, I really really really wish that Java dies a quick death. It's a fucking terrible language, restrictive, verbose, full of boilerplate bollocks, full of glaring errors which, for some ungodly reason, are standard, making every Java environment broken (either in the sense that they're nonstandard but work properly, or they follow the standard but are full of fucking retarded shit like 2147483647 + 1 = -2147483648 (which *IS* an error, as anyone over the age of about 5 can tell you)). Object oriented my arse. What the hell are these "base types" then? What about methods? What about classes? Fuck off Java.

The End

PubSubClient back in development

2009-01-25T01:57:00.002Z

I've been messing around with my pubsubclient library again, and the issue with publishing now appears to be fixed (either thanks to me or thanks to the ejabberd team if it was a bug in the server).

Anyway, it's working again, and it's now an opportunity to get more reply handlers and documentation written. Since I'm currently in the middle of my exam period this obviously should not be a full-steam-ahead effort, but I'm going to keep chipping away at the TODO list (which is now formalised into a not-yet-up-to-date SPEC-COMPLIANCE file). It's now just a case of putting in the work, since it's not hard thought involved, it's just extracting data from XML and putting it into sensible, pure Python representations.

The website is still around at http://pubsubclient.sourceforge.net/ and the code is still on GitHub at http://github.com/Warbo/pubsubclient/tree/master

Enjoy :)

The Importance of Transparency

2008-11-12T19:57:00.004Z

I know some people who read this can't be arsed with the technical posts, but I do use this blog to tell the world, including my friends, what I'm up to, so please bear with me :)

People > Data > Code > Hardware

That sequence represents two things. Firstly, if those are treated as arrows, it shows how computer programs are generally used. A person inputs some data and the code does something with the data by running on the hardware. Another way of looking at it is as an inequality. People are more than data, data are more than code and code is more than hardware.

Hardware is a lump of plastic, silicon, germanium, steel, etc. It only exists to run code, therefore code > hardware.

Code only exists to manipulate data, whether those data are numbers in a calculation, images to be displayed, music to be played, messages to be sent, etc. Therefore data > code.

Data is only kept around because it is of use to people. Despite our best efforts, hardware and software cannot appreciate the humour of a LOLCAT image. Therefore people > data.

This relationship can be seen in many areas. If I have the most awesome server ever, nobody gives a crap if my Web site is crap. Google's search engine started life on incredibly underpowered, unreliable hardware, but nobody noticed because the code was redundant and reliable. Mugshot.org may be coded better than Myspace.com, but nobody uses Mugshot and there are far more data in Myspace.

Hardware doesn't matter, so as much as possible should be as cross-platform as possible. I have Linux running on my desktops, my laptops and my 'phone. Windows will only run on x86 and x86-64 machines, which means no phones, no PDAs and very few embedded devices like set-top boxes and games consoles. If code is cross-platform then users don't need to give a shit about hardware, which makes life a hell of a lot easier.

Code doesn't matter as much as data, so as much as possible should be in standardised, implementable, documented formats. The spreadsheets I write in OpenOffice.org also work fine in Gnumeric and have live copies saved on Google Spreadsheets. Spreadsheets made in Microsoft Office 2007 can only be opened in Microsoft Office 2007, since everyone else's attempts at compatibility are flawed. If data is openly standardised then users don't need to give a shit about software, which makes life a hell of a lot easier.

This just leaves people and data, which are the only things that are important (code and hardware are just tools used by people to manipulate data).

Using the examples above, I can save a spreadsheet on my desktop and access it from anywhere in the world via Google Spreadsheets in the browser on my phone. The proprietary alternative is to only be able to use Microsoft Office 2007, which requires Microsoft Windows, which requires x86/64 hardware. A very cosy position to be in for Microsoft, but for the vast majority of the world who are not Microsoft employees, why give up so much? This isn't just a feature argument either, since Microsoft could make a browser-based spreadsheet system. The argument is WHY DO I HAVE TO WAIT FOR MICROSOFT? If you hand someone the keys to your data, you should expect to be taken for a very long ride, at the end of which you might not even have that data any more.

The same goes for Facebook and other proprietary applications. (Free Software doesn't always use standard formats, but the formats are at least documented to some small degree in the code. Proprietary apps give you no code.)

END COMMUNICATION

Medibuntu :P

2008-10-28T15:03:00.004Z

Just read that the one of the GNU project's Free Software desktops, Gnome, is being used in a new machine which uses flesh elasticity to find breast cancer. That's an awesome reason to hack on Free Software, since its impact on the world literally IS saving lives :)

The company, SuperSonicImagine, aren't just (ab)using Free Software because it's royalty free, like many companies do. They use the Cairo vector imaging library, amongst others, in their own software and contribute patches back upstream so everyone benefits from their improvements :)

Also, if you're in a recent version of KDE 4, try opening the Akregator feed reader, opening some Web pages in its embedded Konqueror part, open Epiphany, then drag a tab from Akregator over the panel entry for Epiphany until it switches, then drop the tab into epiphany and watch it open. Pretty nice integration going on :D

Amarok and roll

2008-10-18T18:40:00.003+01:00

Just installed Amarok 2 via the Neon nightly build service (for Kubuntu, but still works on Debian Unstable :D ). I have to say, it is absolutely teh awesome! It really shows what KDE 4's "pillars" can do when used in combination.

Don't get me wrong, I've used Amarok 2 before. However, the first time I tried it it kept crashing and didn't have much functionality. My attempts since have been greeted with a feature-packed player, which couldn't actually add anything to the playlist other than Internet radio streams :( With the nightlies it seems to be rocking full steam ahead, and doesn't take up too much space either :)

The only problem currently is that the Qt it uses doesn't seem to have antialiasing enabled for text, but that's a very minor issue.

Now to get Nepomuk to run without making my machine crawl. Perhaps the Java backend would make it work faster?

I CAN HAZ OPENMOKO?

2008-10-09T13:52:00.002+01:00

Firstly, thank you to everyone who gave me mobile phone advice. I've probably disregarded all of you with my eventual purchase, an OpenMoko Freerunner :D

The Freerunner is pretty nice, except of course that every piece of software on it is an utter pile of unusable fail. However, I paid for the phone and not the software, so I'm going to try and make some decent apps for it.

At the moment I'm getting responsibilities piling up though :( I've got homework assignments, Free Software Society organisation, Computer Science Society collaboration to manage, Access Space, ShefLUG and Manchester Free Software collaboration to manage, Sun Microsystems relations, out-of-hours programming for my course to catch up on, relationships, general society stuff like RockSoc and things, Free Software programming (some of my projects are in dire need of some time, which I simply don't have), I have a pile of books which I want to read, the constant barrage of email, XMPP and RSS, going to the gym (which I still haven't done), sorting water stuff, sorting rent and contracts, sorting legal bollocks, sorting TV license, sorting the electoral roll and to make matters worse I'm rather ill, resulting in painful sneezing and coughing fits (I've even had to take some days off, which means missing lectures, which means catching up :( ).

I think the way to tackle this is delegation. The Free Software Society takes up a lot of my time, but is also full of awesome people who gladly help out. By getting these people to help out, like Arthur organising the socials, it will result in a lot more free time in which to do the other stuff.

Still, I've only got the one life, so why waste it? It does annoy me though, when I spend two days attempting some Physics homework and make absolutely no progress :'( That's at least 12 hours I could have used to get something else out of the way, but unfortunately I fail at Physics too much. The solution is, of course, to work even longer on it. Bugger.

Ah well, I don't have time to blog away so I'll wrap this up now.

By the way, PubSubClient is now hosted on GitHub rather than Gitorious due to a request in my blog comments.

Until next time!

On People

2008-10-05T01:56:00.002+01:00

People are intelligent, sentient beings.

If you try to deny the intelligence or sentience of any human being then I suggest you give me an incredibly wide berth.

Sentience, in my mind, is the only thing of any value in the entire Universe. I don't give a crap how well you can recite Pi, or tell funny jokes, or how awesome you are at anything. If sentience is at stake, I'd bet you and I together in an effort to save it.

For those who belittle the sentience of others, I severely wish you're being ironic, or you may meet an untimely end at my hands. Yes, that is a death threat, but laws don't mean anything compared to the continuation of sentience, so I would gladly accept whatever temporal punishment may be wrought against me in a fascism such as the UK if it means an ontherwise unobtainable continuation, or possible continuation, of sentience.

Some people are crying out for bricks to reshape their skulls. However, such sentient beings are part of the solution, rather than the problem (for the time being), so the best course of action is to disassociate oneself with acts one finds disagreeable.

I hope that offers some useful philosophy for someone, as it is useful to me.

Brains are Object Oriented

2008-09-21T04:54:00.002+01:00

Following on somewhat from my browser UI rant, an important thing to realise when designing interfaces is that the brain is used to realistic, real-world things. It gets confused by magic, tries to reject Quantum Physics, and so on. In other words, the brain is Object Oriented.

To be Object Oriented simply means that there are a bunch of "things" which can each do stuff and each have stuff. For example, a ball is a thing. It can bounce and roll, and it has size and colour. Being Object Oriented means breaking apart some things which seem to logically go together, like verbs (or in the case of a computer program, functions). However, with really huge projects it is clear that separating like from like and instead combining things based on context (into an object) is less confusing, since this is more understandable to our brains.

With user interfaces there is magic and quantum "spooky action at a distance" which the brain does not like. This is where changing one thing affects another. For instance, the up and down arrows on a scroll bar. These arrows are not connected to the slider, so how do they manage to move it up and down? By magic. How often do you drag the slider on a scroll bar rather than press then buttons? This is because the brain thinks of moving down as a method of the slider, rather than the arrow being a function which moves the slider. For this reason I propose that arrows be taken off scrollbars (some themes to it already).

Another problem is toolbars. They contain precisely that, tools. In the real world when we want to join two pieces of wood together we think about putting a nail through them. In order to do this we get a hammer, but that's just an implementation detail. If we could push the nail in then we would do. Thus toolbars are bad because they are a kind of magic. They contain functions, ie. they perform actions, like save(document). However, the interface *should* provide methods, ie. the documents should be able to perform the action, like document.save().

A key thing to realise is that your application *is* the GUI. Therefore your GUI should be Object Oriented as far as possible, and should itself act like an object. Developers often think of their code as being the heart of an application, with the graphics as a glossy veneer on top. Users, however, think of the graphics as being the heart of an application, and the code just sticks it together. There are far more users going to be using your software than developers (you should hope :P ) so keeping this in mind is important.

Video or it didn't happen

2008-09-21T03:57:00.002+01:00

I've made a screencast to show some functionality that PubSubClient provides. Doesn't play in SWFDec at the moment, so you might have to use something like this. I accept Google Video's terms of use, but not YouTube's.

The video shows the Browser test application being used to find the nodes on a server and their sub-nodes, add and delete nodes, and add and remove node owners. I've been busy tonight, so that the display issues which cause me to close and reopen windows to show updates are fixed, I've got the Owners functionality working for Publishers and Outcasts too, and I'm mulling over a Subscriptions tab in the node properties (awkward since it may involve message stanzas, not just iq stanzas), generating the contents of the Metadata tab dynamically based on what's defined and changing the access model and other configuration options (awkward since it involves requesting, submitting and cancelling XMPP forms).

For now though, I'm getting tired so it'll have to wait.

PubSubClient has a home

2008-09-20T17:03:00.003+01:00

I set up a Gitorious repository for PubSubClient a while ago, but couldn't actually put any code in there because my SSH key wasn't working with the pass phrase I remembered (ie. I forgot it :P ). Now I've revoked that key and added a new one, so I can upload again :D You can find the complete source there. I've also created a Sourceforge project for it, so that I can give it a free website (Google Code hosting doesn't allow GNU Affero GPL licensed software :( ). The project is still pending approval, but I feel confident that it'll get approved since it is pretty novel.

The repository contains the library in its current form, as well as the ever-improving "browser" test, the currently-stalled "reader" test and the not-really-started-yet "writer" test. To use the library itself all you need is lxml and xmpppy, then just stick the "pubsubclient.py" file in the same folder as your application and you're ready to go. The tests make use of some other libraries, since I wanted to demonstrate that it is easy to integrate into any existing toolkit. To use the browser you'll need pygtk and kiwi, the reader needs pygtk, kiwi and webkit, whilst the writer isn't worth bothering with ATM.

Have fun :D

PS: In other news Jabber Inc. have been bought by Cisco, which is pretty cool. There's some confusion though so remember, "Jabber" is just a nickname for the messaging protocol. Its actual name is XMPP (eXtensible Messaging and Presence Protocol), since it may have originally been created by Jabber Inc. a decade ago, but for the past few years it's been looked after by the XMPP Standards Foundation. Jabber Inc. (who own jabber.com but NOT jabber.org) can of course add to and change the standard, but they must follow the same proccess as Google, Microsoft, Facebook or anyone else who wants to do so. In other words: This is a Good Thing(TM) since XMPP is being adopted heavily by a huge firm like Cisco (who previously used the SIMPLE messaging standard, which is anything but), and the XMPP standards are still being kept safe by XSF as they were already. Rock on!

Spot The Difference

2008-09-20T00:54:00.006+01:00

Here's Google Chrome on Fedora:

Here's Firefox with a "Google Chrome theme" on Fedora:
What's the WTF-were-you-thinking mistake? Can't figure it out? How about if I tell you it also applies to the default Firefox theme on OSX:

But not in the default theme for Windows:

Or Ubuntu:

Still can't see? How about an analogy:

Still don't understand? Let me spell it out:
Chrome gets this (as does Opera, but I don't give a shit because their browser is still proprietary), but this supposedly-Chrome theme (as well as the OSX theme) have made the bad UI of Firefox EVEN WORSE. The default Windows and Gnome themes have tabbed pages, with some unknown, magical force changing the address bar when switching tabs. This is BAD since it requires either reverse-engineering, or study of the code, to find out the behaviour. However, with those 'upside-down' tab themes the tabs are now controlling the address bar, with an unknown, magical force changing the page content accordingly. This is EVEN WORSE since it is the page contents that people actually care about! Hype Firefox all you want, but I prefer looking at Web SITES to looking at Web BROWSERS.

In short: EPIC FAIL

Wanna Be A Programmer?

2008-09-19T11:39:00.004+01:00

Computers are all around us, and our lives are to a large extent controlled by them. Your bank balance, your phone calls, your email, messaging and Web browsing, games, wages and bills, music, video, literature and image production, trains, planes and cars, it's all controlled by computers.

Software is the stuff which controls computers, and therefore our lives. So who controls the software? Well, if you deal with proprietary software then it's usually controlled by some foreign corporation trying to wring money out of you. If you deal with Free Software then the control is still in the hands of the developers, however YOU can choose the developers. If you don't like what the original developers are doing then you have every right to fork the software and get some other developers to work on it and take it in the direction you want. Often this involves paying the developers a wage, but there is also another option: YOU can develop it yourself! The only skill you need is computer programming, which is a skill that can even be picked up by young children, as long as they have some exposure to it.

So how can YOU learn to program? Well if you're a complete beginner I would follow these steps:

1) Forget EVERYTHING you think you know about programming.

It's most likely bollocks, perpetuated by the media's obsession with stereotypes and putting flashing, unintelligible crap all over any computer monitor that appears on screen, and the proprietary software companys' desire to look like the crap they serve is somehow magical and unequalled. It's not. Programming is easy. It has to be, because computers are so unfathomably stupid. Just because Turner is able to create beautiful seascapes doesn't mean that a two year old can't scribble with a crayon, in the same way that simple programs are easy despite huge ones being hard.

2) Learn to think like a programmer.

2.1)

A nice way to get the hang of this is to play games like this one (NOTE: You may need to install SWFDec to play that). Light Bot features a very simple programming language to control a robot, it is easy to use since each command is an icon and the program (called "main method") is a grid which you drop the icons into then press Go (the program runs like English text, ie. starting at the top left and going across, then going down a row starting at the left and so on). The nice part about it is that the program can only be a maximum of 12 commands long, which is not enough to complete some levels, but there are two functions (reusable blocks of code) available to make repetitive things take less space.

2.2)

After you've completed that game a few times (there are 12 levels) you can go on to Guido van Robot (this may be in your package manager already), which is very similar to the Light Bot game but uses typed commands rather than movable icons, allowing you to make much longer programs. Even without Light Bot's restricted space it is still important to use functions like you've learned, as they are the best way to make large programs more manageble and less confusing. Transitioning from Light Bot to Guido van Robot is an important skill, since it makes sure you know the principles of programming (commands, functions, repetition, etc.) and how to use them, rather than just learning one specific programming language.

2.3)

After you've mastered Guido van Robot and can comfortably tackle any problem without difficulty or confusion, it's time to move on to something a bit less rigid in structure, like the old favourite Logo (there are a number of different Logo programs out there, you can try XLogo and UCBLogo). Logo is a programming language in its own right, but is often used with the "turtle" graphics system, a very similar concept to controlling the Light Bot and Guido van Robot (it can actually be used to control a real robot, but I'm assuming you don't have one :P ). The turtle can be moved to any pixel on the screen by giving it commands like FORWARD, RIGHT 90, and so on, plus it can draw a trail as it goes, allowing you to draw images. Taking advantage of the incredible speed of modern hardware you can make animations, by drawing lines, erasing them, then drawing them again in a slightly different way. Give yourself some problems to tackle, such as drawing a circle, making a function which can draw a circle to a given size (this uses the concept of "arguments"), drawing a spiral (this uses the concept of "recursion"), a stick man, an animation of a bouncing ball, making the ball squish slightly when it bounces, a windmill with turning sails and a growing vine. All of those are possible with a little thought, but *remember to use functions* and leave yourself *a lot* of comments throughout your code to remind yourself wha each bit does. When you can make those given examples without much thought you've mastered a lot of the art of programming. Well done :D

2.4)

There are many books out there which can help you learn to program. For instance How to Think Like A Computer Scientist. Googling for guides and tutorials on your language of choice is usually helpful too.

3) Learn one powerful programming language

Logo is a nice little language, but your programs can't really talk to anything else. This requires software called "libraries", and for libraries which are not written in your language of choice you will need a "binding" to access them. I don't know of ANY libraries which are written in Logo, or any bindings to let Logo access libraries written in other languages. This means you'll have to move on to something more powerful :( Since you now know Logo, which is a simplified form of the LISP language, it would be sensible to learn another simple, LISP-like language. I would recommend Scheme, which is a very powerful type of LISP, without a lot of the unneeded crap which exists in LISP. Guile is a very good Free Software Scheme system, which has bindings for many libraries, therefore I recommend your next step is to dive in and learn Scheme using Guile. It is very similar to Logo, except that every command is enclosed in brackets. If you want to make real graphical applications, there are bindings for the Gnome desktop, and even the new Clutter 3D graphics library. Now that you know Scheme you can do anything. Although some things are harder than others...

4) Learn the Object Oriented paradigm

In the same way that functions are an INCREDIBLY useful tool to make programs short, readable, understandable and maintainable, there are a few different progamming 'paradigms'; ways to structure and think about your programs and how they work, which will make your life easier and avoid getting headaches.

The first paradigm you used was "procedural programming", where the code describes the procedure to follow, "do this, then do that", but there are many more, some of which you've touched on. "Object Oriented" programming (OOP) takes functions one step further and groups them together into so-called 'objects'. To run a function you must ask the object which contains it. Objects have a type (a "class"), which can be a subclass of another class. For example "dog" might be a subclass of "animal", so that every function which "animal" can do ("breathe", "eat", etc.) a "dog" can do implicitly. Every object, for instance "Lassie", is an 'instance' of its class, for instance "Dog". Objects can also implement different roles (called "interfaces"), like "Lassie" can implement "Entertainer" and "Pet" (since not all "dogs" are "entertainers" or "pets"). By dividing a problem up into the different classes and objects it involves, the program becomes as simple as describing how they interact (eg. "lassie.fetch(big_stick)"). Learning the Object Oriented paradigm will make your life a LOT easier when you start to make large programs, but it is not very easy to do on your own.

5) EXPERIMENT!

If you have an idea or a question, try it out and see what happens! You can ONLY learn through experimenting and playing, there just isn't another way to do it.

6) Learn more languages

Scheme isn't the only kid on the block. There are many other languages you may like to learn. Good choices would be Smalltalk, Ruby, Python, Javascript, Vala and, if you're feeling masochistic, C, C++ and Java. The more languages you learn, the more approaches you learn to tackle problems with and the more you learn about why certain languages do things in certain ways (and therefore how to use them more efficiently). What may be hard in one language may be easy in another, so having a substantial set of knowledge is always a good thing.

7) Contribute to Free Software!

It might seem a daunting prospect to make your own Web browser, file manager or music player, but there are already many such projects out there with the code fully available for you to download and play with. Every Free Software project welcomes new developers, even if you're just fixing a bug which really annoys you. If you contribute to a widely-used piece of software like Firefox or Gedit then your changes, if approved by the maintainers, will be used by millions of people worldwide. If your changes aren't approved, but you would still like to make them available, you can keep them in a distributed version control system like Git or Bzr, letting you cherry-pick the upstream changes you want, and keep any changes you make yourself, and also let other people get your modified version.

Most importantly, don't be scared by all of the complicated stuff you see computers doing every day. Computers don't get harder and harder to program over time, they get easier and easier, since all of that fancy stuff has *already been written*! You might not understand how an image gets from the hard drive to the screen, but you don't need to know or care (I don't!), other people have already written libraries to do that. You just have to say something like "display(my_photo.jpeg)" and voila!

With computers becoming more and more integral to our way of life, I encourage everyone to at least attempt following some of those steps, if only to realise that computers aren't unknowable, magic things; they're understandable, controllable and most importantly they are changable. Posessing an attitude (like my Mum) of "I don't understand these things" is retarded. I didn't know how to piss standing up until I tried it.

...And Laws Were Most Numerous When The Commonwealth Was Most Corrupt

2008-09-18T12:51:00.002+01:00

Personally, I would say that power corrupts more than TV, miniskirts or saggy jeans.

I do, however, completely agree with Nsaba Buturo's statement "What's wrong with a miniskirt? You can cause an accident because some of our people are weak mentally,". He could've given an example if there was a mirror nearby.

The Effects of Promoting Propaganda

2008-09-17T18:10:00.002+01:00

Richard Stallman and the Free Software Foundation are often the butt of jokes due to their campaign of explaining "GNU/Linux". The problem I have with their tactics is that they bring the issue up where it isn't particularly appropriate, for example in the recent Steven Fry video. There was no need to blabber on about such unnecessary bike shed issues in a video that is solely written by the FSF (ie. there's no need to correct anything, since they control its contents). I do, however, agree with the basic reasoning they have, that the phrases and words we use can shape our minds, and especially the minds of those we are talking to (if they are new to a subject).

In their case it is the use of the name "Linux" to describe an entire computer system, where Linux is only the kernel, and the use of the phrase Open Source instead of the phrase Free Software since the former promotes an efficient way of programming whereas the latter promotes the freedom of computer users. An example more common to people who aren't me would be the gross misuse of the word "pirate", used instead of "copyright infringer" in a context which implies that infringing copyright is akin to looting, murdering and raping on the high seas, and thus biases the minds of those who hear the phrase (murder, theft and rape are obviously wrong and criminal, and very serious matters indeed, whereas not only is copyright infringement an intangible and often debatable issue, it is not clear whether infringement is even wrong, despite its status as criminal).

One term a lot of people who know me will know my chargrin at is "secured" and "unsecured"/"insecure" when describing an 802.11 wireless computer network. The phrase is used to describe WEP and WPA encryption, but completely biases the minds of people who use and hear it. Deciding whether to allow or disallow devices to connect to a network is a matter that can be debated by rational people, whereas framing such a debate into choosing a "secure" network or an "insecure" network can easily end all discussion in favour of the option labelled "secure", ie. restricted access.

Such framing is plain wrong: First, a Virtual Private Network (VPN) can be used over any network, even an "unsecured" one, to establish secure communication between machines. For instance, a wireless access point can be used without encryption, thus allowing anyone who wants to to connect, whilst certain computers (for instance the tennants in a house) can use a VPN on top of this network to allow each other to access shared files and networked printers and nobody else on the access point can access things. A network could even be set up to allow the VPN as much bandwidth as it wants, giving what's left over to anyone else (so the tennants wouldn't even realise other people are online, for example, whilst people in the area can get free access to the knowledge and commication abilities that the Internet provides, although at a reduced priority).

Second, WEP encryption was broken years ago, thus any network which is "secured" by WEP actually has no security at all. Any device can use a Free Software tool like Aircrack to monitor the network automatically until it gets enough data to present the user with the encryption key being used.

The reason I'm going on about this is a very serious one: It might soon become illegal in India to allow people to connect to an 802.11 wireless computer network. Now, of course those behind this aren't using those words, they are saying "unsecured" networks will be illegal.

Oh yeah, it's also because those who use "unsecured" wireless networks are apparently terrorists. Since the T-word is in there I wouldn't be suprised if this does become law and sets an unnerving precedence.

BTW, I just noticed this (both by Uli Kusch though):

You may need to install SWFDec to watch those videos.

I am teh awesome

2008-09-12T13:09:00.003+01:00

Seems I was overly cautious in my last post, since node deletion now works :D

Next I think I'll work on affiliations, which might take some thinking to do sensibly...

The Power To Change

2008-09-12T10:16:00.006+01:00

As I've blogged about before, I'm currently working on a general purpose Python library which implements an entity in the XMPP/Jabber Publish/Subscribe specification XEP-0060. The library itself can currently send equivalent stanzas to all of the examples given in the specification. It does not yet handle the replies from everything, doesn't handle incoming messages (ie. updates) and its error handling consists of printing the error stanza to the terminal. However, at around 1,500 lines it's already a bit too much to grasp with only a specification to go on. For this reason, once I had implemented every needed method I decided to take a pragmatic approach to the reply and message handling.

This originally started as a PubSub reader application, similar in form and function to current news reader applications like Akregator and Liferea but using PubSub nodes instead of RSS or ATOM files. This proceeded quite nicely until I hit a bit of a wall: There wasn't anything to read!

To fix this I started to write a PubSub writer application, similar in form and function to current offline blogging applications like KBlogger and Gnome Blog but once again using PubSub nodes instead of RSS or ATOM files, or Web service APIs. This was a bit premature of me, however, since there was nowhere to write things TO, and then I came across x60br and thought it would be the perfect kind of tool to make next, thus I started a simple PubSub browser.

The concept of the PubSub browser I am making is simple, and I have blogged about it before. You're presented with a window containing minimal controls. Into a text box at the top the address of a PubSub-capable server is put, then the "Get" button next to it is pressed. The browser then adds this server to a tree view and uses the PubSub library to send a message to the given server, asking for a list of the nodes it contains. When a reply is received any nodes are added to the tree in a level below the server. Each of these nodes is then queried for any nodes that they may contain, and when the replies come in they are added to a level below their respective parents. This isn't quite a perfect way of doing things since it doesn't take into account the loops which the PubSub system allows, but is good enough for this tool's purposes.

With a tree of nodes available the next step to take was implementing some ability to alter the structure, ie. add, remove, change parents, etc. I've now achieved this, as can be seen in the following screenshot of my current ejabberd server.

Until this point the choice of server hadn't mattered to me (it's all standardised), and since ejabberd is a) packaged in Debian and b) all the rage these days, I figured it was worth using. There are currently VERY few servers which can actually understand PubSub, the most popular being ejabberd and OpenFire (the former being used by jabber.org and the latter being used by the University of Sheffield), but since it's such a new technology there are issues arising with its server-side implementation (which my library is not designed to address). Essentially ejabberd is currently a bit broken, the most important deviations from the standard being that it allows items to be published to a collection (analogous to writing text to a folder, rather than to a file inside the folder), it allows leaf nodes to contain children (analogous to a file containing other files and folders (OK this is possible with archives, but that's not the point :P )) and it doesn't allow subscribing to a collection. Aside from those, a rather obvious restriction (although still standards-compliant, as far as I can tell) is that a rigid filesystem-like structure must be adhered to, with node names following the structure /home/servername/username/... This means that pressing the Add button when the server, /home, /pubsub or /pubsub/nodes is selected will result in a failure, and with /home/localhost selected only one name is allowed, /home/localhost/test1 (since the browser is logged in as the user test1). However, it does work as can be seen (I've created the node /home/localhost/test1), and in the process I've managed to delete quite a lot of code from the library (note for non-programmers: The more code you can throw away, the easier your life becomes :P )

Next on the agenda is deleting nodes. If I can't get that done today, however, then I probably won't get it done until Wednesday. I'm going to see Jooooooooooooooooooooooooooooooooooooooooooooooo...ingtons.

PS: If you want to get the code there's a little difficulty at the moment, since I can't seem to sign anything :( I've set up a git repository here, but at the time of writing it's empty due to the aformentioned difficulty.

Model-View-Controller

2008-09-11T10:25:00.003+01:00

First there was Last.fm's site redesign, now there's Facebook's. Both have been given a hard time, however I don't personally give a flying fuck about their website design. The *ONLY* useful thing from last.fm is the artist information. Fuck the personal statistics. Fuck the Shoutboxes. Fuck the Friends. The *ONLY* reason accounts exist is to prevent spamming which would skew the artist information database. So, do you want to see how last.fm REALLY looks? Well there are a few styles: text and XML. There is also an API (Application Programmer's Interface) available, but it requires an account to use so it can go and die in a bin.

If you are particularly clueless about how computers work then you might be thinking to yourself "those look like shit", and you would be right. However, structure is FAR more important than presentation, and those documents are well structured. The reason thinking along those lines is clueless is because such people have never seen a computer program, they've never pressed the View Source button in their Web browser and they've never taken apart any gadgets in their life. Those of you who have done at least one of those things will know that beauty is only skin deep. A website might look pretty, but the HTML the pages are made of look as ugly as sin. The HTML will have a decent structure though, which means a Web browser can be stuck in between the user and the HTML to make it look pretty.

What I am saying is that last.fm allow access to their database in a structured way, which allows applications (which are completely stupid and need to be told exactly what to do, hence the need for structure) to display the data in whatever the hell way the user wants. You don't need to use their website, since code for putting data into and getting data from last.fm exists inside every decent music player (Amarok, Banshee, Listen, etc.). Your choice of application is completely up to you, and you can keep using that application for as long as last.fm's web services maintain their current structure. If the structure or protocol or something changes, then that's not too bad for anyone using a well written piece of Free Software. If you're using a proprietary program to display it then you're knackered and I hope you've learned a valuable lesson.

Now let's look at the recent Facebook change. Can I access Facebook's database via a well defined and structured interface? Can I bollocks. That means I'm stuck with whatever the almighty Facebook deities bestow upon me, and I'd better pray that I like it because it's all they allow me. Thank fuck I don't use it.

For those of you who haven't realised it by now I am talking about the Semantic Web and the Model View Controller architecture. In the World Wide Web the stuff that gets passed around is HTML. That HTML can contain any data, is layed out in a certain way and the structure is very freeform, as long as it meets a few rules defined in the HTML and XHTML standards. The Semantic Web is different. In the Semantic Web the data is structured in a very specific way, in RDF triples to be precise. There is NO layout in the Semantic Web, since it is not about anything visual like pages, it is about *concepts* and *meaning*. Applications you use which can access the Semantic Web (there are as many as people can create, rather than the Web's singleton the Web Browser) can do whatever the hell they like with the structured information they receive. There's no arguments about the layout and look of a semantic Facebook because there's NO SUCH THING as the "layout" or "look" of anything on the Semantic Web. The layout and look are ENTIRELY up to the user and which program they decide to view it with. Some users may even view it with applications they access via the World Wide Web.

PS: I would just like to point out the first sentence of Wikipedia's World Wide Web article:

"The World Wide Web (commonly shortened to the Web) is a system of interlinked hypertext documents accessed via the Internet." Thank you.

Services, integration, communication and standards

2008-09-07T19:23:00.004+01:00

These days it is possible to do pretty much anything over the Internet. There's eBay, online banking, PayPal, Flickr, OpenStreetMap, OpenDesktop, Email, chat, forums, Wikis, Facebook, scrobbling, blogs, etc. The big problem, in my mind, is that of technological walled gardens.

A walled garden is an area which cannot be accessed without permission, usually by registering some form of account. Facebook is a classic example of a walled garden. Walls are useful, since having everyone's bank accounts available without restriction would be a problem to say the least. A technological walled garden would be an enclosed, restricted area which can only be accessed via certain technological means. Technological walled gardens are often simpler to implement than open systems, but often the reason the garden operator does this is because they see this as a way to run a dot-com or Web-2.0 business.

Let's take an example, Yahoo! Mail, Windows Live Mail and Gmail, which are all walled gardens in the classical sense, an account is needed and the login details must be provided in order to access anything. The first two, however, are also technological walled gardens: whilst mechanisms to send, retrieve, check and manage email have been around for decades, from "get my mail" (POP3) and "send my mail" (SMTP) to more sophisticated "synchronise this lot of email with that lot" (IMAP) and are well defined, standardised, understood and implemented, in order to access Yahoo! Mail or Windows Live Mail you still need to log in via their website because they don't use any of these standards. Gmail supports them, which is how I can use Evolution and Kmail to manage my Gmail account. Yahoo and Microsoft specifically disable them (I know Yahoo used to allow POP3 and SMTP access, when they stopped I moved away from them) with the reasoning that Evolution and Kmail don't display adverts, whereas their websites do. Here interoperability and standardisation desired by customers (if it wasn't used then there's no point disabling it, since nobody would be unexposed to adverts and the POP/SMTP/IMAP server load would be zero) is sacrificed in order to force adverts onto users who don't want them. This of course doesn't even touch upon the flexibility of using an email client (screen readers and other accessibility for the disabled, offline access, complete choice of interface (including Web), etc.).

That is the major reason why I refuse to join Facebook, MySpace, etc. I cannot buy or download Facebook's software and run it on my own machine,and even if I managed to write my own there would be no way to make it talk to Facebook's own servers. Since the entire point of Facebook is the stuff in their database, this would make my software useless. Hence Facebook have created a technological walled garden: If I joined Facebook then I would be sending any data I entered into a blackhole as far as accessing it on my terms is concerned.

Last.fm is better, since although their server/database software is a trade secret (as far as I can tell), the Audio Scrobbler system they use to gather data is completely documented and has many implementations, many of which are Free Software (including the official player). The contents of their database is also available, and doesn't even require an account (I have tried to think of ways to submit similar artists without an account, such as submitting two tracks at a time and building the data from that, but I suppose spam would be too much of a problem). Only the artist recommendations/similarity, tags and thingsare available, but that's the entire reason I use it, fuck the site with all of its Flash, poor social networking, confusing messaging system and stuff, that's all fluff around the periphery of the useful information. Essentially last.fm is like Gmail: I can't get the code which runs it, but I can get my data in and out in standardised ways which can be implemented with Free Software. I could make my own server which synchronises with with their database via the available protocols, and thus get out everything that I put in.

Now, the issue of synchronisation is interesting. How do you keep two things synchronised? There are a few different approaches and each has its place:

Known, unchanging, unmoving data

Here HTML can be used, ie. a web page. This is fine for people, and for applications needing that data it can simply be copied into the application once. An example would be an "about" page.

Unknown, unchanging, unmoving data

Here HTML can still be used, but since the data is not know beforehand it can be hard for an application to get anything useful from it. RDFa can be used inside the HTML to label each piece of information, thus an application only needs to be told what to find and it will look through the labels until it does, regardless of page structure, layout, etc. An example would be a scientific paper.

Changing data which is accessed once at a time

Here RSS or ATOM can be used. This allows changes to be specified in the file. ATOM is a standard, but RSS is a dialect of RDF which means labelled data is possible. An example would be a changelog.

Changing data which is accessed on every change

Here XMPP PubSub can be used. This means that there is no checking for updates since the source will push any changes out to subscribers when they are made. This doesn't use a file, it uses a stream. This is what my library is designed to accomplish. An example would be a blog.

Two-way communication and instruction execution

Here systems such as JOLIE can be used, overlaying protocols like SOAP. This can be used for dynamically generated data like database queries and searches, as well as for sending instructions such as "Approve Payment". An example would be a shop.

Notice that the first technology, HTML, is the only one which needs a Web browser to access. RDFa, ATOM and RSS are all structured in a way that allows applications to handle them directly, no human is needed and thus many more possibilities are available. XMPP can also be structured, since RDF, ATOM and RSS can all be sent over XMPP, allowing machines to handle the data, but doing so in an as-needed basis which makes things more scalable. JOLIE covers a range of protocols which are all inerently machine-focused, they are executing instructions. This might be a "buy this laptop" instruction when a button is pressed, or a "search for this" instruction when a query is entered.

These technologies allow data and communication to break free of implementation and visualisation. The next Facebook doesn't have to be a centralised Web site, it can be a distributed system with many servers run by different people interacting with each other to allow a scalable, unowned network, like the Web but made of pure information without the overhead of layout, styles, widgets or interfaces. This is called the Semantic Web. All of the visualisation, interface and style can be swappable and implemented where it is wanted, for instance as desktop applications on user's machines, or as Web sites running on various servers. There is no reason why, in an interconnected world, I should have to visit Facebook.com in order to interact with Facebook.

Except, of course, that Facebook wants to force unwanted adverts onto their customers.

NOTE TO SELF

2008-09-07T01:34:00.002+01:00

When trying to communicate from a machine to itself, for example trying to run the ejabberd server, it is a good idea to have a loopback network interface. Spent over a week trying to hunt that issue down, now I can finally get back to working on my library :D

Physics + Programming = Pretty

2008-09-05T23:16:00.005+01:00

Whilst looking for a better-than-mine Python implementation of attractive-and-repulsive-based-on-the-inverse-square-law particle simulation I came across this, which is basically a really simple model of gravity. You tell it how many balls you want it to start with, which are then placed at random points on the screen with zero momentum and a mass of 4. Then the simulation starts, running one time step of the simulation and redrawing the screen, then repeating this indefinitely. Particles which collide coalesce into a single particle with the combined mass and momentum of the original. This results in one of three things happening, either all of the masses coalesce into a big, stationary ball (since the net momentum is zero, due to the law of conservation of momentum), two or more masses form a somewhat stable orbit around each other, or one or masses hit the edge of the window during the simulation and 'reflect' (the vector of their velocity perpendicular to the edge is reversed) which breaks the physical simulation by violating conservation of momentum. After this third scenario all hell can break loose, usually resulting in everything coalescing into a huge ball, moving with momentum twice the magnitude of that which was flipped by hitting the wall, and opposite in direction.

Anyway, I looked through the short source file and had a bit of a play. Eventually I gave particles a colour which changes subtley every time they are drawn. I also disabled the old-frame-removing screen fill, allowing each frame of the animation to build upon the previous and create a trail. A little simple colour-cycle logic and I the following patterns appeared to my delight :D

HERE'S THE SOURCE (not properly licensed due to original author. Let's say you can treat is as Public Domain to save complications of licenses)