Communication & Cooperation

My final project for grad OS is done and we came up with a preliminary design for, Matrioshka, a kernel written in Haskell. When I say preliminary, I mean extremely preliminary and not even to the level of a formal specification of the kernel.

My life-goals now consist of three things: continue working on Matrioshka and getting an implementation of it done in House, improving my general category-fu, and studying all the math under the sun.

I'll be putting up my own thoughts about Matrioshka as time goes on.

Ill Communication

So last night I was doing a bit of thinking about how to write my own mud client. I love muds and always have. I think they're incredibly fun, despite not having any real graphics.

In any case, I started thinking about "what is the algebraic structure of communication?". In other words, if we have a server and its clients what is the proper mathematical structure that represents this communication. I guess this is connected to pi-calculus, but I'm not sure if that's exactly what I want. Ideally I want some category theoretic structure that can describe the evolution and interactions of such a system.

Inherent Flaws

Even though I haven't spent as much time as I would have liked thinking about it, I have a feeling that my ideas on trying to connect arrows and resumptions just really aren't going anywhere special. Part of the problem is that resumptions inherently signify breaking points within the process. Now, I had been somewhat naively thinking that the connections between arrows could provide these breaking points as well but that doesn't really work. Arrows are connected with combinators, and once connected there is no way to break them apart again. In general, there can be more than one set of functions that can be composed to make a given function.For example, there's obviously an infinite number of pairs of functions over the integers that can be composed to give (\x -> x+4).

Of course, that does make me wonder what a category would look like if every morphism that was composed of two other morphisms had a unique decomposition.

Resumptions & Arrows

So I've been doing a bit of reading of the paper Cheap (But Functional) Threads and I can't help but wonder how this paper and its Resumption monads might connect to Functional Reactive Programming. Essentially, the mapping I see is that a graph of arrows should corresond to the set of resumptions in the system. My brain is still very fuzzy on this point, so I need to write up some notes making the correspondence truly explicit. I'm not sure what good this correspondence might give, but I'm willing to bet good money that recasting this paper in terms of arrows might actually give greater power.

Capabilities in Pure Functional Operating Systems

This is the topic to which I have been putting all my, albeit limited, brain power.
Capabilities are a very elegant way to handle security, where every resource corresponds to some key that denotes access rights and the keys are passed to and between user processes.
In some older systems, capabilities are essentially just pointers with some extra information attached to them. That model doesn't really fit well into the natural style of functional programming so instead we'll be using static capabilities as outlined in this paper.

As much as I find the Lightweight Static Capabilities paper inspiring, one problem it doesn't tackle is revocation. To push the analogy further, one must be able to change the locks after one has given out the keys. My group's tenative solution to this is to keep a list of capabilities associated with each process which are to be passed in as parameters in the construction of an action. When a system call occurs, a continuation of the running program is to be stored along with this list of the capabilities passed to it the last time it was started. Revocation will occur when a process that has the proper authority to revoke names the process who is going to lose access and provide the capability that is to be revoked. The kernel will then remove this capability from the list associated with the process and when the process is restarted it will be rebuilt with its modified list of capabilities.

This is of course a very tenative design, with most of our ideas based upon the House system and the related work on the OSker kernel.

Updates

So I worked for about a month designed my mud system, wrote probably close to a hundred pages of scattered notes that I've wanted to turn into a design document, initiated a project to design and code up a japanese style rpg by the end of next summer, got hired by Epic Systems, arranged to get a Master's degree, and started working on a project for graduate operating systems that involves hacking on a Haskell microkernel.

A proper grammar

So one of the first big design decisions is a choice of grammar accepted by the IF system.

I think there are a series of fairly simple rules that could be used as a guide.

1: All acceptable sentences should begin with a verb.
2a: Multiple verbs can only be used if there exists an and in the sentence.
2b: Clauses joined by the and statement must also be valid sentences.
3: Uses of at, in, on, etc. should be optional. The only thing that determines the action is the order of the nouns.
4: In MateriaMagica style, constructs such as n.thing should be allowed to refer to the n'th such object that matches the 'thing' keyword. all.thing should refer to all such objects.

Now this is at least a start, but doesn't address things such as anaphorisms. I'd ultimately like to be able to properly process sentences to the point of sounding very natural. There may need to be some "guessing" in some cases to try and determine likely meaning. Those should just be extensions though built upon a good, solid basis though so I'm more concerned with following that first series of rules.

I think the parser will be the first thing I worry about writing, so I'll probably update this blog with code snippets as I write them.

New Project

So having been rather busy this past month with my research, I've neglected to spend much time on hobby and vice.

I do, however, have project I'm working on fairly seriously: writing my own interactive fiction/mud building system. The two are similar in terms of being text based games, but I think the mud building system will definately be more difficult because it will have to deal with multiple players. As such I'm starting with the basics of an interactive fiction system.

First off, I'm not sure if I'm a huge fan of the Inform7 style "natural language" programming style. I think Inform 7 is pretty cool in general though, and I doubt I could make a better IDE for writing interactive fiction.

Now, partly I want to do this just because I can, but there are some things that I think would be very cool to include in a text-based game system that I don't think really exist yet.

First, I think it'd be really nice to be able to extend the language of the game. In other words, I want to be able to type "to blah is to blech" and have typing blah do the sequence of commands that I defined. Now, you can do that kindof thing pretty easily with mud clients such as Zmud, but I'd like it to be something that feels like a part of the world.

An extension of this idea leads to something I think is *really neat*: an extensible magic system. One can define their own spells with different attributes, given some form of spending system that allows one to define spells up to a certain complexity and effectiveness. Basically, I think it would be somewhat similar to the magic system of the table-top game Mage, though not quite as open ended just by necessity.

Of course a refinable magic system probably opens itself to tweaking and gameplay breakage the likes of which Vass has never seen, but honestly I would really want to try and make it anyway.

My plan is probably to write the system in Common Lisp. Haskell is so pretty, but things like this would probably be rather kludgy. I need to have names associated with functions, the ability to call these functions from parsing strings, these functions need to be able to take any number of arguments and need to be able to be extended in a dynamic fashion. In order to do that in Haskell I'd need to define things such as

>data Action = Unary Name (State World String) | Binary Name (Obj -> State World String) ...
>instance Show Action where
> show (Unary n _) = n
> show (Binary n _) = n
> ...

That seems really ugly, and to be honest is a hack to get around the fact that I need to futz with the type system in order to get the concept of "actions" that I want. I may play with it a little, but if it gets too messy I'll drop it like it's hot. The main reason for trying to do it in Haskell is because I do have alot of faith in the powers of the GHC compiler.

Research

So I'm now in week two of my new research job.
I'm working on perturbative QCD and numeric techniques for doing loop amplitudes.

I prefer non-perturbative QCD or heavy ion physics as fields, but this is actually some novel and interesting work. I actually see a definite potential for formal methods of CS to help with evaluating quantities in field theory.

At some point I'd love to work a little on a haskell mini-pythia or perhaps a version of madgraph that lazily generates all possible feynman diagrams.