#:g1: frontpage

 

Multics MACLISPとEmacsを動かす

Posted 2016-09-18 18:14:57 GMT

TwitterのSDFのつぶやきでMulticsが動くようなことが書いてあり、どうもエミュレータで動かしているようなので、Multicsのエミュレータをググってみました。
すると、Multics WikiというページにDPS8MでMulticsを動かすことができるようなことが書いてあるので、Multics Wiki: Getting Startedを参考にMulticsを起動してみました。
起動は非常に簡単で、これで歴史的に有名なMulticsが起動できるとはびっくりです。

Multics MACLISPとMultics Emacs

Multics MACLISP

さて、Multicsといえば、Multics MACLISPとMultics Emacsです。
Multics Emacsは、MACLISPで実装されているのでEmacsが動くということはMACLISPも……、と思えます。
しかし、件のWikiページの利用可能な言語一覧には載ってはおらず、エミュレータが用意したイメージには含まれていないのかと思いましたが、駄目元で、

lisp

コマンドを実行した所、MACLISPではお馴染の*のプロンプトが現れました!
(PDP-10系のMACLISPは*が表示されるのはユーザーがそういう風に設定しているからなのですが、Multics MACLISPではデフォルトの設定がそうなのかもしれません。)

Multics MACLISPと、本家PDP-10 MACLISPの違いは、そこそこあるのですが、Multics MACLISPは、入力を大文字に畳み込まないのがデフォルトだったりします。

(eq 'Foo 'foo)
=> nil

また、Multics MACLISPのコンパイラは、lcpもしくは、lisp_compilerコマンドを実行します。
インタプリタとコンパイラがコマンドで分かれているのは、PDP-10 MACLISP、Franz Lispあたりもそういう構成になっているので当時はこの方式がメジャーだったようです。

Multics Emacs

Emacsの歴史の中でも良く触れられるものの、実物を触ったことがある人はかなり限られそうなMultics Emacsですが、こちらもemacsコマンドで起動できます。
起動は、TECO Emacsと同様、さっくりと起動して来ます。

Lispの編集モードですが、ファイル名が.lispで終わるファイルを開くと自動で適用されます。
手動で適用したい場合には、M-x lisp-modeです。

手前の式を評価するのは、C-M-z、関数のコンパイルは、C-M-cです。
コンパイルは、ファイルに書き出して、lcpでコンパイルしてロードするようです(Lispモードのソース参照のこと)。

Multics Emacsでは、M-xはevalquoteと同じになっている

Multics Emacsについては、井田昌之先生がbitの「Emacs 解剖学 (4)— Multics Emacs — 」で解説されたことがありますが、このなかで私が以前から気になっていたことに、「Multics Emacsでは、M-xはevalquoteと同じになっている」という説明があります。

なんとなく動作は想像できてはいましたが、実際に、

(defun hello (x)
       (minibuffer-print (catenate "Hello, " x "!")))

のような関数を定義して、

M-x hello g000001

と入力すると、

     Command: hello g000001<>
     Hello, g000001!

と出力されます。
Evalquoteというと、hello(g000001)でも入力可能なのかと思い試してみましたが、これは不可でした。引数はクォートされているようなのでEvalquoteといえば、そうなのかもしれません。
これで疑問が一つ解消されました。

LDEBUG モード

上記のようにEmacsの拡張用言語として密に連携するMACLISPですが、Lispモード以外に対話的開発環境のLDEBUGモードがあります。

LDEBUGは、MITが公開しているMulticsのソースで存在は知ってはいたのですが、実際どういうものなのかは想像する他ありませんでした。

M-x ldebugで起動できますが、GNU Emacsでいうところの*scratch*バッファのような感じで、式の後ろでC-mすると結果が=>付きで挿入されます。

(defun fib (n)
        (cond ((< n 2) n)
             (t (+ (fib (1- n))
                   (fib (- n 2))))))

(fib 10.) => 67

(+ 3 3) => 6

Emacs 12.9 (Lisp Debug) - fib >user_dir_dir>SysAdmin>Repair>fib.lisp Select buffer (fib): <>

