null program

Duck Typing vs. Type Erasure

Consider the following C++ class.

#include <iostream>

template <typename T>
struct Caller {
  const T callee_;
  Caller(const T callee) : callee_(callee) {}
  void go() { callee_.call(); }
};

Caller can be parameterized to any type so long as it has a call() method. For example, introduce two types, Foo and Bar.

struct Foo {
  void call() const { std::cout << "Foo"; }
};

struct Bar {
  void call() const { std::cout << "Bar"; }
};

int main() {
  Caller<Foo> foo{Foo()};
  Caller<Bar> bar{Bar()};
  foo.go();
  bar.go();
  std::cout << std::endl;
  return 0;
}

This code compiles cleanly and, when run, emits "FooBar". This is an example of duck typing -- i.e., "If it looks like a duck, swims like a duck, and quacks like a duck, then it probably is a duck." Foo and Bar are unrelated types. They have no common inheritance, but by providing the expected interface, they both work with with Caller. This is a special case of polymorphism.

Duck typing is normally only found in dynamically typed languages. Thanks to templates, a statically, strongly typed language like C++ can have duck typing without sacrificing any type safety.

Java Duck Typing

Let's try the same thing in Java using generics.

class Caller<T> {
    final T callee;
    Caller(T callee) {
        this.callee = callee;
    }
    public void go() {
        callee.call();  // compiler error: cannot find symbol call
    }
}

class Foo {
    public void call() { System.out.print("Foo"); }
}

class Bar {
    public void call() { System.out.print("Bar"); }
}

public class Main {
    public static void main(String args[]) {
        Caller<Foo> f = new Caller<>(new Foo());
        Caller<Bar> b = new Caller<>(new Bar());
        f.go();
        b.go();
        System.out.println();
    }
}

The program is practically identical, but this will fail with a compile-time error. This is the result of type erasure. Unlike C++'s templates, there will only ever be one compiled version of Caller, and T will become Object. Since Object has no call() method, compilation fails. The generic type is only for enabling additional compiler checks later on.

C++ templates behave like a macros, expanded by the compiler once for each different type of applied parameter. The call symbol is looked up later, after the type has been fully realized, not when the template is defined.

To fix this, Foo and Bar need a common ancestry. Let's make this Callee.

interface Callee {
    void call();
}

Caller needs to be redefined such that T is a subclass of Callee.

class Caller<T extends Callee> {
    // ...
}

This now compiles cleanly because call() will be found in Callee. Finally, implement Callee.

class Foo implements Callee {
    // ...
}

class Bar implements Callee {
    // ...
}

This is no longer duck typing, just plain old polymorphism. Type erasure prohibits duck typing in Java (outside of dirty reflection hacks).

Signals and Slots and Events! Oh My!

Duck typing is useful for implementing the observer pattern without as much boilerplate. A class can participate in the observer pattern without inheriting from some specialized class or interface. For example, see the various signal and slots systems for C++. In constrast, Java has an EventListener type for everything:

A class concerned with many different kinds of events, such as an event logger, would need to inherit a large number of interfaces.

tags: [ java cpp ]
? Comments

Northbound 7DRL 2014

Last year I participated in 7DRL 2013 and submitted a game called Disc RL. 7DRL stands for Seven Day Roguelike -- a challenge to write a roguelike game inside of one week. I participated again this year in 7DRL 2014, with the help of Brian. My submission was called Northbound. To play, all you need is a modern web browser.

It only takes about 10-15 minutes to complete.

It's a story-driven survival game about escaping northward away from a mysterious, spreading corruption. ("Corruption" seems to be a common theme in my games.) There's no combat and, instead, the game is a series of events with a number of possible responses by the player. For better or worse, other characters may join you in your journey. I coded the core game basically from scratch -- no rot.js this year -- and Brian focused on writing story events and expanding the story system.

Just as Disc RL was inspired primarily by NetHack and DCSS, this year's submission was heavily, to an embarrassing extent, inspired by two other games: The Banner Saga (LP) and One Way Heroics (LP).

Writing events was taking a lot longer than expected, and time ran short at the end of the week, so there aren't quite as many events as I had hoped. This leaves the story incomplete, so don't keep playing over and over trying to reveal it all!

My ultimate goal was to create a game with an interesting atmosphere, and I think I was mostly successful. There's somber music, sounds effects, and ambient winds. The climate changes as you head north, with varying terrain. There's day and night cycles. I intentionally designed the main menu to show off most of this.

The Event System

Events are stored in a handful of YAML files. YAML is a very human-friendly data format that, unlike JSON, is very well suited for writing prose. Here's an example of an event that may occur if you walk on a frozen lake with too many people.

- title: Treacherous ice!
  filter: [inCold, inWater, [minParty, 2]]
  description: >-
    As everyone steps out onto the frozen lake, the quiet, chilled air
    is disrupted by loud cracks of splits forming through the ice.
    Frozen in place, {{game.player.party.[0]}} looks at you as if
    asking you what should be done.

    {{game.player.party.[1]}} says, "Perhaps we should leave some of
    this stuff behind to lighten load on the ice."
  options:
    - answer: Leave behind some supplies before moving further. (-10 supplies)
      scripts: [[supplies, -10]]
      result: Dropping off excess weight keeps the the ice from cracking.
    - answer: Ignore the issue and carry on.
      scripts: [dierandom, [karma, -3]]
      result: >-
        Throwing caution to the wind you move on. Unfortunately the
        ice worsens and cracks. Someone is going in.

Those paragraphs would be difficult to edit and format while within quotes in JSON.

Events can manipulate game state, with other events depending on the state change, effectively advancing story events in order. The longest event chain in the game reveals some of the nature of the corruption. This gets complicated fast, which really slows down event development.

If this is interesting for you to play with, you should easily be able to add your own story events to the game just by appending to the event YAML files.

The Map

I put off map generation for awhile to work on the story system. For the first few days it was just randomly placed trees on an endless grassy field.

When I finally moved on to map generated it was far easier than I expected. It's just a few layers of the same 3D Perlin noise, capable of providing a virtually infinite, seamless expanse of terrain. Water-dirt-grass is one layer. Trees-mountains-highgrass is another layer. The cold/snow is a third layer, which, in addition to Perlin noise, is a function of altitude (more snow appears as you go north).

One obvious early problem was blockage. Occasionally forests would generate that prohibited movement forward, ending the game. Rather than deal with the complexities of checking connectedness, I went with an idea suggested by Brian: add a road that carves its way up the map, guaranteeing correctness. It plows through forests, mountains, and lakes alike all the way to the end of the game. Its curvature is determined by yet another sample into the same 3D Perlin set.

The snow and corruption effects are all dynamically generated from the base tiles. In short, I write the tile onto a hidden canvas, add a white gradient for snow, and desaturate for corruption. This was faster than manually creating three versions of everything.

In Reflection

While I really like the look and sound of Northbound, it's ultimately less fun for me than Disc RL. With the fixed story and lack of procedually-genertaed content, it has little replayability. This would still be the case even if the story was fully fleshed out.

Even now I still play Disc RL on occasion, about a couple of times per month, just for enjoyment. Despite this, I've still never beaten it, which is an indication that I made it much too hard. On the other hand, Northbound is way too easy. The main problem is that running out of the supplies almost immediately ends the game in a not-fun way, so I never really want that to happen. The only way to lose is through intention.

Next year I need to make a game that looks and feels like Northbound but plays like Disc RL.

tags: [ game media ]
? Comments

Emacs Lisp Defstruct Namespace Convention

One of the drawbacks of Emacs Lisp is the lack of namespaces. Every defun, defvar, defcustom, defface, defalias, defstruct, and defclass establishes one or more names in the global scope. To work around this, package authors are strongly encouraged to prefix every global name with the name of its package. That way there should never be a naming conflict between two different packages.

(defvar mypackage-foo-limit 10)

(defvar mypackage--bar-counter 0)

(defun mypackage-init ()
  ...)

(defun mypackage-compute-children (node)
  ...)

