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.
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.
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.
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.
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.
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,
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.
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.
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.
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.
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:(defvardb(emacsql-connect"~/office.db"));; Create a table with 3 columns:(emacsqldb[:create-tablepatients([name(idinteger:primary-key)(weightfloat)])]);; Insert a few rows:(emacsqldb[:insert:intopatients:values(["Jeff"1000184.2]["Susan"1001118.9])]);; Query the database:(emacsqldb[:select[nameid]:frompatients:where(<weight150.0)]);; => (("Susan" 1001));; Queries can be templates, using $s1, $i2, etc. as parameters:(emacsqldb[:select[nameid]:frompatients: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.
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:
SELECTnameFROMpeopleWHEREage<21;
A vector parameter refers to rows to be inserted or as a set for an
IN expression.
[:insert-intopeople[nameage]:values$v1]
Given the argument (["Jim" 45] ["Jeff" 34]), a list of two rows,
this becomes,
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:([nameidbuildingroom]);; Add some column constraints:([(name:unique)(idinteger:primary-key)buildingroom]);; Add some table constraints:([(name:unique)(idinteger:primary-key)buildingroom](:unique[buildingroom])(:check(>id0)))
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).
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-commandnamebuffer"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!
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.
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"nil010)(buffer-string))
This expands (roughly) to the following expression.
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.
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.
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(vectorprocess)(lambda()(delete-processprocess))));; 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.
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.
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.
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:
Load it into a browser page and poke at it from JavaScript remotely
with Skewer. With the JSON text weighing in at 53MB and
with such a large object count, I decided this was too large for a
browser page. It definitely could be done, it's just that the
browser is not the place to be working on large datasets.
Load it into Clojure. I'm familiar with Clojure's
data.json. This is not a bad choice, but there's
something else I always reach for first if I can.
Load it into Emacs using json.el (part of Emacs). This is what I
ended up doing.
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.
structLisp_Cons{/* Car of this cons cell. */Lisp_Objectcar;union{/* Cdr of this cons cell. */Lisp_Objectcdr;/* Used to chain conses on a free list. */structLisp_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.
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.
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.
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-sizejeopardy);; => 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).
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.
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.
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.
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.
opcodes 48 - 55
opcode 97
opcode 128
opcodes 169 - 174
opcodes 180 - 181
opcodes 183 - 191
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,
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.
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(ab&optionalc)));; => #[(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."
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-string100200250);; => "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(ab)(my-funcba)));; => #[(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.
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.
129, 192-255 : (constant) direct constants vector access
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(defvarfoo"hello")(defalias'get-foo(make-byte-code#x000; no arguments(unibyte-string(+0byte-varref); ref variable under first constantbyte-return); pop and return[foo]; constants1)); 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(+3byte-varref); 4th form of varrefbyte-return)[nilnilnilfoo]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(+6byte-varref); 7th form of varref9; operand, (constant index 9)byte-return)[nilnilnilnilnilnilnilnilnilfoo]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 -*-(defunfoo(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.
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.
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.
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.
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:
integer (1024, ?a)
float (1.7)
cons/list ((...))
vector (one-dimensional, [...])
bool-vector (#&n"...")
string ("...")
char-table (#^[...])
hash-table (readable as of Emacs 23.3, #s(hash-table ...))
byte-code function object (#[...])
symbol
Here are all the non-readable types I can find. Each one has a good
reason for not being serializable.
buffer
process (external state)
frame (user interface element)
marker (live, automatically updates)
overlay (belongs to a buffer)
built-in functions (native code)
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.
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.
The closure has a larger footprint than necessary.
Values are held longer than necessary, delaying collection.
It affects the readability of the closure, which I'll get to later.
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:
The function's lambda list (zero arguments)
Byte-codes stored in a unibyte string
Constants vector
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!)
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.
This past week I added Clojure-style multimethods to Emacs
Lisp through a package I call predd (predicate dispatch). I
believe it is Elisp's very first complete multiple dispatch object
system! That is, methods are dispatched based on the dynamic,
run-time type of more than one of its arguments.
(Unfortunately I was unaware of the
other Clojure-style multimethod library when I wrote mine.
However, my version is much more complete, has better performance,
and is public domain.)
As of version 23.2, Emacs includes a CLOS-like object system cleverly
named EIEIO. While CLOS (Common Lisp Object System) is multiple
dispatch, EIEIO is, like most object systems, only single dispatch.
The predd package is also very different than my other Elisp object
system, @, which was prototype based and, therefore, also single
dispatch (and comically slow).
The Clojure multimethods documentation provides a good
introduction. The predd package works almost exactly the same way,
except that due to Elisp's lack of namespacing the function names are
prefixed with predd-. Also different is that the optional hierarchy
(h) argument is handled by the dynamic variable predd-hierarchy,
which holds the global hierarchy.
Combination Example
To define a multimethod, pick a name and give it a classifier
function. The classifier function will look at the method's arguments
and return a dispatch value. This value is used to select a
particular method. What makes predd a multiple dispatch system is the
dispatch value can be derived from any number of methods arguments.
Because the dispatch value is computed at run-time this is called a
late binding.
Here I'm going to define a multimethod called combine that takes two
arguments. It combines its arguments appropriately depending on their
dynamic run-time types.
(predd-defmulticombine(lambda(ab)(vector(type-ofa)(type-ofb)))"Appropriately combine A and B.")
The classifier uses type-of, an Elisp built-in, to examine its
argument types. It returns them as tuple in the form of a vector. The
classifier of a method can be accessed with predd-classifier, which
I'll use to demonstrate what these dispatch values will look like.
I chose a vector for the dispatch value because I like the bracket
style when defining methods (you'll see below). The dispatch value can
be literally anything that equal knows how to compare, not just
vectors. Note that it's actually faster to create a list than a vector
up to a length of about 6, so this multimethod would be faster if the
classifier returned a list -- or even better: a single cons.
Now define some methods for different dispatch values.
(combine12); => 3(combine"a""b"); =>"ab"(combine'(12)'(34)); => (1 2 3 4)(combine1'(34)); error: "No method found in combine for [integer cons]"
Notice in the last case it didn't know how to combine these two types,
so it threw an error. In this simple example where we're only calling
a single function, so rather than use the predd-defmethod macro
these methods can be added directly with the predd-add-method
function. This has the exact same result except that it has slightly
better performance (no wrapper functions).
Hmmm, the + function is already polymorphic. It seamlessly operates
on both floats and integers. So far it seems there's no way to exploit
this with multimethods. Fortunately we can solve this by defining our
own ad hoc hierarchy using predd-derive. Both integers and floats
are a kind of number. It's important to note that type-of never
returns number. We're introducing that name here ourselves.
(type-of1.0); => float(predd-derive'integer'number)(predd-derive'float'number);; Types can derive from multiple parents, like multiple inheritance(predd-derive'integer'exact)(predd-derive'float'inexact)
This says that integer and float are each a kind of number. Now
we can use number in a dispatch value. When it sees something like
[float integer] it knows that it matches [number number].
We can check the hierarchy explicitly with predd-isa-p (like
Clojure's isa?). It compares two values just like equal, but it
also accounts for all predd-derive declarations. Because of this
extra concern, unlike equal, predd-isa-p is not commutative.
(Remember that 0 is truthy in Elisp.) The integer returned is a
distance metric used by method dispatch to determine which values are
"closer" so that the most appropriate method is selected.
You might be worried that introducing number will make the
multimethod slower. Examining the hierarchy will definitely have a
cost after all. Fortunately predd has a dispatch cache, so
introducing this indirection will have no additional performance
penalty after the first call with a particular dispatch value.
Struct Example
Something that really sets these multimethods apart from other object
systems is a lack of concern about encapsulation -- or really about
object data in general. That's the classifier's concern. So here's an
example of how to combine predd with defstruct from cl/cl-lib.
Imagine we're making some kind of game where each of the creatures is
represented by an actor struct. Each actor has a name, hit points,
and active status effects.
The defstruct macro has a useful inheritance feature that we can
exploit for our game to create subtypes. The parent accessors will
work on these subtypes, immediately providing some (efficient)
polymorphism even before multimethods are involved.
As a side note: this isn't necessarily the best way to go about
modeling a game. We probably shouldn't be relying on inheritance too
much, but bear with me for this example.
Say we want an attack method for handling attacks between different
types of monsters. Elisp structs have a very useful property by
default: they're simply vectors whose first element is a symbol
denoting its type. We can use this in a multimethod classifier.
(make-player);; => [cl-struct-player "Unknown" 100 nil nil](predd-defmultiattack(lambda(attackervictim)(vector(arefattacker0)(arefvictim0)))"Perform an attack from ATTACKER on VICTIM.")
Let's define a base case. This will be overridden by more specific
methods (determined by that distance metric).
We could have instead used :default for the dispatch value, which is
a special catch-all value. The actor-hp function will signal an
error for any victim non-actors anyway. However, not using :default
will force both argument types to be checked. It will also demonstrate
specialization for the example.
However, before we can make use of this we need to teach predd about
the relationship between these structs. It doesn't check defstruct
hierarchies. This step is what makes combining defstruct and predd
a little unwieldy. A wrapper macro is probably due for this.
If the monster applied a status effect in addition to the default
attack behavior then CLOS-style method combination would be far more
appropriate here (if only it was available in Elisp). The method would
instead be defined as an "after" method and it would automatically run
in addition to the default behavior.
If I was actually building a system combing structs and predd, I would
be using this helper function for building classifiers. It returns a
dispatch value for selected arguments.
;;; -*- lexical-binding: t; -*-(defunstruct-classifier(&restpattern)(lambda(&restargs)(loopforselect-pinpatternandarginargswhenselect-pcollect(eltarg0))));; Takes 3 arguments, dispatches on the first 2 argument types.(predd-defmultispeak(struct-classifierttnil));; Messages sent to the player are displayed.(predd-defmethodspeak'(cl-struct-actorcl-struct-player)(fromtomessage)(message"%s says %s."(actor-namefrom)message))
The Future
As of this writing there isn't yet a prefer-method for
disambiguating equally preferred dispatch values. I will add it in the
future. I think prefer-method gets unwieldy quickly as the type
hierarchy grows, so it should be avoided anyway.
I haven't put predd in MELPA or otherwise published it yet. That's
what this post is for. But I think it's ready for prime time, so feel
free to try it out.
A couple of months ago I wrote an Emacs Lisp wrapper for the
reddit API. I didn't put it in MELPA,
not yet anyway. If anyone is finding it useful I'll see about getting
that done. My intention was give it some exercise and testing before
putting it out there for people to use, locking down the API. You can
find it here,
Except for logging in, the library is agnostic about the actual API
endpoints themselves. It just knows how to translate between Elisp and
the reddit API protocol. This makes the library dead simple to use. I
had considered supporting OAuth2 authentication rather than
password authentication, but reddit's OAuth2 support is pretty rough
around the edges.
Library Usage
The reddit API has two kinds of endpoints, GET and POST, so there are
really only three functions to concern yourself with.
reddit-login
reddit-get
reddit-post
And one variable,
reddit-session
The reddit-login function is really just a special case of
reddit-post. It returns a session value (cookie/modhash tuple) that
is used by the other two functions for authenticating the user. Just
as you get automatically with almost all Elisp data structures --
probably more so than any other popular programming language -- it
can be serialized with the printer and reader, allowing a reddit
session to be maintained across Emacs sessions.
The return value of reddit-login generally doesn't need to be
captured. It automatically sets the dynamic variable reddit-session,
which is what the other functions access for authentication. This can
be bound with let to other session values in order to switch between
different users.
Both reddit-get and reddit-post take an endpoint name and a list
of key-value pairs in the form of a property list (plist). (The
api-type key is automatically supplied.) They each return the JSON
response from the server in association list (alist) form. The actual
shape of this data matches the response from reddit, which,
unfortunately, is inconsistent and unspecified, so writing any sort of
program to operate on the API requires lots of trial and error. If the
API responded with an error, these functions signal a reddit-error.
Typical usage looks like so. Notice that values need not be only
strings; they just need to print to something reasonable.
;; Login first(reddit-login"your-username""your-password");; Subscribe to a subreddit(reddit-post"/api/subscribe"'(:sr"t5_2s49f":actionsub));; Post a comment(reddit-post"/api/comment/"'(:text"Hello world.":thing_id"t1_cd3ar7y"))
For plists keys I considered automatically converting between dashes
and underscores so that the keywords could have Lisp-style names. But
the reddit API is inconsistent, using both, so there's no correct way
to do this.
To further refine the API it might be worth defining a function for
each of the reddit endpoints, forming a facade for the wrapper
library, hiding way the plist arguments and complicated responses.
That would eliminate the trial and error of using the API.
(defunreddit-api-comment(parentcomment)(if(nullreddit-session)(error"Not logged in.");; TODO: reduce the return value into a thing/struct(reddit-post"/api/comment/"'(:thing_idparent:textcomment))))
Furthermore there could be defstructs for comments, posts, subreddits,
etc. so that the "thing" ID stuff is hidden away. This is basically
what was already done for sessions out of necessity. I might add these
structs and functions someday but I don't currently have a need for
it.
It would be neat to use this API to create an interface to reddit from
within Emacs. I imagine it might look like one of the Emacs mail
clients, or like Elfeed. Almost everything, including
viewing image posts within Emacs, should be possible.
A few months ago we decided to institute a self-post-only Sunday. All
day Sunday, midnight to midnight Eastern time, only self-posts are
allowed in the subreddit. One of the other moderators was turning this
on and off manually, so I offered to write a bot to do the job. There
weren't any Lisp wrappers yet (though raw4j could be used
with Clojure), so I decided to write one.
As mentioned before, the reddit API leaves a lot to be desired. It
randomly returns errors, so a correct program needs to be prepared to
retry requests after a short delay, depending on the error. My
particular annoyance is that the /api/site_admin endpoint requires
that most of its keys are supplied, and it's not documented which ones
are required. Even worse, there's no single endpoint to get all of the
required values, the key names between endpoints are inconsistent, and
even the values themselves can't be returned as-is, requiring
massaging/fixing before returning them back to the API.
Today is Thanksgiving in the United States. It also happens to be
Hanukkah. There's been news going around that Thanksgiving and
Hanukkah will not coincide again for about 80,000 years. This
sounded somewhat unbelievable to me because
the Gregorian repeats every 400 years. I decided to
compute it for myself to double-check this figure.
I'm not Jewish and I know very little about Hanukkah, so I had to look
it up. After learning that Hanukkah is based on the Hebrew calendar,
the rumors were sounding more believable. The Hebrew calendar repeats
every 689,472 Hebrew years. This means the correspondence between
Gregorian and Hebrew calendars is about 14 billion years.
That 80,000 seems lowball.
Since I decided to use Emacs Lisp for the computation, I fortunately
was able to ignore all the unfamiliar, complicated rules for the
Hebrew calendar: Emacs knows how to compute Hebrew dates. It can be
accessed through the function calendar-hebrew-date-string.
Hanukkah begins on the 25th of Kislev, so I can write a
quick-and-dirty function to detect if a date is the first day of
Hanukkah.
(defunhanukkah-p(date)"Return non-nil if DATE is Hanukkah."(string-match-p"^Kislev 25"(calendar-hebrew-date-stringdate)))
Next I need a function to compute Thanksgiving, which is really
simple. Thanksgiving falls on the fourth Thursday of November.
(defunthanksgiving(year)"Return the date of Thanksgiving for YEAR."(loopfordayfrom1upto7when(=4(calendar-day-of-week`(11,day,year)))return`(11,(+day21),year)))
If there was no calendar-day-of-week I could compute it using
Zeller's algorithm, which I already happen to have
implemented,
(defuncal/day-of-week(yearmonthday)"Return day of week number (0-7)."(let*((Y(if(<month3)(1-year)year))(m(1+(mod(+month9)12)))(y(modY100))(c(/Y100)))(mod(+day(floor(-(*26m)2)10)y(/y4)(/c4)(*-2c))7)))
Now for each year find Thanksgiving and test it for Hanukkah. I
started with 1942 because that's when the fourth-Thursday-of-November
rule was established. Presumably due to the regexp part, this
expression takes a moment to compute.
