null program

Load Libraries in Skewer with Bower

I recently added support to Skewer for loading libraries on the fly using Bower’s package infrastructure. Just make sure you’re up to date, then while skewering a page run M-x skewer-bower-load. It will prompt for a package and version, download the library, then inject it into the currently skewered page.

Because the Bower infrastructure is so simple, Bower is not actually needed in order to use this. Only Git is required, configured by skewer-bower-git-executable, which it tries to configure itself from Magit if it’s been loaded.

Motivation

Skewer comes with a userscript that adds a small toggle button to the top-right corner every page I visit. Here’s a screenshot of the toggle on this page.

When that little red triangle is clicked, the page is connected to Emacs and the triangle turns green. Click it again and it disconnects, turning red. It remembers its state between page refreshes so that I’m not constantly having to toggle.

It’s mainly for development purposes, but it’s occasionally useful to Skewer an arbitrary page on the Internet so that I can poke at it from Emacs. One habit that I noticed comes up a lot is that I want to use jQuery as I fiddle with the page, but jQuery isn’t actually loaded for this page. What I’ll do is visit a jQuery script in Emacs and load this buffer (C-c C-k). As expected, this is tedious and easily automated.

Rather than add specific support for jQuery, I thought it would be more useful to hook into one of the existing JavaScript package managers. Not only would I get jQuery but I’d be able to load anything else provided by the package manager. This means if I learn about a cool new library, chances are I could just switch to my *javascript* scratch buffer, load the library with this new Skewer feature, and play with it. Very convenient.

How it Works

There are a number of package managers out there. I chose Bower because of its emphasis on client-side JavaScript and, more so, because its infrastructure is so simple that I wouldn’t actually need to use Bower itself to access it. In adding this feature to Skewer, I wrote half a Bower client from scratch very easily.

The only part of the Bower infrastructure hosted by Bower itself is a tiny registry that maps package names to Git repositories. This host also accepts new mappings, unauthenticated, for registering new packages. The entire database is served up as plain old JSON.

To find out what versions are available, clone this repository with Git and inspect the repository tags. Tags that follow the Semantic Versioning scheme are versions of the package available for use with Bower. Once a version is specified, look at bower.json in the tree-ish referenced by that tag to get the rest of the package metadata, such as dependencies, endpoint listing, and description.

This is all very clever. The Bower registry doesn’t have to host any code, so it remains simple and small. It could probably be rewritten from scratch in 15-30 minutes. Almost all the repositories are on GitHub, which most package developers are already comfortable with. Package maintainers don’t need to use any tools or interact with any new host systems. Except for adding some metadata they just keep doing what they’re doing. I think this last point is a big part of Melpa’s success.

Bower’s Fatal Weaknesses

Unfortunately Bower has two issues, one of which is widespread, that seriously impacts its usefulness.

Dependency Specification

Even though Bower specifies Semantic Versioning for package versions, which very precisely describes version syntax and semantics, the dependencies field in bower.json is underspecified. There’s no agreed upon method for specifying relative dependency versions.

Say your package depends on jQuery and it relies on the newer jQuery 1.6 behavior of attr(). You would mark down that you depend on jQuery 1.6.0. Say a user of your package is also using another package that depends on jQuery, it’s using the on() method, which requires jQuery 1.7 or newer. It specifies jQuery 1.7.0. This is a dependency conflict.

Of course your package works perfectly fine with 1.7.0. It works fine at 1.6.0 and later. In other package management systems, you would probably have marked that you depend on “>=1.6.0” rather than just 1.6.0. Unfortunately, Bower doesn’t specify this as a valid dependency version. Some package maintainers have gone ahead and specified relative versions anyway, but inconsistently. Some use the “>=” prefix like I did above, some prefix with ”~” (”about this version”), which is pretty useless.

And this leads into the other flaw.

Most Bower Packages are Broken

While some parts of Bower are underspecified, most packages don’t follow the simple specifications that already exist! That is to say, most Bower packages are broken. This is incredibly unfortunate because it means at least half of the packages can’t be loaded by this new Skewer feature.

How are they broken? As of this writing, there are 2,195 packages list in Bower’s registry.

The good news is that most of the important libraries, like jQuery and Underscore, work properly. I’ve also registered two of my JavaScript libraries, ResurrectJS and rng-js, so these can be loaded on the fly in Skewer.

tags: [ javascript emacs ]
? Comments

JavaScript Function Statements vs. Expressions

The JavaScript function keyword has two meanings depending on how it’s used: as a statement or as an expression. It’s a statement when the keyword appears at the top-level of a block. This is known as a function declaration.

function foo() {
    // ...
}

This statement means declare a variable called foo in the current scope, create a closure named foo, and assign this closure to this variable. Also, this assignment is “lifted” such that it happens before any part of the body of the surrounding function is evaluated, including before any variable assignments.

Notice that the closure’s name is separate from the variable name. Except for a certain well-known JavaScript engine, closure/function objects have a read-only name property.

foo.name; // => "foo"

A name is required for function declarations, otherwise they would be no-ops. This name also appears in debugging backtraces.

A function’s name has different semantics in function expressions. The function keyword is an expression when used in an expression position of a statement.

var foo = function() {
    // ...
}

The function expression above evaluates to an anonymous closure, which is then assigned to the variable foo. This is nearly identical to the previous function declaration except for two details.

IIFEs

