Moving

This blog is defunct. It's content, along with that of my other blogs, is now hosted at thomas-sutton.id.au.

Writing and Ownership

My thesis was due last Friday (delayed to last Monady) and I have an extension (or, rather, an I-don't-have-it-done) until today. Unfortunately, it doesn't look like I'll have it done by my deadline today either. For some reason, I just haven't wanted, or been able to, write.

I think that this is due, in part, to the fact that this is my own project (rather than the one I originally started on) which I'd been thinking about for a while before I started my Honours year. As such, I don't feel any sort of obligation to work on it for any purposes other than my own gratification. While this is a good thing by some measures (it's a project that I am interested in, etc., etc.) it is very, very, bad by others (like that fact that I don't feel any particular drive to write about it).

All I know is that I'm well and truly sick of University and computer science. If Honours is a taste of research and a hint of what a Ph.D. is like, then I want nothing to do with either. This used to be fun...

Relational Algebra in Haskell

I've just spoken to Jon about the problems and ideas I have posted about previously. One of the things I came away with is the suggestion that I might be thinking about relational algebras (perhaps an algebra over a set) rather than hypergraphs. I'm not entirely sure that this is the case (the "hypergraph" Wikipedia article above seems to describe what I'm thinking of), but the "algebra over a set" article is certainly applicable as well).

As a result, I've been able to dig up a couple of things that look like they might help me implement support for generic frames (i.e. those with an arbitrary number of n-relations for arbitrary values of n greater than 0).

While I've seen A Relational Algebra Simulator in Haskell before, it didn't occur to me that it might be applicable to my problem. RATH - Relation Algebra Tools in Haskell, however is new to me and looks like it provides a complete library (rather than the example program of the first link).

Whether I have enough time to catch up on my course-work, finish my system (as it stands), write a thesis and learn enough about this topic to extend the system using such a generalisation remains to be seen.

Another possibly useful generalisation might be to extend the concept of "relation" from sets of tuples to mutisets (or bags) of tuples, thereby allowing relations in a frame to be mutigraphs (i.e. graphs allowing multiple edges between a given pair of vertices). The Data.Graph.Inductive library supports labelled edges which suggests that it might also support multigraphs to some degree (if edges with non-identical labels are non-identical, then you can simulate an unlabelled multigraph by labelled each edge with an index).

I'd like to write a generic graph library with support for multigraphs and [uniform] hypergraphs, possibly by extending Data.Graph.Inductive, but this will probably wind up being pushed back until the Christmas break.

Modal Logic Wikipedia Articles

I've been poking at Wikipedia again (I dislike free time) and decided that a list of articles relevant to modal logic might be useful. To that end, I present a partial list of Wikipedia articles:

• Kripke Semantics
• Modal Logic
• Temporal Logic
• Proof Theory
• Model Theory
• Analytic Tableaux

In addition to the articles above (which aren't really directly relevent to my work), there are a number of articles that I've found useful in trying to puzzle my way through things. A partial list of these useful articles is:

• Hypergraph
• Multigraph
• Power set
• Algebra over a set

More articles will be added to this list as they are uncovered.

Annoyances of the Feature Kind

Yesterday, I finally sat down and wrote a priority queue (a heap to those in the know) to store the formulae on a branch that still need to be processed. Chris Okasaki (in his book Purely Functional Data Structures) defines the interface of a heap as follows:

class Heap h where empty :: (Ord a) => h a
isEmpty :: (Ord a) => h a -> Bool

insert :: (Ord a) => a -> h a -> h a
merge :: (Ord a) => h a -> h a -> h a

findMin :: (Ord a) => h a -> a
deleteMin :: (Ord a) => h a -> h a


This is a problem (in my opinion) in that it requires that heaps (all heaps) be over ordered data-types. The entire reason that I am attempting to extend the heap is to remove the ordering from the contained type, and use a priority type instead. Thus we are no longer saying that, for example, α < β but that (priority α) < (priority β)

I'll be the first to admit that this isn't much of a distinction to make (especially from a pragmatic "programmer" point of view), but it is a nicer approach.

I got around this problem, such as it is, by modifying my Prioritised class to have a function to inject values into my Priority type and one to extract them. The heap then is a type synonym:type PriorityHeap t = LeftistHeap (Priority t) with the restriction that you need to explicitly wrap values you insert into a heap:let h' = insert (priority v) h in ... and unwrap those you get out: let v = value $ findMin h' in ...

Not terribly inconvenient, but not ideal. I'm fairly sure that this could be solved with some functional dependancies magic, but the current state of affairs is good enough to be getting on with.

Purely Functional Data Structures

The Haskell code from Purely Functional Data Structures by Chris Okasaki can be found as his web-site at the United States Military Academy.

RSChem is Burning Down, Burning Down, Burning Down...

RSChem is currently on fire. There haven't been any reported injuries, but they have evacuated that precinct of the campus.

Hmmm.

The presentation is over and done with. It didn't go too badly, though I did run under-time: I finished my presentation and asked (begged) for questions half way through my time slot. I'm not sure how much of it the audience caught, or what sort of comments the assessing academics will give me, but I'm reasonable happy with my performance.

Having seen all of the presentations, I find myself wondering at how many of the projects involve writing compilers and optimisers. One is attempting to learn tests to avoid computing expensive functions unless they're required (with collision detection as the experimental framework). Another is doing something with symbolic optimisation of robot dynamics (which looks a lot like single static assignment). I'm compiling a DSL to Haskell. Someone else is experimenting with interval arithmetic (which I want to implement in Haskell) for scientific computations.

Presentations...

I have to give my mid-term seminar tomorrow afternoon and I'm getting rather nervous about it.

My supervisor has told me that my slides aren't accessible enough (i.e. I require too much prior knowledge), but I can't see any way to simplify things or remove content without missing important things. I'm not happy, but I don't the time fine-tune it any more.

If you're at the ANU (I'm not sure if the public is allowed) and free tomorrow at 1:00 (my presentation is at 1:26), come along to the Department of Computer Science seminar room (N101) and watch me embarrass myself.

Stupidity or How Dumb Can I Get

I've just been trying to install hs-plugins on my iBook with GHC 6.4. Sorting out the dependancies, getting stuff to build and getting the libraries installed has been ridiculously complex.

Now that I've got it built and installed (part of which required using hugs because runghc refused to run the setup programme), it doesn't appear to have registered the package, which means I need to manually provide the details to GHC every time I compile some code using System.Plugins (rather than just tell the compiler to use the package: -package plugins).

I need to figure out what it going wrong with my environment and fix it. Perhaps by tearing some capabilities out...

Update: I've got that problem fixed (make install doesn't appear to update the package database). Now all I need to do is work out a way to be able to specify the data-types in the plug-ins.