Inside newLISP (4)

去年あたりからさかんに人口知能と言う言葉が聞かれるようになった。ブームなんですかね。 これで何度目のブームやら。

第一弾としてアイドル篠崎愛をAI化

日本マイクロソフトが男性を虜にする女子高生AI「りんな」を開発

チューリングテストにパスする事を狙ってるんだな。旨く出来れば、闇サイトで女子高生と 怪しい会話ってのが自動化出来ますから、ぼろ儲けでっせ。年金の特殊詐欺なんて危ない 橋を渡らず、こちらにシフトしたらどうでっしゃろ。

勿論、いきなり高度な事は出来ませんから、その道のプロ達が集まっているアプル(シリ)とか、 ぐぐるへ行って3年程、修行をしてきましょう。

じょーだんはさておき、

人工知能が開発されても人類は滅亡したりしない

人工知能はどこへ向かうのか:AIと機械学習の今

スマホの人工知能が直接対決。結果はGoogle Nowの圧勝

BigDataの解析がコンピュータの馬鹿力で出来るようになったので、それを称して人口知能と 言ってる感もしないではないけどね。

Fine Software Writingsなんてのを見ると、 人工知能が人間より高い知性を持つようになったとき何が起きるか? なんてのが話題として取り上げられてるぞ。

人口知能の元祖と言えば、そりゃLispさ。ってんで、 Lispの真実 なんて記事も挙がってる。その記事の最後の方に、Lisp中毒の代替物として、newLISPが あがっているけど、newLISPってLISPの代替品?

ああ、emacsの中にも、doctorが住んでいるね。

I am the psychotherapist.  Please, describe your problems.  Each time
you are finished talking, type RET twice.

M-x doctor で、相談に乗ってもらえる、精神科の先生。emacsな人達は病んでいるんだな。

借りてきて実にする

前回、なんクリ したけど、ちまちまとdocsを読んでたんだ。 C bindings この部分ね。

これって、他人の褌で相撲を取る ってやつだよね。

lib C
  # In C: double cos(double x)
  fun cos(value : Float64) : Float64
end

こうやって、借りてくる準備をしておいてから、C.cos(1.5) こういう風に使えとな。 その多の例に出てた、c.getch ってのは、恥ずかしながら知らなかったぞ。知らない事を 知ったらどうするか? そりゃmanでしょ。そうか、君はcursesの仲間か。

で、newLISPでも他人の褌モードが有ったよなぁ、と思い出したぞ。復習を兼ねて、追って みるかな。

import library

だったような。。。過去ログ確認したら出てきた。Cのライブラリーを何喰わぬ顔してnewLISP から使っちゃうやつ。これが出来るから、やれMySQLを使えるぞとかposgressも使えるぞと、 間口を広げられるんだよな。そんなの、rubyのライブラリィーにも有って、大変お世話に なりました。

モジュールの所に色々あるだろう。面白そうなのがあった。 crypto.lsp。メッセージダイジェストを取るやつ。 コードを見ると、SSL libからのlibcrypto.soが元の褌。

(import library "MD5") して、CのライブラリィーからMD5を使うよって宣言。 libraryってのは、関数になってて使うOSによる正確なライブラィー名の差を吸収してくれる。

lispユーザーの為のインターフェース関数が用意されてる。

;; @syntax (crypto:md5 <string> <bool-raw>)
;; @param <string> The string buffer for which to calculate a MD5 hash
;; @param <bool-raw> Return the raw binay buffer when 'true'.
;; @return The 16 Byte MD5 hash as a 32 Byte long hex string or as a 16 byte binary buffer.
;; @example
;; (crypto:md5 "ABC") => "902fbdd2b1df0c4f70b4a5d23525e932"
;;
;; (crypto:md5 (read-file "newlisp-9.1.0.tgz")) => "46c79c93e904df35c6a8474ace406c92"

(define (md5 str raw-flag)
  (if raw-flag
      (let (buff (dup "\000" 16))
        (cpymem (MD5 str (length str) 0) buff 16)
        buff)
    (join
     (map (lambda (x) (format "%02x" (& x 0xff)))
          (unpack (dup "c" 16) (MD5 str (length str) 0))))
    )
  )

勿論、md5だけじゃなくて、shaとかも定義されてるぞ。

どうも、肝はMD5って関数だな。関数名が大文字で始まってるんで、ひょっとしてマクロかと 思ったぞ。

