#:g1

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)))としています。
他には高階関数で末尾呼び出しの最適化が効かないことがあるようなので、苦肉の策でインライン展開しています。マクロを使うか書き直しをしても良いですが、インラインで済むならそっちの方が楽かなというところ。

まとめ

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

ちょっとしたパズル: ACM SIGPLAN Lisp Pointers Volume 1 Issue 6 にのっていた問題

Posted 2013-02-26 14:53:59 GMT

標準関数名の意図的なシャドウ

(define (foo cons)
  (lambda (x y)
    (if (= x 1)
        ...
        (cons x y))))

のようなものを

(defun foo (cons))
  (lambda (x y)
    (if (= x 1)
        ...
        (cons x y))))

と翻訳

(funcall (foo #'bar) 1 2)

として、

(1 2)

のようなものが出力されて悩む


HTML generated by 3bmd in LispWorks 7.0.0

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

Posted 2013-02-19 19:58:00 GMT

 先月に続いて月一ペースで開催される予定のLisp Meet Up presented by Shibuya.lispの二回目。
今回はSchemeをフィーチャーした回ということでしたが、会場が始まってSchemeメインの人の数を数えたところ0/13でした。Common Lispの人は4、5人いたので、もうちょっとSchemerが参加しても良かったかなとも思いました。

(1)発表: Common Lispでの日本語プログラミング - chikuさん

 chikuさんによる、Common Lispで『なでしこ』のような日本語プログラミングを、という発表。題からしてCLの日本語周りのまとめかと思っていましたが、リーダーマクロ等を駆使して日本語として読めるような構文でプログラムを書く、という内容でした

(2)発表: 日本語プログラミングとLISP - g000001

 発表というよりプロジェクターを使って私@g000001が適当にデモしただけですが、#:g1: 日本語プログラミングとLISPから、谷川俊太郎の『おとこのマーチ』ネタをデモってみました。
コードにバグがあり、公開デバッグという感じになってしまいましたが、ブログの方が良く纏まっているのでブログを参照してくださいw

(3)発表: CLMLでTwitter発言分析 - masatoiさん

 @masatoi0さんによるTwitterのTLをgithub: mathematical-systems / clmlで機械学習させ、発言がポジティブなものかネガティブなものかを判定するというデモ。UIは、ブラウザを利用し、ウェブのフレームワークとしてWeblocksを利用ということで、純Common Lispな構成。
まだ制作途中とのことでしたが、ビジュアル的にも内容的にもShibuya.lispのテクニカル・トークで発表されたら面白いだろうなと思う内容でした。

Schemeの話

 今回はSchemeの回ということで、Schemeネタを捻り出していました。

  • SRFIネタ
    • → なぜかCommon Lispでデモしました。
  • Schemeで関数を返す関数を多用した場合のデバッグのしづらさと、コンパイル時型チェックの効用について
    • → これもCommon Lispの立場から、いちゃもんを付けていました。CLも五十歩百歩ではという声も。
  • 衛生マクロは何が嬉しいんですか?
    • → 手動でgensymしなくて良いとか、パタンマッチとか…
  • Schemeは静的な方向に向ってるって話だけど、本当なのか
    • → R6RS→R7RSの流れは逆行してるように見えるが…。答えられる人おらず

その他雑談etc

  • arc-compatのデモをしてみました - g000001
    • → 『(』の再定義について若干のやりすぎ感による苦笑
  • Common Lispで、Tを変数名に使いたい
    • → 使えば良いんじゃないの。shadowするとか、|t|とか…
  • Common LispでTCOが効いてるか効いてないかどうやって判定すれば良いでしょう
    • → 結局disassembleして読むしかないのでは?

まとめ

 雰囲気も良く、楽しいmeetupでした。Schemerは何名か参加予定だったと思いますが、残念ながら都合が合わなかったみたいで、ちょっと残念でした。次回は、Clojureの回みたいですが、場合によってはArcでも、Common Lispでも、Schemeでもなんでも良いのではないかなと思ったりもしました。

CMU AIレポジトリ探検: Type Simplifier: A simple type simplifier

Posted 2013-02-02 00:48:00 GMT

Type Simplifier: A simple type simplifierとは何か

 Common Lispには型の指示子があり、色々の合成ができたりしますが、これを簡素化するもののようです。

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

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

使ってみる

(in-package :ai.lang.lisp.code.ext.types)

(simplify-type '(and cl:simple-string cl:vector)) ;=> SIMPLE-STRING

(simplify-type '(or cl:simple-string cl:string)) ;=> STRING

(simplify-type '(and cl:simple-string cl:string (cl:string 8))) ;=> (AND SIMPLE-STRING (STRING 8))

まとめ

 もともとは、大昔のAllegro CLのcoerceのバグの対処として作られたもののようですが、型指定が込み入ってきたときに、無駄な指定が入ってないかどうか等を確認するためのツールとして使ってみるのも良いのではないでしょうか。

CMU AIレポジトリ探検: Library of miscellaneous small extensions to Common Lisp

Posted 2013-01-25 12:46:00 GMT

Library of miscellaneous small extensions to Common Lispとは何か

 名前の通り、便利ユーティリティをまとめてみたもののようで、Common Lispには良くあるユーティリティ集といったところです。

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

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

使ってみる

 中身は割合に混沌としていますが、面白いものを幾つか紹介

progfoo
(progfoo (list 1 2 3 4)
  (pop foo)
  (pop foo))
;=>  (3 4)
;; マクロ展開
(LET ((FOO (LIST 1 2 3 4)))
  (POP FOO)
  (POP FOO)
  FOO)
Gaucheのrlet、Rubyのtap的なものですが、加えて一番最初の引数をfooという変数で参照できるアナフォリックなマクロです。
自分もfooではなく、itにしたものをatap(Anaphoric Tap)として使ってみたりしていましたが、全く同じアイデアが1991年には既に存在していたんですね。
with-rhyme
(with-rhyme (cl:delete 2 '(1 2 3)))
no rhyme or reasonという言い回しがあるようですが、reasonまでは行かないが、rhyme位ならということでしょうか。全く何もしないマクロで、気になるところに目印として使うためのマクロということみたいです。with-fixmeでも良さそう。
noting-progress
(noting-progress ()
  (dotimes (i 100)
    (note-progress)))
;>>  ......................................................................
;>>  ..............................
;=>  NIL
note-progressと、note-progressの対で使いますが、進行状況を点々で出力させるためのもの。noting-progressの引数で何個目で改行するかが指定できます。

まとめ

 quicklispにも俺ユーティリティは沢山ありますが、眺めると色々の個性やアイデアが面白いですね。

Older entries (1552 remaining)