2019-12-16

formatterで高速化

Common Lisp

【追記】内容が間違っていたので何回か書き直しました。

Common Lispの、formatterマクロの使い方を紹介します。

このマクロは、formatの制御文字を受け取って関数を返却するものです。
とりあえず例をあげます。

下記のformat文を考えます。

(format t "Hello~%")

実行すると次のような出力をします。

Hello

それに対してformatterは、ただ関数を返却するだけです。
とりあえず実行してみます。

(formatter "Hello~%")
  -> #<FUNCTION>

関数が返却されました。
これを実行してみるとどうなるでしょう。

(funcall (formatter "Hello~%") *standard-output*)
Hello

ちなみにfuncallはnilを返却します。

これは一体なにが楽しいのでしょうか？

formatterはformat関数を高速化するためのものです。
大きく、下記の2つのアプローチから高速化を実現します。

構文解析を事前に行う
コンパイルにより高速化を行う

まず「構文解析を事前に行う」とはどういう事でしょうか。

構文解析とは、例えば"Hello~%"という文字を見て、 ①Helloの出力と②terpriの出力に分けることです。
formatの制御文字は文字列によりゴチャゴチャと記載されているため、一文字ずつ調べて行き、~文字が現れたらさあどうしようかと考える処理が必要になります。
制御文字を一つずつ読んで解析するのはそれなりに時間がかかる作業です。
この解析を行うのがformatterマクロの仕事になります。

もう一つの「コンパイルにより高速化を行う」というのはどういう事でしょうか。
それはformatterを用いることでformatの制御文字そのものを機械語の変換してしまおうというものです。
nptはインタープリタなのでその恩恵は得られませんが、 compileを実装したLisp処理系だと、 format制御文字をLisp式にさえ変換できればコンパイルで機械語に変換できるので、かなり高速に実行できるようになります。

formatterによる高速化の作業は、実際にコードが実行する時点より遥かに前で終わらせておくことができます。
例えば次のような文を考えます。

(dotimes (i 5)
  (format t "Hello: ~A~%" i))

難しいことは何もない文ですね。
実行結果を下記に示します。

Hello: 0
Hello: 1
Hello: 2
Hello: 3
Hello: 4

この文の問題点は、"Hello: ~A~%"という文字を 5回も構文解析している点にあります。
「先頭にHello:があってprincの次にterpriがある」という分析は、何も律義に5回実行する必要なんてありません。

それに今回は5回で済んでいますが何万回も出力するということは珍しくないと思います。
そういうときにformatterマクロの出番です。

(setq *format* (formatter "Hello: ~A~%"))
(dotimes (i 5)
  (funcall *format* *standard-output* i))

いいですね。
構文解析が1回で終わっています。
【変更】さらに次のように書き直すことができます。