An immediately-invoked function expression (IIFE), used to establish a one-off local scope, is typically wrapped in parenthesis. The purpose of the parenthesis is to put function in an expression position so that it is a function expression rather than a function declaration.

(function() {
    // ... declare variables, etc.
}());

Another way to put function in an expression position is to precede it with an unary operator. This is an example of being clever instead of practical.

!function() {
    // ... declare variables, etc.
}();

If function is already in an expression position, the wrapping parenthesis are unnecessary. For example,

var foo = function() { return "bar"; }();
foo; // => "bar"

However, it may still be a good idea to wrap the IIFE in parenthesis just to help other programmers read your code. A casual glance that doesn’t notice the function invocation would assume a function is being assigned to foo. Wrapping a function expression with parenthesis is a well-known idiom for IIFEs.

Function Name and Scope

What happens when a function expression is given a name? Two things.

  1. The name will appear in the name property of the closure (if available). Also, the name will also show up in backtraces. This makes naming closures a handy debugging technique.

  2. The name becomes a variable in the scope of the function. This means it’s possible to write recursive function expressions!

function maths() {
    return {
        // ...
        fact: function fact(n) {
            return n === 0 ? 1 : n * fact(n - 1);
        }
    };
}

maths().fact(10); // => 3628800

The fact function is evaluated as a function expression as part of this object literal. The variable fact is established in the scope of the function fact, assigned to the function itself, allowing the function to call itself. It’s a self-contained recursive function.

Pop Quiz: Function Name and Scope

Given this, try to determine the answer to this problem in your head. What does the second invocation of foo evaluate to?

function foo() {
    foo = function() {
        return "function two";
    };
    return "function one";
}

foo(); // => "function one"
foo(); // => ???

Here’s where we come to the major difference between function declarations and function expressions. The answer is "function two". Even though functions declarations create named functions, these functions do not have the implicit self-named variable in its scope. Unless this variable is declared explicitly, the name will refer to a variable in a containing scope.

This has the useful property that a function can re-define itself and be correctly named at the same time. If the function needs to perform expensive first-time initialization, such reassignment can be used to do it lazily without exposing any state and without requiring an is-initialized check on each invocation. For example, this trick is exactly how Emacs autoloading works.

If this function declaration is converted to what appears to be the equivalent function expression form the difference is obvious.

var foo = function foo() {
    foo = function() {
        return "function two";
    };
    return "function one";
};

foo(); // => "function one"
foo(); // => "function one"

The reassignment happens in the function’s scope, leaving the outer scope’s assignment intact. For better or worse, even ignoring assignment lifting, there’s no way to perfectly emulate function declaration using a function expression.

tags: [ javascript ]
? Comments

Inventing a Datetime Web Service

Recently I wanted to experiment with dates in a JavaScript web app. The JavaScript Date object is a fairly decent tool for working with dates. Unfortunately, it has some annoyances,

Existing Datetime Services

So if I don’t trust the local system time to be precise, where can I get a more accurate time? Surely there are web services out there for it, right? NIST operates time.gov and maybe that has a web API for web applications. I don’t need to be super precise – a web API could never be – just within a couple of seconds.

Turns out there isn’t any such web service, at least not a reliable one. Yahoo used to provide one called getTime, but it’s been shut down. In my searches I also came across this:

It supports JSONP, which is almost exactly what I need. Unfortunately, it’s just a free Google App Engine app, so it’s unavailable most of the time due to being over quota. In fact, at the time of this writing it is down.

I could stand up my own server for the task, but that costs both time and money, so I’m not really interested in doing that. It’s liberating to build web apps that don’t require that I run a server. There are so many nice web APIs out there that do the hard part for me. I can just put my app on GitHub’s free static hosting, like this blog. The biggest obstacle is dealing with the same-origin policy. JSONP isn’t always supported and very few of these APIs support CORS, even though they easily could. This is part of the web that’s still maturing. My personal guess is that WebSockets will end up filling this role rather than CORS.

Deriving a Datetime Service

So I was thinking about how I could get around this. Surely some API out there includes a date in its response and I could just piggyback off that. This is when the lightbulb went off: web servers hand out date strings all the time! It’s a standard HTTP header: Date! Even my own web server does this.

function getServerDate() {
    var xhr = new XMLHttpRequest();
    xhr.open('HEAD', '/?nocache=' + Math.random(), false);
    xhr.send();
    return new Date(xhr.getResponseHeader('Date'));
}

This makes a synchronous XMLHttpRequest to the page’s host, being careful to cache bust so that I’m not handed a stale date. I’m also using a HEAD request to minimize the size of the response. Personally, I trust the server’s clock precision more than the client’s. Here it is in action.

Local: ---
Server: ---

This is probably not too exciting because you should be within a couple of seconds of the server. If you’re feeling ambitious, change your local system time by a few minutes and refresh the page. The server time should still be accurate while your local time is whatever incorrect time you set.

Here’s the code for these clocks:

var Demo = Demo || {};

Demo.setDate = function(id, date) {
    document.getElementById(id).innerHTML = date;
};

Demo.offset = Demo.getServerDate() - Date.now();

setInterval(function() {
    var date = new Date();
    Demo.setDate('time-local', date);
    Demo.setDate('time-server', new Date(Demo.offset + date.valueOf()));
}, 1000 / 15);

You know what? I think this is better than some random datetime web service anyway.

tags: [ javascript ]
? Comments

Disc RL in the Media

My Seven Day Roguelike (7DRL) game, Disc RL, was mentioned in a podcast and demonstrated in a YouTube video. Note that the UberHunter, the one who made the YouTube video, is one of the members of the podcast.

