Dr. C. Scott Ananian

This year I was a member of Codex, the writing team for the 2012 Mystery Hunt. I'm going to describe some of the puzzles I wrote for "The Producers" hunt, in release order. BEWARE SPOILERS!

1. One of the early theme proposals for our hunt was "Alice in Wonderland." Casting about for novel meta ideas, I hit upon the idea of a round with purely numeric answers, 1 through 29,394, which would resolve to words via "looking glass numbers"—that is, numbering all the words in "Through the Looking Glass". It occurred to me that you could make your numbering system self-descriptive if you used certain words; for example, if you wanted to make clear that hyphenated words should be counted as one (instead of two), you could include "great" and "half" on either side of "arm-chair". The numbering of "great" (164) and "half" (166) would make it clear that "arm-chair" should be treated as a single number (165).

   This didn't survive as a meta, but it eventually became a puzzle, called 1207 1370 (which translates to "Looking-Glass Words" using its enumeration system). It also served to ensure that teams had a good wordlist by the time they got to the Charles Dodgson meta...

2. Blinkenlights. A recursive-structured puzzle inspired by (but not reaching the greatness of) Derek Kisman's Maze from Setec's '05 Hunt. If anyone is mourning the lack of Jonathan Coulton-related puzzles from this year's hunt, blame me: I stole the answer PROTECTORS which Andrew Lin had earmarked for a JoCo puzzle. ("Did I say overlords?")

3. Caterpillars. I like giving physical objects to teams. This was another failed meta—you would have assembled the pieces out of words, then would have to assemble the jigsaw from the word-pieces. The location of the caterpillars' heads in the final assembly would spell out the final meta answer using an overlay. But the puzzle is more fun with tangible pieces, I think.

4. B.J. Blazkowicz in ‘Wintertime for Hitler’. I was writing the meta for this round and trying to find non-dictionary words. I needed "CAR..." as a prefix to make the chess game work, which suggested CARMACK as an answer, and the puzzle just wrote itself from there. Scott Handelman contributed the title. This puzzle was going to be distributed on 3.5" disks (remember how I said I like giving teams physical objects?), but the last 3.5" floppy disk puzzle was Blue Steel in '06. (Redundant Obsolescence doesn't count, since the 5 1/4" disk was redundant.) The past six years have not been kind to the 3.5" floppy; ultimately we decided we didn't want to deny teams the pleasure of playing the game because they couldn't locate a floppy drive. It's more important that puzzles be fun than hard!

5. Charles Lutwidge Dodgson meta. I began writing this puzzle immediately after the 2011 hunt, dissatisfied with the mechanism and final clue phrase of that year's Racking Your Brains. I thought I could write a better puzzle using Scrabble Solitaire as a mechanism.

   Slightly later it became part of the "Alice in Wonderland" theme proposal, with Jabberwocky words. Then I spent a couple of months away from the hunt, getting married.

   Upon returning we badly needed critic metas so I dusted off the puzzle, adding an Alice chess frontend yielding the tile string in order to make it a shell meta. The puzzle can still be solved as pure Scrabble Solitaire (ie, without the given "scores after each play") but it's easier for humans to solve with the frequent checkpoints given. For what it's worth, I constructed the chess game with a reasonably-deep alpha-beta search, so all the moves "make sense" as much as is possible given the constraints of the puzzle. And it ends in a clean checkmate, obviously... I have no idea how BENOISY snuck in there.

6. Ben Bitdiddle meta. The idea of making an electronic circuit which was impossible to assemble incorrectly had been in my "Mystery Hunt ideas" folder for years. A coworker at OLPC mentioned the odd power-pin configuration of the PIC chips one day, which gave me the "flip" mechanism. Brainstorming with Andrew Lin brought it the rest of the way.

   I promise never to abuse an optoisolator in this way again.

   (Of course it turned out when constructing this puzzle that Ben Bitdiddle really needed to use the show answers CARPAL and THESOUTH because of their length in morse code, so I ended up having to rewrite parts of Dodgson to make Bitdiddle work. In the rewrite CARPAL became CARMACK... and B.J. Blazkowitcz was born.)

7. JFK SHAGS A SAD SLIM LASS. One of my earliest puzzle submissions was, "A puzzle contained only in its title." Again, the fabulous Codex editor team turned this into a real puzzle.

Some puzzles I enjoyed editing:

1. Revisiting History — I commissioned a Doctor Who-themed puzzle for the answer TORCHWOOD (see the final clue phrase for the reason why) and contributed the "location of the word 'who'" mechanism.

2. Gibberish and More Gibberish. I liked the idea for this puzzle enough that I shoehorned a suitable answer into the Charles Dodgson meta... and then had to do some heavy lifting to get the puzzle finished and into the hunt.

3. Sounds Good to Me. It was immediately obvious this was a brilliant idea from Seth Schoen. But the twin barriers of toki pona and hiragana threatened to make it unsolvable. I'd like to think I played a role in making this an accessible and solvable puzzle.

4. Itinerant People of America. Same deal. Squiggles had bequeathed the world the facial expression described as, "That's my brain leaving out the back door while my face distracts you." My contribution here was solely instilling the fear of God into the authors. Scott Handleman describes how he and Emily Morgan took that advice and constructed a kick-ass puzzle.

And that's it for my puzzles! I also did a heck of a lot of other stuff for the hunt; I hope y'all enjoyed it. (My own favorite part was the wrap-up, since all my responsibilities had been discharged by then. I could just watch Patrick rock my hat and accordion, play along on ukulele, and sing tenor with Francis at the end.)

Here are some banged-together demos of various pieces of One Laptop per Child's Project Nell. The ultimate goal is a Nell demo for CES in January 2012, but these bits should be considered as tech demos, benchmarks, and proofs of concept, not actual pieces of that demo (yet).

Most of these demos require WebGL support. Visit get.webgl.org for information about enabling WebGL in your browser; there is WebGL support in Chrome, Firefox, Safari, and Opera—although it often requires enabling experimental features in the browser preferences.

