append問題

Mosh のコンパイラをチューニングしている。とても大きなコードをコンパイルすると異常に時間がかかるのだ。（１０秒とか）。
原因は大まかに2つに分けられる。
(1)アルゴリズムの問題
「リストに x という要素があるかどうか？」を線形探索 (memq とか assq）している部分が遅い。
これは hashtable を使えば改善できる。

(2)append問題
長いリストを入力してコンパイルすると、リストの要素を append することが多くなる（という実装になっている）。
これが非常にまずい。
append は末尾以外は新しい cons セルを割り当てるので、気軽に append しまくるとあっという間に遅くなる。
さらに Mosh では quasiquote の unquote-splicing（ ,@ のこと）が append を利用して実装されているので、意識せず長いリストに対して append が走ってしまう。
quasiquote 中だと特にこれに気がつきづらい。
なのでこういうポイントをちまちまと append! に置き換えている。

コンパイラを書いた当初からこのことを知っていれば

• cons セルの割り当てが必要かどうかを意識してコーディングする
• cons セルではない別のデータ構造（例えば vector）を利用する

などの方法をとれたかもしれないと思ったのでここに記録として残しておこう。

append! は意図せず循環リストになったりして問題だったりするのでそれはまた困りもの。
部分的なコンパイル結果を結合して全体のコンパイル結果にするみたいな文脈でのベストプラクティスはどんなのだろうか。

追記

＞CLだと、,@は、append(append)的に、,.は、nconc(append!)的動作をするみたいで、
CommonLisp には ,. があるそうです。
id:g000001さんに教えていただきました。