An important complaint I discovered about a week after the contest ended, and mentioned very vocally in both the video and the podcast, was my exclusive use of the classic roguelike controls: hjkl yubn (vi keys). Apparently users really dislike these controls, even the hardcore roguelike players. This was a complete surprise to me! These are only controls I’ve ever used and I didn’t realize other players were using anything different, except for perhaps the numpad. Most of my experience with roguelikes has been on laptops, so the numpad simply wasn’t an option.

Fortunately, as a couple of them had found, these fine-movement controls weren’t that important thanks to the auto-movement features. That was the second surprise: autoexplore sounded like a foreign idea to the podcast. I stole that from Dungeon Crawl Stone Soup, a roguelike I consider second only to NetHack. Dungeon navigation tedious, so I think of autoexplore as a standard feature these days. What sorts of roguelikes these guys playing if autoexplore is a fairly new concept?

Eben Howard made an really interesting suggestion to take auto-movement further. If there had been a key to automatically retreat to safe corridor, manual movement would have been almost unnecessary. That will definitely be a feature in my next 7DRL.

Oddly, UberHunter didn’t make much use of auto-movement in his video. When I play Disc RL, the early game is dominated by the autoexplore (o) and ranged attack (f) keys. Until I come across the first ranged unit (viruses, V), there’s no reason to use anything else.

That’s where the YouTube video is kind of disappointing. He didn’t get far enough to see tactical combat, the real meat of the game. That doesn’t kick in until you’re dealing with ranged units. Eben in the podcast did get this far, fortunately, so it was at least discussed. This issue suggests that I should have made tactical combat show up earlier in the game. My original concern was giving the player enough time to get accustomed to Disc RL before throwing harder (i.e. ranged) monsters at them. I didn’t want to scare potential players off right away.

Also surprising in the YouTube video, UberHunter seemed to be confused about using hyperlinks in the help system, worried that clicking them would break something. He kept trying to open the links in new tabs, which wouldn’t work because they’re JavaScript “hyperlinks.” Disc RL is a single-page application and that’s how single-page applications work. I don’t know if there would be any way to fix this to be more friendly. Single-page applications are still fairly new and I think web users, especially longer-experienced web users, are still getting accustomed to them.

Even though only one of these reviewers thought my game was interesting, getting this rich feedback was still really exciting for me. When you’re doing something that truly isn’t interesting or important, no one says anything at all.

tags: [ game media ]
? Comments

Userspace Threading in JavaScript

There was an interesting Daily Programmer problem posted a couple of weeks ago: write a userspace threading library. I decided to do it in JavaScript, building it on top of setTimeout. Remember that JavaScript is single-threaded by specification, so this will be a nonpreemptive, cooperative system.

Start by creating the Thread prototype. As thread constructors usually work, it accepts the function to be run in that thread.

function Thread(f) {
    this.alive = true;
    this.schedule(f);
}

The schedule method schedules a function to be run in that thread. It’s not really meant for users to use directly. I’ll define it in a moment.

Only one thread actually runs at a time, so globally keep track of the which one is running at the moment.

Thread.current = null;

Now here’s the core method that makes everything work, runner. It accepts a function of arbitrary arity and returns a function that runs the provided function in this thread.

Thread.prototype.runner = function(f) {
    var _this = this;
    return function() {
        if (_this.alive) {
            try {
                Thread.current = _this;
                f.apply(this, arguments);
            } finally {
                Thread.current = null;
            }
        }
    };
};

The runner sets the current thread to the proper value, calls the function, then clears the current thread. If the thread is no longer active, nothing happens.

With that in place, schedule is defined like this,

Thread.prototype.schedule = function(f) {
    setTimeout(this.runner(f), 0);
};

It creates a runner function for f and schedules it to run as soon as possible on JavaScript’s event loop using setTimeout. Queuing up on the event loop is the cooperative part of all this. Other threads and events may already be queued with a timeout of 0, so they run first.

Technically this is all that’s needed. To yield, schedule a function and return.

function() {
    // ... do some work ...
    Thread.current.schedule(function() {
        // ... do more work ...
    });
}

I don’t want the user to need to think about Thread.current, so here’s a convenience yield function.

Thread.yield = function(f) {
    Thread.current.schedule(f);
};

Now to use it,

function() {
    // ... do some work ...
    Thread.yield(function() {
        // ... do more work ...
    });
}

Halting a thread is easy. Any scheduled functions for this thread will not be invoked, as specified in the runner method.

Thread.prototype.destroy = function() {
    this.alive = false;
};

There’s one more situation to worry about: callbacks. Imagine an asynchronous storage API.

// ... in thread context ...
storage.getValue(function(value) {
    // doesn't run in thread context
});

In order to run in the thread the library user would need to create a runner function for the current thread. To avoid making them worry about Thread.current and runner, provide another convenience function, wrap. There may be a better name for it, but I couldn’t think of it.

Thread.wrap = function(f) {
    return Thread.current.runner(f);
};

Fixing the callback,

// ... in thread context ...
storage.getValue(Thread.wrap(function(value) {
    // ... also in thread context ...
}));

Threading Demo

To demonstrate threading I’ll make a thread that continuously fetches random numbers from a server and displays them.

Here’s a simple-httpd servlet for generating numbers. The route for this servlet will be /random.

(defservlet random text/plain ()
  (princ (random* 1.0)))