(dotimes (i 5)
  (format t #.(formatter "Hello: ~A~%") i))

formatterの結果を#.によりread時に実行するように変更しています。
すると全体では下記のような文になります。

(dotimes (i 5)
  (format t #<FUNCTION> i))

なぜformatの引数にformatterを指定しているのか疑問に思うかもしれません。
実はformat関数は、制御文字の引数に関数そのものを受け取ることができます。
ちょうどformatterの返却値を受け取るように考慮されているのです。

実際、やっていることは次の命令と変わりません。

(dotimes (i 5)
  (funcall #<FUNCTION> *standard-output* i))

以上でformat関数をより高速に実行する方法を覚えました。

では実際にやってみましょうということで、速度を測定してみたりしても全然変わらないじゃないかと思う人もいるかもしれません。

実際、全然変わっていない可能性が高いです。
なぜなら、Lisp処理系がeval時に勝手にformatterを実行しているからです。

つまり、

(format t "Hello~%")

と記載していたにも関わらず、処理系はお節介にも

(format t (formatter "Hello~%"))

と変換して実行しているのです。

本当に？
調べる方法があります。

次の例文を考えましょう。

(format t "ERROR ~! ERROR")

見てわかるように、~!なんて命令は無いので不正な文です。
実行してみましょう。

(format t "ERROR ~! ERROR")
  →エラー、~!なんて知らない

そりゃそうです。
しかしlambdaで囲んだらどうなるでしょうか。

(lambda () (format t "ERROR ~! ERROR"))

普通に考えるならば、実行結果は何も問題が無いはずです。
では実際はどうなるでしょうか？
各処理系で実行した結果を示します。

sbcl
- WARNING, ~!がおかしい
- FUNCTION返却
clisp
- FUNCTION返却
ccl
- WARNING, ~!がおかしい
- FUNCTION返却

clispは素直にlambdaで囲んだ分を返却しています。
しかしsbclとcclはWARNINGが出力されているため、 formatの制御文字を構文解析しようと試みたのが分かります。

この事前処理を行おうとしたのはevalの最適化です。
もしformat文の2番目の引数が文字列だったら、先行してformatterを実行しておこうした結果です。

これはありがたい。
何も考えなくてもいいんですから。

しかし最適化が見てくれているとしても、例えば実験データなんかを大量に出力するということが分かり切っている場合は、 format文の制御文字の代わりにformatterを使っておくのはいい考えだと思います。

ちなみにsbclだと、optimizeのspeedを0にすることでこの機能を解除することができました。

(locally
  (declare (optimize (speed 0)))
  (lambda () (format t "ERROR ~! ERROR")))
  -> WARNINGは出ない
  -> FUNCTION返却

書き直しについて

最初は、#.をつけずに下記のように実行することを考えていました。

(dotimes (i 5)
  (format t (formatter "Hello: ~A~%") i))

しかしどの処理系を見てもformatterはlambda式を返却するため、これだと構文解析は1回で終わるのですが、実行するたびに関数が生成されてしまいます。
つまり上記の例では、lambdaにより5個の無名関数が生成されてしまいます。

formatterが無いときに比べれば早くなるので悪くはないのですが、メモリを無駄に使うのも良くはありません。
確実に#.を付けた方がいいでしょう。
しかし#.による仕組みは、見た目は綺麗ですが結構変なことをしていますので、 setqやletなんかでformatterの関数を変数に束縛するのが一番素直で確実なのかもしれません。
つまりはこんな感じ。

(setq *format* (formatter "Hello: ~A~%"))
(dotimes (i 5)
  (format t *format* i))

2019-12-14

clispをFreeBSDにインストールする2

Common Lisp

以前の投稿clispをFreeBSDにインストールする - nptclのブログでは、 portsにてclispのインストールができませんでしたが復活していました。
とても嬉しいです。

それで早速portsでインストールしてみたのですが、やっぱりclangでコンパイルは無理のようで、 gccを入れてからclispを構築しているようです。
gccの分だけ依存関係が多くなっているのではないでしょうか。
どんな感じなのかやってみました。

実験した環境はamd64機器です。

# freebsd-version
12.1-RELEASE

何もインストールされていない状況から、まずはpkgのインストール。

# portsnap fetch extract
# cd /usr/ports/ports-mgmt/pkg
# make install
★pkgが同バージョンだとエラーが出るけど気にしない
# make clean

現時点でのインストール状況を確認。

# pkg info
dialog4ports-0.1.6             Console Interface to configure ports
pkg-1.12.0                     Package manager

clispのインストール

# cd /usr/ports/lang/clisp
# make config-recursive
★考えたくないので全部適当にOK
# make

途中で失敗

===>  llvm80-8.0.1_3 needs Python 3.6 at least, but 2.7 was specified.

Pythonの問題じゃなさそうなので、llvm80を直接インストールする

# cd /usr/ports/devel/llvm80
# make
# make install
# make clean

さらに途中で失敗

===>  meson-0.52.0 needs Python 3.5 at least, but 2.7 was specified.

mesonを直接インストール

# cd /usr/ports/devel/meson
# make
# make install
# make clean

再びclispのインストール

# cd /usr/ports/lang/clisp
# make
# make install
# make clean

完了！
ちなみにうちのPCは遅すぎるので、だらだら作業して、寝てる間もコンパイルしてて丸一日かかりました。

起動してみます。

# clisp
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Welcome to GNU CLISP 2.49.93+ (2018-02-18) <http://clisp.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992-1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2018

Type :h and hit Enter for context help.

[1]> ^D
Bye.
#

では一体どれくらいのパッケージが入ったのか。

# pkg info
autoconf-2.69_3                Automatically configure source code on many Un*x platforms
autoconf-wrapper-20131203      Wrapper script for GNU autoconf
...
...
...
# pkg info | wc
     163    1105   11779
#

163個！
pkg関連の2個とclispの1個以外に、依存関係で160個追加されたことになります。
けっこう入ったなあ。

2019-12-02

pprint-newlineの使い方

Common Lisp

Common Lispで、いまいちよくわからない「条件付き改行」の使い方を見て行きます。

条件付き改行とは、Pretty Printingの機能の一つであり、名前の通り条件よって改行するかどうかが決まるものです。
この機能はpprint-logical-blockマクロの中で、 pprint-newline関数を使うことで実行できます。
簡単に例を挙げるとこんな感じ。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 80)

(pprint-logical-block (nil nil)
  (princ "AAA")
  (pprint-newline :linear))

条件付き改行は4種類ありますが通常の改行であるterpriも特別扱いされますので、下記の5種類の改行について説明してきます。

:linear
:miser
:fill
:mandatory
terpri

さっそく説明に行きたいのですが、その前にPretty Printingの基本である下記の用語の説明をしていきます。

論理ブロック
セクション
マイザ書式

論理ブロック

論理ブロックとは、pprint-logical-blockマクロで囲んだところです。
これは簡単ですね。

例えばこんな感じ。

(pprint-logical-block (nil nil)
  (princ "AAA")
  (princ "BBB"))

セクション

セクションとは、条件付き改行で区切った範囲を表します。
セクションの範囲は条件付き改行に付随するものであり、このセクションで表される範囲によって実際に改行が出力されるかどうかが決定されます。

まずは範囲がどのように決定されるかを見て行きましょう。
次の例を考えます。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 80)

(pprint-logical-block (nil nil)
  (princ "AAA") (pprint-newline :linear)
  (princ "BBB") (pprint-newline :linear)
  (princ "CCC") (pprint-newline :linear)
  (princ "DDD") (pprint-newline :linear))

出力結果は次のようになります。

AAABBBCCCDDD

出力例では、条件付き改行の条件が当てはまらなかったため、一つも改行が出力されませんでした。

ではどの場所で条件付き改行が実施されたかを見たいので、次のように数値で表してみます。

   1  2  3  4
AAABBBCCCDDD

セクションは、自分の改行から見て、前の改行と後ろの改行に挟まれた範囲になります。
数値で範囲を表してみます。

   1  2  3  4
AAABBBCCCDDD
111111
   222222
      333333
         444

セクションの決定には色々と複雑な条件があるのですが、本投稿では全部無視して上記の定義で説明します。

マイザ書式

「マイザ、miser」とは日本語で「けち」を意味します。
例えば、横に長い出力の例を考えましょう。
出力が長くなり、画面右端に近くなった場合は、なんとか狭いスペースで出力したいと考えるかもしれません。
そこで可能な限り横幅をケチって縦長に表示したい、というのがマイザ書式です。

ではどういう時にマイザ書式になるのでしょうか。
それは論理ブロックの開始位置が、画面の右端から *print-miser-width*変数までの間に入っているときです。

画面の横幅は*print-right-margin*であり、マイザ書式の条件が*print-miser-width*です。
例えば、

*print-right-margin*が80
*print-miser-width*が70

のとき、マイザ書式の基準点は80-70=10になります。
論理ブロックの開始位置が10以上であったならばマイザ書式になります。

次の文を考えます。

(setq *print-pretty* t)
(setq *print-miser-width* 70)
(setq *print-right-margin* 80)

(fresh-line)
(princ "AAAAA")
(pprint-logical-block (nil nil)
  ...)

この場合、論理ブロックは左から5文字目で始まっているため、マイザ書式の基準には当てはまりません。
しかし、10を超えればいいので、

(setq *print-pretty* t)
(setq *print-miser-width* 70)
(setq *print-right-margin* 80)

(fresh-line)
(princ "AAAAABBBBBCCCCC")
(pprint-logical-block (nil nil)
  ...)

これだと論理ブロックが15文字から開始になるので、マイザ書式になります。

ではマイザ書式になると何が変わるのでしょうか？
一つは、インデントが強制的に0になり、設定不可能となります。
もう一つは、条件付き改行で改行しやすくなります。

`pprint-newline`関数

条件付き改行はpprint-newline関数によって出力します。
使い方は次の4通り。

(pprint-newline :linear)
(pprint-newline :miser)
(pprint-newline :fill)
(pprint-newline :mandatory)

省略可能な第二引数により、ストリームを指定できます。

(pprint-newline :linear stream)

この関数は論理ブロック内でしか機能しません。
もし普通の場所で呼ばれた場合は何もしません。

引数の簡単な意味を説明します。

:linear
- 一行に入らなかったら全てを改行する。
:miser
- マイザ書式時に、一行に入らなかったら全てを改行する。
:fill
- 一行に入らなかったら改行するが、可能なかぎり改行しない。
:mandatory
- 一行に入らなかったことにして改行する。

こう書けば簡単に見えるのですが、条件というのがまあ複雑で説明に苦労します。
この4種類の改行と通常のterpri改行を合わせて 5通りの挙動について説明していきます。

条件付き改行`:mandatory`

上から順番に説明して行けたらいいのですが、まずは下の方にある:mandatoryから。
この改行は、次の二通りの意味を持ちます。

必ず改行を出力する。
セクションが一行に収まらなかったことにする。

:mandatoryは改行が必ず出力されるので、改行を挿入したいときに使うのかと考えるかもしれませんが、そんなことよりも二つ目の意味が強烈です。

「セクションが一行に収まらなかった」という条件は、他の条件付き改行である:linear, :miser, :fillの判定で使うものです。
:mandatoryは同じ論理ブロックに配置されている他の条件付き改行に全部対して、「セクションが一行に収まらなかった」という報告を出します。
言い換えるなら、他の条件付き改行に対して一斉に改行指示を出す、ということになります。

ただし、他の条件付き改行を絶対に改行させるという訳ではなく、さらに固有の条件を満たしたときだけに出力されます。
例えば:linearは:mandatoryにより絶対に改行しますが、 :miserと:fillは他の条件を満たさないと改行しません。

通常の改行`terpri`

通常の改行であるterpriは、:mandatoryと似ています。
terpriがあった場合は、無条件に改行を出力しますし、同じ論理ブロックの全ての条件付き改行に改行指示を出します。

では:mandatoryとの違いは何でしょうか？
terpri関数はインデントを出力しません。
もし条件付き改行が改行を出力した場合は、次の行の開始からper-line-prefixとインデントの空白が出力されます。
それに対してterpri関数の改行の場合は、per-line-prefixしか出力されません。

条件付き改行`:linear`

条件付き改行の基本となるのが:linearです。
:linearは、次の条件の時に改行が挿入されます。

セクションが一行に収まらなかったとき
同じ論理ブロックに:mandatoryがあるとき

もし条件に当てはまった場合は、その改行が一つだけ挿入されるわけではなく、同じ論理ブロックに含まれる:linearの条件付き改行が一斉に全部改行されます。

つまり同じ論理ブロック中にある:linearは、全てが改行されるか、あるいは全て何もしないかのどちらかになります。

次の例を考えます。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 80)

(pprint-logical-block (nil nil)
  (princ "AAAA") (pprint-newline :linear)
  (princ "BBBB") (pprint-newline :linear)
  (princ "CCCC") (pprint-newline :linear))

この例では全体の出力が80文字以内に余裕で収まるため、全ての条件付き改行は無視されて次のような出力となります。

AAAABBBBCCCC

では次の場合はどうでしょうか。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 11)

(pprint-logical-block (nil nil)
  (princ "AAAA") (pprint-newline :linear)
  (princ "BBBB") (pprint-newline :linear)
  (princ "CCCC") (pprint-newline :linear))

出力幅は11文字に設定しています。
1番目の条件付き改行のセクションはAAAABBBBで8文字です。
2番目の条件付き改行のセクションはBBBBCCCCの8文字であり、開始位置4文字目からだと4+8=12で11文字に収まらないため、次のように出力されると考えるかもしれません。

AAAABBBB
CCCC

しかしこれは間違い。
:linearは今回の判定では無関係なものも全て一斉に改行されるため、実際には次のように出力されます。

AAAA
BBBB
CCCC

改行の条件にはさらに:madatoryがあり、セクションが一行に十分収まる場合でも、同じ論理ブロック内に:madatoryがある場合は全部改行されます。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 80)

(pprint-logical-block (nil nil)
  (princ "AAAA") (pprint-newline :linear)
  (princ "BBBB") (pprint-newline :linear)
  (princ "CCCC") (pprint-newline :mandatory))

実行例は下記の通り。

AAAA
BBBB
CCCC

条件付き改行`:miser`

この条件付き改行は:linearと同じなのですが、マイザ書式中でないと改行を出力しません。

これから例文も含めて色々と書いていくわけですが、結局のところ:miserは:linearとたった一つを除いて全て同じだという事を説明しています。
たった一つの違いとは「マイザ書式中じゃなきゃ改行を出力しない」です。

:linearと同じように動作するので、 :linearが一斉に改行されたらマイザ書式中であれば:miserも改行します。
逆に:miserが一行に収まらなかった場合は、 :linearは一斉に改行しますし、マイザ書式中であれば:miserも改行します。
さらに言うと、:mandatoryがあるだけで :linearとマイザ書式中の:miserは全部改行します。

分かりづらいのですが、マイザ書式中でなくても、一行に収まるか収まらないかの判定は:miserにて行われます。
マイザ書式ではない場合に行われないのは、改行の出力だけです。

下記に例を示します。

(setq *print-pretty* t)
(setq *print-miser-width* 30)
(setq *print-right-margin* 20)

(pprint-logical-block (nil nil)
  (princ "AAAA") (pprint-newline :miser)
  (princ "BBBB") (pprint-newline :miser)
  (princ "CCCC") (pprint-newline :miser)
  (princ "DDDD") (pprint-newline :linear)
  (princ "EEEE") (pprint-newline :linear)
  (princ "FFFF") (pprint-newline :linear))

実行結果は下記の通り。

AAAA
BBBB
CCCC
DDDD
EEEE
FFFF

例では:linear周辺で一行に収まらないため、少なくとも:linearは全部改行されることは分かると思いますが、マイザ書式中のため:miserも同時に全て改行されています。

もしマイザ書式ではなかった場合はどうなるでしょうか。
次に例を示します。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 20)

