リリカル☆Lisp開発日記

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

『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かエミュレータのどちらかのバグでした。
符号無し整数と符号無し整数の剰余を求めたのに何故か元より大きな数になることがあり、
除算と剰余の代わりにシフトとアンドを使ったところ上手いきました。
無事動作して安心すると同時になんだか悲しい気分を味わえました。

突然4コママンガになった。

内容はともかく、かなり教育マンガっぽくなった。

最近のCコンパイラは末尾再帰の最適化を行ってくれるそうです。
しかし、Cにはポインタがある以上、上手く最適化できない場合もあるよなー
みたいなことを一年ほど前に思いついたんですが、試すのが面倒で放置してました。
それが、今さらになって気になってきたので試してみることにしました。
コンパイラには『gcc (GCC) 4.2.1 20070719 [FreeBSD]』を使用。
まずは、最適化されそうな関数。

int f(int n, int acc) {
if (n <= 0) {
return acc;
}
return f(n-1, acc+nanika(n));
}

これを『gcc -c -S -O2』でコンパイルしたところ、以下のようになりました。

f:
pushl   %ebp
movl    %esp, %ebp
pushl   %esi
pushl   %ebx
subl    $16, %esp
movl    8(%ebp), %ebx
movl    12(%ebp), %esi
testl   %ebx, %ebx
jle     .L8
.p2align 4,,7
.L11:
movl    %ebx, (%esp)
call    nanika
addl    %eax, %esi
subl    $1, %ebx
jne     .L11
.L8:
addl    $16, %esp
movl    %esi, %eax
popl    %ebx
popl    %esi
popl    %ebp
ret

再帰がジャンプになってます。さすがGCC。
で、次は去年思いついてた最適化されなさそうなコード。

int g(int x, int *p, int count)
{
x = 0;
x = *p + 1;
if (count <= 0) {
return x;
}
return g(x, &x, count -1);
}

もし、これがループに置き換われば、一つ前のxがx=0により消されてしまうため、
その後で*pで参照するときにおかしなことになってしまいます。
上と同様のオプションでコンパイルしたところ、以下のようになりました。

g:
pushl   %ebp
movl    %esp, %ebp
subl    $12, %esp
movl    12(%ebp), %eax
movl    16(%ebp), %ecx
movl    $0, 8(%ebp)
movl    (%eax), %edx
addl    $1, %edx
testl   %ecx, %ecx
jle     .L2
leal    -1(%ecx), %eax
movl    %eax, 8(%esp)
leal    8(%ebp), %eax
movl    %edx, 8(%ebp)
movl    %edx, (%esp)
movl    %eax, 4(%esp)
call    g
movl    %eax, %edx
.L2:
leave
movl    %edx, %eax
ret

想像通り、最適化は行われずにcallになっていました。
Cにはポインタがある以上、末尾再帰の最適化は完全には行えないよなー、
という夢のないお話でした。

SLIMEで日本語を扱う方法をnathkiに教えてもらったので、忘れないうちにメモ。
文字コードを.emacsで指定すればいいらしいです。

;;; .emacs
(set-language-environment "UTF-8") 
;;; (中略)
(setq slime-net-coding-system 'utf-8-unix)
(require 'slime)
(slime-setup)

こうしたら日本語がちゃんと扱えるようになりましたとさ。
めでたしめでたし。

まさかの続編。

どのコマから読めばいいのかもはや分からない