nptclのブログ

Common Lisp処理系nptの開発メモです。https://github.com/nptcl/npt

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

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

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

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

(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

さて、これはどういうことなのでしょうか。
sbclcclは予想通りでしたが、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が正解ということになります。
しかしsbclclispでは、nil; tではなくnil; nilになっています。
どういうことなのでしょうか?

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

例えば下記の式、

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

は、integerconsは互いに排他のため、当然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になります。

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

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

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

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

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

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
# 

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

ソースから手動で入れる

ここでの手順はパッケージ管理されないので色々問題ありそう。
ずっと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の書き方が変わったんですって。

Nptで把握している問題点

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

  • 標準入出力のリダイレクトが非常に遅いのはなぜか調べる。 例えばこんな感じ$ npt --script file.lisp > zzz。 標準I/Oはキャッシュオフにしているせいだと思うがどうすればいいか考える。

  • defstruct:type vectorにしたacessor関数が、 LISPTYPE_VECTORのみ対応しているが、LISPTYPE_ARRAYに対応させる必要がある。

  • defstruct:typelist, 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)の第三引数は内部用で表に出てこない。

  • typepsatisfiesの実行割り込みreturn 1に対応させる。 つまりsatisfiesの関数内でreturn-fromthrowが発生したときを考慮する。

  • subtypepsatisfiesの実行割り込みreturn 1に対応させる。 つまりsatisfiesの関数内でreturn-fromthrowが発生したときを考慮する。 でもこれは無いかも。

  • fmte, fmtwを実行割り込みreturn 1に対応させる。 つまり関数内でreturn-fromthrowが発生したときを考慮する。

  • RefLispDecl, GetLispDeclを使用しているコードでNOTが考慮されているか調べる。 これなんだったか忘れたので調べなおす。

  • strarraycharactertypeはおかしいかもしれない。 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-keystならたぶんeval時点でwarningが起こるはず。

  • fmakunboundで型も削除

  • functionオブジェクトのnameにあるcallnamesetfになっていない。

  • defunで型を登録する

  • defunの型をもとにeval情報に型を登録

  • function-lambda-expressionのためにlambda-expressionfunctionに登録する。

  • fasl再作成

  • fixnum-localオブジェクトをcacheできるか考える

  • code_macro_functionnameを渡して処理する。 戻り値とdocumentationがどうなるかを調査する。

  • macro-lambdaallow-other-keys判定は必要だが、ordinary-lambdaには不要。 ただし、:allow-other-keysの実装によっていろいろ変わるかも。

  • macroの型チェックをどうするか調査。 現状、他の処理系では型チェックしているが、nptでは一切していない。

  • common-arraystypeチェックしているにもかかわらず、 手動で型のチェックをしている所が結構あるので削除する。 (integer 0 *)SIZE_MAXにすることでgetindex_integerを簡略化できる。

  • indexSIZE_MAXfixnumにしてしまった方が早くてよいのでは?

  • adjust-arrayの試験を追加する。

  • 普段はGetArrayXXではなくgetarrayを使うように変更、type-arrayなど。

  • function型チェックの都合上type-or, and, notasteriskを許容したが、 typepコマンドでちゃんとエラーになることを確認する

  • start-endendは標準でUnboundではなくNilが正解。

  • sxhashはもう少しちゃんとできないか考える。

  • openは8bit以外のbinary入出力をサポート、(unsigned-byte 16)など。

  • :direction :ioread->writeが切り替わるときにunreadを破棄する

  • :direction :ioをもう少し何とかする。

  • ANSI-Cモードのopenをもう少し何とかする。

  • 全てのstreamにてcloseされた状態を考慮していないので見直す。

  • Uniocdeのencodeをもう少し何とかする。 例えばBOMの扱いなど、Lispstrjisモジュール開発でわかったことを反映する。

  • 浮動小数点の出力がおかしいmost-positive-short-float。 これなんだったか覚えてないので調べる。

  • closの情報取得関数にデバッグの型チェックを入れる

  • コードにTODOと埋め込まれている部分が結構あるので片づける。

  • *LOAD-TRUENAME*絶対パス名を入れる必要があるか考える(snmsts様、ご協力ありがとうございました)

  • loopマクロでtermination-testあたりがtype-specを無視しているので見直す。

  • top-levelでsetfによりlogical-pathnameを設定したら認識しなかったが、 たぶん間違いなので調査すること。

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

Nptの開発状況

