リリカル☆Lisp開発日記

Common Lispで作っているWIkiエンジンですが、
今までCLISP専用だったものをSBCLでも動くようにしました。
変更することになったのは主に以下の三つです。
1. 文字コードまわり
2. ディレクトリ操作まわり
3. ネットワークまわり
文字コードまわりはCommon Lisp と 日本語 と 文字コード(LISPUSER)を参考にしました。
基本的にはcharset:utf-8を:utf-8に変えるのと、
ext:convert-string-from-bytesをsb-ext:octets-to-stringに変えるだけでした。
ディレクトリからファイル一覧を取得するための方法はPractical Common Lispの
15. Practical: A Portable Pathname Library
を参考にしました。処理系毎にちょっとずつ違うのは正直やっかい。
あと、ディレクトリの作成、削除にsb-posixパッケージののmkdirとrmdirを使用するように変更。
SBCLのネットワークまわりはある意味わかりやすく、そして面倒でした。
サーバの役割をするためには、まずinet-socketのインスタンスを作って、
sb-bsd-socktesパッケージのsocket-bind, socket-listen, socket-acceptを呼ぶだけ。
いくらわかりやすいとはいえ、少々面倒なのでもう少し楽な関数も欲しかったです。
sb-posixやsb-bsd-socketsパッケージを使うために、
requireを書かないといけないみたいですが、
これってどこに書くものなんでしょう。自分のパッケージを定義するファイル？
何はともあれ、これでSBCLでも動くようになりました。
CLISPで動かしてたときより速く動いた…ような気がします。
気がするだけかもしれません。
—
昨日、「Prologで大阪さんの事を論理的に考える集い」に参加してきました。
いろんなプログラミング言語についてわいわい話し合ってかなり楽しかったです。
ただ、大阪さんの話はほとんど出てきませんでした。
ちゃんとあずまんが大王を全巻読み直して準備してきたのに／（＾ｏ＾）＼

*前回のあらすじ*
文字列を一回なぞって単純な置換をするだけのプログラムの速度が
正規表現エンジンCL-PPCREを使って適当に書いた置換の速度に負けた。
*流石にこれは恥ずかしいので*
CL-PPCREのソースを少し眺めてみることにしました。
気になったのは新たな文字列をどうやって生成しているか。
探してみると、
1. with-output-to-stringでストリームを作成 (先に配列を作ったりはしない)
2. write-stringでストリームに書き込み
という感じになっていました。
*勝利の鍵はwrite-string*
write-stringがどんな関数だったか覚えていなかったので、HyperSpecで調べてみると、
ストリームに文字列を書き出すというのはprincと同じですが、文字列専用な上に、
キーワード引数:startと:endをとり、部分文字列を書き出せるようになってました。
これはどう考えてもprincにsubseqで切り出した文字列を書き出させるより速いはず。
ということで、自作プログラムを書き直して再度速度を比較。

;; 自作プログラム
Evaluation took:
0.005 seconds of real time
0.004562 seconds of total run time (0.004562 user, 0.000000 system)
100.00% CPU
6,969,080 processor cycles
560,584 bytes consed
;; CL-PPCRE
Evaluation took:
0.025 seconds of real time
0.025393 seconds of total run time (0.025393 user, 0.000000 system)
100.00% CPU
38,050,333 processor cycles
2,368,328 bytes consed

やりました。今度は見事に勝利しました。
もっとも、簡単な置換しかできないプログラムが、
正規表現エンジンに負けてたら洒落にならないんですけど(笑)
(と言いながら、CL-PPCREを上手く使ったプログラムに負けたらどうしよう…)
*おまけ*
inner-line-convertはこんな関数です。
マクロdef-inner-convertがどうなっているかは、
各自ご想像にお任せします。