(pprint-logical-block (nil nil)
  (princ "AAAA") (pprint-newline :miser)
  (princ "BBBB") (pprint-newline :miser)
  (princ "CCCC") (pprint-newline :miser)
  (princ "DDDD") (pprint-newline :linear)
  (princ "EEEE") (pprint-newline :linear)
  (princ "FFFF") (pprint-newline :linear))

実行結果は次の通り。

AAAABBBBCCCCDDDD
EEEE
FFFF

:linearだけが全て改行され、:miserは改行が出力されませんでした。

条件付き改行`:fill`

この条件付き改行は、可能な限り横に列挙することを目的とします。
もし一行に収まらなかった場合、:linearでは一斉に改行されましたが、 :fillではセクションが超過したもののみ改行を行い、他の:fillは改行されません。

もし:fillのセクションが一行に収まらない場合は、 :linearと:miserの場合と同様に、同じ論理ブロックに配置している:linearと:miserも改行条件を満たすことになります。

つまり、:fillが一行に収まらない時は:linearは全て改行し、マイザ書式中であれば:miserも全て改行します。
一方、:linearなどでセクションの横幅が超過した場合は、他の条件付き改行も一斉に改行するのですが、 :fillに関しては無関係であり影響を受けません。

次の例を考えます。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 11)

