LISPUSER

LISPMEMOQ: How can you tell when you've reached Lisp Enlightenment?
A: The parentheses disappear. -- Anonymous

(top)  (memo)  (rss)

作って学ぶ Lisp (1) 超やさしいLispインタプリタの作り方

この記事は書きかけです

Lisp 普及を目指しているのに、まず入門記事がないのはどうよ?とか言われて、 グサっときたので。他の言語の入門記事より Lisp の特徴を前面に出していこ うということで、「Lisp を作りながら Lisp を学ぶ」を目指します。 いま入手できる Lisp 処理系ってほんとうに良くできているものが多いのですが、 自分でつくってみると、「本物」のすごさが良くわかるようになるでしょう。

ネタ元: Java で 500 行の Lisp にインスパイアされました。

http://itpro.nikkeibp.co.jp/article/COLUMN/20060922/248738/ (http://d.hatena.ne.jp/textfile/20061204/lisp 経由)

ちょっと探してみると http://tociyuki.cool.ne.jp/archive/index.html とか http://www.biostat.wisc.edu/~annis/creations/PyLisp/ とかありますが、 Lisp をやるなら Lisp がいちばん!!

100 行程度で超シンプルな Lisp インタプリタを作成してみます。 オリジナルの Java 版と同様にマクロはないですが、短かくてもちゃんとクロージャは備えています。 (Lisper な人には断わっておきますが、 Lisp-1 です)

実装方針:

  1. S 式を直接解釈していくインタプリタ
  2. 関数と名前空間は同一
  3. 環境はグローバルな環境と、レキシカルな環境の二本立て

Lisp の基礎

すいません、本か Web で自習してください。一応必須の知識だけ超特急で列挙します。 もちろん他の言語をすでに知っていて、自習しなくてもここに書いてある事が理解できるようなら さっさと先に進んでもらっても結構ですが。

Lisp の概要