(defun inner-line-convert (line)
(declare (optimize (speed 3) (safety 0) (space 0)))
(declare (string line))
(def-inner-convert (line)
("<" "&lt;")
(">" "&gt;")
("''" "<b>" "''" "</b>")
("'''" "<i>" "'''" "</i>")
("[[" "]]" #'inner-link)))

それなりに速い文字列探索は書けましたが、
これを使って文字列の置換を行うプログラムを書いたら、
GCが頻繁に動きあまり速くありませんでした ＼（＾o＾）／
make-arrayで作った配列に、with-output-to-stringを使って
princで書き込むといった感じのプログラムを書いたんですが、
配列の大きさが足りなくなるのを恐れて:adjustableをtにしたのが速度を低下させてるかも。
けど、nilにしたところで、自分で境界のチェックとかした方が遅いかもしれません。
文字列の一部をコピーする際にsubseqしたものをprincで書き込んでるけど、
これは文字列のコピーが一旦作られるからGC発生の原因の一つになってそうです。
Cのmemcpyみたいな関数があればい\いんですけどね。
subseqの代わりにdisplaced-arrayでも\使えばいいのか？
CLで高速な文字列操作を行うのは色々とコツがいりそうです。
*恐怖! 処理系組み込みのsearchは遅かった!?*
(追記)SBCLは一工夫でかなり速くなりました。最後まで読んでね。
なんだか悲しい事実を知ってしまいました。

(defmacro! dfa-search (str1 str2 &key start2 end2)
`(dfa-multi-search (,str2 ,g!pos :start ,start2 :end ,end2)
,str1 ,g!pos))

dfa-searchは見ての通り、dfa-multi-searchのラッパーです。
dfa-multi-searchは複数の候補をDFAを使って探索しますが、
候補が一つしかない場合は、単に文字列を先頭から1文字ずつ見るだけなので、
決して特別速いコードは生成されません。

(defvar *text*
"Function SEARCH
...(全体で1490文字)...
matching subsequence is returned.")
(defun bench% ()
(declare (optimize (speed 3) (safety 0) (space 0)))
(time (progn (dotimes (i 1000) (search "Syntax" *text*))
(dotimes (i 1000) (search "Arguments" *text*))
(dotimes (i 1000) (search "Description" *text*))
(dotimes (i 1000) (search "\\(^o^)/" *text*))))
(time (progn (dotimes (i 1000) (dfa-search "Syntax" *text*))
(dotimes (i 1000) (dfa-search "Arguments" *text*))
(dotimes (i 1000) (dfa-search "Description" *text*))
(dotimes (i 1000) (dfa-search "\\(^o^)/" *text*)))))

HyperSpecのsearchの説明(の一部)から4種類の文字列を
searchとdfa-searchで検索してみました。
結果は次の通りです。

;;; CLISP
;; search
Real time: 1.104947 sec.
Run time: 1.085989 sec.
Space: 0 Bytes
;; dfa-search
Real time: 0.768655 sec.
Run time: 0.746108 sec.
Space: 0 Bytes

;;; SBCL
;; search
Evaluation took:
0.139 seconds of real time
0.138718 seconds of total run time (0.138718 user, 0.000000 system)
100.00% CPU
208,102,940 processor cycles
0 bytes consed
;; dfa-search
Evaluation took:
0.048 seconds of real time
0.048145 seconds of total run time (0.048145 user, 0.000000 system)
100.00% CPU
72,104,234 processor cycles
0 bytes consed

;;; CMUCL
;; search
; Evaluation took:
;   0.33 seconds of real time
;   0.31113 seconds of user run time
;   0.0 seconds of system run time
;   488,008,050 CPU cycles
;   0 page faults and
;   0 bytes consed.
;; dfa-search
; Evaluation took:
;   0.09 seconds of real time
;   0.071036 seconds of user run time
;   0.0 seconds of system run time
;   125,955,056 CPU cycles
;   0 page faults and
;   0 bytes consed.

search遅い!!!
自分の書いたプログラムの方が速かったのに、全然嬉しくない…
基本的な関数なんだからしっかりと最適化してほしいです。
(それとも、ひょっとすると本物のLisperはあまりsearchを使わないのか?)

ytakenakaさんに薦めて頂いたCL-PPCREを使ってみました。
あと、インストールの為にASDFも初めて使ってみることに。

;;; 最初からASDFが入っているSBCLで試しました
* (require 'asdf-install)
* (require 'asdf)
* (asdf-install:install :cl-ppcre)
;; 個人向けインストールかPC全体へのインストールか選択
;; ダウンロード先を信頼していいのか選択
* (asdf:oos 'asdf:load-op :clppcre)
;; これでCL-PPCREを使う準備が完了したみたいです

インストール時の質問が、デバッガを利用して作られており、なかなか面白かったです。
で、使い方もよくわからないままに、とりあえず自分のプログラムと速度を比べてみました。

(defvar *rep-text* "This is ''bold'' and '''italic''' test.")
(defun bench%% ()
(declare (optimize (speed 3) (safety 0) (space 0)))
(time
(dotimes (_ 1000)
(inner-line-convert (the string *rep-text*))))
(time
(dotimes (_ 1000)
(cl-ppcre:regex-replace-all
"''(.+)''"
(cl-ppcre:regex-replace-all "'''(.+)'''"
(the string *rep-text*)
(list "<i>" 0 "</i>"))
(list "<b>" 0 "</b>")))))

* (bench%%)
;; 自作プログラム
Evaluation took:
0.054 seconds of real time
0.054610 seconds of total run time (0.054610 user, 0.000000 system)
[ Run times consist of 0.004 seconds GC time, and 0.051 seconds non-GC time. ]
101.85% CPU
81,858,953 processor cycles
16,181,024 bytes consed
;; CL-PPCRE
Evaluation took:
0.026 seconds of real time
0.025287 seconds of total run time (0.025287 user, 0.000000 system)
96.15% CPU
37,694,210 processor cycles
2,367,952 bytes consed

見事に負けました。
それから、CL-PPCREかなり適当に書いたので、おそらくもっと頑張れそうです。
ボロ負け　＼（＾ｏ＾）／

前のエントリーで書いたdfa-multi-searchの展開形がメモリを食う原因は、
labelsで作った関数を呼んでいたことみたいです。
インライン化して、ついでに型宣言と最適化オプションもつけたところ、
だいぶ速くなってきました。

;;; CLISP
Real time: 0.427904 sec.
Run time: 0.416979 sec.
Space: 0 Bytes
;;; SBCL
Evaluation took:
0.025 seconds of real time
0.024786 seconds of total run time (0.024786 user, 0.000000 system)
100.00% CPU
37,124,872 processor cycles
0 bytes consed

このあたりまできたら、Cとも張り合えるんじゃないかと思い、
似たようなソースをCで書いてみました。

#include <stdio.h>
#include <string.h>
#include <sys/time.h>
char test_data[4][64] = {"This ''text'' is bold sample.",
"This '''text''' is italic sample.",
"This %%text%% is torikeshi sample.",
"This ((text)) is footnote sample."};
int aho_search (char *str)
{
if (strstr(str, "'''")) {
return 0;
}
else if (strstr(str, "''")) {
return 1;
}
else if (strstr(str, "%%")) {
return 2;
}
else if (strstr(str, "((")) {
return 3;
}
return -1;
}
int baka_search(char *str)
{
int state = 0;
for (;;) {
if (*str == '\'') {
if (state == 1) state = 2;
else if (state == 2) return 0;
else state = 1;
}
else if (state == 2) {
return 1;
}
else if (*str == '%') {
if (state == 11) return 2;
else state = 11;
}
else if (*str == '(') {
if (state == 21) return 3;
else state = 21;
}
else {
state = 0;
}
if (*str == '\0') {
break;
}
str++;
}
return -1;
}

strstrを使ったアホな検索をするaho_search、
出来の悪い状態遷移を使ったbaka_search、
この二つをCLの時と同様に10000回ずつ呼んでみました。
処理系はGCC4.2.1で最適化オプションは無しです。

0.038932sec (aho_search)
0.011319sec (baka_search)

SBCLとならかなりいい勝負になってます。
「いい勝負とか言いながら、2倍以上差がついとるで！」
という意見ももちろんあるでしょうが、
baka_searchみたいな関数を、あまり手書きで書きたくないことも考慮に入れれば、
CLの方が勝っていると言えるだろうという私の独断と偏見を書いておきます(笑)
それにしてもstrstrは速いですね。どうなってるんだろ…
*追記*
CMUCLでも試したら、その速さに驚きました。
ただ、searchはSBCLより遅いみたいです。

;;; CMUCL
* (bench)
;; aho-search
; Evaluation took:
;   0.77 seconds of real time
;   0.756969 seconds of user run time
;   0.0 seconds of system run time
;   1,154,705,100 CPU cycles
;   0 page faults and
;   0 bytes consed.
;; use-dfa
; Evaluation took:
;   0.02 seconds of real time
;   0.017071 seconds of user run time
;   0.0 seconds of system run time
;   29,234,741 CPU cycles
;   0 page faults and
;   0 bytes consed.

無駄に長くなりそうなので先に結論から。
バカな文字列検索と比べると速い文字列の検索のコードを書きました。
オートマトンとか使ってるからちょっと格好良くなった気分です。

めちゃくちゃ速くなった反面、メモリを使いすぎてます。
原因は不明。どうやってメモリ使用量を減らせれるかが今後の課題です。
(ここまで結論でした。)
—
ちょっとずつですが、Common LispでWikiをつくってます。
で、Wiki文法からHTMLへの変換の際の文字列処理の話を少し。
Wiki文法からHTMLへの変換規則の一例として、
– 「”bold”」と出会ったら「<b>bold</b>」に変換
– 「”’italic”’」と出会ったら「<i>italic</i>」に変換
といったものがあります。
で、私が「とりあえず動けばいいや」で最初に書いたコードはというと、
searchで文字列から「”’」を探して変換して、「”」を探して変換して…
と言ったものでした。非常にばかばかしくて素晴らしいです。
「じゃあ、正規表現を使えばええやん」
という意見が飛んできそうですが、それじゃあ面白くない
正規表現を使っても以下のような問題がありそうです。
1) 変換規則の数だけ文字列全体を走査しないといけない
2) 「”」の前に「”’」を探さないといけないといった制約がある
(拡張された正規表現をガリガリ書ける人は上手く書けるのかもしれませんが…)
「単純な文字列の変換処理くらい1passで終わらせたいよね」という考えを前提にして、
「検索候補が複数書けるsearchがあればいいんじゃないか」という結論にたどり着きました。

(multi-search "''" "'''" "%%" "((" target)
=> (最初に)どの文字列にtargetの何文字目でヒットしたか

どの文字列にヒットしたかであとで条件分岐するのはほぼ確実なんだから
ということで、

(multi-search (target pos)
"''"  `(bold at ,pos)
"'''" `(italic at ,pos)
"%%"  `(torikeshi at ,pos)
"(("   `(footnote at ,pos))

こんな風に書けるようにしよう。
と、目標を定めたところで作り始めました。
「探す文字列は先に決まっているんだから、効率のよいコードを生成しよう。」
ということで、決定性有限オートマトンを作って探索をすることに。
だいたいこんな感じです。
文字列のリスト -> NFA -> DFA -> Lispコード
(NFA : 非決定性オートマトン, DFA : 決定性オートマトン)
「NFAはすぐに作れるし、DFAに変換するのも教科書的なやり方で充分だろう」
と最初は思ったんですが、よくよく考えてみると少々厄介でした。
pat1 = aa
pat2 = baaab
pat3 = aaac
文字列の中から上記pat1, pat2, pat3を検索する場合、入力が
「baaab」の場合 => 0文字目でpat2にヒット
「baaac」の場合 => 1文字目でpat3にヒット
「baaad」の場合 => 1文字目でpat1にヒット
こんな風に動作して欲しいんですが、ただただDFAを作るだけではこれが実現出来ません。
ヒットするものの候補が複数ある場合、
A) より手前でヒットしたものが優先
B)同じ時点でヒットしたものがあれば長い物を優先
という規則で動作して欲しいので、これを考慮してDFAを構築することにしました。
規則Aは、NFAにおいて「初期状態から何回で遷移可能か」という情報から、
「何文字手前からヒットし始めたか」という情報が得られるので、
これを使ってDFAの遷移から不要なものを消すことによって達成出来ました。
規則Bは、規則Aさえ満たしていれば、「最後に到達した受理状態」を覚えておき、
遷移できなくなれば、それを使うという風にすればすぐに出来ました。
そんなこんなでエントリー冒頭の結論に辿り着きました。
なんであんなにメモリを食うのか、現状ではまったく分かりません。
マクロの展開形を載せておくので、原因が分かった人はこっそり教えてください(笑)

CL-USER> (macroexpand-1
'(dfa-multi-search (str)
"''"  'bold
"'''" 'italic
"%%"  'torikeshi
"(("  'footnote))
(LET ((#:STR131488 STR))
(LET (#:LAST-POS131490 #:LAST-STATE131491)
(BLOCK #:BLOCK131484
(LABELS
((#:TRANS131486 (#:STATE131487 #:CHAR131483 #:POS131489)
(CASE #:STATE131487
((T)
(CASE #:CHAR131483 (#\( '#:G131507) (#\% '#:G131506) (#\' '#:G131505)
(OTHERWISE T)))
((#:G131507)
(CASE #:CHAR131483 (#\( '#:G131508) (#\% '#:G131506) (#\' '#:G131505)
(OTHERWISE T)))
((#:G131508) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131502)
(CASE #:CHAR131483 (OTHERWISE (RETURN-FROM #:BLOCK131484 T))))
((#:G131506)
(CASE #:CHAR131483 (#\% '#:G131509) (#\( '#:G131507) (#\' '#:G131505)
(OTHERWISE T)))
((#:G131509) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131499)
(CASE #:CHAR131483 (OTHERWISE (RETURN-FROM #:BLOCK131484 T))))
((#:G131505)
(CASE #:CHAR131483 (#\' '#:G131510) (#\( '#:G131507) (#\% '#:G131506)
(OTHERWISE T)))
((#:G131510) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131492)
(CASE #:CHAR131483 (#\' '#:G131511)
(OTHERWISE (RETURN-FROM #:BLOCK131484 T))))
((#:G131511) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131495)
(CASE #:CHAR131483 (OTHERWISE (RETURN-FROM #:BLOCK131484 T)))))))
(DO
((#:STATE131487 T) (#:POS131489 0 (1+ #:POS131489))
(#:LEN131485 (LENGTH #:STR131488)))
((>= #:POS131489 #:LEN131485)
(#:TRANS131486 #:STATE131487 #\Null #:POS131489) NIL)
(SETF #:STATE131487
(#:TRANS131486 #:STATE131487 (AREF #:STR131488 #:POS131489)
#:POS131489)))))
(CASE #:LAST-STATE131491 ((#:G131502) (LET NIL 'FOOTNOTE))
((#:G131499) (LET NIL 'TORIKESHI)) ((#:G131492) (LET NIL 'BOLD))
((#:G131495) (LET NIL 'ITALIC)))))
T

defmacro!を知って以来、defmacro!なしにマクロを書けない体になってしまいました。
Let Over Lambdaは体に毒です。注意しましょう。
実際にdefmacro!を使うようになって気になったことを二つほど。
*なぜprogn*
Let Over Lambdaでのdefmacro!の定義は次のようになっています。

(defmacro defmacro! (name args &rest body)
(let* ((os (remove-if-not #'o!-symbol-p args))
(gs (mapcar #'o!-symbol-to-g!-symbol os)))
`(defmacro/g! ,name ,args
`(let ,(mapcar #'list (list ,@gs) (list ,@os))
,(progn ,@body)))))

この定義を見て気になったのが最後の行のprognです。
続くのが ,@body だけなら、わざわざprognで囲まなくても、
,,@body
とだけ書けば充分じゃないのかと思い、そう書き換えてみました。
書き換えて使ってもまったく問題が無かったのでそのままにしていたんですが、
ある時にそのprognの意味を知らされました。

(defmacro! hoge (&rest args)
(unless (= (mod (length args) 2) 0)
(error "odd number of arguments"))
...))

prognがない場合、unlessが返すNILが取り残され、
(hoge 1 2 3 4) などの展開形が次のようになってしまいます。

(let (...)
NIL
...)

何の説明もなく、おまけのように付属しているprognが、
実は意味を持っていたというのはやられました。
*引数の分配に対応してない*
勝手に取り外したprognを付けなおし、
定義どおりのdefmacro!を使っていたら、
今度は次のようなコードを書いた際にコンパイルエラーが発生しました。

(defmacro! foo ((o!bar &optional ...) &rest rest)
...)

defmacro!の定義を見直してみれば一目瞭然。
(remove-if-not #’o!-symbol-p args)
と、argsが平らであるのが前提なコードが書いてあるので、
(flatten args) という風にリストを平坦化することで対応しました。
—
ああ、それから去年の夏頃に「CLでwikiをつくってるよー」と言ってましたが、
最近もちょびちょび触っています。夏の時点で一通りの機能を持っていたんですが、
その頃のCommon Lispの知識が余りに乏しかったため、
汚いコードや無意味なコード(もともとある関数を自分で書いてたり)が多数あり、
書き直しばかりで、なかなか新しい機能を作れないです(笑)

Let Over Lambdaの6章に『#`』というリーダマクロが出てきます。
バッククォートされたものを返す関数を作るためのもので、以下のように定義されています。

(defun |#`-reader| (stream sub-char numarg)
  (declare (ignore sub-char))
  (unless numarg (setq numarg 1))
  `(lambda ,(loop for i from 1 to numarg collect (symb 'a i))
    ,(funcall (get-macro-character #\`) stream nil)))

これをset-dispatch-macro-characterで登録してやれば、
次のような感じに使えます。
CL-USER> ‘#`(car ,a1)
(LAMBDA (A1) `(CAR ,A1))
CL-USER> (mapcar #`(,a1 (gensym)) ‘(x y z))
((X (GENSYM)) (Y (GENSYM)) (Z (GENSYM)))
ちょっと便利そうだけど、そこまで使うのか？
と少し疑問に思いましたが、今までに自分が書いたソースを見直してみると、
(lambda (x) `(…簡単な式…))
というパターンが結構ありました。これを使うとかなり簡潔に書けそうです。
しかし、バッククォートで囲わないで、生のlambda式を作るリーダマクロの方が
むしろ便利ではないのかと思い、作ってみました。

(defun |#^-reader| (stream sub-char numarg)
  (declare (ignore sub-char))
  (unless numarg (setq numarg 1))
  `(lambda ,(loop for i from 1 to numarg collect (symb '$ i))
    ,(read stream t nil t)))

lambda式のsyntax sugarということで、『#^』(sharp-lambda)と命名しました。
引数がa1, a2, …となるのは個人的に気に入らなかったので、
$1, $2, …という名前に変えました。この方が所見の人もきっと分かりやすいはず。多分。

CL-USER> '#^(car $1)
(LAMBDA ($1) (CAR $1))
CL-USER> (mapcar #^(car $1) '((a b) (c d) (e f)))
(A C E)

$0でその関数自身をさせるようにしてもいいかも知れません。
(lambdaの代わりにlabelsを使えばすぐにできますし。)
#^を使ってlambda式を書き直していくと、ソースがかなり簡潔になりました。
これはかなり便利かも。ただ、他人が読みにくくなるという問題がありますね。
私は、lambdaと入力するのはさほど手間に思っていません。
‘l’をタイプすると自然に指が残りの文字をタイプしてくれますし、
どうしても面倒ならエディタの補完機能を使えば全く手間がかかりません。
私が面倒に思うのはlambdaに伴う括弧です。
lambda自身を囲む括弧に、引数を囲む括弧。
「括弧は友達、怖くないよ」とはいえ、何度も打ってると面倒になってきます。
ちょうど一年前、フムフムヌクヌクアプアア本でcut(srfi-26)をはじめて知ったときは、
かなり気持ち悪く見えたのに、今ではこういったものが必要不可欠にみえてきます。
この悲惨なキーボードを修理もせずに使い続けた結果、
括弧を減らせるマクロを求めるようになってきたのかもしれませんが(笑)

ときどきの雑記帖経由で知った
How to make Lisp go faster than C
という論文が面白いです。
簡単な画像処理をCとCommon Lispで書いて速度を比べるというものですが、
CLの速度の劇的な変化が笑えます。
インタプリタで実行 -> Cの2300倍遅い
コンパイルして実行 -> Cの60倍遅い
型宣言と最適化を付ける -> Cと同等の速度(一部に関してはCより速い)
いくらなんでも最初より速くなりすぎだろｗｗｗｗ
おまけに、最初のソースと最終的なソースの差はほとんど無く、
関数一つあたり、2,3行増える程度です。これは凄い。
あと、CMUCLの型推論がACLより優秀という話も面白かったです。

(defun mult (to from val)
(declare (type (simple-array fixnum (*))
to from))
(declare (type fixnum val))
(let ((size (array-dimension to 0)))
(dotimes (i size)
(setf (aref to i) (* (aref from i) val)))))

配列fromの要素とvalの積はfixnumの範囲を超える可能性があるため、
ACLでは何も指定しない限り^(*1)genericな乗算が行われるけど^(*2)、
CMUCLでは格納先のtoの要素の型がfixnumであるため、
fixnum用の乗算(つまりCPUのnativeな乗算命令)が行われるそうです。
手元のSBCLで試したところ、確かにIMULになってました。
(*1) 同様の命令を吐かせたければ (the fixnum (* (aref from i) val)) とすればいいそうです。
(*2) 2006年の論文なので現在のACLではどうか分かりません。
CやCLやSchemeの様にしっかりと仕様が定められている言語は、
色んなところが処理系を作って互いに競い合うため、
どんどんいいものが生まれていくのがいいですね。

バッククォート怖い…
Let Over Lambdaで紹介されてる例が怖い…

CL-USER> (let ((let '`(let ((let ',let))
,let)))
`(let ((let ',let)) ,let))
(LET ((LET '`(LET ((LET ',LET))
,LET)))
`(LET ((LET ',LET)) ,LET))
CL-USER> (equal + *)
T

確かに処理を追っていけば式とその値が等しいことが分かるけど、
どうやってこんなものを思いついたんだろう…
とりあえずインスパイヤしてみた。

((lambda (lambda)
`((lambda (lambda) ,lambda)
',lambda))
'`((lambda (lambda) ,lambda)
',lambda))

さらに、次の式を評価し、
『(set-macro-character #\λ #'(lambda (stream c) ‘lambda))』
lambdaの代わりにλを使えるようにするとますます気持ち悪い書き方ができる。

((λ (λ)
`((λ (λ) ,λ)
',λ))
'`((λ (λ) ,λ)
',λ))

意味不明すぎてかっこよく見えてきた。