#:g1

GCL 2.9.10がgmp対応になった結果

Posted 2013-11-16 00:15:00 GMT

 桁数が大きい計算でかなり速くなったンゴw
新しいgclならMaximaあたりでパフォーマンスがかなり向上するのかも

計測に利用したスクリプト


#+sbcl (ignore-errors (require :sb-gmp))

(in-package :cl-user)

(defun ^^ (base power) (declare (optimize (debug 0) (safety 0) (speed 3)) (fixnum base power)) (loop :repeat power :for x :of-type bignum := (expt base base) :then (expt x base) :finally (return x)))

(compile '^^)

(time (= (^^ 10 6) (^^ 10 6))) (time (progn (^^ 10 6) nil)) (time (progn (^^ 10 6) nil)) (time (progn (^^ 10 6) nil)) (time (progn (^^ 10 6) nil)) (time (progn (^^ 10 6) nil))

(quit)

(time (progn (^^ 10 6) nil))を抜き出した結果

GNU Common Lisp 2.9.10: 0.029s
real time       :      0.029 secs
run-gbc time    :      0.019 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
NIL
ManKai Common Lisp 1.1.6: 0.046
real time : 0.046 secs
run time  : 0.045 secs
gc count  : 0 times
consed    : 1108304 bytes
NIL
SBCL 1.1.13 w/GMP: 0.068
Evaluation took:
  0.068 seconds of real time
  0.068004 seconds of total run time (0.068004 user, 0.000000 system)
  100.00% CPU
  163,051,965 processor cycles
  1,147,424 bytes consed

NIL

Scieneer Common Lisp 1.3.9: 1.359s
Evaluation took:
  1.359979 seconds of real time
  1.3459656 seconds of thread run time
  1.3459662 seconds of process run time
  1.348084 seconds of user run time
  0.0 seconds of system run time
  0 page faults
  5,118,784 bytes consed by this thread and
  5,118,784 total bytes consed.
NIL
Clozure CL 1.9: 4.528s
took 4,566,268 microseconds (4.566268 seconds) to run.
         2,446 microseconds (0.002446 seconds, 0.05%) of which was spent in GC.
During that period, and with 2 available CPU cores,
     4,528,283 microseconds (4.528283 seconds) were spent in user mode
         4,000 microseconds (0.004000 seconds) were spent in system mode
 1,107,808 bytes of memory allocated.
 129 minor page faults, 0 major page faults, 0 swaps.
NIL
CMU Common Lisp 20d: 7.040s
; Evaluation took:
;   7.04 seconds of real time
;   6.956434 seconds of user run time
;   0.028002 seconds of system run time
;   16,869,095,640 CPU cycles
;   [Run times include 0.01 seconds GC run time]
;   0 page faults and
;   5,653,128 bytes consed.
; 
NIL
LispWorks 6.1.1 Personal Edition: 43.434s
Timing the evaluation of (PROGN (^^ 10 6) NIL)

User time = 43.434 System time = 0.040 Elapsed time = 43.772 Allocation = 2472668 bytes 0 Page faults

Allegro CL Enterprise Edition 8.2 64-bit /
Allegro CL Free Express Edition 9.0
Error: Attempt to create an integer which is too large to represent.

Sagittarius 0.4.5 install memo

Posted 2013-05-17 12:59:00 GMT

 Sagittarius 0.4.5 has been released. So I tried it out right away.

OS: Debian GNU/Linux sid x86_64
$ wget http://sagittarius-scheme.googlecode.com/files/sagittarius-0.4.5.tar.gz
$ tar xvf sagittarius-0.4.5.tar.gz
$ cd sagittarius-0.4.5/
$ cmake .
$ make
$ make test
$ make doc
$ make install
Documentation:
Sagittarius Users' Reference
(import (rnrs) (clos user))

(define-method fib ((n (eql 0))) 0)

(define-method fib ((n (eql 1))) 1)

(define-method fib ((n <integer>)) (+ (fib (- n 1)) (fib (- n 2))))

(fib 30) ;=> 832040

 This version of Sagittarius has builtin support for 'eql specializer'.

srfi 112 on Common Lisp

Posted 2013-05-06 04:37:00 GMT

 The new srfi (112: Environment Inquiry) proposal become draft. So I ported it to Common Lisp right away.

 新しいsrfiの提案(112: Environment Inquiry)がドラフトになったので早速CLに移植。

Examples | 実行例

(implementation-name)
;=>  "SBCL"

(implementation-version) ;=> "1.1.7" (cpu-architecture) ;=> "X86-64" (c-memory-model) ;=> NIL (system-instance) ;=> "setq" (os-type) ;=> "Linux" (os-version) ;=> "3.2.0-4-amd64"

About porting | 移植について

 srfi 112 procedures are mostly based on Common Lisp. So just make aliases.

 CLの関数に相当するものを念頭に置いているようなので、エイリアスを作っただけです。

L-99 live coding demo on LispWorks

Posted 2013-05-01 22:49:00 GMT

 About 4 years ago, I had made a live coding demo which tries to solve L-99 on LispWorks. I'm posting this entry, just now, to be remembered.

 4年程前にLispWorks上で、L-99を解く風景のデモを作成していたのを思い出したので掘り出してみました。

  • L-99: Ninety-Nine Lisp Problems
  • srfi 111 on Common Lisp

    Posted 2013-04-26 14:27:00 GMT

     The new srfi (111: Boxes) proposal become draft. so I ported it to Common Lisp right away.

     新しいsrfiの提案(111: Boxes)がドラフトになったので早速CLに移植。(ちなみにこれからは英語風の俺言語と日本語を併記していくことにしました。)

    Examples | 実行例

    (in-readtable :srfi-111)

    (let ((b (box 0))) (set-box! b 42) (= 42 (unbox b))) ;=> T

    (let ((b #&0)) ;Lexical syntax (set-box! b 42) (= 42 (unbox b))) ;=> T

    (box? #&#&42) ;Lexical syntax ;=> T

    (box? (box (box 42))) ;=> T

    (unbox (box 42)) ;=> 42

    (unbox #&42) ;Lexical syntax ;=> 42

    About porting | 移植について

     It's just a copy and paste programming!

     コピペです!

    Sagittarius 0.4.4 install memo

    Posted 2013-04-19 16:40:00 GMT

     Sagittarius 0.4.4 has been released. so I tried it out right away.

    OS: Ubuntu Linux 12.10 x86_64
    $ wget http://sagittarius-scheme.googlecode.com/files/sagittarius-0.4.4.tar.gz
    $ tar xvf sagittarius-0.4.4.tar.gz
    $ cd sagittarius-0.4.4/
    $ cmake .
    $ make
    $ make test
    $ make doc
    $ make install
    Documentation:
    Sagittarius Users' Reference
    (import (time))

    (define (^^ base power) (let loop ((ntimes (- power 1)) (x (expt base base))) (if (zero? ntimes) x (loop (- ntimes 1) (expt x base)))))

    (time (begin (^^ 10 6) #f))

    ;; (begin (^^ 10 6) #f) ;; 1.723382 real 1.716108 user 0.000000 sys #f

    
    (defun ^^ (base power)
      (loop :repeat power
            :for x := (expt base base) :then (expt x base)
            :finally (return x)))

    (progn (^^ 10 6) nil) ;⇒ NIL #|------------------------------------------------------------| Evaluation took: 3.388 seconds of real time 3.428214 seconds of total run time (3.428214 user, 0.000000 system) 101.18% CPU 8,111,056,437 processor cycles 1,207,360 bytes consed

    Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz |------------------------------------------------------------|#

     Wow!, Sagitarius's expt is now faster than SBCL's!

    Lisp Meet Up presented by Shibuya.lisp #3 に参加してきました

    Posted 2013-03-27 19:04:00 GMT

     月一ペースで開催されいるLisp Meet Up presented by Shibuya.lispも今回が三回目。
    今回はClojureをフィーチャーした回でしたが、告知が早かったためか20人を越える人が集まったようです。

    ustream中継/録画

     今回、@naoya_tさんから提供して頂いたカメラを持参しました。自分も、早く会場に到着して調整する時間を確保できれば良かったですが、ぎりぎりのぶっつけ本番でクオリティが低くなってしまい申し訳なかったです。
    まあ、音声はそこそこ聞き取れるので、スライドと合せて眺めれば雰囲気位は伝わるかと…。

    (1)発表: Datomicについて - hozumi さん

     最近注目されている、Clojure作者のHickey氏によるdatomicの解説。既存のデータベースとどう違うのか、どの辺りが画期的なのかを中心に解説されていました。クエリーは、DatalogというS式Prologライクな言語で処理するようです。
    Datalogの採用に関しては、FranzのAllegro CL + Allegro Prolog的だねという話も出ました。(FranzのAllegroCacheやAllegroGraphではクエリー言語にAllegro Prologが使えます)

    (2)発表: Lispを作りながらClojureの言語機能 - @halcat0x15a さん

     Clojureでlisp処理系を作成するというお題で、Clojureの解説。Clojureらしい機能の説明が多く面白かったです。

    その他雑談etc

    Hickey氏のThe Value of Valuesという講演は素晴らしので見た方が良い -hozumiさん
    Keynote: The Value of Values
    Arcのifについて
    「素晴らしい」vs「素晴らしくない」
    素晴しい:
    括弧が少なくてシンプル
    pg曰く、「これを発見した時に震えた」
    素晴らしくない:
    実際のコードでは字下げしたりして見易くしている、つまりぶっちゃけ読み難い
    Clojureのcondについて
    「素晴らしい」vs「素晴らしくない」
    次回のお題はどうするか
    やっぱりArcの回か。Arcも含めて俺Lisp、俺Schemeの回なら発表者が集まるのでは。
    会場でDatalogを切っ掛けに、Prolog系の論理プログラミングの話が盛り上ったので、この流れでhalcat0x15aさんがcore.logicの話を発表。

    (3)発表: core.logic について - @halcat0x15a さん

     直近のCOMFRKに掲載された「Lispでも論理プログラミングがしたい!」の話を下敷きにしたものだそうです。残念ながらUst機材を撤収した後だったのでUstはされず。core.logicで論理プログラミングの特徴を解説、という感じでした。

    まとめ

     今回も雰囲気も良く、楽しいmeetupでした。次回は、会場が渋谷になるとのことです。テーマはまだ決まっていないようですが、処理系実装者の集まりでも楽しそうですね。

    GLS作のIBM 1130 LISP 1.6 を動かしてみる

    Posted 2013-03-25 22:33:00 GMT

    IBM 1130 LISP 1.6

     レトロコンピューティングなメーリングリストを眺めていたのですが、IBM 1130は比較的廉価だったこともあり、当時の人々には随分と愛されたマシンのようです。どんなマシンだったのかなと思ってググってみると、ibm1130.orgという愛好者のためのサイトがあったりして、人気の程が窺い知れます。
    このサイトのニュースを眺めてみると、lisp 1.6が動くようになったというものがあったので、どんなものかと眺めてみたところ、なんと高校生時代のGuy L. Steele, Jr.(GLS)が作ったものが公開されている様子。
    早速ダウンロードして試してみました。

    IBM 1130の準備

    Ubuntu 12.10 64bitでの場合、そのままビルドすると
    sim_timer.c:(.text+0x72): `clock_getres' に対する定義されていない参照です
    のようなエラーとなるのでmakefileを修正して、-lrtを付けます。
    #
    # Build the emulator
    #

    ${BIN}ibm1130 : ${ibm1130} ${SIM} ${ibm1130_INC} ${SIM_INC} ${CC} ${ibm1130} ${SIM} -o $@ -lrt

    IBM 1130 LISP 1.6の準備

    LISP処理系の方は特に準備は必要なく、一式セットで配布されているので、readmeの通りに実行してみます。

    バッチ実行の場合

    
    // job
    // xeq lisp
    (setqq fib (lambda (n)
                  (cond
                     ((lessp n 2) n)
                     (T (plus (fib (sub1 n))
                              (fib (diff n 2)))))))
    (fib 20)
    (quit)
    
    のような、fib.jobを定義したとすると
    $ ibm1130 job fib               

    IBM 1130 simulator V3.8-0 Loaded DMS V2M12 cold start card

    Wait, IAR: 0000002A (4c80 BSC I ,0028 ) Goodbye

    のように実行します。
    実行すると、fib.lstが書き出されるので、これで結果を確認します。

    fib.lst
    PAGE   1

    // JOB 1234

    LOG DRIVE CART SPEC CART AVAIL PHY DRIVE 0000 1234 1234 0000

    V2 M12 ACTUAL 32K CONFIG 32K

    PAGE 1

    // JOB

    LOG DRIVE CART SPEC CART AVAIL PHY DRIVE 0000 1234 1234 0000

    V2 M12 ACTUAL 32K CONFIG 32K

    // XEQ LISP

    ***** 1130 LISP 1.6 ***** BOSTON LATIN SCHOOL ***** LITHP ITH LITHTENING...

    (SETQQ FIB (LAMBDA (N) (COND ((LESSP N 2) N) (T (PLUS (FIB (SUB1 N)) (FIB (DIFF N 2)))))))

    (LAMBDA (N) (COND ((LESSP N 2) N) (T (PLUS (FIB (SUB1 N)) (FIB (DIFF N 2))))))

    (FIB 20)

    6765

    (QUIT)

    ***** 1130 LISP 1.6 ***** END OF RUN ***** THO LONG, COME AGAIN THOON

    ***** 1130 LISP 1.6 ***** BOSTON LATIN SCHOOL ***** LITHP ITH LITHTENING...
    から
    ***** 1130 LISP 1.6 ***** END OF RUN ***** THO LONG, COME AGAIN THOON
    までの間が実行内容と結果ですが、SをTHに書き換えるくどめのギャグがGLSっぽいです。LISP1.5の実行結果でも、鏡の国のアリスの詩が引用されてたりするので、その辺りを踏襲したのかもしれません。

    対話的実行の場合

    対話的実行の場合は、
    $ ibm1130 job ilisp
    とすれば、対話的に実行できます。

    まとめ

    ソースファイルの日付を見ると、1972/2/14とのことなので、GLSが17歳の時のもののようです。上記のサイトでユーザーズガイドも入手できますが、大分作りこんであったりして、高校生とはいえ流石GLSといったところでしょうか。マニュアルを眺めると随分とMITハッカーテイストなところがあるので、既にMITのAIラボに出入りしていた頃なのかもしれません。

    その他 面白いところ/気になったところ

    • 文字列をサポートしていて、コンマからコンマまでが文字列
      ,FOO, => ,FOO,
    • 出力を文字列として取り出せたり、文字列をREADできたりする(READSTR・PRINCSTR等)
    • C(A|D)*Rというシンボルは、任意のcarとcdrの組み合わせの関数として機能する
    • GLSは、当時からThe Great Quuxらしい
    • 恐らく、Quuxに由来していると思われるが、GENSYMのデフォルトのプレフィックスが、QX
      (GENSYM) => QX000
    • コード例のPROG内のラベルがQ
    • 参考にした処理系として、MacLISPと並んでMultics上で動くNultics lispというのがあるが、実際に存在したものなのか気になる
    他にも色々あるので眺めてみると面白いかと思います。

    CMU AIレポジトリ探検: Series

    Posted 2013-03-05 23:27:00 GMT

    Seriesとは何か

     CLtL2でも紹介されている Richard C. Waters氏作の繰り返し/ストリーム系のライブラリです。quicklispでも、インストールできますが、CMUのAI-REPOSで入手できるものは、1991年のバージョンなので大分違っています。

    ソース:
    http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/iter/series/0.html

     例の如くASDF化してgithubに置いてみました

    ANSI CLへの移植について

     コード生成時に変数の型宣言も生成されるのですが、今どきのSBCLのコンパイラの基準からいうと大分矛盾した型宣言が生成されるので、codify-1を改造してざっくり消してあります。
    この辺りは、defSの中のfragLで定義している元の定義がおかしいのことが多いようなので、ちまちま直していけば良いかなとは思います。

    使ってみる

     quicklispで入手できる最新のseriesと、1991年のseriesで何が違うかというと、最新のseriesではコードのサイズが倍近くに膨れています。この20年で色々付け加えたんだと思いますが、seriesは古くからそれ程変更は無いだろうと考えていただけに意外でした。
    seriesはデバッグしたり読んだりしようにも10,000行近くあるので挑戦する前から心が折れる、という人は自分を含めて結構見ましたが、5,000行弱なら、まあ読めるかもなというところではないでしょうか。また、現行のseriesをマクロ展開すると謎に思えるところは結構あるのですが、どうもこの20年位で加えられたものにも見えますし、オリジナルは比較的シンプルなようです。

    生成されるコードの比較

     上述の様に型宣言がざっくり削られているので1991年のseriesの方が短かくなっていますが、リストの処理が、consしてnreverseから、tconcに変更になっているのが大きめな変更点かと思います。他は最適化の為の型宣言等が若干追加されています。

    
    ;; series 1991
    (collect (subseries (series 'a 'b) 0 2))
    ;===>
    (LET ((INDEX-40323 0) ITEMS-40325 LST-40317 LST-40326 OUT-40327)
      (DECLARE)
      (SETQ OUT-40327 (LIST 'A 'B))
      (SETQ LST-40326 (COPY-LIST OUT-40327))
      (SETQ LST-40326 (NCONC LST-40326 LST-40326))
      (SETQ INDEX-40323 -1)
      (SETQ LST-40317 NIL)
      (TAGBODY
       LL-40330
        (SETQ ITEMS-40325 (CAR LST-40326))
        (SETQ LST-40326 (CDR LST-40326))
        (LET* ((G40332 1) (NEW40331 (+ INDEX-40323 G40332)))
          (SETQ INDEX-40323 NEW40331))
        (IF (NOT (< INDEX-40323 2))
            (GO Z::END))
        (IF (< INDEX-40323 0)
            (GO LL-40330))
        (SETQ LST-40317 (CONS ITEMS-40325 LST-40317))
        (GO LL-40330)
       Z::END)
      (NREVERSE LST-40317))
    
    
    ;; series 2013
    (series:collect (series:subseries (series:series 'a 'b) 0 2))
    ;===>
    (LET* ((OUT-40345 (LIST 'A 'B)))
      (LET (ITEMS-40343
            (LST-40344 (COPY-LIST OUT-40345))
            (INDEX-40341 -1)
            (LASTCONS-40334 (LIST NIL))
            LST-40335)
        (DECLARE (TYPE LIST LST-40344)
                 (TYPE (INTEGER -1) INDEX-40341)
                 (TYPE CONS LASTCONS-40334)
                 (TYPE LIST LST-40335))
        (SETQ LST-40344 (NCONC LST-40344 LST-40344))
        (SETQ LST-40335 LASTCONS-40334)
        (TAGBODY
         LL-40348
          (SETQ ITEMS-40343 (CAR LST-40344))
          (SETQ LST-40344 (CDR LST-40344))
          (LET* ((G40350 1) (NEW40349 (+ INDEX-40341 G40350)))
            (SETQ INDEX-40341 NEW40349))
          (LOCALLY
           (DECLARE (TYPE SERIES::NONNEGATIVE-INTEGER INDEX-40341))
           (IF (>= INDEX-40341 2)
               (GO SERIES::END))
           (IF (< INDEX-40341 0)
               (GO LL-40348)))
          (SETQ LASTCONS-40334
                  (SB-KERNEL:%RPLACD LASTCONS-40334 (CONS ITEMS-40343 NIL)))
          (GO LL-40348)
         SERIES::END)
        (CDR LST-40335)))
    

     その他、defSでの、最適化された場合の展開の指定と、最適化されない場合の関数の組み合わせの定義の方法が違っていたり、ちょこちょこ違っています。
    スタイルとしては、1991年のseriesは、やはり80年代のlisp的で、大域にバンバン定義してしまうという感じなのですが、デバッグしたりコードを読むのには昔の方が楽そうです。

    まとめ

     元々、1991年のseriesに興味があったわけではなく、1991年版をちらっと眺めてみたら、大幅に行数が少ないので、一体何事が起きたのか知りたいと思ったため移植してみました。現行のseriesで謎の挙動に遭遇した場合に、検証に動かしてみるのもアリかなと思ったりはします。コードが倍加している原因は、まだ良く解っていないので、ぼちぼち探ってみたいと思います。

    CLでSRFI-101

    Posted 2013-03-01 11:58:00 GMT

     CLでSRFI、今回は、先日finalになったSRFI-101の「Purely Functional Random-Access Pairs and Lists」です。 Common Lispへの移植は既にVincent Toupsさんが移植していた(VincentToups / random-access-lists)ので、スルーしていましたが、finalなったので移植してみました。とはいうものの基本的にどっちもコピペなのでほぼ同じです。自分の方が参照実装そのまま、という感じでしょうか。

    動作

     ランダムアクセスに向いているのが特長ということなので、通常のリストが苦手とするシャッフルで比較してみました。下記のテストでは、100,000の要素のリストをシャッフルした時間の比較をしています。

    
    (defun shuffle-list (list &aux (len (length list)))
      (mapl (lambda (u)
              (rotatef (first u) (nth (random len) list)))
            list)
      list)

    (defun srfi-101-iota (count &optional (start 0) (step 1)) (declare (fixnum count) (number start step) (optimize (debug 1))) (if (< count 0) (error "Negative step count ~S ~S" 'iota count)) (srfi-5:let *loop ((n 0) (r '())) (if (= n count) (srfi-101:reverse r) (*loop (the fixnum (+ 1 n)) (srfi-101:cons (+ start (* n step)) r)))))

    (defun srfi-101-shuffle-list (rlist) (let ((len (srfi-101:length rlist)) (ans rlist)) (dotimes (idx len ans) (let* ((rand (random len)) (elt1 (srfi-101:list-ref ans idx)) (elt2 (srfi-101:list-ref ans rand))) (setq ans (srfi-101:list-set (srfi-101:list-set ans rand elt1) idx elt2)))) ans))

    (defvar *list* (srfi-1:iota 100000))

    (defvar *srfi-101-list* (srfi-101-iota 100000))

    
    (progn (shuffle-list *list*) nil)
    ;⇒ NIL
    #|------------------------------------------------------------|
    Evaluation took:
      53.659 seconds of real time
      53.475342 seconds of total run time (53.475342 user, 0.000000 system)
      99.66% CPU
      128,458,851,489 processor cycles
      506,672 bytes consed

    Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz |------------------------------------------------------------|#

    (progn (srfi-101-shuffle-list *srfi-101-list*) nil) ;⇒ NIL #|------------------------------------------------------------| Evaluation took: 1.167 seconds of real time 1.124070 seconds of total run time (1.120070 user, 0.004000 system) [ Run times consist of 0.080 seconds GC time, and 1.045 seconds non-GC time. ] 96.32% CPU 2,795,521,374 processor cycles 350,225,424 bytes consed

    Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz |------------------------------------------------------------|#

    構造体で組んでいるのと破壊的更新はないのでコンスは多くなっていますが、速度はsrfi 101のリストの方が45倍位高速のようです。

    移植について

     基本的にコピペですが、末尾呼び出しの最適化が効くように(declare (optimieze (debug 1)))としています。
    他には高階関数で末尾呼び出しの最適化が効かないことがあるようなので、苦肉の策でインライン展開しています。マクロを使うか書き直しをしても良いですが、インラインで済むならそっちの方が楽かなというところ。

    まとめ

     ネイティブなリストに比べればデータの表現でメモリを消費しますが、色々最適化すれば消費も結構押えられるのではないでしょうか。
    純粋関数型言語も増えてきているので非破壊的なリストというのも今後需要が増える気はします。

    Older entries (1556 remaining)