Emacs から SLIME を起動すると (http://lispuser.net/emacs/lisphacking.html , http://lispuser.net/commonlisp/clisp.html 参照) 、 CL-USER> というプロンプトが表示されていると思います。

CL-USER> 

ここに、プログラムを入力することで、 Lisp にプログラムを解釈させて結果を確認することができます。 さっそく Lisp にプログラムを実行させてみましょう。

CL-USER> (+ 1 2)
3

これは、 1 + 2 を計算させるプログラムです。 (+ 1 2) の意味は、関数 + パラメータとして 1 と 2 を渡す、という意味になります。 乗算を行いたい場合には関数 * を使用してみてください。

CL-USER> (* 3 4)
12

もちろん、式を入れ個にする事もできます。

CL-USER> (+ (* 2 4) (- 3 1))
10

アトム

Lisp の最も基本的なデータ型です。大抵の言語に備わっているような、数値、文字、文字列がこれに相当します。 Lisp と特色として、「シンボル」というアトムがありますが、これについては別途説明します。その他に、真偽を表す値として t と nil が存在します。

CL-USER> 10 ; 整数
10
CL-USER> -5 ; 整数
-5
CL-USER> 12.01f0 ; 単精度小数
12.01f0
CL-USER> 12.01d0 ; 倍精度小数
12.01
CL-USER> #\h ; 文字
#\h
CL-USER> #\あ  ; 文字 (Unicode 対応処理系のみ)
#\HIRAGANA_LETTER_A
CL-USER> "hello" ; 文字列
"hello" ; ← 文字列
CL-USER> t ; 真を表すシンボル T
T
CL-USER> nil ; 偽を表すシンボル nil
NIL

シンボル

アトムの一部ですが、数字や文字列のようなどの言語にでもあるデータ型とはちょっと違います。 シンボルを直接入力すると、Lisp はそのシンボルを 評価(eval) して「値」を参照します。シンボルは日本語の「それ」や「あれ」に 相当するものだと考えましょう。単に「それ」というだけでは、何の値も差していないため、エラーとなります。

CL-USER> それ
The variable それ is unbound.  ;; Lisp が「それ」ってなんだよ!! と文句たれてる

評価を停止して「それ」そのものを表すにはクォート ( ~'~ ) を使用します。クォートは評価を停止します。これ重要。

CL-USER> 'それ
それ

Common Lisp での代入構文は setf という名前です。この構文を使ってシンボルに値を束縛することができます。 「あー、 そこの果物それりんご 」 と言えば、それ以降「それ」は「りんご」を差すようになります。

CL-USER> (setf そこの果物 'りんご)
りんご
CL-USER> そこの果物
りんご
CL-USER> (setf それ そこの果物)
りんご
CL-USER> (setf それ 'そこの果物)
そこの果物
CL-USER> それ
そこの果物
CL-USER> (eval 'そこの果物)
りんご
CL-USER> (eval それ)
りんご

さて、これがどんな意味を持つのでしょう?言葉で説明すると厄介です。 鏡の国のアリスにもこんなフレーズがあります。

「それともなに?」とアリス。騎士(ナイト)が急に口を止めたからです。
「それとも浮かべないか、だよ。この歌の名前は『タラの目』と呼ばれてるんだ」
「ふーん、そういう名前なんですかぁ」とアリスは、なんとか興味を持とうと努力して申しました。
 騎士(ナイト)はちょっといらいらしたようすで言います。
「いやちがうよ、わかんないかな。それは歌の名前がそう呼ばれているっていう話。名前そのものは『すごく歳寄りの男』なんだ」
「じゃあ、『その歌はそう呼ばれてるんですかぁ』って言うべきだったのね、あたしは」とアリスは自分を訂正しました。
「いいや、べきじゃない。そりゃまったく別の話だよ! 歌は『方法と手段』って呼ばれてるんだ。
でも、これはそれがそう呼ばれてるってだけなんだよ、わかる?」
「じゃあそれなら結局、歌そのものはいったいなんなの?」この時点でアリスは、もう完全に頭がこんがらがっていました。
「いま説明しようとしてたところ。歌そのものは『門にすわって』なんだよ。そしてメロディはぼくならではの発明なんだ」

「歌の名前」と「歌」を別に考えて表にするとすっきりしますね。 (どこだか思い出せなかったのですが「エキスパート C プログラミング」の一節だとの指摘をいただきました。御指摘ありがとうございました)

         | 呼ばれている名前 |  そのもの
 ---------+------------------+------------------
 歌の名前 | タラの目         | すごく歳寄りの男
 歌       | 方法と手段       | 門にすわって

Lisp でも簡単に表現できます。

CL-USER> (setf 方法と手段 '門にすわって)
門にすわって
CL-USER> (setf タラの目 'すごく年寄りの男)
すごく年寄りの男

「呼ばれている名前」を評価すると「そのもの」になり、 クォートをつけると (~'~) 評価されずにシンボルそのものの値になります。

CL-USER> '方法と手段
方法と手段
CL-USER> 方法と手段
すごく年寄りの男
CL-USER> 'タラの目
タラの目
CL-USER> タラの目
門にすわって

つまり、シンボルはふだんのプログラム言語でいう、いわゆる変数としても使えることがわかります。

CL-USER> (setf x 100)
100
CL-USER> 

リスト

Lisp でもっとも良く使うデータ構造です。複数のアトム、もしくはリストを含む事ができます。

:
CL-USER> '(1 2 3)
(1 2 3)
CL-USER> '(+ 2 3)
(+ 2 3)

リストは、アトム、もしくはリストから構成されます(リスト)。

Lisp におけるリストは、 コンスセル (cons cell) という単位で構成されます。 コンスセルは carcdr という二つのポインタを持ちます。 car, cdr はそれぞれ 別のアトム、もしくはリストを参照することができます。

//lispuser.net/files/cons.gif

このコンスセルを連結して、次の図のように並べたものをリストと呼びます。

CL-USER> (cons 1 nil)
(1)
CL-USER> (cons 2 (cons 1 nil))
(2 1)
CL-USER> (cons '+ (cons 2 (cons 1 nil)))
(+ 2 1)

//lispuser.net/files/cons2.gif

正しいリストであるためには、末尾のコンスセルの cdr は NIL でないといけません。 この部分に NIL 以外の値を入れることもできますが、それは正しいリストではなくなり、 リスト処理関数が適用できなくりまるので、あまり使われません。

しかし、コンスセルを一つだけ使って、 car, cdr がそれぞれアトムを指す場合にそのセルをドットペアと呼びます。 これには、二つの値を保持するのにリストだと二つのコンスセルが必要になるところがドットペアだとコンスセルが一つで済むという利点があるため、 あえてこの形式を使う場合があります。

CL-USER> (cons 1 2)     ;; 注: これはリストではなく、ドットペアと呼ばれる形式です
(1 . 2)

リストやドットペアの要素には、car と cdr を組み合わせてアクセスすることができます。

CL-USER> (setf pair (cons 1 2))
(1 . 2)
CL-USER> (car pair)
1
CL-USER> (cdr pair)
2
CL-USER> (setf lst1 (cons '+ (cons 2 (cons 1 nil))))
(+ 2 1)
CL-USER> (car lst1)
1
CL-USER> (cdr lst1)
(2 1)
CL-USER> (car (cdr lst1))
2
CL-USER> (cdr (cdr lst1))
(1)
CL-USER> (car (cdr (cdr lst1)))
1
CL-USER> (cdr (cdr (cdr lst1)))
nil

//lispuser.net/files/list.gif

CL-USER> (setf A (cons 1 nil))
(1)
CL-USER> (setf B (cons 2 A))
(2 1)
CL-USER> (setf C (cons 3 B))
(3 2 1)
CL-USER> (setf D (cons -1 B))
(-1 2 1)

//lispuser.net/files/list2.gif

関数

CL-USER> (defun plus-one (x) (+ x 1))
PLUS-ONE
Cl-USER> (plus-one 10)
11

連想リスト

リストの変種です。リストの要素がリストになっていて、内側のリストの先頭要素を キーとして使うのが普通です。 Lisp にはこの連想リストを操作するための関数が 備わっています。

(キー 関連するもの) ; このようなリストを要素とするリストの事です

((キー1 内容) (キー2 内容) ...) ; こんな見た目になります
CL-USER> (set 記憶 '((白 雪 花) (赤 車 羽 きつね) (緑 植物 たぬき)))
((白 雪 花) (赤 車 羽 きつね) (緑 植物 たぬき)))
CL-USER> (assoc '白 記憶)
(白 雪 花)
CL-USER> (assoc '赤 記憶)
(赤 車 羽 きつね)

ラムダ

通常の関数は、defun で名づけた名前とともに呼び出しますが、 名前のない関数をあらわすのがラムダです。

CL-USER> (defun add1 (x) (+ x 1))
ADD1
CL-USER> (add1 1)
2
CL-USER> (function add1)
#<FUNCTION ADD1 (X) (DECLARE (SYSTEM::IN-DEFUN ADD1)) (BLOCK ADD1 (+ X 1))>
CL-USER> (lambda (x) (+ x 1))
#<FUNCTION LAMBDA (X) (+ X 1)>
CL-USER> ((lambda (x) (+ x 1)) 1)
2

ハッシュテーブル

連想配列と同じく、キーと値を対応させるデータ構造です。 Common Lisp では組み込みデータ型 としてハッシュテーブルがあります。使い方は、以下の通りです。

CL-USER> (setf ハッシュ表 (make-hash-table))
#S(HASH-TABLE :TEST FASTHASH-EQL)
CL-USER> (setf (gethash '赤 ハッシュ表) '(車 屋根 きつね))
(車 屋根 きつね)
CL-USER> (gethash '赤 ハッシュ表)
(車 屋根 きつね)
T

マップ

mapcar!!!

束縛

let とか let* とか。

制御構造

if とか cond とか?

プログラム == データ

プログラムとデータの違いをみてみましょう。 Lisp においては、プログラムもリスト形式で表現されるため、 その違いは評価されるかどうかのみです。

:
CL-USER> (+ 1 2)
3
CL-USER> '(+ 1 2)
(+ 1 2)

実際に、プログラムとして正当なデータを評価してみる事ができます。前にもでてきた eval 関数を使います。

:
CL-USER> (eval '(+ 1 2))
3

できました。さあ、プログラムの構造をコンスセル表記で想像してみましょう。

//lispuser.net/files/image/programs-is-data.png

解釈

では、プログラムを表現しているデータを実行してみます。自作の eval 相当 の関数ですね。小難しく言うと評価器です。 ただし、 eval という関数はもう Lisp に用意されているので、ここでは my-eval という名前にします。

まずは、基本構造を実行してみましょう。

CL-USER> (setf program '(+ 1 2))
(+ 1 2)
CL-USER> (first program)
+
CL-USER> (second program)
1
CL-USER> (third program)
2

ですから、まず先頭要素が + ならば、二番目の要素と三番目の要素を足して みましょう。

:
CL-USER> (defun my-eavl (program)    
           (if (eq (first program) '+)
               (+ (second program) (third program))))
SAMPLE
CL-USER> (my-eval '(+ 1 2))
3

キャッホゥ。解釈できました。ついでに掛算にも対応させてみましょう。

CL-USER> (defun my-eval (program)    
           (if (eq (first program) '+)
               (+ (second program) (third program))
               (if (eq (first program) '*)
                   (+ (second program) (third program)))))
SAMPLE
CL-USER> (my-eval '(+ 1 2))
3
CL-USER> (my-eval '(* 1 2))
2

完璧です。この勢いで四則演算に対応しましょう。 if のみだとどんどんネストが 深くなるので、 cond を使います。

CL-USER> (defun my-eval (program)
           (cond ((eq (first program) '+)
                  (+ (second program) (third program)))
                 ((eq (first program) '-)
                  (- (second program) (third program)))
                 ((eq (first program) '*)
                  (* (second program) (third program)))
                 ((eq (first program) '/)
                  (/ (second program) (third program)))))
MY-EVAL
CL-USER> (my-eval '(+ 10 20))
30
CL-USER> (my-eval '(* 10 20))
200
CL-USER> (my-eval '(/ 30 5))
6

だいぶできてきましたね。が、この評価器には致命的な欠点があります。

CL-USER> (my-eval 100)
ERROR
CL-USER> (my-eval '(+ (* 1 2) (/ 3 1))
ERROR

どちらもエラーになってしまいました。順番に対応していきましょう。 まず前者ですが、数字を入力するとエラーになってしまっています。 数字を評価すると同じ数字になっていましたので、当然我々の my-eval もそ のようにすべきです。数字の他にシンボルや文字列、文字といったデータも 同様でしょう。思い出してください。これらは「アトム」です。つまり、 アトムだったらそのアトムをそのまま返すような処理を追加すればよいのです。

CL-USER> (defun my-eval (program)
           (cond ((atom program)
                  program)
                 ((eq (first program) '+)
                  (+ (second program) (third program)))
                 ((eq (first program) '-)
                  (- (second program) (third program)))
                 ((eq (first program) '*)
                  (* (second program) (third program)))
                 ((eq (first program) '/)
                  (/ (second program) (third program)))))
MY-EVAL
CL-USER> (my-eval 100)
100
CL-USER> (my-eval 'Symbol)
SYMBOL
CL-USER> (my-eval "string")
"string"

一気にアトムに対応できました。次に後者の場合、式の中に式が入っている ケースに対応してみましょう。まずは、エラーになる過程を追ってみます。

CL-USER> (setf program '(+ (* 1 2) (/ 3 1))
(+ (* 1 2) (/ 3 1))
CL-USER> (eq (first program) '+)
T
CL-USER> (second program)
(* 1 2)
CL-USER> (third program)
(/ 3 1)
CL-USER> (+ '(* 1 2) '(/ 3 1)) ; エラーになる
ERROR

ここですね。 + 関数は引数に数値しか取れないのにリストになっています。 本当は (* 1 2) => 2 のように評価してほしいのです。ここで使える関数は… そう、我々の my-eval が使えます。

CL-USER> (+ (my-eval '(* 1 2)) (my-eval '(/ 3 1)))
5

こうすればいいのです。さぁ、my-eval を書き直してみましょう。

CL-USER> (defun my-eval (program)
           (cond ((atom program)
                  program)
                 ((eq (first program) '+)
                  (+ (my-eval (second program)) (my-eavl (third program))))
                 ((eq (first program) '-)
                  (- (my-eval (second program)) (my-eval (third program))))
                 ((eq (first program) '*)
                  (* (my-eval (second program)) (my-eval (third program))))
                 ((eq (first program) '/)
                  (/ (my-eval (second program)) (my-eval (third program))))))
MY-EVAL
CL-USER> (my-eval (+ (* 1 2) (/ 3 1)))
5
CL-USER> (my-eval (+ (* (+ 1 (+ 1 2)) 2) (/ 3 1))) ; もう何個入れ
           子になっていても大丈夫
5

[長い…]

環境

「環境」とはその実行時点でのコンピュータの状態を示す用語です。今回作る Lisp では、環境とはある時点での「変数の束縛」のあつまりです。 あいまいというか良くわからない用語ですが、他に良い用語がないのですが、一般的にいう「場」や「空気」のようなものです。おなじ「シンボル」が 状況によって異なる束縛をもっていることを表すのに使います。

環境: 工場にて
「鉄板!!」 -> 金属製の板のことです

環境: 食堂にて
「鉄板!!」 -> 鉄板焼き等の料理の名称

環境: パチンコ屋にて
「鉄板!!」 -> 確率が高い、安全圏な場合

どうでしょうか、同じシンボル(鉄板)が環境によって異なる意味をもっていますね。これを Lisp で表現してみましょう。

(let ((鉄板 '金属製の板))
   (print 鉄板))

(let ((鉄板 '鉄板焼き))
   (print 鉄板))

(let ((鉄板 '高確率))
   (print 鉄板))

このとき、鉄板というシンボルの意味というか評価結果は、その時の「環境」によってきまると言えます。

このような「環境」を作るにはどうしたら良いでしょうか?実装方法はいくつもありますが、まずは最も単純に 連想リストを使って実装してみましょう。

CL-USER> (setf 環境 '((鉄板 金属製の板) (ベニヤ ベニヤ板)))
((鉄板 金属製の板) (ベニヤ ベニヤ板))
CL-USER> 

そして環境から、シンボルを評価して値取得する関数を作成してみます。

CL-USER> (assoc '鉄板 環境)
(鉄板 金属製の板)
CL-USER> (second *)
金属製の板
CL-USER> (second (assoc '鉄板 環境))
金属製の板
CL-USER> (defun lookup-value (symbol env)
           (second (assoc symbol env)))
LOOKUP-VALUE
CL-USER> 

[くどくなってきた…]

インタプリタソース

(defpackage :minilisp (:use :cl) (:shadow #:eval))
(in-package :minilisp)

(defvar *global-env* (make-hash-table :test #'equal))

(defun lookup-value (symbol &optional env)
  (let ((pair (and env (assoc symbol env))))
    (if pair
      (cdr pair)
      (gethash symbol *global-env*))))

(defun set-value (symbol value &optional env)
  (let ((pair (and env (assoc symbol env))))
    (if pair
       (setf (cdr pair) value)
        (setf (gethash symbol *global-env*) value))
    value))

(defun extend-env (keys values env)
  (append (mapcar #'cons keys values) env))

(defun interpret (sexp env)
  "Lisp インタプリタ本体"
  (cond ((symbolp sexp) (lookup-value sexp env))
       ((atom sexp)    sexp)
       (t
        (case (first sexp)
          ;;; 超必須クォートプリミティブ : 評価をやめて値を返す
          (quote  (second sexp))
          ;;; setq プリミテティブ : まだマクロがないので set + quote にインタプリタ側で展開
          (setq   (set-value (second sexp) (interpret (third sexp) env) env))
          ;;; defun プリミテティブ : まだマクロがないので (defun fname (args) ...) => (setq 'fname (lambda (args) ...)) に展開
          (defun  (set-value (second sexp) (interpret `(lambda ,(third sexp) ,@(nthcdr 3 sexp)) env) env))
          ;;; progn プリミティブ : 最後の値を返す
          (progn  (loop for exp in (cdr sexp)
                        for val = (interpret exp env)
                        finally (return val)))
          ;;; if プリミティブ : 一つ目の式の値によって評価を分岐
          (if     (if (interpret (second sexp) env)
                      (interpret (third sexp) env)
                    (interpret (fourth sexp) env)))
          ;;; ラムダの評価 : 関数を作る、環境を作る
          (lambda (let ((args (second sexp))
                        (body (nthcdr 2 sexp)))
                    #'(lambda (&rest rest)
                        ;;; 新しい環境に変数の束縛を作る
                        (let ((newenv (extend-env args rest env)))
                          ;;; 新しい環境で呼び出す
                          (interpret (cons 'progn body) newenv)))))
          ;;; 関数適用
          (t     (apply (interpret (first sexp) env)
                        (mapcar #'(lambda (e) (interpret e env)) (rest sexp))))))))

(defun eval (sexp)
  "Eval 関数 : ただ評価するだけ"
  (interpret sexp nil))

(defmacro use-cl-functions (&rest rest)
  `(progn ,@(mapcar (lambda (x) `(set-value ',x (function ,x))) rest)))

(defun init ()
  "初期環境構築:ビルトイン関数の登録"
  (setf *global-env* (make-hash-table))
  (use-cl-functions + * / - = < > <= >= car cdr cons list null append nconc eq eql equal))
                        
(defun repl ()
  "対話環境の起動"
  (init)
  (format t "~&Minimal Lisp")
  (loop
   (format t "~&=> ")
   (print (eval (read)))))

性能を見てみましょう。計測用コードは以下の通り。

:
;; for native
(defun fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
(defun tak (x y z) (if (>= y x) z (tak (tak (- x 1) y z) (tak (- y 1) z x) (tak (- z 1) x y))))

;; for interpreter
(defun test-1 ()
  (time
   (flet ((task ()
               (init)
               (eval '(defun fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
               (eval '(fib 30))))
     (task))))

(defun test-2 ()
  (time
   (flet ((task ()
               (init)
               (eval '(defun tak (x y z) (if (>= y x) z (tak (tak (- x 1) y z) (tak (- y 1) z x) (tak (- z 1) x y)))))
               (eval '(tak 18 12 6))))
     (task))))

これで性能を見てみましょう。

:

[SBCL 1.0.0.28 Native]
CL-USER> (time (fib 30))
Evaluation took:
  0.086 seconds of real time
  0.0 seconds of user run time
  0.08 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  0 bytes consed.
832040

CL-USER> (time (tak 18 12 6))
Evaluation took:
  0.002 seconds of real time
  0.0 seconds of user run time
  0.0 seconds of system run time
  0 calls to %EVAL
  0 page faults and
  0 bytes consed.
7

[SBCL 1.0.0.28 自作インタイプタ]
MINILISP> (test-1)
Evaluation took:
  6.105 seconds of real time
  0.77 seconds of user run time
  5.34 seconds of system run time
  [Run times include 0.45 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  420,061,624 bytes consed.
832040
MINILISP> (test-2)
Evaluation took:
  0.14 seconds of real time
  0.0 seconds of user run time
  0.14 seconds of system run time
  [Run times include 0.01 seconds GC run time.]
  0 calls to %EVAL
  0 page faults and
  13,225,632 bytes consed.
7
MINILISP> 

構文木を直接解釈する方式なので、ネイティブコードに比べると非常に遅いことがわかります。 こんなに単純な処理でも、いわゆる LL 言語 Perl や Ruby などよりも遅くなってしまうのです。

[Perl 5.8.8 on coLinux]
% time perl -e 'sub fib { my $n = shift; return ($n<2) ? $n : fib($n-1)+fib($n-2); } fib(20);'
perl -e   0.02s user 0.01s system 86% cpu 0.035 total
% time perl -e 'sub fib { my $n = shift; return ($n<2) ? $n : fib($n-1)+fib($n-2); } fib(30);'
perl -e   0.71s user 2.86s system 88% cpu 4.046 total
% time perl -e 'sub tak { my ($x, $y, $z) = @_; return ($y >= $x) ? $z : tak(tak($x-1,$y,$z), tak($y-1,$z,$x), tak($z-1,$x,$y)); }; tak(18,12,6);'
perl -e   0.11s user 0.01s system 91% cpu 0.131 total
[Ruby 1.8.5 on win32]
def fib (n)
   if n < 2
      n
   else
      fib(n-1)+fib(n-2)
   end
end
def test1 ()
   t1 = Time.now
   fib(30)
   t2 = Time.now
   t3 = t2.to_f - t1.to_f
end
def tak(x,y,z)
   if y >= x
      z
   else
      tak( tak(x-1,y,z), tak(y-1,z,x), tak(z-1,x,y) )
   end
end
def test2 ()
   t1 = Time.now
   tak(18,12,6)
   t2 = Time.now
   t3 = t2.to_f - t1.to_f
end
test1()
=> 3.10
test2()
=> 0.06

この例では Ruby の 2 倍程度の遅さでしょうか。Perl はインタプリタ起動 のハンデがあるので、この数値よりももっと差は多きいです。まぁ、Perl 5 の仮想マシン はかなり最適化されてますし、バイトコードコンパイラも簡単な最適化はしていますので 構文木を素朴に解釈していくインタプリタでは立ち打ちできないのは当然といえば当然でしょう。

そもそも、これはまだ LISP ではありません。マクロがないため、LET のような構文の拡張をしようと思うと defun のようにインタプリタの本体 (interpret 関数) を拡張することになってしまいます。

マクロやコンパイラ、関数と変数の名前空間、パッケージ、などいろんなものがありません。 本物の処理系は偉大です。 Lisp を学ぶときには、その機能をどうやって実装するかを考えてみると面白いでしょう。 LISP は簡単ですが、本当に使いものになる物を作るのは難しいんです。

というわけで、今後はこの Lisp 処理系をいじりながら Lisp を勉強してゆきたいと思います。 次回はマクロ機能を持たせる予定です。

「どこかのハッカーが一週間ほど Lisp と格闘して、"みてくれ!! Lisp をモノにしたぞ!!" と叫ぶ、そんなことがしょっちゅうあるだろうさ。でも、それと本当に使いものになるシステムの間には天と地ほどの差があるんだよ」 ハッカーズより

posted: 2006/12/08 03:54 | permanent link to this entry | Tags: LISP

(top)  (memo)  (rss)