Emacs Lisp で実装された Emacs バイトコードインタプリタを使ってバイトコードの解説

# 前書き
Emacs Lisp で実装された Emacs バイトコードインタプリタを使ってバイトコードの解説記事です。
正確には Emacs Lisp バイトコードと言うべきかもしれないですが、長いのでここでは Emacs バイトコードまたは単にバイトコードと言います。同様に Emacs Lisp を elisp と言います。

作成したバイトコードインタプリタには、トレース機能が実装されているので、それを使って解説する事により、インタプリタの具体的な動作が分かるという具合です。
それと、バイトコードインタプリタは elisp で実装されているので可読性が高く、リファレンスとして参照出来る事も考慮しています。

もちろん、本家の C 言語で実装されたバイトコードインタプリタ`emacs/src/bytecode.c`を参照する事が最も正確な情報源ですが、今一分かり難いのと、そもそもトレース機能が無かったり、デバッグ出力を追加するにしても、一々コンパイルが必要になります。
elisp で実装されているものはトライ&エラーがいとも簡単に出来るという利点があります。

しかし、C 言語で実装せずに elisp で実装している一番大きな理由は他にあります。
それと、全命令を実装してる訳ではないので色々制約がありますが、その内容なども追々説明します。

バイトコードインタプリタや .elc ファイル全体を逆アセンブルするソースコードは以下のサイトにあります。

https://github.com/chuntaro/toy-byte-code.el

使い方等もバイトコードを解説しながら説明します。
まずは、こちらを適当なディレクトリに clone しておいてください。
(実際に手を動かしながら読んで頂けるといいのですが、手元に環境が無い方にも分かるように全ての実行結果を貼り付けてるので、単に読むだけでも十分理解出来るはずです)

