Older blog entries for cananian (starting at number 71)

CoffeeScript and TurtleScript

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.

Syndicated 2010-07-28 20:31:54 from C. Scott Ananian

Adopting an IFRAME

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.

Syndicated 2010-07-16 06:11:54 (Updated 2011-02-21 04:03:53) from C. Scott Ananian

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.

Syndicated 2010-05-27 17:46:33 from C. Scott Ananian

Congratulations, OLPC!

Posted via LiveJournal.app.

Syndicated 2010-05-27 17:06:56 from C. Scott Ananian

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?

Syndicated 2010-01-10 20:58:52 from C. Scott Ananian

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.

Syndicated 2009-12-31 04:15:15 from C. Scott Ananian

Hunting with Google Wave

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.

Syndicated 2009-11-24 18:49:03 (Updated 2009-11-24 18:52:15) from C. Scott Ananian

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.

Syndicated 2009-11-19 19:27:35 (Updated 2009-11-20 16:10:06) from C. Scott Ananian

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.

Syndicated 2009-11-04 19:27:15 (Updated 2009-11-05 03:36:59) from C. Scott Ananian

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

Syndicated 2009-10-06 07:40:53 (Updated 2009-10-06 15:56:44) from C. Scott Ananian