コマンドについては、LDEBUGモードのキーバインドの定義のソースを見ると分かるのですが、

(defun ldebug-mode ()
       (lisp-mode)
       (dont-notice-modified-buffer current-buffer)
       (mapc '(lambda (x)(set-key (car x)(cadr x)))
       '((^M        ldebug-eval-and-print-result)
         (esc-G     ldebug-return-to-emacs-top-level)
         (esc-P     ldebug-return)
         (esc-L ldebug-list-breaks)
         (esc-R ldebug-reset-break)
         (esc-S ldebug-show-bkpt-source)
         (esc-T ldebug-trace-stack)
         (esc-^S    ldebug-display-where-editor-was)))
       (setq current-buffer-mode  'Lisp/ Debug)
       (if ldebug-mode-hook
     (errset (funcall ldebug-mode-hook))))

バックトレースの表示、ブレイクポイントの設定/一覧表示/ソースへのジャンプ等ができて、PDP-10系のMACLISP & Emacs連携のLEDITよりもずっと便利です。

試しに画面を分割して、ソースとLDEBUGを並べてみましたが、試しながら書いていくスタイルでは非常に便利だなと思いました。

(defun fib (n)
        (cond ((< n 2) n)
             (t (+ (fib (1- n))
                   (fib (- n 2))))))

-------------------------------------------------------------------------------

(fib 10.) => 67

Emacs 12.9 (Lisp Debug) - LDEBUG *

まとめ

伝説のMultics MACLISPとMultics Emacsを試してみました。
どちらもまさに伝説だったのですが、実際に触れる環境を作ってくれた方々には感謝感謝です。
今後また何か面白いことが発見できたらこのブログに書いていきたい思っています。


HTML generated by 3bmd in LispWorks 7.0.0

Common Lispで抽象クラス

Posted 2016-09-11 18:50:34 GMT

暇潰しにQITAB - a collection of free Lisp codeのソースを眺めていた所、MOPで抽象クラスを実現したコードをみつけました。
githubに切り出されたりしていないのと短いのとで全掲します(ユーティリティは除く)。

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                                                                  ;;;
;;; Free Software under the MIT license.                             ;;;
;;;                                                                  ;;;
;;; Copyright (c) 2008 ITA Software, Inc.  All rights reserved.      ;;;
;;;                                                                  ;;;
;;; Original author: Dan Weinreb                                     ;;;
;;;                                                                  ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;; Utilities that make use of the meta-object protocol. ;;; Abstract classes are classes that must never be ;;; instantiated. They are only used as superclasses. ;;; In general, they perform two useful function: ;;; First, they can be used to define a "protocol", ;;; namely a set of generic functions that some ;;; group of classes should implement. ;;; Second, they can provide some utility methods ;;; that any of the subclasses is free to take ;;; advantage of, so that the subclasses can share ;;; code in a modular way. ;;; This implementation was provided to us by MOPmeister ;;; Pascal Costanza, of the Vrije Universiteit Brussel, ;;; Programming Technology Lab. (define-condition instantiate-abstract (error) ((class-name :type symbol :initarg :class-name :reader instantiate-abstract-class-name)) (:documentation "There was an attempt to instantiate an abstract class") (:report (lambda (c stream) (format stream "There was an attempt to make an instance of abstract class ~S" (instantiate-abstract-class-name c)))))

(defclass abstract-class (standard-class) () (:documentation "This is a metaclass. Any class that has this as its metaclass is an abstract class. An attempt to instantiate an abstract class signals a INSTANTIATE-ABSTRACT condition."))

;;; Why are the validate methods here? In general, two metaclasses are not semantically compatible with ;;; each other. For example, one metaclass may ensure that slot values are only given to the outside ;;; world in encrypted form, for security reasons, and another metaclass may want to add automatic ;;; logging whenever slot values are changed. Combining them means that either one or the other ;;; metaclass functionality is violated. There is no general way to resolve such problems. ;;; Validate-superclass is a way to announce which metaclasses are compatible with each other. Here we ;;; announce that abstract classes can have standard classes as direct superclasses, and vice versa. (defmethod closer-mop:validate-superclass ((class abstract-class) (superclass standard-class)) t)

