Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2010-11-30

Lemmensさんメモ

| 02:33 | Lemmensさんメモ - わだばLisperになる を含むブックマーク はてなブックマーク - Lemmensさんメモ - わだばLisperになる

昨年の数理システム(MSI)/FranzさんのLispセミナーに引き続き、今年もヨーロッパで活躍されているCommon lisp programmerのArthur Lemmensさんが来日して参加されました。

昨年のセミナーでは、講演者としての講演されていましたが、今年は突如いらした様子。

Lemmensさんは、cl-ppcre等で有名なEdi Weitzさんと一緒に、ヨーロッパLispコミュニティの会合で中心となる役割をされたり、CLのライブラリを書いて公開されたりしています。

なかなか資料が少ない分野でのメモ:

Lemmensさんは、日本語も堪能で、去年のセミナーでは、原稿も日本語で書いてあった程。

今年は、MSI/Franz Lispセミナーだけでなく先日開催されたShibuya.lisp TT#6にも参加して頂けました。

折角の機会なので、quekさんと質問。色々伺いましたが、メモってなかったので結構忘れてしまいました。

  • Q. 日本は何度目でしょうか
    • A. 6回目です
  • Q. 開発で使っている環境は?
    • A. LispWorksのエディタ。最初に本格的に使い始めたのがLispWorksだったというのが理由。クラスブラウザがあったりSLIMEより統合された環境で洗練されていて強力なところが好き
  • Q. メインで使っている言語は?
    • A. Common Lisp。あとは少しMathmatica
  • Q. 開発環境のOSはなにを利用していますか。
    • A. WindowsとLinux。どちらもLispWorksを使っている
  • Q. ライブラリ管理は何を利用していますか?
    • A. ASDFや、ASDF-INSTALLを使ったりもするけれど、自前で管理することが多い。良さそうだけれどquicklispはまだ試してない。
  • Q. テストの環境は何を使っていますか?
    • A. 既存のものを使わないわけではないけれど、プロジェクトに応じて自作している。簡単に作れるものなので。
  • Q. rucksackは更新されないのですか
    • A. 仕事で使うために作ったけれども今は使っていないので…
  • Q. rucksackの開発はどれくらいでしたか?
    • A. 2ヶ月位
  • Q. ヨーロッパで一番LISPが盛んな国はどこでしょうか
    • A. ノルウェーだと思う。ドイツも盛ん。
  • Q. ヨーロッパでLISPが盛り上がってきた(復活してきた)のはいつ頃からですか?
    • A. 大体10年位前から。それ以前は周りをみても見当らない感じだった。
  • Q. 他の言語をdisって退路を断とう、という提案に対して
    • 有名どころでは、Erik Naggumみたいな人もいましたね
  • Q. Erik Naggumの名前の読み
    • A. ナガム(と書いていてナイムだった気もしてきました…)。でも、ノルウェーの人なので正確な発音は分からない。
  • Q. 最初のプログラミング言語は?
    • BASIC
  • A. 最初のLISP処理系は?
    • BBCが出していたPCで動くLisp

機能は限られていたが面白かった

(これでしょうか? File:Acornsoft LISP screenshot (BBC Micro).png - Wikipedia)

  • Q. 現在のお仕事は?
    • A. 今は、3人位の仲間と一緒に建築で使うソフトをCLで作成中。プログラマは一人。会社の名前はまだない。
  • Q. 大規模な人数でのLISP開発について
    • A. ITAで働いてたことがあるけれど、人数が多いと自分の思うようにならず、プログラマ同士が足の踏み合いをしてるような感じだった。個人的には一人の方が自由で好き。
  • Q. 複数人数での開発について:やはりマクロは問題になりますか?
    • A. それなりに危険なこともあるけれども、コードレビューしていれば大丈夫。
  • Q. 次回のECLMの開催時期は?
    • A. いまのところ未定。ILCの開催地がヨーロッパだとイベント的にかぶるので見送りになったりする。そのあたりとの兼ね合いをみつつ開催。

他、思い出したらまた追記します。

2010-11-29

文字列の繰り返し

| 23:34 | 文字列の繰り返し - わだばLisperになる を含むブックマーク はてなブックマーク - 文字列の繰り返し - わだばLisperになる

RubyでもPythonでも、

"a" * 3
#=> 'aaa'

となるのを見て、

"-*" * 3.5

はどうなるのかなあ、と思って試したところ、自分が想像していた

#=> '-*-*-*-' 

みたいなことにはなりませんでした。

ということで折角なので記念に作ってみました。