[ob: ~]$ nm /usr/lib/libcrypto.so.32.0 | grep MD5
0008bee0 T MD5
00120e50 T MD5_Final
00120df0 T MD5_Init
00120f50 T MD5_Transform
00120f90 T MD5_Update

外部に公開されてる純然たる関数ですねぇ。一応manしとく

        #include <openssl/md5.h>

        unsigned char *MD5(const unsigned char *d, unsigned long n,
                         unsigned char *md);

        int MD5_Init(MD5_CTX *c);
        int MD5_Update(MD5_CTX *c, const void *data,
                         unsigned long len);
        int MD5_Final(unsigned char *md, MD5_CTX *c);

RETURN VALUES
       MD2(), MD4(), and MD5() return pointers to the hash value.

OpenBSDはMD5Initなんてのもlibcに入っていて、ちと紛らわしい。こちらは完全にOS依存 なんだろうね。早速追ってみる。

上記のモジュールを分解してくと、下記になるっぽい。

> (setq str "ABC")
"ABC"
> (import "libcrypto.so.32.0" "MD5")
MD5@A58EEE0
> (MD5 str (length str) 0)
763841796
> (MD5 str (length str) 0)
763841796

まずは使う関数を登録する方。nl-import.cにある、p_importLib が、呼ばれる。

 126    int             type = CELL_IMPORT_CDECL;
 127#endif
 128
 129
 130    params = getString(params, &libName);
 131=>  if (params != nilCell)
 132        params = getString(params, &funcName);
 133    else
 134        funcName = NULL;

引数の文字列を登録しておいて

 158=>  if ((hLibrary = dlopen(libName, RTLD_GLOBAL | RTLD_LAZY)) == 0)
   :
 165    symbol = translateCreateSymbol(funcName, type, currentContext, TRUE);
   :
 177=>  pCell->contents = (UINT) dlsym(hLibrary, funcName);

ライブラリィーをdlopenしてから、目的関数のアドレスを取り出して、シンボルに登録してる。 以降、MD5は普通の関数として扱われるんだな。実際にMD5を使うと、evaluateExpression内の

