LAP and Bytecode to Emacs Lisp

From LAP to Lisp...

Bytecode and miscellaneous thoughts on the Emacs Runtime

(enter "s" to see presenter text for slides)

Review

Bytecode in Emacs is pervasive
Gives speedup of 2 to 3 times in computation-bound code
Is in reverse Polish prefix (data first, then operator)
A lot of the operations are either Lisp or Emacs functions
Demonstrated how to turn bytecode to LAP
But how we would go the other way?

Whither Bytecode?

Other programming languages
- Common Lisp — is sort of being done
- Others — huge Elisp code base migration
JITs
- libjit, lightning — works off of Bytecode
- JVM, LLVM — needs to replicate Lisp environment; garbage collector?
- V8, SpiderMonkey — pipcet has gc integrated

Emacs's bytecode is pretty old — as old as Emacs itself. And although there have been some changes to it, there has always been lurking in the background the question of whether it might be totally ditched, either as a by-product of switching out the underlying Lisp implementation for something else, or as a result of using JIT technology. [next]

Let's take these two situations where Emacs Lisp Bytecode might become obsolete separately. Both ideas have been floating around for a long time.

With respect to alternate programming-language implementations, there have been many languages that been proposed and experimented with. The big obstacle in totally replacing Emacs Lisp is in rewriting the huge current Emacs Lisp code base. I think that if such an approach were to work, the language would have to be available as an additional language until the current code base was replaced. Currently alternate programming languages haven't gained much of a foothold; they are not in the Emacs distribution or in any of its branches.

An obvious alternative language proposed is Common Lisp. Over time, an Emacs Lisp package implementation Common Lisp has been providing more and more Common Lisp functionality. The addition of features in Common Lisp has been somewhat reflected in changes in the run-time systems, such as the addition of lexical scoping. And this approach partially solves the large code-base migration problem. But it also reduces the need to jump cold turkey from Emacs Lisp Bytecode to something else.[next]

And what about the other possibility where Emacs incorporates JIT technology? The motivation for this is to speed up Emacs. There is widespread belief among the development community that there could be big performance wins if this were done right. After all, it is not uncommon for some people to live inside a single GNU Emacs session.

This idea of using a JIT to speed performance goes back over a decade, at least back to 2006. Of the JITs that have been proposed, at least four of them use Emacs Lisp Bytecode as the basis from which to JIT from. I think that is because Emacs Lisp Bytecode is a reasonable target to JIT: it is sufficiently low level, while also easy to hook a JIT into.

Two alternatives to Emacs Lisp Bytecode which have sophisticated JIT technology are LLVM IR and JVM IR. For each, the surrounding run-time environment would have to be replicated. Another IR possibility might be JavaScript IRs: specifically, the ones for V8 and Spidermonkey.

A Personal History

Interest in beefing up the runtime environment in programming languages for debugging
Did it for bash, GNU Make, Ruby, ...
Perl and Python also have decompilation at runtime
Can decompilation be applied to bytecode?
Yes, but there is a lot of work to do

A Tale of Two Interpreters part 1: Lisp

plus functionp


ELISP> (functionp 5)
nil
ELISP> (functionp (lambda(x) x))
t

plus symbol-function and funcall


ELISP> (symbol-function (lambda(x) x))
(lambda (x) x)
ELISP> (setq rocky-identity (lambda(x) x))
(lambda (x) x)
ELISP> (symbol-function rocky-identity)
(lambda (x) x)
ELISP> (funcall rocky-identity 5)
5 (#o5, #x5, ?\C-e)

A Tale of Two Interpreters part 2: Bytecode

You can turn any lisp function into bytecode by calling byte-compile. It returns a bytecode object which is a special kind of Lisp vector. What each of the parts in the vector is described in the Elisp bytecode manual. I won't go into any detail into that, except to say that you can isolate each of the parts using aref and that the 3rd item is a bytecode string which is an encoding of a LAP or (Lisp Assembly Program.

Note that functionp, symbol-function (not shown here), and funcall work as they do for Lisp interpreter functions. Under the covers funcall, is using symbol-function to extract the definition of the function in order to figure out how to evaluate it. [next]

Since the bytecode string is abstruse, you can use the disassemble function to produce a more human readable version. Of course, there is question as to whether you really want to understand yet another language. I don't and I'm going to talk about eliminating or reducing that step.

Ok, with allof this a background we can start to see what and understand what's going on when we hit an error. Let's look at some errors reported by Emacs. First, Emacs Lisp.

plus byte-compile and aref


ELISP> (byte-compile rocky-identity)
#[(x)
  "^H\207"
  [x]
  1]