• Tiles. Performance benchmark for a tile-based home screen. "Apps" are "locations" on your world map, which you can customize as you like. (Here's an interesting blog entry discussing world-creation for kids.) Day/night would ultimately reflect current time, although they've been greatly sped up in this demo. Lots of rough edges and missing UI, but all the textured triangles are present, so it should be an accurate benchmark.
  (Drag with left mouse button to rotate, middle mouse button to zoom, right mouse button to pan.)
• Nell at home. Basic idea (including transition) for activities which include dialog with Nell or story-telling.
  Standalone model viewers: Castle (from blendswap), "Nell" (Sintel, from blendswap), Alternate (lightweight) Nell model, Alternate (heavyweight) house model (from blendswap).
  In model viewers: drag with left mouse button to rotate, middle mouse button to zoom, right mouse button to pan.
• Music maker. Uses WebGL and the Web Audio APIs to let you draw and perform music.
  Inspired by André Michelle's ToneMatrix and Karplus-Strong Guitar (see also wiki and this 2008 Linux Audio Conference paper), as well as DinahMoe's ToneCraft and the Tenori-on.
• Quake on XO-1.75 (video). Of course we need to actually run WebGL with good performance on XO hardware. Jon Nettleton has been working hard on our GL drivers, enabling the GPU on the XO-1.75 hardware for the first time. This Quake demo shows his progress—don't worry, Quake is not actually part of the Nell demo! (We have a GPU in the XO-1.5 as well, which hasn't yet been utilized.)
• Codify—not one of our demos (it's a commercial iPad app) but it demonstrates the direction we'd like to push Pippy.

Coming soon: TurtleArt and Implode for the web. We've started converting them to GTK3 in preparation for hoisting them bodily onto the interwebs. Here's the source code repository for the TurtleArt port if you'd like to watch or participate in this hackage. (See repl.it for one of the more unusual ways to get Python running in the web context.) The rest of the demo source code is on github (or just "View Source" in your browser).

Between now and January CES, Chris Ball and I will be building Nell for the OLPC XO-3 tablet. Nell is a name, not an acronym, but if you want to pronounce it as "Narrative Environment for Learning Learning," I won't stop you.

Nell's development will be demo-oriented—we're going to try to write the most interesting bits first and learn as we go—so don't be upset if you don't see support right away for legacy Sugar activities ("Sweet Nell"), robust sharing support, mesh networking, or whatever your favorite existing feature is. They'll come, but the new crazy stuff is what we need to evaluate first.

Here are four of the big ideas behind Nell, along with pointers to some of our sources of inspiration.

Narrative. I probably don't need to restate that Neil Stephenson's "The Diamond Age" has been hugely influential, and we also owe a large debt to interactive fiction and the Boston IF group in particular. (Check out the talks from our "Narrative Interfaces day" at OLPC.) Wide Ruled (conference paper) and Mark Riedl at Georgia Tech have demonstrated interesting approaches to story representation. I'm also looking forward to the results of the Experimental Game Play group's September Story Game competition.

Emotion. The Radiolab podcast "Talking To Machines" crystallized my thinking about emotionally-attractive environments. The discussion with Caleb Chung, the creator of Furby, is particularly apropos. Caleb's goal is to make things which kids want to "play with for a long time," and he contributes his three rules for creating things which "feel alive": it must (1) feel and show emotions, (2) be aware of itself and its environment, and (3) have behaviors which change over time. Furby's pursuit of these goals include expressive eyes and ears, crying when held upside down, reacting to loud noises, and gradually switching from Furbish to English for its utterances. A living thing emits a constant stream of little surprises. Expect to see Nell put the XO-3's microphone and accelerometer to good use.

Talking and Listening. The "Talking To Machines" podcast also discusses ELIZA and Cleverbot, which dovetails with my interest in the popular Speak activity for Sugar and related toys like Talking Tomcat for mobile phones. The key insight here is that a little bit of "cheap trick" AI can go a long way toward making a personable and engaging system. We want Nell to feel like a friend. Recent work by the Common Sense Computing Initiative at MIT's Media Lab shows how we can reset this on a sounder basis and use mostly-unstructured input to allow the system to grow and learn (creating "behaviors changing over time"). In particular, I'll cite ConceptNet for its database and practical NLP tools, and inspiration from "Empathy Buddy," "StoryFighter," and the other projects described in their Beating Common Sense paper. It's also worth noting that open source speech tools are good and getting better (the VoxForge site points to most of them); also interesting is this technique for matching a synthesized voice to that of the user.

Collecting, nurturing, and rewarding. Collector games such as Pocket Frogs and Flower Garden are sticky activities which encourage kids to come back to the device and continue working toward a goal over a long period of time. Memrise is educational software illustrating this technique: its users tend a garden of flowers by mastering a set of flash cards. Nell will incorporate the sticky aspects of such games, possibly also integrating the Mozilla Open Badges infrastructure into an achievement/reward system.

I hope this has given you a general sense of the direction of our Nell project. In future blog posts I'll drill down into implementation details, demonstration storyboards, and other more concrete facets of Nell.

One Laptop per Child creates student-centric learning experiences. Our current software stack, however, is somewhat "shallow". When you turn on the XO, all the content is immediately available but there is no path or guidance provided. Nothing suggests what you should try first, or indicates an order to progress through the activities provided. Everything is available, but there's no built-in journey. No plot. How can we improve this?

This Friday (June 17) at 2pm Eastern we're inviting some folks over to OLPC's new offices at the American Twine building to discuss Narrative Interfaces, as part of the proposed XO-3 software stack. Nick Montfort will give a short talk on Curveship, his model-based interactive fiction system, and Chris Ball will present some related recent hacking. Angela Chang will present her Tinkerbooks early-literacy platform, which allows kids to interactively change the written story on the page. And I'll discuss Neal Stephenson's novel The Diamond Age (a recap of a short talk I gave at EduJAM in Uruguay), and give concrete suggestions for how Diamond Age's Primer might influence the software architecture for the XO-3. (I might even reveal how to make software testing semantically indistinguishable from writing a game!) Chris Ball and I have also been collecting best-of-breed "comic books that teach you something" as examples of educational narrative; we'll pass those around and post a reading list after the event.

The real point of this meeting isn't the talks, per se, but the discussions to follow. We're trying to gather folks who know a lot more about this stuff than we do, in order to learn from them and be inspired. We don't have a lot of space, unfortunately, so I'm going to have to ask for RSVPs from those who wish to attend. If you're in the Boston area and feel like you have something to contribute (and especially if you have created/could create Creative Commons-licensed content for education), drop me a line at cscott at laptop dot org. Describing what you can contribute to the discussion will help break ties if space is inadequate.

We will also live-stream the meeting at ustream.tv/channel/cscottnet. Afterwards we'll post higher-quality video and a list of cited works. Thanks in advance to everyone who will participate, online and off!

UPDATE: video now up; see this writeup on Chris Ball's blog.

Today I stumbled across some very interesting projects by Nickolay Platonov which I'd like to discuss in an OLPC context.

I've been hacking away at TurtleScript fueled partly by a drive for minimalism: a small system is a learnable system. To that end, the language is based on Douglas Crockford's "Simplified JavaScript" (as recognized by this top-down operator precedence parser) which tries hard to include only JavaScript's "Good Parts". For example, the initial code for the TurtleScript system uses prototype inheritance (via Object.create) rather than classical class-style inheritance. In fact, the new operator isn't even included in the Simplified JavaScript/TurtleScript language.

In a discussion of TurtleScript Alan Kay mentioned, "It is very tricky to retain/maintain readability (so the first Smalltalk was also an extensible language not just semantically but syntactically)." And today I stumbled across the Joose library, which gives a very readable syntax for traditional class-based inheritance. It backs this up with a robust meta-object protocol, introspection, and lots of nice features borrowed from Perl 6, CLOS, and Smalltalk. The syntax ought to work fine with the limited tile set of TurtleScript, although I might have to add a tile for the new operator.

However, adding Joose raises some questions. Is the increase in readability worth the addition of such a large library to the system? What impact will this have on understanding problems and debugging? Is a return to class-based inheritance a positive change? (There have been arguments that the make-a-clone-and-change-it practice of prototype inheritance is easier to understand for new learners.) Can a larger overall system actually be easier to understand?

And once we're looking at libraries... Nickolay Platonov is now working on Syncler, based on the Bayou system. Unobstructive replication mechanisms would certainly make it easier to construct the sorts of collaborative applications we've wanted for Sugar. I have two concerns with Syncler's current state. First, the use of explicit continuation-passing style greatly impairs readability. The JavaScript yield keyword helps a lot when writing asynchronous code. (It's not supported by all JavaScript engines, but yield wouldn't be hard to add to TurtleScript.) Second, Syncler's event model uses explicit callbacks. I've been greatly impressed with the Flapjax event model (and its strongly-typed functional cousin). Both of these changes ought to make asynchronous code much more readable—and isn't that an important part of grokking a system?

Inspired by Bert Freudenberg, Ian Piumarta, and Walter Bender, I started hacking on "Turtles All The Way Down" (aka TurtleScript) on the plane back from Uruguay. Now there's a nice rendering demo to show what a tile-based editor for JavaScript might look like, as well as a bytecode compiler and interpreter for the language. The bytecode instruction set is still too large; encouraged by Craig Chambers' work on SELF I think I ought to be able to replace all the unary and binary operators, conditional jumps, and slot selectors by a single mapof operator. I can put a better object model on the interpreter, too; I've written some notes on the matter.

The question is: does this really have educational value? "Turtles all the way down" is a great slogan, and a fine way to teach a graduate-level class on compiler technology, but I feel that the higher-level UI for tile-based program editing is the really useful thing for tablet computing. I'm a compiler geek and love the grungy underbelly of this stuff, but I keep reminding myself I should really be spending more time building a beautiful fluffy surface.

Chris Ball has done an excellent job posting video from all the talks at EduJam in Montevideo. I gave talks on Sugar, Education, and Tablets, The Diamond Age, Internationalization Everywhere, and Sugar on Android and Native Client.

I've reached the end of the month. I've accomplished my Android and NativeClient-related goals, but didn't get the time to do as much mesh and python investigation as I'd wanted. Here are some ideas for next month's work. (Next week I'll be in Uruguay for EduJAM.)