今まで開発に注力してきましたが、そろそろ時間が取れなくなってきたので、 現時点の完成度をまとめます。
loopマクロの開発が終わってv0.1.13commitした時点では、 ANSI Common Lispの関数やらマクロやらが

全996個中 919完成 (92%作成)

となります。
未完成の部分を表にまとめました。

f:id:nptcl:20190721020207p:plain
npt未完成部分

以前、Npt Lispの紹介 - nptclのブログで話題にした足りない部分の進捗は、

  • CLOSほぼ全部 ⇒半分くらい作成、redefineとchange-classがまだ
  • structure全部 ⇒全部作成
  • loopマクロ全部 ⇒全部作成
  • pretty printing全部 ⇒手つかずだが着手
  • 環境に関する関数 ⇒未着手
  • coreファイルの読み書き ⇒全部作成
  • faslファイルの読み書き ⇒未着手
  • isqrt関数 ⇒未着手
  • adjust-array関数 ⇒半分完成

です。

それで、最初に言った通り、作者は開発時間があまりとれなくなったため、 今後の開発速度は遅くなると思います。
せっかくここまで作ったので、中断するわけではなく、 遅かろうが何だろうが100%開発までは続けて行こうとは思っています。

あと、Nptを作ってハイ終わりって言うわけでもなく、 個人的な別の開発に使って行きたいという目的があるので、 C言語インターフェイス部分だけ開発されていくかもしれません。
9割もできてりゃあ、やれる事は結構ありますよ。

でもやっぱり100%の方が優先だろうなあ。

構造体とクラスの読み書きの速度

Common Lispの構造体とクラスはとても似ています。
一体何が違うのかというと、クラスの方が高機能であるというのは何となくわかります。
では、構造体なんていらないのでは? と思われるかもしれませんが、 CLtL2には次のような記載があります。

https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node170.html
The defstruct feature is intended to provide ``the most efficient'' structure class.
CLOS classes defined by defclass allow much more flexible structures to be defined and redefined.

つまり効率はstructureを、柔軟性はclassを。
そういう方針で両者は設計されています。

今回の話題は構造体とクラスの効率について記載します。
具体的にはslotの読み書きに関することです。
ちょうどdefstructを実装し終わった所なので、記憶が残っているうちに書き残します。

slot-valueによるslotの読み書き

クラスも構造体も、どちらもslot-valueが使えます。
まずはこいつから見て行きます。

通常のクラスシステムにおいて、slotを保有しているのは standard-objectインスタンスです。
つまりは、standard-classに関わる全てのオブジェクトです。
とても分かりづらいですね。
クラスに関係するもの全部だと思ってもらえればいいと思います。

純粋な意味での「オブジェクト指向」とは、 全てを「オブジェクト」で表すことです。
で、その「オブジェクト」とは一体何かなのですが、 本処理系やCommon Lispに限ったことではなく、 オブジェクト指向と呼ばれるものすべてに共通すると思うのですが、 オブジェクトはkey-value構造体です。
つまり、keyが与えられたらvalueを返却するというもの。
ここで言うkeyとはslotの名前のことであり、

