uDiary

◆ [Scheme] というわけで、僕も Scheme もどき処理系（C で 650 行）を書いてみた。

「勉強する前に書け！」 ということで、 Scheme もどき処理系を書いてみた。

きちんとした処理系を書くだけの能力がないことは自覚していて、 だからこそ、ぼちぼち勉強しているつもりなのですが。 じゃあ「きちんとしてないやつなら書けるのか？」というと ……うーん、書いたことがないなぁ。

これは、まずい。というわけで、書いてみた。

• iscm000.tar.bz2: version 0.0.0
• iscm001.tar.bz2: version 0.0.1 (後述)
• iscm002.tar.bz2: version 0.0.2 (可搬性やや改善、同じく後述)

なるべく手を抜けるところは手を抜いて、小さいコードにしたかったんだけど、 500 行は切れなかったよ：

% wc -l iscm0.[hyl] main.c eval.c
  36 iscm0.h
  20 iscm0.l
  28 iscm0.y
 176 main.c
 390 eval.c
 650 合計

iscm というのは、integer くらいしかサポートしていない スキーム（笑）くらいのつもりです。 国際現代音楽協会とは関係ないと思います。

動作例

いちおう、動作サンプルは以下のような感じ：

(display "Hello!\n")

(define x 2)
(define y 3)

(display (+ x y))
(display "\n")

(define f
  (lambda (x y)
    (define pow (lambda (x) (* x x)))
    (+ (pow x) (pow y))))

(display (f x y))
(display "\n")

(set! x 4)
(display (f x y))
(display "\n")

を実行すると：

% ./iscm0 < sample1.scm
Hello!
5
13
25

となります。

(define mkf (lambda ()
              (define ct 0)
              (lambda ()
                (set! ct (+ ct 1))
                (display ct)
                (display "\n"))))

(define gg (mkf))
(define g (mkf))

(g)
(g)
(g)
(gg)
(g)
(gg)

なら、

% ./iscm0 < sample2.scm
1
2
3
1
4
2

です。いわゆるクロージャってやつ？

(define f
  (lambda (x)
    (define f_loop
      (lambda (x result)
        (cond
         ((= x 1) result)
         (else
          (f_loop (- x 1) (* result x))))))
    (f_loop x 1)))

(display (f 2)) (display "\n")
(display (f 3)) (display "\n")
(display (f 5)) (display "\n")

のような、再帰関数も一応動く：

% ./iscm0 < sample3.scm
2
6
120

意図的に手をぬいたとこ

• 最適化？ぜんぜんしてません。
• パースした S 式をいきなり実行しようとします。中間言語とかない。
• 整数しかつかえません。
• 文字列は、使えるとはいい難い。
• すべてのオブジェクトは無限の寿命をもつのですが、ガベージコレクターがありません*1。つまり、常にプロセスが先に死にます（笑）。
• で、デバッグ？これからです。
• エラー処理は…われながら酷いな、こりゃ。

わかってないところ

• レキシカル・スコープって、こーゆーことでいいの？
• ケイゾク。聞き齧ったことがあるだけ。
• マ…ク…ロ…。そのまえに reader をきちんと分離するのかな？（わかってない）

ほかにも、書いているときにはいろいろ思ったような気がするんだけど。 思い出したら書き足そう。

とにかく、いまの僕に書けるものを、なるべく思い込みに基づいて書きました。 「Lisp の必須要素は、えーと、なんだっけ？」というのも調べずに書く（笑）！ 動くものをつくってから、どこがダメなのかを理解していこうと。

これを触りつつ SICP を読んでいくと、よく解りそうだ！

今後は、これを徐々にまともにしていこう。 iscm8 くらいで、見られるものになる筈（←言うだけならタダ！）。 それに、ほんとは、インタプリタじゃなくて、コンパイラが書きたいんだよなぁ。

◆ [Scheme] iscm0: 不等号がない！

できたてほやほやの iscm0 を使いつつ、SICP の練習問題でもやってみるかなと思っ……て……、 あら？

整数の四則演算 (+, -, *, /) と比較演算 (=) は、built-in 関数として実装したのに、 不等号をわすれた！！

ぎぃやぁん！

◆ [Scheme] iscm0: version 0.0.1

しばらく遊べるかなと思ったら、いきなりのバグフィックス。

• iscm001.tar.bz2: version 0.0.1

不等号も欲しいねというのがいっこ。

もういっこは、スコープが変で、 関数のなかからグローバル？（一番外の）環境が見えなかったバグを直した。 ちぃ、これは、わかってたのに、いろいろ書いている途中で劣化してしまったもの。 スコープの理解が変で、実装がまちがっているところは、あるんじゃないかと思っているんだが、 今回のは、単なるミスです。くやしい。

というわけで、SICP の練習問題 1.3 はこんな感じでしょうか：

ex1_3.scm:

(define f
  (lambda (a b c)
    (define g (lambda (x y) (+ (* x x) (* y y))))
    (cond
     ((and (<= a b) (<= a c))
      (g b c))
     ((and (<= b a) (<= b c))
      (g a c))
     (else
      (g a b)))))

(display (f 1 2 3)) (display "\n")
(display (f 4 2 3)) (display "\n")
(display (f 4 5 3)) (display "\n")

iscm0 (version 0.0.1) で動かすには、さらに、

lib4iscm0.scm:

(define and
  (lambda (a b)
    (cond
     (a b)
     (else ()))))

(define not
  (lambda (a)
    (cond
     (a ())
     (else 1))))

(define <=
  (lambda (a b)
    (not (> a b))))

が必要。

実行結果：

% cat lib4iscm0.scm ex1_3.scm | iscm0
13
25
41

lambda の仮引数部の形式を一種類しかサポートしてなくて、 引数を可変個数にできないのが、いきなり目障りになってきた（and が二項しかとれない！）。

(追記：and については、二項の場合しかサポートしていないことよりも、 致命的な問題があります。and のセマンティクスを実現するには、 and は特殊形式である必要があります（筈）。or も同様。SICP 問題 1.6 近辺)

おっと、そうそう。論理については、() が偽、それ以外が真という体系になってます。

◆ [Scheme] iscm0: version 0.0.2

• iscm002.tar.bz2: version 0.0.2

Unnamed union がお行儀わるくて、 gcc でもバージョンによってはコンパイルできないようだった。 他にも、いくつか警告メッセージを頼りに修正した。

やはり、警告メッセージを無視しちゃいけませんでした。