GObject Introspection (Android or NaCl)

1. Start by porting libffi. An android port would be straightforward, but since libffi involves code generation (ARM, x86), this is going to require a bit of assembly magic and the new "JIT"/"shared library" support in the NaCl plugin.
2. Then port gobject-introspection. GObject-Introspection relies on libffi for its guts, but the hard part of this port will be refactoring g-i's build process, which is not cross-compilation friendly. Might need to rewrite some tools. If targeting NaCl, you might consider finishing the code allowing execution of unsandboxed NaCl binaries.
3. Turn gobject-introspection on its head: generate GIR and a C binding for the platform "native" interface. For NaCl, this would be a GObject-using C-level binding of the browser-native DOM; for Android, this would be a GIR binding of the native Android APIs. These bindings should be mostly automatically generated, since they will need to continue tracking successive native platform releases/HTML5 features.
4. Demos! Change browser DOM from Python, write native Android apps in Python. Add a gobject-introspection binding to cforth, then do the same from forth. (Forth might be a simpler place to start than Python. Or not.)

GTK (Android or NaCl)

1. Build on the cairo/pango port to proceed to a full GTK backend for Android/NaCl. These backends ought to be upstreamable. The NaCl port should be based on the broadway work: the cairo canvas would be drawn to more directly, but a lot of the mechanism which captures JavaScript events and translates them into the GTK event loop could probably be reused.
2. Demo: "Hello GTK world" in Android/NaCl.

Sugar partitioning.

Bring Sugar closer to being a true multi-language multi-library platform.

1. Refactor sugar modules (for example, sugar toolbar widget) as standalone C libraries. Basic idea is to embed Python and export a C API, while preserving as much of the code as possible. Python libraries now invoke this library via g-i-r instead of directly. The python embedding tool is probably a useful standalone product.
2. Rewrite "Hello, Sugar" activity in C (or vala), using #include for import and GObject inheritance instead of python inheritance. Use this as a guide to pull apart sugar into modules (as above) to make this code actually work as written.

Miscellanous topics

1. ChromeOS w/ touch support.

   Find an appropriate machine, do an installation, what are the roadblocks/rough spots? Can we install on XO-1.75 as a testbed?

2. TurtleArt as JavaScript viewer/editor.

   Revisit TurtleScript work, but skip over the time-consuming "construct an editor" step by reusing the (excellent) TurtleArt code.

3. Mesh: android olsrd frontend, build testbed, research 802.11 DCF issues.

Summary

There are four rough topics here; I might try to continue the breadth-first search by spending a week on each. It might be more satisfying to downselect two of these issues and spend two weeks on each.

At the end of my Sugar/Android week, I had a simple Pango-on-Cairo demo running. This was built on a stack of ported libraries, including gettext, pixman, freetype, libxml2, fontconfig, and glib, as well as cairo and pango. You can run the demo yourself by sideloading pango-demo.apk onto your Android device (tested on a Motorola Xoom), and you can browse the source code to see what it entailed (here's the scariest part). (I was inspired by Akita Noek's android-cairo project, but I ended up reworking the build scheme and redoing most of the ports.)

It made sense to start my Sugar/NaCl investigation by porting the same demo application to Native Client. The same stack of ported libraries was involved, although it was easy to include more functionality in the Native Client ports, including threading and PNG/PS/PDF support in cairo. The source code is a fork from the upstream naclports project, and the process was generally much cleaner. (But see my previous post for some caveats regarding naclports.) If you're using Chrome 10 or 11, you can run the demo in your browser (follow the instructions on that page). The Wesnoth team has a parallel project which ported some of these libraries as well, but not in an upstreamable manner.

The demo app uses cairo to draw the background, an animated X, and some basic text in the center; it uses Pango's advanced international text support to draw properly-shaped Persian text in a circle around it. The center text is the "proper" bilingual Greek/Japanese written form of "pango"; the text around the edges is the Persian name of the internationalization library, "harfbuzz". Note that the Persian text is written right-to-left—and that I didn't put a full CJK font in the NaCl app, so the Japanese "go" character is missing. The Android port rebuilds the font cache at each startup, so it loads rather slowly; the NaCl port contains a prebuilt font cache so it starts more quickly.

