Rust Advent Calendar 2019 1日目 Rust の非同期プログラミングモデルはランタイム観点だと Go のそれに似ている

この記事は Rust Advent Calendar 2019 の1日目の記事になります.

明日は topecongiro さんの予定です.

TL;DR

去る 11/07 に Rust 1.39.0 がリリースされました. これはユーザー待望の async/await 構文が言語機能として取り込まれた安定版リリースとなります. Advent Calendar 最初の記事としては取り上げないわけにはいきません.

もう既に他の良い記事がたくさん書かれていますが, この記事ではそれらを補完する視点から説明してみようと思います.

async/await 構文自体の解説や言語機能としてどう実装するかという話は多いので,

  • 何故 async/await による非同期モデルがユーザー, 言語実装の両観点から扱い易いのか.
  • runtime で Future を効率的に実行するための工夫.

あたりの入門的な話をしようと思います.

async/await の概念自体は知っている人が対象です.

async/await 知らないよって人は, まずは OPTiM TECH BLOG -- Rustの非同期プログラミングをマスターする を読むのが良いでしょう.

いろいろな非同期プログラミングモデル

お題として, web サーバーで大量のリクエストを捌くことを考えます.

あたりが指標になります.

シングルスレッド (非同期機構なし)

ものすごく単純な場合として, 16コアの CPU を積んだサーバーに web アプリのプロセスがひとつあって, それがシングルスレッドで動いているような場合を考えてみます.

use std::net::TcpListener;

fn main() {
    let listener = TcpListener::bind("127.0.0.1:80").unwrap();

    for stream in listener.incoming() {
        let stream = stream.unwrap();

        // 何かの処理をする.
    }
}

引用: https://doc.rust-lang.org/book/ch20-01-single-threaded.html

一度に100リクエストのアクセスが来たとき, このプロセスはそれを順番に処理していきます.

なので, 例えば1リクエストの処理に0.1秒かかるような場合, 100個目のリクエストは約10秒待たされることになります.

きょうびそんなことが許容されることもないでしょう. なので, 非同期に処理をする必要があります.

リクエスト毎にスレッドを立てる

リクエスト毎にスレッドを立てればどうでしょうか.

fn main() {
    let listener = TcpListener::bind("127.0.0.1:80").unwrap();

    for stream in listener.incoming() {
        let stream = stream.unwrap();

        thread::spawn(|| {
            handle_connection(stream);
        });
    }
}

引用: https://doc.rust-lang.org/book/ch20-02-multithreaded.html

16個あるコアを使い切れて, 一番遅いレスポンス(最悪のレイテンシ)は 100 * 0.1 / 16 = 0.625 秒後になります.

これでいいようにも見えますが, 1リクエストあたり 0.001 秒かかる API に 10000 リクエスト来た場合はどうなるでしょうか.

この場合は同時に 10000 スレッド立つことになりますが,

  • このスレッドたちを管理するのは OS です. (よくある) OS は CPU を使いたいスレッドたちが公平に CPU を使えるように, 一定時間ごとに CPU を使えるスレッドを切り替えます. スケジューリングのコストとコンテクストスイッチのコストがかかりますが, これらはそれなりに高価です.
  • 1 OS スレッド毎にそのスレッドが使うスタック領域(メモリ)を確保する必要があります. このスタックのサイズは後から変更できないので, 十分なサイズを割り当てておく必要があります. (スタックについては Performance without the event loop にわかりやすい説明があります.)

このため, スレッド数がコア数よりも大幅に大きい場合は性能が劣化します. この問題を解決するためには, 使用する OS スレッド数を抑える必要があります.

スレッドプール

そういった用途で用いられるのがスレッドプールです.

fn main() {
    let listener = TcpListener::bind("127.0.0.1:80").unwrap();
    let pool = ThreadPool::new(16);

    for stream in listener.incoming() {
        let stream = stream.unwrap();

        pool.execute(|| {
            handle_connection(stream);
        });
    }
}

引用: https://doc.rust-lang.org/book/ch20-02-multithreaded.html

これは最初に説明したシングルスレッドのものをスレッドプールのサイズ分(ここでは16個)並べたものと思うことができます. (Perl, Ruby, Python などでよくある prefork 型の並列化も非同期プログラミングモデルとしてはこれと似たようなものです.)

1リクエストあたり 0.001 秒かかる API に 10000 リクエスト来た場合, 性能劣化もなく, 最悪のレイテンシは 0.625 秒です.

おめでとう! これでコアをフルに使えるようになりました!

と言いたいところですが, これでもまだ不十分です.

fn main() {
    let listener = TcpListener::bind("127.0.0.1:80").unwrap();
    let pool = ThreadPool::new(16);

    for stream in listener.incoming() {
        let stream = stream.unwrap();

        pool.execute(|| {
            handle_connection(stream);
        });
    }
}

fn handle_connection(mut stream: TcpStream) {
    let x = call_other_api();  // 外部 API 呼び出し. 0.999 秒かかる.
    process_something(x);      // このプロセスでの処理. 0.001 秒しかかからない.
}

例えば, 処理に1秒かかる API の中で外部サービスの API 呼び出しをしていて, その呼び出しに 0.999 秒かかっているとします.

このサーバー自体は殆ど処理をしていないのに, 同時に処理できるリクエストの数は最大でもスレッドプールのサイズ分です.

