Congratulations, OLPC!

Today OLPC announced a partnership with Marvell to develop the XO-3. This is great news — according to my little birdies this will put development efforts at OLPC on substantially more solid financial footing. And software development for new tablet computers is non-trivial! Here's hoping that OLPC, which led the netbook movement, can similarly spur the nacent tablet computer market. So far tablets are seen as content consumers, with all "real" content creation (ie not just jotting notes or makng minor edits) being done on seperate "real" computers. OLPC's vision should insist on fully productive machines which allow kids to create and contribute, not just passively consume. (In particular, the killer app for kids on XO laptops to date is making movies and telling stories.)

In addition to funding further software development, the Marvell partnership ought to give OLPC the muscle to continue pushing forward the hardware state of the art. A lot of the reality of modern electronics manufacturing depends on guaranteeing enough production volume to sustain the interest of suppliers and their engineers. For low volumes you instead get "least effort" solutions from your partners, which result in higher costs and poorer results. So I'm cautiously optimistic that the "capture" of OLPC resources for Marvell's high volume "first world" tablet efforts will in the end be a means to accomplishing the XO-3 goals for "the rest". But care and caution are waranted. OLPC is not large enough to do multiple things at once; its resources and attention are dissipated easily.

Baker's (Square Dance Concepts)

In a previous post I introduced the "Baker's" square dance concept. By analogy to "Baker's dozen", it was proposed the "Baker's" meant to do 13/12 of the call it modified.

But let's reconsider: a "baker's half dozen" isn't 6 1/2 eggs, it's 7. Let's redefine the "Baker's" concept to mean "one more part" of the call. (Hence the title of this post: "one more square dance concept".)

So a "Baker's Square Thru" is a square thru 5. A "Baker's Eight Chain 3" is an eight chain 4. A "Baker's Right and Left Grand" goes 5 hands around. Note that this is different from "do the last part twice"; we continue the alternation of parts in the base call.

Let's push this a little further to include calls with arithmetic sequences. "Baker's Remake the Wave" would end with 4 quarters by the left. "Baker's Quarter Thru" would be a remake the wave. "Baker's Three Quarter Thru" is a reverse order remake.

Slightly more controversial: "Baker's Swing the Fractions" would end with zero quarters by the left (would that still set a roll direction?). "Baker's Touch By 1/4 By 1/2" from a single file column of 6 would have the very outsides touch 3/4. Sue Curtis suggests that "Baker's Reverse Echo As Couples Trade" (from a tidal one-faced line) would be "trade, as couples trade, as couples as couples trade", or equivalently "trade, couples trade, couples of 4 trade".

This definition for "Baker's" seems a lot more fun. Do any other square dance callers have concept-worthy last names?

SDR 0.6

Another holiday, another SDR release. Version 0.6 (now on github!) comes with definitions for almost all of the Mainstream square dance program, excepting thars, stars, and that pesky allemande left. The basic abstract syntax tree representation of calls has been refactored, building on a implicitly-typed expression representation — clearly we're approaching fulfillment of Greenspun's tenth rule. On the REPL front of this quest, SDR now includes PMSD, a text UI incorporating an interactive javascript context. The test case transcripts probably provide the best overview of its use.

The SDR web frontend now supports implemented bigon, hexagon, and octagon dancing. There's also a square resolver based on Dave Wilson's ocean wave method. Since the previous release, I've also reimplemented square breathing using the Cassowary constraint solver. Expanding the square to make space for inserted tandems, couples, etc is formulated as a linear programming problem, optimized so that the resulting formation is compact. Resolving overlaps is formulated as a mixed integer program, which allows for either-or constraints: if dancers overlap on both X and Y axes, either the X overlap must be resolved, or the Y overlap must be resolved, or the dancers have to form a star.

Although there's plenty of core engine work left to do, I've started to shift back to working on the game UI. Hooking the newly improved dance engine up with the Sphinx voice recognition engine, tuning the recognizer, and generally putting all the bits together is expected to be the focus of the next (0.7) release.

Chrome OS, litl, and OLPC