(pprint-logical-block (nil nil)
  (princ "AAAA") (pprint-newline :fill)
  (princ "BBBB") (pprint-newline :fill)
  (princ "CCCC") (pprint-newline :fill))

実行結果は次の通り。

AAAABBBB
CCCC

この例文は、:linearの例を全て:fillに変えたものです。
:linearの時は全てが改行されましたが、 :fillの場合はなるべく一行に収めようとして、はみ出る場合にのみ改行をしているのがわかります。

:fillにはさらに言っておかなければいけないことが色々とあります。

:mandatoryだとどうなるでしょうか？
:mandatoryは、セクションが一行に収まらなかったことにする意味があると書きました。
しかし:fillの場合には当てはまらず、もし:mandatoryが存在しても:fillの挙動は変わりません。

実行例を見て行きます。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 11)

(pprint-logical-block (nil nil)
  (princ "AAAA") (pprint-newline :fill)
  (princ "BBBB") (pprint-newline :fill)
  (princ "CCCC") (pprint-newline :mandatory))

実行結果は次の通り。

AAAABBBB
CCCC

:mandatoryがあっても:fillの挙動が変化していないのがわかります。

ただし例外があるのです。
:fillは、マイザ書式中だと:linearと全く同じ意味になります。
よって:fillのセクションが一行に収まらなかったら他の条件付き改行も巻き込んで一斉に改行するし、 :linearと:miserと:mandatoryが改行した場合はつられてマイザ書式中の:fillも改行します。

次の例を示します。

(setq *print-pretty* t)
(setq *print-miser-width* 100)
(setq *print-right-margin* 11)

(pprint-logical-block (nil nil)
  (princ "AAAA") (pprint-newline :fill)
  (princ "BBBB") (pprint-newline :fill)
  (princ "CCCC") (pprint-newline :mandatory))

実行結果は次の通り。

AAAA
BBBB
CCCC

マイザ書式なので:fillが:miserと同じ動きになっているのがわかります。
さらに次の例を示します。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 15)
(pprint-logical-block (nil nil)
  (princ "AAAA") (pprint-newline :linear)
  (princ "BBBB") (pprint-newline :fill)
  (princ "CCCC") (pprint-newline :fill)
  (princ "DDDD") (pprint-newline :fill)
  (princ "EEEE") (pprint-newline :fill))

実行結果は次の通り。

AAAA
BBBBCCCCDDDD
EEEE

この例では、:fillのセクションが一行に収まらなかったため、 :linearにも影響が出て改行されています。
:fillは一行に収めようとする挙動自体は変わらないのですが、論理ブロック全体に改行の条件が加わるため:linearにも影響が出るのです。

改行の連鎖

次の出力はどうなるかわかるでしょうか。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 100)

(pprint-logical-block (nil nil)
  (princ "AAA") (pprint-newline :linear)
  (princ "BBB") (pprint-newline :linear)
  (pprint-logical-block (nil nil)
    (princ "CCC") (pprint-newline :linear)
    (princ "DDD") (pprint-newline :linear)
    (pprint-logical-block (nil nil)
      (princ "EEE") (pprint-newline :linear)
      (princ "FFF") (pprint-newline :linear)
      (princ "GGG") (pprint-newline :mandatory))))

論理ブロックが3つネストしており、一番最後に:mandatoryで強制改行をしています。
最後のブロックだけが強制的に改行されるので、次のようになると思うかもしれません。

AAABBBCCCDDDEEE
FFF
GGG

しかしそうではなく、全部改行されます。
実行結果は下記の通り。

AAA
BBB
CCC
DDD
EEE
FFF
GGG

なぜこうなるのでしょうか？
論理ブロックの:linearの考え方を思い出しましょう。
もし:linearのセクションが一行に収まらなかったら、同じ論理ブロックの全ての:linearが一斉に改行されました。
そのあとに:miserも:fillも改行されることがあると言いました。
これは論理ブロック内にある出力関数が、一つでも改行した場合にはすべてを一斉に改行させるという機能によるものです。

条件付き改行が一つでも改行したら他の条件付き改行も同時に改行しますが、改行の出力は必ずしも「条件付き改行」じゃなくても構いません。
terpriであったり、formatでもいいわけです。
もっと言うと、並列に配置してあるpprint-logical-blockでもいいわけです。

では:linearと同じ論理ブロックに配置されている別の論理ブロックが改行した場合はどうなるでしょうか？
別の論理ブロックの改行が契機となって:linearが一斉に改行します。
じゃあ別の論理ブロックに配置されている、さらにネストされた別の論理ブロックが改行したら？

答えは例文で示した通り、ネストされた論理ブロックで出力された改行が元の論理ブロックへと次々と伝搬していきます。
結果、条件付き改行は全てが改行されたわけです。

では、今回の例のように連鎖のきっかけとなる改行は何でしょうか？
答えはterpriか:mandatoryのどちらかだけとなります。

不思議に思うかもしれませんが、例えば、ネストされた:linearでは改行の連鎖のきっかけにはなりません。

例を示します。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 20)

(pprint-logical-block (nil nil)
  (princ "AAA") (pprint-newline :linear)
  (princ "BBB") (pprint-newline :linear)
  (pprint-logical-block (nil nil)
    (princ "CCC") (pprint-newline :linear)
    (princ "DDD") (pprint-newline :linear)
    (pprint-logical-block (nil nil)
      (princ "EEE") (pprint-newline :linear)
      (princ "FFF") (pprint-newline :linear)
      (princ "GGG") (pprint-newline :linear))))

横幅20文字に対して

AAABBBCCCDDDEEEFFFGGG

の横幅21文字を出力しようとしています。
入りきれないのでどこかで改行するわけですが、どこで改行するかわかるでしょうか。
出力結果は下記の通り。

AAA
BBB
CCCDDDEEEFFFGGG

見てわかる通り、ネストされていない一番最初の論理ブロックで改行してしまうため、連鎖して改行するということがありえないのです。

繰り返しになりますが、以上の結果から覚えておかなければいけないことは、 terpriと:mandatoryはネストされた論理ブロックを巻き込んで一斉に改行させる、ということです。

規約を見ただけでは、この動作を作り込むのは困難だと思います。

`format`による条件付き改行

最後に条件付き改行のformatの話をします。
formatの書式では、条件付き改行~_が用意されています。

こんな感じ。

:linear      ~_
:miser      ~@_
:fill       ~:_
:mandatory  ~:@_

さらに言うと、pprint-logical-blockも用意されています。

~< ... ~:>

こちらは引数を1つ取ります。
pprint-logical-blockの~<は非常に多機能で色んなことができるのですが説明しません。

次の例文を考えます。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 20)