(defmethod closer-mop:validate-superclass ((class standard-class) (superclass abstract-class)) t)

(defvar *outside-abstract-class* nil)

(defmethod allocate-instance ((class abstract-class) &key &allow-other-keys) (unless *outside-abstract-class* (error 'instantiate-abstract :class-name (class-name class))))

(defmethod closer-mop:class-prototype :around ((class abstract-class)) (let ((*outside-abstract-class* t)) (call-next-method)))

元は、Pascal Costanza氏のコードらしいのですが、元コードは探しても見付けられませんでした。

とりあえず、面白い所は、allocate-instanceをエラー出すものに挿し替えてしまい、class-prototypeから呼ぶ時はエラーにならないようにする、という所でしょうか。
何故こういう構成になっているのかさっぱり分からなかったので調べてみました。

MOPで抽象クラスを実現する方法

まず、MOPで抽象クラスを実現する方法ですが、抽象クラスのインスタンス生成しようとした場合にエラーにすることが多いようです。

make-instance に細工をする方法

現在、Quicklispで導入できるTim Bradshaw氏のabstract-classesでは、abstract-classというメタクラスを作って、それに、make-instanceを設定し、make-instanceが実行されたらエラーという感じです。

;;; 導入方法
(ql:quickload :abstract-classes)

この仕組みは、Gaucheで書いてみるとシンプルで分かり易いのですが、

(define-class <abstract-class> (<class>) ())

(define-method make ((class <abstract-class>) :rest initargs) (error "There was an attempt to make an instance of abstract class" class))

という感じです。

(define-class <foo> ()
  ()
  :metaclass <abstract-class>)

(make <foo>) ⊳ *** ERROR: There was an attempt to make an instance of abstract class #<class <foo>>

のように、<abstract-class>メタクラスでは、エラーになりますが、メタクラスが<abstract-class>でなければ、エラーになりませんので、mixinすれば使えます。

(define-class <bar> (<foo>)
  ()
  :metaclass <class>)

(make <bar>) → #<<bar> 0x2797b30>

以上の仕組みで、抽象クラスのインスタンス生成を防いでいるわけですが、なんとなく安直な気もしてしまいます。

しかし、これでOKかと思いきや、Common Lispの場合は、make-instanceせずにクラス変数を取得するのにclass-prototypeが利用されているようで、make-instanceを潰す方法では、抽象クラスのクラス変数が取得できてしまうようです(なお、Gaucheにはclass-prototypeはないようなので、この心配はなさそうです)

別の言い方をすれば、プロトタイプとしてインスタンスが一つ生成されてしまっている、ということです。

(defclass foo ()
  ((c :initform 42 :allocation :class))
  ;;上述のQuicklispで導入できるabstract-classes
  (:metaclass abstract-classes:abstract-class)) 

(finalize-inheritance (find-class 'foo)) → nil

(slot-value (class-prototype (find-class 'foo)) 'c) → 42

ちなみに議論は、comp.lang.lispをclass-prototypeで検索すると色々出てきます。

class-prototype に細工をする方法

ということで、冒頭のコードのclass-prototypeに細工をする方法になるわけですが、恐らく、クラス変数が取得できる云々というよりは、一番最初にallocate-instanceが呼ばれる場所であるからなのでしょう。

MCSの場合

そういえば、MCSは、抽象クラスの定義構文を持っていた、と思い出したので、MCSではどうなっているか眺めてみましたが、instantiableクラスとabstractクラスに分かれた構成になっていて、allocate-instance/class-prototypeは、instantiableクラスにしか定義されていないので、No applicable methodsエラーになります。
さすが最初から組込まれているだけあってすっきりしていますね。

まとめ

Common LispのMOPはなかなか全貌を捕えることが難しい印象ですが、なんといっても参考にできる資料が少ないと思います。
MOPのレシピ集が欲しい……。


HTML generated by 3bmd in LispWorks 7.0.0

LispのFIXNUM、BIGNUM、INTEGERとRuby

Posted 2016-09-10 14:24:46 GMT

RubyとFixnum/Bignum

Ruby 2.4からFixnum/Bignumクラスが統合されて、Integerクラスになるそうですが、 Fixnum/Bignumに分かれていたのは実装の詳細をユーザーに見せることになるので良くないデザインだった、とのことらしいです。

まあ、それはそれで良いのですが、この件について調べてみていると、Fixnumは、Bignumは、Lispを意識しすぎて導入してしまった失敗例としてMatz氏が説明しているのを目にしました。

まあ、Rubyのデザインの失敗なので、それはそれで良いのですが、失敗の文脈でFIXNUM/BIGNUMを説明されると、Lispのデザインの悪い所を真似ちゃった、的な解釈をされちゃうことが多い気がしたので、そんなことはないよ、という主張を書いてみることにしました。

ユーザーのコーディング作法とFIXNUM/BIGNUM

Rubyのユーザーの作法は知らないのですが、とりあえず、Lispでは、1970年あたりの古くからBIGNUMが導入されたこともあり「多倍長整数といえばLisp」という感じなので、入門書などでは、FIXNUMやBIGNUMの使い分けを励行するようなことはありません。
勝手に切り替わってくれて、オーバーフローを考える必要もなく便利だね、という説明が多いです。

また、Common Lispには、integerpはありますが、FIXNUMかどうかをユーザーが調べる関数は標準規格では用意していません。

MACLISPでも、Common Lispでも基本はintegerで考え、FIXNUMやBIGNUMを意識するのはパフォーマンスチューニングが必要になった場合のみ、が基本です。

また、FIXNUMを利用する時は、処理系依存動作を承知の上で利用するものというコンセンサスもありますし、そもそも仕様と実装がきっちり分かれていて、処理系が多数あるLisp系言語では、処理系依存というものを扱う意識をはっきり持つようになります。

以上をまとめると、Lisp村の通念では「Lispでは通常、多倍長整数がサポートされていて便利だが、高速に処理したい場合のことも考慮されている仕様がある」位の所であり、「Lispの整数にはFIXNUMとBIGNUMがあるけど、とりあえずFIXNUMで書いちゃったら、そのプログラムが処理系によっては妙な動作をする」ような通念ではないのです。

FIXNUMとBIGNUMの歴史を眺めてみる

話はまったく変わりますが、そもそもFIXNUMやBIGNUMという用語は、どういった経緯で導入されたのかの歴史もついでに調べてみました。

1966年頃: FIXNUM と FLONUM が導入される

MACLISP(当時はPDP-6 LISP)にfixnumとflonumというものが導入されたのは、資料で確認できる限りでは、1966年6月以降のようです。

AI Memo 98 — PDP-6 LISP / Peter Samson

...

FIXNUM Indicator for fixed-point number.

FLONUM Indicator for floting-point number.

...

FIXとFLOは小数点が固定(FIX)か浮動するかを表わしていたようで、今でいうintegerと、floatになるかと思います。
ちなみに、LISP 1.5の頃から数値はfixed-point numberと、floting-point numberという分けられ方をしています。
小数点にフォーカスした語句表現ですが、FIXNUMは、固定小数点数というわけではありません。

現在、FIXNUMというと、ビット表現がマシンアーキテクチャの1ワードに収まる範囲の整数(単精度整数)という感じなので、1ワードに固定される的な表現なのかと思いきや、小数点のことだったようです。

ちなみに、現在、FIXNUMは、Common Lispに残っていますが、FLONUMという表現は無くなりFLOATになっています。
FLONUMという表現はSchemeに残っていますが、個人的にこの辺りは、SchemeがMIT系Lispだなと感じるところです。

1970年頃: BIGNUM 登場

The Evolution of Lispによると、BIGNUMは、1970-1971年辺りにMACLISPで実装されていた数式処理システムのMACSYMAのために導入されたようです。

BIGNUMは、1ワードに表現が収まらない数のことですが、1ワードの範囲から溢れた場合には自動で切り替わります。

ということで、本来BIGNUMは、1ワードに収まらないFIXNUMだったと思いますが、BIGNUM導入後、FIXNUMに単精度整数という意味が出てきたのではないでしょうか。

MACLISPでは、integerpに相当するものはfixpですが、BIGNUM導入後も、ずっとそのままであった辺りにその痕跡が残っているように思えます。(後にfixnumpが導入されます。)

1984年頃: Common Lisp

MACLISPの後継のCommon Lispでは、integerタイプが導入され、FIXNUMと、BIGNUMはそのサブタイプとして整理されました。
なお、それぞれ範囲は処理系依存ですが、FIXNUMは、(signed-byte 16)の範囲以上であることは保証されます。

ANSI Common Lispでは、クラスが導入され、integerはクラスの意味も持つようになりましたが、FIXNUM、BIGNUMはクラスではありません(処理系拡張でクラスになっている処理系もある)

まとめ

Rubyの話にかこつけて結局Lispの歴史話になりました。
とりあえず、ユーザーがコンパイル〜最適化を意識するMACLISP〜Common Lispで、integerがFIXNUM/BIGNUMに分かれているのは妥当なデザインかと思いますが、性質の違うRubyに取って付けたのが、失敗だったんじゃないかなと思います。

追記

Twitterで、本文まとめの

ユーザーがコンパイル〜最適化を意識するMACLISP〜Common Lispで、integerがFIXNUM/BIGNUMに分かれているのは妥当なデザインかと思いますが、性質の違うRubyに取って付けた

という表現の「性質の違うRuby」という意味がまったく分からんというご指摘があったので、補足します(一応このブログにもコメント欄があるのですが……)

Common Lispの「性質」

  • コンパイル指向(ユーザーが明示的にコンパイルすることが多い)※もちろんインタプリタも可ではあります。
  • 型指定はしなくても良く、安全だが遅いコードというのが基本。
    しかし、ユーザーが希望とあれば、それを明示的に指定させることで、速いが危険なコードを生成することが可能。

fixnumの使われ方

fixnumは上述のようなコンパイルの時に最適化の型指定として使われます。

bignumへの切り替わりのオーバーヘッドを見越して、fixnumの範囲しか使わないことをコンパイラに指定することで余計なチェックコード(ディスパッチのコスト)を切り捨てることによって高速化を図ります。

ですので、

(defun foo (n)
  (declare (fixnum n))
  ...)

(the fixnum n)

は妥当でも、(fixnump x) や、 (typep x 'fixnum) 等の実行時チェックは余り出てこないのです。 (チェックを省いたコンパイル済み関数に数値を渡す前のチェックとして書かれることはあると思います)

Rubyの「性質」

  • コンパイル指向ではない(と思いますが)
  • 型指定はしなくても良い。 Fixnum/Bignumのようなものの型の使い分けを意識したプログラミングをしても高速化のような御利益ははっきりしない

Fixnumの使われ方

自分はあまり詳しくはありませんが、ユーザーが、

1.class
=> Fixnum

というのをみてFixnumってなんだろう?と思う程度には利用価値が少ない(謎のジャーゴン)らしいです。

追記のまとめ

Common Lispでは、実行時にディスパッチされるものとして、fixnum/bignumは指定しません。
この場合はintegerを使います(もちろん常に例外はあるものですが)

コンパイル時の最適化には使いますので、謎の歴史的遺物でもないです。 (手動による型指定など古臭いのではないか、等々はまた別の話としてください)

Rubyは実行時にディスパッチするのでしょうから、もとからIntegerだけで良かったのでは、と思ってしまいます。

Ruby誕生のずっと前の1984年から、Common Lispは、integerのサブタイプとしてfixnum/bignumという構成です。
使われ方も上述のようなもので変化はありません。

Lispの影響でFixnum/Bignumを取り入れたそうですが、どんな効果を期待して導入されたのかちょっと興味はありますね。


HTML generated by 3bmd in LispWorks 7.0.0

リーダーマクロでシンボルの略記をする

Posted 2016-09-04 11:43:43 GMT

David Moon氏が1974年に書いたエディタのソースコードにリーダーマクロの面白い使い方があったのをふと思い出しました。
コードはMACLISPですが、

(setsyntax '/~ 'macro '(lambda nil (implode (cons '+ (nconc (exploden (read)) '(+))))))

(defun ~car nil (or (atom it) ;if done car'ing, stop and return t (progn (setq ~stack (cons (cons it 'car) ~stack)) (setq it (car it)) nil)))

のようなものです。

Common Lispにすると、

(set-macro-character #\~ (lambda (strm char)
                           (declare (ignore char))
                           (intern (concatenate 'string
                                                "+"
                                                (string (read strm T nil T))
                                                "+"))))

という所でしょうか。

これで

(defun ~fib (n)
  (if (< n 2)
      n
      (+ (~fib (1- n))
         (~fib (- n 2)))))

と書いたものは、

(defun +fib+ (n)
  (if (< n 2)
      n
      (+ (+fib+ (1- n))
         (+fib+ (- n 2)))))

のように展開されます。

プログラムが内部で利用するシンボル名が他のシンボル名とバッティングしないようにしたものだと思いますが、あまりこういう例はないと思いますし面白いです。

応用

長いパッケージ名を省略して記述する

何か応用できないか考えてみましたが、長いパッケージ名を省略して記述するのに使ったらどうなるか試してみました。

(make-package :abcdefghijklmnopqrstuvwxyz :use '())

(defvar *a-package* (find-package :abcdefghijklmnopqrstuvwxyz)) (defparameter *a-prefix* :demo-) (defparameter *a-postfix* :-demo)

(set-macro-character #\~ (lambda (strm char) (declare (ignore char)) (intern (concatenate 'string (string *a-prefix*) (string (read strm T nil T)) (string *a-postfix*)) *a-package*)))

(defun ~fib (n) (if (< n 2) n (+ (~fib (1- n)) (~fib (- n 2))))) ===> (defun abcdefghijklmnopqrstuvwxyz::demo-fib-demo (n) (if (< n 2) n (+ (abcdefghijklmnopqrstuvwxyz::demo-fib-demo (1- n)) (abcdefghijklmnopqrstuvwxyz::demo-fib-demo (- n 2)))))

パッケージに加え接頭辞、接尾辞も付けられます。
まあ工夫すれば何かに使えるかもしれないです。

ファイルローカルなUninterned Symbolを記述するのに使う

〈ファイルローカルなUninterned Symbol〉ってなんだという感じですが、Uninterned Symbolは、読み取りの度に異なったシンボルになるので、同じ名前なら同じシンボルが返ってくる記法を実現しようというアイデアです。

(defvar *obtab* (make-hash-table :test #'equal))

(defun intern-file-local (sym-or-string) (or (gethash (string sym-or-string) *obtab*) (setf (gethash (string sym-or-string) *obtab*) (make-symbol (typecase sym-or-string (STRING sym-or-string) (SYMBOL (string sym-or-string)))))))

(set-macro-character #\_ (lambda (strm char) (declare (ignore char)) (intern-file-local (read strm T nil T))) T)

これで、

(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))))

のようなものは、

(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は全て同じシンボルであることがミソです。
また、ファイルローカルといっていますが、コードをみて分かるように、別にファイルローカルではありません。
*readtableの変わり目としてファイルが一つの単位とすることが多いので、そんな感じの名前にしてみました。

クラスのスロット名で使うと、単に#:fooと記述したのと違ってchange-classでのスロットの保持ができるなと思いました(まあ、あまり活用できなそうですが)

(defclass foo ()
  ((_x :initform 0)
   (_y :initform 1)
   (_z :initform 2)))

(defclass bar () ((z :initform 0) (_x :initform 20) (y :initform 0)))

(describe (change-class (make-instance 'bar) 'foo)) ⊳ #<foo 40200CDEDB> is a foo ⊳ x 20 ⊳ y 1 ⊳ z 2

まとめ

リーダーマクロでシンボルの略記ですが、使い方によっては便利な気がします。

  • あるパッケージのグループに属するシンボルを共通の接頭辞で記述する
  • 階層パッケージの真似事

等々も実現できるでしょう。

何か活用できそうなものを発見したら、またエントリーを書いてみたいと思います。


HTML generated by 3bmd in LispWorks 7.0.0

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

Older entries (2013 remaining)