つまり RPS (Request Per Second; 1秒あたりに処理できるリクエスト数)は

RPS = スレッドプールのサイズ / 処理にかかる時間

になります. 上の例だと秒間 16 リクエストしか捌けません.

別の毛色の違う例としては, エディタなどの GUI アプリケーションで各コンポーネントを並列に動かすような場合です.

スレッドプールのサイズより多くのコンポーネントたちが同時に(人間や外部プロセスとの通信などで)入力待ちをしようとすると, スレッドが足りずにデッドロックします.

まぁ, このケースだと処理の負荷はあまり問題にならないことが多いので, サイズを固定しないスレッドプールを使うという選択肢もありますが.

これらのケースで共通するのは, 「処理のコンテキストを保持したまま, blocking な処理をしたい」ということです.

(blocking な処理というのは, 正確ではないですがラフに言えば「CPU を消費しないが時間がかかる処理」のことです.)

これにはコルーチンが利用できます.

コルーチン

通常の関数は呼び出した後は return されるだけです. それに対し, 呼び出した後に中断で一度処理を戻し, 後で再開できるもののことをコルーチンと言います.

コルーチンには symmetric/asymmetric なものと stackful/stackless のものがあり, 言語やライブラリによって違います.

「処理のコンテキストを保持したまま, blocking な処理をしたい」という文脈で一番簡単なのは asymmetric stackful coroutine です.

実装方法として例えば, 関数呼び出し時にスレッドを立てて戻り値返却/処理再開用の channel を与えて呼び出し, 処理を戻したい場合は戻り値返却用の channel に値を流して処理再開用の channel で待つようにします.

(Go のプログラムを書くときに似たようなパターンが頻出すると思います.)

この「スレッドが自分の stack を持っている」というのが stackful, 「呼び出し元にしか処理を委譲できない」というのが asymmetric です.

逆に symmetric coroutine は呼び出し元以外にも処理を委譲できます. 処理の委譲をするのが「次の処理を行う」というひとつで, 関数を呼び出すのも値を戻すのも同じ動作でできるから symmetric なわけです.

symmetric stackful coroutine に近いモデルが Rust/tokio の blocking API です.

https://qiita.com/legokichi/items/30e577d996851b6b3ba1

blocking 処理のためにそれ用のスレッドプールに自分で入り, 別のスレッドに処理を委譲します.

ただ, これはスレッドプールのサイズ問題を緩和するためのもの(という風に理解している)であり, コンテキストスイッチが発生する問題は残っています.

コルーチンについては他にも色々あるのでここでは詳しくは述べません. (というか自分もそこまで詳しくない.) 詳しく知りたい方は以下のリンク先のリンクから入るのがよいかもしれません.

https://gist.github.com/yutopp/d3a184f3389df819a5b4b99f2da9b774

Goroutine

最近人気の Go は簡単に並列化対応したプログラムを書けると言われています. これは

  • コンパイラが頑張っている: blocking な API 呼び出しを non-blocking にしていたり, 実行しているタスクの切り替えをユーザーから隠蔽している. (ので, 従来的な書き方のまま並列に動作するプログラムが書き易い.)
  • MPG model: M:N モデルの work stealing スケジューラなので少ないスレッドで効率的に処理ができる. (上の Rust/tokio の blocking API の仕組みも内蔵している. 自動でやってくれるのでユーザーは特別なことをしなくてもよい.)
  • netpoller: 頻出するネットワーク通信の API については, epoll/kqueue を利用している. (OS スレッド数を抑える効果もある.)
  • 可変のスタックサイズ

というのが主なポイントです.

(因みに, Go は stackful symmetric coroutine と言えると思います. 自分は Go の runtime のソースコード読んでないので間違っているかもですが.)

上記は以下の記事で大変わかりやすく解説されているため, ここでは解説しません.

じゃあ, goroutine を Rust に輸入すればいいじゃないかと思うかもしれませんが, Rust が重要視しているものと噛み合わないため, そのままでは難しいのだと思います.

  • ユーザーレベルのスタック操作: goroutine はそれぞれスタックを持っており, タスクの切り替えはそれらを切り替えることで実現される. これにはアセンブラによるスタック操作が必要.
    • 古くは Rust にもこの種のものがあったが, なくなった.
  • 可変スタックサイズや自動でのタスク切り替えのためには, ユーザーが書いたプログラム中にコンパイラが別の命令を差し込む必要がある.
    • OS やベアメタル用途も見据える関係上, コードは書かれたものそのまま動作するべき.

Rust での方針: async/await, Future, Pin, runtime, Waker

Rust の方針は, 上記の Go の方法を上手いこと Rust 流に落し込んだものだと見做すことができるでしょう. (断片的にしか追ってないので, それを意図されているかは知りません. ご存知の方がいたら教えてください.)

表層としては,

  • async/await 構文を Future に変換.
  • Future は asymmetric stackless coroutine. 状態機械として実装可能なので低コスト.
  • Future は合成可能なので asymmetric stackful coroutine 概念を作れる.
  • runtime がそれらを管理することで symmetric stackful coroutine のように見做せる.

詳細:

注意ですが, あくまでも後ろのふたつは概念的にそう見做せるという話です. symmetric/asymmetric や stackful/stackless の定義的には厳密には違うと思います.