ELISP> (aref rocky-identity 2)  ;; just the byte string
  "^H\207"
ELISP> (functionp rocky-identity)
t
ELISP> (funcall rocky-identity 5)
5 (#o5, #x5, ?\C-e)

plus disassemble


    ELISP> (disassemble rocky-identity)
byte code:
  args: (x)
0	varref	  x
1	return

An Emacs Error from the Lisp Interpreter


(fib-bug 3)
Debugger entered--Lisp error: (arith-error)
/(1 0)
(cond ((< n 1) 1) ((= fib-bug-count 0) (/ n 0)) (t (+ (fib-bug (1- n)) (fib-bug (- n 2)))))
fib-bug(1) ;; A link to the source code
(+ (fib-bug (1- n)) (fib-bug (- n 2)))
(cond ((< n 1) 1) ((= fib-bug-count 0) (/ n 0)) (t (+ (fib-bug (1- n)) (fib-bug (- n 2)))))
fib-bug(2) ;; A link to the source code
...

Note that we get the text fragment from were it comes from. Oddly it is shown as the more conventional function form with the parameters but not the function name in parenthesis. So we see /(1 0).

But it is a little weird for another reason. Look at the cond on the next line. It is supposed to be the surrounding context. It is a bit too broad. More specific would be that we are in the first clause of the cond.

The line below that now gives the function called with the parameter value: fib-bug(1). In Emacs there is also a link which you can click on that will get you to the source of that function if available. To do this though there is some serious magic getting used which is the same magic used by the (describe-function) function. The underlying hacky function that gets called is find-lisp-object-file-name.

After the fib-bug call, we now have another context line. And as before it is a bit too broad, and we begin to the pattern. Thespecific call location is not shown but its parent. Here, we are unluckly because it is ambiguous. This is frustrating me because the interpreter has the ability to distinguish.

If you find this as I do a little lacking, compare what you get when bytecode is run...

An Emacs Lisp Error from the Bytecode Interpreter


(fib-bug 3)
Debugger entered--Lisp error: (arith-error)
fib-bug(1)
fib-bug(2)
fib-bug(3)
eval((fib-bug 3) nil)
elisp--eval-last-sexp(nil)
...

Location, Location, Location...

What Emacs concepts exist for storing a location that might be useful here?

marks?

Marks associate a buffer and offset, not a file.

What Emacs concepts exist for storing a location in a file?

Docstrings
Info nodes

I didn't reveal this before, but symbol-function can actually return some other funky things. The reason for this set of slides is to show you that Emacs currently has a lot of flexibility right now in deciding how to execute a function. And therefore lends itself to extension. (I bet you knew that already).

Try this for on insert-file and notice the document field is a location inside a file. [next]

It is not really symbol-function that is being funky, what can be stored as a symbols "function" property. And when that is a byte-code object, there can be variation in what gets stored in the bytecode fields.

So here is another variation you can have in a bytecode object. Sometimes there can be two pointers to file locations: one for the docstring, and another one for the byte string. The reason we didn't see this before in "insert-file" is because insert-file was already loaded in emacs. When emacs starts up, it already has the bytecode for "insert-file" so it doeesn't need to retrieve it again. The same thing is true for the doc string. Once it gets loaded, that file pointer will disasppear. [next].

Another thing that can stored as the function property and reported by symbol-function are autoloaded functions. [next]

Finally, symbol-function can report that the function is some C code. In the Emacs written in Rust project, it can also be Rust source code.

`symbol-function` Revisited


ELISP> (load-file "/usr/share/emacs/25.2/lisp/files.elc")
t
ELISP> (symbol-function 'insert-file)
#[257 "\300^A\301\";"\207
  [insert-file-1 insert-file-contents]
  4
  ("/usr/share/emacs/25.2/lisp/files.elc" . 154863)
  "*fInsert file: "]

Note the "doc-string" field.

More symbol-function results:


ELISP> (symbol-function 'calendar)
#[(&optional arg)
  ("/usr/share/emacs/25.2/lisp/calendar/calendar.elc" . 40335)
  nil 3
  ("/usr/share/emacs/25.2/lisp/calendar/calendar.elc" . 38677)
  "P"]

The first pointer is to bytecode; the second is to docstring.

symbol-function autoload


ELISP> (autoload 'realgud:remake "realgud.el"
      	"Debugger for GNU (re)make" t)
realgud:remake
ELISP> (symbol-function 'realgud:remake)
(autoload "realgud.el" "Debugger for GNU (re)make" t nil)

symbol-function defalias


ELISP> (defalias 'remake 'realgud:remake)
remake
ELISP> (symbol-function 'remake)
realgud:remake

symbol-function C function


ELISP> (symbol-function 'end-of-line)
#<subr end-of-line>

Tracking Bytecode offsets

An Emacs Lisp Decompiler

Parse to Text

Here we'll show how to reconstruct the source text from this tree.

Bytecode instructions are the leaves of the tree, and none of the instructions are missing. So in that sense this is not the same as an "abstract syntax tree" in a compiler. Nothing abstract about it. It is more like a grammar parse you might see in linguistics imposed on top of an English sentence.

Some of the instruction like "VARREF" have an operand while others like "QUO" does not.

I'm sorry that the instructions are not in a nice linear sequence as they were shown previously. However as we will see, the fact that the instructions like "QUO" are at different levels of the tree has a big impact on describing where you are in your program. Even though these two instructions follow one another.

One other thing to note here is that there only three different node internal types: "expr", "binary_op", and "binary_expr".

We will enter text in each of the nodes, first focusing on expanding the two "binary_op" nodes. down

With "binary_op" rule

With "expr" rule where possible

With "binary_expr" rule

Finishing up

Parse at offset 3

Parse at offset 3 Display


(/ a (/ b c))
     -------

Parse at offset 4

Parse at offset 4 Text display


(/ a (/ b c))
-------------

A Decompiler Pipeline

Adding Locations to Bytecode

This stuff is pretty complicated. You may say, Rocky is this how things are normally done? Isn't there are simpler way?

Well, yes. But it involves changing the code to emit bytecode and the bytecode optiizer.

Recall in both kinds of compilers we have a parse tree. In byte compiling you have accurate information about which constructs were used and the position in source text that they are located. What you'd have to do is save those somewhere as you are parsing. That's not currently done. And then typically along with the bytecode you'd have to store this somewhere. The most logical place would be to extend the bytecode object to have what is somewhat narrow-mindedly called a "line number table". Really it is a mapping of positions from the source text to the object code.

I suppose you could also save this in the bytecode file somewhere as a constant giving it a name that is related to the function name.

In our example we would have:

A downside with this "eager" approach is that you have to do all the work up front first. I imagine getting this blessed by the Emacs devel community and signed off on enough to change Emacs would be a lot of work.

In contrast, in the decompiler, there is that one little change to track offsets, and the the rest can be done independent of Emacs core development. The two approaches are not mutually exclusive. And I do agree that it would be nice to have a traditional line number table like this.


0         1
01234567890123456789
(/ a (/ b c))

("tmp", "divide.el"
  '(0 . (3 . 3))
   (1 . (8 . 8))
   (2 . (10 . 10))
   (3 . (5 . 11))
   (4 . (0 . 12)))

Suggested Projects

Bytecode Manual

bugs: typos, grammar typos, thinkos
expand optimization section
links back to Emacs/Elisp manual

Decompiler:
- Earley algorithm in Emacs Lisp
- Fill out grammar
- Complete the "massage instructions" phase
Emacs Hacking
- Add run-time support for getting offset or adding a "line number table"
- Bytecode lint checker

Links...

- fin