(pprint-logical-block (nil nil)
  (princ "AAAA") (pprint-newline :miser)
  (princ "BBBB") (pprint-newline :miser)
  (princ "CCCC") (pprint-newline :miser)
  (princ "DDDD") (pprint-newline :linear)
  (princ "EEEE") (pprint-newline :linear)
  (princ "FFFF") (pprint-newline :linear))

format文で書き換えると次の通り。

(setq *print-pretty* t)
(setq *print-miser-width* nil)
(setq *print-right-margin* 20)

(format t "~<AAAA~@_BBBB~@_CCCC~@_DDDD~_EEEE~_FFFF~_~:>" '(nil nil))

出力結果は下記の通り。

AAAABBBBCCCCDDDD
EEEE
FFFF

format文は相変わらず何書いてあるんだが全然わからん。

このアルゴリズムについて

Pretty Printingは、次の論文がもとになっているとのこと。

22.2.3 Notes about the Pretty Printer's Background
http://www.lispworks.com/documentation/HyperSpec/Body/22_bc.htm
XP. A Common Lisp Pretty Printing System
https://dspace.mit.edu/handle/1721.1/6503

見てはいませんが、cltl2にそのまま書き写されたような感じでした。
次のような文があったのを何となく覚えています。

27.1. Introduction
https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node254.html
Implementation note: ...XP uses a highly efficient linear-time algorithm.

highly efficient？
確かにそうかも。
作ってみてわかったのですが、確かに線形時間で終わりそうなものです。
もっとバックトラックとかふんだんに使って試行錯誤する訳の分からないものかと思ってたんですが、この通り作って行けば、素直に出力できると思います。

初めは何書いてるのかさっぱりわからなくて、一体どうすりゃいいんだと何日も悩んでたんですけど、たぶん何とかなりそうです。
ただ、条件付き改行の挙動をちゃんと理解するのはとても難しかったです。
めちゃ苦労しました。
だから本投稿にて文章で残します。

2019-11-26

amd64ユーザーランド（とりあえず実行）

amd64の機械語を勉強していきます。

本投稿はnptに最小限のamd64 コンパイラを実装できるか検討したときのメモです。
まあ結局nptでamd64 コンパイラは実装しないんですけど。

ユーザーランドとは、つまり一般ユーザーが作るプログラムのことです。
OSを作るわけじゃないので、カーネルモードは対象外になります。

条件は次の通り。

CPUはamd64形式
64bitモードのみ
ユーザーランドのみ

まず覚えなければいけないのは、機械語を実行して確認する方法です。
自分にとってはC言語から実行する方法が簡単だったので、その方法を示します。
方法はOS依存なので、下記の環境を対象に考えます。

FreeBSD, Linux （どちらも同じ方法で実現できる）
Windows

機械語とは、結局は単なるバイナリデータの集合です。
C言語で言うならば、unsigned charの配列でも作って、
それを強制的に関数ポインタとみなして実行すればいいことになります。

例えばこんな感じ。

unsigned char data[] = {
    /* exit(9)を呼び出す例文です */
    0xB8, 0x01, 0x00, 0x00, 0x00,       /* mov eax <- 1 */
    0xBF, 0x09, 0x00, 0x00, 0x00,       /* mov edi <- 9 */
    0xCD, 0x80                          /* int 0x80 */
};

int main()
{
    void (*call)(void);

    call = (void (*)(void))data;
    call();  /* ★たぶんうまく行かない */

    return 0;
}

注釈に記載した通り、たぶんうまく行きません。
FreeBSDで実行した結果が下記の通り。

$ cc main.c
$ ./a.out
Segmentation fault (core dumped)

大昔のOSだったらうまく行ったことでしょう。
しかしセキュリティが大切だともてはやされた結果、メモリに対して実行可能な許可が無いとOSレベルでエラーになってしまいます。

実行許可があるメモリを用意する方法は大きく2つあり、すでに確保されたメモリに実行許可を与える方法と新しく確保する方法です。
どちらの方法でも、mmap関数か、VirtualAlloc関数を使います。

今回は新規にメモリを確保することにします。
malloc/freeのかわりに、mmap/munmapを使う方法を示します。

ではC言語にて下記の命令を実行することを考えます。

ptr = malloc(size);

これを実行可能なメモリ領域の確保に変えると次のようになります。

FreeBSD, Linux

ptr = mmap(0, size, PROT_READ|PROT_WRITE|PROT_EXEC, MAP_ANON|MAP_SHARED, -1, 0);

Windows

ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_EXECUTE_READWRITE);

ptrが指しているメモリ空間は、関数と同様に実行可能な領域となります。
それでは、簡単な例として下記のコードを自力で機械語に翻訳してみます。

int testcode(int a, int b)
{
    return a + b;
}

関数testcodeは、単純に二つの引数を足すだけです。
面倒なことにOSによって機械語の翻訳結果が異なります。

FreeBSD, Linux

unsigned char code[] = {
    0x89, 0xF8,     /* mov eax <- edi */
    0x01, 0xF0,     /* add eax <- esi */
    0xC3            /* ret */
};

Windows

unsigned char code[] = {
    0x89, 0xC8,     /* mov eax <- ecx */
    0x01, 0xD0,     /* add eax <- edx */
    0xC3            /* ret */
};

どうして内容が異なるのでしょうか？
それは「呼出規約」というものが異なるからです。

呼出規約とは、関数の呼び出しと返却をどのようにして行うかという、関数間のインターフェイスのことです。
例えば、第一引数はスタックに積むのか、あるいはレジスタに格納するのか、格納するならどういう順番で何を使うかなどを規定したものです。

呼出規約は、CPU、OS、言語の種類ごとに異なります。
例えばCPUのSPARCとIntelでは違っていますし、同じIntelでもi386とx86-64(amd64)で違います。
FreeBSDとLinuxは同じ場合も違う場合もあります。
FreeBSDとWindowsはどうも絶対に異なっているようです。

つまりコンパイラを作るためには、次の2つを勉強する必要があるという事です。

amd64の機械語
amd64の呼出規約

一気に説明することはできないので次の投稿になるとは思うのですが、とりあえずは例で挙げた機械語のコードを実行するためのソースを示します。

FreeBSD, Linux amd64

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

unsigned char code[] = {
    0x89, 0xF8,     /* mov eax <- edi */
    0x01, 0xF0,     /* add eax <- esi */
    0xC3            /* ret */
};

void execute(void *ptr)
{
    int (*proc)(int, int);
    int result;

    memcpy(ptr, code, 5);
    proc = (int (*)(int, int))ptr;
    result = proc(30, 10);
    printf("%d\n", result);
}