アセンブリでスタックポインタを切り替えるのを, runtime が Future を poll して, 戻ってきて, 別の Future を poll する, というので実現しているわけですね.

メモリ管理としては,

  • Future は状態機械なのでヒープに確保すればよいはず.
  • 問題となる自己参照のケースは Pin を導入することによって解決.

詳細:

ただ, 愚直に Future を poll するだけだと, 実はできる仕事がないのに CPU を手放せないということになってしまいます. それを解決するのが Waker です.

(雑に言うと) Waker は Future を poll して欲しくなったら叩くスイッチですが, これは Go で blocking な goroutine が再開可能になったときに global queue に入る動作に似ています.

epoll/kqueue を管理する netpoller に対応するのが, mio などのライブラリなわけです. こういったライブラリは Waker のインターフェースを利用してタスクの実行可否を runtime に伝えることになります.

まとめ

  • いろいろな非同期プログラミングモデルがあり, スレッドプールなど単体では不十分.
  • ユーザーからすると, 非同期プログラミングモデルとして stackful coroutine が扱い易い.
  • Go の方法が参考になるが, そのままでは Rust に導入できない.
  • async/await, Pin, Waker などにより, Go のモデルを上手く Rust に導入することができた. (と見做せる.)

一連の話は Rust に導入するという話でしたが, 実はこれは(OS スレッドは触れるがアセンブリで危いことはできない/したくない)他の言語でも可能でしょう.

Common Lisp はそれに該当する言語で, 実際にやってみようと思ってます.

Rust Advent Calendar 2019, 明日は topecongiro さんの予定です.

Emacs Lisp で quasiquote はどれくらい速いのか?

memo Lisp Emacs Lisp

最近consとlistとかをあまり使わなくなったことに気付いた. 昔はリストを返すときは地道にconsしていた気がするのだけれど, いつからかquasiquoteの味をしめたようでツリーの場合はもちろん単純にconsやlistすればいいときなんかにも読み易さとか条件分岐の兼ね合いとかでquasiquoteを使っている場合も多い.

そういう事情もあってふと, 効率が気になった. コンパイラが頑張ればlistやconsを使うのと同等の測度が出るはずなので, 取り敢えず簡単な計測をしてみた.

(defun my:test-list (x)
  (list 0
        (list (list 1 2)
              (list x 4))))
(defun my:test-quasiquote (x)
  `(0 ((1 2) (,x 4))))

(my:test-list 100)
; => (0
;     ((1 2)
;      (100 4)))
(my:test-quasiquote 100)
; => (0
;     ((1 2)
;      (100 4)))

(let ((elp-function-list '(my:test-list my:test-quasiquote)))
  (elp-instrument-list)
  (dotimes (i 100000)
    (my:test-list 100)
    (my:test-quasiquote 100))
  (elp-results)
  (elp-reset-list))

実行すると以下の様な結果になった. (全て起動直後の値.)

(version)
; => "GNU Emacs 24.2.1 (amd64-portbld-freebsd9.1, GTK+ Version 2.24.6)

;;; Interpreted case
;;; 1st
;;  Function Name       Call Count  Elapsed Time  Average Time
;;  my:test-quasiquote  100000      2.0486769999  2.048...e-05
;;  my:test-list        100000      0.5728829999  5.728...e-06
;;; 2nd
;;  Function Name       Call Count  Elapsed Time  Average Time
;;  my:test-quasiquote  100000      2.0178639999  2.017...e-05
;;  my:test-list        100000      0.4008109999  4.008...e-06

;;; Compiled case
;;; 1st
;;  Function Name       Call Count  Elapsed Time  Average Time
;;  my:test-quasiquote  100000      0.3489519999  3.489...e-06
;;  my:test-list        100000      0.3064099999  3.064...e-06
;;; 2nd
;;  my:test-quasiquote  100000      0.1925460000  1.925...e-06
;;  my:test-list        100000      0.1898700000  1.898...e-06

まぁ予想通りですね. しかしコンパイルしてもquasiquoteの方がちょっと遅いのが何故なのか気になる.

(defun my:test-list-2 (x y)
  (list 0
        (list (list (cons x 2)
                    3)
              (list y
                    (list 5 6)))))
(defun my:test-quasiquote-2 (x y)
  `(0 (((,x . 2) 3) (,y (5 6)))))

