Don't Trust. Do Verify.

Thanks to Tateru Nino for disabusing me of the idea that a Second Life viewer actually uploads CIL code to the SL server. That bit of information certainly invalidates a lot of the musing in my previous post. As Emily Litella would say, never mind.

But my misadventure led me to Tateru's blog, which is not only a mother lode of delicious dirt on SL and Linden Lab (and some other interesting companies), but is also full of recommendations for magnificent productivity killers like Dwarf Fortress. I haven't dared try Dwarf Fortress, but I could just feel the usefulness seeping out of my body reading Tateru's description of it.

To be sure, if I were Linden Lab, I'd probably be pretty hesitant to let someone upload completely unrestricted Mono code. But the whole business of cooperating untrusted code is still one that fascinates me. If you want to create an environment in which unknown people load possibly malicious code of unknown quality into a running system without breaking that system, what are your options?

It turns out that more has been written on the topic than I had realized. Either I'm getting better at choosing search terms, or Google is getting smarter about figuring out what I mean, or more stuff is getting indexed (or all three). I'd never previously managed to find anything relevant, but searching last night for “cooperating untrusted code” turned up these three papers:

• Resource Control of Untrusted Code in an Open Network Environment by Paul B. Menage, 2003;
  
• Memory Accounting without Partitions by Adam Wick and Matthew Flatt, 2004; and
  
• Strategies for Memory Accounting of Cooperating Pi-Calculus Processes by Matej Košík and Jiří Šafařík, 2008, which apparently led to a project called Sahara.

I haven't had time to do any more than skim the three papers, but I gather that the first paper's approach is to give each untrusted code its own VM, like Second Life, whereas the other two actually commingle objects created by different programs on a common heap. Intuitively, the latter approach sounds more flexible (and possibly more space-efficient, if some data can have multiple owners), but without having read the papers in any detail, I have trouble visualizing just how much trouble you can get into this way.

It seems to me that in designing a system that accommodates untrusted code, you have to decide early on how and when to restrain code that threatens to crash your server by completely exhausting a critical resource. Do you place a small fixed upper bound on each program's consumption of a resource, as SL does with a script's memory, and hope that the total number of programs is never enough that the resource runs out? Do you allow programs to bid (with some currency or other) on resources, where prices tend towards infinity as a resource runs out? Do you apply some sort of fixed throttle to program actions, as LSL does with its energy and delay costs for each routine that manipulates the virtual world?

Another thing you have to decide is how to treat trusted code imported into your system. For example, assume someone wants to program your system using some well-known library. You firmly believe the library has no issues related to security or inefficiency (yeah, right!), and you're willing to install the library on your system for others to use. But once someone invokes library code, thereby loading it into memory, there's less memory available for all the other programs, even those not using the library. So how do you decide how much common code to allow? Who pays for it?