int main()
{
    void *ptr;
    size_t size;

    size = 1024;
    ptr = mmap(0, size, PROT_READ|PROT_WRITE|PROT_EXEC, MAP_ANON|MAP_SHARED, -1, 0);
    if (ptr == MAP_FAILED) {
        perror("mmap");
        return 1;
    }

    execute(ptr);

    if (munmap(ptr, size)) {
        perror("munmap");
        return 1;
    }

    return 0;
}

Windows amd64

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned char code[] = {
    0x89, 0xC8,     /* mov eax <- ecx */
    0x01, 0xD0,     /* add eax <- edx */
    0xC3            /* ret */
};

void execute(void *ptr)
{
    int (*proc)(int, int);
    int result;

    memcpy(ptr, code, 5);
    proc = (int (*)(int, int))ptr;
    result = proc(30, 10);
    printf("%d\n", result);
}

int main()
{
    void *ptr;
    size_t size;

    size = 1024;
    ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_EXECUTE_READWRITE);
    if (ptr == NULL) {
        fprintf(stderr, "VirutalAlloc error\n");
        return 1;
    }

    execute(ptr);

    if (! VirtualFree(ptr, 0, MEM_RELEASE)) {
        fprintf(stderr, "VirutalFree error\n");
        return 1;
    }

    return 0;
}

実行結果は、どちらも40が出力されます。
これで思い通りのバイトコードを実行できるようになりました。

次からはamd64の機械語を紹介できればいいなと思います。

2019-09-07

クラスをsubtypepしたときの問題点

Common Lisp

クラスはsubtypepで継承関係を調査できます。
例えば次の通り。

(subtypep 'standard-class 'class)
  -> t; t

つまり、standard-classはclassを継承しているということです。
次の例はどうでしょうか。

(defclass aaa () ())
(defclass bbb (aaa) ())
(subtypep 'bbb 'aaa)
  -> t; t

(subtypep 'aaa 'bbb)
  -> nil; t

何ら問題なく理解できると思います。

問題は否定したときです。
以前subtypep実装の基本 - nptclのブログでは、右側が否定の場合は、比較する2つの型が完全に排他かどうかをチェックする必要があると書きました。

例として挙げた、

(defclass aaa () ())
(defclass bbb (aaa) ())

は、継承関係にあるため完全に排他とは言えません。
つまり、右を否定した場合は必ずnil; tが返却されるはずです。
では実際にはどうなるでしょうか。

(subtypep 'aaa '(not bbb))
  -> nil; t       ;; sbcl, ccl
  -> nil; nil     ;; clisp

(subtypep 'bbb '(not aaa))
  -> nil; t       ;; sbcl, ccl
  -> nil; nil     ;; clisp

さて、これはどういうことなのでしょうか。
sbclとcclは予想通りでしたが、clispは第二返却値がnilのため、つまりは分からないと言って判定を放棄したことになります。

排他的な場合はどうなるでしょうか。
テスト用に次のクラスを用意します。

(defclass ccc () ())
(defclass ddd () ())

両者は一見すると排他的に見えます。
subtypepの結果を次に記載します。

(subtypep 'ccc '(not ddd))
  -> nil; nil     ;; sbcl, clisp
  -> t; t         ;; ccl

大きく分かれました。
これから上記の結果について私の見解を書いて行くわけですが、実の所これらの結果はかなりわかりづらいですし、ちゃんとした説明はできないかもしれません。

まずは次の結果から。

(subtypep 'ccc '(not ddd))
  -> t; t         ;; ccl

クラスcccとクラスdddは継承関係ではないため、互いに排他として見るならば、返却値tは一見して正しいように見えます。
しかし実はクラスcccもクラスdddもどちらも同じtというクラスを含んでいるため、互いに排他ではないのです。