;;; from quasiquote-test.elc
; (defalias 'my:test-list #[(x) "\301\302\303D^H\304DDD\207" [x 0 1 2 4] 4])
; (defalias 'my:test-quasiquote #[(x) "\301\302^H\303BDD\207" [x 0 (1 2) (4)] 4])
; (defalias 'my:test-list-2 #[(x y) "\302^H\303B\304D	\305\306DDDD\207" [x y 0 2 3 5 6] 5])
; (defalias 'my:test-quasiquote-2 #[(x y) "\302^H\303B\304B	\305BDD\207" [x y 0 2 (3) ((5 6))] 4])

コンパイルした .elc の中身はこんな感じになっていた. うーむ, 何でそこまでやってるのに最後までやらないんだ(笑)

取り敢えず速度に大きな影響を与えはしなさそうなので安心してquasiquoteを使うことにする.

`(Happy quasiquoted ,life !)


quasiquotedを使って構築されたリストを返すマクロ

蛇足. たまに, quasiquoteのレシピを返すマクロを書きたいときがある. (どうしてもコンパイル時に展開して欲しいんだけどmacroexpandがdefsubstを展開してくれないのでdefmacroを使うしかなかったり.)設計が悪いと言えばそうなのだけれど.

Emacs Lispではspecial formとして quasiquote や unquote は存在しない. 代りに \` と \, と \,@ を使う. (list 'unquote 'a) みたいなのを書くには `(,'\` 'a) と書く.

`(,x a)

みたいなのだと

`(,'\` ((,'\, x) a))

という風になる.

(defmacro f (y)
  `(,'\` ((,'\, ,y) a)))
(let ((x 1))
 (f x))
; => (1 a)

参考

Schemeのマクロ -- Island Life

>>私がLispを知るきっかけとなった『CプログラムブックIII Lisp処理系の作成』 でも、確か「熟練したLispプログラマはlistなんて使いません。 リストを作る時はbackquoteを使います」って説明があったような気がする。<<

quasiquote -- togetter
'`'と',' -- Qiita

alias中のawkの挙動がまったくわからん

zsh

同じコマンドなのにaliasするのとしないので違いが出る. まったくわからん.

$ echo "Oh \\My God" | awk '{print $1}'
Oh
$ alias ohmygod="echo 'Oh \\My God' | awk '{print $1}'"
$ ohmygod
Oh \My God

謎の挙動. bash, zsh, tshで確認.
わかりにくいがどちらも \\M は一回だけ展開されて \M になる.

誰かわかる人がいたら教えてください.

zshで略語展開

zsh Dvorak

zshにはglobal aliasという機能があって, commandの位置(例えば行頭)以外でもaliasが使えるようになっている. 例えば

$ alias -g L='| less'

とすれば

$ some-command L

は

$ some-command | less

に展開されて実行される. けれどもこれだと予期せず展開されることがあるのと, historyに展開されてない形で記録されるので使い難い.

http://homepage1.nifty.com/blankspace/zsh/zsh.html で紹介されている略語展開はスペースを用いて展開している*1. スペースだと思わぬところで展開されることがあって大文字を入力するのに毎回 C-v を入力しなければならず面倒である. かといって他のキーにbindするにしても, yasnippetの展開は C-. にbindしていてこれはterminalでは使えないので暫く放置していた. (そもそも open-line を使ってないから C-o を展開に使ってもいいかもしれない.)

けれども, zshで略語展開を行なうのは大体行末においてだということに気付いたので C-e にbindして, 行末なら展開, そうでなければ end-of-line するようにしてみた. 以下そのコード*2.

https://gist.github.com/kenoss/8985182

typeset -A myabbrev
myabbrev=(
    "DN"  "&> /dev/null"
    "L"   "| $PAGER "
    "G"   "| grep "
    "S"   "| sed '_|_'"
    "R"   " rm "
    "M"   " mkdir "
    "C"   " cat "
    "TX"  " tar -xvzf "
    "TC"  " tar -cvzf "
    "RS"  "rsync -av --exclude '\#*' --exclude '*~' "
    "FX"  "find _|_ -print0 | xargs -0 "
    "PWD" ""
)

my-expand-abbrev() {
    if [ -z "$RBUFFER" ] ; then
        my-expand-abbrev-aux
    else
        zle end-of-line
    fi
}

my-expand-abbrev-aux() {
    local init last value addleft addright
    init=$(echo -nE "$LBUFFER" | sed -e "s/[_a-zA-Z0-9]*$//")
    last=$(echo -nE "$LBUFFER" | sed -e "s/.*[^_a-zA-Z0-9]\([_a-zA-Z0-9]*\)$/\1/")
    value=${myabbrev[$last]}
    if [[ $value = *_\|_* ]] ; then
        addleft=${value%%_\|_*}
        addright=${value#*_\|_}
    else
        addleft=$value
        addright=""
    fi
    if [ "$last" = "PWD" ] ; then
        LBUFFER=""
        RBUFFER="$PWD"
    else
        LBUFFER=$init${addleft:-$last }
        RBUFFER=$addright$RBUFFER
    fi
}

zle -N my-expand-abbrev
bindkey "^e" my-expand-abbrev

例えば

$ some-command L

で行末にカーソルがあるときに C-e すると

$ some-command | less

に展開される. おまけに

$ FX

だと

$ find  -print0 | xargs -0

に展開されて, 「find」の直後にカーソルが動く. 何気に便利.
(PWDは$PWDの値に展開されるんだけど, 何に使ってたんだっけ...?)

global aliasでないのだしShiftからCtrl押すのはめんどいのでキーは小文字にした方が楽かしら?

*1:省略+トリガー文字列+スペースで展開するというのもある. http://hackerific.net/2009/01/23/zsh-abbreviations/

*2:gistが貼れない...

Clojure のインストール

Lisp Clojure FreeBSD

言われた通りにやれば全く問題ないのだけれど, 「まぁ言うてなんとかなるやろ」で躓いたのでメモ.

結論から言うとLeiningen git clone しても駄目. https://github.com/technomancy/leiningen に書いてあるようにパッケージマネージャを使うかスクリプトをダウンロードして入れるべし.

駄目なパターン: git clone してパスを通して

$ lein self-install

しても

Leiningen is missing its dependencies.
Please run "lein bootstrap" in the leiningen-core/ directory
with a stable release of Leiningen. See CONTRIBUTING.md for details.

と怒られる. 言われるがままに(?) git checkout して lein bootstrap しても駄目.

パッケージマネージャが駄目な場合は素直に https://raw.github.com/technomancy/leiningen/stable/bin/lein を ~/bin に入れて lein bootstrap する. ファイルは ~/.lein/ 以下にインストールされる.

最新版を使うにはこの lein を使って leiningen-core/ で lein bootstrap する. 最新版と安定板を使い分けるには https://raw.github.com/technomancy/leiningen/stable/bin/lein にあるように ~/bin/lein を git の bin/lein のsymlinkに, ~/local/bin/lein をstableなもの(へのsymlink)にすればよい.

因みに

  • FreeBSD には lein の port はない.
  • macports にはある. 問題なく使える.
  • rlwrap が要るので portinstall devel/rlwrap しておく.

あと, Javaには java/openjdk7 を使った. 何故か fetch http://download.java.net/openjdk/jdk7u6/promoted/b24/openjdk-7u6-fcs-src-b24-09_aug_2012.zip がめちゃくちゃ遅かったので手動でダウンロードしたけど, それ以外は自動でやってくれたので楽だった. (最初は java/linux-sun-jdk17 を入れたのだけれど symlink しても libjli.so がないと怒られたので.)

参考

第３１７日目：【Java】JDKのインストール方法が変わったみたいです・・・
FreeBSDにJavaをインストール
Clojure開発環境インストール手順(Emacs)
CIDER と ac-nrepl で Clojure開発環境 on Emacs

messageデバッグを投げ捨てろ! debug-print.el -- .emacs Advent Calendar 2013 24日目

Emacs Lisp Gauche

これは .emacs Advent Calendar 2013 24日目の記事です. 日本時間ではもう25日ですがイタリア出張で時間感覚が狂っていたのでセーフです. (すみません.)
printfデバッグを簡単に便利に使えるようにする debug-print.el を紹介します.

インストール

debug-print.el はGitHubに上げています. (https://github.com/kenoss/debug-print) ダウンロードしてパスを通すか, el-getを使っている場合は

(push '(:name debug-print
        :type git
        :url "https://github.com/kenoss/debug-print"
        :description "Gauche's reader macro for printf debugging")
      el-get-sources)

を評価してから M-x el-get-install RET debug-print でインストールできます.

紹介

皆さん Emacs Lisp を書くときにデバッグには何を使われているのでしょうか. backtrace? edebug? 個人的には, backtrace は本当に最低限でデバッグという用途には向かず, 一方 trace-function や edebug は高機能ですが, 例えば前者の場合traceするかどうかをいちいち切り替えする必要があり, 多少面倒だと思います.

これらの中間に位置する使いやすいデバッグ方法は, 誰でも知っているはずのprintfデバッグです. 例えば次のような階乗を計算する函数の呼び出しの挙動を見てみましょう:

(defun fact (n)
(if (zerop n)
    1
    (* n (fact n))))

(見るからに無限ループしそうです...) これを C-x C-e (eval-last-sexp) で定義して (fact 5) してみましょう. おおっと! 予想通り下の方に Lisp nesting exceeds `max-lisp-eval-depth' と出ましたね. こういうバグは backtrace では検知できません.

Emacs Lispでprintfデバッグをするにはmessage函数を使います. 函数 fact がどの様に呼び出されているのかを見てみましょう.

(defun fact (n)
  (message "fact is called with n=%s" n)
  (if (zerop n)
      1
      (* n (fact n))))
(fact 5)

このとき上を評価したときの *Messages* バッファは次のようになりました.

fact
fact is called with n=5
Entering debugger...
yas-extra-modes: Lisp nesting exceeds `max-lisp-eval-depth'
 [2 times]

んー, 「fact is called with n=5」が何回も出て無限ループであることがわかると思ったんですが...

しょうがないですね. debug-print.el を使ってみましょう.

;; debug-print.el を使えるようにする. (予め load-path に通しておく.)
(require 'debug-print)
(debug-print-init)
(define-key global-map (kbd "C-x C-e") 'debug-print-eval-last-sexp)

(defun fact (n)
  (if (zerop n)
      1
      (* n ::?= (fact ::?= n))))
(fact 5)

factの定義と (fact 5) を C-x C-e (debug-print-eval-last-sexp)) で評価すると *debug-print* バッファに次の様なメッセージが延々出てきます.

::?="fact"::(fact (debug-print n nil))    
::?="fact"::n                             
::?-    5                             
::?="fact"::(fact (debug-print n nil))    
::?="fact"::n                             
::?-    5                             
::?="fact"::(fact (debug-print n nil))    
::?="fact"::n                             
::?-    5                             
::?="fact"::(fact (debug-print n nil))    
::?="fact"::n                             
::?-    5

無限ループですね!! ちゃんとした函数に戻しておきましょう.

(defun fact (n)
  (if (zerop n)
      1
      (* n ::?= (fact ::?= (- n 1)))))
(fact 5)

このとき *debug-print* バッファは次の様になります.

::?="fact"::(fact (debug-print (- n 1) fact))
::?="fact"::(- n 1)                       
::?-    4                             
::?="fact"::(fact (debug-print (- n 1) fact))
::?="fact"::(- n 1)                       
::?-    3                             
::?="fact"::(fact (debug-print (- n 1) fact))
::?="fact"::(- n 1)                       
::?-    2                             
::?="fact"::(fact (debug-print (- n 1) fact))
::?="fact"::(- n 1)                       
::?-    1                             
::?="fact"::(fact (debug-print (- n 1) fact))
::?="fact"::(- n 1)                       
::?-    0                             
::?-    1                             
::?-    1                             
::?-    2                             
::?-    6                             
::?-    24

もう使ってしまいましたが, 拙著 debug-print.el (https://github.com/kenoss/debug-print) はprintfデバッグを簡単に便利に使えるようにします. お気付きの方も多いと思いますが, 仕組みはGaucheのリーダマクロ #?= を元にしています. (emacsでは #?= は使えないので debug-print.el では ::?= になっています.) debug-print.el を使えるようにするには, (load-path に debug-print.el を見えるようにした後で) .emcas に次の様に書きます.

(require 'debug-print)
(debug-print-init)
(define-key global-map (kbd "C-x C-e") 'debug-print-eval-last-sexp)

函数 debug-print-eval-last-sexp は eval-last-sexp と似ていますが, シンボル ::?= (変数 debug-print-symbol のデフォルト値)に続くS式をマクロ debug-print で包んでから評価します. 上記例では

(* n ::?= (fact ::?= (- n 1)))))

の行は

(* n (debug-print (fact (debug-print (- n 1) "fact")) "fact"))))

に変換されます. debug-printの2番目の(オプショナルな)引数は「そのS式はどの関数の中にあるか」を示します. 関数 debug-print は *debug-print* バッファに受け取ったS式とそれを評価した結果を表示します. (バッファ名は変数 debug-print-buffer-name で変更可能.) debug-print-eval-last-sexp は下請けの eval-with-bebug-print にS式を渡しますが, ただのS式変換器なので引数が ::?= を含まない場合の作用は普通に評価した場合と同じになります.

至極単純な機構ですが, Gaucheで使っている経験上, 普通のprintfデバッグよりも便利だと思います. 例えば次の

(hoge (something-with-side-effect a) b c)

のhogeの第一引数がどうなっているのか調べたいとき, messageを使うには

(hoge (let ((tmp (something-with-side-effect a)))
        (message "%s" tmp)
        tmp)
      b c)

の様に let (+progn) を使わなければなりません. messageの書式を指定するのも, 確認が終わって元に戻すのも面倒です. その点 debug-print.el は調べたいものの前に ::?= を挟むだけなのでこれらの問題点は全て解消されます.

Merry Christmas & enjoy debugging Emacs Lisp!

明日はtakaxpさんです.

TeX でリスト処理

TeX Lisp

日々TeX言語でプログラムを書いているLisperなら一度は「ここでLispみたいにリスト処理ができたらなぁ」と
感じたことがあるだろう. *1 大抵の場合, 要求される演算はcdrとかlengthとか
for-eachの様な簡単な処理なので, コンマ区切りのリストを使ってその場を凌いだりする...のだろうか.
(TeXで配列が使えることを自分が知ったのは相当後だったと思う.) しかしコンマ区切りのリストでは
それ以上の標準的なリスト処理を即興で書くのは面倒くさい. LISP on TeX
(https://bitbucket.org/hak7a3/lisp-on-tex)の様な高機能なものもあるけど,
(そもそもLoTのことをよく知らないし,) あくまでTeXからちょろちょろっとリストを使いたいだけにしては
大仰だ.


代数的データ型としての実装

ZRさんち id:zrbabbler:20120115:1326571496 ではリストを代数的データ型として扱っていた.
*2 こんな風に:

% LIST := \mwml@NULL | \mwml@CONS{ELEM}{LIST}
% ELEM := anything
\def\mwml@CONS#1#2{}
\def\mwml@NULL{}

% リストの例
\def\listA{\mwml@CONS{A}{\mwml@CONS{B}{\mwml@NULL}}}

さて, リストに新しい要素を付け加えリストを作る \mwml@set@cons を作ろう. これは #1 に制御綴りを取り,
#2 と #3 を cons したリストを束縛する. ZRさんの記事では CONS と NULL を凍結した状態で \edef
するという方法だったが, これでは頑強でないマクロを要素として持つリストを扱えない.
これは \mwml@CONS を \relax に束縛した状態で 第三引数を \expandafter することで解決できる.

\def\mwml@with@freezed@list#1{%
  \let\mwml@CONS@before\mwml@CONS
  \let\mwml@NULL@before\mwml@NULL
  \let\mwml@CONS\relax% 一旦凍結して
  \let\mwml@NULL\relax
  #1% 実行する
  \let\mwml@CONS\mwml@CONS@before
  \let\mwml@NULL\mwml@NULL@before
}

\def\mwml@set@cons#1#2#3{%
% #2 と #3 のconsを #1 に束縛する
  \mwm@in@group@with@nonlocal#1#1{% \begingroup ... \endgorup だが #1 を \endgroup の外に持ち出す
    \mwml@with@freezed@list{%
      \toks2{#2}%
      % #3 が制御綴のときはそれが(一段階だけ)展開される. そうでないときは
      % (リスト #3 は \mwml@CONS か \mwml@CONS で始まるはずで, それは今 \relax してるから)何もしない.
      \toks3\expandafter{#3}%
      \edef#1{\mwml@CONS{\the\toks2}{\the\toks3}}%
    }%
  }%
}

\def\mwm@in@group@with@nonlocal#1#2#3{%
  \begingroup
  #3%
  \global\let\mwm@in@group@with@nonlocal@@a#1% 一旦大域変数に入れて
  \endgroup
  \let#2\mwm@in@group@with@nonlocal@@a% それを戻す
}

第三引数には制御綴りでも生のリストでもどちらでも渡すことができる. 第二引数は展開されないことに注意.

% (setq listA '(A B))
% (setq listB (cons 'Z listA))
\def\listA{\mwml@CONS{A}{\mwml@CONS{B}{\mwml@NULL}}}
\mwml@set@cons\listB{Z}\listA
% => \mwml@CONS{Z}{\mwml@CONS{A}{\mwml@CONS{B}{{\mwml@NULL}}}}

% (setq listC (cons {\nonrobustcmd ごにょごにょ} '(\nonrobustcmd)))
\mwml@set@cons\listC{\nonrobustcmd ごにょごにょ}{\mwml@CONS{\nonrobustcmd}{\mwml@NULL}}
% => \mwml@CONS{\nonrobustcmd ごにょごにょ}{\mwml@CONS{\nonrobustcmd}{\mwml@NULL}}

car と cdr はZRさんちのものをほぼそのまま.

\def\mwml@set@car#1#2{%
% Bind car of #2 to #1
  \mwm@in@group@with@nonlocal#1#1{%
    \def\mwml@CONS##1##2{\def#1{##1}}%
    \let\mwml@NULL\undefined
    #2%
  }%
}
\def\mwml@set@cdr#1#2{%
% Bind cdr of #2 to #1
  \mwm@in@group@with@nonlocal#1#1{%
    \def\mwml@CONS##1##2{\def#1{##2}}%
    \let\mwml@NULL\undefined
    #2%
  }%
}

ここまで来れば後は欲しい函数をどんどん実装するだけである.


例題: 行列を生成する

数学をやっていると行列を書く機会が多い. しかし対角成分のみの行列を書くのに毎回 pmatrix 環境を
書くのは面倒だ. 対角成分が A, B, \ddots, D で右上が*, 左下が空の行列なら

\begin{pmatrix}
  A & * & \cdots & * \\
    & B & \cdots & * \\
    &   & \ddots & \vdots \\
    &   &        & D
\end{pmatrix}

ではなく単純に

\[
  \diagmatrix[*,] A, B, ..., D ;
\]

と書きたい. *3

Lispの演習問題としては簡単だ. Scheme(Gauche)で書くなら, こんな感じになるだろう.
(TeXに移植するのでLispとしては少し不自然. というかTeXのコードを逆にLispに直した)

(use srfi-1)
(use srfi-11)
(use srfi-13)

(define (diagmatrix ufill lfill diagonals)
  (define (dots? str)
    (rxmatch #/^ *(\.\.\.|\\dots)$/ str))
  (define (mask-with e b replacement)
    (if b
        replacement
        e))
  (define (make-row d i b right-cdots left-cdots mask right-line left-line right-dots-line left-dots-line)
    (let-values (((left-mask r) (split-at mask i)))
      (let1 right-mask (cdr r)
        (if b
            `(,@(map (cut mask-with <> <> "") left-dots-line left-mask)
              "\\ddots"
              ,@(map (cut mask-with <> <> "") right-dots-line right-mask))
            `(,@(map (cut mask-with <> <> left-cdots) left-line left-mask)
              ,d
              ,@(map (cut mask-with <> <> right-cdots) right-line right-mask))))))
  (let* ((r (if (string-null? ufill)
                '("" . "")
                '("\\cdots" . "\\vdots")))
         (right-cdots (car r))
         (right-vdots (cdr r))
         (l (if (string-null? lfill)
                '("" . "")
                '("\\cdots" . "\\vdots")))
         (left-cdots (car l))
         (left-vdots (cdr l))
         (mask (map dots? diagonals))
         (size (length diagonals))
         (indice (iota size 0 1))
         (right-line (make-list size ufill))
         (left-line (make-list size lfill))
         (right-dots-line (make-list size right-vdots))
         (left-dots-line (make-list size left-vdots))
         ; row は実際には行列が入る
         (row (map (cut make-row <> <> <>
                        right-cdots left-cdots mask right-line left-line right-dots-line left-dots-line)
                   diagonals indice mask)))
    row))

試しに実行してみよう.

(diagmatrix "*" "0" '("A" "B" "..." "D"))
; => (("A" #0="*" #1="\\cdots" #0#)
;     (#2="0" "B" #1# #0#)
;     (#3="\\vdots" #3# "\\ddots" "\\vdots")
;     (#2# #2# "\\cdots" "D"))

; 見難いが, (2,4)-成分と(4,2)-成分が空になっている
(format "~s" (diagmatrix "0" "0" '("a_1" "..." "a_i" "..." "a_n")))
; => "((a_1 \\cdots 0 \\cdots 0)\
;     (\\vdots \\ddots \\vdots  \\vdots)\
;     (0 \\cdots a_i \\cdots 0)\
;     (\\vdots  \\vdots \\ddots \\vdots)\
;     (0 \\cdots 0 \\cdots a_n))"
(diagmatrix "0" "0" '("a_1" "..." "a_i" "..." "a_n"))
; => (("a_1" #0="\\cdots" #1="0" #0# #1#)
;     (#2="\\vdots" #3="\\ddots" #4="\\vdots" "" #4#)
;     (#5="0" #6="\\cdots" "a_i" #0# #1#)
;     (#2# "" #2# #3# #4#) (#5# #6# #5# #6# "a_n"))

mwmlist.styを使えばこのコードをほぼそのまま移植できる. mainの部分だけなら30行しかない.
(わかりにくいが, 頑強でない要素を取れるようになったので実装自体も少し簡単になっている.
頑強なものを扱えない場合は最初の部分で \mwm@dm@@right@cdots 等を \relax にしておき, 最後に
pmatrix 環境の中身を生成した後で適切なdotのマクロを束縛しなければならない.)

% []の部分を読み取って \mwm@dm@main を呼び出す
\def\diagmatrix{% [ufill,lfill] CSL ;
% Diagonal matrix whose diagonal elements are CSL, upper triangle filled with ufill,
% lower with lfill. In CSL, the strings "..." and "\dots" following spaces have special meaning.
% Matrix elements of rows and columns <dots> exist are replaced with appropriate dots
% as the element see how many <dots> in the diagonal. For example, if an element sees
% <dots> vertically and no <dots> horizontally, it is replaced with \cdots .
  \begingroup
%  \def\mwm@dm@@upper@filling{}%
%  \def\mwm@dm@@lower@filling{}%
  \@ifnextchar[ \mwm@dm@bite@bracket {\mwm@dm@bite@bracket[,]}%
}
    \def\mwm@dm@bite@bracket[#1]{%
      \mwm@dm@bite@bracket@aux#1,\@nil
      \mwm@dm@main
    }
        \def\mwm@dm@bite@bracket@aux#1,#2\@nil{%
          \def\@tempa{#2}%
          \ifx\@tempa\@empty
            \def\mwm@dm@@upper@filling{#1}%
            \def\mwm@dm@@lower@filling{#1}%
          \else
            \mwm@dm@bite@bracket@aux@two#1,#2\@nil
          \fi
        }
            \def\mwm@dm@bite@bracket@aux@two#1,#2,\@nil{%
              \def\mwm@dm@@upper@filling{#1}%
              \def\mwm@dm@@lower@filling{#2}%
            }
    \def\mwm@dm@main#1;{%
      % 色々設定する
      % filling が空ならドットはなし
      \let\mwm@dm@@ddots\ddots
      \ifx\mwm@dm@@upper@filling\@empty
        \let\mwm@dm@@right@cdots\relax
        \let\mwm@dm@@right@vdots\relax
      \else
        \let\mwm@dm@@right@cdots\cdots
        \let\mwm@dm@@right@vdots\vdots
      \fi
      \ifx\mwm@dm@@lower@filling\@empty
        \let\mwm@dm@@left@cdots\relax
        \let\mwm@dm@@left@vdots\relax
      \else
        \let\mwm@dm@@left@cdots\cdots
        \let\mwm@dm@@left@vdots\vdots
      \fi
      \mwml@set@list@from@csl\mwm@dm@@diagonals{#1}% コンマ区切りリストからリストへ変換
      \mwm@dm@make@mask% どの対角成分に「ドット」が入っているかのマスクを作る. \mwm@dm@@mask に束縛する.
      \mwml@set@length\mwm@dm@@size\mwm@dm@@diagonals
      \mwml@set@iota\mwm@dm@@iota\mwm@dm@@size{0}{1}% 普通の行列の添字とは異なることに注意.
      \mwml@set@make@list\mwm@dm@@right@line\mwm@dm@@size\mwm@dm@@upper@filling% ufill を並べたリスト
      \mwml@set@make@list\mwm@dm@@left@line\mwm@dm@@size\mwm@dm@@lower@filling% lfill を並べたリスト
      \mwml@set@make@list\mwm@dm@@dots@left@line\mwm@dm@@size{\mwm@dm@@left@vdots}%% 左側のドットを並べたリスト
      \mwml@set@make@list\mwm@dm@@dots@right@line\mwm@dm@@size{\mwm@dm@@right@vdots}%% 同様
      % メインの処理
      % \mwm@dm@make@row (3引数函数) は返り値を \mwm@dm@@row に入れる.
      % #1 は #2 番目の対角成分, #3 は #1 が「ドット」かどうか. 返り値は #2 番目の行を表すリスト.
      \mwml@set@map@three\mwm@dm@@row\mwm@dm@make@row\mwm@dm@@diagonals\mwm@dm@@iota\mwm@dm@@mask
      % \mwml@set@map@three は生成したリストを \mwm@dm@@row に入れる.
      \mwml@output@matrix@with@pmatrix\mwm@dm@@row% 行列を表示する
      \endgroup
    }
% 続く...

あとは残った補助函数を書けばいいのだが, (コメントを書くのが)面倒なので興味があれば
https://gist.github.com/kenoss/6384624を見てみるとよい. (\diagmatrixは全部で120行.)

*1:もちろん個人差がある.

*2:書いてから思ったけど, この記事パクリ以外の何ものでもないのでは...

*3:実のところ, 普通に配列でやろうとして挫折して mwmlist.sty を書いた.