Chapter 09

その他のテクニック: 計算量を意識した Lisp を書く

zk_phi
zk_phi
2020.09.24に更新

安全な関数を諦める

Emacs の設定を書いていると、 add-hookadd-to-list などの関数によく出会うと思います。これらの主な機能はリストに値を追加することですが、このときリストの要素に重複が出ないようにチェックもしてくれます。

一見便利なように思えますが、重複チェックはリストの全要素との比較が必要なのであまり軽い計算とはいえず、しかもあらかじめ重複しないとわかっている場合は無駄になってしまいます。

そこで、私は明らかに重複しないとわかっている(あるいは重複しても問題にならない)場合は add-to-list の代わりに push を使うようにしています。

(push '("\\.scad$" . scad-mode) auto-mode-alist)

add-hook には重複チェックに加えて、「リストじゃない場合はリストに変換する」などの機能も備わっているので、次のようなオレオレ雑 add-hook を用意しておくと便利です。

(defun my-function-list-p (val)
  (or (null val) (and (consp val) (not (eq (car val) 'lambda)))))

;; 重複チェックしない add-hook
(defun my-add-global-hook (hook fn)
  (let ((oldvalue (when (default-boundp hook) (default-value hook))))
    (if (my-function-list-p oldvalue)
        (set-default hook (cons fn oldvalue))
      (set-default hook (list fn oldvalue)))))

defsubst

Emacs Lisp にも関数のインライン展開があります。

defun と同じ要領で defsubst を使って定義でき、コンパイラーに対してインライン化してもいいよという指示を出せます。小さな関数に適用していくことで、関数呼び出し分のコストを削減することができます。

lexical-binding

Emacs Lisp は現時点ではデフォルトで動的束縛です。

(defvar fn
  (let ((a 1))
    (lambda (x) (+ x a))))

;; 関数定義時には a が定義されていたが、今はされていない
(funcall fn 3) ;; => void variable 'a'

;; a が定義されている環境で呼び出すとそれが参照される
(let ((a 2))
  (funcall fn 3)) ;; => 5

が、最近はローカル変数をまとめて静的束縛にすることができる lexical-binding オプションが実装されているので、静的束縛を利用することもできます。

;;; -*- lexical-binding: t -*-

(defvar fn
  (let ((a 1))
    (lambda (x) (+ x a))))

;; 関数定義時の a の値を関数が覚えている (関数閉包)
(funcall fn 3) ;; => 4

;; 新しいスコープで a をシャドーイングしても関数の振る舞いは変わらない
(let ((a 2))
  (funcall fn 3)) ;; => 4

変数が静的に束縛されるとわかっていると、たとえば let がただの stack push / pop で済むなど、最適化の余地が広がるので効率よく実行できます。

動的束縛でないと困るという場面はさほど多くないので、「俺、いま動的束縛活用してんなー」という自覚なしに書いている init.el はおそらく lexical-binding: t にしても問題なく動くと思います (動かない場合、たいてい警告が出るので従いましょう)。


自分はずっと、動的束縛こそ Emacs Lisp の味だぜと思って lexical-binding を使ってこなかったのですが、静的束縛になるのは変数束縛だけだと知って宗旨替えしました。

advice や関数再定義こそ Emacs Lisp の真髄だなあと思うことがあります。

オブジェクトの実体を意識する

Emacs Lisp には似たような機能の関数が複数あることがあります。それぞれの実装を理解して使い分けることで、より効率の良い設定ファイルを書くことができます。

等値比較

eq, eql, equal はどれも等値比較の関数ですが、

  • eq ... オブジェクトの実体が同じ
  • eql ... オブジェクトの実体が同じか、数値として等しい
  • equal ... オブジェクトの実体が同じか、数値として等しいか、文字列として等しいか、リストや配列の要素がすべて等しい

のように判定の緩さと実行効率に違いがあります。特に equal については、コレクションの全ての要素を確認するので他の比較に比べて顕著に遅いです。判定の目的に応じて適切に使い分けましょう。

比較の対象が数値や文字列とあらかじめわかっている場合は、 =, string= などの専用の関数もあります。

要素が配列に含まれているかを検査する関数など、内部的に等値比較をおこなう関数群にも同様に memq, memql, member などのバリエーションがあるので、使い分けましょう。

コンスセルを理解する

LISP のリストは、空リスト (nil) に「コンスセル」(2要素タプル)を被せていくことで作られます:

(cons 1 (cons 2 (cons 3 nil))) ;; = '(1 2 3)

要はリンクトリストです。

たとえば二つのリストを連結したいとき、 Emacs Lisp では append または nconc を使うことができますが、それぞれ次のような違いがあります。

  • (append A B) ... A, B の要素をすべて並べた新しいリストを作る
  • (nconc A B) ... リスト A の末尾を nil からリスト B に置き換える

後者は新しいコンスセルをアロケートしないので効率が良いです。

ただし、元のリスト A は破壊されてしまいます。また B も破壊こそされませんが、一方でコピーもされません。たとえば以下のようなコードを実行すると:

(defconst a '(1 2 3))
(defconst b (nconc '(1 2 3) a)) ;; => '(1 2 3 1 2 3)
(defconst c (nconc '(3 2 1) a)) ;; => '(3 2 1 1 2 3)

メモリ上には木構造のようなものができあがります。

(b) 1 - 2 - 3
             \
              +- (a) 1 - 2 - 3
             /
(c) 3 - 2 - 1

ここでたとえばリスト a の先頭 1 を破壊的に書き換えると:

(setcar a 9)
(print a) ;; => '(9 2 3)

残りのリストたちも書き換わります。

(print b) ;; => '(1 2 3 9 2 3)
(print c) ;; => '(3 2 1 9 2 3)
(b) 1 - 2 - 3
             \
              +- (a) 9 - 2 - 3
             /
(c) 3 - 2 - 1

コンスセルやリストはいたるところで使う LISP の基本オブジェクトなので、このような仕組みを理解した上で上手に活用していくと、よりパフォーマンスの出る Emacs Lisp を書くことができます。