ちなみに、Emacs バイトコードについては [Emacs Byte-code Internals « null program](https://nullprogram.com/blog/2014/01/04/) という素晴らしい解説記事があります。
上記記事を、私が翻訳[^1]したものを[こちら](https://qiita.com/chuntaro/items/4fbbd41d6c5b5fc258a2)にアップしています(Google 翻訳よりはマシというレベルですが…)。
この記事は、上記記事に目を通している事が前提になります(完全に理解してなくても問題無いです)。
この記事は上記記事をより詳細な動作を解説しながら、補足するものになります。
それと、最小限の elisp の知識も必要になります。`if`などが使えて設定ファイルが書けるレベルであれば十分です。

[^1]: 一応許可を貰う為にメールをしましたが、返事は貰えませんでした。ただし、null program の記事は「All information on this blog, unless otherwise noted, is hereby released into the public domain, with no rights reserved. 」(このブログの全ての情報は、特に明記されている場合を除き、権利を保持せずここにパブリックドメインで公開されます。)と最下部に書いてある為、翻訳記事を公開しています。

更に、最近バイトコードについてリファレンスを作成された方もいらっしゃいます。
https://rocky.github.io/elisp-bytecode.pdf
このドキュメントの最初の方は、先の null program の解説記事と同じですが、プラスαの内容と、ほぼ全ての命令のリファレンスが記載されています。
これが無ければ elisp でバイトコードインタプリタの作成は難しかったでしょう。
本当に感謝です！
ただ、残念ながら間違いが結構あって、完全に信頼していると少し痛い目に合います(´;ω;｀)
(量が多いのでプルリクは保留…)
今や elisp での実装があるので、不明な点はリファレンスを参照しつつもソースも参照してもらえると良いと思います。

この記事を読み終わった後に「Emacs バイトコード完全に理解した」と思ってもらえる事を目指します！

では早速 Emacs バイトコードを解説します。

# バイトコードが実行されるまで
Emacs には elisp インタプリタが実装されていて、Emacs に含まれる機能の大部分(単純にコードの行数で言えば 70 %)が elisp で実装されている事は皆さんご存知の事と思います。

Emacs をインストールしたディレクトリ内を探すと`*.el`(または`*.el.gz`)ファイルがあり、それが elisp のソースコードです。
通常はそのファイルと同じ名前で`*.elc`ファイルがありますが、これが elisp のバイトコードが格納されたファイルになります。`*.elc`は`*.el`をコンパイルして作成します。(バイトコンパイルすると言います)

Emacs はある機能をロードして使う時は`(require 'ffap)`などと記述しますが、その際に Emacs は`ffap.elc`があればそちらを優先してロードします。
`*.elc`は`*.el`を実行するよりも大幅に高速に実行する事が出来ます。
高速に実行出来る理由は、`*.elc`ファイルに含まれている関数は**バイトコード関数**という形式にコンパイルされていて、Emacs が`*.elc`を実行中にこの関数に出会うと、実行をバイトコードインタプリタに切り替えて実行を始めますが、このバイトコードインタプリタが非常に高速だからです。

ちなみに、`*.elc`は全てがバイトコードにコンパイルされている訳ではないので、微妙な言い回しになっています。

では、実際に`*.elc`ファイルを見てみましょう。
先に挙げた github のサイトに`hello.el`というファイルがありますが、これを使って説明します。

```emacs-lisp:hello.el
;;; -*- lexical-binding: t; -*-

(defun main ()
  (print "Hello, World."))

(main)
```

このファイルをバイトコンパイルするには幾つか方法がありますが、ここでは以下のようにコマンドラインから行います。

今後全ての作業をコマンドラインで行います。理由としては、`byte-code`というバイトコードを実行する肝の関数を、今回 elisp で作成したもので置き換える事になりますが、これは完全なものではないので、起動中の Emacs でそれを行ってしまうと、終了すらままならなくなります…。
という事で、今後の作業は全てコマンドラインで(`emacs --batch`で)行います。そうすれば、何も問題は起きません。

```shell
$ emacs --batch -f batch-byte-compile hello.el
```

これで、同じディレクトリ内に以下のファイルが出来るはずです。

```emacs-lisp:hello.elc
;ELC^W^@^@^@
;;; Compiled
;;; in Emacs version 26.1
;;; with all optimizations.

;;; This file uses dynamic docstrings, first added in Emacs 19.29.

;;; This file does not contain utf-8 non-ASCII characters,
;;; and so can be loaded in Emacs versions earlier than 23.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(defalias 'main #[0 "\300\301!\207" [print "Hello, World."] 2])
(main)
```

これを実行するには以下の様にします。

```shell
$ emacs --batch -l hello.elc

"Hello, World."
```

コンパイル後の内容を見ると .elc 内にはバイトコードだけじゃなくて普通に elisp のコードが書かれている事が分かります。
バイトコードにコンパイルされるのは関数の中身だけで、関数を設定(バインド)する関数(`defalias`)や単純な式(ここでは`(main)`)は、そのまま出力されています。
他にもグローバル変数を定義する`defvar`なども、あればそのまま出力されます。
結局のところ、.elc 内にはあらゆる elisp のコードが格納される可能性があります。
これこそが、バイトコードインタプリタを elisp で実装した最大の理由です。
要するに、ちゃんとした elisp リーダーを実装しない限り、バイトコードを実行する事すらままならないのです。

elisp で実装すると、`read`や`eval`を使えば、簡単に .elc をパースして実行(評価)する事が出来ます。(しかし、これでも 1 つ問題がありますが、それは後ほど説明します)

`hello.el`だと少しシンプル過ぎるので、今度は`hello2.el`と`hello2.elc`を使います。

```emacs-lisp:hello2.el
;;; -*- lexical-binding: t; -*-

(defun main ()
  (print "Hello, World."))

(print (main))
```

```emacs-lisp:hello2.elc
;ELC^W^@^@^@
;;; Compiled
;;; in Emacs version 26.1
;;; with all optimizations.

;;; This file uses dynamic docstrings, first added in Emacs 19.29.

;;; This file does not contain utf-8 non-ASCII characters,
;;; and so can be loaded in Emacs versions earlier than 23.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(defalias 'main #[0 "\300\301!\207" [print "Hello, World."] 2])
(byte-code "\300\301 !\207" [print main] 2)
```

バイトコードの実行のされ方には 2 種類ありますが、`hello2.elc`には両パターンが出力されています。
1 つ目は`#[0 "\300\301!\207" [print "Hello, World."] 2]`と表示されている、バイトコード関数オブジェクトです(正確にはバイトコード関数オブジェクトのリテラル表記)。
`defalias`は最終的に`fset`を呼び出して、バイトコード関数オブジェクトをシンボル`main`の関数に設定(バインド)します。
中身を取り出す場合は、

```emacs-lisp
(symbol-function 'main) ; => #[0 "\300\301!\207" [print "Hello, World."] 2]
```

とします。

少し横道にそれますが、Emacs Lisp のシンボルは C 言語で以下のように定義されています。(簡略化しています)

```c
struct Lisp_Symbol
{
  Lisp_Object name;
  Lisp_Object value;
  Lisp_Object function;
  Lisp_Object plist;
  struct Lisp_Symbol *next;
};
```

`name`はシンボル名が文字列オブジェクトに格納されていて、上記の場合は`"main"`です。
`name`を後から書き換える事は出来ません。
`value`は`setq`(または`set`)を使うと設定されるメンバーで、`function`は先ほど説明した`fset`を使うと設定され、`plist`はプロパティリストといい`setplist`を使って設定します。
`next`はシンボルをハッシュテーブル(実際は`obarray`という`vector`型の変数)に格納(`intern`)した際に、衝突があると`next`を使い線形リストで繋ぎます。
各メンバーにアクセスする関数は、それぞれ、

- `symbol-name`
- `symbol-value`
- `symbol-function`
- `symbol-plist`

です。`next`にアクセスする関数はありません。(そうする意味もないですが)
より詳しく知りたい場合は、[Emacs Lisp あれこれ](http://www.mew.org/~kazu/doc/elisp/index.html)が非常に参考になります。

`function`に何らかのオブジェクトが設定されていれば、`(main)`のように S 式の先頭に書く事により、elisp リーダーが`function`の中身を取り出し、実行可能なオブジェクトであれば実行します(そうでなければ、`Symbol's function definition is void: main`のようなエラーが発生します)。

`hello2.elc`ではバイトコード関数オブジェクトが登録されているので、elisp リーダーがそれをバイトコードインタプリタに渡して実行します。
これが 1 つ目の実行方法です。

2 つ目の実行方法は、`(byte-code "\300\301 !\207" [print main] 2)`です。
バイトコードインタプリタである`byte-code`に、バイトコード文字列など適切な引数を渡して、その場で実行されます。
要するにトップレベルに書かれているコードが複雑な場合は、そこがバイトコンパイルされ、`byte-code`に渡されてその場で実行されます。

この`byte-code`関数は(高速化の為当然ですが) C 言語で実装されています。1 つ目の実行方法の時にバイトコードインタプリタと言いましたが、この C 言語で実装されたものが間接的に呼び出されています。
関数呼び出しが起こる前に、そのオブジェクトは必ず`eval`(C 言語で実装されている)により評価されますが、その際にバイトコード関数オブジェクトであった場合は、`eval`内から`byte-code`が呼び出されています。

最終的に呼び出される関数は C 言語で実装された`byte-code`ですが、呼び出され方に違いがあるという事です。

以下、また少し余談になりますが、elisp で実装したバイトコードインタプリタが既存のバイトコードインタプリタをどのように置き換えるかを説明します。

elisp は既存の関数を簡単に上書き出来るので、今回作成した elisp のバイトコードインタプリタは、この`byte-code`を`(defun byte-code (...) ...)`のようにして自前のものに置き換えています。
問題は`eval`から直接呼び出されている場合ですが、`eval`は C 言語で実装されている為、`eval`→`byte-code`の呼び出しを横取りする事は不可能です。
`eval`自体を自前のものに置き換えて──と思うかもしれませんが、`eval`は他の C 言語で実装された沢山の関数から直接呼び出されている為、`eval`を自前のものに置き換える事もほとんど不可能です。
結局のところ、対処方法を簡単に説明すると、.elc ファイルを順に`read`していって、`read`した S 式をパースして、バイトコード関数を呼び出してる箇所があれば(前の例では`(main)`)、自前の`byte-code`を呼び出すコードに書き換え、無ければ何もせず、それらの S 式を`eval`に渡す事で対処しました(`toy-byte-code.el`内の`eval-elc`関数がそれです)。

これで大抵の場合は問題無いですが、1 つ問題があります。
`(main)`が`(defun main () ...)`より前に書かれていた場合に(ソースの位置的に前でも実行する順番が後になれば問題は無い)、`main`がバイトコード関数と認識出来ない為、置き換える事無くスルーしてしまい、元々の Emacs の`byte-code`が呼び出されてしまいます。
そうなると、elisp で実装した`byte-code`のスタックに積まれるはずの戻り値が消滅し、辻褄が合わなくなり妙なエラーが表示されます。
とはいえ、単なるバイトコードインタプリタの動作確認にしか使わない為、そういうコードを書かなければ良いだけなので、特に問題は無いでしょう。

さて、少し長くなりましたが、バイトコードが実行されるまでを説明したので、この後は早速バイトコードをトレース実行してみましょう！

# バイトコードのトレース実行

```shell
$ emacs --batch -l toy-byte-code.el -f dump-elc hello.elc

hello.elc

================================================================
constants: [print "Hello, World."]                  maxdepth: 2
----------------------------------------------------------------
PC  Byte  Instruction                  Operand
 0  192   constant[0]                  print
                                  | 0: print
 1  193   constant[1]                  "Hello, World."
                                  | 0: "Hello, World."
                                  | 1: print
 2   33   call[1]                      print "Hello, World."

"Hello, World."
                                  | 0: "Hello, World."
 3  135   return                       "Hello, World."
```

`hello.elc`をトレース実行した様子がこちらです。途中で`print`が実行されて`"Hello, World."`の出力が混ざってます。
`constants:`の項目は**定数ベクター**で、`maxdepth`は**最大スタック使用量**です。
(それぞれ詳細は *Emacs Byte-code Internals* で解説済みなのでそちらを参照してください)

`PC`はいわゆる`プログラムカウンター`でバイトコードの実行位置(インデックス)を表します。
`Byte`はバイトコードの値そのものです(10 進数)。オペコードやインストラクションと言います。
`Instruction`はオペコードに付けられた名前です。(ここは正確には`Instruction[Operand]`と書くべきですが、長いので省略しています)
`Operand`はオペランドと言い、インストラクションに対するいわゆる引数です。オペランドは通常ただの整数ですが(`constant[0]`の`0`がそれ)、それだと分かり難いので、具体的にどのオブジェクトを処理しているかを表示しています。なので、表示内容はインストラクションにより異なります。
オペランドが無いインストラクションもあります(上記の場合は`return`)。
ちなみに、`call`などは逆アセンブルではなくトレース実行だからこそ、オペランドに実行時にしか分からないオブジェクトを表示出来ています。

`hello.elc`をもう 1 度見てみます。

```emacs-lisp:hello.elc
(defalias 'main #[0 "\300\301!\207" [print "Hello, World."] 2])
(main)
```

`(main)`で`main`に設定されたバイトコード関数が実行されます。
その際に`#[0 ...`の`0`が引数無しを意味していて、引数の個数チェックが行われます。
その後、バイトコード文字列内の`"\300\301!\207"`がバイトコードインタプリタにより実行されます。
文字列を 10 進数で表すと、

- \300 → 192
- \301 → 193
- !    → 33
- \207 → 135

となり、上記のトレース結果と確かに一致します。

`192`は`constant[0]`で、この命令は**定数ベクターからオペランドが示す位置`0`のオブジェクトをスタックに積む**です。

```
 0  192   constant[0]                  print
```

の下に

```
                                  | 0: print
```

という表示がありますが、これはスタックの内容をダンプしていて、確かにシンボルの`print`が積まれている事が分かります。

同様に`193`は`constant[1]`で`"Hello, World."`がスタックに積まれ、

```
                                  | 0: "Hello, World."
                                  | 1: print
```

とスタックがダンプされています。スタックは伸びる方向の末端のオブジェクトを`0`としてインデックスされているので、そのように表示されています。0 番目のオブジェクトを特別にスタックトップ(TOS: Top Of Stack)と呼びます。それ以外は便宜上、スタック[n]と書きます。

今後は、スタックに積む事をプッシュ、スタックトップを削除する事をポップとします。
一度に複数プッシュしたりポップする事があり、ポップの場合は削除したオブジェクトをその後使ったり使わずに破棄する事もあります。

では、次に`33`の`call[1]`が実行されています。
`call[1]`はスタック[1]にあるオブジェクトを関数として実行します(いわゆる、ファンクションコール)。引数は`call[n]`とするとスタック\[n - 1\](第1引数) からスタックトップ(最後の引数)までの n 個になります。
実行から戻ってきたら、`n + 1`個のオブジェクトをポップして、戻り値を 1 つプッシュします。

```
 (func arg1 arg2) -> retval
  ↓
 | 0: arg2
 | 1: arg1
 | 2: func                          | 0: retval
 | 3: aa                 | 0: aa    | 1: aa
 | 4: bb   -> call[2] -> | 1: bb -> | 2: bb
```

`call[1]`が実行されると`print`が引数`"Hello, World."`を伴って実行されて

```
"Hello, World."
```

と`print`が出力した内容が表示されて、スタックが

```
                                  | 0: "Hello, World."
```

となっています。`print`の戻り値は渡された引数をそのまま返すので、こうなります。

最後に`135`の`return`が実行されています。このインストラクションはオペランドが無く**スタックトップの値をポップし、そのオブジェクトを戻り値として関数から戻る**という動作を行います。
`return`の後は何も表示されていませんが、それはスタックが空になっているという意味です。ここでスタックに何か残っていると、関数を呼び出している内にスタックが溢れてしまう事を意味するので、ちゃんとスタックが空になってないとまずいです。

これだけでも、スタックマシーンである Emacs バイトコードインタプリタの動作が、概ね分かったのではないかと思います。

ただ、これだけだと簡単すぎるので、今度はみんな大好きフィボナッチ数列のコードで試してみます。

```emacs-lisp:fib.el
;;; -*- lexical-binding: t; -*-

(defun fib (n)
  (cond
   ((= n 0) 0)
   ((= n 1) 1)
   (t (+ (fib (1- n))
         (fib (- n 2))))))

(print (fib 2))
```

```emacs-lisp:fib.elc
;ELC^W^@^@^@
;;; Compiled
;;; in Emacs version 26.1
;;; with all optimizations.

;;; This file uses dynamic docstrings, first added in Emacs 19.29.

;;; This file does not contain utf-8 non-ASCII characters,
;;; and so can be loaded in Emacs versions earlier than 23.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


#@10 

(fn N)^_
(defalias 'fib #[257 "\211\300U\203^H^@\300\207\211\301U\203^P^@\301\207\302^AS!\302^B\303Z!\\\207" [0 1 fib 2] 5 (#$ . 408)])
(byte-code "\300\301\302!!\207" [print fib 2] 3)
```

`fib.elc`を実行してみてください。`(fib 2)`なので`1`が表示されるだけですが、それで十分です。
それでも少し長いですが、トレース結果を貼り付けます。
ちなみに、トレース結果には関数名が出力されてないですが、実際バイトコード自体には名前が無いのでそうなります。
なので、どこが実行されているかを確認するには、`constants`と`maxdepth`の項目を見て対応をとります。
ひとまず、ざっと眺めて後続の説明を参照してください。

```shell
$ emacs --batch -l toy-byte-code.el -f dump-elc fib.elc

fib.elc

================================================================
constants: [print fib 2]                            maxdepth: 3
----------------------------------------------------------------
PC  Byte  Instruction                  Operand
 0  192   constant[0]                  print
                                  | 0: print
 1  193   constant[1]                  fib
                                  | 0: fib
                                  | 1: print
 2  194   constant[2]                  2
                                  | 0: 2
                                  | 1: fib
                                  | 2: print
 3   33   call[1]                      fib 2

================================================================
constants: [0 1 fib 2]                              maxdepth: 5
----------------------------------------------------------------
PC  Byte  Instruction                  Operand
 0  137   dup                          2
                                  | 0: 2
                                  | 1: 2
                                  | 2: fib
                                  | 3: print
 1  192   constant[0]                  0
                                  | 0: 0
                                  | 1: 2
                                  | 2: 2
                                  | 3: fib
                                  | 4: print
 2   85   eqlsign                      2 0
                                  | 0: nil
                                  | 1: 2
                                  | 2: fib
                                  | 3: print
 3  131   goto-if-nil[8]               nil
           8
           0
                                  | 0: 2
                                  | 1: fib
                                  | 2: print
 8  137   dup                          2
                                  | 0: 2
                                  | 1: 2
                                  | 2: fib
                                  | 3: print
 9  193   constant[1]                  1
                                  | 0: 1
                                  | 1: 2
                                  | 2: 2
                                  | 3: fib
                                  | 4: print
10   85   eqlsign                      2 1
                                  | 0: nil
                                  | 1: 2
                                  | 2: fib
                                  | 3: print
11  131   goto-if-nil[16]              nil
          16
           0
                                  | 0: 2
                                  | 1: fib
                                  | 2: print
16  194   constant[2]                  fib
                                  | 0: fib
                                  | 1: 2
                                  | 2: fib
                                  | 3: print
17    1   stack-ref[1]                 2
                                  | 0: 2
                                  | 1: fib
                                  | 2: 2
                                  | 3: fib
                                  | 4: print
18   83   sub1                         2
                                  | 0: 1
                                  | 1: fib
                                  | 2: 2
                                  | 3: fib
                                  | 4: print
19   33   call[1]                      fib 1

================================================================
constants: [0 1 fib 2]                              maxdepth: 5
----------------------------------------------------------------
PC  Byte  Instruction                  Operand
 0  137   dup                          1
                                  | 0: 1
                                  | 1: 1
                                  | 2: fib
                                  | 3: 2
                                  | 4: fib
                                  | 5: print
 1  192   constant[0]                  0
                                  | 0: 0
                                  | 1: 1
                                  | 2: 1
                                  | 3: fib
                                  | 4: 2
                                  | 5: fib
                                  | 6: print
 2   85   eqlsign                      1 0
                                  | 0: nil
                                  | 1: 1
                                  | 2: fib
                                  | 3: 2
                                  | 4: fib
                                  | 5: print
 3  131   goto-if-nil[8]               nil
           8
           0
                                  | 0: 1
                                  | 1: fib
                                  | 2: 2
                                  | 3: fib
                                  | 4: print
 8  137   dup                          1
                                  | 0: 1
                                  | 1: 1
                                  | 2: fib
                                  | 3: 2
                                  | 4: fib
                                  | 5: print
 9  193   constant[1]                  1
                                  | 0: 1
                                  | 1: 1
                                  | 2: 1
                                  | 3: fib
                                  | 4: 2
                                  | 5: fib
                                  | 6: print
10   85   eqlsign                      1 1
                                  | 0: t
                                  | 1: 1
                                  | 2: fib
                                  | 3: 2
                                  | 4: fib
                                  | 5: print
11  131   goto-if-nil[16]              t
          16
           0
                                  | 0: 1
                                  | 1: fib
                                  | 2: 2
                                  | 3: fib
                                  | 4: print
14  193   constant[1]                  1
                                  | 0: 1
                                  | 1: 1
                                  | 2: fib
                                  | 3: 2
                                  | 4: fib
                                  | 5: print
15  135   return                       1
                                  | 0: 1
                                  | 1: 2
                                  | 2: fib
                                  | 3: print

================================================================
constants: [0 1 fib 2]                              maxdepth: 5
----------------------------------------------------------------
PC  Byte  Instruction                  Operand
20  194   constant[2]                  fib
                                  | 0: fib
                                  | 1: 1
                                  | 2: 2
                                  | 3: fib
                                  | 4: print
21    2   stack-ref[2]                 2
                                  | 0: 2
                                  | 1: fib
                                  | 2: 1
                                  | 3: 2
                                  | 4: fib
                                  | 5: print
22  195   constant[3]                  2
                                  | 0: 2
                                  | 1: 2
                                  | 2: fib
                                  | 3: 1
                                  | 4: 2
                                  | 5: fib
                                  | 6: print
23   90   diff                         2 2
                                  | 0: 0
                                  | 1: fib
                                  | 2: 1
                                  | 3: 2
                                  | 4: fib
                                  | 5: print
24   33   call[1]                      fib 0

================================================================
constants: [0 1 fib 2]                              maxdepth: 5
----------------------------------------------------------------
PC  Byte  Instruction                  Operand
 0  137   dup                          0
                                  | 0: 0
                                  | 1: 0
                                  | 2: fib
                                  | 3: 1
                                  | 4: 2
                                  | 5: fib
                                  | 6: print
 1  192   constant[0]                  0
                                  | 0: 0
                                  | 1: 0
                                  | 2: 0
                                  | 3: fib
                                  | 4: 1
                                  | 5: 2
                                  | 6: fib
                                  | 7: print
 2   85   eqlsign                      0 0
                                  | 0: t
                                  | 1: 0
                                  | 2: fib
                                  | 3: 1
                                  | 4: 2
                                  | 5: fib
                                  | 6: print
 3  131   goto-if-nil[8]               t
           8
           0
                                  | 0: 0
                                  | 1: fib
                                  | 2: 1
                                  | 3: 2
                                  | 4: fib
                                  | 5: print
 6  192   constant[0]                  0
                                  | 0: 0
                                  | 1: 0
                                  | 2: fib
                                  | 3: 1
                                  | 4: 2
                                  | 5: fib
                                  | 6: print
 7  135   return                       0
                                  | 0: 0
                                  | 1: 1
                                  | 2: 2
                                  | 3: fib
                                  | 4: print

================================================================
constants: [0 1 fib 2]                              maxdepth: 5
----------------------------------------------------------------
PC  Byte  Instruction                  Operand
25   92   plus                         1 0
                                  | 0: 1
                                  | 1: 2
                                  | 2: fib
                                  | 3: print
26  135   return                       1
                                  | 0: 1
                                  | 1: print

================================================================
constants: [print fib 2]                            maxdepth: 3
----------------------------------------------------------------
PC  Byte  Instruction                  Operand
 4   33   call[1]                      print 1

1
                                  | 0: 1
 5  135   return                       1
```

初出の命令を説明します。

`dup`は単純に**スタックトップのオブジェクトをプッシュ**します。結果的にスタックトップが複製されます。

`eqlsign`は elisp の`(= 2 0)`の`=`で**スタックから 2 つポップして、それらを引数として整数の比較をし、`t`か`nil`のオブジェクトをプッシュします**。
この`=`はサブル(subr)とかプリミティブ(primitive)と呼ばれますが、バイトコードに割り当てられている命令の大半は、このサブルの呼び出しになってます。
`=`は 2 引数のサブルになりますが、ほとんどが 1 つか 2 つの引数をもつものです。(少しだけ 3 や 4 があります)

`goto-if-nil[8]`は条件分岐命令です。3 バイトの命令なので、2 バイトを余計に取得してオペランドにします。縦に`8 0`と表示されていますが、それらが取得した 2 バイトです(2 バイトはリトルエンディアンなので 8 になります)。
`goto-if-nil[8]`は**スタックトップの値をポップしてそれが`nil`であったら、オペランドの値 8 を`PC`に設定し、そうでなければそのまま次の命令を実行**します。
今回はスタックトップが`nil`なので、`PC`に`8`が設定されてる事が次の命令の`PC`の項目で分かります。

```shell
PC  Byte  Instruction                  Operand
...
 3  131   goto-if-nil[8]               nil
           8
           0
                                  | 0: 2
                                  | 1: fib
                                  | 2: print
 8  137   dup                          2
...
```

`goto-if-*`は 4 つバリエーションがあります。

- `goto-if-nil`
- `goto-if-not-nil`
- `goto-if-nil-else-pop`
- `goto-if-not-nil-else-pop`

`not-nil`は比較が反転してて、`else-pop`は最初にポップせずに、条件が`else`の場合だけポップするという違いがあります。
ただの`goto[n]`もありますが、これは無条件に`PC`に`n`を代入します。

`stack-ref[1]`は**スタック[1]のオブジェクトをプッシュする**です。

他には`sub1`が elisp の`(1- n)`の`1-`で、`diff`が`(- n 2)`の`-`で、`plus`が`(+ a b)`の`+`になります。
`sub1`が 1 引数のサブルで、`diff`と`plus`は 2 引数です。

実はもうこれでバイトコードを読めるようになったと言っても過言ではありません！
実際にトレースした実行結果を辛抱強く眺めてみてください。
後は`diff`が`-`のようなサブルとの対応を知る事と、その他の細々した実装の詳細は`toy-byte-code.el`を見る事で理解出来るはずです。

バイトコード実行の最後の例として、クロージャがどのようにバイトコードで実装されているかを見てみます。

```emacs-lisp:closure.el
;;; -*- lexical-binding: t; -*-

(defun make-closure ()
  (let ((count 0))
    (lambda () (setq count (1+ count)))))

(setq cls (make-closure))
(print cls)

(print (funcall cls))
(print cls)

(print (funcall cls))
(print cls)
```

このコードをバイトコンパイルせずに実行すると、

```shell
$ emacs --batch -l closure.el

(closure ((count . 0) t) nil (setq count (1+ count)))

1

(closure ((count . 1) t) nil (setq count (1+ count)))

2

(closure ((count . 2) t) nil (setq count (1+ count)))
```

このように、関数定義の中に捕捉した変数`count`が格納されていて、`setq`で書き換えられてる事が分かります。(`setq`は捕捉した変数を書き換えているかを内部で判別して動作を変えています)
elisp はバイトコンパイルする前の関数定義は単なるリストですが、捕捉した変数を値込みで持っている事がクロージャの全てと言えるでしょう。(なんと分かり易い！)

これがバイトコンパイルされるとどうなるか？

```shell
$ emacs --batch -f batch-byte-compile closure.el
$ emacs --batch -l toy-byte-code.el -f trace-elc closure.elc | cat -n
     1	
     2	closure.elc
     3	
     4	================================================================
     5	constants: [cls make-closure print]                 maxdepth: 2
     6	----------------------------------------------------------------
     7	PC  Byte  Instruction                  Operand
     8	 0  193   constant[1]                  make-closure
     9	 1   32   call[0]                      make-closure
    10	
    11	================================================================
    12	constants: [0 make-byte-code "\300\211\242T\240\207" vconcat vector [] 2] maxdepth: 7
    13	----------------------------------------------------------------
    14	PC  Byte  Instruction                  Operand
    15	 0  192   constant[0]                  0
    16	 1   67   list1                        0
    17	 2  193   constant[1]                  make-byte-code
    18	 3  192   constant[0]                  0
    19	 4  194   constant[2]                  "\300\211\242T\240\207"
    20	 5  195   constant[3]                  vconcat
    21	 6  196   constant[4]                  vector
    22	 7    5   stack-ref[5]                 (0)
    23	 8   33   call[1]                      vector (0)
    24	 9  197   constant[5]                  []
    25	10   34   call[2]                      vconcat [(0)] []
    26	11  198   constant[6]                  2
    27	12   36   call[4]                      make-byte-code 0 "\300\211\242T\240\207" [(0)] 2
    28	13  135   return                       #[0 "\300\211\242T\240\207" [(0)] 2]
    29	
    30	================================================================
    31	constants: [cls make-closure print]                 maxdepth: 2
    32	----------------------------------------------------------------
    33	PC  Byte  Instruction                  Operand
    34	 2   16   varset[0]                    cls <- #[0 "\300\211\242T\240\207" [(0)] 2]
    35	 3  194   constant[2]                  print
    36	 4    8   varref[0]                    cls -> #[0 "\300\211\242T\240\207" [(0)] 2]
    37	 5   33   call[1]                      print #[0 "\300\211\242T\240\207" [(0)] 2]
    38	
    39	#[0 "\300\211\242T\240\207" [(0)] 2]
    40	 6  136   discard                      #[0 "\300\211\242T\240\207" [(0)] 2]
    41	 7  194   constant[2]                  print
    42	 8    8   varref[0]                    cls -> #[0 "\300\211\242T\240\207" [(0)] 2]
    43	 9   32   call[0]                      #[0 "\300\211\242T\240\207" [(0)] 2]
    44	
    45	================================================================
    46	constants: [(0)]                                    maxdepth: 2
    47	----------------------------------------------------------------
    48	PC  Byte  Instruction                  Operand
    49	 0  192   constant[0]                  (0)
    50	 1  137   dup                          (0)
    51	 2  162   car-safe                     (0)
    52	 3   84   add1                         0
    53	 4  160   setcar                       (0) 1
    54	 5  135   return                       1
    55	
    56	================================================================
    57	constants: [cls make-closure print]                 maxdepth: 2
    58	----------------------------------------------------------------
    59	PC  Byte  Instruction                  Operand
    60	10   33   call[1]                      print 1
    61	
    62	1
    63	11  136   discard                      1
    64	12  194   constant[2]                  print
    65	13    8   varref[0]                    cls -> #[0 "\300\211\242T\240\207" [(1)] 2]
    66	14   33   call[1]                      print #[0 "\300\211\242T\240\207" [(1)] 2]
    67	
    68	#[0 "\300\211\242T\240\207" [(1)] 2]
    69	15  136   discard                      #[0 "\300\211\242T\240\207" [(1)] 2]
    70	16  194   constant[2]                  print
    71	17    8   varref[0]                    cls -> #[0 "\300\211\242T\240\207" [(1)] 2]
    72	18   32   call[0]                      #[0 "\300\211\242T\240\207" [(1)] 2]
    73	
    74	================================================================
    75	constants: [(1)]                                    maxdepth: 2
    76	----------------------------------------------------------------
    77	PC  Byte  Instruction                  Operand
    78	 0  192   constant[0]                  (1)
    79	 1  137   dup                          (1)
    80	 2  162   car-safe                     (1)
    81	 3   84   add1                         1
    82	 4  160   setcar                       (1) 2
    83	 5  135   return                       2
    84	
    85	================================================================
    86	constants: [cls make-closure print]                 maxdepth: 2
    87	----------------------------------------------------------------
    88	PC  Byte  Instruction                  Operand
    89	19   33   call[1]                      print 2
    90	
    91	2
    92	20  136   discard                      2
    93	21  194   constant[2]                  print
    94	22    8   varref[0]                    cls -> #[0 "\300\211\242T\240\207" [(2)] 2]
    95	23   33   call[1]                      print #[0 "\300\211\242T\240\207" [(2)] 2]
    96	
    97	#[0 "\300\211\242T\240\207" [(2)] 2]
    98	24  135   return                       #[0 "\300\211\242T\240\207" [(2)] 2]
```

ちょっと長いので、ざっと眺めると、9 行目で`make-closure`が呼ばれた後の 27 行目の`make-byte-code`関数が肝です。
なんと、実行時にバイトコードを生成しています！
生成されたバイトコードは`cls`に格納されて、その定数ベクター内が`[(0)]`→`[(1)]`→`[(2)]`と変化している事が分かります。
要するに、適当に`count`の値をどこかに格納するのではなく、定数ベクターに格納する為に一々`make-byte-code`をしています。
そして、そこを書き換える為に、`car-safe`やら`setcar`やら(一見面倒な事…)を行っています。
こういう戦略を取ったのは、多分ですが、レキシカルバインディング対応の際に、バイトコードインタプリタの変更を不要にする為でしょう。

こうやって、レキシカルバインディングの実装を見てみると、実はバイトコードインタプリタやバイトコードの仕様自体は変更せずに済んでいるという事です！
.elc の互換性も(ある程度)確保されています。(26.1 では`switch`というインストラクションが追加されているので、それを使ってる場合は互換性は無くなっています。過去にも色々追加されているので、基本的には後方互換性は無い事になっています)
変更があったのは、elisp リーダとバイトコードコンパイラという事になります。

elisp リーダの変更点の一つですが、

```emacs-lisp
(lambda () (setq count (1+ count)))
↓
(closure ((count . 0) t) () (setq count (1+ count)))
```

への変形は誰がやってるかというと、lambda は実はマクロで最終的には

```emacs-lisp
(function (lambda () (setq count (1+ count))))
```

と展開されて、`function`が`(closure ...)`への変形(クロージャ作成)をしています。
昔の Emacs は`function`と`quote`と全く同じで、単に引数をそのまま返すだけでしたが、レキシカルバインディングが実装された時から`function`は重責(?)を担うようになりました。

この後はファイル全体を逆アセンブルする方法や、`toy-byte-code.el`の読み方と未実装機能などについて説明します。

# ファイル全体を逆アセンブルする方法

disass-elc.el を使い、以下のようにします。

```text
$ emacs --batch -l disass-elc.el fib.elc

fib.elc

================================================================
(defalias 'fib
  #[257 "\211\300U\203^H^@\300\207\211\301U\203^P^@\301\207\302^AS!\302^B\303Z!\\\207"
	[0 1 fib 2]
	5])
----------------------------------------------------------------
byte code:
  args: (arg1)
0	dup	  
1	constant  0
2	eqlsign	  
3	goto-if-nil 1
6	constant  0
7	return	  
8:1	dup	  
9	constant  1
10	eqlsign	  
11	goto-if-nil 2
14	constant  1
15	return	  
16:2	constant  fib
17	stack-ref 1
18	sub1	  
19	call	  1
20	constant  fib
21	stack-ref 2
22	constant  2
23	diff	  
24	call	  1
25	plus	  
26	return	  
================================================================

================================================================
(byte-code "\300\301\302!!\207"
	   [print fib 2]
	   3)
----------------------------------------------------------------
byte code:
  args: nil
0	constant  print
1	constant  fib
2	constant  2
3	call	  1
4	call	  1
5	return	  
================================================================
```

そもそも、バイトコードは elisp コードの合間に入り込んでいるので、全体を逆アセンブルすると言っても難しいのですが、それらしく出てるのではないかと思います。

この出力は Emacs 標準の逆アセンブラを使ってるので、今までのトレース結果とは出力内容が少し違います。
トレースの場合は`goto-if-nil`などでジャンプすると間の命令が飛ばされてしまいますが、逆アセンブルだと全体が分かります。

ちなみに`goto-if-nil`のオペランドが違ってるじゃないかと思われるかもですが、これは Emacs の逆アセンブラがジャンプ先を示すオペランドに`1`から始まるラベルを割り振ってそれを出力しています。左の列の`8:1`の`1`がラベルです。(正直、余計な事してる気がしますが…そういうもんだと思ってください)

# `toy-byte-code.el` の読み方

`toy-byte-code.el`は分かり易く書いたつもりなので、上から順に見てもらえれば分かるはず…ですが、多少補足します。
`toy-byte-code.el`は 3 つの動作モードがあります。

- 単純に実行する
- トレース実行する
- トレース実行中にスタックの内容を逐一ダンプする

それぞれの実行方法は以下です。

```shell
# foo.elc を単純に実行する
$ emacs --batch -l toy-byte-code.el -f eval-elc foo.elc

# foo.elc をトレース実行する
$ emacs --batch -l toy-byte-code.el -f trace-elc foo.elc

# trace-elc にスタックダンプ出力追加
$ emacs --batch -l toy-byte-code.el -f dump-elc foo.elc
```

`toy-byte-code.el`の制約などの注意事項を箇条書きしておきます。

・Emacs のコーディング規約である、プリフィックス付けを可読性を上げる為にしていません。(`tbc-debugf`でなく`debugf`など)

・レキシカルバインディングが有効になった状態でバイトコンパイルされたコードしか実行出来ません。
　具体的には、.el ファイルの先頭に

```emacs-lisp
;;; -*- lexical-binding: t; -*-
```

が必要です。(現在は、elisp のソースコードを書く時は必須になっていますが)

・`goto-char`の様な、テキスト編集でしか使いそうもないインストラクションは対応していません。

・`condition-case`や`unwind-protect`の様な例外処理に対応していません。

・当然なんですが…速度は激遅です。

以上です。
例外処理は対応してみたかったですが、手が回らなかったので…もしかしたらいずれ対応してこの記事を更新するかもしれません。
もし他の方が実装したら、ここのコメント欄や github で教えてください！

# おわりに
バイトコードを見ていると色々分かる事があります。
`(while)`ループで`(break)`をしたかったりとか、関数の途中で`(return)`したい場合は、elisp の場合は`(catch)`を使います。cl-lib に Common Lisp っぽく書くマクロも用意されています。
しかし、`(catch)`は状態を保存するので重い処理です。
ただ、バイトコードには`goto`や`return`というインストラクションがあるので、`(break)`や`(return)`を実装する事は理論上可能な事が分かります。
しかし、elisp はバイトコンパイルしてないコードも実行出来ないといけないので、結局`(catch)`を使う事が無難な実装になります。

他にも、バイトコードインタプリタは非常に単純ですが、本家の C 版は switch 分を使っているので、これをジャンプテーブルにすればもっと早くなるんじゃないかとか、そもそももっと早いバイトコードの仕様があるのではないか？など、色々思いが尽きません(笑)

本家では JIT コンパイルの実装が始まっていますが、Emacs のバイトコードを理解すれば JIT コンパイラのソースも読めるようになるかもしれません。

この記事を読んで、バイトコードインタプリタや、いわゆる VM と呼ばれるものに興味を持つ人が出てくればと思います。
何しろ、自分自身がもうバイトコードのコンパイラを作成したくなり、実際に作成中です！

次は Emacs Lisp → Emacs バイトコードへのコンパイラ解説記事を書ければと思っています。

それでは、また！

# 参考にしたサイト

[Emacs Byte-code Internals « null program](https://nullprogram.com/blog/2014/01/04/) (日本語訳：https://qiita.com/chuntaro/items/4fbbd41d6c5b5fc258a2)
https://rocky.github.io/elisp-bytecode.pdf