ということで、最近出版したＣＯＭＭＯＮ ＬＩＳＰの教科書の内容ですけれども、英語で書いた紹介ページがあるんでそっちをみればわかりまーす
primitive-lisp.blog.so-net.ne.jp
以上！
というわけにもいかないので、日本語でも説明しようと思います。とりあえず本の前半は基本ですね。プログラミングというのはなんなのか、とかＬＩＳＰっていうのはどういうプログラミング言語なのか、ということを説明した部分です
でもそういう部分は一目みたら一瞬でわかるというものでもないので、ＬＩＳＰをつかったらこういうことができるよ！ ということを説明した後半部分の紹介をしたいと思います
でもその前にこれはＰＲしておかないとですね
以下の説明を見たらわかると思いますがこの本は外部のライブラリーを一切使ってないです。あ、コンピューターについて詳しくない人のために説明すると、外部ライブラリーというのは要するに他人の書いた（実質的にはブラックボックスの）プログラムのことです
もう入門書で外部のライブラリーを使うやつがあればそれだけで読む気失せますからね。だってはっきりいって外部ライブラリーを使ったとしたら、まずプログラミングの原理以前にそのライブラリーの使い方を勉強しないといけない
プログラミングの勉強はただでさえ面倒そうなのに、そのうえライブラリーの勉強するなんて冗談じゃないわけですよ。だって勉強したいのは言語の勉強で、このあと自分が使うかどうかもわかんないライブラリーの勉強ではないからね
ライブラリーを使えるようにするのも面倒だし、だいたいインストールしてうまく動作するという保障もない
まあそういうわけでこの本は外部ライブラリーを一切使ってないです。処理系インストールすればいいだけ
それから重要なのは、この本はものすごい読みやすいです。それは内容もそうあるように心がけましたけれども、まず視覚的に読みやすいんです
もしかして、これが予の教科書の一番の売りかもしれない
これは本気ですから。予は目がよく見えなくて苦労した時期が長かったんで、読みにくい電子書籍には我慢がならない
きちんとインデントがかかるのはもちろん、文字もかなり大きくできるようにレイアウトしてます。これはかなり苦労しました
なんで、その点について心配がある人も安心して読めると思います
ということで、紹介の方にうつりたいと思います
マークダウン
プログラマーでないかぎりマークダウンなんて聞いたこともないと思いますが、これは文書をテキストファイルで表現するための記法のことです。文書をワープロなしで作る方法といってもいいでしょう。たとえばですね
# 大見出し ## 小見出し 文章・・・・
というテキストファイルがあるとします。このファイルをマークダウンを処理するプログラムにかけると、マークダウン記法に書いた通りの内容のファイルが出力されます。それはＨＴＭＬでもＭＳ Ｗｏｒｄのファイルでもいいですが、この出力ファイルをブラウザなりＭＳ Ｗｏｒｄなりで見れば、大見出しは大見出しに、小見出しは小見出しになっています
大見出し
小見出し
文章・・・・
↑こんな感じね
便利でしょ？いちいちワープロなんか使わなくても一文字二文字＃を書くだけで見出しが作れる。しかもワープロがなくても文章の内容が確認できるわけ。見出しのほかにも表とかリストなど、いろいろ作ることができます
もっとも、予の本で取り上げたマークダウンというのは普通のマークダウンとは少し違います。というか全然関係ないです。マークダウンと全く同じことができるというだけでマークダウンといってるだけ
ただね、予の考えた記法というのはマークダウンよりも遥かに強力です
というか、この本にのってるプログラムは予がこの本を作るために作ったものです
電子書籍作るにはまずePubファイルというものを作るんですが、これは基本的にはHTMLファイルです。つまり電子書籍リーダーというのはブラウザーの一種です
HTMLというのは<とか>,&を使って表すものなんですが、そうすると<とか>自体をブラウザーで表示するにはどうするか、ということになるので、これらの記号はHTMLファイルの中ではそれぞれ< > & と表記されます（HTMLというのが何であるかは本の中で説明するので安心してください）
だから電子書籍にこういう記号がでてきたら全部置き換えることになります。それが一か所二か所だったらいいですけれども、プログラムの本とかだったらこういう記号が数えきれないくらい出てくるのでプログラムを使って自動的にやらないとやってられません。だって本にHTMLデータが出てきたらどうしますか？絶対無理でしょ
それで次のような変換をするプログラムを書きました（実際は高速化のため、あまり使わないタグは省くんですけど）
#html# => <html> #/html# </html> #h1# <h1> #/h1# </h1> #h2# <h2> #/h2# </h2> #p# <p> #/p# </p> #pre# <pre> #/pre# </pre> < < > > & &
こういう変換をすることによって記号が衝突するのを回避することができるわけです。別にHTMLタグというのは<とか>を使わなくても表記できるわけですね
しかしこのような単純な変換で処理できないHTMLタグがあるので、そのために ## で囲んだ部分は変換されないようにしました
とりあえず例をみてみますかね
#html#
##<style>p{font-size: x-large; color: mediumslateblue;}</style>##
#h1#Chapter 1#/h1#
#h2#Section 1#/h2#
#p#This is an emphasised text#/p#
#h2#Section 2#/h2#
#pre#
(defun & (x y) (and x y))
=> &
(defun f (x)
(& (> x 0)
(< x 10)))
=> F
(f 4) => T
(f 12) => NIL
#/pre#
#/html#
これが予の書いたプログラムだと次のように変換されます
<html>
<style>p{font-size: x-large; color: mediumslateblue;}</style>
<h1>Chapter 1</h1>
<h2>Section 1</h2>
<p>This is an emphasised text</p>
<h2>Section 2</h2>
<pre>
(defun & (x y) (and x y))
=> &
(defun f (x)
(& (> x 0)
(< x 10)))
=> F
(f 4) => T
(f 12) => NIL
</pre>
</html>
=> NIL
これをブラウザーで表示させると次のようになります
なんか一部スペリングがヨーロッパですけれども。このプログラムを書いた後は原稿の編集作業が劇的に楽になりました
技術的には、辞書に基づいて変換する部分と変換しない範囲を定める部分をすっきりと分離させることが難しかったです。ここでつかったトリックはかなり気に入ってます
３Ｄアニメーション
いかにも難しそうな感じしませんか？ところがこれ、基本的な部分はおどろくほど簡単です。まず以下の図をみてください
ここで距離が１だけ離れている直線を画面とすると、物体の画面上の位置というのは物体の位置を奥行きで割ったものになります。上の例でいうならx/dですね。３次元の例でいうと、もし物体の座標が(x, y, z)だとするとスクリーン上の物体の位置は(x/z, y/z)になります
それから３次元のＣＧというと物体がぐるぐる回転するやつですね。これもびっくりするほど簡単に回転できるんです。以下の図をみてください
z軸の回転について考えてみましょう。ex'とey'はexとeyから求められることがわかります。sinとcosを使って、新しい軸を以前の軸から計算すればいいだけ。あとは他の軸についても同じことをすればいいだけです
本当にこんな簡単でいいの？
と思いますよね。やっぱ実際に見てみないことにはわかんないですからね
こんな感じですかね
本来は３Ｄアニメーションの話題をいれるつもりはなかったんです。物体のデータが複雑すぎると思いました
でも３Ｄアニメーションを扱うことにしたのは、これを書いているときがコンピューター教育の現状にかなり腹を立てていた時期だったんです。何かガツンと言ってやらないといけないと思いました
しばらく考えて思いついたのは、２次元の物体を３次元空間に置けばいいじゃん！ということです。それでなんとかなりましたけれども、この企画を形にするのは大変といえば大変でした。奥行きで割るという話も自分で考えたんだよね
次の日の朝になって１０年前に同じ話を本で読んだことを思い出したんですけど
天体の運動
太陽の周りをぐるぐる回っている惑星というのは楕円軌道の上を回っているという話はどこかで聞いたことがあると思うんです。え？ 聞いたことない？ ・・・それはちょっとヤバイかもですね。まあ予のブログにアクセスするような人がこの話を知らなかったら、そっちのほうがビックリですけれども
LISPを使ったら本当に軌道が楕円になるのかを簡単に確かめることができます。もともとLISPは数学的なバックグラウンドをもつ人たちが使ってたものなんで、数学的なことを扱うのが非常に得意なんです
とりあえず計算結果をいくつか貼っておきましょうか
だれがどうみても楕円ですね。これ、プログラマーでも実際に計算したことある人はそんなにいないんじゃないでしょうか
ステップを大きくとってもそれなりの精度で計算します
この章を書くのは大変でした。まず運動を説明するのに微積が使えない。微積の話をすると極限の概念を説明することになるけど、これをうまく説明する方法が見つからなかった。しかも２次元ですからね。なんとか微積なしで説明する方法を考えましたけど
あとは精度の問題。ふつう、こういう計算をするにはルンゲ・クッタ法というダサイ方法を使います。でも予はルンゲクッタはどうしても使いたくなかった。だってダサイから
しかし、２次で近似するとやっぱり不正確なんですよね。楕円軌道というのは結構不安定なんで。解析力学という学問の結果を使ったもっと深遠な方法もあるんですけど、これを使うと女子高生さんとOLさんはたぶん読めないですからね
まあ、なんとか解析力学でもルンゲクッタ（あるいはルンゲクッタもどき）でもない方法を見つけることができました
コンパイラ
PostScriptって聞いた事ありますか？デザインやっている人ならだれでも知っていると思うけれども、これはPDFの先祖です。１９８４年発表ですから今から３０年くらい前の規格ですね
発表当時、これはものすごい革命的なテクノロジーだったんです。どういうテクノロジーかというと、たとえばプリンターかなんかに図形などを描かせるときに、プリンターにこういう動作をしなさい！という制御プログラムを送るんです
たとえば、ここからここまで線を引きなさい！それからこの位置にこういう大きさでこういう文字を描きなさい！それからそれから・・・という感じです
この方法のどこが素晴らしいかというと、まずデータの量が少なくてすみます。ここからここまで線を引きなさい。というコマンドなんて数十文字のデータで伝わります。それから将来新しいプリンターなどが発売されても問題なし。より美しい線が引けるだけのことです
ということで、PostScriptファイルというのはプログラムです。PostScript言語というプログラミング言語があって、PostScriptファイルにはPostScript言語のプログラムが書かれているわけです。なのでテキストエディターで直接、PostScriptファイルを書くこともできます。そうすることで理屈の上ではあらゆる図形を描くことができます
PostScriptというのはすごい原始的な言語です。だれでもわかります。ただ原始的すぎてちょっと、というかかなり使いにくいんだよね（あ、もちろんPostScriptの説明はぜんぶ本のなかにあります）
ということでLISPのプログラムをPostScriptにするコンパイラを作りました。以下の例を見てみましょう
CL-USER> (_lc '(defun f (x)
(if (eq x 1)
1
(add 1 (f (sub x 1)))))
"d:/f.ps")
/f { 1 dict begin /x exch def x 1 eq { 1 } { 1 x 1 sub f add } ifelse end } def
NIL
これは1 + 2 + .. +ｘを求めるLISPのプログラムをPostScriptにして、結果をd:/f.psというファイルに出力したところです。これをPostScript処理系に読みこませると次のようになります
GS>(d:/f.ps) run GS>10 f = 55
複数の関数を一気にコンパイルするlcというのもあります。たとえば以下のデータを記録したprime-numbers.lというファイルがあるとします
(defun a-seq (a b n)
(if (eq n 0)
/nil
(cons a (a-seq (add a b) b (sub n 1)))))
(defun pn (xs)
(if (eq xs /nil)
/nil
(cons (car xs)
(pn (thru xs (car xs))))))
(defun thru (xs a)
(cond ((eq xs /nil)
/nil)
((eq (mod (car xs) a) 0)
(thru (cdr xs) a))
(true
(cons (car xs) (thru (cdr xs) a)))))
これは次のようにしてコンパイルできます
CL-USER> (lc "d:/prime-numbers.l" "d:/prime-numbers.ps") NIL
そうすると以下のようなd:/prime-numers.psというファイルができます
/a-seq { 3 dict begin /n exch def /b exch def /a exch def n 0 eq { /nil } { a a b add b n 1 sub a-seq 2 array astore } ifelse end } def
/pn { 1 dict begin /xs exch def xs /nil eq { /nil } { xs dup /nil ne { 0 get } if xs xs dup /nil ne { 0 get } if thru pn 2 array astore } ifelse end } def
/thru { 2 dict begin /a exch def /xs exch def xs /nil eq { /nil } { xs dup /nil ne { 0 get } if a mod 0 eq { xs dup /nil ne { 1 get } if a thru } { true { xs dup /nil ne { 0 get } if xs dup /nil ne { 1 get } if a thru 2 array astore } if } ifelse } ifelse end } def
これを使って素数を計算できます
GS>(d:/prime-numbers.ps) run GS>2 1 99 a-seq pn == [2 [3 [5 [7 [11 [13 [17 [19 [23 [29 [31 [37 [41 [43 [47 [53 [59 [61 [67 [71 [73 [79 [83 [89 [97 /nil]]]]]]]]]]]]]]]]]]]]]]]]]
もちろん図形も書くことができます
こんな感じです
このプログラムもこの本を書くために書きました。この本にでてくる図はぜんぶこのコンパイラを使って作ったものです。上にでてきた３Dアニメーションの図なんかそうですね
本を書き始めて困ったのが、図をどうするか、ということです。もちろんそんなのは適当なイラストレーターもどきで作れるわけですが、どうもそういうドローイングソフトで描きたい図形が得られるか疑問だったんですよね
そういうドローイングソフトは正確な図を描くためにできてないですから
それで思い出したのがPostScriptのことです。これを使えばどんな画像でも描きたい放題です。んで、いろいろネットをみているうちに、これはコンパイラ書けるなと思いました
難しかったのはCONSセルを要素数２の配列で表現できることに気づくところですかね。PostScriptには型がないから、配列を配列の要素にできます。わかってしまったら当たり前のことですけれども、普通にPostScriptの言語仕様を勉強していると結構わからないと思います
あと、PostScriptには変数の値を決めるためにdefとstoreという２つの命令があるんですけれども、storeというのはほとんど知られてないんですね。defだけでは問題があるとわかった時は相当あせりました
そのほかには空リストの扱いでしょうか。carとcdrをどう実装するかということです
ということで結論ですが、コンパイラ組んで大正解でした。はっきりいってコンパイラないと
やってらんねーよ
ということです
あれを自分で書くなんて頭おかしくなりますよ。LISPというのはほんと、文字通り誰でも処理系がつくれますからね
ほんとLISP使っててよかったと思いました
Huffman/LZデータ圧縮
データ圧縮って不思議だと思いませんか？ ネットみても結構情報ないんですよね。いやあるにはあるんでしょうが、データ圧縮の専門家しかわからなそうなものばっかり
この章ではハフマン符号化だけでなく、ハフマン符号化とLZ圧縮を組み合わせた方法を議論します
とりあえず例ね。以下のデータは皆さんおなじみの（でもないかもだが）アメリカ合衆国憲法の一部です
We the People of the United States, in Order to form a more perfect Union, establish Justice, insure domestic Tranquility, provide for the common defence, promote the general Welfare, and secure the Blessings of Liberty to ourselves and our Posterity, do ordain and establish this Constitution for the United States of America. Article. I. Section. 1. All legislative Powers herein granted shall be vested in a Congress of the United States, which shall consist of a Senate and House of Representatives. Section. 2. The House of Representatives shall be composed of Members chosen every second Year by the People of the several States, and the Electors in each State shall have the Qualifications requisite for Electors of the most numerous Branch of the State Legislature. No Person shall be a Representative who shall not have attained to the Age of twenty five Years, and been seven Years a Citizen of the United States, and who shall not, when elected, be an Inhabitant of that State in which he shall be chosen. Representatives and direct Taxes shall be apportioned among the several States which may be included within this Union, according to their respective Numbers, which shall be determined by adding to the whole Number of free Persons, including those bound to Service for a Term of Years, and excluding Indians not taxed, three fifths of all other Persons. The actual Enumeration shall be made within three Years after the first Meeting of the Congress of the United States, and within every subsequent Term of ten Years, in such Manner as they shall by Law direct. The Number of Representatives shall not exceed one for every thirty Thousand, but each State shall have at Least one Representative; and until such enumeration shall be made, the State of New Hampshire shall be entitled to chuse three, Massachusetts eight, Rhode-Island and Providence Plantations one, Connecticut five, New-York six, New Jersey four, Pennsylvania eight, Delaware one, Maryland six, Virginia ten, North Carolina five, South Carolina five, and Georgia three. When vacancies happen in the Representation from any State, the Executive Authority thereof shall issue Writs of Election to fill such Vacancies. The House of Representatives shall chuse their Speaker and other Officers; and shall have the sole Power of Impeachment.
これをこの本にのってるプログラムで圧縮して解凍すると、以下のような結果を得ます。 / で囲まれた部分が圧縮されていた部分です
We the People of the United States, in Order to form a more perfect Union, establish Justice, insure domestic Tranquility, provide for the common defence/, pro/mot/e the /general Welfare, and secur/e the /Blessings of Liberty to ourselves and our Poster/ity, /do ordain and/ establish /this Constitution/ for the //United States/ of America. Article. I. Section. 1. All legislative Powers herein granted shall be vested in a Congress/ of the United //States, /which/ shall /consist of a Senate and House of Represent/ative/s/. Section. /2. The/ House of Repre//sentatives// shall be /composed of Members chosen every second Year by/ the People of /the several/ States, /and the Electors in each/ State// shall /hav/e the /Qualifications requisit/e for //Electors //of the /most numerous Branch/ of the //State /L/egislat/ure. No Person/ shall be /a/ Representative/ who/ shall /not/ have /attained to the Ag/e of t/wenty five/ Year//s, and /been seven/ Years/ a Citizen/ of the United //States, and //who shall not/, when elected, be an Inhabitant/ of th/at/ State /in/ which /h/e shall /be/ chosen/. /Representatives/ and direct Tax/es shall be /apportioned among/ the several St/ates/ which /may be included within/ this //Union, /according/ to the/ir respective Nu/mbers//, which shall /be determined by ad/ding to the/ whol/e Number/ of free/ Person//s, in/clu/ding t/hose bound to Servic/e for /a Term of/ Years, and /ex/cluding /Indians not taxed, three fifths of all other/ Persons/. The actual E/numer/ati/on shall be /made/ within th/re/e Years/ afte/r the /first Meeting/ of the //Congress of the// United States,// and w//ithin //every s/ubsequent/ Term of /t/en Years/, in such Manner as they/ shall b/y Law/ direct//. The //Number of //Representatives// shall not /exceed on/e for //every /thirty Thousand, but/ each State sha//ll have /at Least one/ Representative/; and until/ such /e/numeration shal//l be made/,/ the State /of New Hampshir/e shall be /entitl/ed to /chuse/ three/, Massa/chuse/tts eight, Rhode-Island and P/rovide/nce Plant/ations /one, Connecticut/ five/, New-York six/, New/ Jersey four, Pennsylvania/ eight, /Delaware/ one, /Mary/land //six, /Virginia ten, North Carolina/ five, /Sou/th Carolina fiv//e, and /Georgia/ three/. When vacancies happen in th/e Representati/on from any/ State//, the /Executive Authorit/y the/reof/ shall /issue Writs of/ Elect/ion to fil/l such /V/acancies//. The House of// Representative//s shall //chuse th/eir Speaker and/ other /Officers/; and //shall have the /sol/e Power/ of Impeachment.
かなり強烈に圧縮がかかっているのがわかりますね。これはデータ量にして５６パーセント減少します。もとのデータ量の４４パーセントになるということですね
これも予にはかなり難しかったです。スライド辞書のデータとハフマン符号化された文字のデータ、どう区別すればいいのか？ ネットを見てもわけがわからないし、面倒だから自分で考えたんだけど、よくわかんなかった
でもある日、ふらふら廊下を往復しながらそのことを考えてたときに突然わかったんです。スライド辞書のデータを開始するトークン（しるし）をハフマン木に入れてやればいいんだというね。その瞬間は結構おぼえています
これがわからなかったら、データ圧縮を取り上げるという企画はボツだったと思います。ハフマン圧縮だけではどうしようもないですから
内容としてはそんなところです
これを書くのには３年以上かかってます。一つのテーマが終わりかけて、これで出版になるな、と思っているうちに次のテーマを思いつくんです。それを数か月かけてちんたらやって、そろそろ終わりかな、と思ったらこれもやるか、ということになるという
２１章の本を書く予定では全くなかったです
本を書いてた３年間、コンピューター関連の本は一冊も読んでないです。これを機会にいままで適当に理解していたことを徹底的に考えようと思ったんですが、なんか本には自分が本当に知りたいことは絶対に書いてない！という確信があったんです
だからこの本の内容は、文字通り３年間で考えたことのすべてです。本をみてカンニングした部分は一ヵ所もないんで、相当わかりやすいはずです。わかりやすくないと、そもそも自分自身がわからないですからね
とにかく、ものすごい勉強になりました。本が売れる前の時点でもとは取ったという感じでしょうか
おわり！