Well, Google just announced Chrome OS, to be available next Christmas. Some parts of it are very similar to what you can already put under the tree this Christmas from litl (actually, you can buy one right now) — and other parts are familiar from my time at OLPC. For example, the legacy-free BIOS and signed bootloader are what OLPC shipped two years ago on the XO-1. The XO-1 was not an "always connected" device, though — in fact the opposite: it assumed connectivity was infrequent and low-bandwidth. At OLPC, the signed code scheme was part of an theft-deterrence system, crucial for OLPC's target third-world deployments. It wasn't very popular among our first-world users, and I'm not actually sure why Google implemented it for Chrome OS. Phone company lock-in (due to largely misplaced concerns about maintaining the integrity of their networks) are why phone apps are locked down with signature schemes; this isn't necessary (and verges on Evil) for what's intended as a general-purpose computing device.

The somewhat oddly-technical (and often slightly-wrong) middle section of the Chrome OS presentation veered off at one point about filesystem partitions (!) and how having a read-only partition is a novel feature of their OS. Read-only partitions are one of the oldest security mechanisms — my boot floppy had the write-protect notch taped over back when I was booting DOS — and a near-universal feature of thin-client deployments (which Chrome OS certainly is). OLPC maintained a mostly-read-only root, but primarily to extend the lifetime of the flash disk (flash lifetime was not touched on in the Chrome OS presentation). Litl mounts a read-only root with a writable unionfs on top, which actually works much better in practice: improved maintainability because all the various Linux system daemons can still "do their thing" as they expect, but you can wipe the top partition whenever you like to return to a clean state (at litl we do this on every update). (If you haven't hacked the lower levels of a Linux distribution, you'd probably be surprised at how many system daemons assume they can write various places in the root partition, and you really don't want to maintain hacked versions of all of them.) Since ChromeOS gave an Ubuntu shout-out at one point, I strongly suspect the unionfs scheme is actually what they are doing as well — and, for that matter, what all the other Ubuntu Mobile downstreams are doing. Not new.

The emphasis on a read-only root partition is rather misleading from a security standpoint (as much of the middle portion of the presentation was). If you're not storing your files locally, it doesn't mean that you suddenly have no security concerns. It just means you have different security concerns. Cross-site scripting attacks give a malicious website access to your Google account through your web browser: these sorts of things are the malware for a WebOS. You have a different attack surface, but a vulnerability in your browser or flash plugin still gives access to private data. Mentioning that they encrypt the data on disk seems to be pure snake oil: your browser has access to the unencrypted data, and that's your most vulnerable surface anyway.

Overall, Chrome OS is a nice validation of some of the cloud-computing ideas we've been working on at litl, and it's always nice to see more legacy-free hardware (like the OLPC XO-1 and the litl webbook), but the presentation was oddly underwhelming. They're not really "reimagining the PC" — they're just removing all the applications on the PC except for Chrome. You still interact with "the PC" the same way you currently interact with Chrome. For reimagination, watch the videos at litl.

litl's technical secrets revealed!

Update: Lucas has written up some additional technical details — and he mentions our update system, which was one of the first bits I worked on when I arrived. We heavily dog-food the updater, using buildbot to push out the latest bits to developers every night.

Update 2: Welcome, slashdot! The videos at http://litl.com/support/ give a good idea of what the UI is like.

Update 3: Non-technical press coverage: Wired, WSJ, Xconomy, CrunchGear

Update 4: More words: dignacio on litl's server side, J5, twitter

litl launches today, so I can finally talk a bit about the cool technologies behind our software stack.

On the server side, litl is a cloud computer, built on Google App Engine, Amazon S3, and Django — all of which are fantastic technologies. All machine data is stored in the cloud, so you can have a gorilla stomp on your litl, pick up another one, log on and instantly recreate your environment. (Since we developers are always abusing our prototype hardware, we've tested this a lot!)

On the client side, the litl software (naturally, code-named "big") is built on gjs, which is the smallest possible wrapper around JavaScript necessary to make it a large-scale programming language. I've really enjoyed programming in JavaScript, which might seem odd to people who (a) have had frustrating experiences with global variables and crazy incompatibilites trying to make JavaScript work on the web, and (b) know that I'm a static types and compiler-bondage sort of guy. So I'll spend a little time here talking about gjs.

From a language standpoint gjs adds just one feature: a minimal module/namespacing mechanism built on a single top-level definition: the name "imports". Modules are imported using (typically constant) definitions, such as:

const StringUtil = imports.stringUtil;

s = StringUtil.sprintf("%d", 3);

The dynamic stringUtil property of the imports object is an object whose properties are the top-level definitions in the file stringUtil.js, found on the import path. Subdirectories are additional dot-separated components, as in Java package names; imports.util is a dynamic object representing modules found in a util directory on the path. You may need to compare this to the namespacing mechanism in the abandoned ES4 proposal to appreciate how small and elegant this is.

Further, this module system integrates with the GObject system via GObject introspection annotations for library code. This allows easy integration with libraries written in C or any other introspectable language. For example:

const Gtk = imports.gi.Gtk;
Gtk.init(0, null);

let w = new Gtk.Window({ type: Gtk.WindowType.TOPLEVEL });
w.connect('destroy', Gtk.main_quit );

let button = new Gtk.Button({ label: "Hello, world!" });
button.connect('clicked', function() { w.destroy(); } );
w.add(button);
w.show_all();

Gtk.main();

The gjs system is built on the SpiderMonkey JavaScript engine, the one used in Firefox, so JavaScript execution benefits from all the JIT and performance work done upstream. Further, it means that we can code in JavaScript 1.8, Mozilla's dialect of JavaScript with lots of bells and whistles (mostly borrowed from Python):

gjs> function range(n) { for (let i=0; i<n; i++) yield i; }
gjs> [i*2 for (i in range(5))]
0,2,4,6,8

(In a later post perhaps I'll describe how you can use the yield expression to build a continuation-based system for writing asynchronous callbacks for UI code in a natural manner.)

Overall, JavaScript as a system programming language feels a lot like Lisp must have for the programming generation before mine: minimal syntax, very powerful and orthogonal core abstractions, and (dare I say it) not much type-checking or busy-work to get in your way. (gjs is not a homage to Sussman, but it should be!) JavaScript is a programming language for those who know what they're doing and aren't afraid of a little functional abstraction. (Now if only there was a way to disable semicolon insertion!)

OK, enough about gjs. The litl software stack is based on Canonical's distribution of Ubuntu for mobile/embedded devices, and the Canonical folks have been great partners. It's been a joy to get changes integrated upstream, and Canonical has done a lot of excellent work accommodating their distribution to litl's unique needs. On the UI side, we use X11 and some GTK widgets, but implement our own (very simple) window manager. Most of the actual look and feel is done with Clutter (hardware-accelerated 3d animated effects, whee!), and we have a Flash-based API for external developers. We also have hardware-accelerated h.264 video.

Regardless of the technical fun, though, I have to say that the best thing about working at litl is its management: developing with all the other rockstars here is made the more fun by the knowledge that management will help ensure that our goals are realistic and that we'll be able to hit our targets, with time left over to polish before release. It's just much more fun to code when you know you'll be proud of the end result.

Echo^n Square Thru A(5)

[Square Dance primer for computer scientists: square dance calls are (recursive) sequences of basic actions: walk forward, turn around, do a square dance call. "U-turn back" is a square dance call, which means simply "turn around". Some calls take numeric arguments: "square thru N" for N=1 means "pull by"; "pull by" is another square dance call which is roughly "step past the person you're facing". For N>1, "square thru N" means "pull by, turn in, mirror square thru (N-1)". The word "mirror" in that definition is a square dance concept. It is a function which takes a square dance call and transforms it, yielding square dance calls or actions. "Mirror" means to simply do the call as if you were looking in a mirror, exchanging right and left. (If you've ever tried to comb your hair looking into the display from a webcam, which is not mirrored the way you expect it to, you know how hard it can be to do well-practiced actions mirror-wise. "Mirror" is a simple square dance concept.) So the definition of square thru N I gave above is recursive, defined in terms of a transformation of the call itself. The concept "twice" takes a call and merely means to repeat the call twice.

Concepts can take multiple arguments, including arguments which are themselves concepts, not just calls. (Some would call these supercalls or meta-concepts, but we'll gloss over this for now.) Which brings us to the subject of today's post: the ECHO concept.]

"ECHO <concept> <call>" means do <concept> <call> then do <call> — like you were hearing the last part of the phrase echoed back from a distance. So, "ECHO mirror square thru 4" means do a "mirror square thru 4" and then a "square thru 4". "Echo twice u-turn back" means u-turn back three times.

Most dancers have a bit of a formal grammar in their heads, something like:

call: <simple_call> | <concept> <call> | <metaconcept> <concept> <call> ;
simple_call: square thru <number> | u-turn back | pull by | ... ;
concept: mirror | twice | ... ;
metaconcept: echo | ... ;

Examples of valid utterances:
"mirror square thru 4", "echo mirror square thru 4", "echo twice u-turn back".
Some invalid utterances:
"square thru 4 mirror", "mirror square", "echo mirror".

Now here comes the fun part: how do you parse the expression "echo echo twice u-turn back"?

It doesn't parse according to the grammar above: you have to mentally curry an argument to make "echo twice" into a concept (since when provided with a concept the remaining part is a 'function taking a call', aka a concept). You end up with something like "echo (echo twice) u-turn back", which would mean, "echo twice u-turn back, u-turn back". Thus, "echo twice u-turn back" means do the u-turn back 3 times; "echo (echo twice) u-turn back" thus means to do the call 4 times, and "echo (echo (echo twice)) u-turn back" is 5 times. Adding another echo adds another u-turn back. Bo-ring.

Because we're adventurous types, let's throw the grammar out the window and treat echo as a simple macro-expander, which grabs the shortest possible phrase following it as its argument. Now we'll parse "echo echo twice u-turn back" as "echo (echo) twice u-turn back", that is, "echo twice u-turn back, twice u-turn back". That's 5 u-turn backs. The next one, "echo echo echo twice u-turn back" becomes "echo (echo) (echo (echo) twice u-turn back)", which is 8. Continuing, "echo (echo) (echo (echo) (echo twice u-turn back))" is 13. Adding more echos yields subsequent terms in the Fibonacci sequence. Now we're talking!

The sequence constructed above grows in duration as an exponential function of the length of the utterance, but we already know of another such construction: the humble "square thru N" also grows exponentially with its input, since the value of its numeric argument "999...9" is also exponential with the number of digits uttered. Let's say that the goal is to allow the square dance caller time to enjoy a nice beverage and sporting event on TV while the dancers work out the implications of a short call. Exponential is okay, but we could certainly do better.

Some readers might be aware of the "baker's function", which naturally involves multiplying everything by 13/12. One might imagine "Baker's Square Thru 6" called using this function as a concept; this is equivalent to "square thru 6 1/2 times". (Computer scientists: define "square thru 1/2" as "do the first half of a pull by" then you can continue using the recursive definition above.)

But, for packing the most dancing into the fewest words — super-exponentially! — I submit "Ackermann's Square Thru 5". (Use f(n)=A(n,n) as computer scientists do.) Guy Steele has suggested that the caller might use "Ackermann's Square Thru Your Couple Number", finish the tip calling for two couples, and then use three-couple figures for the rest of the night. Perfect for the lazy caller who wants to do 25% less.

(Credits: Justin Legakis discovered the Fibonacci connection. Guy Steele had most of the good ideas here. Bill Ackerman is the recipient of the eponymous super-exponential concept. I just wrote it all up.)

Flash Filesystems

Dave Woodhouse in a recent article calls shenanigans on hardware translation for flash devices. I agree: flash memory is a Horse Of A Different Color, and trying to gussy it up to look like a rotating disk of magnetized rust is using a bad and leaky abstraction that will only end in tears. But I don't think the engineers' better judgment will prevail: the use of hardware translation is driven by Windows/DOS compatibility concerns, since Microsoft (to my knowledge) has shown no desire in writing a new filesystem for flash drives. OLPC used a raw flash device in the XO-1, but in their follow-on had to switch to a hardware-translation device because market/scale economics were making those devices cheaper and cheaper while the original raw flash device was (a) not increasing in volume (aka, getting relatively more expensive), (b) not increasing in size (no one wanted to make new ones), and (c) getting discontinued (aka, impossible to buy). The best one can hope for is that a raw interface be offered in addition to the standard "Windows-compatible" one, for specialized embedded or high-performance applications — but the chicken and egg problem applies: until there are compelling gains, these interfaces won't be purchased in sufficient volumes to yield reasonable prices, and no one is writing the optimized filesystems because you can't find reasonably-priced flash devices to run them on. The end result is likely to be that Worse Is Better, and we'll be left with another set of legacy chains. Given enough time and transistors, the hardware may eventually grow Heroic Measures to work around the bad abstraction (see: the x86 instruction set).

If your filesystem is large enough and the amount of data being rewritten small enough, the flash problems "probably" won't bite you until after the obsolescence of the device — flash storage doesn't have to be good, it just has to be "not too bad" until, say, 3 years after purchase. Like non-removable rechargeable batteries that slowly degrade over time, you'll find your filesystem slowly degrading — one more reason to eventually buy a new one, and I've never known manufacturers to be especially sorry about that. Heroic Measures may never be needed/taken.

Leaving amateur market economics (and despair), let's revisit a cryptic and probably overlooked paragraph in my olpcfs proposal:

Implementations tuned for flash memory can use Adaptive Packed Memory Arrays for efficient CAS. This is an open research topic, but there is some evidence that a high-performance scalable flash-based filesystem can more profitably be implemented using cache-oblivious B-Trees and APMAs, rather than more "traditional" filesystem structures.

Here I'm trying to build a little bridge between filesystem designers and functional data structure researchers, two groups who probably rarely sit down together for a beer. I think Packed Memory Arrays are the "B-trees of flash filesystems": a better way to build an on-disk index given the peculiar characteristics of flash memory. Just as BeOS demonstrated that your filesystem could be "B-trees all the way down", I believe you could build a compelling filesystem using PMAs as the primary data structure. Ultimately, I suspect that the development strategy Dave Woodhouse describes — small incremental changes to existing filesystems whose philosophies are "close enough" — will probably prevail over a ground-up PMA rewrite. Incremental improvements and shared codebases are the Right Strategy for successful open source projects: you get more developers and testers for those parts which aren't flash-specific, and you've already gotten yourself out of the Cathedral with some working code to kick things off.

But if anyone's interested in attempting a clean slate design, PMAs are my advice. Maybe you'll come up with something so wonderful it will make a compelling book (and inspire folks like me), even if ultimately you don't win in the marketplace.

(But maybe you'll win! Flash storage and your optimized filesystem will prevail, and one day we'll think of rotating media in the same way we now think of core memory, floppy disks, tape drives, and the x86 instruction set... er, hmm.)

Waiting for Godot/the 87 bus

A: What time?
B: Should be here at 11:30
A: 2, 3 minutes. (spits)
Pause.
A: Look. Here.
B: Davis at 11:22. But that's down there.
A: 2, 3 minutes.
B: Yeah. 11:30.
Pause.
A: Maybe look, you see yet?
B: No, no, I can't see past the construction.
A: 2, 3 minutes. No more.
A: It's hot. Inside my house, 90% humidity. Outside: 100.
Pause.
A: How old are you? 26? 28?
B: No, 32. (looks down street)
A: You see?
B: No, not yet.
A: 2, 3 minutes. (spits)
Pause.
A: Maybe 10.
Pause.
A: You married?
B: No.
Pause.
A: Maybe is better.
Pause
A: You're 26?
B: 32.
A: I was 28.
Pause
A: You see yet?
B: No. I can't see. (shrugs)
A: 2, 3 minutes. (spits)

Posted via LiveJournal.app.

Sugar waves: time to get started!

While I was abroad, it seems that Google released their wave server/federation code. So you can now get started tackling some of the projects I outlined in my previous post on Waves and Sugar: getting a basic federation server running on the school server and/or writing a server running locally on the XO which exports the content of the Journal/filesystem for collaboration. I'm hoping someone other than me thinks this is an exciting idea, and runs with it!