1536        /* simple ffi with CDECL or DLL and extended libffi */
1537        if (pCell->type & IMPORT_MASK) {
1538=>          result = executeLibfunction(pCell, args->next);
1539            break;

nl-import.c 内のexecuteLibfunctionへ制御が移り、引数を評価した後

 243=>      return (stuffInteger(cdeclFunction(pCell->contents, args, count)));

に到達する。

cdeclFunction (fAddress=227258080, args=0xcfbf18a0, count=3) at nl-import.c:252
252         function = (UINT(*) ()) fAddress;

で呼ばれて

 264    case 3:
 265        /*
 266         * printf("args[0] %llx, args[1] %llx, args[2] %llx,
 267         * args[1]-args[2] %llx\n ", args[0], args[1], args[2],
 268         * args[1] - args[2]);
 269         */
 270
 271        return (*function) (args[0], args[1], args[2]);

この時のそれぞれの引数は

(gdb) x/s args[0]
0x7c68ca00:     "ABC"
(gdb) p args[1]
$5 = 3
(gdb) p args[2]
$6 = 0

返ってきた値はポインターだそうなので、そこを調べてみると

(gdb) x/16b 763841796
0x2d874d04 <m.3250>:    0x90    0x2f    0xbd    0xd2    0xb1    0xdf    0x0c    0x4f
0x2d874d0c <m.3250+8>:  0x70    0xb4    0xa5    0xd2    0x35    0x25    0xe9    0x32

ちゃんとMD5を計算してました。まずは、目出度し目出度し。

MD5

先ほどは、MD5のルーチンを素通りしちゃったけど、今度はMD5の中へ潜ってみる。

(gdb) n
271             return (*function) (args[0], args[1], args[2]);
(gdb) s
MD5 (d=0x79c5e8c0 "ABC", n=3, md=0x0) at /usr/src/lib/libcrypto/crypto/../../libssl/src/crypto/md5/md5_one.c:65
65              {

OpenBSDは親切な事にライブラリィーの中まで入って行ける。これはもうどんなOSにも勝る 特色と言って良いだろう。

おいらが疑問だったのは、MD5の返してくれるポインターが常に同一だった事。それって、 リエントラント性(再入性)を失っていないかって事。もしそうなら、並列実行出来ないじゃん。 こういう疑問はソース嫁。

64unsigned char *MD5(const unsigned char *d, size_t n, unsigned char *md)
65=>      {
66        MD5_CTX c;
67        static unsigned char m[MD5_DIGEST_LENGTH];
68
69        if (md == NULL) md=m;
70        if (!MD5_Init(&c))
71                return NULL;
72        MD5_Update(&c,d,n);
73        MD5_Final(md,&c);
74        OPENSSL_cleanse(&c,sizeof(c)); /* security consideration */
75        return(md);
76        }

関数自体は、MDを計算する流れ(initしてupdateしてfinalする)をまとめて、使い易くした ものだな。

mdに0x0が渡って行くって事は、NULLなんで、69行目が実行される。ライブラリィー内に用意 した配列mが使われるのだな。この行が実行された後

(gdb) p &md
Address requested for identifier "md" which is in register $esi
(gdb) p $esi
$11 = 609639684

ちょいとgdbに文句を言われたのは、最適化の都合なんだろうね。それはそうと、newlispの 結果はと言うと

> (MD5 str (length str) 0)
609639684

確かにこのままじゃ、再入性を担保出来ないな。ちゃんとやろうとしたら、lisp側でバッファーを 用意して、そこに答えを入れて貰えとな。

昔の事を思い出した。祖父の唯一の楽しみは晩酌。家に酒があると、あるだけ呑んじゃうので、 酒は置いていなかった。酒瓶を持って酒屋へ買いに行くのは、おいらの役目。 ある日、いたずらでちょいと呑んでみた。なんでこんなのが旨いんだ。大人は変だなと思った ものだ。それがどうだ、今じゃ、一日の締めに酒はかかせない、佳き友となっております。

       MD2(), MD4(), and MD5() compute the MD2, MD4, and MD5 message digest of
       the n bytes at d and place it in md (which must have space for
       MD2_DIGEST_LENGTH == MD4_DIGEST_LENGTH == MD5_DIGEST_LENGTH == 16 bytes
       of output). If md is NULL, the digest is placed in a static array.

こんな大事な事を見落としていた。まだまだ修行が足りないな。 Wataru's memoのプログラマの教養は manual pagesを 再読してみよう。

GC

newLISPってガベコレって有るの? いいえ有りません。ですから、何処かのジャバみたいに、 GC Overhead limit exceeded とか は原理的に発生しません。以上。

で話が終わってしまってはつまらないので、ガベコレフリーをどうやって実現してるか、 さわりを見てみたい。

cellが必要になったらgetCellで空きセルを貰ってきて、不必要になったら、deleteListの中で 開放されているようだ。cellCountに注目してみる。

実行したのは、ただの数値 1 の評価。

(gdb) watch cellCount
Watchpoint 1: cellCount
(gdb) c
Continuing.
Watchpoint 1: cellCount

Old value = 472
New value = 473
getCell (type=26) at newlisp.c:2088
2088        cell->type = type;
(gdb) bt
#0  getCell (type=26) at newlisp.c:2088
#1  0x16be50c6 in evaluateStream (stream=0xcfbd86e0, outDevice=2, flag=0) at newlisp.c:1267
 :

この時のフレーム1は

1267=>      pushResult(program = getCell(CELL_QUOTE));
1268        result = compileExpression(stream, program);

入力された文字列をS式にコンパイルし、その結果を保持する用だな。

(gdb) c
Old value = 473
New value = 474
stuffInteger64 (contents=1) at newlisp.c:1949
1949        cell->type = CELL_INT64;
(gdb) bt
#0  stuffInteger64 (contents=1) at newlisp.c:1949
#1  0x16be9f35 in compileExpression (stream=0xcfbd86e0, cell=0x80c499d0) at newlisp.c:3320
#2  0x16be50e0 in evaluateStream (stream=0xcfbd86e0, outDevice=2, flag=0) at newlisp.c:1268
 :

コンパイル結果の1を保持するためのセル確保。数値とか文字列は1つのセルを消費するんだった。

(gdb) c
Continuing.

Breakpoint 2, evaluateExpression (cell=0x7bf809e0) at newlisp.c:1453
1453        symbolCheck = NULL;

そしてS式の評価

(gdb) c
Continuing.

Breakpoint 3, printCell (cell=0x7bf809e0, printFlag=1, device=2) at newlisp.c:2447
2447        if (cell == debugPrintCell)

続いて、結果の表示

(gdb) c
Old value = 474
New value = 473
deleteList (cell=0x80c499e0) at newlisp.c:2241
2241                cell = next;
(gdb) bt
#0  deleteList (cell=0x80c499e0) at newlisp.c:2241
#1  0x16be761d in deleteList (cell=0x80c499d0) at newlisp.c:2226
#2  0x16be6647 in cleanupResults (from=0x829c9000) at newlisp.c:1717
#3  0x16be5255 in evaluateStream (stream=0xcfbd86e0, outDevice=2, flag=0) at newlisp.c:1294
 :
(gdb) c
Old value = 473
New value = 472
deleteList (cell=0x80c499d0) at newlisp.c:2241
2241                cell = next;
(gdb) bt
#0  deleteList (cell=0x80c499d0) at newlisp.c:2241
#1  0x16be6647 in cleanupResults (from=0x829c9000) at newlisp.c:1717
#2  0x16be5255 in evaluateStream (stream=0xcfbd86e0, outDevice=2, flag=0) at newlisp.c:1294
 :

評価が終わったんで、不要になった2つのセルを開放。

(gdb) c
Old value = 472
New value = 473
getCell (type=26) at newlisp.c:2088
2088        cell->type = type;
(gdb) bt
#0  getCell (type=26) at newlisp.c:2088
#1  0x16be50c6 in evaluateStream (stream=0xcfbd86e0, outDevice=2, flag=0) at newlisp.c:1267
 :

もう一度、evaluateStreamに戻って、次のS式の評価準備。

(gdb) c
Old value = 473
New value = 472
deleteList (cell=0x80c499d0) at newlisp.c:2241
2241                cell = next;
(gdb) bt
#0  deleteList (cell=0x80c499d0) at newlisp.c:2241
#1  0x16be6647 in cleanupResults (from=0x829c9000) at newlisp.c:1717
#2  0x16be5255 in evaluateStream (stream=0xcfbd86e0, outDevice=2, flag=0) at newlisp.c:1294
 :

でも、次に続くS式が無かったので、先ほどのセルを回収。結局、Streamの終端判定を、 S式のコンパイルで行っているって事、なんともまどろっこしいけど、こういうのも有りなんだな。

なお、使ったセルの後での消去のために、pushResultとpopResultと言うマクロが使われている。

#define pushResult(A) (*(++resultStackIdx) = (UINT)(A))
#define popResult() ((CELL *)*(resultStackIdx--))

このように、使った分を覚えておいて、不用になったら直ぐに開放するって戦略を取っている。 それじゃ数有るGC方式のうちのレファレンスカウント方式とどう違うか。カウンタ方式は、それ用の カウンタをセルごとに設ける必要が有るんだけど、newLISP式はそれが不要。 なかなかよく出来ているな。

なお、セルの開放をやってるdeleteList内で、メモリーの大量消費に繋がる、文字列やダイナミックシンボル、それに巨大数の場合は、 メモリー領域をOSに返却してから、cellを開放してる。こうしないとメモリーリークになるからね。

勿論、永久保存しなけれならないようなS式を実行した時は、セルの使用数は増える。

> (sys-info)
(482 268435456 416 1 0 2048 0 32026 10602 130)
> (setq hoge '(1 2 3 4 5))
(1 2 3 4 5)
> (sys-info)
(488 268435456 417 1 0 2048 0 32026 10602 130)

セル数は6個増えた。(1 2 3 4 5) のリストは、5エレメント プラス nilで構成されてるから、 6セルになるんだった。

この状態から、(set 'hoge '(1 2)) したらどうなる? setなんで、p_setが呼ばれて、 その中からsetDefineへ移ってくる。

4983=>  cell = copyCell(evaluateExpression(params));
4984
4985    deleteList((CELL *) symbol->contents);
4986    symbol->contents = (UINT) (cell);

パラメータを評価して、それをコピーしてる。だって、渡されてきたパラメータは、compileExpressionが 作ったもので、やがて削除される運命にあるから。

4985行で、昔のシンボルの結果(1 2 3 4 5)を削除し、新しくコピーしたものに置き換えて いる。大きなリストとかだとコピーが大変とかあるけど、それでもリアルタイムGCは 魅力的って作者は判断したんだな。

言ってみれば、大掃除を長い時間かけてやるんじゃなくて、普段から綺麗にしておきましょって、 日本的な美的精神に溢れる所業です。