リリカル☆Lisp開発日記

*Lisp本*
そろそろ新しくLispの本が一冊くらい欲しいんですが、
Paradigms of Artificial Intelligence Programming
と
Let Over Lambda
で迷っています。
Let Over Lambdaの方が安いし読みやすそうでいいかなと思っているんですが、
日本語訳が出るとか出ないとかいう噂を聞いたので悩んでいます。
Programming Erlangの時みたいにがんばって全部読み終えた頃に日本語訳が出ると悲しい気分になれる…
*カッコイイformatの例*
CLのformatを使ったカッコイイ例って結構ありますよね。
時々「あの例ってどこに書いてあったっけ？」と探し回るので、
忘れないようにメモを書き残しておきます。
まずは、CLTL2より、Lisp Machineのformatの内部ルーチンであるformat-error。

(defun format-error (string &rest args)
(error nil "~?~%~V@T↓~%~3@T\"~A\"~%"
string args (+ *ctl-index* 3) *ctl-string*))

これはformatの引数に誤りがあったときに呼び出され、
次のように表示が行われます。

(format t "The item is a ~[Foo~;Bar~;Loser~]." 'quux)
>>ERROR: The argument to the FORMAT "~[" command
must be a number.
↓
"The item is a ~[Foo~;Bar~;Loser~]."

次に、bit 85年5月号の「Common Lisp入門」より、8クイーン問題の解の出力

(apply 'format t
"~@{~%~V{. ~}Q ~V{. ~}~}"
(mapcan #'(lambda (x)
(list x '( t ) (- 7 x) '( t )))
column))

これはcolumnが(3 1 6 2 5 7 4 0)の場合次のように出力されます。

. . . Q . . . .
. Q . . . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . Q . .
. . . . . . . Q
. . . . Q . . .
Q . . . . . . .

どちらもかっこよすぎ。
しかし、読む人が大変だｗｗｗ
*Syntax Salt*
とある方に、CLでの中置記法の記事[pdf]を読んで頂いたときに行われた会話。
「てっきりSyntax Sugarとか構文糖とかいう言葉が出てくるものだと思ったら出てこないんだね」
『これは本来読みやすいS式を読みにくい中置記法にしてるからSyntax Sugarじゃないんですよ』
「なるほど。じゃあ構文塩なんやね」
構文塩…?
構文糖、糖衣構文、Syntax Sugarにそれぞれ反意語があるとすれば、
それらは構文塩、塩漬構文、Syntax Saltあたりになるんでしょうか。
これら言葉が実在するのか気になったので検索してみました。
そしたらSyntax Saltでひっかかった。

Syntax Salt
古いコンピュータ言語しか知らない中年管理職に売り込む目的で、新しいコンピュータ言語の構文を退化させ、一見古いコンピュータ言語のように見せること。[反対語 = Syntax Sugar]
「例」
オブジェクト指向COBOL
Syntax Saltを振りかけ、本来 A move: Bと書くべきところを move A to Bと書くことを許し、価格を釣り上げた、日経スポーツ愛読者の管理職向けSmalltalkのこと。
(佐原伸　私家版悪魔の辞典より)

とりあえず、ネタ用語としては存在するようです。
糖衣構文という言い方が好きな私としては塩漬構文という言葉を推したい。

前から作っていたポケステ用Lispインタプリタですが、ついに実機で動作しました。

実機ではネストの深いリストを作ると動作がおかしくなってしまいました。
(だから上の動画では簡単な式しか試していません(笑))
関数の再帰呼び出しでスタックが破壊されているんじゃないのかと疑っていますが、
今のところ原因はまだ分かっていません。
でもまあとりあえず動いたので満足してます。

何も言わずにここを見て欲しい。
面倒ならこの画像だけでも見て欲しい。

『LISPマシン・プログラミング技法LISPマシン・プログラミング技法』ですが、
ようやくほとんど読み終えました。何とか返却期限までに全部読めそうです。
忘れないうちに気になったことをメモ。
*stack-let*
Lispマシンは効率に関してかなり気を使っているらしく、色々な工夫がしてあるそうです。
その中の一つにstack-letというマクロがあり、これを使うと変数をヒープではなく、
スタックに割り付けることが出来るそうです。
現在のCommon Lispではdynamic-extent宣言でしょうか。
マクロを使ってこんな風にかけるかと思います。

