Higher Order Messaging backgrounded

Piers Cawley talks about RSpec's use of HOM:

It is, however, encouraging to see initiatives like Rspec which, through judicious use of higher order messages enables a much more fluent environment for writing tests:

I think that's the first time I've seen HOM used to explain something else, rather than being the object of attention itself. So HOM is starting to be seen as simply a part of the computing landscape, at least by some. Cool. HOM was never conceived of as an interesting thing by itself but rather as a (meta-)building block for building more expressive computational forms. RSpec looks exactly like one of those cool things HOM enables that I would never have come up with myself. I look forward to seeing more.

Not just high performance Objective-C

Addendum to my article on implementing a high performance Postscript interpreter in Objective-C: not just is performance better, so is accuracy. Despite the fact that we are optimizing the heck out of the Objective-C objects we are using, they still give us encapsulation and polymorphism, allowing us to choose arbitrary representations. For example, most Postscript interpreters use a fixed-size value object (polymorphic in a C-union type of way) that constraints floating point precision to 32 bits. With Objective-C, we have no such constraints, so EGOS floats are actually 64 bit doubles, so running the modified benchmark below in PostView doesn't just yield the result 75% faster than Preview, it also produces it with 7 orders of magnitude less error. Not that that is necessarily important in Postscript, but it is a pleasant side effect and shows the power of combining performance with abstraction.

%!
  usertime
  1000 0 1 10000000 { pop 0.0001 sub  } bind for
  exch usertime exch sub dup ==
  20 20 moveto /Times-Roman 24 selectfont
  100 string cvs show ( ms) show ( error:  ) show 
  1000.0 div 100.0 mul abs  100 string cvs show ( %) show
  showpage

Better HOM selects

Wincent Colaiuta discusses a variant of the select HOM that takes an arbitrary number of argument messages. I like it!

My initial implementation actually had arbitrary nesting, but as he discusses with collect, that requires a trigger message to start, as there is no way of knowing at runtime when the expression terminates. It never occurred to me that this limitation did not apply to select, which can look at the return type of the messages sent and stop when it reaches a BOOL (char).

Nice.

p.s.: the arbitrary nesting is still in the implementation, with each of the collection processing HOMs actually running an enumerator and those enumerators stackable, and this is two of the reasons the implementation is so gnarly: (1) there is extra generality that is not needed and (2) making that more general mechanism run fast was really, really tricky.

p.p.s: He actually discussed it almost a year ago, but I just saw it now.

Reading Helps

James Robertson slams the proposal by the EU free market institute to unbundle the OS from PCs sold in the EU.

I've seen a lot of stupid ideas float past, but this one from the EU's Globalization Institute makes it into the top 5 - only the existence of the RIAA and the MPAA prevent a complete victory for these morons:

[..] The think tank recommended to the EU that all computers be sold without an operating system and sees no reason "why computer operating systems could not follow the same model as computer hard drives and processors."

Yes, installing an OS from scratch is exactly what most buyers long to do - it's such a productive use of their time.

Hmmm, what could they mean with the "same model as computer hard drives and processors"?

Well, of course! We all buy processors and hard drives separately, mount the CPU on our separately purchased motherboard, hook up hard-drive and power-supply and stick it all in a chassis. That *must* be what they meant with that phrase.

Or maybe, they meant that you can configure your computer with different CPUs and hard drives, and have the vendor ship you a machine configured to your specifications, whereas you cannot actually get a computer and not pay the Microsoft tax? Nah, that's just *crazy*:

IT professionals are being forced to adopt Microsoft's operating systems — even if they tell their PC supplier they want a system free of Microsoft software, ZDNet UK's research has revealed.

Oh.

'Thousands' or transistor²

The Alan Kay quote in my previous post made me think of Montecito, the new Itanic version with 1.72 billion transistors. Compare that to the ARM6, which had a measly 35K transistors, including its 4K cache.

Dividing the two numbers gets you almost 50K. That's how many ARM6 CPUs you could get on the same chip with the same transistor budget as the Montecito. A processor for every object. Or viewed another way, more ARM6-equivalents than the ARM6 has transistors. Which begs the question: is the Montecito proportionally as much an improvement in computational capacity as an ARM6 is over a single transistor?