(slot-value instance 'key) -> value

ということになります。

このkey-value構造体を実装する方法は色々ありますが、 nptではただの配列を使っています。
assocplistに近い構造だと思ってもらえればいいと思います。
つまり検索には線形探索が使われるので、O(n)だけの時間がかかります。

これはどうなんだろう?
遅くはないかどうか少し考えました。

以前、インスタンスhash-tableを使うように実装したことがありました。
うまく行けば探索がO(1)で済むようになるわけです。
でもやめました。
やめた理由はメモリ容量が多い事です。
あとhash-tableは何だかんだでオーバーヘッドが大きいので、 slotが一万個、十万個くらいないとhash-tableの恩恵が受けられないのではないでしょうか。

オブジェクト指向というシステムにおいて何が大量に生成されるかというと、 スロットではなくインスタンスだと思います。
それなのにひとつひとつにhash-tableは余りに無駄が多すぎると判断しました。

調べたわけではありませんが、たぶんどの実装も 線形探索になっているのではないでしょうか。
つまり、slotは大量にあればあるだけ動作は遅くなります。

slotにアクセスする命令は下記の4つにまとまっています。

  • slot-value
  • slot-boundp
  • slot-exists-p
  • slot-makunbound

この関数すべてが線形探索を実施していると考えてください。
そんなに安くはない関数なのです。

今までの話はクラスだけではなく構造体にも当てはまりますが、 クラスとは違っている部分がいくつかあります。

まず構造体のインスタンスstandard-objectではなくstructure-objectです。
両者の違いは何でしょうか。
構造体でもクラスでも、どちらもslot-valueが扱えるということは、 実装面から見れば、ジェネリック関数であるslot-value-using-classstandard-objectstructure-objectを両方定義しておいて、 別々の方法で読み書きをするということになります。

しかしnptの場合はどちらも全く同じものを使っています。
分ける必要性があまりありませんから。
他の処理系であるsbclやらclispやらも同じように実装しているのかと思います。

ここで言いたかったことは、構造体もクラスもslot-valueを使うのであれば違いはなく、 次のようなコストがかかるということです。

  • slot-valueは線形探索でO(n)だけの時間がかかります
  • slot-valueジェネリック関数を裏で呼んでいます

次はアクセス関数について見て行きます。

関数による読み書き(defstruct, defclass共通)

関数による読み書きとは、slotに対してreader/writer/accessorを経由するやり方です。
つまり、slot-valueを使わずに値を取得します。

構造体の場合は、何もオプションを指定しなければ、 全てのスロットに対して自動的に関数が生成されます。
クラスは、オプションを指定することでジェネリック関数が生成されます。

・構造体の場合
(defstruct aaa bbb)
  -> aaa-bbb, (setf aaa-bbb) という関数が生成される

・クラスの場合
(defclass aaa ()
  ((bbb :accessor aaa-bbb)))
  -> aaa-bbb, (setf aaa-bbb) というジェネリック関数が生成される

構造体は、関数を生成します。
クラスは、ジェネリック関数を生成します。

両者は似ていますが、速度面においては差が出てきます。
関数を使っている構造体の方が圧倒的に早く処理されます。

ジェネリック関数はどのような動きをするでしょうか。
最悪なケースとしては、実行するとまずはジェネリック関数に 登録されているすべてのmethodを寄せ集め、 引数の型から合致するmethodを選別します。
そのあと、method-combinationの実行によりLisp式が生成されます。
Lisp式はそのままでは実行できませんので、 evalcompileにより実行形式に変換されます。
生成された関数をはじめの引数に結びつけることで、 ようやくreader/writer/accessorが実行されます。

つまりジェネリック関数が呼ばれるたびに、 evalcompileが毎回走るかもしれないということです。
普通に考えると遅すぎます。

この辺りは規約に書かれているわけではないので処理系依存ですが、 もしかしたら本当に毎回evalが実行するような処理系があるかもしれません。
当然、これだと全く使い物にならないため、 キャッシュを用いる方法が提案されています。

The Art of the Metaobject Protocolという書籍では、 ジェネリック関数に与えられた引数の型をキーにして、 method-combinationが生成した関数をhash-tableに保存する方法が紹介されています。
その方法を用いると、初回実行は上記で説明したようにevalcompileが実行されますが、 2回目からは、引数の型をチェックし、 hash-tableを検索するだけで関数が実行できることになります。

ここでの結論は速度においては大切です。
構造体は純粋な関数を呼ぶため早いです。
しかしクラスはジェネリック関数が呼ばれるため、 早くてもhash-tableの検索が1回動いた後で関数が実行されます。

ここで言いたかったこと。

  • 構造体のアクセス関数呼び出しは、純粋な関数なので早い
  • クラスのアクセス関数呼び出しは、ジェネリック関数なので遅い

ちなみにslot-value関数も、 裏ではジェネリック関数であるslot-value-using-classを呼ぶため、 ある程度のコストがかかることを覚えておいた方がいいです。

関数による読み書き(defstruct

それでは関数が呼ばれたあとの内容について見て行きます。
構造体は、クラスと違って再定義が禁止されています(正確には未定義)。
よって、生成された関数は、その構造体のみを対象にすることができます。

構造体の定義で作成した関数なんだから当たり前じゃないかと 思われるかもしれませんが、defclassの方は再定義や変更が許されるので、 クラスのslotの内容が変わるかもしれないのです。

構造体は変更の心配がないため、 もしstructure-objectvalueの格納場所が配列であるならば、

(elt slots 3)  ;; このスロットに対応する値は3番目

のように数値を直接指定しておくことができます。
線形探索ではないので、処理はたぶんO(1)で完了します。
例外があり、構造体が(:type list)で生成された場合は nth関数が呼ばれるのと同じなのでそんなに早くはありません。

実際には値の返却だけではなく前処理が少しあります。
それは、引数が構造体であるかどうかと、 構造体が:include含めて型と合っているかどうかの判定です。

構造体の関数は、slot-valueに比べると、とても速いことがわかります。
slot-valueは便利ですが、それほど早くないかもしれないということも わかってもらえるかと思います。

ここで言いたかったこと。

  • 構造体のアクセス関数は、配列指定なので早い
  • 構造体のslot-value関数は、線形探索なので遅い

関数による読み書き(defclass

一方、クラスの場合は構造体とは全く変わり、slot-valueと何も変わりません。
せっかく苦労して呼び出されたジェネリック関数ですが、 ただ単純にslot-valueを呼んでいるだけなのです。

理由は再定義とクラス変更があるためです。
変更されたあと、関数は一体何を対象に読み込めばよいのかということと、 関数を実行したときに、例えばupdate-instance-for-redefined-classみたいな関数を どうやって呼べばいいかなどの色々な問題があり、 それらをすべて考慮しなければならないのは大変だということで、 slot-valueを使った処理と一致するようにと規約で制定されています。

以前は構造体と同じように配列を直で指定しようと考えていました。 つまり、クラス再定義やchange-classなどの実行契機で アクセス関数の対象メソッドを総入れ替えするというものです。

でも規約でそこまでするなと書かれているような気がするので、 今では単純にslot-valueを呼ぶだけです。 slotが既に存在していないとか、そういうのを一切気にしていません。

ここで言いたかったこと。

  • クラスのアクセス関数は、slot-valueと同じなので遅い。

まとめ

slotのアクセスは次の順に早い

  • 構造体のアクセス関数 ★一番早い
  • 構造体とクラスのslot-value
  • クラスのアクセス関数

npt-amalgamationの作成

私はnptというCommon Lisp処理系を細々と開発しています。
まだ目標であるANSI Common Lispの機能は完成していませんが、 以前紹介したときに言った「sqlite3みたいにamalgamationをやってみたい」 というのが先にできたので公開します。

npt-amalgamation
https://github.com/nptcl/npt-amalgamation

npt-amalgamationとは、nptソースコードをまとめて数個のソースファイルにしたものです。
テストケースは除外されていますが、本体のnptと同じようにコンパイルできます。
現段階では下記の3つのファイルにまとめました。

  • lisp.c
  • lisp.h
  • shell.c

実行例を示しますが、次のように適当にコンパイルしても何となく動いてしまいます。

$ cc lisp.c shell.c -lm
$ ./a.out
(defun aaa (x) (if (<= x 1) 1 (* x (aaa (1- x)))))
AAA
(aaa 111)
1762952551090244663872161047107075788761409536026565516041574063347346955087248316436555574598462315773196047662837978913145847497199871623320096254145331200000000000000000000000000
^D
$

C言語のモジュールとして使うためのインターフェイスは何も整備されていませんが、 そのうちどうにかしたいです。

C言語のconstの使い方

今までconstの書き方がよくわかっていませんでした。
で、調べたら予想以上に難しかったです。

本投稿ではconstの使い方を記載していくわけですが、 規約を調査したわけではなく、Cコンパイラで実験した内容です。 もしかしたらおかしい所があるかもしれません。
実験に使用したコンパイラは、FreeBSD 11.1 clang, Gentoo Linux gcc, Windows 10 Visual Studio 2017付属のやつです。

constの意味

constとは定数を宣言するときに使います。
書き込み不可という意味が強いと思います。

簡単な例としては下記の通り。

const int a = 100;

別の書き方もあります。

int const a = 100;

意味は同じになります。
あるいは2つ書いても同じです。

const int const a = 100;  /* 警告 */

しかしconstを重複させるのはダメのようで、コンパイル時に警告が出ました。

あと、古いC言語だと、intに限って省略できたはず。
つまり、

const int a = 100;
は
const a = 100;  /* 警告 */

と記載できます。
でもこれは今のC言語だと規約レベルでダメだったような記憶があります。
clangとgccでは警告が出ました。

では、もし値を代入しようとした場合はどうなるでしょうか。
下記の例を示します。

const int a = 100;
a = 200;  /* エラー */

この場合は、コンパイルエラーとなりますので、実行できません。
なんとかして無理やり代入するとどうなるでしょうか。

#include <stdio.h>
int main()
{
    const int a = 100;
    *((int *)&a) = 200;  /* 危険 */
    printf("%d\n", a);
    return 0;
}

実行結果

$ cc main.c
$ ./a.out
200
$

やったね、うまく行きました。
でも確かこれはかなり危険だったはず。

上記の例はコンパイラとOSによって挙動が変わります。
constの定数は、書き込み不可のメモリ領域に配置することが許されています。 実行例では書き込み可能な領域に配置されたようですが、 もし書き込み不可の領域を書き換えようとした場合は、 OSレベルにて不具合が生じるため、最悪Segmentation violationコースとなります。

上記の実行はGentoo Linux+gccによるものです。
FreeBSD+clangでは、なぜか100が返却されました。

constポインタの書き方

constはポインタにも使用できます。
詳しく見ていく前に、まずは書き方から。

通常の変数の場合、constは、重複と省略を考慮しないのであれば、 次の2通りの方法があると説明しました。

const char a;
char const a;

ポインタの場合は、ポインタを表すアスタリスク*が一つ増えるごとに、 constの書ける位置が1つずつ増えていきます。

charのポインタであるchar *の場合は、次の3通りの位置に記載できます。

const char *a;
char const *b;
char *const c;

abは同じ意味となります。
ではポインタのポインタの……ポインタの場合はどうなるでしょうか。
例えば、

char ******a;

の全てにconstをつけたものは、次のどちらかになります。

const char *const *const *const *const *const *const a;
char const *const *const *const *const *const *const a;

アスタリスクが6個で、constの書ける場所は8か所。
そのうち、上記の2例は同じ意味なので、 値を定数として指定できるのは7か所ということになります。

もうこの時点で簡単ではないです。
constの記載する位置は、一見規則正しく並んでいるようなのですが、 左から一番目と二番目が同じ意味であり、かつ重複不可なので混乱するのです。

ではconstの位置によって何が変わるのでしょうか。
引き続き、

char ******a;

constにする場合を考えて行きます。
変数aは、式で宣言したときと同じ数のアスタリスクを付けると、 指定した型そのものになります。

つまり、******aの型はcharなので、

******a = 'Z';

みたいに書けるわけです。
このcharconstとして定数と宣言したい場合は、 一番左側にconstを付けます。 一番左と言っても書き方は二通りあるため、 例えば次のどちらかとなります。

const char ******a;
char const ******a;

一方、式でアスタリスクを一つもつけない場合は全く逆となります。
つまり、aの型はchar ******であり、 constを指定したい場合は一番右側にconstを付けます。

char ******const a;

*aconstにしたい場合は、

char *****const *a;

**aconstにしたい場合は、

char ****const **a;

と順番にずれていくわけです。

constを2つ以上宣言することも可能であり、**a***aconstにしたい場合は、

char ***const *const **a;

となります。

初期化と代入

初期化とは、変数宣言時に値を設定することです。
例えばこんな感じ。

int a = 100;

代入とは、変数に値を格納することです。
例えばこんな感じ。

a = 100;

const変数を初期化する、あるいは代入する場合は、 両辺の各constがどうなっているのかを合わせて調査して行き、 問題がある場合はエラーか警告が出力されます。

このチェックは、次の3段階に分けて行われます。

  • 右から1番目のconst
  • 右から2番目のconst
  • 右から3番目以降のconst

これらをひとつずつちゃんと説明していきます。

右から1番目のconst

右から1番目のconstとは、例えば

int ****const a;

のような場合です。
これは変数そのもののconstなので、 代入は禁止されますが初期化は禁止されません。

初期化とは

int ****const a = b;

みたいなものです。
初期値を与えられなければ定数にもできないので、 当然有効な宣言となります。

一方、const指定されたということで、

a = b;

とするのは値を変更することになるのでエラーです。

当たり前のことですよね。
でも、右から1番目のconstは、右から2番目、3番目とは違って、 ポインタとは一切関係がないと覚えておくといいと思います。

右から2番目のconst

例えば、

const int ****const *ptr;

のような場合です。
よく文字列を扱うときに、

const char *ptr;
char const *ptr;

と宣言しますが、まさにこの場合が該当します。

右から2番目のconstは、それ以外のconstとは違っていて特別な判定がされます。
初期化と代入で、チェックの内容は変わりません。
例えば、下記の場合を考えます。

a = b;

もしbよりもaの方が制限がきつくなる場合はOKです。
しかし逆にbよりもaの方が制限が緩くなれば警告が発せられます。

つまり、せっかく値をconstで保護をしていたにも関わらず、 それを解除するような代入をする場合は警告になるのです。

次の宣言があったとします。

const char *a;
char *b;

このとき、

a = b; /* OK */
b = a; /* 警告 */

となります。

ちなみにこの右から2番目のチェックは、 違反していた場合はコンパイルエラーではなく警告が出力されます。
たぶんコンパイルは継続されるので実行ファイルができてしまいます。
しかし正しいと思わずにちゃんと原因を突き止めるべきであり、 もし問題ないならば明にキャストしましょう。

右から3番目以降のconstgcc, clang)

恐ろしいことにVisual Studio 2017と挙動が異なりました。
まずはgcc, clang編。

3番目以降は、初期化か代入を行う際には、 constと非constが全て同じでなければなりません。

右辺にconstと指定されていたら、左辺もconstです。
2番目みたいに、左辺constで右辺非constは許されません。
左辺が非constなら、右辺も非constでなければなりません。

こちらも違反した場合は、エラーではなく警告が出力されます。

それでは例をあげます。

char ****a = NULL;
char const *const *const *const *const b = a; /* 警告 */

右から1番目、2番目はOKですが、3番目以降のconstが 合っていないので違反です。

char ****a = NULL;
char ***const *const b = a; /* OK */

3番目以降が全て非constなのでOKです。

char const **const **const a = NULL;
char const **const *const *b;
b = a; /* OK */

このとき、

aは(const, なし, const, なし,  const)です。
bは(const, なし, const, const, なし )です。

右から1番目は、const→なしなのでOK。
右から2番目は、なし→constなのでOK。
右から3番目以降は、全て一致するのでOK。

右から3番目以降のconstVisual Studio 2017)

コンパイル間で挙動が変わったので、Visual Studio 2017編です。
こちらは単純に、右から2番目と同じです。
つまり、非constconstへの値の変更は許されます。

なので下記の例

char ****a = NULL;
char const *const *const *const *const b = a;

は、gcc, clangではエラーでしたが、 Visual Studio 2017では問題なくコンパイルが通りました。

もし移植性を考慮するなら、こちらではなくより厳しいgcc, clangの方に 合わせればいいと思います。

修飾子の複合

c89時点でC言語の修飾子は6個あると記憶しています。

register
auto
extern
const
static
volatile

今はもっとあるんでしょうか、知らないですけど。

constと同じように記載できるのは、volatilerestrictだそうです。
なんですかrestrictって。
c99から出てきたようですが、あまりよく知らない人なので今回は無視。

それで、これらを複合すると、一見してよくわからないことになったりします。
例えばchar *constvolatileを合わせたい場合はどうしたらいいでしょうか。
volatileの記載する位置は、constと変わりません。
そして、constvolatileは、同じ位置に順番は関係なく記載できます。
例えば下記の通り。

char *a;  /* 通常のポインタ */
const volatile char *b;  /* charにconstとvolatile */
char volatile const *c;  /* bと同じ */
const char *volatile d;  /* charがconstでポインタがvolatile */
volatile char const *const volatile e;  /* charもポインタもconst volatile */

ではvolatileの初期化と代入は、constとはどう違っているのでしょうか。
簡単に説明すると次の通り。

  • 右から1番目は、volatileでは制約は無し
  • あとはconstと同じ

ではconstvolatileが合わさって宣言された場合はどうなるのか。
ただconstvolatileを分けて考えればいいだけです。
例えば次の通り。

const char *a;
const volatile char *b;
b = a; /* 問題なし */
a = b; /* エラー */

続いて、次の例を考えます。

volatile char const *volatile const *volatile **const a = NULL;
char const volatile *const *volatile *volatile *volatile b;
b = a;  /* エラー */

このとき、

aは(v+c, v+c,   volatile, なし,     const)
bは(v+c, const, volatile, volatile, volatile)

右から1番目は、volatileは制約なし、const→なしとなるのでOK。
右から2番目は、なし→volatileなのでOK。
右から3番目以降は、4番目がv+cconstなのでエラー。

引き続き、次の例を考えます。

volatile char const *const *volatile **const a = NULL;
char const volatile *const *volatile *volatile *volatile b;
b = a;  /* OK */

このとき

aは(v+c, const, volatile, なし,     const)
bは(v+c, const, volatile, volatile, volatile)

つまり、代入は問題なしです。