God Lizard

When designing something new, nothing seems to matter more than getting the terminology right. If you don't name things precisely—one concept, one word—you're likely to confuse yourself. And if you don't name them concisely, people won't bother to use your terms, and they'll confuse themselves when they try to talk about what you've built.

The API designer's most important tool is the thesaurus. Which, contrary to what you might think, does not come from the Greek words for “god lizard”, but from the word for “treasure”.

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!