Help us understand the problem. What is going on with this article?

Emacs Byte-code Internals

More than 1 year has passed since last update.
This article translated “Emacs Byte-code Internals « null program” into Japanese.
(この記事は “Emacs Byte-code Internals « null program” を日本語に翻訳したものです。)

バイトコードのコンパイルは ─ 最近のレキシカルバインディングの更新についても同様に ─ Emacs において文書化されていないものの一つです。ほとんどのユーザーは通常 Elisp をバイトコードにコンパイルして .elc ファイルに保存し、そのバイトコードをロードすれば、コンパイルしていない Elisp より速く実行出来る事を知っています。それらは全てのユーザーが間違いなく知っておくべき事ですが、GNU Emacs Lisp Reference Manual は、より深い部分まで突っ込む事を明確に避けています。

皆さんは直接バイトコードを書かないで; その仕事はバイトコードコンパイラに任せましょう。ただ、皆さんの旺盛な好奇心1を満たす為に逆アセンブラは提供されています。

そんなこと知ったこっちゃない!自分でバイトコードを手書きしたってかまわないのだが? :-) この記事の目的は Elisp バイトコードインタプリタの内部を紹介することです。どのように動作するのか、レキシカルスコープのコードがなぜ高速なのか、手作業で幾つかバイトコードを書く方法を説明します。

質素な(humble)スタックマシーン

バイトコードインタプリタはシンプルなスタックマシーンです。スタックは任意の lisp オブジェクトを保持します。インタプリタは後方互換性がありますが、前方互換性はありません(古いバージョンでは新しいバイトコードを実行することはできません)。それぞれの命令(instruction)は 1 ~ 3 バイトです。最初のバイトはオペコードを表し、2 番目と 3 番目は単一のオペランドか中間値(intermediate value)です(訳注:中間値という言葉は今後出てこないので、全てオペランドで良いと思われる)。幾つかのオペランドはオペコード内にパックされています。(訳注:パックドオペランドと言い、後ほど説明される)

この執筆時点(Emacs 24.3)で 142 個のオペコードがあり、そのうち 6 個は廃止と宣言されています。ほとんどのオペコードは、高速にアクセスする為によく使用される組み込み関数を指します(その取捨選択を見ると、Elisp は本当にテキスト編集が目的なのが分かります!)。Elisp はパックドオペランドを考慮すると、未使用の潜在的なオペコードは最大 27 個あり、将来のために予約されています。

  • opcodes 48 - 55
  • opcode 97
  • opcode 128
  • opcodes 169 - 174
  • opcodes 180 - 181
  • opcodes 183 - 191

bytecomp.elの中で手っ取り早くオペコードの一覧が得られます。オペコードのコメントの一部は、現在は古くなっていることに注意してください。

セグメンテーションフォルトに注意

バイトコードは、通常の Elisp と同等の安全性はありません。不正なバイトコードは Emacs をクラッシュさせる可能性があります。自分で試す事が出来ます。

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

またはバッファ内でコードを手動で評価してください(その前に全てを保存してください!)、

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

この segfault は、定数ベクター(constants vector)(訳注:[] がそれで、後ほど説明される)の終わりを超えて参照される為で Emacs のバグではありません。範囲チェック(boundary test)を実行すると、バイトコードインタプリタが遅くなります。実行時にこのチェックを行わない事は効果的な設計上の判断です。Emacs の開発者は、代わりにコンパイラによる正しいバイトコードの出力に依存する事を選択したので、独自のバイトコードを書きたいと思っている皆さんには以下の免責事項を挙げておきます。

バイトコード関数を自前で組み立てても、個々の内容に矛盾があるとそれを呼び出した時に Emacs がクラッシュする可能性があるので、やめるべきです。これらのオブジェクトを作成するには、常にバイトコードコンパイラに任せてください。(皆が望むように)常に一貫性のあるものにします。

ちゃんと警告しましたよ。それでは、爆竹で遊んでみましょうか。(Now it’s time to start playing with firecrackers.)

バイトコードオブジェクト

