2016年4月18日月曜日

[SICP][Lisp]遅延評価の解釈系の実装

引き続きSICPを読みながら、Common LispでLispインタープリタを作成している。
「4.2.2 遅延評価の解釈系」を参考に、遅延評価できるように修正してみた。

https://github.com/takeisa/LispInCommonLisp/tree/lazy_evaluation

ifの反対のunlessを作って試してみる。

CL-USER> (repl)
LISP>
(define (unless condition usual exceptional)
    (if condition exceptional usual))
OK
LISP> (unless (= 1 0) 'hoge (/ 1 0))
HOGE

引数の(/ 1 0)は評価しないで、'hoge を返している。


cons,car,cdrを使えるようにして、前章のストリームで作成した無限リストを作ってみようとしたが、今の実装では、Common Lispの関数をそのまま使おうとすると、全ての引数をforceするようになっているので、簡単にできない。

5章のレジスタ計算機まで、早めに進みたいので後回しにしよう。

2016年4月9日土曜日

[SICP][Lisp]Common LispでLispインタープリタを書いてみた

SICP 第4章 超言語的抽象を参考にして、Common LispでLispインタープリタを書いてみた。

ソースはこちら。
https://github.com/takeisa/LispInCommonLisp

350行程度になった。
letはまだ実装していない。
言語処理系を実装するのは楽しいなー。

動作例


※evalで評価する式をデバッグ出力している。

フィボナッチ数を求める関数を定義する。
CL-USER> (repl)

LISP> (define (fibonacci n)
    (if (<= n 1)
 n
 (+ (fibonacci (- n 2)) (fibonacci (- n 1)))))
make-lamba parameters: (N)
make-lamba body: ((IF (<= N 1)
                      N
                      (+ (FIBONACCI (- N 2)) (FIBONACCI (- N 1)))))
lambda: (LAMBDA
            ((N) (IF (<= N 1) N (+ (FIBONACCI (- N 2)) (FIBONACCI (- N 1))))))
lambda parameters: (N)
lambda body: ((IF (<= N 1)
                  N
                  (+ (FIBONACCI (- N 2)) (FIBONACCI (- N 1)))))
OK

20番目のフィボナッチ数を求める。
LISP> (fibonacci 10)
t-eval: (FIBONACCI 10)
t-eval: FIBONACCI
t-eval: 10
t-eval: (IF (<= N 1)
            N
            (+ (FIBONACCI (- N 2)) (FIBONACCI (- N 1))))
t-eval: (<= N 1)
t-eval: <=
t-eval: N
t-eval: 1
..snip..
6765