Both ports took about two weeks. I blew my original schedule, partly due to the Patriot's day holiday, and partly because I'd given Android about a week's head start by tinkering on it before my original schedule post. The framerate of the demo is much better on NaCl (so fast that the edges of the animated X look choppy in the screenshot), but the hardware isn't easily comparable, so the comparison doesn't really tell us much. The porting effort was certainly more pleasant on NaCl, since newlib is a much more complete libc than Android's "Bionic"—but having gdb available made debugging on Android easier. (There is an unintegrated NaCl branch that integrates NaCl gdb in the browser, though!)

Much of the GNOME/POSIX library stack assumes access to a filesystem tree and does file-based configuration. In our demo application, fontconfig was the most culpable party: it wanted to load a configuration file describing font locations and naming, then to load the fonts themselves from the file system, and finally to write a cache file describing what it found back to the file system. Most ported software is going to want similar access—even if you store the user's own documents in a Journal, software still expects to find configuration, caches, and other data in a filesystem.

Android provides the POSIX filesystem APIs, but the filesystem an app can touch is segmented and sandboxed. As discussed previously, Android's Opaque Binary Blob feature may allow you to create a app-specific filesystem, but this doesn't let you share (for example) fonts and font configuration between activities. NaCl might eventually provide a similar unshared mechanism based on the HTML5 AppCache.

The preferred solution is more limited, but more flexible: no built-in filesystem APIs are used (or in NaCl's case, provided!) at all. Instead, you provide your own implementation of the POSIX file APIs (either via the --wrap linker indirection or through an appropriate backend to newlib/glibc/glib). For the NaCl demo app, I wrote a rather-elaborate in-memory filesystem --- only to find that an even-more-elaborate one already existed in naclports. But the longer-term solution uses message-passing (SRPC in NaCl, intents in Android) to implement these POSIX APIs. In Native Client, the implementation would be in browser-side JavaScript, which would then allow you to share parts of the filesystem tree between activities and/or map it into (cached) web-addressed resources. In either case, your application still sees the bog-standard POSIX API it expects.

More problematic are the networking APIs. Here Android provides a pretty standard socket library, while Native Client provides nothing at all. Using a browser-based implementation, as for the file APIs, will work fine for HTTP, WebSockets and even P2P via the HTML5 P2P APIs. But it's not clear that (for example) glib's elaborate asynchronous DNS name resolver implementation can (or should!) be implemented in a NaCl port.

In the end, the porting effort and abstraction shifts needed for Native Client and Android are roughly comparable. I expect Native Client will hold a strong edge in allowing close integration with web standards and web technologies. Android will probably continue to hold an edge in third-party application support and platform maturity.

This post will describe the state of Native Client in general, based on week 2 of my original four week plan. In the next post, I'll link to my work so far, and compare the Native Client and the Android efforts. Recapping, the end goal of these explorations is a platform for the next generation of the Sugar learning environment.

To begin, the Native Client (NaCl) plugin is fairly mature in a number of areas. Version 0.2 of the NaCl SDK was recently released (a version number which substantiates the "fairly" in my previous sentence), and the NativeClient plugin is currently shipping in Chrome (versions 10 and 11), although you have to manually turn on a preference in the about:flags dialog to enable it. The NaCl toolchain is much more standard than the Android NDK toolchain I discussed previously, and the robust naclports tree shows that the patches required for NaCl ports of common packages tend not to be too evil. The Tcl interpreter and Qt tookit port demos show that fairly complex pieces of code can be deployed today on NaCl.

On the other hand, there are three main difficulties:

1. The default NaCl toolchain uses newlib as its standard C library. This is consistent with Google's preference for BSD-licensed code in SDKs they provide to the public (see the discussion of Bionic in the Android SDK). However, there also exists a branch of the SDK which uses glibc. The glibc branch supports several additional features, like shared library support. However, it is unclear whether this will ever be a "supported" part of the SDK. If glibc does become supported, it is unlikely ever to be the only supported libc; the BSD-licensed newlib will need to remain available as an option. (Yes, the LGPL license of glibc shouldn't inspire such paranoia, but Google has elected not to undertake the education of all prospective third-party developers.)
2. The naclports project, although fairly robust, is driven between the Scylla and Charybdis of compatibility. The goal is that all the code in naclports be buildable at all times on all three major platforms: Windows, Mac, and Linux. Further, it should support both x86_32 and x86_64 backends, and ideally ARM and pNaCl as well. It's auto-built against the latest SDK sources, but should also work on the latest released SDK. And with the addition of the glibc/newlib split discussed above, the possible build targets are multiplied further. Needless to say, keeping the tree building against such a large number of variants is not an easy task, and naclports is usually broken in some way. In practice, most developers seem to pay attention to some subset (say, x86_32/newlib/Linux host), but it's hard to push patches upstream without worrying about breaking some obscure target. It might be best to base future work on a proper package technology, like (say) dpkg-cross.
3. In general, a lot of interesting NaCl development has occurred on branches that are not easily integrated. I've already mentioned glibc support, which is a toolchain branch; shared library support is on another branch that requires a new chromium plugin as well. At various times different means have been implemented to run NaCl binaries "natively" outside the sandbox (for example, in order to test some feature at build time, or auto-generate some piece of code via introspection). These efforts live on abandoned branches, while the "official" means to do this is incomplete. Similarly, a lot of interesting NaCl work used the now-abandoned legacy "NPAPI" plugin interface to interact with the browser. It was followed by the "Pepper" plugin interface, which was itself abandoned. Current work uses the Pepper2 browser plugin APIs, which (unfortunately) have not yet been implemented in non-Chrome browsers and continue to flux about. Many interesting browser interactions exist only in deprecated Pepper APIs, not having yet been built into Pepper2. ARM and pNaCl work also appears to be on unintegrated branches. There are a number of different gdb support strategies.

None of these difficulties is insurmountable—and in fact, some are side-effects of the desirable active development and productization of Native Client. To date I've done my work on the (more compatible) SDK v0.1 and the (more upstreamable) newlib library. So far newlib has not been a huge obstacle, and this basis allows my patches and ports to be more broadly useful. This might change in the future—certainly at some point we need to move to ARM and/or pNaCl for XO-3, which will probably require building chrome and the NaCl toolchain from scratch. At that point, it may be worth further exploring the non-mainstream branches.