Since I’m doing this interactively with Skewer on the blank demo page, make a tag for displaying the number.

var h1 = document.createElement('h1');
document.body.appendChild(h1);

Here’s the function that will run in the thread. It fetches a number asynchronously, displays it, then recurses. Notice that Thread.yield() acts like a trampoline, providing free tail-call optimization! This is because the stack is cleared before the provided function is invoked.

function random() {
    var xhr = new XMLHttpRequest();
    xhr.open('GET', '/random', true);
    xhr.send();
    xhr.onload = Thread.wrap(function() {
        h1.innerHTML = xhr.responseText;
        Thread.yield(random);
    });
};

I set onload after calling send just for code organization purposes. That code is evaluated after send is called. As far as I know this should work fine.

Now to create a thread!

var foo = new Thread(random);

The heading flashes with random numbers as soon as the thread is created. Even though this thread is continuously running, it’s frequently yielding. Everything remains responsive, including the ability to stop the thread.

foo.destroy();

As soon as this is evaluated, the heading stops being updated. I think that’s pretty neat!

Performance

I haven’t tested performance, but I imagine it’s awful. Especially because of that frequent use of the apply method. You wouldn’t want CPU-intensive operations to cooperate like this. Fortunately, in my demo above I’m manipulating the DOM and waiting on a server response, so the performance penalties of threading should be negligible.

tags: [ javascript lisp ]
? Comments

Tracking Mobile Device Orientation with Emacs

Nine years ago I bought my first laptop computer. For the first time I could carry my computer around and do productive things at places beyond my desk. In the meantime a new paradigm of mobile computing has arrived. Following a similar pattern, this month I bought a Samsung Galaxy Note 10.1, an Android tablet computer. Having never owned a smartphone, this is my first taste of modern mobile computing.

Once the technology caught up, laptops were capable enough to fully replace desktops. However, this tablet is no replacement for my laptop. Mobile devices are purely for consumption, so I will continue to use desktops and laptops for the majority of my computing. I’m writing this post on my laptop, not my tablet, for example.

Owning a tablet has opened up a whole new platform for me to explore as a programmer. I’m not particularly interested in writing Android apps, though. I’m obviously not alone in this, as I’ve found that nearly all Android software available right now is somewhere between poor and mediocre in quality. The hardware was worth the cost of the device, but the software still has a long way to go. I’m optimistic about this so I have no regrets.

A New Web Platform

Instead, I’m interested in mobile devices as a web platform. One of the few high-quality pieces of software on Android are the web browsers (Chrome and Firefox), and I’m already familiar with developing for these. Even more, I can develop software live on the tablet remotely from my laptop using Skewer – i.e. the exact same development tools and workflow I’m already using.

What’s new and challenging is the user interface. Instead of traditional clicking and typing, mobile users tap, hold, swipe, and even tilt the screen. Most challenging of all is probably accommodating both kinds of interfaces at once.

One of the first things I wanted to play with after buying the tablet was the gyro. The tablet knows its acceleration and orientation at all times. This information can be accessed in JavaScript using a fairly new API. The two events of interest are ondevicemotion and ondeviceorientation. Using simple-httpd I can transmit all this information to Emacs as it arrives.

Instead of writing a new servlet for this, to try it out I used skewer.log(). Connect a web page viewed on the tablet to Skewer hosted on the laptop, then evaluate this in a js2-mode buffer on the laptop.

window.addEventListener('devicemotion', function(event) {
    var a = event.accelerationIncludingGravity;
    skewer.log([a.x, a.y, a.z]);
});

Or for orientation,

window.addEventListener('deviceorientation', function(event) {
    skewer.log([event.alpha, event.beta, event.gamma]);
});

These orientation values appeared in my *skewer-repl* buffer as I casually rolled the tablet on one axis. The units are obviously degrees.

[157.4155398727678, 0.38583511837777246, -44.61023992234689]
[155.4477623728871, -0.6438986350040569, -44.69645057005079]
[154.32208572596647, -0.7516393196323073, -45.79730289443301]
[155.437674183483, -0.48375529832044045, -46.406449900466015]
[156.2974174150692, 0.21938214098430556, -47.482812581579154]
[154.85869270791937, 0.11046702400456986, -48.67378583696511]
[153.3284161451347, -0.9344782009891125, -48.61755630462298]
[154.11860073021347, -0.6553947505116874, -49.949668589018074]
[155.85919247792117, 0.05473832995756562, -49.84400214746339]
[156.92487274317241, 0.4946305069438346, -49.86369016774595]
[158.06542554210534, 0.712759801803332, -49.61875275392013]
[159.356905031128, 1.3387109941852697, -49.9372717956745]

It would be neat to pump these into a 3D plot display as they come in, such that my laptop displays the current tablet orientation on the screen as I move it around, but I didn’t see any quick way to do this.

Here are some acceleration values at rest. Since I took these samples on Earth the units are obviously in meters per second per second.

[-0.009576806798577309, 0.31603461503982544, 9.816226959228516]
[-0.047884032130241394, 0.3064578175544739, 9.806650161743164]
[-0.009576806798577309, 0.28730419278144836, 9.787496566772461]
[0.009576806798577309, 0.3064578175544739, 9.816226959228516]
[-0.06703764945268631, 0.3256114423274994, 9.797073364257812]
[-0.047884032130241394, 0.2968810200691223, 9.864110946655273]
[-0.028730420395731926, 0.2968810200691223, 9.576807022094727]
[-0.019153613597154617, 0.363918662071228, 9.691728591918945]
[-0.05746084079146385, 0.3734954595565796, 10.199298858642578]