And finally, Linden Lab has apparently at least dipped its toes into the idea of a more unconstrained scripting interface. Tateru mentions in this post that the idea of other scripting languages has at least been considered (and I gather from her heading that C# is one of those languages), but believes no work is ongoing.

LSL and Its Discontents

Like many software-literate residents of Second Life, I haven't been very impressed with Linden Lab's scripting language, LSL.

How Second Life runs LSL programs (“scripts”) is neat: each script gets its own little 64-kbyte VM, and the state of the script persists—a script is suspended when the object it lives in is removed from the world (by being taken into your inventory), and resumed when the object is put back into the world.

But LSL itself is no gem of programming language design. It's verbose, and the only thing that looks like a data structure is the list. A list can't contain other lists, which pretty much dashes all hopes of using LSL to build any data structure you would recognize from more full-featured programming languages. The paucity of control and data structures makes code repetitious and, in many cases, inefficient.

There are, sort of, ways to impose some large-scale structure on your code, in that scripts can communicate with each other. But there's no built-in protocol that lets scripts view each other as implementing any particular interface, and building such a protocol would eat a good chunk out of your 64k (and the source code for your protocol would need to be replicated in each script).

So what, exactly, would it take to make a better scripting language for Second Life? Knowing that the compiler for LSL lives in the Second Life viewer (rather than on Linden Lab's servers, which might be your first guess), I got intrigued enough by this question the other night to download the source code for the open-source Phoenix viewer and see how LSL is compiled.

As best I can figure out, the viewer compiles scripts to CIL. That makes sense, since I know the Second Life servers run Mono. For most operations that aren't generated inline, LSL calls routines in namespaces called [ScriptTypes]LindenLab.SecondLife, [LslLibrary]LindenLab.SecondLife, or [LslUserScript]LindenLab.SecondLife, but there are also direct calls to [mscorlib]System.Collections.ArrayList. This suggests that the generated code could refer to other things in [mscorlib] (and that the restriction that LSL lists cannot contain other lists is peculiar to LSL, because ArrayList has no such restriction).

For each script, the viewer compiles a single class that extends [LslUserScript]LindenLab.SecondLife.LslUserScript. I'm guessing that that's a fundamental characteristic of the viewer-server protocol for dealing with compiled scripts, so you can't throw in additional supporting classes, not even teeny-weeny ones.

So where do these observations get us? Well, consider three possible strategies for implementing a new scripting language:

1. Entirely within LSL. Write a script that compiles and interprets some other language, or (more likely, because even a small interpreter will have trouble fitting in 64k) several intercommunicating scripts. The several-scripts approach would require saving the execution stack while awaiting a reply from another script—meaning you have to manage your own stack, getting continuations for free (well, not that expensive, anyway).
   
   
2. Within the viewer. Generate CIL, but assume you have access to all of [mscorlib].
   
   
3. In the viewer and (with the assistance of Linden Lab, should such assistance be forthcoming) the server. Generate CIL, but in addition to [mscorlib] and the LindenLab.SecondLife libraries, install and use any additional classes your language's runtime system requires.
   

I've seen rumors that implementations of the first kind (entirely within LSL) for Lisp and Forth exist. However, I wasn't able to track down any actual code, and I suspect these are just myths (someone prove me wrong!). It's hard to imagine that a single-script LSL-based approach would leave much memory for user code, or that a multiple-script approach would run very fast.

An implementation of the second kind (entirely within the viewer) is more flexible, but [mscorlib] is not, by itself, ideally suited as a runtime library for a small scripting language. You'd probably wind up needing to generate the contents of your runtime library along with user code, and replicate it in every 64k VM that uses your language, which is not very encouraging. And I'm not sure whether the Second Life Terms of Service would allow you to run a viewer with an altered compiler without the permission of Linden Lab.

The only practical approach might be the third. I haven't talked with Linden Lab about it, or know anyone who has, so I have no idea how open they'd be to the suggestion of a new scripting language not developed in-house, or to installing the language's libraries on their servers. I do imagine they'd want any such libraries to be compact, which probably rules out any of the larger existing programming languages out there.

One thing I don't think you'd need to do is change any of the existing LSL routines for interacting with the Second Life virtual world itself. These routines (whose names all begin with ll) appear in the generated CIL to have perfectly ordinary interfaces that should work for any language compiled for Mono (although some of the routines might have had friendlier calling conventions if more data types were available).

What would a new scripting language actually look like? The first thing that comes to mind is something Lisp-like; a common representation for code and data sidesteps the need to design serialization conventions, and makes it easy to ship little bits of code around from one place to another. Don't like the way some other Second Life object is behaving? Just send it a new behavior!

I have some vague ideas for the design of a small, statically-typed Lisp that (aside from its static typing) looks a little like Clojure. But that's a project I'd rather not get sucked into right now. And almost any scripting language with a little bit of thought given to its design would be an improvement over LSL.

Fluorescent, Incandescent, or LED?

A couple of weeks have gone by since the Scala Lift Off in Mountain View, which was a blast. I would have blogged about it right away, except that my copy of Civilization V arrived the same day as the Lift Off, and Civ ate my homework.

I particularly enjoyed the Lift Off sessions by Daniel Spiewak and by Martin Odersky himself. Both are exceptionally good at taking a complicated concept and presenting it so clearly that it doesn't look complicated at all.

For example, I had read the Fighting Bit Rot with Types paper but not fully digested it. The light bulb went off over my head when Martin described the implicit builders used by Scala collections as Prolog axioms. So that's what's going on.

Public Constructors Considered Harmful: Or, the Amazing Misadventures of HashSet and HashMap

A few months ago I thought I'd try my hand at an implementation of hash array mapped tries. This is the data structure used by Scala (and Clojure) for immutable hash sets and maps. The data structure provides copy-on-write semantics with reasonably fast update and, after each update, a high degree of sharing between the old and new versions of the structure.

My purposes in this adventure were twofold:

• To see whether I could come up with variations that improve on the performance of the standard Scala implementations.
  
• To see whether I could browbeat Scala's type system into letting me use a single implementation for both sets and maps.

I managed to achieve the latter goal, although I went down a number of blind alleys before I got there. This was my first project with much use of higher-kinded types, and it took me a while to wrap my mind around the idea that I was, in effect, writing compiletime functions of types that produce new types. That's a powerful idea, but not what I wanted to get to in this post.

Trait Hierarchies with Lots of Variables Can Be Slow

My first attempt at the hash array mapped trie class hierarchy looked something like this (HashMap, type parameters, and most other details omitted—and we all know what's in the details):

  trait HAMT { ... }
  trait EmptyNode extends HAMT { ... }
  trait InternalNode extends HAMT { ... array of nodes ... }
  trait Leaf1 extends HAMT { ... leaf node with one element ... }
  class HashSet extends ... Scala collection stuff ...
      with EmptyNode {
    def this () = ... constructor for an empty set ...
    ...
  }
  class InternalNodeHashSet extends HashSet with InternalNode
  class Leaf1HashSet extends HashSet with Leaf1

This struck me as a natural phrasing of the solution: each of the components of a hash trie is itself a valid hash trie (at least the way I wrote it), and also a valid hashed set or map.

I got this approach to work, and compared its speed with the standard HashSet. Alas, it was a good deal slower. Profiling led me to conclude that the problem lay in the way variable accessor methods work in traits: control flow runs through an interface, a static method, and an instance method in such a way that the JVM doesn't realize it can inline an access to an object's own instance variable.

Is-A vs. Has-A

So I went back to the drawing board and came up with:

  abstract class HAMT { ... }
  class EmptyNode extends HAMT { ... }
  class InternalNode extends HAMT { ... array of nodes ... }
  class Leaf1 extends HAMT { ... leaf node with one element ... }
  class HashSet (hamt: HAMT)
      extends ... Scala collection stuff ... {
    def this () = ... constructor for an empty set ...
    ...
  }

Now a HashSet has-a HAMT (note the parameter to HashSet's primary constructor), but is-not-a HAMT. Not quite the way I had thought of it originally, but not inconsistent.

Performancewise, reading this data structure runs just a wee bit slower than the standard HashSet. In fact, the difference is small enough that it might be accounted for entirely by the extra level of reference indirection entailed in the has-a relationship (the standard HashSet, having its own implementation, needs no such indirection).

Many of the variations I tried out did result in faster adds and removes than the current Scala implementation, and also in more compact data structures. This is not too surprising, since the 2.8.0 scala.collection.immutable.HashSet is a preliminary implementation. Comments in the source code say that specialized node types exist to optimize small numbers of leaves, but those nodes aren't there when you read the code. (I'm not sure why modifying the official HashSet is so slow compared to mine. It may be because I do have several different types of specialized nodes, and those nodes have custom versions of the add and remove methods.)

Public Constructors Considered Harmful

The slightly slower read time of the has-a approach irks me. I'd like to speed it up (and rescue my original intuition that a hashed set is-a HAMT) by doing this:

  abstract class HAMT { ... }
  class EmptyNode extends HAMT { ... }
  class InternalNode extends HAMT { ... array of nodes ... }
  class Leaf1 extends HAMT { ... leaf node with one element ... }
  trait HashSet extends ... Scala collection stuff ... { ... }
  class EmptyNodeHashSet extends HashSet with EmptyNode
  class InternalNodeHashSet extends HashSet with InternalNode
  class Leaf1HashSet extends HashSet with Leaf1

This looks a lot like my first hierarchy, except that HashSet is now a trait, and the HAMTs are now classes. Data members are all inherited from classes, not traits, which should be fast.

But something is broken: you can no longer say new HashSet(). HashSet is now a trait, not a class, and so you can't invoke a constructor on it. You can package up a HashSet with a nice factory method (as indeed Scala does for the class scala.collection.immutable.HashSet), but to get rid of the public constructor, you'd have to remove something from the published interface.

So now I finally come to the point of my post (you knew I would—or did you?): public constructors are bad. They commit the implementation of a type to be a class, even though the day may come when you want your type to graduate to traithood.

I'm not the only one who's cranky about this; Gilad Bracha has a post that comes at the topic from a slightly less Javacentric point of view.

A better language than we have now could keep most of the beloved Java-style OO paraphernalia (like insisting on completely constructed objects) but refuse to allow constructors to be more visible than protected. This would force object construction by anyone who's not a subtype of the type in question to go through a factory method. And a really good language would try to generate the appropriate factory methods automatically, as Scala does for case classes.

Descent from the Summit

Just back from wallowing in geekery at another JVM Language Summit. These things always leave me overcaffeinated, exhausted, and completely thrilled.

My big discovery this year is that everyone more or less agrees on what the pain points in the JVM are, in terms of performance and convenience. The people who work on Oracle's (formerly Sun's) JVMs largely mentioned the same desiderata as the people who write languages for the JVM, which are also the things I've wanted as a library writer and occasional author of weird bytecode hacks. Those include structs and value types, arrays that behave well with type parameters and can themselves be value types, and unerased type arguments, all things I would have used recently if I had them.

Of course, just catching the attention of the movers and shakers doesn't mean a quick solution is around the corner. I attended a workshop in 1998 where many of the attendees were quite insistent that they needed value types, and James Gosling agreed and said they ought to go into Java “soon”…

The Psychology of Syntax: Lemon Meringue Pie, Functional-Style

A lemon meringue pie results from baking in a preheated oven for 10 minutes, or until golden brown, a baked pastry shell filled with a lemon filling produced by stirring and boiling until thick the whisked combination of egg yolks and a sugar mixture obtained from whisking together sugar, flour, cornstarch, and salt and adding water, lemon juice, and zest topped with a meringue, spread to seal the edges at the crust, created by whipping until peaks form the mixture resulting from gradually adding sugar to egg whites whipped until foamy.

Functional style is mathematically elegant, but except in small doses, most people find imperative style a lot more readable (as in the original from which this recipe was derived).

Bon appétit!

Hash Table Performance: the Not Always Completely Told Story

Here is a story everyone knows, but with an ending that maybe not everyone knows.

How do you find a piece of information in a data structure? If you want to do so efficiently, generally you use either an array or a hash table.

Your typical Von Neumann machine has only one really efficient data structure built into its architecture: namely, the array, which allows you to map an integer index into a memory location. If the contents of your array are instances of some data type with a fixed maximum size, you can premultiply the index by that size and thereby map the index to a value of the data type stored in the array. If your data type is implemented as pointer to some structure, you can effectively drop the maximum-size constraint (because all array elements are the size of a pointer), at the cost of a pointer dereference on each array element access.

Looking up something in an array generally requires constant (O(1)) time, whereas finding a particular value in a data structure without an array (such as a linked list) takes time proportional to the size of the data structure (O(n)).

Arrays are fine if each thing you want to look up has a number, and if the set of numbers assigned is compact enough that the array fits easily in memory. But not everything you want to find out about is easy to represent as a number. For example, you'll want to order an address book by name, not by assigning a number to everyone you know.

Hash functions are functions that take a value (the “key”) and return an integer (a “hash code”). For a given value, the hash code must always be the same (a hash function is a pure function of the value). The key value is not itself usually an integer (although it can be, which is useful when you look something up using a noncompact set of integers as lookup keys). A hash function argument is often a text string, but it makes sense to transform just about any type of value into a hash code (which is why Java puts hashCode at the top of the type hierarchy, in Object). For example, if you want to keep track of information by object type, you can use a java.lang.Class instance as a hash key.

Hash functions are typically used in a conjunction with a hash table, which is an array whose index is a hash code (or a truncation of a hash code, in the common case where the hash function produces a larger range of values than the size of the array). The hash table has a mechanism for dealing with hash collisions, to cover the case where more than one value has the same truncated hash code. You can view a hash table as an array indexed by something other than an integer, and because the key lookup operation is an array index operation, which is O(1), hash table performance can often be taken to be O(1).

A hash table is more complicated than an array, however, because a hash table usually needs to include its index values within its entries. Except in the case of perfect (collision-free) hashing, you must ensure that the key you think you're looking up is really present in the table—that you haven't instead reached an entry that happens to have the same truncated hash code as the one you want. This typically entails comparing the key you're given with the copy of the key stored in the hash table to entry, to make sure they're the same.

The real performance characteristics of a hash table depend on several factors:

• The time to compute the hash code on an index value. This time is actually O(n), where n is the size of input to the hash function, which might be nontrivial (consider a hash code that examines every character of a long string. If you use the same value as an index more than once, it may be worthwhile to cache the hash code. java.lang.String, for example, caches the hash code for a Java string.)
  
  
• The mechanism used by the hash table to deal with collisions. In hash tables that allocate larger arrays as they grow (the usual strategy), collisions are few, and the overall cost of the array reallocations is amortized O(1), so this cost can typically be ignored.
  
  
• The time required to check whether the index value is valid by comparing it with the index value stored in the hash table. Like the computation of the hash code itself, in the general case, this is O(n) in the size of the data compared. (To ensure that a hash table behaves both efficiently and consistently, you typically want to examine exactly the same components of an index value in both the hash function and the comparison for equality.)

So in fact, hash table performance is not strictly O(1), because it depends on the speed of the hash and equality-check functions applied to the table's keys. For many data structures, however, keys are small (of fixed size, or with a reasonably small maximum size), so that calling the performance O(1) is no more than a little white lie.

Pictures of the Superdesk

The completed desk, partly raised. It goes several inches lower, or a good deal higher, so that it's quite comfortable for both sitting and standing.

I use the mat on the floor when I'm standing to keep my feet from getting tired.

And I heartily recommend the book sitting on my desk, Coders at Work. It's inspiring to see how much great work some people have done, and also a little depressing to see how much I have yet to learn, but mostly it's eye-opening to learn where the experts agree and disagree on how to go about the craft of writing software.

Dragon's Demise, Desk's Design

The copy of Dragon Naturally Speaking that I ordered back in January is no longer with us. As I guessed, it turned out to be too strange to be talking to my computer in the house I share with my partner. I gave it to a friend of mine who has an attic office where he's unlikely to disturb his wife by talking to a machine.

In the brief experimentation I did with Dragon, it was difficult to adjust the microphone close enough that it could hear me talking at a normal volume. And even when I did so, the recognition rate was very low—less than 10%. Since I invested no effort in further effort in figuring out How to Train My Dragon, I don't know how much or how quickly that might improve.

Other people I've since talked to who have experimented with speech recognition software had mixed reviews, but the consensus seemed to be that the technology is still rough around the edges. Given my experience with the microphone, I doubt I'll pursue speech recognition anymore until it advances a lot farther—ideally to the point where you don't actually have to wear the microphone.

Another experiment I'm conducting in smoothing the human-computer interface looks more promising. My partner and I have been building me a sit-stand desk, so that I don't have to spend all day in the same position. I ordered a motorized desk frame from GeekDesk, and we got a piece of butcher block countertop from Ikea to use as the desktop. We also got a Workrite monitor arm for the new 28-inch Hanns G monitor I got from Costco (to keep me from constantly bending my neck down to look at the laptop screen) and a Workrite keyboard tray arm (so I can position the laptop keyboard at a comfortable angle). We cut the butcher block to size and made an additional cutout in it for the keyboard tray to keep the overall desktop size about 48 by 32 inches. Today we finished sanding and oiling the desktop and attached the frame and keyboard arm. Tomorrow, if all goes according to plan, we'll attach the keyboard tray, and move the monitor arm (which I've temporarily attached to an old manually adjustable desk to try it out) to the new desk. And that should be it—I won't have to take computing sitting down any longer!

Postcard from the Bleeding Edge

I love Scala. It's so expressive, it's almost not like writing code at all. It's more like just thinking.

I hate Scala. The official beta release of 2.8 is out, and my existing code doesn't compile anymore. I get a bunch of errors related to the way Scala redesigned its collection classes.

And then when I fix those errors, I get a bunch of deprecation warnings related to my favorite Scala feature, the case class. This has me so irked that I screwed up my courage and made my first post to the Scala mailing lists about it.

It's clear that Scala is still a young language that makes substantial changes from release to release, and that it has not yet achieved the near-perfect stability (or is it fossilization?) of Java.

So does this instability mean the end of my romance with Scala? No. I don't have any installed code base to worry about. And to the extent that I understand the changes in Scala 2.8.0, they mostly seem like a good idea. So for now at least, I'm willing to be tossed in the wake of Scala's developers and deal with whatever they come up with.

It was just a lover's quarrel. Scala and I are fine now. At least until a better language comes along.

Are You a Man, or a Mouse? Or a Joystick?

Maybe the Aerobic Keyboard is a little closer to realization. An article on the front page of yesterday's New York Times talks about how hardware and software have progressed to the point where controlling electronic devices by gestures may soon become common.

And this site describes an experimental project (still in existence?) that effectively lets you use your body as a joystick to move through Second Life.

Computer users of the world, arise! You have nothing to lose but your flab!

Typing and Dancing

One of the biggest problems with computers is that you can't dance and type at the same time.

In a world where people spend ever-longer periods of time in front of computers, the fact that interacting with the computer general requires a near-motionless seated posture has major implications for the health and fitness of society as a whole.

Perhaps my best unrealized invention is the Aerobic Keyboard, which would use cameras to recognize large gestures made using your arms and legs, and interpret them as characters typed. This solves the typing and dancing problem by turning dancing into typing. However, gestures vigorous enough to give you a decent workout might be problematic in small cubicles.

I was talking the other night with a guy in Second Life who solves the Typing and Dancing Problem in a different way. He has a copy of Dragon Naturally Speaking, the speech recognition software. When he visits a dance club in SL, he stands in front of a big-screen monitor with a wireless headset microphone and a wireless mouse, cranks up the music, and dances along with his avatar. When he wants to say something, he lets Dragon turn speech into type. He assures me that Dragon is smart enough to decipher what he's saying even over the music.

(In most places in Second Life that play music—and there are a lot of them—voice chat is either turned off or discouraged, as I mentioned in my previous post.)

I've never used speech recognition software, but even if it is as accurate as claimed, I have some doubts about the wisdom of using it when you're not alone in a room. Won't people constantly be asking, “Who ya talkin' to?” But I'm intrigued enough by the concept that I ordered myself a copy of Dragon, which is supposed to magicking its way to me via UPS at this very moment.