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.
(more...)
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.
(more...)
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?
(more...)
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 
Back in 2004 I jotted some notes on requirements for IRON types.
Since then I've been drifting somewhat towards looser typing, in the Lisp model; having that as the underlying system provides for more expressive programming power, while optional type declarations as assertions, where required, can bring back the statically checkable safety and runtime efficiency of a strict type system.
But that's not what I'm posting about in the current insomniac haze - I've been thinking about written syntax.
IRON is a data model for values. Although I'm still deciding how the mutable data structures like queues fit into things (specifications of them are definitely needed for TUNGSTEN, but whether they count as part of IRON or not is something I'm still debating), I think I may have settled on a basic syntax for written values.
Now, the key requirement here is that IRON is, in the manner of S-expressions, usable to express just about anything - from source code to boring data. Creating a written data syntax that's pleasant enough to use day in and day out is quite a challenge. s-expressions come pretty close, but are deficient in a few areas. YAML is pretty good, but I wouldn't want to write source code in it.
The main thing I'm adding over s-expressions is Smalltalk-like syntax, which I will explain in detail below.
So, without further ado, here's a basic IRON syntax.
(more...)
