Lispの国に行きたくて

Land of Lispを読了

Land of Lispをひと通り読んで掲載されたコードを動かしてみた後,ちょっとだけ簡単なコードで遊んでみた.中盤までは読み終わったら早速なにかつくろうと思っていたのだけれど後半の内容が結構重くて理解が難しかったところも結構あったため,結構な読了感でちょっとしたコードで遊ぶくらいの気持ちしかわかなかった,というのが正確だけど.

Land of Lisp

Land of Lisp

これから読む人は,Dice of Doomのゲーム木のフラクタルチックな構造が頭の中でヴィジュアルに思い浮かべられるようになるまで眺めれば,多分引っかからないで最後まで行けると思うよ?そこがクリアできればこの本で一番の難関は間違いなく開発環境を作るところ.CLISPを使うとしか書いてないけどCLISPだけじゃとてもじゃないけどコーディングできないって言う.開発環境に関してほとんど全くと行っていいほど説明がない以外は,教科書としてかなり秀逸な構成になってるように感じる.訳もかなり良かった.ハッカーと画家でも川合史朗さんの訳読んだけれど,どちらもリズムが良くてかつわかりやすい良訳.

遊びながら作ったガラクタ

ということで,なんの役にも立たないけどちょっとだけ本書で書かれてたことを反映したガラクタを紹介.

フィボナッチ数列のn番目に評価される関数

(let ((acc (make-hash-table)))
   (defun fib (n)
      (cond ((zerop n) 0)
            ((eq 1 n) 1)
            ((minusp n) nil)
            (t (or (gethash n acc) (setf (gethash n acc) (+ (fib (1- n)) (fib (- n 2)))))
               (gethash n acc)))))

クロージャを使ってハッシュテーブルを参照するので,loopマクロを使って順番に呼びだせばメモリが許す限りスタックオーバーフローを起こさずに計算します.処理系によってはGCがエラーを吐く模様.

> (loop for n to 200000
     do (fib n)
     if (eq n 200000) do (format t "~a" (fib n)))

//前略
574322186287559282059723208383808531011618825713740726934434742559093323706126196002712537368795203860187900060895217407977181945388053286947239052473752453296225053538805624817479197417467060417752514347515076498182239531088303954238221549351009970624402084900272950782638693852022231142741503929713071110792074068146485179081595572528904785663877616462653669462689359261747364212532866024476944192614519310076109974861926126352359630329214201957704677119789193142654798777312450935031089429802652246259408175853125

>

うちの環境だと200000まで計算するとメモリを1.6GBほど使います.二回目以降はハッシュテーブルから持ってくるだけだから処理が早いという利点はあるけど青天井にメモリを使ってしまいます.

さすがに頭が悪いのでアキュームレータを引数として取るローカル関数を定義して,アキュームレータにフィボナッチ数列の0番目と1番目の要素である0と1を渡して再帰呼出し.呼び出されるごとにnをデクリメントしてnが0の時のacc2の値がn番目の要素.

(defun fib (n)
  (labels ((f (n acc1 acc2)
             (cond ((minusp n) nil)
                   ((zerop n) acc2)
                   (t (f (1- n) (+ acc1 acc2) acc1)))))
     (f n 1 0)))
> (fib 200000)

//前略
574322186287559282059723208383808531011618825713740726934434742559093323706126196002712537368795203860187900060895217407977181945388053286947239052473752453296225053538805624817479197417467060417752514347515076498182239531088303954238221549351009970624402084900272950782638693852022231142741503929713071110792074068146485179081595572528904785663877616462653669462689359261747364212532866024476944192614519310076109974861926126352359630329214201957704677119789193142654798777312450935031089429802652246259408175853125

>

CLISPだと(compile 'fib)して末尾呼び出し最適化しないとダメでした.sbclならそのまま行けます.

非負整数の引数の階乗に評価される関数

(defun factorial (x acc)
   (if (zerop x)
       acc
       (if (minusp x)
           nil
           (factorial (1- x) (* acc x)))))

やってることはフィボナッチの二番目と同じ.

これから

マクロは上に上げたものよりつまらない実験しかしてないので紹介しませんがマクロやクロージャで遊んでたらなんか色々できそうな気がしてきたのでなにか作ってみたいなと感じています.レポート書くときにCで数値計算させてLaTeXのテーブルを出力するくらいしかプログラムしたことがないから,Noobが(あえて)Lispでなにか作るてきなことをやってみようかなって思ってます.(今思えばよくCでやってたなと思わなくもない)

感想

はてなシンタックスハイライト強い!!!