A few months ago, a number of stories came out covering the iPad's remarkable-seeming ability to share the GPS of a tethered iPhone. Apple's latest location database FAQ confirms the suspicions I voiced at the time: there's no actual GPS sharing involved. Instead, Apple is using the simultaneous GPS and Wifi radios on your iPhone to "crowd-source" what I'll call a "skyhook" database (after the first company to publicly use the technique). This correlates Wifi base station identifiers with their GPS locations in real time -- including (most likely) the real time location of the "base station" created by the iPhone when it is in tethering mode. All nearby Apple devices use this database to compute their location (based on all visible wifi base stations). Since the nearby device sees the iPhone's "base station" and the iPhone is busily updating the position of that "base station" in real time (along with all the other base stations the iPhone can see), the iPad (lacking a GPS of its own) gains the apparent magical ability to compute a very accurate position for itself.

The real interesting part of this story involves user consent and privacy—do iPhone users generally know that their devices are registering their location in Apple's database in real time whenever tethering is turned on? Any device which can query Apple's location database for the MAC address of your iPhone can track the position of your iPhone whenever you are tethering. That's basically what the magical ability of the iPad/iPhone pair tells us. Did you know that?

Last week I described a four-week plan to survey key technologies for One Laptop Per Child's forthcoming XO-3 tablet computer. Here I'll describe the results of the first week of work, which dove into Google's Android operating system. Warning: technical content ahead...

Basic design of Sugar-on-Android

1. Cross-compile gobject/GTK/gobject-introspection/cairo/dbus for Android; distribute these key libraries as NDK libraries. This is what I spent most of my time on this week: I've managed so far to port libiconv, gettext, glib, pixman, freetype, fontconfig, cairo, libxml2, and pango. (Source code)
2. Use cairo or OpenGL backends of GTK3 to render legacy Sugar activities directly to Android canvas.
3. Modularize sugar; use D-Bus for inter-module communication. Interprocess communication mechanism is Android 'intents'; these can redirect to the web or the Android Market for missing dependencies. (Collabora reportedly already has a D-Bus implementation for Android.) Sugar components can also become Android Services.
4. Implement Sugar Home/Groups/Neighborhood views and Journal as four separate Android App Widgets. These could also be implemented by providing a new Android home application, but I think the finer-grained modularity afforded by splitting these functions would yield a better design and make it easier to incorporate upstream improvements to the Android launcher.(Android Live Wallpaper is also similar in function, but not as good a fit.)
5. The Sugar Journal becomes an Android "Content Provider", which stores/retrieves content for other Sugar activities. (There is special Android support for "collection-based Widgets" and Live Folders which may be helpful.)
6. Use gobject-introspection to build a multi-language environment. Use JGIR to expose Sugar APIs to "native" Dalvik apps; use something like the Android Scripting Environment to expose Android native APIs to GIR languages (Python, JavaScript, C, etc).
7. [opportunity] Use the Android port of OLSRd to implement a Neighborhood view. Alternatively, investigate AODV routing on Android and/or AllJoyn (which also requires root access, see pg 24-25 of the manual).

Key Benefits

• Sugar is integrated into Android environment; use native Android education apps, or apps like Movie Studio which have no Sugar equivalents yet.
• Android APIs and customization hooks are good, and provide a more-extensible framework for development.

Open challenges (general)

1. The web integration story is cloudy. Java and JavaScript can call each other inside a bundled WebView widget, but this isn't supported in standard Browser app. Browser plugin interface would help.
2. No good story for building 'native' Java/Dalvik or C apps on the device. Writing a simple Dalvik compiler would help. Dalvik specs are available, and people have written Dalvik compilers for toy languages.
3. "View source" requests can be implemented as an Android 'intent' message, but no good story for implementing this functionality other than on a case-by-case basis in each activity.
4. Although the Amazon Marketplace for Android indicates that it can be done, it appears that there is no "blessed" mechanism for creating .apk files on the device and installing them. (Android bug, discussion)

Current technical issues/bugs

1. Cross-compiling for Android is currently a miserable experience. The Android NDK appears to have been put together by a team which had never seen a proper cross-compiler before. Since I only had a week for this exploration, I mostly kludged things together to get past this, but any serious work with Android should start by defining and upstreaming proper autoconf "target triplets" for Android-on-{ARMv5, ARMv7, x86} and building a proper cross-compiler. Then patches to various tools and libraries could start being upstreamed. Using the bespoke Android.mk build system of the NDK is a non-starter. No serious obstacles here, just work to do.
2. Xoom hardware is ARMv7, but Android emulator is ARMv5 only. Unfortunately, gdb is broken on the Xoom. So we're building for ARMv5 at the moment, so we can debug in the (slow) emulator.
3. No good support for shared libraries may cause activity bloat. May be able to be worked around using the new Opaque Binary Blob (OBB) feature.
4. Much existing code (fontconfig, gettext, gtk, etc) expects to read configuration files from the filesystem. Currently we are using the default fall-back configurations. OBB support may help here as well. There are a number of different storage APIs in Android, but none seems quite right.
5. It would be nice to implement a ring-style XO home screen without completing replacing the android Launcher. No clear way to constrain app layout on home screen w/o completely replacing the Launcher. Is it worth hacking the Launcher source?
6. Mesh on Android using OLSRd current requires root access. In order to run on unrooted Android devices, we need (a) proper power management for Ad Hoc mode wifi, (b) APIs to enable Ad Hoc mode, and (c) APIs to manipulate kernel routes.
7. We're building libraries without thread support because Android's "Bionic" libc has an eccentric thread library. Linking with -lpthread fails because the thread functionality is bundled into -lc. Probably just providing an empty libpthread.so would help a lot.
8. Some work has been done to build GNU libc for Android. This bloats activities even further, but might help ease library porting.
9. Porting gobject-introspection will be painful because its makefiles are not set up for cross-compiling. Some steps want to run on the target hardware, which is difficult in the Android environment.

Bottom line

I can see how the whole Sugar stack can be put together on the Android platform. The hardest part is probably just setting up packaging and a good and repeatable build environment for the different components, and getting enough adoption of this that patches to support Android can be pushed upstream. Many of the important pieces can be developed in parallel (Theme, Journal, Mesh, Friends, Home, library porting, etc). A little early to tell how hard it will be to port existing Sugar activities to the new Python/pygobject/GTK3 framework.

Last Monday I rejoined One Laptop Per Child as Director, New Technologies. My mandate is hardware and software for the XO-3, OLPC's upcoming ARM-based tablet computer for education in the developing world. The new machine should be lower cost, lower power, more indestructible, more powerful, and potentially more expandable than ever. There are about two million machines in the XO-1 family (XO-1, XO-1.5) in the hands of kids today. The XO-3 will build upon this impressive foundation to reach further into the poorest and least-connected regions of the world.

I will kick-off my work with a series of four week-long sprints between now and eduJAM Uruguay to investigate a number of possible directions for the educational software stack on the XO-3 tablet. On the XO-1—series machines OLPC ships Sugar, an impressive collection of educational software developed by Sugar Labs. How can we best keep the best of Sugar while yanking the UI forward into a touch-friendly tablet world?