Objective-C future(s)

Via LtU, I got alerted to the fact that theEtoile project now has an implementation of futures. Cool.

However, their implementation has specific objects reacting asynchronously to messages, making it more similar to the actor model,which as they mention is also very much Alan Kay's original conceptual model for Smalltalk:

Bob Barton, the main designer of the B5000 and a professor at Utah had said in one of his talks a few days earlier: "The basic principle of recursive design is to make the parts have the same power as the whole." For the first time I thought of the whole as the entire computer and wondered why anyone would want to divide it up into weaker things called data structures and procedures. Why not divide it up into little computers, as time sharing was starting to? But not in dozens. Why not thousands of them, each simulating a useful structure? [Emphasis mine]

Actors are inherently asynchronous, each actor runs in a separate process/thread and messages arealso asynchronous, with the sender not waiting for the message to be delivered or ever gettinga return value. Of course the actor model also makes all objects active, so the Etoile model, whichonly makes objects of specific classes active, is somewhere inbetween.

Futures, on the other hand, as introduced in MULTLSIP (pdf), tryto integrate asynchronous execution into a traditional call/return control- and data-flow. So messages(or functions in MULTILSIP) appear to have normal synchronous semantics and immediately yielda return value, but when annotated with the future keyword execution of that return valueis done in a background thread and the immediate return value is just a proxy for the value that is still being computed.

In the HOM paper (pdf) presented at OOPSLA 2005, I also describe a Future implementationbased on Higher Order Messaging that comes very close to the way it was done in MULTILSIP. A -futureHOM is all that is needed to indicate that you would like a result computed in a background thread:

  result = [anObject lengthyOperation:parameter];           //  synchronous
  result = [[anObject future] lengthyOperation:parameter];  //  asynchronous with future

I am probably biased, but this seems about as easy-to-use as possible,with all the nasty machinery (worker-queues, lockless FIFOs, etc.)hidden behind a single -future message.

Message-oriented persistence

The good folks at Omni posted an interesting discussion of their persistence strategy for OmniFocus. In short they found that using a database, specifically a CoreData data store, was not exactly ideal for their primary public data format.

Instead, they appear to be using a pattern that Martin Fowler calls EventPoster. After reading David Reed's thesis, I think I prefer to call it message-oriented persistence.

I first stumbled on this pattern when designing a replacement for a feed processor at the BBC. The basic task was to process a feed of information snippets encoded as XML and generate/update web and interactive TV (Ceefax) pages.

Like a good little enterprise architect, and similar to the existing system, I had originally planned to use a central SQL database for storage, though designing a data model for that was proving difficult due to the highly irregular nature of the feed data. As an auditing/logging measure, I also wanted to keep a copy of the incoming feed data, so when the time came to do the first implementation spikes, I decided we would implemented the display, update and XML feed processing logic, but not the datastore. Instead, we would just re-play the feed data from the log we had kept.

This worked so well that we never got around to implementing the central database.

Leaving out the database vastly simplified both our code-base and the deployed system, which I could run in its entirety on my 12" AlBook whereas the system we were replacing ran around a dozen networked machines. Apart from making us popular with our sysadmin team both in terms of reliability and deployment/maintenance complexity (essentially a jar and a working directory was all it needed), a fringe benefit was being able to work on the system on said AlBook while disconnected from the network, working from home or from a sunny patch of grass outside the office.

In addition to personal happiness, systen performance was also positively affected: since we kept our working state completely in memory, the AlBook mentioned outperformed the original cluster by 2-3 orders of magnitude, producing hundreds of pages per second versus taking from several seconds to several minutes to produce a single page.

Performance and simplicity are exactly the benefits claimed for prevlayer, a persistence layer for Java based on the same principles.

TeaTime, the theoretical foundation and actual engine working underneath Croquet, takes this idea to a whole different level: objects do not have state, but are simply names for message histories. This is truly "objects [and messages] all the way down". Turtles need not apply.