(provide 'mypackage)

While this has solved the problem for the time being, attaching the package name to almost every identifier, including private function and variable names, is quite cumbersome. Namespaces can almost be hacked into the language by using multiple obarrays, but symbols have internal linked lists that prohibit inclusion in multiple obarrays.

By convention, private names are given a double-dash after the namespace. If a "bar counter" is an implementation detail that may disappear in the future, it will be called mypackage--bar-counter to warn users and other package authors not to rely on it.

There's been a recent push to follow this namespace-prefix policy more strictly, particularly with the depreciation of cl and introduction of cl-lib. I suspect someday when namespaces are finally introduced, packages with strictly clean namespaces with be at an advantage, somehow automatically supported. Nic Ferrier has proposed ideas for how to move forward on this.

How strict are we talking?

Over the last few years I've gotten much stricter in my own packages when it comes to namespace prefixes. You can see the progression going from javadoc-lookup (2010) where I was completely sloppy about it, to EmacSQL (2014) where every single global identifier is meticulously prefixed.

For a time I considered names such as make-* and with-* to be exceptions to the rule, since these names are idioms inherited from Common Lisp. The namespace comes after the expected prefix. I've changed my mind about this, which has caused me to change my usage of defstruct (now cl-defstruct).

Just as in Common Lisp, by default cl-defstruct defines a constructor starting with make-*. This is fine in Common Lisp, where it's a package-private function by default, but in Emacs Lisp this pollutes the global namespace.

(require 'cl-lib)

;; Defines make-circle, circle-x, circle-y, circle-radius, circle-p
(cl-defstruct circle
  x y radius)

(defvar unit-circle (make-circle :x 0.0 :y 0.0 :radius 1.0))

unit-circle
;; => [cl-struct-circle 0.0 0.0 1.0]

(circle-radius unit-circle)
;; => 1.0

This constructor isn't namespace clean, so package authors should avoid defstruct's default. If the package is named circle then all of the accessors are perfectly fine, though.

To fix this, I now use another, more recent Emacs Lisp idiom: name the constructor create. That is, for the package circle, we desire circle-create. To get this behavior from cl-defstruct, use the :constructor option.

;; Clean!
(cl-defstruct (circle (:constructor circle-create))
  x y radius)

(circle-create :x 0 :y 0 :radius 1)
;; => [cl-struct-circle 0 0 1]

(provide 'circle)

This affords a new opportunity to craft a better constructor. Have cl-defstruct define a private constructor, then manually write a constructor with a nicer interface. It may also do additional work, like enforce invariants or initialize dependent slots.

(cl-defstruct (circle (:constructor circle--create))
  x y radius)

(defun circle-create (x y radius)
  (let ((circle (circle--create :x x :y y :radius radius)))
    (if (< radius 0)
        (error "must have non-negative radius")
      circle)))

(circle-create 0 0 1)
;; => [cl-struct-circle 0 0 1]

(circle-create 0 0 -1)
;; error: "must have non-negative radius"

This is now how I always use cl-defstruct in Emacs Lisp. It's a tidy convention that will probably become more common in the future.

tags: [ emacs lisp elisp ]
? Comments

The Julia Programming Language

Julia is a new programming language primarily intended for scientific computing. It's attempting to take on roles that are currently occupied by Matlab, its clones, and R. "Matlab done right" could very well be its tag-line, but it's more than that. It has a beautiful type system, it's homoiconic, and its generic function support would make a Lisp developer jealous. It still has a long ways to go, but, except for some unfortunate issues, it's off to a great start.

Speaking strictly in terms of the language, doing better than Matlab isn't really a significant feat. Among major programming languages, Matlab's awfulness and bad design is second only to PHP. Octave fixes a lot of the Matlab language, but it can only go so far.

For both Matlab and R, the real strength is the enormous library of toolboxes and functionality available to help solve seemingly any scientific computing task. Plus the mindshare and the community. Julia has none of this yet. The language is mostly complete, but it will take years to build up its own package library to similar standards.

If you're curious about learning more, the Julia manual covers the entire language as it currently exists. Unfortunately anything outside the language proper and its standard library is under-documented at this time.

A Beautiful Type System

One of the first things you'll be told is that Julia is dynamically typed. That is, statically typed (C++, Java, Haskell) versus dynamically typed (Lisp, Python, JavaScript). However, Julia has the rather unique property that it straddles between these, and it could be argued to belong to one or the other.

The defining characteristic of static typing is that bindings (i.e. variables) have types. In dynamic typing, only values and objects have types. In Julia, all bindings have a type, making it like a statically typed language. If no type is explicitly declared, that type is Any, an abstract supertype of all types. This comes into play with generic functions.

Both abstract and concrete types can be parameterized by other types, and certain values. The :: syntax it used to declare a type.

type Point {T}
  x::T
  y::T
end

This creates a Point constructor function. When calling the constructor, the parameter type can be implicit, derived from the type of its arguments, or explicit. Because both x and y have the same type, so must the constructor's arguments.

# Implicit type:
Point(1, -1)
# => Point{Int64}(1,-1)

# Explicit type:
Point{Float64}(1.1, -1.0)
# => Point{Float64}(1.1,-1.0)

Point(1, 1.0)
# ERROR: no method Point{T}(Int64,Float64)

The type can be constrained using <:. If Point is declared like the following it is restricted to real numbers. This is just like Java's Point<T extends Number>.

type Point {T <: Real}
  x::T
  y::T
end

Unlike most languages, arrays aren't built directly into the language. They're implemented almost entirely in Julia itself using this type system. The special part is that they get literal syntax.

[1, 2, 3]
# => Array{Int64,1}

[1.0 2.0; 3.0 4.0]
# => Array{Float64,2}

Each Array is parameterized by the type of value it holds and by an integer, indicating its rank.

The Billion Dollar Mistake

Julia has avoided what some call The Billion Dollar Mistake: null references. In languages such as Java, null is allowed in place of any object of any type. This allowance has lead to many run-time bugs that, if null didn't exist, would have been caught at compile time.

Julia has no null and so there's no way to make this mistake, though some kinds of APIs are harder to express without it.

Generic Functions

All of Julia's functions are generic, including that Point constructor above. Different methods can be defined for the same function name, but for different types. In Common Lisp and Clojure, generic functions are an opt-in feature, so most functions are not generic.

Note that this is significantly different than function overloading, where the specific function to call is determined at compile time. In multimethods, the method chosen is determined by the run-time type of its arguments. One of Julia's notable achievements is that its multimethods have very high performance. There's usually more of a trade-off.

Julia's operators are functions with special syntax. For example, the + function,

+(3, 4)
# => 7

A big advantage is that operators can be passed around as first-class values.

map(-, [1, 2, 3])
# [-1, -2, -3]

Because all functions are generic, operators can have methods defined for specific types, effectively becoming operator overloading (but better!).

function +(p1::Point, p2::Point)
  return Point(p1.x + p1.y, p2.x + p2.y)
end

Point(1,1) + Point(1, 2)
# => Point{Int64}(2,3)

(Note that to write this method correctly, either Point or the method should probably promote its arguments.)

Foreign Function Interface

Julia has a really slick foreign function interface (FFI). Libraries don't need to be explicitly loaded and call interfaces don't have to be declared ahead of time. That's all taken care of automatically.

I'm not going to dive into the details, but basically all you have to do is indicate the library, the function, the return type, and then pass the arguments.

ccall((:clock, "libc"), Int32, ())
# => 2292761

Generally this would be wrapped up nicely in a regular function and the caller would have no idea an FFI is being used. Unfortunately structs aren't yet supported.

Julia's Problems

Not everything is elegant, though. There are some strange design decisions. The two big ones for me are strings and modules.

Confused Strings

Julia has a Char type that represents a Unicode code point. It's a 32-bit value. So far so good. However, a String is not a sequence of these. A Julia string is a byte-array of UTF-8 encoded characters.

Indexing into a string operates on bytes rather than characters. Attempting to index into the middle of a character results in an error. Yuck!

"naïvety"[4]
# ERROR: invalid UTF-8 character index

I don't understand why this behavior was chosen. This would make sense if Julia was an old language and this was designed before Unicode was established (e.g. C). But, no, this is a brand new language. There's no excuse not to get this right the first time. I suspect it has to do with Julia's FFI.

Clunky, Closed Modules

Julia's module system looks like it was taken right out of Scheme's R6RS. This isn't a good thing.

The module definition that wraps the entire module up in a single syntactic unit. Here's an example from the documentation. According to the style guide, the body of the module is not indented out.

module MyModule
using Lib
export MyType, foo

type MyType
  x
end

bar(x) = 2x
foo(a::MyType) = bar(a.x) + 1

import Base.show
show(io, a::MyType) = print(io, "MyType $(a.x)")
end

That final end seals the module for good. There's no opening the module back up to define or redefine new functions or types. If you want to change something you have to reload the entire module, which will obsolete any type instances.

Compare this to Clojure, where the module isn't wrapped up in a syntactical construct.

(ns my.module
  (require : [clojure.set :refer [rename-keys]]))

Common Lisp's defpackage also works like this. At any time you can jump into a namespace and make new definitions.

(in-ns 'my.module)

This is absolutely essential to interactive development. The lack of this makes Julia far less dynamic than it should be. Combined with the lack of a printer, Julia is not currently suitable as an interactive interpreter subprocess (Slime, Cider, Skewer, etc.).

This is a real shame, because I'd like to start playing around with Julia, but right now it feels like a chore. It's needlessly restricted to a C++/Java style workflow.

I'll probably revisit Julia once it's had a few more years to mature. Then we'll see if things have improved enough for real use.

tags: [ rant ]
? Comments

Reimaging a VM from the inside with Debian

Recently I was in a situation where I wanted to spin up a virtual machine in a cloud computing service but the provided operating system selection was meager. The two options were Ubuntu 11.10 (i.e. October 2011) or RHEL 6.3 (June 2012). Worse, these were the desktop versions of these platforms, so they had X.Org installed along with a bunch of desktop applications. These images were not really intended as servers.

As always, I strongly prefer Debian. Ubuntu is derived from Debian so it isn't far from ideal, but I didn't want to deal with such an old version, plus all the desktop cruft. Also, I really just want to use Debian Wheezy (currently stable). It's extremely solid and I know it through and through.

Since there's no way for me to provide my own image, my only option is to install Debian from within the virtual machine. A significant difficulty in this is that I also have no way to provide alternate boot media. I would need to install Debian from within Ubuntu, over top of Ubuntu while it's running. Within these restrictions this may sound like an impossible task.

Fortunately, Debian, being the universal operating system and living up to its name, has a way to do this, and do it cleanly. When I'm done there will be absolutely no trace of Ubuntu left. I could do the same from within the Red Hat system, but working from Ubuntu takes one fewer step. The magic tool for solving this problem is debootstrap. It installs a Debian base system into an arbitrary subdirectory. This is what the official Debian installer uses and it's used to build my live CD. Ubuntu offers this as a normal package, so I don't need to download anything special.

Creating a Pivot

So I've got a way to install Debian from within another Linux installation, but now how can I install Debian over top of Ubuntu? I will ultimately need to use debootstrap on the root of a fresh filesystem. I can't wipe Ubuntu's root partition while it's running. I can't even resize it since that's where / is mounted.

Fortunately for me the person who set up this VM just went through Ubuntu's defaults. This means there's a single primary partition holding the entire Ubuntu installation (sda1), a second extended partition (sda2), and within the extended partition there's a swap partition (sda5).

The swap partition is 1GB, which, while cramped, is plenty of room for a Debian base system. I have no use for an extended partition so I can just blow the whole thing away and install Debian to sda2.

ubuntu# swapoff /dev/sda5
ubuntu# fdisk /dev/sda  # (fix up partitions)
ubuntu# mkfs.ext4 /dev/sda2
ubuntu# mkdir /mnt/debian
ubuntu# mount /dev/sda2 /mnt/debian
ubuntu# debootstrap wheezy /mnt/debian <local-deb-mirror>

Now I have a proper Debian base system installed on a second partition. At this point I could configure Grub to boot into it by default rather than Ubuntu. However, as it stands so far, I would have no way to access it remotely (or at all) since I haven't set anything up. From here I just follow the guide in appendix D and configure it from a chroot,

ubuntu# LANG=C.UTF-8 chroot /mnt/debian /bin/bash
chroot# mount -t proc proc /proc
chroot# dpkg-reconfigure tzdata
chroot# apt-get install linux-image-amd64 locales openssh-server
chroot# passwd

I just copy Ubuntu's /etc/network/interfaces so that the new system uses the same network configuration (DHCP in this case).

ubuntu# cp /etc/network/interfaces /mnt/debian/etc/network/

A create a one-line /etc/fstab, mounting /dev/sda2 as /.

/dev/sda2  /  ext4  defaults  0  1

Finally I overwrite the Ubuntu-installed Grub. I need to set up the devices in order to actually install Grub.

chroot# apt-get install makedev
chroot# cd /dev
chroot# MAKEDEV generic
chroot# apt-get install grub-pc
chroot# update-grub

The Ubuntu system isn't visible to the Grub installer, so the VM will now boot into my tiny Debian system by default.

ubuntu# reboot

Taking Over the Host

After about a minute I can SSH into the VM again. This time I'm in a proper Debian Wheezy system running from sda2! Now the problem is making use of that large partition that still houses Ubuntu. I could try slicing it up and mounting parts of it for Debian, but there's something simpler I can do: repeat the same exact process on the first partition. The Debian system I just set up becomes a pivot for the real installation.

pivot# mkfs.ext4 /dev/sda1
pivot# mkdir /mnt/debian
pivot# mount /dev/sda1 /mnt/debian
pivot# debootstrap wheezy /mnt/debian
(... etc ...)

After installing Grub again, reboot. There may be some way to simply copy the pivot system directly but I'm not confident enough to trust a straight cp -r.

Final Touches

Now I'm running Debian on the large partition. The pivot can be converted back into a swap partition.

debian# mkswap /dev/sda2
debian# swapon /dev/sda2
debian# echo /dev/sda2 swap swap defaults 0 0 >> /etc/fstab

This is now as good as a fresh installation of a Debian base system (i.e. what the cloud provider should have offered in the first place). If it was possible on this cloud, this is where I'd make a snapshot for cloning future VMs. Since that's not an option, should I need more Debian VMs in the future I'll write a pair of shell scripts to do all this for me. An automated conversion process would probably take about 5 minutes.

I love Debian.

tags: [ debian ]
? Comments

Introducing EmacSQL

Yesterday I made the first official release of EmacSQL, an Emacs package I've been working on for the past few weeks. EmacSQL is a high-level SQL database for Emacs. It primarily targets SQLite as a back-end, but it also currently supports PostgreSQL and MySQL.

It's available on MELPA and is ready for immediate use. It depends on the finalizers package I added last week.

While there's a non-Elisp component, SQLite, there are no special requirements for the user to worry about. When the package's Elisp is compiled, if a C compiler is available it will use it to compile a SQLite binary for EmacSQL. If not, it will later offer to download a pre-built binary that I built. Ideally this makes the non-Elisp part of EmacSQL completely transparent and users can pretend Emacs has a built-in relational database.

The official SQLite command line shell is not used even if present, and I'll explain why below.

Just as Skewer jump started my web development experience, EmacSQL has been a crash course in SQL and relational databases. Before starting this project I knew little about this topic and I've gained a lot of appreciation for it in the process. Building an Emacs extension is a very rapid way to dive into a new topic.

If you're a total newb about this stuff like I was and want to learn SQL for SQLite yourself, I highly recommend Using SQLite. It's a really solid introduction.

High-level SQL Compiler

By "high-level" I mean that it goes beyond assembling strings containing SQL code. In EmacSQL, statements are assembled from s-expressions which, behind the scenes, are compiled into SQL using some simple rules. This means if you already know SQL you should be able to hit the ground running with EmacSQL. Here's an example,

(require 'emacsql)

;; Connect to the database, SQLite in this case:
(defvar db (emacsql-connect "~/office.db"))

;; Create a table with 3 columns:
(emacsql db [:create-table patients
             ([name (id integer :primary-key) (weight float)])])

;; Insert a few rows:
(emacsql db [:insert :into patients
             :values (["Jeff" 1000 184.2] ["Susan" 1001 118.9])])

;; Query the database:
(emacsql db [:select [name id]
             :from patients
             :where (< weight 150.0)])
;; => (("Susan" 1001))

;; Queries can be templates, using $s1, $i2, etc. as parameters:
(emacsql db [:select [name id]
             :from patients
             :where (> weight $s1)]
         100)
;; => (("Jeff" 1000) ("Susan" 1001))

A query is a vector of keywords, identifiers, parameters, and data. Thanks to parameters, these s-expression statements should not need to be constructed dynamically at run-time.

The compilation rules are listed in the EmacSQL documentation so I won't repeat them in detail here. In short, lisp keywords become SQL keywords, row-oriented information is always presented as vectors, expressions are lists, and symbols are identifiers, except when quoted.

[:select [name weight] :from patients :where (< weight 150.0)]

That compiles to this,

SELECT name, weight FROM patients WHERE weight < 150.0;

Also, any readable lisp value can be stored in an attribute. Integers are mapped to INTEGER, floats are mapped to REAL, nil is mapped to NULL, and everything else is printed and stored as TEXT. The specifics vary depending on the back-end.

Parameters

A symbol beginning with a dollar sign is a parameter. It has a type -- identifier (i), scalar (s), vector (v), schema (S) -- and an argument position.

[:select [$i1] :from $i2 :where (< $i3 $s4)]

Given the arguments name people age 21, three symbols and an integer, it compiles to:

SELECT name FROM people WHERE age < 21;

A vector parameter refers to rows to be inserted or as a set for an IN expression.

[:insert-into people [name age] :values $v1]

Given the argument (["Jim" 45] ["Jeff" 34]), a list of two rows, this becomes,

INSERT INTO people (name, age) VALUES ('"Jim"', 45), ('"Jeff"', 34);

And this,

[:select * :from tags :where (in tag $v1)]

Given the argument [hiking camping biking] becomes,

SELECT * FROM tags WHERE tag IN ('hiking', 'camping', 'biking');

When writing these expressions keep in mind the command emacsql-show-last-sql. It will display in the minibuffer the SQL result of the s-expression statement before the point.

Schemas

A table schema is a list whose first element is a column specification vector (i.e. row-oriented information is presented as vectors). The remaining elements are table constraints. Here are the examples from the documentation,

;; No constraints schema with four columns:
([name id building room])

;; Add some column constraints:
([(name :unique) (id integer :primary-key) building room])

;; Add some table constraints:
([(name :unique) (id integer :primary-key) building room]
 (:unique [building room])
 (:check (> id 0)))

In the handful of EmacSQL databases I've created for practice and testing, I've put the schema in a global constant. A table schema is a part of a program's type specifications, and rows are instances of that type, so it makes sense to declare schemas up top with things like defstructs.

These schemas can be substituted into a SQL statement using a $S parameter (capital "S" for Schema).

(defconst foo-schema-people
  '([(person-id integer :primary-key) name age]))

;; ...

(defun foo-init (db)
  (emacsql db [:create-table $i1 $S2] 'people foo-schema-people))

Back-ends

Everything I've discussed so far is restricted to the SQL statement compiler. It's completely independent of the back-end implementations, themselves mostly handling strings of SQL statements.

SQLite Implementation Difficulties

A little over a year ago I wrote a pastebin webapp in Elisp. I wanted to use SQLite as a back-end for storing pastes but struggled to get the SQLite command shell, sqlite3, to cooperate with Emacs. The problem was that all of the output modes except for "tcl" are ambiguous. This includes the "csv" formatted output. TEXT values can dump newlines, allowing rows to span an arbitrary number of lines. They can dump things that look like the sqlite3 prompt, so it's impossible to know when sqlite3 is done printing results. I ultimately decided the command shell was inadequate as an Emacs subprocess.

Recently there was some discussion from alexbenjm and Andres Ramirez on an Elfeed post about using SQLite as an Elfeed back-end. This inspired me to take another look and that's when I came up with a workaround for SQLite's ambiguity: only store printed Elisp values for TEXT values! With print-escape-newlines set, TEXT values no longer span multiple lines, and I can use read to pull in data from sqlite3. All of sqlite3's output modes were now unambiguous.

However, after making significant progress I discovered an even bigger issue: GNU Readline. The sqlite3 binary provided by Linux package repositories is almost always compiled with Readline support. This makes the tool much more friendly to use, but it's a huge problem for Emacs.

First, sqlite3 the command shell is not up to the same standards as SQLite the database. Not by a long shot. In my short time working with SQLite I've already discovered several bugs in the command shell. For one, it's not properly integrated with GNU Readline. There's an .echo meta-command that turns command echoing on and off. That is, it repeats your command back to you. Useful in some circumstances, though not mine. The bug is that this echo is separate from GNU Readline's echo. When Readline is active and .echo is enabled, there are actually two echos. Turn it off and there's one echo.

Pseudo-terminals

Under some circumstances, like when communicating over a pipe rather than a PTY, Readline will mostly become deactivated. This would have been a workaround, but when Readline is disabled sqlite3 heavily buffers its output. This breaks any sort of interaction. Even worse, on Windows stderr is not always unbuffered, so sqlite3's error messages may not appear for a long time (another bug).

Besides the problem of getting Readline to shut up, another problem is getting Readline to stop acting on control characters. The first 32 characters in ASCII are control characters. A pseudo-terminal (PTY) that is not in raw mode will immediately act upon any control characters it sees. There's no escaping them.

Emacs communicates with subprocesses through a PTY by default (probably an early design mistake), limiting the kind of data that can be transmitted. You can try this yourself in a comint mode sometime where a subprocess is used (not a socket like SLIME). Fire up M-x sql-sqlite (part of Emacs) and try sending a string containing byte 0x1C (28, file separator). You can type one by pressing C-q C-\. Send that byte and the subprocess dies.

There are two ways to work around this. One is to use a pipe (bind process-connection-type to nil). Pipes don't respond to control characters. This doesn't work with sqlite3 because of the previously-mentioned buffering issue.

The other way to work around this is to put the PTY in raw mode. Unfortunately there's no function to do this so you need to call stty. Of course, this program needs to run on the same PTY, so a start-process-shell-command is required.

(start-process-shell-command name buffer "stty raw && <your command>")

Windows has neither stty nor PTYs (nor any of PTY's issues) so you'll need to check the operating system before starting the process. Even this still doesn't work for sqlite3 because Readline itself will respond to control characters. There's no option to disable this.

There's a package called esqlite that is also a SQLite front-end. It's built to use sqlite3 and therefore suffers from all of these problems.

A Custom SQLite Binary

Since sqlite3 proved unreliable I developed my own protocol and external program. It's just a tiny bit of C that accepts a SQL string and returns results as an s-expression. I'm not longer constrained to storing readable values, but I'm still keeping that paradigm. First, it keeps the C glue program simple and, more importantly, I can rely entirely on the Emacs reader to parse the results. This makes communication between Emacs and the subprocess as fast as it can possibly be. The reader is faster than any possible Elisp program.

As I mentioned before, this C program is compiled when possible, and otherwise a pre-built binary is fetched from my server (popular platforms only, obviously). It's likely EmacSQL will have at least one working back-end on whatever you're using.

Other Back-ends

Both PostgreSQL and MySQL are also supported, though these require the user have the appropriate client programs installed (psql or mysql). Both of these are much better behaved than sqlite3 and, with the stty trick, each can reliably be used without any special help. Both pass all of the unit tests, so, in theory, they'll work just as well as SQLite.

To use them with the example at the beginning of this article, require emacsql-psql or emacsql-mysql, then swap emacsql-connect for the constructors emacsql-psql or emacsql-mysql (along with the proper arguments). All three of these constructors return an emacsql-connection object that works with the same API.

EmacSQL only goes so far to normalize the interfaces to these databases, so for any non-trivial program you may not be able to swap back-ends without some work. All of the EmacSQL functions that operate on connections are generic functions (EIEIO), so changing back-ends will only have an effect on the program's SQL statements. For example, if you use q SQLite-ism (dynamic typing) it won't translate to either of the other databases should they be swapped in.

I'll cover the connections API, and what it takes to implement a new back-end, in a future post. Outside of the PTY caveats, it's actually very easy. The MySQL implementation is just 80 lines of code.

EmacSQL's Future

I hope this becomes a reliable and trusted database solution that other packages can depend upon. Twice so far, the pastebin demo and Elfeed, I've really wanted something like this and, instead, ended up having to hack together my own database.

I've already started a branch on Elfeed re-implementing its database in EmacSQL. Someday it may become Elfeed's primary database if I feel there's no disadvantage to it. EmacSQL builds SQLite with the full-text search engine enabled, which opens to the door to a powerful, fast Elfeed search API. Currently the main obstacle is actually Elfeed's database API being somewhat incompatible with ACID database transactions -- shortsightedness on my part!

tags: [ emacs elisp ]
? Comments

Emacs Lisp Object Finalizers

Problem: You have a special resource, such as a buffer or process, associated with an Emacs Lisp object which is not managed by the garbage collector. You want this resource to be cleaned up when the owning lisp object is garbage collected. Unlike some other languages, Elisp doesn't provide finalizers for this job, so what do you do?

Solution: This is Emacs Lisp. We can just add this feature to the language ourselves!

I've already implemented this feature as a package called finalize, available on MELPA. I will be using it as part of a larger, upcoming project.

In this article I will describe how it works.

Processes and Buffers

Process and buffers are special types of objects. Immediately after instantiation these objects are added to a global list. They will never become unreachable without explicitly being killed. The garbage collector will never manage them for you.

This is a problem for APIs like those provided by the url package. The functions url-retrieve and url-retrieve-synchronously create buffers and hand them back to their callers. Ownership is transfered to the caller and the caller must be careful to kill the buffer, or transfer ownership again, before it returns. Otherwise the buffer is "leaked." The url package tries to manage this a little bit with url-gc-dead-buffers, but this can't be relied upon.

Another issue is when a process is started and is stored in a struct or some other kind of object. There is probably a "close" function that accepts one of these structs and kills the process. But if that function isn't called, due to a bug or an error condition, it will become a "dangling" process. If the struct is completely lost, it will probably be inconvenient to deal with the process -- the "close" function is no longer useful.

With Macros

A common way to deal with this problem is using a with- macro. This macro establishes a resource, evaluates a body, and ensures the resource is properly cleaned up regardless of the body's termination state. The latter is accomplished using unwind-protect. For example, with-temp-buffer,

;; Fetch the first 10 bytes of foo.txt
(with-temp-buffer
  (insert-file-contents "foo.txt" nil 0 10)
  (buffer-string))

This expands (roughly) to the following expression.

(let ((temp-buffer (generate-new-buffer "*temp*")))
  (with-current-buffer temp-buffer
    (unwind-protect
        (progn
          (insert-file-contents "foo.txt" nil 0 10)
          (buffer-string))
      (and (buffer-live-p temp-buffer)
           (kill-buffer temp-buffer)))))

For dealing with open files, Common Lisp has with-open-stream. It establishes a binding for a new stream over its body and ensures the stream is closed when the body is complete. There's no chance for a stream to be left open, leaking a system resource.

However, with- macros aren't useful in asynchronous situations. In Emacs this would be the case for asynchronous sub-processes, such as an attached language interpreter. The extent of the process goes beyond a single body.

Finalizers

What would really be useful is to have a callback -- a finalizer -- that runs when an object is garbage collected. This ensures that the resource will not outlive its owner, restoring management back to the garbage collector. However, Emacs provides no such hook.

Fortunately this feature can be built using weak hash tables and the post-gc-hook, a list of functions that are run immediately after garbage collection.

Weak References

I've discussed before how to create weak references in Elisp. The only weak references in Emacs are built into weak hash tables. Normally the language provides weak references first and hash tables are built on top of them. With Emacs we do this backwards.

The make-hash-table function accepts a key argument :weakness to specify how strongly keys and values should be held by the table. To make a weak reference just create a hash table of size 1 and set :weakness to t.

(defun weak-ref (thing)
  (let ((ref (make-hash-table :size 1 :weakness t :test 'eq)))
    (prog1 ref
      (setf (gethash t ref) thing))))

(defun deref (ref)
  (gethash t ref))

The same trick can be used to detect when an object is garbage collected. If the result of deref is nil, then the object was garbage collected. (Or the weakly-referenced object is nil, but this object will never be garbage collected anyway.)

To check if we need to run a finalizer all we have to do is create a weak reference to the object, then check the reference after garbage collection. This check can be done in a post-gc-hook function.

Registration

To avoid cluttering up post-gc-hook with one closure per object we'll keep a register of all watched objects.

(defvar finalizable-objects ())

(defun register (object callback)
  (push (cons (weak-ref object) callback) finalizable-objects))

Now a function to check for missing objects, try-finalize.

(defun try-finalize ()
  (let ((alive (cl-remove-if-not #'deref finalizable-objects :key #'car))
        (dead (cl-remove-if #'deref finalizable-objects :key #'car)))
    (setf finalizable-objects alive)
    (mapc #'funcall (mapcar #'cdr dead))))

(add-hook 'post-gc-hook #'try-finalize)

Now to try it out. Create a process, stuff it in a vector (like a defstruct), register delete-process as a finalizer, and, for the sake of demonstration, immediately forget the vector.

;;; -*- lexical-binding: t; -*-
(let ((process (start-process "ping" nil "ping" "localhost")))
  (register (vector process) (lambda () (delete-process process))))

;; Assuming the garbage collector has not already run.
(get-process "ping")
;; => #<process ping>

;; Force garbage collection.
(garbage-collect)

(get-process "ping")
;; => nil

The garbage collector killed the process for us!

There are some problems with this implementation. Using cl-remove-if is unwise in a post-gc-hook function. It allocates lots of new cons cells but garbage collection is inhibited while the function is run. The docstring warns us:

Garbage collection is inhibited while the hook functions run, so be careful writing them.

Similarly, all of the finalizers are run within the context of this memory-sensitive hook. Instead they should be delayed until the next evaluation turn (i.e. run-at-time of 0). Some of the finalizers could also fail, which would cause the remaining finalizers to never run. The real implementation deals with all of these issues.

A major drawback to these Emacs Lisp finalizers compared to other languages is that the actual object is not available. We don't know it's getting collected until after it's already gone. This solves the object resurrection problem, but it's darn inconvenient. One possible workaround in the case of defstructs and EIEIO objects is to make a copy of the original object (copy-sequence or clone) and run the finalizer on the copy as if it was the original.

The Real Implementation

The real implementation is more carefully namespaced and its API has just one function: finalize-register. It works just like register above but it accepts &rest arguments to be passed to the finalizer. This makes the registration call simpler and avoids some significant problems with closures.

(let ((process (start-process "ping" nil "ping" "localhost")))
  (finalize-register (vector process) #'delete-process process))

Here's a more formal example of how it might really be used.

(cl-defstruct (pinger (:constructor pinger--create))
  process host)

(defun pinger-create (host)
  (let* ((process (start-process "pinger" nil "ping" host))
         (object (pinger--create :process process :host host)))
    (finalize-register object #'delete-process process)
    object))

To make things cleaner for EIEIO classes there's also a finalizable mixin class that ensures the finalize generic function is called on a copy of the object (the original object is gone) when it's garbage collected.

Here's how it would be used for the same "pinger" concept, this time as an EIEIO class. An advantage here is that anyone can manually call finalize early if desired.

(require 'eieio)
(require 'finalizable)

(defclass pinger (finalizable)
  ((process :initarg :process :reader pinger-process)
   (host :initarg :host :reader pinger-host)))

(defun pinger-create (host)
  (make-instance 'pinger
                 :process (start-process "ping" nil "ping" host)
                 :host host))

(defmethod finalize ((pinger pinger))
  (delete-process (pinger-process pinger)))

It's a small package but I think it can be quite handy.

tags: [ emacs elisp ]
? Comments

Measure Elisp Object Memory Usage with Calipers

A couple of weeks ago I wrote a library to measure the retained memory footprint of arbitrary Elisp objects for the purposes of optimization. It's called Caliper.

Note, Caliper requires predd, my predicate dispatch library. Neither of these packages are on MELPA or Marmalade since they're mostly for fun.

The reason I wanted this was that I came across a post on reddit where someone had scraped 217,000 Jeopardy! questions from J! Archive and dumped them out into a single, large JSON file. The significance of the effort is that it dealt with some of the inconsistencies of J! Archive's data presentation, normalizing them for the JSON output.

When I want to examine a JSON dataset like this I have three preferred options:

(defvar jeopardy
  (with-temp-buffer
    (insert-file-contents "/tmp/JEOPARDY_QUESTIONS1.json")
    (json-read)))

(length jeopardy)
;; => 216930

Here, jeopardy is bound to a vector of 216,930 association lists (alists). I'm curious exactly how much heap memory this data structure is using. To find out, we need to walk the data structure and sum the sizes of everything we come across. However, care must be taken not to count the identical objects twice, such as symbols, which, being interned, appear many times in this data.

Measuring Object Sizes

This is lisp so let's start with the cons cell. A cons cell is just a pair of pointers, called car and cdr.

These are used to assemble lists.

So a cons cell itself -- the shallow size -- is two words: 16 bytes on a 64-bit operating system. To make sure Elisp doesn't happen to have any additional information attached to cons cells, let's take a look at the Emacs source code.

struct Lisp_Cons
  {
    /* Car of this cons cell.  */
    Lisp_Object car;

    union
    {
      /* Cdr of this cons cell.  */
      Lisp_Object cdr;

      /* Used to chain conses on a free list.  */
      struct Lisp_Cons *chain;
    } u;
  };

The return value from garbage-collect backs this up. The first value after each type is the shallow size of that type. From here on, all values have been computed for 64-bit Emacs running on x86_64 GNU/Linux.

(garbage-collect)
;; => ((conses 16 9923172 2036943)
;;     (symbols 48 57017 54)
;;     (miscs 40 10203 18892)
;;     (strings 32 4810027 197961)
;;     (string-bytes 1 104599635)
;;     (vectors 16 103138)
;;     (vector-slots 8 2921744 131076)
;;     (floats 8 12494 5816)
;;     (intervals 56 119911 69249)
;;     (buffers 960 134)
;;     (heap 1024 593412 133853))

A Lisp_Object is just a pointer to a lisp object. The retained size of a cons cell is its shallow size plus, recursively, the retained size of the objects in its car and cdr.

Integers and Floats

Integers are a special case. Elisp uses what is called tagged integers. They're not heap-allocated objects. Instead they're embedded inside the object pointers. That is, those Lisp_Object pointers in Lisp_Cons will hold integers directly. This means to Caliper integers have retained size of 0. We can use this to verify Caliper's return value for cons cells.

(caliper-object-size 100)
;; => 0

(caliper-object-size (cons 100 200))
;; => 16

Tagged integers are fast and save on memory. They also compare properly with eq, which is just a pointer (identity) comparison. However, because a few bits need to be reserved for differentiating them from actual pointers these integers have a restricted dynamic range.

Floats are not tagged and exist as immutable objects in the heap. That's why eql is still useful in Elisp -- it's like eq but will handle numbers properly. (By convention you should use eql for integers, too.)

Symbols and Strings

Not counting the string's contents, a string's base size is 32 bytes according to garbage-collect. The length of the string can't be used here because that counts characters, which vary in size. There's a string-bytes function for this. A string's size is 32 plus its string-bytes value.

(string-bytes "naïveté")
;; => 9
(caliper-object-size "naïveté")
;; => 41  (i.e. 32 + 9)

As you can see from above, symbols are huge. Without even counting either the string holding the name of the symbol or the symbol's plist, a symbol is 48 bytes.

(caliper-object-size 'hello)
;; => 1038

This 1,038 bytes is a little misleading. The symbol itself is 48 bytes, the string "hello" is 37 bytes, and the plist is nil. The retained size of nil is significant. On my system, nil's plist has 4 key-value pairs, which themselves have retained sizes. When examining symbols, caliper doesn't care if they're interned or not, including symbols like nil and t. However, nil is only counted once, so it will have little impact on a large data structure.

Miscellaneous

Outside of vectors, measuring object sizes starts to get fuzzy. For example, it's not possible to examine the exact internals of a hash table from Elisp. We can see its contents and the number of elements it can hold without re-sizing, but there's intermediate structure that's not visible. Caliper makes rough estimates for each of these types.

Circularity and Double Counting

To avoid double counting objects, a hash table with a test of eq is dynamically bound by the top level call. It's used like a set. Before an object is examined, the hash table is checked. If the object is listed, the reported size is 0 (it consumes no additional space than already accounted for).

This automatically solves the circularity problem. There's no way we can traverse into the same data structure a second time because we'll stop when we see it twice.

Using Caliper

So what's the total retained size of the jeopardy structure? About 124MB.

(caliper-object-size jeopardy)
;; => 130430198

For fun, let's see if how much we can improve on this.

json.el will return alists for objects by default, but this can be changed by setting json-object-type to something else. Initially I thought maybe using plists instead would save space, but I later realized that plists use exactly the same number of cons cells as alists. If this doesn't sound right, try to picture the cons cells in your head (an exercise for the reader).

(defvar jeopardy
  (let ((json-object-type 'plist))
    (with-temp-buffer
      (insert-file-contents "~/JEOPARDY_QUESTIONS1.json")
      (setf (point) (point-min))
      (json-read))))

(caliper-object-size jeopardy)
;; => 130430077 (plist)

Strangely this is 121 bytes smaller. I don't know why yet, but in the scope of 124MB that's nothing.

So what do these questions look like?

(elt jeopardy 0)
;; => (:show_number "4680"
;;     :round "Jeopardy!"
;;     :answer "Copernicus"
;;     :value "$200"
;;     :question "..." ;; omitted
;;     :air_date "2004-12-31"
;;     :category "HISTORY")

They're (now) plists of 7 pairs. All of the keys are symbols, and, as such, are interned and consuming very little memory. All of the values are strings. Surely we can do better here. The strings can be interned and the numbers can be turned into tagged integers. The :category values would probably be good candidates for conversion into symbols.

Here's an interesting fact about Jeopardy! that can be exploited for our purposes. While Jeopardy! covers a broad range of trivia, it does so very shallowly. The same answers appear many times. For example, the very first answer from our dataset, Copernicus, appears 14 times. That makes even the answers good candidates for interning.

(cl-loop for question across jeopardy
         for answer = (plist-get question :answer)
         count (string= answer "Copernicus"))
;; => 14

A string pool is trivial to implement. Just use a weak, equal hash table to track strings. Making it weak keeps it from leaking memory by holding onto strings for longer than necessary.

(defvar string-pool
  (make-hash-table :test 'equal :weakness t))

(defun intern-string (string)
  (or (gethash string string-pool)
      (setf (gethash string string-pool) string)))

(defun jeopardy-fix (question)
  (cl-loop for (key value) on question by #'cddr
           collect key
           collect (cl-case key
                     (:show_number (read value))
                     (:value (if value (read (substring value 1))))
                     (:category (intern value))
                     (otherwise (intern-string value)))))

(defvar jeopardy-interned
  (cl-map 'vector #'jeopardy-fix jeopardy))

So how are we looking now?

(caliper-object-size jeopardy-interned)
;; => 83254322

That's down to 79MB of memory. Not bad! If we print-circle this, taking advantage of string interning in the printed representation, I wonder how it compares to the original JSON.

(with-temp-buffer
  (let ((print-circle nil))
    (prin1 jeopardy-interned (current-buffer))
    (buffer-size)))
;; => 45554437

About 44MB, down from JSON's 53MB. With print-circle set to nil it's about 48MB.

tags: [ emacs elisp ]
? Comments

Emacs Byte-code Internals

Byte-code compilation is an underdocumented -- and in the case of the recent lexical binding updates, undocumented -- part of Emacs. Most users know that Elisp is usually compiled into a byte-code saved to .elc files, and that byte-code loads and runs faster than uncompiled Elisp. That's all users really need to know, and the GNU Emacs Lisp Reference Manual specifically discourages poking around too much.

People do not write byte-code; that job is left to the byte compiler. But we provide a disassembler to satisfy a cat-like curiosity.

Screw that! What if I want to handcraft some byte-code myself? :-) The purpose of this article is to introduce the internals of Elisp byte-code interpreter. I will explain how it works, why lexically scoped code is faster, and demonstrate writing some byte-code by hand.

The Humble Stack Machine

The byte-code interpreter is a simple stack machine. The stack holds arbitrary lisp objects. The interpreter is backwards compatible but not forwards compatible (old versions can't run new byte-code). Each instruction is between 1 and 3 bytes. The first byte is the opcode and the second and third bytes are either a single operand or a single intermediate value. Some operands are packed into the opcode byte.

As of this writing (Emacs 24.3) there are 142 opcodes, 6 of which have been declared obsolete. Most opcodes refer to commonly used built-in functions for fast access. (Looking at the selection, Elisp really is geared towards text!) Considering packed operands, there are up to 27 potential opcodes unused, reserved for the future.

The easiest place to access the opcode listing is in bytecomp.el. Beware that some of the opcode comments are currently out of date.

Segmentation Fault Warning

Byte-code does not offer the same safety as normal Elisp. Bad byte-code can, and will, cause Emacs to crash. You can try out for yourself right now,

emacs -batch -Q --eval '(print (#[0 "\300\207" [] 0]))'

Or evaluate the code manually in a buffer (save everything first!),

(#[0 "\300\207" [] 0])

This segfault, caused by referencing beyond the end of the constants vector, is not an Emacs bug. Doing a boundary test would slow down the byte-code interpreter. Not performing this test at run-time is a practical engineering decision. The Emacs developers have instead chosen to rely on valid byte-code output from the compiler, making a disclaimer to anyone wanting to write their own byte-code,

You should not try to come up with the elements for a byte-code function yourself, because if they are inconsistent, Emacs may crash when you call the function. Always leave it to the byte compiler to create these objects; it makes the elements consistent (we hope).

You've been warned. Now it's time to start playing with firecrackers.

The Byte-code Object

A byte-code object is functionally equivalent to a normal Elisp vector except that it can be evaluated as a function. Elements are accessed in constant time, the syntax is similar to vector syntax ([...] vs. #[...]), and it can be of any length, though valid functions must have at least 4 elements.

There are two ways to create a byte-code object: using a byte-code object literal or with make-byte-code. Like vector literals, byte-code literals don't need to be quoted.

(make-byte-code 0 "" [] 0)
;; => #[0 "" [] 0]

#[1 2 3 4]
;; => #[1 2 3 4]

(#[0 "" [] 0])
;; error: Invalid byte opcode

The elements of an object literal are:

Parameter List

The parameter list takes on two different forms depending on if the function is lexically or dynamically scoped. If the function is dynamically scoped, the argument list is exactly what appears in lisp code.

(byte-compile (lambda (a b &optional c)))
;; => #[(a b &optional c) "\300\207" [nil] 1]

There's really no shorter way to represent the parameter list because preserving the argument names is critical. Remember that, in dynamic scope, while the function body is being evaluated these variables are globally bound (eww!) to the function's arguments.

When the function is lexically scoped, the parameter list is packed into an Elisp integer, indicating the counts of the different kinds of parameters: required, &optional, and &rest.

The least significant 7 bits indicate the number of required arguments. Notice that this limits compiled, lexically-scoped functions to 127 required arguments. The 8th bit is the number of &rest arguments (up to 1). The remaining bits indicate the total number of optional and required arguments (not counting &rest). It's really easy to parse these in your head when viewed as hexadecimal because each portion almost always fits inside its own "digit."

(byte-compile-make-args-desc '())
;; => #x000  (0 args, 0 rest, 0 required)

(byte-compile-make-args-desc '(a b))
;; => #x202  (2 args, 0 rest, 2 required)

(byte-compile-make-args-desc '(a b &optional c))
;; => #x302  (3 args, 0 rest, 2 required)

(byte-compile-make-args-desc '(a b &optional c &rest d))
;; => #x382  (3 args, 1 rest, 2 required)

The names of the arguments don't matter in lexical scope: they're purely positional. This tighter argument specification is one of the reasons lexical scope is faster: the byte-code interpreter doesn't need to parse the entire lambda list and assign all of the variables on each function invocation.

Unibyte String Byte-code

The second element is a unibyte string -- it strictly holds octets and is not to be interpreted as any sort of Unicode encoding. These strings should be created with unibyte-string because string may return a multibyte string. To disambiguate the string type to the lisp reader when higher values are present (> 127), the strings are printed in an escaped octal notation, keeping the string literal inside the ASCII character set.

(unibyte-string 100 200 250)
;; => "d\310\372"

It's unusual to see a byte-code string that doesn't end with 135 (#o207, byte-return). Perhaps this should have been implicit? I'll talk more about the byte-code below.

Constants Vector

The byte-code has very limited operands. Most operands are only a few bits, some fill an entire byte, and occasionally two bytes. The meat of the function that holds all the constants, function symbols, and variables symbols is the constants vector. It's a normal Elisp vector and can be created with vector or a vector literal. Operands reference either this vector or they index into the stack itself.

(byte-compile (lambda (a b) (my-func b a)))
;; => #[(a b) "\302\134\011\042\207" [b a my-func] 3]

Note that the constants vector lists the variable symbols as well as the external function symbol. If this was a lexically scoped function the constants vector wouldn't have the variables listed, being only [my-func].

Maximum Stack Usage

This is the maximum stack space used by this byte-code. This value can be derived from the byte-code itself, but it's pre-computed so that the byte-code interpreter can quickly check for stack overflow. Under-reporting this value is probably another way to crash Emacs.

Docstring

The simplest component and completely optional. It's either the docstring itself, or if the docstring is especially large it's a cons cell indicating a compiled .elc and a position for lazy access. Only one position, the start, is needed because the lisp reader is used to load it and it knows how to recognize the end.

Interactive Specification

If this element is present and non-nil then the function is an interactive function. It holds the exactly contents of interactive in the uncompiled function definition.

(byte-compile (lambda (n) (interactive "nNumber: ") n))
;; => #[(n) "\010\207" [n] 1 nil "nNumber: "]

(byte-compile (lambda (n) (interactive (list (read))) n))
;; => #[(n) "\010\207" [n] 1 nil (list (read))]

The interactive expression is always interpreted, never byte-compiled. This is usually fine because, by definition, this code is going to be waiting on user input. However, it slows down keyboard macro playback.

Opcodes

The bulk of the established opcode bytes is for variable, stack, and constant access opcodes, most of which use packed operands.

Except for the last item, each kind of instruction comes in sets of 8. The nth such instruction means access the nth thing. For example, the instruction "2" copies the third stack item to the top of the stack. An instruction of "9" pushes onto the stack the value of the variable named by the second element listed in the constants vector.

However, the 7th and 8th such instructions in each set take an operand byte or two. The 7th instruction takes a 1-byte operand and the 8th takes a 2-byte operand. A 2-byte operand is written in little-endian byte-order regardless of the host platform.

For example, let's manually craft an instruction that returns the value of the global variable foo. Each opcode has a named constant of byte-X so we don't have to worry about their actual byte-code number.

(require 'bytecomp)  ; named opcodes

(defvar foo "hello")

(defalias 'get-foo
  (make-byte-code
    #x000                 ; no arguments
    (unibyte-string
      (+ 0 byte-varref)   ; ref variable under first constant
      byte-return)        ; pop and return
    [foo]                 ; constants
    1))                   ; only using 1 stack space

(get-foo)
;; => "hello"

Ta-da! That's a handcrafted byte-code function. I left a "+ 0" in there so that I can change the offset. This function has the exact same behavior, it's just less optimal,

(defalias 'get-foo
  (make-byte-code
    #x000
    (unibyte-string
      (+ 3 byte-varref)     ; 4th form of varref
      byte-return)
    [nil nil nil foo]
    1))

If foo was the 10th constant, we would need to use the 1-byte operand version. Again, the same behavior, just less optimal.

(defalias 'get-foo
  (make-byte-code
    #x000
    (unibyte-string
      (+ 6 byte-varref)     ; 7th form of varref
      9                     ; operand, (constant index 9)
      byte-return)
    [nil nil nil nil nil nil nil nil nil foo]
    1))

Dynamically-scoped code makes heavy use of varref but lexically-scoped code rarely uses it (global variables only), instead relying heavily on stack-ref, which is faster. This is where the different calling conventions come into play.

Calling Convention

Each kind of scope gets its own calling convention. Here we finally get to glimpse some of the really great work by Stefan Monnier updating the compiler for lexical scope.

Dynamic Scope Calling Convention

Remembering back to the parameter list element of the byte-code object, dynamically scoped functions keep track of all its argument names. Before executing a function the interpreter examines the lambda list and binds (varbind) every variable globally to an argument.

If the caller was byte-compiled, each argument started on the stack, was popped and bound to a variable, and, to be accessed by the function, will be pushed back right onto the stack (varref). There's a lot of argument indirection for each function call.

Lexical Scope Calling Convention

With lexical scope, the argument names are not actually bound for the evaluation byte-code. The names are completely gone because the compiler has converted local variables into stack offsets.

When calling a lexically-scoped function, the byte-code interpreter examines the integer parameter descriptor. It checks to make sure the appropriate number of arguments have been provided, and for each unprovided &optional argument it pushes a nil onto the stack. If the function has a &rest parameter, any extra arguments are popped off into a list and that list is pushed onto the stack.

From here the function can access its arguments directly on the stack without any named variable misdirection. It can even consume them directly.

;; -*- lexical-binding: t -*-
(defun foo (x) x)

(symbol-function #'foo)
;; => #[#x101 "\207" [] 2]

The byte-code for foo is a single instruction: return. The function's argument is already on the stack so it doesn't have to do anything. Strangely the maximum stack usage element is wrong here (2), but it won't cause a crash.

;; (As of this writing `byte-compile' always uses dynamic scope.)

(byte-compile 'foo)
;; => #[(x) "\010\207" [x] 1]

It takes longer to set up (x is implicitly bound), it has to make an explicit variable dereference (varref), then it has to clean up by unbinding x (implicit unbind). It's no wonder lexical scope is faster!

Note that there's also a disassemble function for examining byte-code, but it only reveals part of the story.

(disassemble #'foo)
;; byte code:
;;   args: (x)
;; 0       varref    x
;; 1       return

Compiler Intermediate "lapcode"

The Elisp byte-compiler has an intermediate language called lapcode ("Lisp Assembly Program"), which is much easier to optimize than byte-code. It's basically an assembly language built out of s-expressions. Opcodes are referenced by name and operands, including packed operands, are handled whole. Each instruction is a cons cell, (opcode . operand), and a program is a list of these.

Let's rewrite our last get-foo using lapcode.

(defalias 'get-foo
  (make-byte-code
    #x000
    (byte-compile-lapcode
      '((byte-varref . 9)
        (byte-return)))
    [nil nil nil nil nil nil nil nil nil foo]
    1))

We didn't have to worry about which form of varref we were using or even how to encode a 2-byte operand. The lapcode "assembler" took care of that detail.

Project Ideas?

The Emacs byte-code compiler and interpreter are fascinating. Having spent time studying them I'm really tempted to build a project on top of it all. Perhaps implementing a programming language that targets the byte-code interpreter, improving compiler optimization, or, for a really big project, JIT compiling Emacs byte-code.

People can write byte-code!

tags: [ emacs lisp elisp ]
? Comments

Emacs Lisp Readable Closures

I've stated before that one of the unique features of Emacs Lisp is that its closures are readable. Closures can be serialized by the printer and read back in with the reader. I am unaware of any other programming language that has this feature. In fact it's essential for Elisp byte-code compilation because byte-compiled Elisp files are merely s-expressions of byte-code dumped out as source.

Lisp Printing

The Lisp family of languages are homoiconic. Lisp source code is written in the syntax of its own data structures, s-expressions. Since a compiler/interpreter is usually provided at run-time, a consequence of this is that reading and printing are a fundamental feature of Lisps. A value can be handed to the printer, which will serialize the value into an s-expression as a sequence of characters. Later on the reader can parse the s-expression back into an equal value.

To compare, JavaScript originally had half of this in place. JavaScript has convenient object syntax for defining an associative array, known today as JSON. The eval function could (dangerously) be used as a reader for parsing a string containing JSON-encoded data into a value. But until JSON.stringify() became standard, developers had to write their own printer. Lisp s-expression syntax is much more powerful (and complicated) than JSON, maintaining both identity and cycles (e.g. *print-circle*).

Not all values can be read. They'll still print (when *print-readably* is nil) but will do so using special syntax that will signal an error in the reader: #<. For example, in Emacs Lisp buffers cannot be serialized so they print using this syntax.

(prin1-to-string (current-buffer))
;; => "#<buffer *scratch*>"

It doesn't matter what's between the angle brackets, or even that there's a closing angle bracket. The reader will signal an error as soon as it hits a #<.

Almost Everything Prints Readably

Elisp has a small set of primitive data types. All of these primitive types print readably:

Here are all the non-readable types I can find. Each one has a good reason for not being serializable.

And that's it. Every other value in Elisp is constructed from one or more of these primitives, including keymaps, functions, macros, syntax tables, defstruct structs, and EIEIO objects. This means that as long as these values don't refer to an unreadable value, they themselves can be printed.

An interesting note here is that, unlike the Common Lisp Object System (CLOS), EIEIO objects are readable by default. To Elisp they're just vectors, so of course they print. CLOS objects are unreadable without manually defining a print method per class.

Elisp Closures

Elisp got lexical scoping in Emacs 24, released in June 2012. It's now one of the relatively few languages to have both dynamic and lexical scope. Like Common Lisp, variables declared with defvar (and family) continue to have dynamic scope. For backwards compatibility with old Lisp code, lexical scope is disabled by default. It's enabled for a specific file or buffer by setting lexical-binding to non-nil.

With lexical scope, anonymous functions become closures, a powerful functional programming primitive: a function plus a captured lexical environment. It also provides some performance benefits. In my own tests, compiled Elisp with lexical scope enabled is about 10% to 15% faster than with the default dynamic scope.

What do closures look like in Emacs Lisp? It takes on two forms depending on whether the closure is compiled or not. For example, consider this function, foo, that takes two arguments and returns a closure that returns the first argument.

;; -*- lexical-binding: t; -*-
(defun foo (x y)
  (lambda () x))

(foo :bar :ignored)
;; => (closure ((y . :ignored) (x . :bar) t) () x)

An uncompiled closure is a list beginning with the symbol closure. The second element is the lexical environment, the third is the argument list (lambda list), and the rest is the body of the function. Here we can see that both x and y have been "closed over." This is a little bit sloppy because the function never makes use of y. Capturing it has a few problems.

Fortunately the compiler is smart enough to see this and will avoid capturing unused variables. To prove this, I've now compiled foo so that it returns a compiled closure.

(foo :bar :ignored)
;; => #[0 "\300\207" [:bar] 1]

What's returned here is a byte-code function object, with the #[...] syntax. It has these elements:

  1. The function's lambda list (zero arguments)
  2. Byte-codes stored in a unibyte string
  3. Constants vector
  4. Maximum stack space needed by this function

Notice that the lexical environment has been captured in the constants vector, specifically noting the lack of :ignored in this vector. The compiler didn't capture it.

For those curious about the byte-code here's an explanation. The string syntax shown is in octal, representing a string containing two bytes: 192 and 135. The Elisp byte-code interpreter is stack-based. The 192 (constant 0) says to push the first constant onto the stack. The 135 (return) says to pop the top element from the stack and return it.

(coerce "\300\207" 'list)
;; => (192 135)

The Readable Closures Catch

Since closures are byte-code function objects, they print readably. You can capture an environment in a closure, serialize it, read it back in, and evaluate it. That's pretty cool! This means closures can be transmitted to other Emacs instances in a multi-processing setup (i.e. Elnode, Async)

The catch is that it's easy to accidentally capture an unreadable value, especially buffers. Consider this function bar which uses a temporary buffer as an efficient string builder. It returns a closure that returns the result. (Weird, but stick with me here!)

(defun bar (n)
  (with-temp-buffer
    (let ((standard-output (current-buffer)))
      (loop for i from 0 to n do (princ i))
      (let ((string (buffer-string)))
        (lambda () string)))))

The compiled form looks fine,

(foo 3)
;; => #[0 "\300\207" ["0123"] 1]

But the interpreted form of the closure has a problem. The with-temp-buffer macro silently introduced a new binding -- an abstraction leak.

(foo 3)
;; => (closure ((string . "0123")
;;              (temp-buffer . #<killed buffer>)
;;              (n . 3) t)
;;      () string)

The temporary buffer is mistakenly captured in the closure making it unreadable, but only in its uncompiled form. This creates the awkward situation where compiled and uncompiled code has different behavior.

tags: [ emacs elisp lisp javascript ]
? Comments
Fork me on GitHub