Apps as containers (by alaric)

As I have mentioned before, it annoys me that many applications try (subtly or otherwise) to appear as the 'containers' of your data; they are both editors of a particular type of object, and a browsing/management interface for that type of object. The insidiously widespread case being applications that have 'Open' and 'Save As' menu items that pop up mini filesystem browsers, only showing the types of documents that application cares about and hiding others.

Read more »

Replicated data (by alaric)

The project I'm currently working on is to build a replicated database; and, of course, this gets me thinking about TUNGSTEN, my own replicated database design.

Now, a fully-replicated database like the one I'm writing works by multicasting write operations to every node, so that each node has a copy of the entire database. This means that you can increase your read capacity by just adding more nodes and spreading the work between them. Each node can read its local database independently of the others, so there's no inherent limit to how many reads the cluster as a whole can do in one second. As long as you have unbounded money and space to keep adding more nodes.

However, since writes get multicast to every node, there comes a point at which your write load is the highest the weakest node in the system can keep up with. Adding more nodes doesn't help, since every write still happens on every node. The cluster as a whole has a maximum write capacity, regardless of the number of nodes.

So this system will do for now, but the next big bit of work on it will be to increase the write capacity - by partitioning the data set.

Read more »

Garbage collection (by alaric)

I read this paper shortly after it came out:

One Pass Real-Time Generational Mark-Sweep Garbage Collection

However, I've spent ages since trying to find it again. Mainly due to confusing it with The Treadmill: Real-Time Garbage Collection Without Motion Sickness, which describes a somewhat related algorithm that uses a read barrier to support mutation.

The algorithm described in the first paper is pretty amazing. It's simple, effective, fast, real-time, and requires no read barrier. The downside, however, is that it requires that pointers only ever point back in time to older objects. Which is fine if you have a purely functional language, since an object being created can only ever obtain references to objects that already exist at creation, and those references can never be updated to point to a newer object thereafter. However, you cannot then use any optimisations that use mutation "under the hood" such as in-place update of linear values.

Read more »

Source Transformation for Fun and Profit (by alaric)

Back when I was a kid, I designed a low-level macro system for purely functional Lispy languages, based around a cunning use of partial evaluation. I called it meta.

Since I was a dreadfully lazy student, when I had to do a final year project, I suggested it as an idea and then pretended to think of and develop it all over again, before spending far too little time writing up a report on it, and a sample implementation. Which may have been why the sample implementation broke in the demonstration...

But at the time, I didn't think much of macro hygiene. All I'd seen of it was that Scheme at the time had a hygienic macro system called syntax-rules that, as far as I could tell, sucked - it was limited to basic-seeming rule-based substitutions, and did not use the full power of the Scheme language as a macro language.

However, things have changed since then. The Scheme community has come up with hygienic macro systems that let you write macros in Scheme, such as syntactic closures. And so I've found that hygiene is a desirable property, rather than a terrible design tradeoff.

So, I wonder to myself, can my meta macro system be brought up to date and incorporate hygiene?

Read more »

Structured Streams (by alaric)

I read this today:

Structured Streams

It looks like somebody's implemented a stream protocol that lets you create substreams at will, sharing congestion control information with the parent stream but having their own redelivery queues, so missing messages will only stall the one (ordered) stream they pertain to.

Good to see that great minds think alike. When I get some time, I'll read their results in more detail, and see if there's anything useful to be learnt for MERCURY 🙂