1. This week (April 4-8) I'll begin by working on a port of the GTK3 UI library to Android. The GTK3 library contains touch support missing from the GTK2 library on which Sugar is currently based. The end goal here would be a full port of the Python/GTK-based Sugar APIs, running on something like the Honeycomb Android OS. Our existing educational activities could be ported to the new APIs without too much difficulty, but we'd largely use the existing Android OS facilities instead of the parts of Sugar concerned with low-level system management. To clarify: this is a preliminary exploration—we haven't decided to base the tablet software on Android (or anything else) yet.
2. The next week brings a new direction. During the week of April 11-15 I will start porting Python/GTK3 to Chrome or ChromeOS via the Google NativeClient plugin. This path would result in activities which more fully integrate with web technologies—even in disconnected regions of the world. On desktop machines, Sugar activities could be run inside the Chrome browser, while ChromeOS (or another embedded OS running chrome/webkit) would provide the system management functions on tablet machines like the XO-3. As with the Android port, this is an exploration, not a definite software direction.
3. The week of April 18-22 I hope to focus on mesh networking. This has a somewhat checkered history in our deployments; I hope to identify the remaining roadblocks and map a way forward to make this a flagship feature of the XO-3 software.
4. The week of April 25-29 is for the existing Python-based Sugar codebase. In order to continue moving forward, it needs to migrate to GTK3, gobject-introspection, and some other key enabling technologies. I believe it would also benefit from language-independent APIs and better modularization to allow a more incremental migration path.

The following week is Conozco Uruguay and the Uruguay EduJAM where I'll present my progress on these initial exploratory projects and discuss the path ahead with the wider OLPC and Sugar communities. Clearly, a week each is not enough time to finish any of these projects! But the focused effort should help to better identify the promise, roadblocks, and challenges in each of these paths, which then in turn will help us to plan the future.

A recent article on Nokia's internal culture contained this interesting quote:

Designers are also, by training and predilection, inclined to design for the usual, where engineers are taught a kind of rigor that compels them to account for, and overweight, low-probability events.

This does seem to me to often be a fundamental problem in not only interaction and UI design, but also internal programming APIs and interfaces. Good engineering is a clever balance; as Larry Wall has said: "Easy things should be easy, and hard things should be possible." An engineering mindset often fixates on the hard things (the "interesting part of the problem"!) and tries to make the hard things easy (or easier), at the risk of making the easy things hard. The end result is failure.

Truly elegant engineering involves finding a view of the problem where the hard parts of the problem disappear. We're not always fortunate enough to find that solution. In falling back to a practical/possible solution, we must be careful to ensure that we keep the easy things easy — it's fine if the hard things are difficult, so long as they are possible. Effort spent making the hard things easier is wasted if it makes the easy things harder. The goal is not a uniform mediocrity of design.

There's been a lot of discussion about publishing and sharing the software that Mystery Hunt teams use to collaborate to solve puzzles. This is mostly misguided, IMO: teams are very different, and they organically grow solutions to fit their unique processes. On the other hand, an increasing number of teams (including my team, Codex), are building their collaboration software on top of Google services, especially Google Docs and Spreadsheets. Rather than trying to collaborate on One True Hunt Team Software, I think it would be far more useful (for all teams) to lobby for improvements to Google's services. These raise the bar for everyone, and indirectly benefit many other people with collaborative processes.

So here's my list of improvements I'd like to see in Google services:

1. Integrating Docs and Spreadsheet. If we had an initial "sheet" of the spreadsheet with editable formatted text (not spreadsheet cells) we could actually do away with the wiki we use for capturing free form thoughts and links related to a puzzle.
2. Integrating Spreadsheet chat, Google Talk, and Jabber. We could just use the chat in the spreadsheet if it were open and accessible, instead of creating our own per-puzzle chat rooms.
3. Making publish and "setAnonymous" access available via APIs that actually work. We need to use Google Doc Script to do the setAnonymousAccess call, which is not exported via the otherwise-more-complete GData APIs, and drive a headless Firefox 2 instance via Selenium to get the publish bits enabled for the spreadsheet. That's ridiculous.
4. Providing a way for Google Doc Scripts on a spreadsheet to export data more easily. We can use a Google Form to create a spreadsheet for a puzzle, but no easy way to provide a link to that spreadsheet on the page that results after form submission, or redirect from there.
5. IIRC Google Talk support for multi-user chat is still barely supported. It doesn't use the standard Jabber protocols, for one. If this were a better supported/more standard service, we wouldn't have to run our own Jabber server.
6. And, of course, the "next generation" of all this would integrate audio and video into the chat as well. Video is probably more useful, as it communicates human emotional cues. Audio isn't easily archived or searchable, and doesn't work well in crowded rooms, so it is less useful to us. But it would be great if we could actually see some/many/most of the particants in ringhunters, maybe little live video icons next to their faces.

Any further suggestions from other teams?

We won the Mystery Hunt this year! You can read a Boston globe article which mentions us, but mostly talks about Palindrome.

That means we have to—er, "get to"—write the Mystery Hunt for 2012. My free time for the next year has just vanished.

A recent article in the Economist points out that Wikileaks is not unique: modern network tools have made anonymous communication ubiquitous. You can't stop "wikileaks" by attacking Julian Assange alone. The article is incorrect, however, in claiming that anonymity is easy — in some sense anonymous leafleteers in Colonial America were better off. Bradley Manning currently sits in jail. Haystack was fundamentally flawed. There continues to be a role for organizations who desire to facilitate anonymous speech to identify and provide trustworthy and user-friendly tools and procedures.