(defmacro stack-let (bind &body body)
`(let ,bind
(declare (dynamic-extent
,@(mapcar
#'(lambda (b) (if (consp b) (car b) b))
bind)))
,@body))

*エリア*
ページフォルトの回数を減らすために、エリアというものがあるそうです。
オブジェクト(flavorに限らず配列やコンスも)を作成する際に、エリアというものを指定でき、
同一のエリアを指定すれば(可能な限り)同一のページに配置されるそうです。
もちろん新たなエリアを自分で定義することも可能です。

(defvar *my-area* (make-area :name '*my-area*))
(defun create-a-foo (&rest options)
(apply #'make-instance 'foo :area *my-area* options))

このようにしておくと、create-a-fooで作られたインスタンスは
同一のページに配置される(可能性が高い)そうです。
*IP-TCP*
非常にどうでもいい話なんですが、IP-TCPという用語が出てきたんですよ。
今までTCP/IPという表記しか見たことがなかったんですが、
よくよく考えてみたらIPが先でも悪いことはないはずですよね。
どうしてTCPの方が先に書かれるようになったんだろう…

ねんがんの　かきこみきをてにいれたぞ！

『Lispマシン・プログラミング技法』を読んで色々気になったことをメモ。
*ファイルの先頭*
サンプルプログラムのソースに、defpackageは出てくるものの、
in-packageが出てこないので、不思議に思っていたんですが、
第29回慢性的CL勉強会でg000001さんに

Lispマシンでは、ファイルの先頭の行が意味を持つので、
ここでパッケージを指定したりする。

と教えていただきました。
確かに、ソースの先頭の行を見てみると

;;; -*- Mode: LiSP; Syntax: Common-lisp; Package: GRAPHER; Base: 10 -*-

と、いかにも意味ありげなコメントが書いていました。
Lispマシンは基本的に8進数を使うという話を聞いたことがありますが、
上記の様に「Base: 10」を記述しておけば10進数を使えるみたいですね。
*CDR’ing down*
気になったソースとコメント。

(defmethod (delete-self node) ()
;; (borrowed from tv:sheet's :kill method)
;; Do it this way to prevent CDR'ing down list structure
;; being modified
(loop until (null arcs)
do (delete-self (car arcs)))
(setq *all-the-nodes* (delete self *all-the-nodes))

CARを取ってますが、その要素が削除されるためリストを先頭から辿っていくことになります。
当たり前といえば当たり前ですが、LISPではこんなソースを書いたことがなかったので、少々面食らいました。
ところで、”CDR down”という言葉は知っていたのですが、
“CDR’ing down”という言葉ははじめて知りました。
「くだりんぐ」の辺りがリストを下っていく感じがしていいですね。
*パッケージの指定*
現在のCommon Lispでは『cl:car』のようにコロンを使ってシンボルが属すパッケージを
指定することが出来ますが、当時のLisp Machineではもう少し凄いことが出来たようです。

(defparameter
*grapher0display-margin-components*
'dw:((margin-ragged-borders )
(margin-scroll-bar :history-noun "display")
(margin-scroll-bar :history-noun "display"
:margin :bottom)
(margin-white-borders :thickness 2)))

リストに対してパッケージを指定しています。詳しい説明は書いてありませんでしたが、
恐らくリスト内のシンボルが属すパッケージを丸ごと指定しているようです。
*入力できない*
ちょっと笑ったのがこれ。

(format t "~&Didn't find an arc between~
~'I⊂~A~⊃ ~and ~'I⊂~A~⊃"
node1 node2)

入力できないよ( ＾ω＾)
「~⊂」と「~⊃」フォントの変更を行うそうです。
引数に’Iが書いてあるので恐らくイタリック体に変更しているのかと思います。
*フォント*
上に続いてフォントの話。
「(char= char #\a)」という式について以下のような説明がありました。

char=による比較は厳密である。これは(大文字の)Aに対してtを返さないばかりか、
小文字のAに対しても、ファイルの中で異なった文字スタイルをしていたらtを返さない。

そういえばCLTL1では文字型がfontという属性を持っていましたね。
Lispマシンの名残だったのか。
(「ファイルの中で」と書いてあるのはファイルから読み取った文字に対してchar=を使っているためです。)
他にも「引数の名前をignoreにしたら、その引数を使用しなくても警告が出ない」とか、
「declareは無いものの、ほぼそっくりの書き方で型宣言が出来る」など、
色々と気になる話がありました。やはりこの本は面白い。

FlavorとはZetaLispで取り入れられたオブジェクトシステムで、
Lisp MachineでもFlavorが使われていたそうです。
私がFlavorというものをはじめてみたのは「bit 1985年 11月号」の
『Lispマシンのオブジェクト指向プログラミング』
という特集で、そこにはこんな感じのプログラムが書かれていました。

;;; 全部書くのが面倒だったので結構書き換えてます
(defflavor circle (x y r) ())
(defmethod (circle :define) (xi yi ri)
(setq x xi y yi r ri))
(setq c1 (make-instance 'circle))
(send c1 ':define 5 5 10)

メソッドを呼ぶのにsendという関数を使う必要があり、良くも悪くも
「オブジェクトにメッセージを送る」
というのがはっきりしてプログラムを書くものだったんですが、
『Lispマシン・プログラミング技法』
によるとこれは”古い”スタイルらしく^(*1)、
後に次のように書けるようになったそうです^(*2)。

(defflavor circle (x y r) ())
(defmethod (define circle) (xi yi ri)
(setq x xi y yi r ri))
(setq c1 (make-instance 'circle))
(define c1 5 5 10)

sendがなくなり、メソッドが通常の関数と同様に扱えるようになっています。
現在のCommon LispのオブジェクトシステムであるCLOSと同様ですね。

(*1) 新しいスタイルで書けるようになったのはGenera7.0がリリースされた1986年からのようです。
しかし、今となってはこれまた十分に古いですね(笑)
(*2) このようにインスタンス変数を設定するだけであれば、
defflavorのオプションである:initable-instance-variablesを使うことにより、
make-instanceの引数としてインスタンス変数の初期値を設定できます。
これが”古い”Flavorで出来たかどうかは分かりません。

このFlavor、かなり凶悪なもので、sendを使っていた”古い”スタイルの時から既に、
:beforeメソッド、:afterメソッドが定義でき、
:list, :and, :orなどといったメソッド結合も出来たそうです。
メソッドの第一引数がインスタンスに固定されていて、
引数(とそのマッチング)の自由度が低いことを除けば、
今のCLOSと大差がないように見えます。
Flavor恐ろしや・・・

以前、g000001さんに教えていただいた、
『LISPマシン・プログラミング技法』
という本を京大の図書館で借りてきました。
(学外の学生でも普通に借りれました。すごく親切。)
まだ途中までしか読んでいませんが、なかなか面白いです。
「クリック」に対する説明が書いてあるのが時代を感じます。
それにしても、最後に借りられていたのが92年のようなので、
実に17年ぶりの貸し出しのようです。
なんてもったいない・・・

Common Lispにはdisplaced arrayと呼ばれるものがあります。
これは他の配列へのポインタのようなもので、CLHSでは以下のように定義されています。

displaced array n. an array which has no storage of its own, but which is instead indirected to the storage of another array, called its target, at a specified offset, in such a way that any attempt to access the displaced array implicitly references the target array.
(CLHS: Glossary-Section D)

試しに使ってみるとこんな感じです。

CL-USER> (defvar *a1* (make-array 5 :initial-contents '(a b c d e)))
*A1*    ; まずは普通の配列を作ります
CL-USER> *a1*
#(A B C D E)
CL-USER> (defvar *a2* (make-array 3 :displaced-to *a1*
:displaced-index-offset 1))
*A2*    ; 続いて、*a1*をターゲットにしたdisplaced arrayを作ります
CL-USER> *a2*
#(B C D)    ; *a2*の中身は*a1*の部分配列と同じです
CL-USER> (setf (aref *a2* 1) 2009)
2009    ; *a*2の要素を一つ変更してみます
CL-USER> *a2*
#(B 2009 D)    ; 確かに変更されました
CL-USER> *a1*
#(A B 2009 D E)    ; *a1*の方にも影響がでます

これはなかなか面白いですね。
使用する領域も少なそうだし、部分配列を沢山作るような場面では、
displaced arrayを使うと大幅に使用領域を減らせるんじゃないかと思い、試してみました。

(defun s1 (str &optional (n 1))
(let (acc)
(dotimes (i (- (length str) (1- n)) (nreverse acc))
(push (subseq str i (+ n i)) acc))))
(defun s2 (str &optional (n 1))
(let (acc)
(dotimes (i (- (length str) (1- n)) (nreverse acc))
(push (make-array n :displaced-to str
:displaced-index-offset i
:element-type (array-element-type str))
acc))))

という訳で、意味はありませんが、とにかく部分配列を沢山作る関数を二つ用意しました。
引数は作成する配列の一つあたりのサイズです。
s1はsubseqを使い、配列のコピーを作るのに対して、
s2はdisplaced arrayを作るようにしています。
で、CLISPで両者を動かしてみました。

CL-USER> (time (progn (s1 *long-long-text* 1) nil))
Real time: 0.0200288 sec.
Run time: 0.0200288 sec.
Space: 112420 Bytes
NIL
CL-USER> (time (progn (s2 *long-long-text* 1) nil))
Real time: 0.0100144 sec.
Run time: 0.0100144 sec.
Space: 179872 Bytes
NIL
CL-USER> (length *long-long-text*)
5621
CL-USER> (time (progn (s1 *long-long-text* 100) nil))
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 640552 Bytes
NIL
CL-USER> (time (progn (s2 *long-long-text* 100) nil))
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 176704 Bytes
NIL
CL-USER> (time (progn (s1 *long-long-text* 1000) nil))
Real time: 0.0901296 sec.
Run time: 0.0901296 sec.
Space: 4695952 Bytes
GC: 4, GC time: 0.0600864 sec.
NIL
CL-USER> (time (progn (s2 *long-long-text* 1000) nil))
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 147904 Bytes
NIL

サイズ1の配列を作る場合はsubseqの方が使用領域が少ないですが、
サイズが大きな配列を作る場合はdisplaced arrayの方が圧倒的に少なくなりました。
Common Lispは(純粋)関数型言語のように副作用をあまり使わないプログラムが書ける一方で、
領域を共有するようなメモリを節約するプログラムも書けるのがいいですね。

あけましておめでとうございます。今日から2009年ですね。
ところで、今から10年前の1999年はポケステが発売した年です。
という訳で、ポケステ発売から10年^(*1)を記念して、
プログラムの書初めとして、ポケステ用Lispインタプリタを作りました。
(*1) ちなみに、生産は2002年で終了しています。
電池がすぐに切れることで有名になったハードだからそんなもんですかね(笑)
私も2回ほど電池交換をした後に面倒になり、ただのメモリーカードとして使いました。
メモリーカードとしてはいまだに現役ですが、ゲーム機としては使っていません(笑)


残念ながら書き込み装置がないので実機ではなくエミュレータです。
実機で動くかは残念ながら不明です。
画面は小さいですが、256文字までの式を入力可能です。

RAMが非常に小さいため、使用できるセルの数は少ないですが、
GCをちゃんと付けたので、ちょっとした再帰なら耐えれます。
この画像からは分かりにくいですが、リストを反転させる関数を定義して呼び出しています。
末尾再帰的に書いていますが、残念ながら末尾再帰の最適化までは付いていません。
そんなこんなで今年最初のLispインタプリタでした。

ポケステ向けプログラミングというのは10程年前には結構流行っていたらしいですよ。
残念ながら当時小学生だった私はまだプログラミングはしていませんでした。
ポケステは32bitのARMを搭載しており、GCCでプログラムを作ることが出来ます。
1999年当時資料を載せていたWebサイトの多くは閉鎖してしまったようですが、
今も簡単な資料や自作プログラムのソースを公開しているサイトが残っているため、
そちらを参考になんとかLispインタプリタを作り上げることが出来ました。
でも、実はこれ去年中につくるつもりだったんですよね…
30日にインタプリタの核の部分が出来上がり、31日の午前中にはGCが完成しました。
で、ここからARM用のGCCを使ってエミュレータでテストを始めたんですが、
どうしてもインタプリタ一部の処理が上手く動きませんでした。
半日かけて原因を探したんですが、結局分からず今年に持ち込んでしまいました。
で、原因はというと、(恐らく)GCCかエミュレータのどちらかのバグでした。
符号無し整数と符号無し整数の剰余を求めたのに何故か元より大きな数になることがあり、
除算と剰余の代わりにシフトとアンドを使ったところ上手いきました。
無事動作して安心すると同時になんだか悲しい気分を味わえました。