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 »

Learning new programming languages (by alaric)

I program computers for a living, mainly. This involves writing programs - instructions for the computer on how to do things, written in a "programming language".

There's a lot of programming languages out there; mainly because it's easy to create new ones, and an interesting exercise to do so. But if you browse a programming jobs site, you will see a lot of people who say "I am a Java programmer". Or PHP or Perl or C# or C++ or Python or Visual Basic. This means two things: that a few programming languages hold the majority of the "market share" and that people consider "their language" an important part of their identity.

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 🙂

A syntax for IRON (by alaric)

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.

Read more »