#:g1: frontpage

 

Common Lisp版Portable Prologを動かすメモ

Posted 2016-08-22 17:54:47 GMT

中島秀之先生は、Portable PrologというLispで実装されたProlog処理系をお書きになっていますが、それのCommon Lisp版が古えのfjに流れていたようです。
そのCommon Lisp版Portable Prolog(以下PPiCL)ですが、CMUのAIリポジトリに保存されています。

行数にして150行足らずのコンパクトな処理系です。

しかし、このPPiCL、使い方の解説が全くないので、使い方を調べてみました。

とりあえず、ANSI Common Lisp対応

'(lambda (form subst) ...)

クォートされたlambda式は、ANSI CLでは廃止になったので、

#'(lambda (form subst) ...)

とします。

動かしてみる

PPiCLのプリミティブ

コードを眺める限りでは、

  • assert
  • call
  • end
  • eval
  • if

がプリミティブのようです。

使い方を探る

prologという関数がインタプリタの本体のようです。
S式Prologなので実行すると、ユーザーの入力するS式を待ちます。
(end)でインタプリタの終了のようですが、ループを抜けるフラグであるepilogTがセットされるので一度実行されると、epilogに再度nilを設定しない限り起動したら直ぐ終了してしまいます。
恐らく毎度一から起動するのが想定された使い方なのでしょう。

毎度コマンドラインから起動するのは面倒なので、Common Lisp処理系から起動するとしたら、こんな感じになるかなと思います。