(class-precedence-list (find-class 'ccc))
  -> (#<STANDARD-CLASS CCC> #<STANDARD-CLASS STANDARD-OBJECT> #<BUILT-IN-CLASS T>)

(class-precedence-list (find-class 'ddd))
  -> (#<STANDARD-CLASS DDD> #<STANDARD-CLASS STANDARD-OBJECT> #<BUILT-IN-CLASS T>)

完全に排他ではないということならば、subtypepの右がnotの場合は tではなくnilが正解ということになります。
しかしsbclとclispでは、nil; tではなくnil; nilになっています。
どういうことなのでしょうか？

この返却は規約に矛盾が生じているため、判定不可能とするのが正しいという妥協によるものだと思います。
もしnil; tを許容してしまうならば、 built-in-classはどうなんだと突っ込まれてしまいます。

例えば下記の式、

(subtypep 'integer '(not cons))
  -> t; t

は、integerとconsは互いに排他のため、当然tが返却されます。
しかしどちらの型もCLOSオブジェクトの写像を持っており、両方ともtクラスを含んでいます。

(class-precedence-list (find-class 'integer))
  -> (#<BUILT-IN-CLASS INTEGER> #<BUILT-IN-CLASS RATIONAL> #<BUILT-IN-CLASS REAL>
      #<BUILT-IN-CLASS NUMBER> #<BUILT-IN-CLASS T>)

(class-precedence-list (find-class 'cons))
  -> (#<BUILT-IN-CLASS CONS> #<BUILT-IN-CLASS LIST> #<BUILT-IN-CLASS SEQUENCE>
      #<BUILT-IN-CLASS T>)

型として判定した場合はtであり、クラスとして判定した場合はnilになります。

もうどうしようもないですよね。
矛盾が生じた以上は未定義です。
sbclとclispはnil; nilとして、申し訳ないけどわからないと返却し、 cclはclassの場合だけでもtクラスを無視しようという結果になります。

さて、では次の場合はどうなるでしょうか。

(subtypep 'bbb '(not aaa))
  -> nil; t       ;; sbcl, ccl
  -> nil; nil     ;; clisp

sbclとcclはnil; tであっています。
しかしclispはnil; nilとしています。
私の個人的な意見としてはsbclとcclが正しいとは思います。
しかしすでにclassの判定に妥協が生じている以上は、 nil; nilとしてしまってもいいのではないでしょうか。

以上です。
結論を書くならば、 subtypepでclassをチェックするときには、notを使うべきではない。となります。

2019-07-23

FreeBSD 12にOpenSMTPDを入れたかった

昔はこうやって入れていました。

# portsnap fetch update
# cd /usr/ports/mail/opensmtpd
# make
===>  opensmtpd-5.9.2p1_6,1 is marked as broken: Incompatible with Openssl
1.1.x yet.
*** Error code 1

Stop.
make: stopped in /usr/ports/mail/opensmtpd
#

何か月たってもエラー。
あきらめようか。

【追記】FreeBSD 12.1-RELEASEでやったらうまく行きました。
やったー！！

# freebsd-version
12.1-RELEASE
# portsnap fetch update
# cd /usr/ports/mail/opensmtpd
# make install
# rehash
# smtpd -h
version: OpenSMTPD 6.6.0-portable
usage: smtpd [-dFhnv] [-D macro=value] [-f file] [-P system] [-T trace]
#

ソースから手動で入れる

ここでの手順はパッケージ管理されないので色々問題ありそう。
ずっとOpenSMTPDを使ってきたけど、結局sendmailに戻すかも。

それではOpenSMTPDをソースから入れる手順を示します。
方針は下記の通り。

必要なライブラリも全部ソースから入れる
/opt/smtpdにインストール
起動停止スクリプトは/usr/local/etc上に配置

管理ユーザーの作成

# pw useradd -n _smtpd -u 257 -c OpenSMTPD -w no -m -d /opt/smtpd -s sh
# pw useradd -n _smtpq -u 258 -c OpenSMTPD -w no -m -d /var/empty -s /usr/sbin/nologin

切り替え

# su - _smtpd
$

ディレクトリ作成

# mkdir src
$ mkdir distfiles

ダウンロード

$ cd distfiles
$ fetch --no-verify-peer https://ftp.openbsd.org/pub/OpenBSD/LibreSSL/libressl-2.9.2.tar.gz
$ fetch --no-verify-peer https://github.com/libevent/libevent/releases/download/release-2.1.10-stable/libevent-2.1.10-stable.tar.gz
$ fetch --no-verify-peer https://www.opensmtpd.org/archives/libasr-1.0.2.tar.gz
$ fetch --no-verify-peer https://www.opensmtpd.org/archives/opensmtpd-6.4.1p2.tar.gz

LibreSSL構築

$ cd
$ cd src
$ tar zxf ../distfiles/libressl-2.9.2.tar.gz
$ cd libressl-2.9.2/
$ ./configure --prefix=$HOME
$ make
$ make install
$ make clean

環境変数LD_LIBRARY_PATHを設定する。

$ cd
$ vi .profile

下記の3行を追記

# OpenSMPTD
LD_LIBRARY_PATH="${HOME}/lib:${LD_LIBRARY_PATH}"
export LD_LIBRARY_PATH

一度ログアウトする

$ exit

切り替え

# su - _smtpd

環境変数の確認

$ env | grep LD_LIBRARY_PATH
LD_LIBRARY_PATH=/opt/smtpd/lib:

libevent構築

$ cd
$ cd src
$ tar zxf ../distfiles/libevent-2.1.10-stable.tar.gz
$ cd libevent-2.1.10-stable/
$ ./configure --prefix=$HOME
$ make
$ make install
$ make clean

libasr構築

$ cd
$ cd src
$ tar zxf ../distfiles/libasr-1.0.2.tar.gz
$ cd libasr-1.0.2/
$ ./configure --prefix=$HOME
$ make
$ make install
$ make clean

OpenSMPTD構築

$ cd
$ cd src
$ tar zxf ../distfiles/opensmtpd-6.4.1p2.tar.gz
$ cd opensmtpd-6.4.1p2/
$ ./configure --prefix=$HOME \
--with-libasr=$HOME \
--with-libevent=$HOME \
--with-libssl=$HOME
$ make
$ make install
$ make clean

環境設定

rootにて作業を行う

ディレクトリの移動

# cd /usr/local/etc/rc.d/

もし存在しない場合は作る

# mkdir -p /usr/local/etc/rc.d/
# mkdir -p /usr/local/etc/mail/
# cd /usr/local/etc/rc.d/

サービス用スクリプトを作成する。

# vi optsmtpd

内容は下記の通り。

#!/bin/sh
# PROVIDE: optsmtpd mail
# REQUIRE: LOGIN
# KEYWORD: shutdown
. /etc/rc.subr
basepath="/opt/smtpd"
LD_LIBRARY_PATH="${basepath}/lib:${LD_LIBRARY_PATH}"
export LD_LIBRARY_PATH

name="optsmtpd"
rcvar=optsmtpd_enable

start_precmd="optsmtpd_precmd"
restart_precmd="optsmtpd_checkconfig"
configtest_cmd="optsmtpd_checkconfig"
extra_commands="configtest"

load_rc_config $name

: ${optsmtpd_enable:="NO"}
: ${optsmtpd_config:="/usr/local/etc/mail/smtpd.conf"}
: ${optsmtpd_procname:="${basepath}/sbin/smtpd"}
: ${optsmtpd_flags:=""}

command=${optsmtpd_procname}
command_args="-f ${optsmtpd_config} ${command_args}"
required_files="${optsmtpd_config}"

procname=${optsmtpd_procname}
pidfile="/var/run/smtpd.pid"

optsmtpd_checkconfig()
{
    echo "Performing sanity check on optsmtpd configuration:"
    eval ${command} ${command_args} ${optsmtpd_flags} -n
}

optsmtpd_precmd()
{
    optsmtpd_checkconfig
}

run_rc_command "$1"

権限の設定を行う

# chmod 755 optsmtpd
# service -l | grep optsmtpd
optsmtpd

自動起動の設定を行う。

# cd
# vi /etc/rc.conf

下記の行を追加する。

sendmail_enable="NO"
sendmail_submit_enable="NO"
sendmail_outbound_enable="NO"
sendmail_msp_queue_enable="NO"
optsmtpd_enable="YES"

sendmailの強制停止

# service sendmail forcestop
Stopping sendmail.
Waiting for PIDS: 1983.
Stopping sendmail_msp_queue.
Waiting for PIDS: 1986.

設定ファイルの配置

# vi /usr/local/etc/mail/smtpd.conf

内容は下記の通り。

table aliases file:/etc/mail/aliases
listen on 127.0.0.1
action "local" mbox alias <aliases>
match for local action "local"

プロセスを立ち上げる

# service optsmtpd start
Performing sanity check on optsmtpd configuration:
configuration OK
Starting optsmtpd.

起動確認

# ps -ax | grep smtpd
70778  -  SsJ  0:00.02 /opt/smtpd/sbin/smtpd -f /usr/local/etc/mail/smtpd.conf
70779  -  IJ   0:00.02 smtpd: klondike (smtpd)
70780  -  IJ   0:00.02 smtpd: control (smtpd)
70781  -  IJ   0:00.03 smtpd: lookup (smtpd)
70782  -  IJ   0:00.03 smtpd: pony express (smtpd)
70783  -  IJ   0:00.03 smtpd: queue (smtpd)
70784  -  IJ   0:00.02 smtpd: scheduler (smtpd)
70790  0  S+J  0:00.00 grep smtpd

メール送信テスト

# echo hello | mail root
（少し待つ）
# mail
Mail version 8.1 6/6/93.  Type ? for help.
"/var/mail/root": 1 message 1 new
>N  1 root@empty.lan        Tue Jul 23 05:08  18/575
& 1
Message 1:
From root@empty.lan Tue Jul 23 05:08:39 2019
Delivered-To: root@empty.lan
Date: Tue, 23 Jul 2019 05:08:39 GMT
From: Charlie Root <root@empty.lan>
To: root@empty.lan

hello

& q
Saved 1 message in mbox
#

停止確認

# cd
# service optsmtpd stop
Stopping optsmtpd.
Waiting for PIDS: 70778.
# ps -ax | grep smtpd
70810  0  S+J  0:00.00 grep smtpd
#

最後に

どこまでうまく動くかは不明。
あと、6.4.0からsmtpd.confの書き方が変わったんですって。

2019-07-21

Nptで把握している問題点

npt

いま現在問題と思っていることを列挙します。
書いておかないと本人が忘れるので。
これは、問題と確定しているわけではなく、問題があるかどうか調査することから必要があるものです。

標準入出力のリダイレクトが非常に遅いのはなぜか調べる。例えばこんな感じ$ npt --script file.lisp > zzz。標準I/Oはキャッシュオフにしているせいだと思うがどうすればいいか考える。
defstructで:type vectorにしたacessor関数が、 LISPTYPE_VECTORのみ対応しているが、LISPTYPE_ARRAYに対応させる必要がある。
defstructで:typeがlist, vectorのとき、slot-makunboundをすると、オブジェクトの内容がunboundになってしまうのでそれをやめる。
defstructで:type vectorがspecialized arrayなら生成するオブジェクトも specializedにするべきなのでは？
deftypeで標準のtypeを設定したらエラーになるか調べる。例えば(deftype integer ...)でエラーになるべきでは？
deftypeで指定したsymbolがreadonlyの場合はエラーになるか調べる。例えば(deftype :hello ...)はエラーになるべきでは？
その場合carとかいう名前のdeftypeはどうなる？
Common Lispパッケージのsymbolをreadonlyにする必要がある。もうなっているかも？
type-functionの第三引数のテストケースを追加。型(function 第1 第2 第3)の第三引数は内部用で表に出てこない。
typepでsatisfiesの実行割り込みreturn 1に対応させる。つまりsatisfiesの関数内でreturn-fromやthrowが発生したときを考慮する。
subtypepでsatisfiesの実行割り込みreturn 1に対応させる。つまりsatisfiesの関数内でreturn-fromやthrowが発生したときを考慮する。でもこれは無いかも。
fmte, fmtwを実行割り込みreturn 1に対応させる。つまり関数内でreturn-fromやthrowが発生したときを考慮する。
RefLispDecl, GetLispDeclを使用しているコードでNOTが考慮されているか調べる。これなんだったか忘れたので調べなおす。
strarrayのcharactertypeはおかしいかもしれない。 strarray-base-p関数を使うこと。これなんだったか忘れたので調べなおす。
subtypepの引数にclosを指定すると、notで正しく出力されない。これは規格自体に問題がある可能性があるため、他の処理系と合わせる。現在、TODOと書かれているはず。
:allow-other-keysが対応していない。
全体的に見直す必要がある、とても作業量が多くなるかも。引数が(&rest args &key)の場合、&allow-other-keysが自動的に付与されるべきなのか？ &key &allow-other-keysのとき、key-valueのペアのチェックが行われていない？一般の関数でも:allow-other-keys tが使用できる(★&ではなく:)。現時点だと:allow-other-keysがtならたぶんeval時点でwarningが起こるはず。
fmakunboundで型も削除
functionオブジェクトのnameにあるcallnameがsetfになっていない。
defunで型を登録する
defunの型をもとにeval情報に型を登録
function-lambda-expressionのためにlambda-expressionをfunctionに登録する。
fasl再作成
fixnum-localオブジェクトをcacheできるか考える
code_macro_functionにnameを渡して処理する。戻り値とdocumentationがどうなるかを調査する。
macro-lambdaのallow-other-keys判定は必要だが、ordinary-lambdaには不要。ただし、:allow-other-keysの実装によっていろいろ変わるかも。
macroの型チェックをどうするか調査。現状、他の処理系では型チェックしているが、nptでは一切していない。
common-arraysでtypeチェックしているにもかかわらず、手動で型のチェックをしている所が結構あるので削除する。 (integer 0 *)をSIZE_MAXにすることでgetindex_integerを簡略化できる。
型indexやSIZE_MAXはfixnumにしてしまった方が早くてよいのでは？
adjust-arrayの試験を追加する。
普段はGetArrayXXではなくgetarrayを使うように変更、type-arrayなど。
function型チェックの都合上type-or, and, notのasteriskを許容したが、 typepコマンドでちゃんとエラーになることを確認する
start-endのendは標準でUnboundではなくNilが正解。
sxhashはもう少しちゃんとできないか考える。
openは8bit以外のbinary入出力をサポート、(unsigned-byte 16)など。
:direction :ioでread->writeが切り替わるときにunreadを破棄する
:direction :ioをもう少し何とかする。
ANSI-Cモードのopenをもう少し何とかする。
全てのstreamにてcloseされた状態を考慮していないので見直す。
Uniocdeのencodeをもう少し何とかする。例えばBOMの扱いなど、Lispのstrjisモジュール開発でわかったことを反映する。
浮動小数点の出力がおかしいmost-positive-short-float。これなんだったか覚えてないので調べる。
closの情報取得関数にデバッグの型チェックを入れる
コードにTODOと埋め込まれている部分が結構あるので片づける。
*LOAD-TRUENAME*で絶対パス名を入れる必要があるか考える（snmsts様、ご協力ありがとうございました）
loopマクロでtermination-testあたりがtype-specを無視しているので見直す。
top-levelでsetfによりlogical-pathnameを設定したら認識しなかったが、たぶん間違いなので調査すること。

結構ありますね。
そしてもっとあると思います。
もし何かバグやら問題を見つけましたら、githubのissuesでもいいですけど、ここにコメントで書きなぐってもらっても構いません。ただし開発時間があまりとれなくなったため、対応に時間がかかるとは思います。

書き直しについて

論理ブロック

セクション

マイザ書式

pprint-newline関数

条件付き改行:mandatory

通常の改行terpri

条件付き改行:linear

条件付き改行:miser

条件付き改行:fill

改行の連鎖

formatによる条件付き改行

このアルゴリズムについて

ソースから手動で入れる

LibreSSL構築

libevent構築

libasr構築

OpenSMPTD構築

環境設定

最後に

`pprint-newline`関数

条件付き改行`:mandatory`

通常の改行`terpri`

条件付き改行`:linear`

条件付き改行`:miser`

条件付き改行`:fill`

`format`による条件付き改行