Now that I have the hardware for it, I really want to use this API to do something interesting in a web application. I just don’t have any specific ideas yet.

tags: [ emacs javascript ]
? Comments

Prototype-based Elisp Objects with @

Last weekend I had the itch to play around with a multiple-inheritance prototype-based object system in lisp. It would look a lot like JavaScript’s object system but wanted to try experimenting some different ideas. My favorite lisp to hack in is Emacs Lisp, so that’s what I built it on. What I ended up with is actually pretty neat. Despite the lack of reader macros in Elisp, I still managed to introduce new syntax by manipulating symbols at compile time.

See the README for a quick demonstration. What follows is the long explanation.

It’s called @, due to the syntax that it adds to Elisp as a domain-specific language. It’s a mini-language, really. The name is also a challenge to the code that supports Elisp, because so much of it – including emacs-lisp-mode and Paredit – doesn’t properly handle @ in identifiers. Even Maruku, the Markdown to HTML translator I use for this blog, has bugs that won’t allow it to handle the @ characters in my code, so I had to forgo most syntax highlighting for this post.

Fortunately require does manage just fine.

(require '@)

Objects in @ are vectors with the symbol @ as the first element. The rest of the elements are implementation specific, but, at the moment, the second element is a plist (property list) of all of that object’s properties.

The root object of @ is @, and all other objects are instances of this object, either directly or indirectly. Because it’s prototype based, creating a new object is a matter of extending one or more (multiple-inheritance) existing objects. This is done with the function @extend.

;; Create a brand new object
(defvar foo (@extend @))

If no objects are given to @extend, @ will be used as the parent object, so it’s not necessary as an argument above. This is actually very important, as objects that don’t inherit from @ will not work at all! I’ll get into that detail in a bit. Additionally, @extend accepts keyword arguments, which become properties on the created object.

The function @ is used to access properties on an object. Remember, Elisp is a lisp-2 meaning that variables and functions exist in their own namespaces. This means there can be both a variable @ (the root object) and function @ (property accessor).

(setf rectangle (@extend :width 3 :height 4))
(@ rectangle :width)  ; => 3
(@ rectangle :height)  ; => 4

The @ function is also setf-able, so setting properties should be obvious to any lisper.

(setf (@ rectangle :width) 13)
(@ rectangle :width)  ; => 13

Like JavaScript, methods are just functions stored in properties on an object. In @, the first argument for a method is the object itself, which is called @@ by convention.

(setf (@ rectangle :area)
  (lambda (@) (* (@ @@ :width) (@ @@ :height))))

(funcall (@ rectangle :area) rectangle)  ; => 52

New Syntax

Here’s the first really neat part. I find all that (@ @@ ...) business to be visually unpleasing. Fortunately this can be fixed by adding syntax. The macro def@ transforms variables that look like @: into these @ accessors. The following declaration is equivalent to the lambda assignment above. It’s meant to be very convenient.

(def@ rectangle :area ()
  (* @:width @:height))

This macro walks the body of the function at compile-time (macro expansion time) and transforms these symbols into the full @ calls above. Like most lisp macros, this has no run-time performance cost.

Because using funcall all the time and remembering to pass the object as the first argument is tedious, the @! function is provided for calling methods.

(@! rectangle :area)  ; => 52

The @: variables become function calls when in function position.

(def@ rectangle :double-area ()
  (* 2 (@:area))

In a lisp-1 this would happen for free, but in Elisp this situation expands to the @! form.

Inheritance

This rectangle is starting to look like a nice re-usable object. There’s a @ convention for this: prefix “class” object names with @.

(setf @rectangle rectangle)

Now to create new rectangle objects.

(setf foo (@extend @rectangle :width 3 :height 7.1))
(@! foo :area)  ; => 21.3

Notice that the foo object doesn’t actually have an :area property on itself. It was found on its parent, @rectangle by inheritance. :width and :height were not looked up on the parent because they’re already bound on foo.

Here’s another re-usable prototype. Notice that @: variables are also setf-able – using push in this case.

(defvar @colored (@extend :color ()))

(def@ @colored :mix (color)
  (push color @:color))

The object system has multiple-inheritance, so colored rectangles can be created from these two objects. The parent objects of an object are listed in the :proto property as a list (similar to JavaScript’s __proto__), which can be modified at any time to change an object’s prototype chain.

(defvar foo (@extend @colored @rectangle :width 10 :height 4))

(@! foo :area)  ; => 40
(@! foo :mix :red)
(@! foo :mix :blue)
(@ foo :color)  ; => (:blue :red)

Even though the initial property was read from the parent, the assignment (push), like all assignments, actually occurred on foo.

Setters and Getters

Remember how I said that objects that don’t eventually inherit from @ will be broken? This is because properties are actually set and accessed through :set and :get methods. That is, @ calls these methods as needed. The @ object provides the default actions for these. An interesting part of the @ code: initially setting :set on @ is a circularity problem, so there’s a special bootstrap step to accomplish it.

By providing your own you can fundamentally change how your object works. For example, here’s an @immutable mix-in which prevents all property assignments. It’s provided as part of @.

(defvar @immutable (@extend))

(def@ @immutable :set (property _value)
  (error "Object is immutable, cannot set %s" property))

This :set method will be found before the @ :set method, so it gets overridden.

Remember how I said all object have a :proto that can be used to modify the objects inheritance? This can be used to freeze an object’s properties in place. Here’s a :freeze method for all objects.

(def@ @ :freeze ()
  "Make this object immutable."
  (push @immutable @:proto))

Pretty cool, eh?

The :get method can be used to provide virtual properties.

(defvar @squares (@extend))

(def@ @squares :get (property)
  (if (numberp property)
      (expt property 2)
    (@^:get property)))  ; explained in a moment

(mapcar (lambda (n) (@ @squares n)) '(0 1 2 3 4))
; => (0 1 4 9 16)

I use this technique in the @vector class under lib/ to expose the elements of the internal vector as if they were properties. Brian used this trick to make a @buffer prototype that wraps Emacs’ buffers, with methods provided virtually by :get. For example, the :string property would return a lambda that calls buffer-string.

With multiple-inheritance and these setters and getters, there are a lot of interesting mix-in possibilities. I’m only just discovering some of them now.

Supermethods

Sometimes it’s really useful to call supermethods. There’s syntax for this: @^:. This calls the next method of that name in the prototype chain. For example, here’s a @watchable mix-in (also provided by @) that allows other code to be notified of changes to an object. It needs to override :set but still call the original :set.

(defvar @watchable (@extend :watchers nil))

(def@ @watchable :watch (callback)
  (push callback @:watchers))

(def@ @watchable :unwatch (callback)
  (setf @:watchers (remove callback @:watchers)))

(def@ @watchable :set (property new)
  (dolist (callback @:watchers)
    (funcall callback @@ property new))
  (@^:set property new))

This behavior is also used for constructors. By convention, the :init method is the constructor. It should generally call the next constructor with (@^:init). @ has a no-op, no-argument :init method to bottom-out this process.

(def@ @rectangle :init (width height)
  (@^:init)
  (setf @:width width @:height height))

(@! (@! @rectangle :new 13.2 2.1) :area) ; => 27.72

As shown, the :new method provided by the @ object combines both @extend and :init to provide simple single-object inheritance.

The Cost of @

In the lib/ directory there are a bunch of example objects implemented: including @vector, @queue, @stack, and @heap. I found these to be very enjoyable to write, and they’ve been the testing grounds for @. @heap uses an internal @vector instance and exercises @’s features the most.

The performance cost of @ very apparent with @heap. Even byte-compiled it’s slower than the naive implementation (compose push and sort) for even as high as 1,000 elements. While I think @ leads to elegant code, there’s still plenty to do for performance. It’s comically slow.

This really caught Brian’s interest, because it was an opportunity to put on his programming language designer’s hat – which I believe to be his favorite hat. He’s been trying different caching strategies to reduce all the walking of the prototype chain. This effort can be found in the other repository branches and in his fork. The system is so dynamic that cache invalidation is a really complex problem.

Every time a property is set, @ has to find the :set property for that object, which generally means walking all the way up to @. Because :proto can be modified at any time, every property look-up requires computing the precedence order (lazily). This all makes property assignment quite expensive! I can understand why real object systems aren’t this flexible. It comes at a high price.

tags: [ lisp emacs ]
? Comments

Precise JavaScript Serialization with ResurrectJS

One of the problems I needed to solve while writing my 7DRL was serializing the game’s entire state for a future restore. It needed to automatically save the game so that the player could close their browser/tab and continue the game later from where they left off. I attempted to use HydrateJS, but finding it inadequate for the task I rolled my own solution from scratch.

After the week ended, I ripped my solution out of the game, filled in the rest of the missing features, and created a precise serialization library called ResurrectJS. It can do everything HydrateJS is meant to do and more: Dates, RegExps, and DOM objects.

It works with all the major browsers, including You Know Who.

To demonstrate, here’s another Greeter prototype.

function Greeter(name) {
    this.name = name;
}
Greeter.prototype.greet = function() {
    return "Hello, my name is " + this.name;
};

var kelsey = new Greeter('Kelsey');
kelsey.greet();
// => "Hello, my name is Kelsey"

ResurrectJS can serialize kelsey for storage, including behavior. I’m creating new Resurrect objects each time just to show that this definitely works across different instances. Nothing up my sleeves! There’s no reason to avoid reusing Resurrect objects because the only state they maintain between method calls is their configuration.

var string = null;
string = new Resurrect().stringify(kelsey);
// => '[{"#":"Greeter","name":"Kelsey"}]'

kelsey;
// => {"name":"Kelsey","#id":null}

Notice that the serialization format is a bit unusual: it’s wrapped in an array. It’s still a valid JSON encoding. Also notice that kelsey gained a new property, #id, assigned to null, but this property was not encoded. I’ll explain all this below.

Here’s object resurrection.

var zombie = null;
zombie = new Resurrect().resurrect(string);
// => {"#":"Greeter","name":"Kelsey"}

zombie.greet();
// => "Hello, my name is Kelsey"

zombie === kelsey;  // A whole new object
// => false

The resurrected object has a # property. As explained before this is used to link the object back into the prototype chain so that its behavior is restored.

What’s special now, which I didn’t need in my game, is that identity, including circularity, is properly maintained! For example,

var necromancer = new Resurrect();
necromancer.stringify([kelsey, kelsey]);
// => '[[{"#":1},{"#":1}],{"#":"Greeter","name":"Kelsey"}]'

var array = necromancer.resurrect(string);
array[0] === array[1];
// => true

The encoding should begin to reveal itself now. There’s only one Greeter object serialized and two {'#': 1} objects – references into the top-level array.

Identity and Equality Review

Just to make sure everyone’s on the same page I’m going to go over the difference between identity and equality. Identity is referential: testing for it is effectively comparing memory pointers. Equality is structural: testing for it walks the structures recursively.

In JavaScript the === operator tests equality for primitive values (numbers, strings) and identity for objects.

2 === 2;
// true, these values are equal

({foo: 2} === {foo: 2});
// false, these are equal but different object instances

JavaScript has no operator for testing object equality and writing a function to do the job is surprisingly complicated. Underscore.js has such a function and it’s about 100 lines of code.

JSON maintains object equality but not object identity. Due to the former it can be used to fake an equality test.

Object.prototype.equals = function(that) {
    return JSON.stringify(this) === JSON.stringify(that);
};

({foo: 2}).equals({foo: 2});
// => true

However, keys are encoded in insertion order, so this is really fragile. Bencode would be better suited (sorted keys), except that it supports few of JavaScript’s types.

({a: 1, b: 2}).equals({b: 2, a: 1});
// => false (incorrect), due to ordering

ResurrectJS extends JSON to maintain identity as well as equality across serialization. It does so through the use of references, as explained below.

In functional languages, such as Haskell or most of Clojure, there is little to no practical distinction between these two concepts. When objects are immutable it makes no difference to a program if they are identical. Everything is a value.

Serialization Algorithm

The clever algorithm used by ResurrectJS was thought up by Brian while I discussing the problem with him. Unlike HydrateJS, the serialized form doesn’t follow the original structure’s form. While walking the data structure, copies of objects are placed into an array as they’re visited. When an object is first seen, it is tagged with an #id property corresponding to the copy’s position in the array. If we come across an object with a non-null #id we know we’ve seen it before and skip over it.

Most importantly, these copies don’t actually have any direct references to other objects. Instead these properties are replaced with references to objects in other positions in the array. Primitive, non-object values aren’t referenced like this. They’re left in place and encoded as part of the object copy.

I’m using the word “object” broadly here to include Arrays. Objects and Arrays are composite and everything else are atoms/values. Composites are things that are made up of atoms, so they need to be taken apart before serialization.

When walking the data structure is complete, the program walks the copy array and sets the #id properties of the original objects to null. This prevents them from being mistaken as already-visited by future ResurrectJS walks (and this was one of HydrateJS’s flaws). If the cleanup config option is set to true, these #id properties are completely removed with delete, which has performance implications for those objects.

Finally, the copy array is serialized by JSON.stringify(). That’s it! Because objects are identified by their position in the copy array they don’t need identifiers attached to them when encoded.

In the array example above {'#': 1} is a reference to the second object in the copy array. The first object in the copy array is the original array being serialized. For example, here’s a circular reference,

var circle = [];
circle.push(circle);
necromancer.stringify(circle);
// => '[[{"#":0}]]'

The first object in the copy array is an array that contains a reference to itself.

JSON doesn’t support undefined but I get it for free with this scheme: any time I come across undefined I replace it with a reference to the object at index -1. This will always be undefined!

string = necromancer.stringify([undefined]);
// => '[[{"#":-1}]]'

Deserialization

To deserialize, the string is parsed as regular JSON resulting in the final copy array, which is walked. Prototypes are properly linked and references are replaced with the appropriate object from the array. The first object in the array is the root of the data structure (the very first object seen during serialization), so it is returned as the result. Simple!

Special Values

ResurrectJS handles Dates automatically, treating them as atomic values.

var object = {date: new Date(Math.pow(10, 12))};
string = necromancer.stringify(object);
// => '[{"date":{"#.":"Date","#v":["2001-09-09T01:46:40.000Z"]}}]'

necromancer.resurrect(string).date.toString();
// => "Sat Sep 08 2001 21:46:40 GMT-0400 (EDT)"

When the program comes across one of these special values, a “constructor” object is placed in the copy. On deserialization, not only are references restored, but special values are also reconstructed. The #. field indicates the constructor and the #v field provides the constructor’s arguments as an array. Applying a constructor was a non-trivial issue.

A consequence of treating Dates as values is that ResurrectJS doesn’t maintain their identity. Having the same Date in two places on a data structure will result in two different date objects after deserialization.

var date = new Date();
string = necromancer.stringify([date, date]);
array = necromancer.resurrect(string);
array[0] === array[1];
// => false

If the user was intending on mutating the Date and having it update Dates (the same one) elsewhere in the structure, this will break it. In my opinion, people mutating Dates deserve whatever is coming to them.

Here’s a RegExp being serialized,

string = necromancer.stringify(/abc/i);
// => '{"#.":"RegExp","#v":["abc","i"]}'

necromancer.resurrect(string).test('abC');
// => true

If you were watching carefully you might notice there’s no wrapper array. If an atomic value is stringified directly then the copy array process is not performed.

Here’s one of the most interesting values to serialize: a DOM element.

var h1 = document.createElement('h1');
h1.innerHTML = 'Hello';
necromancer.stringify(h1);
// => '{"#.":"Resurrect.Node","#v":["<h1>Hello</h1>"]}'

document.body.appendChild(necromancer.resurrect(string));
// (the heading appears on the page)

It uses XMLSerializer to serialize the DOM element into XML. The counterpart to XMLSerializer is DOMParser, but, unfortunately, DOMParser is near useless. Instead I create a wrapper div, shove the string in as innerHTML, and pull the DOM element out. It works beautifully.

Configuration

The Resurrect constructor accepts a configuration object. Check the documentation for all of the details. It lets you control the prefix used for the intrusive property names, in case you need # for yourself. You can control prototype relinking and post-serialization cleanup, as mentioned before.

necromancer = new Resurrect({
    prefix: '__',
    cleanup: true,
    revive: false
});

I’m really quite proud of how this library turned out. As far as I know it’s the only library that can actually do all this. It’s tempting to pull it into Skewer so that it can transmit data structures between Emacs Lisp and JavaScript as perfectly as possible, but I’m afraid that the properties I’m adding during serialization are too intrusive.

tags: [ javascript ]
? Comments

JavaScript Fantasy Name Generator

Also in preparation for my 7-day roguelike I rewrote the RingWorks fantasy name generator in JavaScript. It’s my third implementation of this generator and this one is also the most mature by far.

Try it out by playing with the demo (GitHub).

The first implementation was written in Perl. It worked by interpreting the template string each time a name was to be generated. This was incredibly slow, partly because of the needless re-parsing, but mostly because the parser library I used had really poor performance. It’s literally millions of times slower than this new JavaScript implementation.

The second implementation I did in Emacs Lisp. I didn’t actually write a parser. Instead, an s-expression is walked and interpreted for each name generation. Much faster, but I missed having the template syntax.

The JavaScript implementation has a template compiler. There are five primitive name generator prototypes – including strings themselves, because anything with a toString() method can be a name generator – which the compiler composes into a composite generator following the template. The neatest part is that it’s an optimizing compiler, using the smallest composition of generators possible. If a template can only emit one possible pattern, the compiler will try to return a string of exactly the one possible output.

typeof NameGen.compile('(foo) (bar)');
// => "string"

Here’s the example usage I have in the documentation. On my junk laptop it can generate a million names for this template in just under a second.

var generator = NameGen.compile("sV'i");
generator.toString();  // => "entheu'loaf"
generator.toString();  // => "honi'munch"

However, in this case there aren’t actually that many possible outputs. How do I know? You can ask the generator about what it can generate. Generators know quite a bit about themselves!

generator.combinations();
// => 118910

var foobar = NameGen.compile('(foo|bar)');
foobar.combinations();
// => 2
foobar.enumerate(); // List all possible outputs.
// => ["foo", "bar"]

After some experience using it in Disc RL I found that it would be really useful to be mark parts of the output to the capitalized. Without this, capitalization is awkwardly separate metadata. So I extended the original syntax to do this. Prefix anything with an exclamation point and it gets capitalized in the output.

For example, here’s a template I find amusing. There are 5,113,130 possible output names.

!BsV (the) !i

Here are some of the interesting output names.

Quisey the Dork
Cunda the Snark
Strisia the Numb
Pustie the Dolt
Blhatau the Clown

Mostly as an exercise, I also added tilde syntax, which reverses the component that follows it. So ~(foobar) will always emit raboof. I don’t think this is particularly useful but having it opens the door for other similar syntax extensions.

If you’re making a procedurally generated game in JavaScript, consider using this library for name generation!

tags: [ javascript game interactive ]
? Comments

A Seedable JavaScript PRNG

In preparation for my 7-day roguelike, I developed a seedable pseudo-random number generator library. Half of it is basically a port of BrianScheme’s PRNG.

JavaScript comes with an automatically-seeded global uniform PRNG, Math.random(). This is suitable for most purposes, but if repeatability and isolation is desired – such as when generating a roguelike dungeon – it’s inadequate. I also wanted to be able to sample from different probability distributions, particularly the normal distribution and the exponential distribution.

The underlying number generator is the elegant RC4. Seeds are strings and anything else (except functions) is run through JSON.stringify(). Characters above code 255 are treated as two-byte values. If no seed is provided it will grab some of the available entropy for the job. To generate a uniform random double-precision value, 7 bytes (56 bits) are generated to account for the full 53-bit mantissa.

All other distributions sample from the uniform number generator, so bits are twiddled in only one place. Moreso, it means that Math.random() can be used as the core random number generator. My RC4 implementation is about 10x slower than V8’s Math.random(), so if all you care about is the probability distributions, not the seeding, then you could benefit from better performance. Just provide Math.random as the “seed”.

Here’s an example of it in action. I’m seeding it with an arbitrary object and generating six normally-distributed values. The output should be exactly the same no matter what JavaScript engine is used.

(function(array, n) {
    var rng = new RNG({foo: 'bar'});
    for (var i = 0; i < n; i++) {
        array.push(parseFloat(rng.normal().toFixed(4)));
    }
    return array;
}([], 6));
// => [0.807, -0.9347, -1.4543, -0.2737, 0.5064, -1.7342]

Provided probability distributions:

As far as the extras go, in my game I only ended up using the exponential distribution, for generating monster-spawning events. I intended to use the normal distribution for map generation, but, to save time, I used rot.js for that purpose.

As far as testing goes, I basically just exported the output to GNU Octave so that I could eyeball the histogram and do some basic statistical checks. Everything looks reasonable, so I assume it’s implemented correctly. “That’s the problem with randomness. You can never be sure.”

Using the same seed as above, here are some histograms of the first 10,000 samples for different probability distributions.

Uniform:

Normal:

Exponential:

Gamma (mean = 4):

tags: [ javascript ]
? Comments
Fork me on GitHub