(defun ppicl (file)
  (with-open-file (*standard-input* file)
    (let ((ppicl::cue nil)
          (ppicl::clause nil)
          (ppicl::epilog nil)
          (ppicl::fetched-subst nil)
          (ppicl::goal nil)
          (ppicl::new-subst nil)
          (ppicl::old-subst nil)
          (ppicl::undo-list nil)
          (pkg (make-package (string (gensym))
                             :use '(:cl))))
      (do-external-symbols (s :ppicl)
        (shadowing-import s pkg))
      (prog1 (let ((*package* pkg))
               (ppicl::prolog))
        (delete-package pkg)))))

なんだかややこしいことをしていますが、PPiCLがシンボルの属性リストをいじるので、都度初期化して、予想外のことにならないように対策したためです。
Common Lisp処理系も一緒に終了するならば、こういうことは必要ないと思います。

また、上記では、パッケージの記載がありますが、PPiCLのファイルの先頭には、

(defpackage ppicl
  (:use :cl)
  (:shadow :if :assert :eval)
  (:export :assert :call :end :eval :if))

(in-package :ppicl)

のようなものを追加しています。

takでも実行してみる

tak.ppiclというファイルに、

(assert (tak *x *y *z *a)
        (eval (<= *x *y) T)
        (eval (values *z) *a))

(assert (tak *x *y *z *a) (eval (1- *x) *x1) (tak *x1 *y *z *a1) (eval (1- *y) *y1) (tak *y1 *z *x *a2) (eval (1- *z) *z1) (tak *z1 *x *y *a3) (tak *a1 *a2 *a3 *a))

(tak 3 2 1 *a) (tak 6 4 2 *a) (tak 9 6 3 *a) (tak 12 8 4 *a) (tak 15 10 5 *a) (tak 18 12 6 *a)

(end)

のようなものを書き、上記で作成したユーティリティで読み込ませます。

(ppicl ".../tak.ppicl")

と実行すると、

(portable prolog (in common lisp))

(assert (tak *x *y *z *a) (eval (<= *x *y) t) (eval (values *z) *a))

(assert (tak *x *y *z *a) (eval (1- *x) *x1) (tak *x1 *y *z *a1) (eval (1- *y) *y1) (tak *y1 *z *x *a2) (eval (1- *z) *z1) (tak *z1 *x *y *a3) (tak *a1 *a2 *a3 *a))

(tak 3 2 1 2)

(tak 6 4 2 3)

(tak 9 6 3 6)

(tak 12 8 4 5)

(tak 15 10 5 10)

(tak 18 12 6 7)

(end)

と答えが出ます。

Uranusと同じように成功すれば、マッチした式が返ってくるという形式のようです。

なお、(tak 18 12 6 7) 位になると大抵の処理系ではスタックが溢れて実行できないようです。
(ちなみに、LispWorksでは7006173まで拡張していけば実行が完了しました。)

構文の解説

変数の表記はProlog/KRやUranusと同じく先頭に‘*’を付けます。

定義のためのassertと、パタンマッチ以外には、ほぼ何もありませんので、何かパタンマッチ以外のことをするにはLisp関数を呼ぶevalを利用することになります。

(eval lisp式 結果)

という形式ですが、(< 1 2)のようなものが成功したことを表すには、どうやら、(eval (< 1 2) T)と書くようです。
また、上記takでは変数のマッチでも(eval (values *a) *b)のように書いていますが、ほんとにこんな書き方で良いのか謎です。
とはいえ、他に書き方がないようにも思えます。

そして、上でも書きましたが、読み込みの終了には(end)が必須です。

まとめ

Portable PrologのCommon Lisp版の使い方を探ってみました。
初代Portable Prologは、もう少し違った記述方法のようです。こちらもそのうちCommon Lispで動かしてみようかなと思っています。


HTML generated by 3bmd in LispWorks 7.0.0

Common LispでFast inverse square rootを実装してみました!

Posted 2016-08-13 15:56:34 GMT

30のプログラミング言語でFast inverse square rootを実装してみました!—プログラムモグモグを読んでFast inverse square rootというのを知ったのですが、この記事にはClojure、Scheme(Gauche)版はあってもCommon Lisp版がなかったので試しに書いてみました。

single-float から IEEE 754形式のビットの並び(binary32)を取得する

Fast inverse square rootの肝は、singleをintにキャストする所にあるようなのですが、Common Lispには、キャストというものはない訳です。
とはいえ何通りか方法があるようなので試してみました。

LispWorks篇

floatをintegerにキャストするようなコードを適当に探してみましたが、最初に見付けたのが、CLXの

(defun %single-float-bits (x)
    (declare (type single-float x))
    (fli:with-dynamic-foreign-objects ((bits :int32))
      (fli:with-coerced-pointer (pointer :type :lisp-single-float) bits
        (setf (fli:dereference pointer) x))
      (fli:dereference bits)))

のようなコードです。他のプラットフォームでは、single-float-bitsのような内部関数があるようですが、LispWorks用のコードではFFIを経由。
なんだか遅そうな印象がありますが、実測してみたらそうでもないみたいです(後述)

ということでint→floatのコードも真似して作ってみました。

(defun single-float-bits (x)
  (declare (type single-float x))
  (fli:with-dynamic-foreign-objects ((bits :int32))
    (fli:with-coerced-pointer (pointer :type :lisp-single-float) bits
      (setf (fli:dereference pointer) x))
    (fli:dereference bits)))

(defun single-float-from-bits (x) (declare (type (integer 0 #xffffffff) x)) (fli:with-dynamic-foreign-objects ((bits :single-float)) (fli:with-coerced-pointer (pointer :type :int32) bits (setf (fli:dereference pointer) x)) (fli:dereference bits)))

これで、

(defun fast-inv-sqrt (x)
  (let* ((i (single-float-bits x))
         (y (single-float-from-bits (- #x5f3759df (ash i -1)))))
    (* y (- 1.5f0 (* 0.5f0 x y y)))))

(mapcar #'fast-inv-sqrt '(100.0 10.0 1.0 0.1 0.01 0.0025))(0.09984488 0.31568578 0.99830717 3.157232 9.982522 19.965044)

という感じです。

SBCL篇

SBCLでは、LispWorksで自作した single-float-bitsのようなものが備え付けであるので、floatオブジェクトのアドレスに埋め込まれたbinary32表現を取り出してみることにしました。
自分が調べた限りでは、floatオブジェクトのアドレスにbinary32表現が埋め込まれているらしき処理系は、

  • SBCL 64bit
  • Clozure CL 64bit
  • LispWorks 64bit

位でした。
ちなみに、Allegro CL 64bitは一見した限りではアドレスが毎度変わっているようです。

ということで、SBCL 64bitでしか動かない版はこちらです。

(defun fast-inv-sqrt (x)
  (let* ((i (ldb (byte 32 32) (sb-kernel:get-lisp-obj-address x)))
         (y (sb-kernel:make-lisp-obj (+ (ash (- #x5f3759df (ash i -1)) 32) 25))))
    (* y (- 1.5f0 (* 0.5f0 x y y)))))

binary32が埋め込まれているのは、32ビット目より上のようなのでldbで切り抜いています。
またアドレスに変換する所では謎の(+ ... 25)がありますが、これが下駄を履かせている部分です。

(mapcar #'fast-inv-sqrt 
        '(100.0 10.0 1.0 0.1 0.01 0.0025))
→ (0.09984488 0.31568578 0.99830717 3.157232 9.982522 19.965044)

一応、同じ結果となりましたが、float全部で正しいかは分かりません。

ポータブル版

binary32形式のビット列を整数として取り出すライブラリは何点かあるようですが、Pascal Bourguignon(PJB)氏のcom.informatimago.common-lisp.data-encodingを利用してみます。
PJB氏のプロダクトは、あいかわらずパッケージ名が長いので、下記ではuse-packageしています。

(ql:quickload :com.informatimago.common-lisp.data-encoding)

(use-package :com.informatimago.common-lisp.data-encoding.ieee-754)

(defun fast-inv-sqrt (x)
  (let* ((i (float-32-to-ieee-754 x))
         (y (ieee-754-to-float-32 (- #x5f3759df (ash i -1)))))
    (* y (- 1.5f0 (* 0.5f0 x y y)))))

(mapcar #'fast-inv-sqrt 
        '(100.0 10.0 1.0 0.1 0.01 0.0025))
→ (0.09984488 0.31568578 0.99830717 3.157232 9.982522 19.965044)

このライブラリでは、変換するのにinteger-decode-floatを使っています。
具体的な方法はソースを眺めてみてください。
他、同種のライブラリであるieee-floatsは、decode-floatを利用しているようです。

速度について

integer-decode-floatを利用するのが一番まっとうに思えますが、どの方法も速度的には大体同じようなので、まっとうなinteger-decode-floatを利用する方法が良さそうです。

まとめ

floatのビットの並び(binary32)をintとして利用する趣旨からすれば、アドレスに埋め込まれたbinary32を取り出すのが一番近いような気もしますが、アドレスとLispオブジェクトを相互変換する手段があるかどうかは処理系の中身を探ってみても良く分からないことが多いです。
今回、SBCLでは、それらしき方法が見付かりましたが、LispWorksでは、オブジェクトからアドレスは拾えても、アドレスからオブジェクトを拾う方法は分からず、でした。

とはいえ処理系内部を探検するのもたまには面白いと思うので、好みの処理系がfloatをどう処理しているのか覗いてみては如何でしょうか。


HTML generated by 3bmd in LispWorks 7.0.0

Common Lispの埋め込みPrologを試してみる: takベンチ篇

Posted 2016-08-10 15:50:11 GMT

前回は、Zebraパズルをお題に各種埋め込みPrologがどんなものかを試してみましたが、今回は、たらいまわしの竹内関数で有名なtakです。
どうしてtakかというとAZ-Prologのベンチにあったので、AZ-Prologと比較するには都合が良いという理由です。

Takとは

正式な竹内関数はtakとは微妙に違いますが、Lispのベンチで有名なGabrielベンチで広まってしまったのは、マッカーシー先生の憶え違いのtakの方でした。
以来ベンチではこちらが良く使われます。

比較する埋め込みPrologについて

今回も比較する埋め込みPrologは、

  • Allegro Prolog
  • PAIPROLOG
  • Uranus

です。

ベンチ

  • CL処理系: Allegro CL 8.2 Linux 64bit版
  • CPU: Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz
  • メモリ32GiB

AZ-Prolog

  • タイム: 1.050 sec

今回は、AZ-Prologを基準にしてみたいと思うので、まずAZ-Prologからですが、 takを100回繰り返しています。
takの引数は、tak(18,12,6)です。iが付いていますがintegerのiでしょうか。

※interpreterのiでした。やたらcallが付いているのはそのためだったんですね。
callなしのtakもベンチにあったのを見逃していましたので、追記し、AZ-Prologとの比較表もtakを基準としたものに修正します。

tak(100) :                   0.140 Sec  0.370 Sec  1.250 Sec

最速のCへの変換版で0.140です。

参考インタプリタ版:

---Module Name(Iterate)----   C-Code     ByteCode   Interpreter
-----------------------------+----------+----------+-----------
itak(100) :                   1.050 Sec  1.310 Sec  1.500 Sec

Uranus

  • タイム: 26.5536 sec

(define tak
        ((*x *y *z *a)
         (<= *x *y)
         (cut)
         (= *z *a))
        ((*x *y *z *a)
         (1- *x *x1)
         (tak *x1 *y *z *a1)
         (1- *y *y1)
         (tak *y1 *z *x *a2)
         (1- *z *z1)
         (tak *z1 *x *y *a3)
         (tak *a1 *a2 *a3 *a)))

Uranusですが、上記のような定義です。

(dotimes (i 100)
  (result '(tak 18 12 6 *ans)))
;=> nil
#|------------------------------------------------------------|
; cpu time (non-gc) 22.020000 sec user, 0.000000 sec system
; cpu time (gc)     4.530000 sec user, 0.000000 sec system
; cpu time (total)  26.550000 sec user, 0.000000 sec system
; real time  26.553695 sec
; space allocation:
;  354,620,051 cons cells, 2,900,592,192 other bytes, 0 static bytes
; x86_64
 |------------------------------------------------------------|#

Allegro Prolog

  • タイム: N/A

(<-- (tak ?x ?y ?z ?a)
     (lispp* (<= ?x ?y)) !
     (= ?z ?a))
(<-  (tak ?x ?y ?z ?a)
     (is ?x1 (1- ?x))
     (tak ?x1 ?y ?z ?a1) 
     (is ?y1 (1- ?y))
     (tak ?y1 ?z ?x ?a2)
     (is ?z1 (1- ?z))
     (tak ?z1 ?x ?y ?a3) 
     (tak ?a1 ?a2 ?a3 ?a))

こんな感じに直訳で書きましたが、スタックオーバーフローで完走できません。
Prologのスタックを伸ばす方法もありますが、ちょっと伸ばしてもLisp処理系のスタックオーバーフローになってしまいます。コンパイルしてみても駄目。

PAIProlog

  • タイム: N/A

Allegro Prologと同じ定義ですが、同じくスタックオーバーフロー

Allegro Prolog で Lisp側のtakを呼ぶ

  • タイム: 0.050 sec

なんとなく姑息な気がしますが、takみたいなものは、すべからくLisp側で定義すべし、ということなのかもしれないので、そういう定義を書いてみました。

(defun tak (x y z)
  (if (<= x y)
      z
      (tak (tak (1- x) y z)
           (tak (1- y) z x)
           (tak (1- z) x y))))

(<-- (tak ?x ?y ?z ?a) (is ?a (tak ?x ?y ?z)))

(dotimes (i 100) (prolog (tak 18 12 6 ?a) (lisp (return-from prolog ?a)))) ;=> nil #|------------------------------------------------------------| ; cpu time (non-gc) 0.050000 sec user, 0.000000 sec system ; cpu time (gc) 0.000000 sec user, 0.000000 sec system ; cpu time (total) 0.050000 sec user, 0.000000 sec system ; real time 0.043480 sec ; space allocation: ; 100 cons cells, 412,800 other bytes, 0 static bytes ; x86_64 |------------------------------------------------------------|#

今度は、飛び抜けて速いですね。

PAIProlog で Lisp側のtakを呼ぶ

  • タイム: 0.140 sec

Allegro Prologと同じですが、ユーティリティ述語が少ない分、若干違っています。

(<-- (tak ?x ?y ?z ?a)
     (lisp ?a (tak ?x ?y ?z)))

(dotimes (i 100) (let (ans) (prolog (tak 18 12 6 ?a) (lisp (setf ans ?a))) ans)) ;=> nil #|------------------------------------------------------------| ; cpu time (non-gc) 0.140000 sec user, 0.000000 sec system ; cpu time (gc) 0.000000 sec user, 0.000000 sec system ; cpu time (total) 0.140000 sec user, 0.000000 sec system ; real time 0.139851 sec ; space allocation: ; 397,000 cons cells, 17,860,000 other bytes, 0 static bytes x86_64 |------------------------------------------------------------|#

Allegro Prologより若干遅い位です。
といってもtakの速さは同じですが。

Uranus で Lisp側のtakを呼ぶ

  • タイム: 0.054 sec

(dotimes (i 100)
  (result '(tak 18 12 6 *ans)))
;=> nil
#|------------------------------------------------------------|
; cpu time (non-gc) 0.050000 sec user, 0.000000 sec system
; cpu time (gc)     0.000000 sec user, 0.000000 sec system
; cpu time (total)  0.050000 sec user, 0.000000 sec system
; real time  0.054857 sec
; space allocation:
;  1,900 cons cells, 0 other bytes, 0 static bytes
; x86_64
 |------------------------------------------------------------|#

Uranusは、Lisp側で関数を定義してやれば、それに引数が増えた形式で、Uranus側から呼べるので、特に追加の定義は必要ありません。

順位とタイム

順位 処理系 タイム(秒) AZ-Prolog比
1 Allegro Prolog←Lisp 0.050 1/2.8
2 Uranus←Lisp 0.054 1/2.6
3 PAIProlog←Lisp 0.140 1
3 AZ-Prolog 0.140 1
5 SWI-Prolog 0.781 5.5
6 Uranus 26.5536 189
7 Allegro Prolog N/A N/A
8 PAIProlog N/A N/A

まとめ

埋め込み処理系は、それ自体、独立したものとは考えず、Prologが得意とするもの以外はLisp側に投げる、という使い方が吉なのでしょうか。
単体のProlog処理系であれば、Cを呼び出したりしそうなので、Lisp⇔Prologの行き来がシームレスで高速であれば、それで良いのかなあ、という気がしないでもないです。

しかし、Prologからコードを移植したりする場合を考えると、とりあえず愚直に書き直したものが動いてくれると嬉しいですねえ。


HTML generated by 3bmd in LispWorks 7.0.0

Common Lispの埋め込みPrologを試してみる: Zebraベンチ篇

Posted 2016-08-06 07:26:42 GMT

古くからLispで実装されたPrologは多いようです。
処理系として独立しているものからLisp内に埋め込まれたものまで色々あるようですが、Common Lispの埋め込みPrologってどんな感じかなと思い適当にベンチでも取ってみることにしました。

ベンチのお題ですが、Allegro Prologの解説ページにZebra Puzzleを解くという定番ベンチのコードが載っていたので、これで比べてみます。

Zebraパズルとは

Zebraパズルは、Wikipediaの解説ページに詳しいですが、提示される15の条件から、「水を飲んでいる人」と「シマウマの所有者」を推理するものです。

比較する埋め込みPrologについて

今回比較する埋め込みPrologは、

  • Allegro Prolog
  • PAIPROLOG
  • Uranus

です。

Allegro PrologはAllegro CL 8.2に付属のものですが、元はNorvig先生のPAIPにあるProlog処理系がベースです。
ユーティリティを追加しつつ、かなり最適化しているとのこと。

PAIPROLOGは、PAIPのPrologをまとめたもので、(ql:quickload :paiprolog)で導入できます。

Uranusは、中島秀之先生の知識表現向け言語で、多重世界機構等でPrologを大幅に拡張した言語ですが、S式Prologの仲間でLisp Machine Lispで実装されています。
埋め込みの処理系というよりは単体の処理系ですが、Lispマシン上での利用は、埋め込みProlog的な利用がされていたようで、そのためのインターフェイスもあります。
CMUのAIリポジトリで配布されていますが、ANSI CLでも動くように調整してみました。

なお、まだまだ調整が足りていません。

ベンチ

Allegro Prologのページでは、Zebraを1000回ループした時間を測定していますので、これを基準に計測してみました。

  • 処理系: Allegro CL 8.2 Linux 64bit版
  • CPU: Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz
  • メモリ32GiB

Allegro Prolog

  • タイム: 0.852126 sec

; cpu time (non-gc) 0.850000 sec user, 0.000000 sec system
; cpu time (gc)     0.000000 sec user, 0.000000 sec system
; cpu time (total)  0.850000 sec user, 0.000000 sec system
; real time  0.852126 sec
; space allocation:
;  0 cons cells, 0 other bytes, 0 static bytes

0 cons cellsとは一体。
聞き知るところでは、Allegro Prologの担当者はSteve M. Haflich(smh)氏とのことです。

PAIProlog

  • タイム: 11.712953 sec

; cpu time (non-gc) 11.400000 sec user, 0.000000 sec system
; cpu time (gc)     0.320000 sec user, 0.000000 sec system
; cpu time (total)  11.720000 sec user, 0.000000 sec system
; real time  11.712953 sec
; space allocation:
;  48,220,135 cons cells, 1,920,202,272 other bytes, 0 static bytes

memberが定義されていないので、

(<-- (member ?item (?item . ?)))
(<-  (member ?item (? . ?rest)) (member ?item ?rest))

として定義した他はAllegro Prologと同じです。

Uranus

  • タイム: 51.080032 sec

; cpu time (non-gc) 50.810000 sec user, 0.000000 sec system
; cpu time (gc)     0.270000 sec user, 0.000000 sec system
; cpu time (total)  51.080000 sec user, 0.000000 sec system
; real time  51.080032 sec
; space allocation:
;  501,877,675 cons cells, 450,448,848 other bytes, 0 static bytes

Uranusは色々と調整していますが、

(define nextto
        ((*x *y *list)
         (iright *x *y *list))
        ((*x *y *list)
         (iright *y *x *list)))

(define iright ((*left *right (*left *right . *rest))) ((*left *right (*x . *rest)) (iright *left *right *rest)))

(define zebra ((*h *w *z) ;; Each house is of the form: ;; (house nationality pet cigarette drink house-color) (= *h ((house norwegian ? ? ? ?) ;1,10 ? (house ? ? ? milk ?) ? ?)) ; 9 (member (house englishman ? ? ? red) *h) ; 2 (member (house spaniard dog ? ? ?) *h) ; 3 (member (house ? ? ? coffee green) *h) ; 4 (member (house ukrainian ? ? tea ?) *h) ; 5 (iright (house ? ? ? ? ivory) ; 6 (house ? ? ? ? green) *h) (member (house ? snails winston ? ?) *h) ; 7 (member (house ? ? kools ? yellow) *h) ; 8 (nextto (house ? ? chesterfield ? ?) ;11 (house ? fox ? ? ?) *h) (nextto (house ? ? kools ? ?) ;12 (house ? horse ? ? ?) *h) (member (house ? ? luckystrike oj ?) *h) ;13 (member (house japanese ? parliaments ? ?) *h) ;14 (nextto (house norwegian ? ? ? ?) ;15 (house ? ? ? ? blue) *h) (member (house *w ? ? water ?) *h) ;Q1 (member (house *z zebra ? ? ?) *h) ;Q2 ))

のようなものをファイルに書いて、

(defun ura-load (file)
  (let ((*package* (find-package :uranus-user))
        (*readtable* (copy-readtable ura:uranus-readtable)))
    (set-macro-character #\? (lambda (s c)
                               (declare (ignore s c))
                               (gensym "*"))
                         T)
    (with-open-file (in file)
      (loop :for xpr := (read in nil in)
            :until (eq xpr in)
            :do (ura:toplevel-execute xpr)))))

で読み込んでいます。
Uranusでは?が匿名変数ですが、マッチの結果が違ってくるので、?をリーダーマクロとしてgensymで一意の変数を生成しています。
ドライバーは、

(defun ura-zebra-benchmark (&optional (n 1000))
  (declare (optimize (speed 3) (safety 0)))
  (let (rt0 rt1)
    (time (loop initially (setf rt0 (get-internal-run-time))
              repeat n do (result '(do (zebra *houses *water-drinker *zebra-owner)
                                       (cut)     ; Stop once answer is found.  
                                                 ; This appears to be
                                                 ; what other implementations do, 
                                                 ; e.g. time/1 in
                                                 ; SWI Prolog.
                                    ))
                finally (setf rt1 (get-internal-run-time))))
    (destructuring-bind (zebra houses water-drinker zebra-owner)
                        (result '(zebra *houses *water-drinker *zebra-owner))
      (declare (ignore zebra))
      (values (/ (* n 12825) (/ (- rt1 rt0) 1000.0)) ; real time 
                                                     ; is milliseconds
              zebra-owner water-drinker houses))))

です。
Prologの世界とLispの世界を行き来するオーバーヘッドが大きそうなので、ループもProlog側で回すようなものも書いて比較してみましたが、ほぼ同じ結果でした。

SWI-Prolog

  • タイム: 1.422 sec

% 12,848,838 inferences, 1.422 CPU in 1.422 seconds (100% CPU, 9035334 Lips)

Allegro Prologのページのコードで計測したものです。

AZ-Prolog

  • タイム: 0.710 sec

---Module Name(Iterate)----   C-Code     ByteCode   Interpreter
-----------------------------+----------+----------+-----------
zebra(1000) :                  0.710 Sec  0.800 Sec  1.530 Sec

AZ-Prologは、「ISO/DEC-10 Prolog」に準拠した、世界最速級の処理性能を誇る論理型言語Prolog処理系とのことなので比較してみました。
商用処理系ですが、無償で個人利用可能です。素晴しい!
AZ-PrologのベンチマークにZebraがあるので1000回繰り返すように調整して計測しました。
C-CodeというのはCにトランスレートしたものを実行した速度のようです。

順位とタイム

順位 処理系 タイム(秒)
1 AZ-Prolog 0.710 1
2 Allegro Prolog 0.852 1.2
3 SWI-Prolog 1.422 2
4 PAIProlog 11.712 16.5
5 Uranus 51.080 71.9

参考までに単体のProlog処理系とも比較してみましたが、世界最速級のAZ-Prologと比べてもAllegro Prologは良い線を行ってそうです。
Allegro Prologの元になったPAIPrologですが、タイムは約13倍になっています。
他のベンチもちょっと試してみたりしていますが、大体10〜40倍位違うようなので、かなりの最適化が施されているようです。

UranusはS式Prologとして構文が良い感じなのと、面白い機構があるので速度とは別に深追いしてみたい所です。

まとめ

このベンチに限っては、ですが、Allegro PrologがメジャーなProlog並の速度が出ているのに驚きです。
とはいえ、Prolog側で繰り返しを書くと簡単にスタックオーバーフローになってしまう等、使い方に工夫が必要そうです(PAIPrologも同じく)
今後、別のベンチの結果も書いて行こうかなと思っています。

LispWorksにもCommon Prologというものがあり本格的なProlog処理系っぽいのですが、Enterprise Editionでしか利用できないので残念ながら試せていません。
しかし、OPS5をベースにした前向き推論と、Prologベースの後ろ向き推論を組み合わせることが可能で、さらにCommon Lispのクラスとも融合しつつMOPの論理言語版ともいえそうなMRP(Metarule Protocol)というものを持ち、デバッグ機能も充実しているらしいです。

試してみたい!


HTML generated by 3bmd in LispWorks 7.0.0

setqの引数の謎

Posted 2016-07-29 13:03:45 GMT

SNSでsetqは一度に複数の変数を代入できて、引数が奇数個の場合はnilが返る、という説明を目にしました。
コードにすると、

(setq x 1 y)
→ nil

(list x y)(1 nil)

のような動作です。

Common Lispでは奇数個の引数の場合はエラーなので、もしやEmacs Lispのことかと思って確認してみましたが、どうもEmacs Lispではそのようです(最近のバージョンでは成立しない:詳細は後述)

この仕様はなかなか面白いので、Emacsを含む他のMACLISP系Lispではどうなっているのか確認してみました。

MACLISP

本家MACLISPです。

  • 0引数 → エラー
  • 1引数 → エラー

MACLISPで育ったrmsの設計したelispなので、実はMACLISPから引き継いだ仕様だろうと思っていましたが、意外にも0、1共にエラーとなりました。

(setq)

;((SETQ)) ODD NUMBER OF ARGS - SETQ ;BKPT WRNG-NO-ARGS (setq x)

;((SETQ X)) ODD NUMBER OF ARGS - SETQ (setq x 42) 42

Common Lisp

  • 0引数 → nil
  • 1引数 → エラー

です。

Franz Lisp

Franz Lispも、Common Lispと同じく

  • 0引数 → nil
  • 1引数 → エラー

でした。

-> (setq)
nil
-> (setq x)
Error: odd number of args to setq

Lisp Machine Lisp

CADR System 78.48では、

(setq)
NIL
(setq x)
NIL
x
NIL

のように、

  • 0引数 → nil
  • 1引数 → nil

となりました。
しかし、System 99では、

  • 0引数 → nil
  • 1引数 → エラー

のようです。ソースを確認してみましたが、古いバージョンでは、

(DEFUN SETQ (&QUOTE &REST SYMBOLS-AND-VALUES)
  (PROG (VAL)
   L    (COND ((NULL SYMBOLS-AND-VALUES) (RETURN VAL)))
        (SET (CAR SYMBOLS-AND-VALUES) (SETQ VAL (EVAL (CADR SYMBOLS-AND-VALUES))))
        (SETQ SYMBOLS-AND-VALUES (CDDR SYMBOLS-AND-VALUES))
        (GO L)))

のようになっています。
このコードを眺めた限りでは、値を省略した場合に値がnilとなるのは、『nilcadrnilだから』のようで、どうも偶々に見えます。
後にエラーにされるのでバグだったと言っても良いかなと思います。

Emacs Lisp

Emacs 25.0.50では、

  • 0引数 → nil
  • 1引数 → nil

Emacs 25.1.50では、

  • 0引数 → nil
  • 1引数 → エラー

となりました。

どうやら最近この動作は修正されてしまったようです。

ソースを確認してみると、値を省略した場合にnilとなるのは、Lisp Machine Lispと同じく、nilcadrnilだからのようで偶発的なもののようです。

Arc

この仕様で思い出したのがArcですが、Arcの場合は意図的な仕様です。

(set x)
→ t

x → t

しかし、setより良く使われる=は、setの上位互換の筈ですが、

  • 0引数 → nil
  • 1引数 → nil

となっています。
1引数の場合にtが代入されないのは何故かな思い追い掛けてみましたが、どうもマクロ展開時のパタンマッチで、偶々nilが入ってしまっているようにも思えます。
具体的なコードにすると、

((fn ((a b)) (list a b)) '(0))(0 nil)

的な動作の結果ですが、nilcadrnilの遠縁とも言えそうです。

まとめ

どうでも良いところを掘り下げてみましたが、最近elispの仕様が変更になったらしい、ということが判明したりで面白いなと思いました。

もしかすると、『可変長引数でかつ、ペアで処理しなくてはいけない場合に奇数個の場合の対処を忘れる』という典型的なバグ(もしくはミスフィーチャー)なのかもしれません。


HTML generated by 3bmd in LispWorks 7.0.0

実用Common LISP を読んだ

Posted 2016-07-25 15:37:50 GMT

実用Common LISPという本は実は2種類あるのですが、PAIPの翻訳ではなく、1987年に発行された 衣笠成一著の方です。

jitsuyo-cl

以前から一度読んでみたいなと思っていましたが、Amazonのマーケットプレイスで1500円位だったので購入してみました。

本の内容について

1987年という時代を反映してか、まず最初に人工知能について軽い解説があります。
後は、Common Lisp(1984)の標準関数についての解説が、機能ごとに章立てされ、そこそこ網羅的に記述されています。

解説は、どこかのマニュアルを書き写したようなものではなく、著者の言葉で解説されているという感じで、なかなか分かり易かったりもしますが、ちょっと間違った解説も散見され若干残念です。

例えば、stable-sortの解説等ですが、

;; stable-sortはコピーを作ってソーティングする.sortより安全性がある.

(stable-sort (copy-list '((1 2) (5 9) (3 2) (8 1)))
             #'>
             :key #'cadr)
==> ((5 9) (1 2) (3 2) (8 1)) 

となっていたりします。

コード例は、安定ソートを説明するためのものに見えるので、マニュアルを解釈する際の著者の勘違いでしょうか。

この本の面白いところ

非常にどうでも良い所ではありますが、個人的に興味を惹かれたのは、コードの出力例に利用されている処理系が、HPのCommon Lispである、HP Common Lispであることです。
HPのCommon Lispは、最初は、Portable Standard Lisp(PSL)をCommon Lispに仕立てた独自のものでしたが、後にLucid CLのOEM版処理系に置き換わります。

この本で利用されているのは、どうもPSLベースの処理系のようなので、この辺りがとてもレア。 とはいえ、それ以上のことは何もありません……。

まとめ

なかなか小気味良くまとまった本でしたが、こういうコンパクトな感じでANSI Common Lisp解説書があったら良いのになと思いました。

当然ではありますが、この本はCommon Lisp(1984)仕様の本ですし、2016年の今Common Lispの参考書として利用するような本ではありません。

とはいえCommon Lispマニアの方にも、それ程面白味もなさそうです。


HTML generated by 3bmd in LispWorks 7.0.0

Common Lispと猫

Posted 2016-07-03 14:01:43 GMT

ANSI Common Lispの規格書には猫が登場します。 登場する場所は、22.3.7.2 Tilde Left-Bracket: Conditional Expression

で、format指示子の~[の箇所です。

"~[Siamese~;Manx~;Persian~:;Alley~] Cat"

のようなコード例中に登場しますが、

(dotimes (i 5)
  (format T "~&i = ~D — ~[Siamese~;Manx~;Persian~:;Alley~] Cat~%" i i))
⊳ i = 0 — Siamese Cat
⊳ i = 1 — Manx Cat
⊳ i = 2 — Persian Cat
⊳ i = 3 — Alley Cat
⊳ i = 4 — Alley Cat
→ nil 

のような機能になります。

登場する猫の種類は、

  • シャム(サイアミーズ)
    siames
  • マンクス
    manx
  • ペルシャ(パージャン)
    persian
  • 野良
    alley

です。野良(雑種)も勘定して全4種。

この解説は、CLtL2でも見たことがあるなと思ってCLtL2を確認してみましたが、CLtL2にもそのままありました。

更に遡ってCLtL1を確認しましたが、CLtL1でもそのままでした。

もしやCLtL1では、Lispマシンのマニュアル(所謂Chinual)のformatの内容を再利用していたりしないかなと思いChinualを確認してみたところ、22.4.1 The Format Function(エラーで見れない)に記載がありました。

こちらは、

"~[Siamese ~;Manx ~;Persian ~;Tortoise-Shell~;Tiger ~;Yu-Shiang ~]kitty"

"~[Siamese ~;Manx ~;Persian ~;Tiger ~;Yu-Shiang ~:;Bad ~] kitty"

という風になっていて、シャム、マンクス、ペルシャは同じですが、

  • サビ(柄)子猫
    tortoise-shell
  • 虎(柄?)子猫
  • Yu-Shiangの子猫
  • 悪い子猫

が増えています。
Yu-ShiangはMITハッカー御用達の中華料理店だと思いますが、そこに猫でもいたのでしょうか。

Chinualに関しては、1979年あたりの第2版には既に登場しているようなので、formatがドキュメント化されたのと同時に登場したのかもしれません。

まとめ

特に意味もなくCommon Lisp(Lisp Machine Lisp)の仕様書に登場する猫を追い掛けてみました。
~[は猫を連想して暗記するのも良いかもしれません。

他に猫が登場する箇所があったら教えてください。


HTML generated by 3bmd in LispWorks 7.0.0

ANSI Common Lispの規格書(に近いもの)のPDFを入手する

Posted 2016-06-30 17:58:13 GMT

ANSI Common Lispの規格書を入手となれば当然ANSIが出しているので、ANSIから入手することになります。
現在PDFで$60のようなので約6,000円でしょうか。

しかし、このPDFは、紙媒体をスキャンした画像をPDFとしていて、検索もできないし電子媒体としては出来がひどいことで知られています。

さて、では、お馴染のLispWorksのHyperSpecや、FranzのFranz online ANS for Common Lispはどこから電子データを持ってきているのかというと、ANSIに持ち込む前のドラフトを元にしています。

HyperSpecの方はどの時点のものかは不明ですが、Franzの方は、dpANS2を元にしているという解説ページがあります。

このページにはdpANSが3つあると解説されていますが、この3つのdpANSは、CMUのAIリポジトリ等入手可能です。

今回は、このうちdpANS3RからPDFを作成してみます。

dpANS3RからPDFを作成する

用意するもの

  • dpans3のdviファイル
  • DVI→PDF変換ツール(dvipdf)
  • PDF結合ツール(pdftk)

まず、上記CMUのサイトからdpans3r.tgzとdpans3.tgzをダウンロードします。

$ wget http://www.cs.cmu.edu/afs/cs/Web/Groups/AI/lang/lisp/doc/standard/ansi/dpans/dpans3.tgz
$ wget http://www.cs.cmu.edu/afs/cs/Web/Groups/AI/lang/lisp/doc/standard/ansi/dpans/dpans3r.tgz

あとは展開して、DVIファイルをPDFに変換し、結合するだけです。

$ tar xvf dpans3.tgz
$ tar xvf dpans3r.tgz
$ mv dpANS3R/* dpANS3/
$ cd dpANS3
$ gunzip *.dvi.Z
$ for f in chap-*.dvi;do dvipdf $f;done
$ pdftk chap-0.pdf chap-1.pdf chap-2.pdf chap-3.pdf chap-4.pdf \
chap-5.pdf chap-6.pdf chap-7.pdf chap-8.pdf chap-9.pdf chap-10.pdf \
chap-11.pdf chap-12.pdf chap-13.pdf chap-14.pdf chap-15.pdf \
chap-16.pdf chap-17.pdf chap-18.pdf chap-19.pdf chap-20.pdf \
chap-21.pdf chap-22.pdf chap-23.pdf chap-24.pdf chap-25.pdf \
chap-26.pdf chap-a.pdf cat output dpANS3-15.17.pdf

以上の操作で、電子データとして中身の検索も可能な、dpANS3-15.17.pdfが生成されます。

なお、手元のANSI INCITS 226-1994(R2004)のPDFのページ数を確認すると表紙も含めて全体で1153ページですが、dpANS3では1360ページあります。
上述のCL Untold Storyによると、縦方向のスペースを調整した結果200ページも圧縮されたらしいです。

まとめ

ANSI規格の著作権は、ANSIが所有することになるようです。
規格をまとめたコミュニティ側としては、パブリックドメインにしたかったようですが、この辺りの経緯はCommon Lisp: The Untold Story - nhplace.comで語られています。

dpANSがリファレンスとして加工されて利用されるのにはこんな経緯がありますが、dpANSのTeXについては、Kent Pitman氏の見解によれば、派生、再配布、自由とのことです。


HTML generated by 3bmd in LispWorks 7.0.0

LispWorks IDE起動時のツールを指定する

Posted 2016-06-25 13:55:41 GMT

問題:

起動時のデフォルトだとGCモニターとリスナーが起動してくるがこれを変更したい

解決策:

lispworks-tools::*default-tools* で指定する

デフォルトだと、lispworks-tools::*default-tools*は、(lispworks-tools:lispworks-echo-podium lispworks-tools:listener)ですが、これを変更することで起動時のツールを変更できます。

設定は、~/.lispworks 等で可能です。

;;; ~/.lispworks
(setq lispworks-tools::*default-tools* '(lispworks-tools:editor))

仕組み

デフォルトのツールは、lispworks-tools:start-lispworksで起動しますが、起動時のツールは、:tools引数で指定することになっていて、初期値は、lispworks-tools::*default-tools* になっています。

lispworks-tools::*default-tools*の初期値は、(lispworks-tools:lispworks-echo-podium lispworks-tools:listener)です

所感

マニュアルに記載がないようですが、これは書いてて欲しい……。

  • env:start-environment
  • method-function env-internals:environment-start env::capi-environment

disassembleして眺めて、lispworks-tools:start-lispworksに辿り着き、lispworks-tools::*default-tools*変数を見付けました。


HTML generated by 3bmd in LispWorks 7.0.0

GNU Emacs の ledit-mode の謎

Posted 2016-06-22 15:15:10 GMT

EmacsにはLisp編集支援モードのledit-modeというものがかなり古くから標準で同梱されています。
しかし、このledit-modeですが実際に使っているという人や、利用方法の紹介などのブログ記事もこの十数年で見掛けたことは一度もありません。
ledit-modeのソースを眺めてみると分かりますが、現在では使い方も良く分からない代物となっています。

leditといえば、MACLISPをEmacsから利用する環境の名前でもあるのですが、ソース上のキーバインドから類推するに、どうもそれをGNU Emacs + Franz Lispで実現したもののように思えます。

以前、Franz LispをSIMH上のUltrix 4.0上で動かしてみたりしましたが、最近rshでのファイル転送も上手く行くようになったので、VAX Ultrix用にビルドされたEmacsとFranz Lispでこのledit-modeがどのように機能するのか試してみることにしました。

VAX UltrixのEmacsを用意する

世界にはVAX UltrixでGNU Emacs 21.4.1をビルドして配布している酔狂な方がいらっしゃるので、ありがたく使わせて頂きます。

/freeware以下に展開するのが前提のようなので、/freewareディレクトリを作成して展開します。

leditの設定

Emacs側だけでなく、Franz Lisp側でもledit.lleditcfns.o というファイルが必要になります。
(以前はGNU Emacsに添付されてきていたようですが、現在は添付されていないようです。)
leditcfns.cがあるディレクトリで、make leditcfnsすれば、leditcfns.oができますので任意のディレクトリに配置します。
Franz Lispの標準のライブラリのディレクトリは、/usr/lib/lispのようなので、下記では、ここに設置することにします。

次に、設置場所に応じてledit.lleditcfns.oの読み込み場所を書き換えます(標準のパスであればファイル名のみで良いようです)

(cfasl "leditcfns.o" '_switch_to_proc 'emacs)

後は

$ liszt ledit

で、ledit.oを生成することができるので、これをまたライブラリパスに置いておきます。

ledit の操作

MACLISPのleditと同じく、Emacsとlisp処理系を行ったり来たりするのにUNIXのジョブコントロールを利用するようです。
Emacsをサスペンドさせ、処理系を起動し、処理系をサスペンドし、Emacsを起動し……というのを交互に繰り返します。
Emacsからは、Franz Lispのインタプリタのlispと、コンパイラのlisztに移行することが可能です。

利用に際して、lisplistz、をバックグラウンドとして起動してemacsを起動します。

なお、Emacs側のコマンドは下記の通りです。

  • ledit-save-defun (c-m-d)
  • ledit-save-region (c-m-r)
  • ledit-go-to-lisp (c-x z)
  • ledit-go-to-liszt (c-m-c)

試しに下記のようなファイルの場合、

(load 'flavors)
(load 'describe)

(defflavor foo (x y z) () :initable-instance-variables :settable-instance-variables :gettable-instance-variables)

(setq foo (make-instance 'foo ':x 0 ':y 1 ':z 2))

(describe foo)

Emacsのバッファ上で、c-x h c-m-r c-x z すると、lisp に切り替わって、

%?lisp

[3]+ Stopped emacs bash$ %?lisp lisp ;Reading from LEDIT: [load /usr/lib/lisp/flavors.l] [fasl /usr/lib/lisp/vanilla.o] ; t ; foo ; fclosure[6] fclosure[6], an object of flavor foo, has instance variable values: x: 0 y: 1 z: 2

; fclosure[6] t ->

というような結果になります。
ここからemacsに復帰するには、c-eの後に改行を入力します。

まとめ

Emacsのledit-modeを実際にFranz Lispとの組み合わせで動かしてみました。
最新のEmacs 25でもledit-modeは(require 'ledit)で利用することが可能なようですが、

  • ターミナルで動かすことが前提
  • 最新のGNU EmacsとFranz Lispが同時に動く環境は存在しない
  • Franz Lisp側のコードが添付されてこない

等の理由で、実質機能しないライブラリとなっています。
削除してしまっても困る人はいないと思われますが、恐らくledit-modeが何物なのか不明なので削除して良いのかも判断できず、そのまま生き残っているのではないでしょうか。
一体いつまでGNU Emacsに添付され続けるのかこれからも見守り続けたいと思いますが、Franz Lispを最新の環境で動くようにすれば、このライブラリは生き返ることになりますし、Franz Lispを最新の環境でビルドできるようにする酔狂な人の登場も期待しています。


HTML generated by 3bmd in LispWorks 7.0.0

Older entries (2009 remaining)