LISPUSER

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

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

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

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

CL-USER> 'それ
それ

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

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

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

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

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

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

:

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

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)

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

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

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)

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

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

((キー1 内容) (キー2 内容) ...) ; こんな見た目になります

CL-USER> (set 記憶 '((白 雪 花) (赤 車 羽 きつね) (緑 植物 たぬき)))
((白 雪 花) (赤 車 羽 きつね) (緑 植物 たぬき)))
CL-USER> (assoc '白 記憶)
(白 雪 花)
CL-USER> (assoc '赤 記憶)
(赤 車 羽 きつね)

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

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

if とか cond とか？

:

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

:

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

では、プログラムを表現しているデータを実行してみます。自作の 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 をモノにしたぞ!!" と叫ぶ、そんなことがしょっちゅうあるだろうさ。でも、それと本当に使いものになるシステムの間には天と地ほどの差があるんだよ」 ハッカーズより