Aaron Brady achieves a more fundamental insight by examining Julian Assange's aims. Assange's goal is to hobble "conspiracies", that is, the small cliques of power and secrecy embedded in most organizations, and he seeks to do this by causing them to fear information sharing. By this metric, Wikileaks seems to be succeeding. (Read Aaron Brady's essay for the details.)

But it's worth pausing to consider: are open organizations truly better? Is openness practically achievable? This is an organizational problem which was on the front burner at OLPC while I worked there: OLPC pledged an open development and governance model, but was continually charged with being closed, insular, and secretive in practice. We reorganized previously-internal mailing lists and pledged to conduct all important business on public archived lists. Yet there was continual backsliding. Sometimes private email was used merely to prevent embarrassment or confusion—to fact-check before making a public statement. Other times it was claimed that some measure of secret/private communication was a fundamental part of business or negotiation, necessary for interacting with external entities. In order to evaluate the latest components/plans/schedules of our partners, we had to sign NDAs. The secrecy requirements of the third-party then contaminated related discussions. In the end, even an organization with a goal of openness ended up embedding pockets of secrecy, which always threatened to grow and spread unless they were occasionally beaten back. Attempting to stand for open principles was often claimed to make OLPC "uncompetitive," as in: we couldn't hope to get the best deals/access to the latest components/whatever if we insisted on being open about everything.

The quest for openness in business seems to parallel the role of Wikileaks in national affairs. As with OLPC's business negotiations, we are being told that secrecy is an essential part of the diplomatic process, and that publishing internal cables hobbles America's ability to achieve its goals. The claim is that Wikileaks threatens to make America "uncompetitive."

Is this true? Openness is an ethical position, but not a black-and-white one. Very few people argued that OLPC (or America) should have no secrets — the debate was always "how many?" In practice if the desired answer was "as few as possible", there was always a Wikileaks-like need to continually drag private content to public forums in order to combat the creep of secrecy. Perhaps the same is true of governments.

Then again, over-reaching openness threatens individual privacy — where to draw the line? Must all our personal mistakes be made in public? Must all our national mistakes be made in public?

For the record, my personal bugbear is the privacy implications of the new "advanced imaging" machines appearing at airports. But then again, I've distrusted supermarket loyalty cards and freeway FastLane programs, too -- my experience is that data which is collected will eventually escape your control (if you had any to begin with), and that no one is willing to offer a believable privacy pledge for such data (it would have to have 3rd-party audits for compliance, for example).

All that said, I just read a very reasonable article discussing the health impacts of the new scanners. I'm not going to play the alarmist card — ironically, the risks of injury from passing through a scanner are most likely about the risk of injury in a terrorism-related incident, that is to say extremely small — but it's prudent to admit honestly where risks are unknown, and to call the lie when deceptive arguments are used.

So let's not get all "ooh, scary, radiation" about this — quantum-physically speaking, everything is radiation at some wavelength — but it's worth keeping the risks in mind so you can make your own decisions, especially if you'd otherwise feel peer-pressured to "just do it". I'm just glad that as a nation we've apparently decided that this is where we're going to step up and draw the line, libertarians and liberals together. Contemplating our freedoms progessively and silently eroding away one by one is a far more worrying prospect.

I've caught the Words With Friends bug. Worse: the Words With Pirates subtype. (It's all the tile-placement and strategy fun of Words with less of the tedious racking your brain for obscure words; a more relaxing variant for when I don't want to think so hard.)

Today I discovered that I didn't actually understand the full word-creation rules for Words With Pirates. For the benefit of other similarly unenlightened folk, here's the accepted word list as a regular expression:

^((([gh]y?|y)?ar+(g(h?))?)|(harhar(har)?))!?$

In more verbose format, these are all the words:

ar arg argh gar garg gargh gyar gyarg gyargh har harg hargh harhar harharhar hyar hyarg hyargh yar yarg yargh

In addition, an exclamation mark is always allowed at the end, and any non-zero number of r's may be substituted for any r.

Note that the words 'har', 'harhar', and 'harharhar', with optional exclamation marks at the end, are allowed. This is a little unusual, since the 15x15 grid should allow 'harharharhar' and 'harharharharhar' to also be played -- but these are not in the dictionary. Nevertheless, these oddball forms will probably prove useful to those stuck with excess a's.

For the benefit of the obsessive, there are 15 A's (worth 2 points), 9 G's (worth 3 points), 6 H's (worth 5 points), 28 R's (worth 1 point), 3 Y's (worth 10 points), and 3 !'s (worth 10 points), for a total of 64 tiles.

Enjoy!

Via reports on the OSCON 2010 Emerging Languages Camp, I recently discovered CoffeeScript, a very interesting "dialect" of JavaScript. The original idea for CoffeeScript seems to be to clean up the syntax of JavaScript, while preserving direct correspondence as much as possible. Over time, it seems to have grown more and more "neat features" which have increasingly-hairy desugarings into JavaScript — but the JavaScript translation of a CoffeeScript program is still very readable.

This has some relationship to my TurtleScript project, which also sought to clean up JavaScript to some degree. In TurtleScript I've tried to pare down as much of the language as possible, using the smallest number of syntactic forms and JavaScript features as possible, with the smallest possible parser/compiler/runtime system, inspired by Crockford's Simplified JavaScript.

CoffeeScript has some very elegant simplifications: for example, everything is an expression, which reduces the statement/expression syntactic distinction in C-like languages. Making the body of a function into an expression removes unnecessary return statements. Making for and while into expressions is a cute means to introduce (the power of) array comprehensions without additional syntax. CoffeeScript also has a nice way to express functions both with and without lexical this binding (a JavaScript skeleton in the closet).

Unfortunately, the full CoffeeScript language includes many many syntactic forms — even more than full JavaScript. Some of these can trivially be moved into a library, at a slight cost in compactness. While having varied syntax that precisely and concisely expresses programmer intent is certainly admirable, it makes the language harder to learn and, in my opinion, less elegant. For a scalable, learner-friendly language system I like something like NewSpeak more: a language whose goal is to grow smaller, not larger.

Warning: heavy geek content.

Google recently rolled out a new Gmail feature: if you pop open a new little compose or chat window, and then close your main window, the small child window doesn't go away.

This is a pretty esoteric little tweak, but the underlying functionality is quite profound: in order to make this feature work, the entire document context (all the JavaScript responsible for running Gmail's UI) needs to get teleported from the main window out into the child window. For speed and memory reasons, you don't want to run a copy of the main code in the child window — no, you want to wait until just before you close the main window and then instantly teleport the guts of the main window over to the child. How's Google doing that?

In the browser model, separate windows are usually separate security contexts, safely sandboxed from each other. So this magic teleportation trick is also creating a wormhole between the different security domains. My curiosity was piqued, but Google (both blog and search engine) was strangely silent on how their new trick was pulled off.

Here's the story I eventually discovered. Google had long been thinking about a way to make this feature work. Their initial proposal was something called GlobalScript (or sometimes, "SharedScript"). This proposal met resistance and a new simpler solution was found: the "Magic IFRAME".

The guts are hidden inside bug 32848 in webkit's bug tracker. You put all of your application's good stuff inside an <iframe> element — we've guessed that already. You pass your child window a copy of that IFRAME, something like:

function doSomethingCoolThatNeedsANewWindow() {
     var childWin = window.open(...);
     childWin.onload = function() {
         childWin.functionThatTakesScriptContext(mySharedIFrame);
     }
 }

Now, the crux: when your main window is about to close, you just adoptNode the shared <iframe>:

// adoptNode in this case does removeChild() internally
// but does not unload the content
childWin.adoptNode(mySharedIFrame);
childWin.body.appendChild(myShareIFrame);

Voila! This used to completely unload and reload the iframe, erasing the existing application context, but with this one small hack Chrome (and now Safari, too) suppresses the reload and allows the untouched <iframe> context to teleport over to the child.

This doesn't work on Mozilla yet. And it's a pretty ugly hack, tweaking the behavior in just this one narrow case. (And Mozilla is a little bit cranky about adoptNode() being used without an prior importNode().) But this hack also allows work-arounds for two other long-standing iframe-reparenting "bugs". It suggests that <iframe> is now the <module> tag Crockford wanted, especially now that the <iframe> can be sandboxed in various ways as well. By putting each piece inside an <iframe> you can now build a robust module system for browser JavaScript.

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.

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?

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.

We used Google Wave this past weekend during a practice for January's Mystery Hunt. It was an interesting experience, but Wave needs better group support before it's really usable for large-group collaboration. Further, wave threads with lots of discussion start becoming unwieldy: what usually ends up evolving is a collaboratively-edited document/summary/link forest on top, and lots of discussion and comments trailing off below. This forces you to keep scrolling between the "useful stuff" at top and the end of the comment thread, rapidly vanishing off below. The terrible scrollbar implementation doesn't help. This seems like a basic UI problem — and one that wikis have to some degree, too: anyone who's done any collaborative editing of a wiki knows the temptation to insert little inline comments, which spawn discussions that threaten to overwhelm the text. I suspect the solution is some sort of split view or toggle so you can keep an eye on both the discussion and the document at once — think of the little chat window integrated into a collaboratively-edited Google Spreadsheet, but with history and linking and all that wave goodness.

So, as presently constituted, the web Google Wave app is Not Quite There Yet (there are also some instability, compatibility, and slowness issues, but they seem more straightforward to solve). But the underlying Wave technology remains very exciting, and I believe it's something Sugar should build on, as I've written before.

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.

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.

[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.)

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.)

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.

It seems I missed a nice little Slashdot/Negroponte/Krstić OLPC/Sugar row while I was away in Europe savoring the efficient intercity rail. While Tomeu and OLPCnews choose to blame particular words or phrases ("Sugar", "$100 laptop"), both J5 and gregdek seem to think the Real Problem was the fact that OLPC wouldn't upstream its patches.

I beg to disagree. As I wordily tried to explain in a comment to gregdek's post, I think Ivan is mostly right here: OLPC tried to do "seven new things" (as Mary Lou explained to me when I was hired) -- and "new things" end up costing a lot of debugging and development time, in one of the Iron Laws Of Writing New Code And Making New Hardware. But another problem was just Picking The Wrong Partners. With the exception of the display (one of the few unalloyed successes of the XO hardware), most of our hardware and software partners were working at cross purposes. Red Hat didn't really want to build an embedded OS product, "mesh networking" to Marvel meant household networks between your TV and your stereo with maybe 10 participants, the Geode was an orphaned offering from AMD, the display and flash NAND controller was a unloved one-off, etc. Success is found by aligning your partners' interests with your own.

At Litl our OS partner has many other embedded-systems clients, and has developed the toolsets to handle forks and customization without all the angst I'd grown used to at OLPC. We just say, "we need feature X turned on/off" or "set to Y" or just "somehow Z needs to happen" and it's done. We're not fighting, we're not destabilizing their core OS, we don't waste time with elaborate justifications why This Is The Right Thing To Do. If the change is appropriate to upstream, they upstream it, and maybe the work benefits the other embedded-systems clients. There's no drama, because We All Want The Same Thing.

I think "upstreaming" is entirely the wrong hero for OLPC here. If anything, I think OLPC's best hope is to continue to aggressively innovate -- no one buys a computer because its code has been upstreamed. Unfortunately, I don't think OLPC has enough current funding to do anything but follow the upstream, so maybe this current round of praise for Fedora-ization is just the old cliché: making a virtue of necessity.

Over the 4th of July weekend, I released SDR 0.5, now with a GWT/GAE frontend you can check out at square-dance.appspot.com. It's still incomplete -- breathing and collision resolution need to be hooked up, it doesn't do "centers X sides Y" yet, and it's missing lots of call definitions -- but at least there's something tangible to play with that doesn't require mucking around in a javascript shell. Progress!

(Oh, and if you click '+' and then 'Add to Home Screen' when looking at square-dance.appspot.com in Safari on your iPhone, you get a cute "there's an app for that" mobile version.)

So, yesterday I posted a entry discussing how Google Wave actually implements the collaborative vision Sugar (and OLPC) were working towards. (It's a shame we didn't have better contacts with Google while I was at OLPC; Google was actually on OLPC's board, and beta-ing Waves would have been a very fruitful partnership.)

If you agree with the premise: what should the next steps in a Waves-ification of Sugar be? Eventually Google promises to release "the lion's share" of its source code, for both server and client, so getting the google server installed on the school server is one task — but not one which can be done immediately. Implementing Network Principles is another necessary precondition, in order to use Wave's DNS-based participant naming system ("SuzyQStudent@lima.peru.schoolserver.laptop.org" or whatever). That's something which can be done now. What else?

Eventually, when the source code drops, making the waves client work offline would be important, since Waves (and embedded gadgets) basically replace Write and Sugar's bulletin board. Waves edit XML trees, so porting existing activities to use XML-based file formats will go far in integrating them into a new Wave World Order. I haven't seen any demo of a waves-based drawing activity/gadget (tuxpaint is a favorite of most kids), so Waves Paint would be a fun project if you want to start playing with the Waves extension APIs.

More controversially, work on Waves-enabling a next-gen Journal could be interesting. As predicted by proponents of the Journal for some time, the "wave of the future" (so to speak) is filesystem-independent storage. Waves in Google's demo are titled and searched like email messages, not as "documents" in a filesystem hierarchy. However, we had repeated requests to unify Journal storage and traditional filesystems, for (a) better interoperability with existing systems, and (b) sneakernet collaboration. In my mind, this would mean exporting a waves-like view of an existing filesystem, as I proposed for the Journal, where directories are interpreted as slightly-special tag markers. One could imagine implementing a "Wave Server" based around this idea, in effect using the filesystem as the wave database. With the magic of Wave Federation, these "filesystem" waves can interoperate with other wave clients and servers. This standalone file-based server might also server as the basis for "one child under a tree" wave editing. (For that matter, a robust sneakernet implementation of the Wave Federation Protocol would also be very useful!)

Exciting times! Wave promises to bring OLPC/Sugar's vision of ubiquitous collaboration to life at long last. Google has the funding and development resources to tackle what is in effect a bottom-up reorganization of the software stack. OLPC/SugarLab's role is peripheral but vital: strongly lead the development of offline or "flakey connectivity" aspects of this technology so that it can be used everywhere from the solar-powered jungle to the dense urban cities, and to provide the educational software on top of the platform so that kids can *learn* as they collaborate and create.