Tuesday 27 April 2010

(Anti)Object-oriented reasoning

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

Monday 12 April 2010

The Web as an Oracle

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

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.

Thursday 8 April 2010

Publicly whoring onesself out for politics

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


Wednesday 7 April 2010

My Current Browser Tabs

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


Thursday 1 April 2010

Twilight: New Moon

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

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.