バイトコードオブジェクトは、関数として評価できる点を除いて、普通の Elisp のベクター(vector)と機能的に同等です。それぞれの要素は一定時間でアクセスが出来、構文はベクターの構文([...]#[...]) に似ていて、任意の長さにすることが出来ますが、有効な関数には少なくとも 4 つの要素が必要です。

バイトコードオブジェクトを作成するには、バイトコードオブジェクトリテラルまたはmake-byte-codeを使用する 2 つの方法があります。ベクターリテラルのように、バイトコードリテラルはクオートする必要はありません。

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

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

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

オブジェクトリテラルの要素は次の通りです。

  • 関数パラメータ(ラムダ)リスト
  • バイトコードの Unibyte 文字列
  • 定数ベクター
  • 最大スタック使用量
  • ドキュメント文字列(Docstring) (オプション、nil の場合は無し)
  • interactive の仕様(Interactive specification) (オプション)

パラメータリスト

パラメータリストは、その関数がレキシカルまたは動的(ダイナミック)スコープかによって、2 つの異なる形式をとります。関数が動的スコープの場合、パラメータリストはまんま lisp コードに現れるものです。

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

引数の名前(訳注:ab)を保持することが重要であるため、パラメータリストを表現するための簡単な方法はありません。動的スコープでは、関数本体が評価されている間、これらの変数は関数の引数としてグローバルにバインドされています(ウゲッ!)。

関数がレキシカルスコープの場合、パラメータリストは Elisp の整数にパックされ、様々な種類のパラメータの数を表します。(必須引数(required)、&optional&rest)

最下位 7 ビットは必須引数の数を表します。これは、コンパイルされたレキシカルスコープの関数は必須引数が 127 個に制限されている事に注意してください。8 番目のビットは&restの引数の数です(最大 1)。残りのビットは、&optional引数と必須引数の合計を表します(&restの個数ではありません)。それぞれの部分が大体そのままの「数字」になっているので、これらの 16 進数を頭の中で解読するのはとても簡単です。

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

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

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

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

引数の名前(訳注:ab)はレキシカルスコープには関係ありません。それらは純粋に位置だけで参照されます。この、よりタイトな引数の仕様は、レキシカルスコープが高速である理由の 1 つです。バイトコードインタープリタは、ラムダリスト全体を解析し、各関数呼び出しで全ての変数を割り当てる必要はありません。(訳注:動的スコープの場合はそれが行われる)

Unibyte 文字列のバイトコード

2 番目の要素は Unibyte 文字列です。これは厳密にオクテット(訳注:8 ビット値)を保持しており、Unicode エンコーディングとして解釈されることはありません。string(訳注:string 関数)はマルチバイト文字列を返す可能性があるため、これらの文字列はunibyte-stringで作成する必要があります。より大きい値(> 127)が存在する場合は、文字列型を lisp リーダーに明確にするために、文字列は 8 進表記でエスケープされ、文字列リテラルが ASCII 文字セット内であればそのまま表示されます。
(訳注:以下の例だと"d\310\372"が lisp リーダーに読み込ませた場合にちゃんと Unibyte 文字列として読み込めるという意味)

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

135(#o207、byte-return) で終わらないバイトコード文字列を見るのは珍しいことです。多分これはまだ言ってませんでしたね?後ほどバイトコードについて詳しく説明します。

定数ベクター

バイトコードのオペランドは非常に限られています。ほとんどのオペランドはほんの数ビットであり、一部はバイト全体を占め、場合によっては 2 バイトです。関数に含まれる全ての定数、関数シンボル、および変数シンボルを保持するものが定数ベクターです。これは通常の Elisp ベクターであり、vector(訳注:vector 関数)またはベクターリテラルで作成することが出来ます。オペランドはこのベクターを参照するか、スタック内を指し示します。

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

定数ベクターには、変数シンボルと外部関数シンボルがリストされているということに留意してください。これがレキシカルスコープの関数であった場合、定数ベクターは変数はリストされず、[my-func]だけです。

最大スタック使用量

これは、このバイトコードによって使用される最大スタックスペースです。この値はバイトコード自体から導出できますが、バイトコードインタープリタがスタックオーバーフローを迅速にチェックできるように事前計算されています。この値を過少報告することは、おそらく Emacs をクラッシュさせる別の手段です。

ドキュメント文字列(Docstring)

最も単純なコンポーネントで完全にオプションです。これは docstring 自体か、docstring が特に大きい場合は、コンパイルされた .elc と遅延アクセスの位置を示すコンスセルです。lisp リーダはそれを読み込んで認識する方法を知っているので、開始位置 1 つだけが必要です。
(訳注:例えばeshell関数などは#[256 "..." [eshell-buffer-name ...] 6 ("c:/emacs-25.2/share/emacs/25.2/lisp/eshell/eshell.elc" . 2153) "P"]のようにバイトコンパイルされている。通常は#[257 "..." [a print] 2 "ドキュメント文字列"]のように格納されている)

interactive の仕様(Interactive specification)

この要素が存在しnilでない場合、関数は対話型関数です。コンパイルされていない関数定義のinteractiveの内容を正確に保持します。

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

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

interactive式は常にインタプリタで解釈され、決してバイトコンパイルされません。これは、通常このコードがユーザーの入力を待つことになるため、(訳注:速度が)問題になる事はありません。ただし、キーボードのマクロ再生は遅くなります。

オペコード

既存のオペコードバイトの大部分は、変数、スタック、および定数へのアクセス用オペコードであり、ほとんどはパックドオペランドを使用します。

  • 0 - 7 : (stack-ref) stack reference
  • 8 - 15 : (varref) variable reference (from constants vector)
  • 16 - 23 : (varset) variable set (from constants vector)
  • 24 - 31 : (varbind) variable binding (from constants vector)
  • 32 - 39 : (call) function call (immediate = number of arguments)
  • 40 - 47 : (unbind) variable unbinding (from constants vector)
  • 129, 192-255 : (constant) direct constants vector access

(訳注:訳すと分かり難くなるのでそのまま記載。補足すると、(from constants vector) は定数ベクターにある変数シンボルを使うという事で、(immediate = number of arguments) はオペランドが引数の数を表し、direct constants vector access は、定数ベクターに格納されている値をそのまま使う(直接スタックに積む)という事)

最後の項目を除いて、各命令は 8 個ずつの組になっています。このような n 番目の命令は、n 番目のものにアクセスすることを意味します。例えば、命令 "2" は、第 3 のスタックアイテム(訳注:スタックの伸びる方向の末尾にあるアイテムを 0 番目と数えるので 2 番目は第 3 のアイテムとなる)をスタックの一番上にコピーする。"9" の命令は、定数ベクターにリストされた第 2 の要素(訳注:9 - 8 = 1 番目なので)によって指定された変数の値をスタックにプッシュする。
(訳注:スタックの内容が[123 "abc" 4 5 6]の場合、"2"(stack-ref)を実行すると[123 "abc" 4 5 6 4]になる)

しかし、各組の 7 番目および 8 番目の命令は、1 バイトまたは 2 バイトのオペランドを取ります。7 番目の命令は 1 バイトのオペランドをとり、8 番目の命令は 2 バイトのオペランドをとります。2 バイトのオペランドは、ホストプラットフォームに関係なくリトルエンディアンのバイトオーダーで書き込まれています。

例として、グローバル変数fooの値を返す命令を手動で作成してみましょう。各オペコードはbyte-Xの名前付き定数を持ちますので、実際のバイトコードの番号を気にする必要はありません。

(require 'bytecomp)  ; named opcodes

(defvar foo "hello")

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

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

じゃじゃーん!これは手作りのバイトコード関数です。私は"+ 0"を追加してオフセットを変更できるようにしました。以下の関数は全く同じ振る舞いをしていますが、最適なものではありません。

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

foo が 10 番目の定数だった場合は、1 バイトのオペランド版を使用する必要があります。繰り返しますが、同じ挙動ですが、更に最適ではありません。

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

動的スコープのコードは varref を大量に使用しますが、レキシカルスコープのコードではそれを使用することは滅多にありません(グローバル変数のみ)。代わりにstack-refに大きく依存し、それはより速いです。ここで、呼び出し規約の違いについて始めるべきでしょう。

呼び出し規約

スコープの種類ごとに独自の呼び出し規約があります。ここでは最終的に、Stefan Monnier のレキシカルスコープ用のコンパイラの改善による、本当に素晴らしい仕事の幾つかを垣間見ることになります。

動的スコープ呼び出し規約

バイトコードオブジェクト内の要素のパラメータリストを思い出してみると、動的にスコープされた関数は、全ての引数名を追跡します。関数を実行する前に、インタプリタはラムダリストを調べ、全ての変数を引数としてグローバルにバインドします(varbind)。

呼び出し側がバイトコンパイルされている場合、各引数はスタックからポップされて変数にバインドされ、関数によってアクセス(varref)されるために、スタックに直接プッシュバックされます。各関数呼び出しには、引数の間接参照が沢山あります。

レキシカルスコープ呼び出し規約

レキシカルスコープでは、引数名は実際には評価するバイトコードにバインドされて(訳注:含まれて)いません。コンパイラがローカル変数をスタックのオフセットに変換したため、名前は完全に消え去りました。

レキシカルスコープ関数を呼び出すとき、バイトコードインタープリタは整数のパラメータ記述子(訳注:パラメータリストの項目参照)を調べます。適切な数の引数が与えられていることを確認し、指定されていない&optional引数のそれぞれについてnilをスタックにプッシュします。関数に&restパラメータがある場合、余分な引数がリストに変換され、そのリストがスタックにプッシュされます。

ここから関数は、名前付き変数というミスディレクションせずにスタック上の引数に直接アクセス出来ます。直接消費(consume)する事さえ出来ます。(訳注:アクセスだけでなく書き換えたり自由に使えるという意味だと思われる)

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

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

fooのバイトコードはreturn命令 1 つです。関数の引数はすでにスタック上にあるので、何もする必要はありません。不思議なことに、スタックの最大使用量はここでは間違っていますが(2)、クラッシュは発生しません。

;; (As of this writing `byte-compile' always uses dynamic scope.)
;; (訳注:-*- lexical-binding: t -*- が無いのでダイナミックスコープになる)

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

時間の掛かるセットアップを行い(xを暗黙的にバインドします)、明示的な間接参照(varref)を作成しなければなりません。それから、xをアンバインド(暗黙のアンバインド)してクリーンアップする必要があります。レキシカルスコープが速いのは不思議ではありません!

バイトコードを調べるための逆アセンブル機能もありますが、それは物語のほんの一部のベールを剥がしたに過ぎません。(but it only reveals part of the story.)
(訳注:バイトコードインタプリタがxを暗黙的にバインドしたり、アンバインドしたりする必要があるので、逆アセンブルしたコードは仕事のほんの一部という意味だと思われる)

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

コンパイラの中間コード "lapcode"

Elisp バイトコンパイラには、lapcode("Lisp Assembly Program")という中間言語があり、これはバイトコードよりも遥かに簡単に最適化出来ます。これは基本的に S 式から構築されたアセンブリ言語です。オペコードは名前で参照され、パックドオペランドを含むオペランドは全てうまく処理してくれます。各命令はコンスセル(opcode . operand)であり、プログラムはこれらのリストです。

lapcode を使って最後のget-fooを書き直してみましょう。

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

私達が使っていたvarrefの形式や、2 バイトのオペランドをエンコードする方法さえも気にする必要はありません。ラップコード“アセンブラ”が、それら詳細を良きに計らってくれます。

プロジェクトのアイデア?

Emacs のバイトコードコンパイラとインタプリタは魅力的です。それらの調査に時間を費やしてみて、私は実際にその上にあらゆるプロジェクトを構築したい誘惑に駆られています。おそらく、バイトコードインタープリタをターゲットとするプログラミング言語を実装したり、コンパイラの最適化を改善したり、本当に大きなプロジェクトでは Emacs のバイトコードを JIT コンパイルしたりなどです。

People can write byte-code!


All information on this blog, unless otherwise noted, is hereby released into the public domain, with no rights reserved. (このブログの全ての情報は、特に明記されている場合を除き、権利を保持せず、ここにパブリックドメインとして公開されます。)


  1. 原文: But we provide a disassembler to satisfy a cat-like curiosity. 猫のような好奇心は Curiosity killed the cat. (好奇心は猫を殺す) ということわざにかけていると思われる。 

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away