(defun string* (string n)
  (collect 'string
           (subseries (apply #'series (coerce string 'list))
                      0
                      (truncate (* n (length string))))))
(string* "-*" 5.5)
;=> "-*-*-*-*-*-"

(string* "-***" (+ 3 1/4))
;=> "-***-***-***-"

2文字の場合にしか上手くはまらず、全然使いやすくないです…。

2010-11-28

XCLがSBCLより速いところ

| 23:24 | XCLがSBCLより速いところ - わだばLisperになる を含むブックマーク はてなブックマーク - XCLがSBCLより速いところ - わだばLisperになる

Common Lispの入門ページで、(Common)Lispが他の言語に比べて便利なところにbignum(多倍長整数)があり、特にユーザーが意識することなくそのまま大きな数を扱えるという例で、

(DEFUN ^^ (BASE POWER)
  (LOOP :REPEAT POWER
        :FOR X := (EXPT BASE BASE) :THEN (EXPT X BASE)
        :FINALLY (RETURN X)))

(integer-length (^^ 10 5))
;=> 332193

こんな感じの例がありました。

SBCLだと思ったより時間がかかって、

(progn (^^ 10 6) nil)
;⇒ NIL
----------
Evaluation took:
  5.140 seconds of real time
  5.120000 seconds of total run time (5.120000 user, 0.000000 system)
  99.61% CPU
  12,305,748,798 processor cycles
  1,273,168 bytes consed
  
Intel(R) Core(TM)2 Duo CPU     P8600  @ 2.40GHz

位の感じです。

他の処理系だとどうなのかなと思ってXCLで試してみると、

(time (progn (^^ 10 6) nil))
;⇒ NIL
----------
Execution took:
  0.122491002 seconds of real time
  0.119999997 seconds of user run time
  0.0 seconds of system run time
  2,687,456 bytes allocated
  0 cons cells

断然速い結果に。

もしや、GMPを使っている処理系が速いのかもしれないと思って試してみると、

;; ECL
> (time (progn (^^ 10 6) nil))

real time : 0.078 secs
run time  : 0.080 secs
gc count  : 2 times
consed    : 18454345 bytes
NIL
;; scheme
(define (^^ base power)
  (let loop ((ntimes (- power 1))
             (x (expt base base)))
    (if (zero? ntimes)
        x
        (loop (- ntimes 1)
              (expt x base)))))
;; mosh (gmp)
(time (begin (^^ 10 6) #f))
;;0.23214101791381836 real 0.2 user 0.02 sys
#f
;; gosh
(time (begin (^^ 10 6) #f))
;(time (begin (^^ 10 6) #f))
; real  22.394
; user  22.320
; sys    0.000
#f

どうもそういう気がします。

以上、オチなし。

2010-11-27

Shibuya.lisp TT#6が開催されました!

| 22:25 | Shibuya.lisp TT#6が開催されました! - わだばLisperになる を含むブックマーク はてなブックマーク - Shibuya.lisp TT#6が開催されました! - わだばLisperになる

2年前に秋に発足したShibuya.lispですが、今回で丸2年を迎え、6回目の開催となりました。

今回も色々な方々にご協力頂き無事に終了することができました。

発表された方、参加された方、ustreamで中継をご覧頂いた方、ありがとうございます。

2年前に比べると、地味ながらも着実に層の厚みは増してきたかなあという感じはしています。

この流れを止めることなく推進することができたら良いなと思います。

さて、次回のTT#7は今のところまったく計画は立ってないですが、そのうち動き始めることだろうと思います。

何か実現したいこと/提案などありましたら、Shibya.lispメーリングリストに投げてみて頂けると嬉しいです。

2010-11-26

KMRCLを眺める(229) SCORE-MULTIWORD-MATCH

| 23:51 | KMRCLを眺める(229) SCORE-MULTIWORD-MATCH - わだばLisperになる を含むブックマーク はてなブックマーク - KMRCLを眺める(229) SCORE-MULTIWORD-MATCH - わだばLisperになる

xml-utils.lispも眺め終えたので、今回はKMRCLのstrmatch.lispから、SCORE-MULTIWORD-MATCHです。

名前からすると、与えられた引数の文字列の類似度を測定する関数のようです。

定義は、

(defun score-multiword-match (s1 s2)
  "Score a match between two strings with s1 being reference string.
S1 can be a string or a list or strings/conses"
  (let* ((word-list-1 (if (stringp s1)
                          (split-alphanumeric-string s1)
                        s1))
         (word-list-2 (split-alphanumeric-string s2))
         (n1 (length word-list-1))
         (n2 (length word-list-2))
         (unmatched n1)
         (score 0))
    (declare (fixnum n1 n2 score unmatched))
    (decf score (* 4 (abs (- n1 n2))))
    (dotimes (iword n1)
      (declare (fixnum iword))
      (let ((w1 (nth iword word-list-1))
            pos)
        (cond
         ((consp w1)
          (let ((first t))
            (dotimes (i-alt (length w1))
              (setq pos
                (position (nth i-alt w1) word-list-2
                          :test #'string-equal))
              (when pos
                (incf score (- 30
                               (if first 0 5)
                               (abs (- iword pos))))
                (decf unmatched)
                (return))
              (setq first nil))))
         ((stringp w1)
          (kmrcl:awhen (position w1 word-list-2
                               :test #'string-equal)
                       (incf score (- 30 (abs (- kmrcl::it iword))))
                       (decf unmatched))))))
    (decf score (* 4 unmatched))
    score))

となっていますが、どうも自分には、使い方がいまいち不明でした

(kl:score-multiword-match "foo" "foo")
;=> 30

(kl:score-multiword-match '("foo") "foo")
;=> 30

(kl:score-multiword-match '("foo" "foo") "foo")
;=> 55

(kl:score-multiword-match '("foo" "foo" "foo") "foo")
;=> 79

(kl:score-multiword-match '("foo" "foo" "foo" "foo") "foo")
;=> 102

(kl:score-multiword-match '("foo" "foo" "foo" "foa") "foo")
;=> 71

(kl:score-multiword-match '("foo" "fao" "foo" "foa") "foo")
;=> 38

有名なアルゴリズムだったりするのでしょうか。

2010-11-25

GOOでL-99 (P23 指定した個数の要素をランダムに選択)

| 23:30 | GOOでL-99 (P23 指定した個数の要素をランダムに選択) - わだばLisperになる を含むブックマーク はてなブックマーク - GOOでL-99 (P23 指定した個数の要素をランダムに選択) - わだばLisperになる

以前は、L-99しかやってないブログと化していた程、L-99を色々なLISP方言で解いてみていましたが、どの方言でも完遂してはいません。

久々にちょっと久々に挑戦してみようかなと思い、ブログを眺めてみると、直近のエントリーは、2年前のGOOでの挑戦でした。

GOOもすっかり忘れているので、ちょっと書いて遊んでみることに。

久々に触ってみましたが、やっぱり色々と変わっています。

ちなみに、GOOはどういう言語かというと、Dylanの開発にも携わった、Jonathan Bachrach氏が開発した言語で、Dylan+Scheme+当時構想だけ発表されていたArcという感じのLISP方言です。

S式のDylanな感じもしつつ、Paul Graham氏の「生まれて3週間目のArc」を意識した機能と、短かすぎて逆に覚えられない関数名が特徴だと個人的には思っています。(GOOのページにもArcのパロディのような題名が多くあります)

ざっと目立つところだと

  • Arc/Perl風の短い関数名(と動作)
  • 基本的にメソッド主体で、総称関数
  • Dylanっぽい構文
  • Seriesが組み込み
  • 多値の代わりにタプル

というところでしょうか。

結構面白いので変わったLISP方言が好きな方にはお勧めです。

P23 (**) Extract a given number of randomly selected elements from a list.
    The selected items shall be returned in a list.
    Example:
    * (rnd-select '(a b c d e f g h) 3)
    (E D A)

    Hint: Use the built-in random number generator and the result of problem P20.
(df random-pop (u|<lst> => (tup <lst> <any>))
  (def rest (packer-fab <lst>))
  (def item (packer-fab <lst>))
  (def picknum (random (- (len u) 1)))
  (for ((e u)
        (i (from 0)))
    (if (= picknum i)
        (pack-in item e)
        (pack-in rest e)))
  (tup (packer-res rest)
       (1st (packer-res item))))

(df rnd-select (u|<lst> n|<int> => <lst>)
  (loc ((self1 (acc rest n)
          (if (or (zero? n) 
                  (empty? rest))
              acc
              (let (((tup nrest item) 
                     (random-pop rest)))
                (self1 (pair item acc)
                              nrest
                              (- n 1))))))
    (self1 () u n)))

実行例

(for ((i (range 1 <= 100)))
  (say out (rnd-select '(a b c d e f g h) 3) "\n"))
;-> 
;   (e g d)
;   (d e a)
;   (f d b)
;   (a b e)
;   (c a g)
;   (f d e)
;   (c f e)
;   (f g c)
;   (c f g)
;   (c g a)
;   (b e a)
;   (c a f)
;   (g f b)
;   (b a f)
;   (e d b)
;   (c a b)
;   (b f a)
;   (c g a)
;   (c b a)
;   (f e a)
;...

2010-11-24

Land of Lisp 読書記録 (1)

| 01:41 | Land of Lisp 読書記録 (1) - わだばLisperになる を含むブックマーク はてなブックマーク - Land of Lisp 読書記録 (1) - わだばLisperになる

去年の10月位に出るんじゃないかと言われていたLand of Lispですが、待つこと一年、先日の10/26日に発売となりました。

著者は、このブログのエントリーの題にもいるLISPエイリアンの作者でもある、Conrad Barski氏です。

ブログでエイリアンも使わせてもらっているので御布施ということで購入。

紙の本としても買えますが、自分は、No Starch PressからPDF版を$24位でダウンロード購入しました。

しかし、購入して安心したのか、この一ヶ月ずっと積読に。

ブログに記録を付けていけば読む進められる気がするので読書記録を付けてゆきます。

ACKNOWLEDGMENTS

Land of Lispは、ウェブ上のチュートリアルであるCasting SPELs in Lispから発展したのもだそうです。

Casting SPELs in Lispをつくるにあたって色々な人にアドバイスをもらったそうですが、RMS(Richard Stallman)にも、Emacs lispのコード例付きの親切なメールでLispのスタイル上のアドバイスなどをもらったらしいです。本文に出てくるeqとequalの話などがなんとなくこの辺りに由来するのかなあとちょっと思いましたが、実際はどうなのか。

INTRODUCTION

内容は、割と良くある感じの、LISPに初めて触れる人向けのLISPの歴史と特長の解説ですが、人類史(地球史?)と重ね合せての説明になっていて、ギャグなのか本気なのか良く分からない内容になっていますが、面白いです。

Lispの流行り廃りについても触れられていて、AIの冬以降のLISPプログラマがUMAに喩えられていたりするのですが、山奥や密林に潜む、ウェンディゴ、イエティ、サスカッチに混ざってなぜかRMSの名が並んでいます。

他には、C++とLISPを比べ、C++の場合は、Stroustrupという凄い人がCを拡張して俺C(C++)を作ったけど、LISPでは誰でも簡単に拡張して俺LISPのようなものが作れるのだよ、というのが、どの辺の層にアピールするのか謎ではありますが、なるほどとは思いました。

ちなみに、この本は、Barski氏の挿絵が沢山あるのですが、本文とはそれほど関係ないように思われ、本文の補足を図示して分かり易くしたい、というより、描きたいから描いてる!、という感じで、これも面白い点です。

2010-11-22

KMRCLを眺める(228) SGML-HEADER-STREAM

| 22:41 | KMRCLを眺める(228) SGML-HEADER-STREAM - わだばLisperになる を含むブックマーク はてなブックマーク - KMRCLを眺める(228) SGML-HEADER-STREAM - わだばLisperになる

今回はKMRCLのxml-utils.lispから、SGML-HEADER-STREAMです。

名前の通り、SGML系のヘッダを出力するのに使うようです。

定義は、

(defun sgml-header-stream (format stream &key entities (encoding "iso-8859-1") standalone (version "1.0")
                          top-element (availability "PUBLIC") registered organization (type "DTD")
                           label (language "EN") url)
  (when (in format :xhtml :xhtml11 :xhtml10-strict :xhtml10-transitional :xhtml10-frameset :xml :docbook)
    (xml-declaration-stream stream :version version :encoding encoding :standalone standalone))
  (unless (eq :xml format)
    (doctype-format stream format :top-element top-element
                    :availability availability :registered registered
                    :organization organization :type type :label label :language language
                    :url url :entities entities))
  stream)

動作は、

(with-output-to-string (out)
  (kl::sgml-header-stream :xhtml10-transitional
                          out))
;=> "<?xml version=\"1.0\" encoding=\"iso-8859-1\" ?>
;   <!DOCTYPE html PUBLIC \"-//W3C//DTD XHTML 1.0 Transitional//EN\" \"http://www.w3.org/TR/xhtml10/DTD/xhtml10-transitional.dtd\">
;   "

といったところ。

ふと気付いたのですが、どうも、一般的には、http://www.w3.org/TR/xhtml10/DTD/xhtml10-transitional.dtdじゃなくて、 http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtdのようなんですが、定義が古かったりするんでしょうか。

2010-11-21

アナフォリックマクロのITをどうするか

| 20:54 | アナフォリックマクロのITをどうするか - わだばLisperになる を含むブックマーク はてなブックマーク - アナフォリックマクロのITをどうするか - わだばLisperになる

アナフォリックマクロを提供しているユーティリティ集は割とあるのですが、束縛を参照するためのITやSELFも同じパッケージのものを対で使わなくてはいけないので、複数パッケージを混ぜて使う場合は面倒です。

具体的にどういうケースがあるかというと、KMRCLからはAIF、FARE-UTILSからは、AANDを使うとすると、どちらかのITはパッケージ名を付けなくては機能しません。

マクロの作り方自体を工夫すればこういうこともないかもしれませんが、既存のライブラリを書き換えるのも面倒です。

どれか一つを選んで使うというのもありなのですが、できれば複数を同時に使いたい。

大本のパッケージがITをEXPORTしていれば良い

ということで、どんなライブラリでもCLパッケージは継承していることを利用し、CLパッケージがITをEXPORTするようにしたら良いのではないかと思い、実際に試してみました。

しかし、結果としては、処理系内部でもITを使っていることがあるらしく、競合の解消が面倒な様子。

しょうがないので、ITパッケージを作って、ITとSELFだけをエクスポートするものを作成して、アナフォリックマクロを提供するパッケージは、IT:ITを継承するようにしてみました。

手順としては、ライブラリが読み込まれる前にIT:ITを含んだパッケージを作成しておいて、その後にライブラリをロードします。

(defpackage :it
  (:export :it :self))

(defmacro inherit-it (pkg)
  `(progn
     (defpackage ,pkg)
     (shadowing-import '(it:it it:self) ,pkg)))

(inherit-it :kmrcl)
(inherit-it :fare-utils)
(inherit-it :anaphora)
(inherit-it :it.bese.arnesi)
(inherit-it :mycl-util)
(inherit-it :sclf)
(inherit-it :common-idioms)
(inherit-it :elephant-utils)

(asdf:oos 'asdf:load-op :kmrcl)
〜

こうすると、各ライブラリのITはIT:ITを継承しているので使うパッケージでもIT:ITを継承しておけば、すんなり動くようです。

こんな乱暴で大丈夫なのかなあとも思いますが、アナフォリックマクロ自体飛び道具な気もするので、まあ良しとします。

ちなみに、あまり深く考えていない対処法なので、この方法に何か問題があれば教えて頂けると嬉しいです。

2010-11-20

LAMBDAを使うなスタイル (1)

| 23:49 | LAMBDAを使うなスタイル (1) - わだばLisperになる を含むブックマーク はてなブックマーク - LAMBDAを使うなスタイル (1) - わだばLisperになる

先日のLISPセミナー参加者との雑談で「LAMBDAを使うな、LOOPを使え」というスタイルがあるということを知りました。

それだったら、高階スタイルで書いたフォームをSeriesみたいにマクロでループに展開してしまえば良いじょのいこ!、と思って家に帰ってちょっと書き始めたのですが、いやいや、その辺りは、コンパイラが良きに計らってくれるんじゃないか、と思い、SBCLではどうなのかを少し追い掛けてみました。

とりあえず、

(mapc (lambda (x) x) '(1 2 3 4))

のようなコードをお題に調べて行きます。

まず、MAPCの定義を眺めてみると、最初に、MAPCにはコンパイラにより最適化の変形が施されます。

これには、SB-C::MAPFOO-TRANSFORM(SB-Cの-CはコンパイラのC)が使われて、

(let ((list '(1 2 3 4))
      (more-lists () ))
  (sb-c::mapfoo-transform (lambda (x) x) (cons list more-lists) nil t))
;=> (LET ((#:G3164 (SB-KERNEL:%COERCE-CALLABLE-TO-FUN #)))
;     (LET ((#:G3162 (1 2 3 4)))
;       (SB-INT:DO-ANONYMOUS ((#:G3163 #:G3162 (CDR #:G3163)))
;                            ((OR (ENDP #:G3163)) (SB-EXT:TRULY-THE LIST #:G3162))
;                            (SB-C::%FUNCALL #:G3164 (CAR #:G3163)))))

のような感じで元の式から変形された式が取り出されます。

ここのDO-ANONYMOUSですが、DOのブロック名がNILではなくて、GENSYMなブロック名になっているもののようです。

ここでDO-ANONYMOUSを展開すると、

(LET ((G3162 arg))
  (BLOCK G3168
    (LET ((G3163 G3162))
      (TAGBODY (GO G3170)
         G3169 (TAGBODY (SB-C::%FUNCALL G3164 (CAR G3163)))
               (PSETQ G3163 (CDR G3163))
         G3170 (UNLESS (OR (ENDP G3163)) (GO G3169))
               (RETURN-FROM G3168 (PROGN (SB-EXT:TRULY-THE LIST G3162))))))))

となっているのが分かりますが、べたべたのGOTOループです。

次に、手書きで、上の様にGOTOループに展開したものと、素直に書いたものが、どう違ってくるかを確かめます。

(defun call-my-mapc (fn arg)
  (let ((fn (sb-kernel:%coerce-callable-to-fun fn))
        (list arg))
    (block block
      (let ((tail list))
        (tagbody (go L2)
              L1 (tagbody (sb-c::%funcall fn (car tail)))
                 (psetq tail (cdr tail))
              L2 (unless (or (endp tail)) (go L1))
                 (return-from block
                   (progn 
                     (sb-ext:truly-the list list))))))))
(defun call-mapc (fn arg)
  (mapc fn arg))

この二つをDISASSEMBLEして比べてみたところ、当たり前かもしれませんが、全く同じ内容になることを確認しました。(長いので結果は省略)

とりあえず、分かることは、良く使うところは処理系がやっぱり良きに計らってくれるんだなという感じです。

しかし、他にもループメインのスタイルとLAMBDAを使うスタイルとでは、処理効率を考えた場合に気をつける点が違ってくるようなので引き続き比較して書いていきたいと思います。

2010-11-19

2日間まるごとLISPセミナー 2010 2日目

| 23:28 | 2日間まるごとLISPセミナー 2010 2日目 - わだばLisperになる を含むブックマーク はてなブックマーク - 2日間まるごとLISPセミナー 2010 2日目 - わだばLisperになる

毎年開催されている数理システム/Franz開催のセミナー2日目に行ってきました。

2日目は毎年セミナーというよりは、事例紹介が多いようです。

(1) 射程内に入った実時間ごみ集め(竹内郁雄/東京大学名誉教授)

10年程前にTAO/SILENTで実際に実装したハードリアルタイムのGCについてのお話でした。

「LISPはGCをまじめにやれば実時間処理に使える!」とのことで、並列GCの実装戦略や、経験談を交えて解説されていました。

まとめとして、LISPに実時間処理がつけば鬼に金棒 それは必ず実現する! とのしめくくり。

今回の内容は、10年程前のLISP専用機での話でしたが、現在、竹内先生は、それとは別に、x86でいろいろ実験されているとのこと。楽しみです!

(2) Garbage Collection in Lisp(Carl Shapiro/Google Inc., USA)

Googleの方がLISPのことを話されるというのでちょっと意外に思いましたが、GCを中心とした話で、実際にClozure CLや、Allegro CLがどういう風な戦略で実装しているかをかなり綿密に調べてのお話だったようです。

現在のCLのGCについては、概して戦略が古めのようで、もっとがんばれる部分が多いとのこと。

GCハッカーには活躍できる場があるとポジティブに捉えることもできる、とのことでしたが確かにそういう風にも考えられるなと思いました :)

最後のまとめで、「アプリがGCの性能を要求する」→「GCが改善される」という関連があるからには、「まずはもっとLISPでアプリを書いて行くべき」という言葉が印象的でした。確かにそうですよね。

(3) データフロービジュアルプログラミングシステム(阿部正佳/数理システム)

先日JAISTで行なわれたELIS復活祭で話された内容の進展という感じでした。

本質的に並列なデータ駆動プログラミングについては、7〜80年代にさかんに次世代技術として研究されていたようですが、ビジュアル的な操作でのプログラミングで、このデータフロープログラミングを採用したとのこと。

現在は、ビジュアルな画面記述が、Allegro CLに翻訳されて実行されています。

ビジュアルプログラミングシステムだけに、やはり一度見てみると面白さが分かるかなと思いました。

また、おまけで、データフロープログラミングからモナドを説明してみせるというのも興味深かったです。

(4) テレコムビジネスとセマンティックWeb(Jans Aasman/Franz Inc.)

テレコムビジネスも顧客の欲しいものを提供する時代から、顧客の欲しいものを予測して先に提示するような時代にはいっているようで、顧客の欲しいものを予測する技術の基盤として、セマンティックWeb技術が活用されているという事例が紹介されていました。

これからは、受け身ではなく、どんどん打って出るような時代になっていくのかなあという感じでした。

今年も興味深い内容で楽しい2日間でした。

来年も是非とも参加したいです。

2010-11-18

2日間まるごとLISPセミナー 2010 1日目

| 23:44 | 2日間まるごとLISPセミナー 2010 1日目 - わだばLisperになる を含むブックマーク はてなブックマーク - 2日間まるごとLISPセミナー 2010 1日目 - わだばLisperになる

毎年開催されている数理システム/Franz開催のセミナーに行ってきました。

メモを取りつつきいていたのですが、まとめる時間がないので、今回はざっくり書きたいと思います。

あとで、詳しく書きたいと思っています。

(1) セマンティックWeb入門

講師: 黒田寿男 (Mathematical Systems Inc.)

時間: 13:00 〜 14:00

次の (2) Common Lisp と Prolog を使ったセマンティックWeb開発 の準備的な内容ということで、セマンティックウェブについての入門的な説明でした。

概略の説明の後には、AllegroGraphを使ったデモ。三つ組をどういう手段で検索するか等を病院の院内感染の発生源を突き止めるというストーリーでデモしたりしていました。

(2) Common Lisp と Prolog を使ったセマンティックWeb開発

講師: Jans Aasman (Franz Inc.)

時間: 14:10 〜 15:40

AllegroGraphの使い方を、今回は、クエリ言語として、Allegro Prologを用いて解説。

まずは、Allegro Prologの解説から始まり、同様のクエリ言語であるSPARQLと比べて柔軟であることを解説。

その後は、実際にAllegroGraphのRDF triple storeを用いてクエリをデモしたりしていました。

(3) Practical Tutorial on Machine Learning using Common Lisp

講師: 阿部祐介 (Mathematical Systems Inc.)

時間: 15:50 〜 16:30

機械学習についてのお話。LISPで云々というよりは、機械学習そのものについての解説が多めでした。

今回は、名寄せと呼ばれる複数の異なるデータベースをつき合せて同一人物、同一対象のデータをとりまとめる問題を取り上げての解説でした。

興味を持たれやすそうな分かり易い例で解説されていて、とても面白く聴くことができました。

(4) Allegro CL debuggerを利用したデバッグ方法

講師: 茂野真弓 (Mathematical Systems Inc.)

時間: 16:40 〜 17:30

Allegro CLのLDB(Lisp DeBug)の解説。アセンブリコードをステップ実行できるものだそうで、実際にコマンドを解説しつつデモを行なっていました。

また、Allegro CL 8.2から導入された、ソースレベルでのステップ実行も解説。

ステップ実行では、マクロをどう展開するかというのが問題になりますが、その辺りもFranzは苦心されているようです。

実際にデモしてもらえると非常に面白そうだなと思いました。

ざっとこんな感じですが、近々、個々の内容についてもメモした限りブログに書いてみたいと思っています。

2010-11-16

car/cdrの別表記を考えてみた

| 21:05 | car/cdrの別表記を考えてみた - わだばLisperになる を含むブックマーク はてなブックマーク - car/cdrの別表記を考えてみた - わだばLisperになる

何万回目の再発明なのかは分かりませんが、carとcdrの別表記がふと浮びました。

carやcdrというより、どちらかというと、firstや、secondに由来する考えだと思いますが、carを、

(i '(1 2 3 4 5))
;=> 1

と書いたら楽なんじゃないかと。

それで、cdrは、

(ii> '(1 2 3 4))
;=> (2 3 4)

という風、

(caaar (cddr '(1 2 ((3 4) 5))))
;=> 3

のようなものも、元の関数名が短かいので

(i (i (i (iii> '(1 2 ((3 4) 5))))))
;=> 3

そんなに膨れません。

(i@i@i@iii> '(1 2 ((3 4) 5)))
;=> 3

みたいに合体して書けても良いかなと思います。

まあ、これは、パターンマッチとか

(destructuring-bind (a b ((c d) e))
                    '(1 2 ((3 4) 5))
  c)
;=> 3

みたいに書くと思いますが…

自分は、carやcdrの組み合わせは、精々caddr、cddr位までしか使わない感じです。

最初の3つ位までが楽に書ければ、それで良いのかなあとも思います。

(letS* ((i (Erange 1 10))
        (name (intern (format nil "~@R" i))))
  (Rlist (eval `(defun ,name (list) (nth ,(1- i) list)))))
;≡ (loop :for i :from 1 :to 10
;         :for name := (intern (format nil "~@R" i))
;         :collect (eval `(defun ,name (list) (nth ,(1- i) list))))

;=> (I II III IV V VI VII VIII IX X)

(letS* ((i (Erange 2 11))
        (name (intern (format nil "~@R>" i))))
  (Rlist 
   (eval `(defun ,name (list) (nthcdr ,(1- i) list)))))
;=> (II> III> IV> V> VI> VII> VIII> IX> X> XI>)

2010-11-15

KMRCLを眺める(227) DOCTYPE-STREAM

| 21:23 | KMRCLを眺める(227) DOCTYPE-STREAM - わだばLisperになる を含むブックマーク はてなブックマーク - KMRCLを眺める(227) DOCTYPE-STREAM - わだばLisperになる

今回はKMRCLのxml-utils.lispから、DOCTYPE-STREAMです。

眺める順番を間違えてしまいましたが、DOCTYPEを作成するためのユーティリティで、ストリームを取って出力するものです。

前回のDOCTYPE-FORMATは内部でこれを利用しています。

定義は、

(defun doctype-stream (stream top-element availability registered organization type
                       label language url entities)
  (format stream "<!DOCTYPE ~A ~A \"~A//~A//~A ~A//~A\"" top-element
          availability (if registered "+" "-") organization type label language)

  (when url
    (write-char #\space stream)
    (write-char #\" stream)
    (write-string url stream)
    (write-char #\" stream))

  (when entities
    (format stream " [~%~A~%]" entities))

  (write-char #\> stream)
  (write-char #\newline stream))

動作は、

(with-output-to-string (out)
  (kl::doctype-stream out
                      "html"
                      "PUBLIC"
                      NIL
                      "W3C"
                      "DTD"
                      "XHTML 1.1"
                      "EN"
                      "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"
                      NIL))
;=> "<!DOCTYPE html PUBLIC \"-//W3C//DTD XHTML 1.1//EN\" \"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd\">
;   "

といったところ

2010-11-14

COMPILER-LETの使い道

| 23:57 | COMPILER-LETの使い道 - わだばLisperになる を含むブックマーク はてなブックマーク - COMPILER-LETの使い道 - わだばLisperになる

COMPILER-LETは、CLtL2までは存在したスペシャルフォームで、今でも互換性の維持のため処理系によっては、サポートしています。

動作としては、インタプリタでは、束縛する変数をスペシャル宣言したletと同じ動きをするのですが、コンパイラが処理すると、コンパイル時にその変数束縛が有効にされた状態でボディが評価されます。

言葉では上手く説明できないのですが、動きとしては、コンパイル時にスペシャル変数の束縛が固定される、というような感じです。

#+sbcl (import 'sb-cltl2:compiler-let)

(defmacro foo () 
  (if *flag* 
      :hello
      :bye))

(list *flag* (foo))
;=> (NIL :BYE)

(defmacro bar ()
  (foo))

(list *flag* (bar))
;=> (NIL :BYE)

(defmacro baz ()
  `(let ((*flag* t)) ;マクロ展開後には効くが展開時には効かない
     (foo)))

(list *flag* (baz))
;=> (NIL :BYE)

(defmacro quux ()
  `(compiler-let ((*flag* t))
     (foo)))

(list *flag* (quux))
;=> (NIL :HELLO)

これはどういうところで使うんだろうと常々思っていましたが、Seriesがマクロの展開にスペシャル変数をフラグとして使っていて、このフラグの値を制御をしたい場合に必要になりました。

具体的には、SERIES::*SERIES-IMPLICIT-MAP*という変数があり、これがマクロ展開で参照されるのですが、このフラグを参照するマクロを使って、さらにその上にマクロを組むにあたって、大域変数の値によらず常にSERIES::*SERIES-IMPLICIT-MAP*がTの状態で展開されて欲しいということになりました。

COMPILER-LETは、用途が曖昧で大抵の局面では、MACROLETや、SYMBOL-MACROLETで置き換え可能ということで廃止になったようです。

に置き換えの説明があるのですが、やはり色々とややこしい気がします…

2010-11-13

同じ年月は同じグループとしてカウントして数を求める例でのコード比較を Common Lisp でも

| 22:05 | 同じ年月は同じグループとしてカウントして数を求める例でのコード比較を Common Lisp でも - わだばLisperになる を含むブックマーク はてなブックマーク - 同じ年月は同じグループとしてカウントして数を求める例でのコード比較を Common Lisp でも - わだばLisperになる

sumimさんの302 Found経由

まけるなCommon Lisp。しかし、ライブラリを使ってる時点で反則かもしれず。

最近、comp.lang.schemeで似たような質問があったんですが、そのスレッドの回答で見かけたequivalence-classesというのを使ってみました。

;;---(logic)----で囲んだ箇所を比較対象箇所とする
(import 'com.informatimago.common-lisp.list:equivalence-classes)

(defvar *year-months* '("2009-11"
                        "2009-01"
                        "2010-01"
                        "2010-12"
                        "2010-01"
                        "2010-04"
                        "2010-01"
                        "2010-12"
                        "2010-12"
                        "2010-04"))

;;---(logic)----
(mapcar (lambda (x) (cons (car x) (length x)))
        (sort (equivalence-classes *year-months* :test #'string=)
              #'string< :key #'car))
;;---(logic)----
;=> (("2009-01" . 1) ("2009-11" . 1) ("2010-01" . 3) ("2010-04" . 2)
;    ("2010-12" . 3))

無駄にSeriesで頑張ってみる

;; series::*series-implicit-map* ;=> T
(let ((ans () ))
  (iterate ((item (scan *year-months*)))
    (let ((place (member item ans :key #'car :test #'string=)))
      (if place
          (push item (car place))
          (push (list item) ans))))
  (series::let* ((ym (scan ans))
                 (ym.sum (cons (car ym) (length ym))))
    (alter ym ym.sum)
    (sort ans #'string< :key #'car)))
;=> (("2009-01" . 1) ("2009-11" . 1) ("2010-01" . 3) ("2010-04" . 2)
;    ("2010-12" . 3))

長い…まあ、equivalence-classesを使えば…

(series::let* ((ym (scan (equivalence-classes *year-months* :test #'string=)))
               (ym.sum (cons (car ym) (length ym))))
  (sort (collect ym.sum) #'string< :key #'car))
;=> (("2010-04" . 2) ("2010-12" . 3) ("2010-01" . 3) ("2009-01" . 1)
;    ("2009-11" . 1))

;; LetS風
(letS* ((ym (Elist (equivalence-classes *year-months* :test #'string=)))
        (ym.sum (cons (car ym) (length ym))))
  (sort (Rlist ym.sum) #'string< :key #'car))
;=> (("2010-04" . 2) ("2010-12" . 3) ("2010-01" . 3) ("2009-01" . 1)
;    ("2009-11" . 1))

2010-11-12

Medleyを使ってみよう(1)

| 23:25 | Medleyを使ってみよう(1) - わだばLisperになる を含むブックマーク はてなブックマーク - Medleyを使ってみよう(1) - わだばLisperになる

80年代初頭で二大LISPといえば、MacLISPInterlispのことだったらしいですが、今の二大LISPといえば、Common LispとSchemeで、MacLISP系のCLやEmacs lispに触る機会はあってもなかなかInterlisp系に触る機会もなくなってしまいました。

ほぼ見掛けなくなったInterlispですが、実はMacLISP系/Interlisp系ともにLispマシンが作成されていて、MacLISP系は、CADR〜Symbolics、Interlisp系は、XeroxのInterlisp-Dと進化をしていったようです。

このInterlisp-Dなのですが、最終的には専用マシンが仮想マシン化されていて、仮想マシン化されたものは、Medleyと呼ばれているようです。

このMedleyなのですが、丁度5年程前に、

の記事を読んで面白いと思ってちょっといじってみていました。

当時はLISPのことは殆ど分からなかったのですが、今なら少しは分かるようになったので、改めていじってみようかなと思います。

起動させる

とりあえず、上記のInterlisp-D紹介ページのリンクを辿って

ftp://ftp.parc.xerox.com/pub/lfg/ldex
ftp://ftp.parc.xerox.com/pub/lfg/lfg.sysout.gz

をダウンロードします。

ldexに実行属性をつけ、

./ldex lfg.sysout

で起動すれば良いのですが、libcのバージョンやらなにやらで起動しないことが結構あります。

OSが変わる度に動いたり動かなくなったりすることも多いので、今回は、qemuや、VMware上で動かしてみることにしました。

ちなみに、自分は、VirtualBoxで試しています。

自分が動くことを確認したのは、ちょっと古めのKNOPPIX V3.6-2004です。

KNOPPIX_V3.6-2004-08-16-EN.iso

を探してこのLiveCDから起動するのが簡単かなと思いました。

LiveCDでOSを起動させ、仮想マシンに上記のダウンロードしたファイルを設置し、

./ldex lfg.sysout

として起動してみます。

送信者 LISP

という感じで起動します。

実は、このMedleyはこれ単体で配布されているのではなく、LFGというアプリケーションを動かす環境として配布されているらしいのですが、Medleyもほぼ丸ごと付属してきている、ということらしいです。

とりあえず、Medleyの環境を使いたいので、LFGのアプリは、ウィンドウの画面の上で右クリックしてぽちぽち消して行きます

LISP環境の起動の仕方

送信者 LISP

LISP環境としては、Interlispだけでなく、Xerox Common Lisp(CLtL1)も起動します。この環境もなかなかレアではないでしょうか。

起動方法ですが、右クリック→EXEC→でXerox Common Lispでリスナーが開きます。

ヘルプは、リスナー上で、:?するとヘルプ一覧が出てきます。

関数を定義して遊ぶ

関数の定義は、

(ed 'foo)

などとすると、エディタが開くので、それを編集するという流れになります。既存の定義も同じようにして編集できます。

環境はイメージ指向

今の馴染みの開発/実行環境は、関数定義などは、ファイルに書き出すというファイル指向だと思いますが、Medleyは、同じXeroxのSmalltalkと同じようにイメージ指向です。

環境の保存には、右クリックメニューからSaveVMを選択しイメージの状態を保存します。

この方法だと、ホームディレクトリ直下にlisp.virtualmemというイメージが保存されます。

次回起動時には、

./ldex lisp.virtualmem

とすることによって保存した仮想マシンの状態をそのまま復活させることができます。

ということで今回はざっと導入までを調べてみましたが、結局CLの方を触ってばかりで、全然Interlispの方は触っていませんでした。

徐々に、Interlispの世界も探っていきたいと思います。

2010-11-11

KMRCLを眺める(226) DOCTYPE-FORMAT

| 23:51 | KMRCLを眺める(226) DOCTYPE-FORMAT - わだばLisperになる を含むブックマーク はてなブックマーク - KMRCLを眺める(226) DOCTYPE-FORMAT - わだばLisperになる

今回はKMRCLのxml-utils.lispから、DOCTYPE-FORMATです。

名前から大体分かるようにDOCTYPEを作成するためのユーティリティです。

定義は、

(defun doctype-format (stream format &key top-element (availability "PUBLIC")
                       (registered nil) organization (type "DTD") label
                       (language "EN") url entities)
  (case format
    ((:xhtml11 :xhtml)
     (doctype-stream stream "html" availability registered "W3C" type "XHTML 1.1" language
                     (if url url "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd")
                     entities))
    (:xhtml10-strict
     (doctype-stream stream "html" availability registered "W3C" type "XHTML 1.0 Strict" language
                     (if url url "http://www.w3.org/TR/xhtml10/DTD/xhtml10-strict.dtd")
                     entities))
    (:xhtml10-transitional
     (doctype-stream stream "html" availability registered "W3C" type "XHTML 1.0 Transitional" language
                     (if url url "http://www.w3.org/TR/xhtml10/DTD/xhtml10-transitional.dtd")
                     entities))
    (:xhtml-frameset
     (doctype-stream stream "html" availability registered "W3C" type "XHTML 1.0 Frameset" language
                     (if url url "http://www.w3.org/TR/xhtml10/DTD/xhtml10-frameset.dtd")
                     entities))
    (:html2
     (doctype-stream stream "HTML" availability registered "IETF" type "HTML" language url entities))
    (:html3
     (doctype-stream stream "HTML" availability registered "IETF" type "HTML 3.0" language url entities))
    (:html3.2
     (doctype-stream stream "HTML" availability registered "W3C" type "HTML 3.2 Final" language url entities))
    ((:html :html4)
     (doctype-stream stream "HTML" availability registered "W3C" type "HTML 4.01 Final" language url entities))
    ((:docbook :docbook42)
     (doctype-stream stream (if top-element top-element "book")
                     availability registered "OASIS" type "Docbook XML 4.2" language
                     (if url url "http://www.oasis-open.org/docbook/xml/4.2/docbookx.dtd")
                     entities))
    (t
     (unless top-element (warn "Missing top-element in doctype-format"))
     (unless organization (warn "Missing organization in doctype-format"))
     (unless label (warn "Missing label in doctype-format"))
     (doctype-stream stream top-element availability registered organization type label language url
                     entities))))

で、色々と条件を指定することができます。

動作は、

(with-output-to-string (out)
  (kl::doctype-format out :xhtml))
;=> "<!DOCTYPE html PUBLIC \"-//W3C//DTD XHTML 1.1//EN\" \"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd\">
;   "

というところ

2010-11-10

KMRCLを眺める(225) XML-DECLARATION-STREAM

| 21:48 | KMRCLを眺める(225) XML-DECLARATION-STREAM - わだばLisperになる を含むブックマーク はてなブックマーク - KMRCLを眺める(225) XML-DECLARATION-STREAM - わだばLisperになる

今回はKMRCLのxml-utils.lispから、XML-DECLARATION-STREAMです。

名前の通りXMLの宣言を作成するもので定義は、

(defun xml-declaration-stream (stream &key (version "1.0") standalone encoding)
  (format stream "<?xml version=\"~A\"~A~A ?>~%"
          version
          (if encoding
              (format nil " encoding=\"~A\"" encoding)
              ""
              )
          (if standalone
              (format nil " standalone=\"~A\"" standalone)
              "")))

という風。

動作は、

(with-output-to-string (out)
  (kl::xml-declaration-stream out :standalone "yes" :encoding "utf-8"))
;=> "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"yes\" ?>
;   "

となっています。

2010-11-09

KMRCLを眺める(224) WRITE-CDATA

| 21:35 | KMRCLを眺める(224) WRITE-CDATA - わだばLisperになる を含むブックマーク はてなブックマーク - KMRCLを眺める(224) WRITE-CDATA - わだばLisperになる

今回はKMRCLのxml-utils.lispから、WRITE-CDATAです。

定義は、

(defun write-cdata (str s)
  (declare (simple-string str) (optimize (speed 3) (safety 0) (space 0)))
  (do ((len (length str))
       (i 0 (1+ i)))
      ((= i len) str)
    (declare (fixnum i len))
    (let ((c (schar str i)))
      (case c
        (#\< (write-string "&lt;" s))
        (#\& (write-string "&amp;" s))
        (t   (write-char c s))))))

となっていて、単純に"<"や"&"などを、&lt;、&amp;に置き換えるだけのものの様子。

動作は、

(kl:write-cdata "<![CDATA[こんにちは]]>" *standard-output*)
;-> &lt;![CDATA[こんにちは]]>
;=> "<![CDATA[こんにちは]]>"

となっていますが、CDATAセクションの中でCDATAのタグを使うための文字列を生成するというのもちょっとおかしいし、CDATAを表示させるためとしたら、>が置き換えされていないし…、ということでちょっと謎の関数です。

(#\> (write-string "&gt;" s))

が忘れられていたりするんでしょうか。

2010-11-08

READのrecursive-pの働き (1)

| 22:33 | READのrecursive-pの働き (1) - わだばLisperになる を含むブックマーク はてなブックマーク - READのrecursive-pの働き (1) - わだばLisperになる

READ系の関数にはrecursive-pというオプションがあり、READがトップレベルからの呼ばれたのか、リーダーマクロ内などから(入れ子になって)呼ばれたかを区別するためにあるようです。

自分はいまいちこのオプションを理解していないのですが、CLtL2には、quoteのリーダーマクロを例にして、

(set-macro-character #\' 
                     #'(lambda (stream char) 
                         (declare (ignore char)) 
                         (list 'quote (read stream))))

のように、recursive-pをTにしておかないと、

(cons '#3=(p q r) '(x y . #3#))

を読んだときにラベルが上手く参照できないという例が載っています。

「'」を再定義すると元の状態と区別が付かなくなるので、「保」を定義して実験してみます。

(set-macro-character #\保
                     (lambda (stream char)
                       (declare (ignore char))
                       (list 'quote (read stream))))
(progn
  保(1 2 3 4))
;=> (1 2 3 4)

とりあえず、これはOK。

(setq *print-circle* t)

;; 本物のquote
(progn
  (cons '#3=(p q r)
        '(x y . #3#)))
;=> (#1=(P Q R) X Y . #1#)

(progn
  (cons 保#3=(p q r)
        保(x y . #3#)))
>>> reference to undefined label #3#

なるほど、#3#が見付からないということです。

どういう解釈かを考えてみると、

  1. 最初の「保」を通過した時点で#3というラベルは覚えている
  2. 2番めの「保」でラベルのことは忘れる(トップレベルで呼ばれていると思っているから)
  3. 読み進んでいくと#3#なんて知らないラベルを発見した

ということなのかと思いました。

ということは、2番目の「保」がラベルの定義を見ることができるようにしてやれば動くのかというと、

(progn
  (cons 保#3=(p q r)
        保#3=(x y . #3#)))
;=> ((P Q R) . #1=(X Y . #1#))

動きました。

これは、まともにrecursive-pをTにした定義では、逆にラベルが多過ぎというエラーになります。

(progn
  (cons '#3=(p q r)
        '#3=(x y . #3#)))
;>>>  multiply defined label: #3=

あとは、これがどんどんネストしていったりすることを考えればrecursive-pの意義は大体把握できた気がします。

おまけ

SBCLでは、

(progn
  (cons 保#3=(p q r)
        #3=保(x y . #3#)))
;=> ((P Q R) . #1=(X Y QUOTE #1#))

のようなものもOKみたいなのですが、CLISPはエラーになります。

エラーになっていた方が上の解釈としては納得行くのですが、実装依存だったりするのでしょうか。

HyperSpecと他の処理系の動作を確認してみなくては…。

2010-11-07

Seriesでリーダーマクロ

| 23:06 | Seriesでリーダーマクロ - わだばLisperになる を含むブックマーク はてなブックマーク - Seriesでリーダーマクロ - わだばLisperになる

リーダーマクロを書くのにSeriesを使うのも抵抗があるなあということで、実験。

Gauche風に、fooという正規表現にマッチする関数が、#/foo/と書けるようにしてみます。

CL-PPCRE:SCANに展開されて、

(#/f\\\/oo/ "f\\/oo")
;=> 0
;   5
;   #()
;   #()

上記のように動作すれば良しとします。

ということで、

(defun |#/-READER| (stream char arg)
  (declare (ignore char arg))
  (let ((g (gensym))
        (re (ppcre:regex-replace-all
             "\\\\/"
             (collect 'string
                      (choose
                       (let ((prev nil))
                         (until-if (lambda (c)
                                     (cond ((and (eql #\/ c)
                                                 (not (eql #\\ prev)))
                                            'T)
                                           (:else (setq prev c)
                                                  nil)))
                                   (scan-stream stream #'read-char)))))
             "/")))
    `(lambda (,g)
       (ppcre:scan ,re ,g))))

(set-dispatch-macro-character #\# #\/ #'|#/-READER|)

と書いてみましたが、微妙な感じに。

特に、"\\\\/"を"/"に置換しているところが悲しいですね。

それはさておき、リーダーマクロの展開ですが、

(#/f\\\/oo/ "f\\/oo")
;⇒
((LAMBDA (#:G3528) (CL-PPCRE:SCAN "f\\\\/oo" #:G3528)) "f\\/oo")

という風に展開されます。

書いていて、バックスラッシュの解釈をどうすれば良いんだったか分からなくなってきたので、テストを書いてみましたが、余計分からなくなってきました。

(defpackage :g000001-test
  (:use :cl :lisp-unit))

(in-package :g000001-test)

(do-symbols (s :g000001)
  (shadowing-import s))

(remove-all-tests :g000001-test)

(define-test |#/-READER|
  (assert-equal 
   "(LAMBDA (#:G0) (CL-PPCRE:SCAN \"Foo\" #:G0))"
   (let ((*readtable* (copy-readtable nil))
         (*gensym-counter* 0))
     (set-dispatch-macro-character #\# #\/ #'|#/-READER|)
     (write-to-string
      (read-from-string "#/Foo/"))))
  (assert-equal
   "(LAMBDA (#:G0) (CL-PPCRE:SCAN \"F/oo\" #:G0))"
   (let ((*readtable* (copy-readtable nil))
         (*gensym-counter* 0))
     (set-dispatch-macro-character #\# #\/ #'|#/-READER|)
     (write-to-string
      (read-from-string "#/F\\/oo/"))) )
  (assert-equal
   "(LAMBDA (#:G0) (CL-PPCRE:SCAN \"F\\\\\\\\/oo\" #:G0))"
   (let ((*readtable* (copy-readtable nil))
         (*gensym-counter* 0))
     (set-dispatch-macro-character #\# #\/ #'|#/-READER|)
     (write-to-string
      (read-from-string "#/F\\\\\\/oo/")))))

(run-all-tests :g000001-test)
;-> #/-READER: 3 assertions passed, 0 failed.

2010-11-06

KMRCLを眺める(223) CDATA-STRING

| 21:46 | KMRCLを眺める(223) CDATA-STRING - わだばLisperになる を含むブックマーク はてなブックマーク - KMRCLを眺める(223) CDATA-STRING - わだばLisperになる

今回はKMRCLのxml-utils.lispから、CDATA-STRINGです。

動作は、

(kl:cdata-string "<いろはにほへと><ちりぬるを>")
;=> "<![CDATA[<いろはにほへと><ちりぬるを>]]>"

という風。

定義は、単純に

(defun cdata-string (str)
  (concatenate 'string "<![CDATA[" str "]]>"))

となっています。

2010-11-05

letS*への道

| 23:28 | letS*への道 - わだばLisperになる を含むブックマーク はてなブックマーク - letS*への道 - わだばLisperになる

Seriesに先行するLetSには、letS*(レットエススター)というletを踏襲した構文があります。

このletS*の束縛部では、Series(LetSでいうsequence)を束縛することができます。

動作的には、

(defparameter *alist*
  '((A . 0) (B . 1) (C . 2) (D . 3) (E . 4) (F . 5) (G . 6) (H . 7) (I . 8)
    (J . 9) (K . 10) (L . 11) (M . 12) (N . 13) (O . 14) (P . 15) (Q . 16)
    (R . 17) (S . 18) (T . 19) (U . 20) (V . 21) (W . 22) (X . 23) (Y . 24)
    (Z . 25)))

(defun square-alist (alist)
  (letS* ((entry (Elist alist))
          (square (* (cdr entry) (cdr entry))))
    (Rlist (cons (car entry) square))))

(letS* (((key . val) (Elist (square-alist *alist*)))
        (key (symbol-name key))
        (val (format nil "~@R" (1+ val))))
  (Rlist (cons key val)))
;=> (("A" . "I") ("B" . "II") ("C" . "V") ("D" . "X") ("E" . "XVII") ("F" . "XXVI")
;    ("G" . "XXXVII") ("H" . "L") ("I" . "LXV") ("J" . "LXXXII") ("K" . "CI")
;    ("L" . "CXXII") ("M" . "CXLV") ("N" . "CLXX") ("O" . "CXCVII")
;    ("P" . "CCXXVI") ("Q" . "CCLVII") ("R" . "CCXC") ("S" . "CCCXXV")
;    ("T" . "CCCLXII") ("U" . "CDI") ("V" . "CDXLII") ("W" . "CDLXXXV")
;    ("X" . "DXXX") ("Y" . "DLXXVII") ("Z" . "DCXXVI"))

のようなことができます。

Seriesを束縛できるだけでなく、分配束縛機能もあるという優れもの。

さて、このletS*を再現してみようと思ったのですが、色々と難しいところがあります。

まず、square-alistの束縛部のsquareとentryを比べてもらうと分かるのですが、entryはSeriesを束縛していて、squareは、entryの要素にアクセスする格好になっています。

SERIES::*SERIES-IMPLICIT-MAP*を知る前は、どうやって解析したものやらと思ったのですが、これはSERIES::LETの機能にのっかれば簡単にできそうです。

加えて分配束縛機能ですが、これは、DESTRUCTURING-BINDを使えば良いだろうと思いました。

ということで、マクロを組んでいったのですが、Seriesでは、LETやMULTIPLE-VALUE-BINDは用意しているもののDESTRUCTURING-BINDは用意していない様子。

これは、SeriesがDESTRUCTURING-BINDが導入されたCLtL2より前から存在するからかもしれないと思っているのですが、それはさておき、DESTRUCTURING-BINDはLETやMULTIPLE-VALUE-BINDがあれば作れそうなので、処理系のコードを利用し、その中のLETや、MULTIPLE-VALUE-BINDをSERIES::LETや、SERIES::MULTIPLE-VALUE-BINDに書き換えて偽物を作成。

DESTRUCTURING-BINDはSeriesのコードの中では利用されていたので、衝突を回避してdestructuring-bindSという名前で導入することにしました。

そんなこんなで、letS*は

(defmacro letS* (binds &body body)
  (if (endp binds)
      `(progn ,@body)
      (let ((bind (car binds)))
        (if (consp (car bind))
            `(series::destructuring-bindS ,(car bind)
                                          ,(cadr bind)
               (letS* ,(cdr binds)
                 ,@body))
            `(series::let ((,(car bind) ,(cadr bind)))
               (letS* ,(cdr binds)
                 ,@body))))))

のように定義できました。

コードは汚いですが、

にあります。

SERIES::*SERIES-IMPLICIT-MAP*がTでないと機能しませんが、とりあえずは、良しとして、Seriesの理解が深まったら対策したいと思っています。

2010-11-03

*SERIES-IMPLICIT-MAP*の怪

| 23:30 | *SERIES-IMPLICIT-MAP*の怪 - わだばLisperになる を含むブックマーク はてなブックマーク - *SERIES-IMPLICIT-MAP*の怪 - わだばLisperになる

Seriesの先祖であるletS*では、

(defun pairwise-max (list1 list2)
  (Rlist (mapS #'max (Elist list1) (Elist list2))))

というのが、

(defun pairwise-max (list1 list2)
  (Rlist (max (Elist list1) (Elist list2))))

と書けたりします。Seriesで書くとすると、

(defun pairwise-max (list1 list2)
  (collect (#Mmax (scan list1) (scan list2))))

が、

(defun pairwise-max (list1 list2)
  (collect (max (scan list1) (scan list2))))

書けるということらしいのですが、ここで変っている点としては、SCANで生成したSeriesをSeriesを扱う関数でないMAXが受けているように見えること。

なかなか便利なような、思いっきり黒魔術のような感じなのですが、Seriesのソースの中の解説にこういうletSのような書き方ができるオプションについて解説がありました。

解説によると、

SERIES::*SERIES-IMPLICIT-MAP*

を非NILにすれば

(let* ((x (car (scan '((1) (2) (3)))))
       (y (1+ x))
       (z (collect-sum (* x y))))
  (print (list x y 4))
  (print z)
  (collect (list x (catenate #Z(a) (gensym)))))

のような書き方で、

(let* ((x (#Mcar (scan '((1) (2) (3)))))
       (y (#M1+ x))
       (z (collect-sum (#M* x y))))
  (collect-last (#Mprint (#Mlist x y (series 4))))
  (print z)
  (collect (#Mlist x (catenate #Z(a) (series (gensym))))))

と等価になるよ、とのこと。

#M等を使っていた方がなんとなくSeriesかそうでないかをソース上で意識できるので健全な気もしますが面白いです。

ちなみに上記の式は、マクロ展開すると、

(LET* ((#:OUT-35 (GENSYM)))
  (LET (#:ELEMENTS-31
        (#:LISTPTR-32 '(A))
        #:ELEMENTS-1
        (#:LISTPTR-2 '((1) (2) (3)))
        X
        Y
        #:OUT-13
        (Z 0)
        #:ITEMS-28
        (#:FLAG-29 NIL)
        #:OUT-37
        (#:LASTCONS-18 (LIST NIL))
        #:LST-19)
    (DECLARE (TYPE LIST #:LISTPTR-32)
             (TYPE LIST #:LISTPTR-2)
             (TYPE NUMBER Z)
             (TYPE BOOLEAN #:FLAG-29)
             (TYPE CONS #:LASTCONS-18)
             (TYPE LIST #:LST-19))
    (SETQ #:LST-19 #:LASTCONS-18)
    (TAGBODY
     #:LL-38
      (IF (ENDP #:LISTPTR-2)
          (GO SERIES::END))
      (SETQ #:ELEMENTS-1 (CAR #:LISTPTR-2))
      (SETQ #:LISTPTR-2 (CDR #:LISTPTR-2))
      (SETQ X (CAR #:ELEMENTS-1))
      (SETQ Y (1+ X))
      (SETQ #:OUT-13 (* X Y))
      (SETQ Z (+ Z #:OUT-13))
      (PRINT (LIST X Y 4))
      (IF #:FLAG-29
          (GO #:B-23))
      (IF (ENDP #:LISTPTR-32)
          (GO #:F-24))
      (SETQ #:ELEMENTS-31 (CAR #:LISTPTR-32))
      (SETQ #:LISTPTR-32 (CDR #:LISTPTR-32))
      (SETQ #:ITEMS-28 #:ELEMENTS-31)
      (GO #:D-21)
     #:F-24
      (SETQ #:FLAG-29 T)
     #:B-23
     NIL
      (SETQ #:ITEMS-28 #:OUT-35)
     #:D-21
      (SETQ #:OUT-37 (LIST X #:ITEMS-28))
      (SETQ #:LASTCONS-18 (SETF (CDR #:LASTCONS-18) (CONS #:OUT-37 NIL)))
      (GO #:LL-38)
     SERIES::END)
    (SETQ #:LST-19 (CDR #:LST-19))
    (PRINT Z)
    #:LST-19))

のようになってしまいます。

どうもSeriesで定義されているLETや関数などは組み合わさるとマクロ展開で別のものにごりごり変形するようですね…。

2010-11-02

Seriesを引数に取ってSeriesを返す関数

| 23:10 | Seriesを引数に取ってSeriesを返す関数 - わだばLisperになる を含むブックマーク はてなブックマーク - Seriesを引数に取ってSeriesを返す関数 - わだばLisperになる

前回のエイリアスを作ってみた時の

(COLLECT-SUM (EVECTOR #(1 2 3 4)))
Non-series to series data flow from:
(EVECTOR #(1 2 3 4))

のような警告は、どうも最適化の指定が無かったためのようです。

Seriesを引数に取ってSeriesを返す関数は、

(DECLARE (OPTIMIZABLE-SERIES-FUNCTION))

のように指定してあげると最適化指定時には最適化される様子。

OPTIMIZABLE-SERIES-FUNCTIONには整数が指定できて、多値で返すSeriesの個数を指定します(デフォルトは1で省略可能)

この指定をして

(in-package :series)

(defun Rsum (Z)
  (declare (optimizable-series-function))
  (collect-sum Z))

(defun Evector (vector)
  (declare (optimizable-series-function))
  (scan 'vector vector))

と定義したところ

(funcall #'Rsum (Evector #(1 2 3 4)))
;⇒ 10

のようにしても警告は出なくなりました。

そして、この式をマクロ展開すると、

(funcall #'Rsum (Evector #(1 2 3 4)))
;⇒
(CL:LET* (#:ELEMENTS-5
          (#:LIMIT-3 (ARRAY-TOTAL-SIZE #(1 2 3 4)))
          (#:INDEX-2 -1)
          (#:SUM-0 0))
  (DECLARE (TYPE VECTOR-INDEX+ #:LIMIT-3)
           (TYPE -VECTOR-INDEX+ #:INDEX-2)
           (TYPE NUMBER #:SUM-0))
  (TAGBODY
    #:LL-8
    (INCF #:INDEX-2)
    (LOCALLY
        (DECLARE (TYPE VECTOR-INDEX+ #:INDEX-2))
      (IF (= #:INDEX-2 #:LIMIT-3)
          (GO END))
      (SETQ #:ELEMENTS-5
            (ROW-MAJOR-AREF #(1 2 3 4) (THE VECTOR-INDEX #:INDEX-2))))
    (SETQ #:SUM-0 (+ #:SUM-0 #:ELEMENTS-5))
    (GO #:LL-8)
    END)
  #:SUM-0)

となります。

なんでFUNCALLがマクロ展開されるのか、DEFUNで定義した筈のRsumもマクロ等々、色々突っ込みどころは多いですが、とりあえずSeriesを入出力する関数(マクロ)はOPTIMIZABLE-SERIES-FUNCTIONの指定が大事らしいということは分かりました。

また、Series系関数/マクロを定義する場合、関数が良いのかマクロが良いのか悩むこともありましたが、これで悩みも解消(勝手にマクロになってるので…)

2010-11-01

Seriesの関数名が長い

| 02:55 | Seriesの関数名が長い - わだばLisperになる を含むブックマーク はてなブックマーク - Seriesの関数名が長い - わだばLisperになる

Seriesを使ってみると分かるのですが、どうも微妙にSeriesの関数名は長いのです。

(collect-sum 
 (scan-range :from 1 :upto 10))
;⇒ 55

こんな感じに、Seriesを生成→collectでリストの形で収集という流れなのですが、これが色々とネストして行くと、少しの関数名の長さが蓄積していって微妙に冗長になるのです。

このあたりをどうにかできないかなあと思っていましたが、Seriesに先行するLetSというものの関数名が良い感じに短かいのでこれを踏襲してみたらどうだろうとLetSを探りつつ試してみました。

LetSだと上記は、

(Rsum (Erange 1 10))

になります。良い感じの短さ。

Rは、Reducer、Eは、Enumeratorの略の様ですが、ぱっと見た目でも分かり易い気がします。

ということで、エイリアスを定義してみたのですが、エイリアスを使うと

(COLLECT-SUM (EVECTOR #(1 2 3 4)))
Non-series to series data flow from:
(EVECTOR #(1 2 3 4))

のような警告が出ます。エイリアスでは何かが最適化できなくなるようなのですが、この辺りにもSeriesの黒魔術をみる気がします…。